It looks like we had a longer session in the
last lecture, so will try to make it slightly lesser this time. To begin with we are looking
at advance method which will increase the rate of convergence of our iteration method. When we say increase over what we can get
with Jacobi method and Gauss-Seidel method and one of the first methods that were proposed
is what is known as the successive over relaxation method. This method is, goes together with Jacobi
method and Gauss-Seidel method as almost like a basic iterative method, because it is not
very different from those methods. So, the idea of this successive over relaxation is
that, in the general case in an iterative method we have some way of determining x k
plus 1 from x k and there is an increment, we are in essence incrementing in x k by delta
x k to get x k plus 1. We know that in the case of convergent schemes and especially
under asymptotic convergence conditions and we are approaching this solution asymptotically
from one side. So, if you are approaching asymptotically
then that means, that we are taking steps, but may be not taking as big as step as can
be taken and we are taking small steps. So, if you can increase the step size more than
what we think it should be, because we are getting delta x k from the equation and the
amount of delta x k that we get depends on the iteration matrix p and it also depend
on x k. So, that means that delta x k is not constant, the step size is not constant, but
we seem to be every time under estimating that step size. So, is it possible to increase
it by factor and thereby over relax it than what we can do and that is the essence of
this. So, suppose we write x k plus 1 equal to x
k plus omega times delta x k, where delta x k is what we get using our conversions scheme.
So, if you put omega equal to 1 then, we have no over relaxation. So, we are saying that
x k plus 1 is the previous value and whatever your Jacobi method or Gauss-Seidel method
praise this delta x k to be. We are saying that it is only asymptotically approaching
and it can be higher. So, can it be higher by a factor omega? If you say omega is greater
than 1 then, you are over relaxing at every step so it becomes a successive over relaxation
method. So, this relaxation methods are by which you
can find delta x k and you are saying that is more than that by certain amount omega
when omega is greater than 1, for typical problems where you apply Gauss-Seidel method
all though not in all cases, in the case where a is diagonally dominant is good way of saying
it. In such a case you can show that omega can be less than 1 and this modification factor
will not affect it is property of whether it is converging or diverging.
So, the method will remain convergent as long as omega is between 0 and 2. If it is less
than 0 or greater than 2, then it may diverge. So that means, that we can take any value
between these and typically when omega is less than 1, you say it is under relaxation.
When omega is greater than 1 you say it is over relaxation. So when omega is greater
than 1 you are taking a step size which is greater than what should be taken as per the
Jacobi method or the Gauss-Seidel method. When omega is less than 1 you are saying that
it should be less than what it should be taken what is estimated.
If you are trying to speed up the rate of convergence, speed up the number of steps
that are required to get your objective of getting close enough to the true value, then
you would like an over relaxation omega to be greater than 1. But if you suspect, for
example this delta x k estimate itself is subject to errors because you are solving
a set of equations and you are making assumptions because of coupling or non-linearity or making
assumptions about what is the delta x k? That is when you are trying to solve non-linear
algebraic equation or a set of equations, then you could say for the sake of safety,
for the sake of convergence you could say that i will under relax i would not take the
full value that is predicted and only take part of the value.
So, then you could say that i will take omega to be between 0 and 1, you will be under relaxing,
but here are a, x equal to b is a linear equation linear algebraic equations and we do not have
to worry about under relaxation. We can definitely use over relaxation and when a is diagonal
dominant we can take omega to be anything between 1 and 2 and we can do that over relaxation.
So, once you put a value to omega here, then given that you have delta x k determined by
Jacobi method or whatever method. So, if you use Gauss-Seidel method, this is
equivalent to saying that x k equal to m x x k plus 1 equal to m x k minus 1 plus n in
that m is d by omega minus e and n is 1 minus omega by omega times d plus f. Where, d is
the diagonal terms of a and e is the those terms which are below the diagonal and f for
the terms which are above the diagonal. So, with this notation for a given a in a x equal
to b you can directly find m and n as per the Gauss-Seidel method with this extra factor
omega which is added and we take for over relaxation omega to be between 1 and 2 .
So, this is will give us an iteration scheme like this. So, now you have x k plus1equal
to d by omega minus e inverse of this whole thing here and what we would like to say is
that in this case if you put this as x k plus 1 equal to p x k plus q, this p here is different
from the p that you have with g s with the Gauss-Seidel method. What it means is that,
it is convergence rate is affected by the change that you are making and the change
that you are making is omega here. If you take omega to be 1 then this thing
will go to 0 and you will have d by 1 is d and you will get back to Gauss-Seidel method.
If omega is greater than 1, then you have extra influence of the diagonal elements here
and these things here. So, that will mean that you have and iteration matrix, which
is different from what you have it is the Gauss-Seidel method and therefore, it will
have different convergence behavior. Now all though we are putting it like this
in terms of this inverses as before, as in the case of Jacobi method and Gauss-Seidel
method, we do not do matrix inversion directly. This whole thing can be written just like
we wrote in the Gauss-Seidel method except that, we put this a11 x 1 k plus 1 here and
then we have this a 1 1 x 1 k minus omega times this whole thing and what is the omega
times a 1 1 x 1 k plus a 1 2 x 2 play that is all the elements at the previous time step
minus b 1and this whole thing is minus b 1. So, this is b 1 times omega minus this value
and plus this value here. And similarly for x 2 k it is a 2 2 x 2 k
minus omega times this whole thing. Since we know x 1 as the updated value we make use
of the updated value, as for as evaluating as per the successive over relaxation is concerned,
we are adding 1 multiplication here. Omega times this and then this is we can depending
on how it is computed. So, it is either already computed or it is there and this gives a subtraction.
So, and then this whole thing is divided by a 1 1.
So, I can see as a result of this may be 1 or 2 more multiplications per equation and
since you have equation here is like that for us pass matrix you have only certain number
of non 0 components here. The total number of arithmetic operations to go from step k
to step k plus 1, is not very different from that for Jacobi or Gauss-Seidel method and
it varies as may be six n or seven n and like that compare to 5 n for the case are Gauss-Seidel
method or Jacobi method. So, despite putting this extra factor here,
you are only increasing the number of arithmetic operations by n in this. So, it becomes and
instead of factor of 5 you now have factor of 6 or 7 depending on how you compute it
here. That makes it readily implementable as easily implementable, as the Gauss-Seidel
method or Jacobi method. So, in a way it is a small extension to the Gauss-Seidel method.
Just as Gauss-Seidel method can be considered as a small extension to the Jacobi method.
So, this is all in the same family with the same kind of approach solution. Now what does
it did to the convergence rate? We have said that as long as this omega is between 0 and
2, whether it diverges; converges is not changed. Convergence is assured, but at what rate?
Now the rate of convergence is depends as before on the spectral radius of the new iteration
matrix. So, that is involving all this omegas and
it cannot be computed for the general case. For any case of either that may be resulting
from the discretization like this, but for the specific case of a symmetric and positive
definite. So, then optimum value of omega, so the idea
is that this omega varies between 1 and 2 for the case of over relaxation, but the rate
of convergence does not vary monotonically between 1 and 2, it typically goes through
a minimum or the number of iterations needed to reduce a residual by factor of 10. That
value which was saying is asymptotically convergence rate. It reduces as omega is increased it
goes to a minimum and then it is starts again coming back up. So that means, there is an
optimum value of omega at which for a given a matrix and for a given SOR method.
There is in optimum value for which you will have the least number of iterations steps
need to reduce the residual by factor of 10. So, it will have the highest convergence rate.
What the optimum value is not known apriori, but for the specific case of when a is symmetric
in positive definite, then the optimum value for Gauss-Seidel method of SOR where delta
x k is determined as per the Gauss-Seidel method is given by this expression here. So,
this is 2 divided by 1 minus 1 minus rho square root of 1 minus rho square and what is this
rho? it is rho is a spectral density of the optimum value of optimum iteration matrix
think. So, where the Jacobi s o r is optimal, when
this is known when the optimal value of omega is known, then the spectral radius is defined
as omega optimal minus 1. So, this is a spectral radius. For the optimal value of Gauss-Seidel
SOR and this it depends on the spectral radius of this. For the specific case of Laplace equation with Dirichlet boundary conditions, you know
all this things. We know the Eigen values and we know everything about it and the spectral
radius of the Jacobi iteration matrix is cosine pi by m therefore, the optimum value of omega,
the over relaxation parameter for the Gauss-Seidel SOR scheme is given by 2 by 1 plus sine pi
m which is roughly equal to 2 times 1 minus pi by m and therefore, the spectral radius
is given by this minus one. So, that gives us 1 minus 2 pi by m.
Now, how does this is compared with the previous values? For the previous value for the g s
scheme we had rho g s as 1 minus pi square by m square. What do we have here? We have 1 minus 2 pi
by m and what is significant is that in the case of the spectral radius for Gauss-Seidel
it is pi square by m square and here it is m and what is m? m is the number of divisions
in the x direction and n the number of equations is the number of divisions in the x direction
times the number of divisions in the y direction because that gives you the total number of
grid points. So, in the case where the number divisions
in the x direction and y direction are the same, this m is equal to square root of n,
where as in the case of Gauss-Seidel method without SOR m is you had m square here so,
it is proportion to m. Now what does that mean? That for large m this 2 pi by m is smaller
than pi square by m square so that means that, and the spectral radius here is 1 minus this
value. So, this value is higher than the spectral radius is smaller. When spectral radius is
smaller the rate of convergence is faster. So, for large values of m therefore we can
expect the successive over relaxation method of the Gauss-Seidel think to be faster than,
what it is for the simple Gauss-Seidel method. So, for large value of m and in the asymptotic
limit, the number of iterations require to reduce error or residual by in order magnitude
varies as square root of n, where n is the number of equations or number of grid points
and the total number of arithmetic operations required to reduce error by a factor of 10
varies as, n raise power 3 by 2 or enter power 1.5 and this value varies as n square for
Gauss-Seidel method so, that means that the arithmetic number of multiplications or divisions,
is reduce from constant times n square to constant times n to power 1.5 or square root
of n cubed. How significant is it? If you take million
grid points then n square is million square. So, 10 to the power 12 and n to the power
1.5 is million times square root of million. So, that is 10 to the power 3. So, that is
10 to the power 9. So, that means, that instead of taking 10 to the power 12 number of multiplications
you are taking 10 power 9 number of multiplications. So, that is multiplicative factor of 1000.
So that means that, s o r method is almost 1000 times faster than the non SOR Gauss Seidel
method. So, that is a kind of computation advantage we can get, if we were using the
optimal value of omega. Optimal value of omega is known only for set in special cases.
If you want to find out for the true case then you have to do much more and you have
to known the all the Eigen values, and the determination of Eigen values for a general
matrix itself will take n cube number of mathematical operations so that means that, we cannot look
at we cannot say that let us take the matrix and let us find the Eigen values and then
try to choose try to find the best optimal value all that is not possible because Eigen
value determination is take itself will take n cube number of operations. So, that is why
only for certain class of problems under certain cases we know it is a convergence rate and
we know that it can converge very fast by significant margin compares to the Gauss-Seidel
method. So, in a general case the optimum value of
omega changes with a, with the matrix. So,1 may need to estimate numerically. So, that
is you do for 50 equations and you see by how much by what factor the residual has decreased
for a given value of omega. For example, you take omega to be 1.5 and now you do another
50 with omega equal to1.6 and see whether that residual reduction factor has increased
or decreased. If their residual reduction factor rate is decreased, that is; if it has
taken the amount of reduction is more than what you had with 1.5 so then that means that
may be you can go to 1.7 and then you keep on going like that until you hit the reverse
trend. So, that is now you take 1.8 and you find
that it has not reduced in the 50 iterations by as much as it has reduce with value 1.7.
Then the optimal values between 1.7 and 1.8, now you take you do another 50 iterations
with 1.75 and then try to locate that kind of thing and then you can finally, get an
estimate if not the exact value you can get an estimate value of this and then use that
value to continue to drive the residual down to you are decide value.
So, that is how you can make use of this. But all this is in a way theoretical because
it takes certain number of iterations before you can get into the asymptotic convergence
limit and it is under the asymptotic convergence limit, will you have good success with the
determination of the optimal value. So, the overall margin may not be like 1000
fold it may be like 10 fold it may be like 5 fold, but still it is definitely worth it.
So, SOR method is a simple extension of the Gauss-Seidel method and for the class of Laplaces
type of equations, Parson type of equations, diagonal dominant conditions it is it can
be use very quickly very effectively to improve the rate of convergence.
In the next lecture we look at other methods having different kinds of philosophies for
increasing rate of convergence over these basic methods.