WEBVTT
Kind: captions
Language: en
00:00:24.570 --> 00:00:32.130
Hello friends, so welcome to the lecture on
iterative methods . So, in past few lectures
00:00:32.130 --> 00:00:38.910
we have learnt about singular value decomposition,
least square approximation and their analysis
00:00:38.910 --> 00:00:46.140
in terms of singular values .
So, now in next few lectures we will learn
00:00:46.140 --> 00:00:52.350
another method for solving linear system of
equations, but by using iterative methods.
00:00:52.350 --> 00:00:58.210
So, in the beginning of this course we have
learnt direct method for solving linear systems
00:00:58.210 --> 00:01:07.460
. Some of them are like Gaussian elimination
and then lu decomposition, like in lu decomposition
00:01:07.460 --> 00:01:15.200
we write the coefficient matrix a in terms
of 2 matrices product of 2 matrices L and
00:01:15.200 --> 00:01:21.590
u, where L is a lower triangular matrix and
U is an upper triangular matrix and then by
00:01:21.590 --> 00:01:31.240
using the forward substitutions and then backward
substitutions we solve the system of equations.
00:01:31.240 --> 00:01:39.350
Now in the category of iterative methods we
can solve the square linear system means we
00:01:39.350 --> 00:01:46.080
are having n equations in n unknown.
So, iterative methods for Ax equals to b begin
00:01:46.080 --> 00:01:53.950
with an approximation to the solution let
us say x 0, which is the initial solution
00:01:53.950 --> 00:02:01.400
and then seek to provide a series of improved
approximations like x 1 x 2 up to like in
00:02:01.400 --> 00:02:07.539
this way that converts to the exact solution
or somehow we reach near to the exact solution
00:02:07.539 --> 00:02:17.410
. These iterative methods are quite popular
in engineering for engineers because we are
00:02:17.410 --> 00:02:26.100
looking for the approximations and once we
are having a required precision means a marginal
00:02:26.100 --> 00:02:32.180
error between the exact solution and the sequence
of approximation then we can stop.
00:02:32.180 --> 00:02:38.950
So, these are in this way we can save the
time or computation for solving the linear
00:02:38.950 --> 00:02:45.850
system, more over when we are solving especially
partial differential equation using some numerical
00:02:45.850 --> 00:02:51.610
methods , we encounter the large and sparse
systems.
00:02:51.610 --> 00:02:57.760
We will discuss what we mean by the sparse
system and these iterative methods are quite
00:02:57.760 --> 00:03:02.480
useful , when we are solving the large and
sparse system when compared to the direct
00:03:02.480 --> 00:03:07.220
method.
A general form of an iterative methods for
00:03:07.220 --> 00:03:15.000
solving a n by n linear system Ax equals to
b can be seen in this way x k plus 1 means
00:03:15.000 --> 00:03:22.440
the approximation of the solution in k plus
1 iteration equals to a matrix p which will
00:03:22.440 --> 00:03:31.490
be n by n matrix into the solution in kth
iteration plus a n by n vector n by 1 vector
00:03:31.490 --> 00:03:37.340
q .
So, here the matrix p is called a iteration
00:03:37.340 --> 00:03:42.820
matrix, there are different schemes next couple
of lectures we are going to discuss three
00:03:42.820 --> 00:03:50.280
different schemes and they differ in the process
of computing the iteration matrix and the
00:03:50.280 --> 00:03:57.090
vector q from the input data that is the coefficient
matrix a and from the right hand side vector
00:03:57.090 --> 00:04:06.430
b. So, from these data a and b we will compute
our iteration matrix p and the vector q and
00:04:06.430 --> 00:04:12.060
then using this iteration process we will
find out the sequence of approximations .
00:04:12.060 --> 00:04:20.840
So, first we will take the Jacobi method , so
the Jacobi method is the simplest iterative
00:04:20.840 --> 00:04:27.389
method for solving a square linear system
Ax equals to b square means our matrix a is
00:04:27.389 --> 00:04:35.100
a square matrix this method use the concept
of simultaneous displacements .
00:04:35.100 --> 00:04:42.221
We can write a n by n matrix a as the sum
of a lower triangular matrix let us say L
00:04:42.221 --> 00:04:51.690
a diagonal matrix D and an upper triangular
matrix u. So, if you are you take this 3 by
00:04:51.690 --> 00:04:58.850
3 matrix then I can write this equals to this
matrix L which is a lower triangular matrix
00:04:58.850 --> 00:05:03.321
plus a diagonal matrix D plus an upper triangular
matrix U .
00:05:03.321 --> 00:05:15.700
Now, how to drive the Jacobi iterations .
So, I am talking about Jacobi method consider
00:05:15.700 --> 00:05:51.030
the system Ax equals to b where A is a n by
n matrix . So, now, you are having Ax equals
00:05:51.030 --> 00:06:00.660
to b write A as the sum of 3 matrices L, D
and U lower triangular triangular lower triangular
00:06:00.660 --> 00:06:09.090
diagonal and upper triangular into x equals
to b or here write it like DX equals to minus
00:06:09.090 --> 00:06:18.560
L plus U X plus b. So, what I have done I
have taken this L and U in the right hand
00:06:18.560 --> 00:06:36.750
side , or I can write x equals to minus D
inverse L plus U x plus D inverse into b and
00:06:36.750 --> 00:06:44.730
set your iterations in this way .
So, x at k plus 1 iteration can be given by
00:06:44.730 --> 00:07:00.290
minus D inverse L plus U x at kth iteration
plus D inverse b, which is equals to the general
00:07:00.290 --> 00:07:14.039
iterative system p into x k plus a column
vector q . So, here iteration matrix P is
00:07:14.039 --> 00:07:28.520
minus D inverse L plus U and the column vector
q is D inverse into b . So, this is our Jacobi
00:07:28.520 --> 00:07:49.260
method if we take a means how to solve a system.
So, consider a 3 by 3 system
00:07:49.260 --> 00:08:09.010
a 1 1 x 1 plus a 1 2 x 2 plus a 1 3 x 3 equals
to b 1 a 2 1 x 1 plus a 2 2 x 2 plus a 2 3
00:08:09.010 --> 00:08:23.140
x 3 equals to b 2 a 3 1 x 1 plus a 3 2 x 2
plus a 3 3 x 3 equals to b 3 .
00:08:23.140 --> 00:08:37.810
. So, now, by the Jacobi method I can write
a 1 1 x 1 equals to b 1 minus a 1 2 x 2 minus
00:08:37.810 --> 00:08:45.180
a 1 3 x 3. So, this I am writing from the
first equation from the second equation I
00:08:45.180 --> 00:08:58.130
can write a 2 2 x 2 equals to b 2 minus a
2 1 x 1 minus a 2 3 x 3 and from the third
00:08:58.130 --> 00:09:11.570
equation I can write a 3 3 x 3 equals to b
3 minus a 3 1 x 1 minus a 3 2 x 2 .
00:09:11.570 --> 00:09:20.790
Now, for setting the iterations what I will
do the same system I can write x 1 equals
00:09:20.790 --> 00:09:38.540
to 1 upon a 1 1 provided a 1 1 is not 0, b
1 minus a 1 2 x 2 minus a 1 3 x 3 . Similarly,
00:09:38.540 --> 00:09:49.540
I can write from the second line x 2 equals
to 1 upon a 2 2 b 2 minus a 2 1 x 1 minus
00:09:49.540 --> 00:10:07.310
a 2 3 x 3 and then x 3 equals to 1 upon a
3 3 b 3 minus a 3 1 x 1 minus a 3 2 x 2 .
00:10:07.310 --> 00:10:19.500
So, now set this at left hand side at k plus
1 iteration and in the right hand side take
00:10:19.500 --> 00:10:35.890
everything at kth iteration . So, this is
the iterative equations for Jacobi method
00:10:35.890 --> 00:10:41.410
for a 3 by 3 system .
When I introduce you about Jacobi method I
00:10:41.410 --> 00:10:48.920
told you this method is a method of simultaneous
displacement, why I told it because here you
00:10:48.920 --> 00:10:57.491
can see that for finding k plus 1 for each
component x 1 x 2 x 3 for each variable I
00:10:57.491 --> 00:11:04.800
am using the value of these variables from
the previous iteration. So, what I am doing
00:11:04.800 --> 00:11:11.640
simultaneously for getting the value at k
plus 1 iteration, I am using the value of
00:11:11.640 --> 00:11:17.790
kth iteration . So, now, we will take one
example and we will solve this example.
00:11:17.790 --> 00:11:26.470
Using the Jacobi method, so, so let us take
an example .
00:11:26.470 --> 00:11:55.910
Solve the system of equation 4 x 1 plus 2
x 2 plus 3 x 3 equals to 8 3 x 1 minus 5 x
00:11:55.910 --> 00:12:17.500
2 plus 2 x 3 equals to minus 14 and minus
2 x 1 plus 3 x 2 plus 8 x 3 equals to 27 .
00:12:17.500 --> 00:12:36.160
and solve this using Jacobi iterative method
. So, here I am having x 1 equals to 1 upon
00:12:36.160 --> 00:12:52.690
4 8 minus 2 x 2 minus 3 x 3 ok. So, this is
my first equation and it is at k plus 1 iterate
00:12:52.690 --> 00:13:02.330
it is at k and it is kth iteration , similarly
x 2 at k plus 1 iteration can be obtained
00:13:02.330 --> 00:13:16.339
minus 1 upon 5 minus 14 minus 3 x 1 minus
2 x 3 and both are at kth iteration number
00:13:16.339 --> 00:13:24.880
k .
similarly x 3 at k plus 1 iteration is given
00:13:24.880 --> 00:13:39.990
as 1 upon 8 27 plus 2 of x 1 and this x 1
in kth iteration minus 3 x 2 at kth iteration
00:13:39.990 --> 00:13:50.290
. So, this is the initially scheme if I take
the initial solution x 0 x 1 0 equals to x
00:13:50.290 --> 00:14:00.760
2 0 equals to x 3 0 equals to 0 means my initial
solution is 0 0 0 transpose which is my initial
00:14:00.760 --> 00:14:11.480
x then what I have.
My x 1 1 will become 1 upon 4 into 8 minus
00:14:11.480 --> 00:14:24.959
0 minus 0. So, 2 x 2 1 will become minus 1
upon 5 minus 14. So, this will become 2 point
00:14:24.959 --> 00:14:46.380
8 and then x 3 1 will become 1 upon 8 into
27. So, it will be 3 point 3 and then 7 5,
00:14:46.380 --> 00:14:52.690
so this is the initial value of x 1 x 2 x
3 at first iteration.
00:14:52.690 --> 00:15:00.080
so if I go in the same way in the second iteration
I got x 1 as minus 1 point 9 3 1 x 2 as 5
00:15:00.080 --> 00:15:09.760
point 3 5 0 and x 3 as 2 point 8 2 5 . If
we need a solution correct up to 3 decimal
00:15:09.760 --> 00:15:15.570
places then we need to calculate this sequence
of values and if we go in the same way in
00:15:15.570 --> 00:15:20.140
the third equation x 1 will be obtained like
this x 2 will be this 1.
00:15:20.140 --> 00:15:28.910
And x 3 will be 0 point 8 8 6 in fourth iteration
continuing in the same manner in twenty second
00:15:28.910 --> 00:15:34.310
iteration value will be like this in twenty
third iteration value will be like this still
00:15:34.310 --> 00:15:40.690
you can see we are having not much flexibility
in the value of x 2, but in the value of x
00:15:40.690 --> 00:15:46.190
1 and x 2 .
Moving continuing in the same way we see in
00:15:46.190 --> 00:15:56.060
the forty fifth iteration x 1 comes out to
be minus 1 x 2 is 3 and x 3 is 2 which remains
00:15:56.060 --> 00:16:03.250
same in 46 iteration, so it is my exact solution.
So, we have taken 46 iteration for converging
00:16:03.250 --> 00:16:14.800
to the exact solution from the sequence of
approximations and this is the Jacobi method.
00:16:14.800 --> 00:16:20.950
My next method in this category is gauss seidel
method which is a bit better when compared
00:16:20.950 --> 00:16:28.860
to the to Jacobi method in terms of convergence.
So, the gauss seidel method is a variant of
00:16:28.860 --> 00:16:34.459
the Jacobi method that usually improves the
rate of convergence by using successive displacement
00:16:34.459 --> 00:16:45.029
in Jacobi we have used the simultaneous
displacement. So, here we will use successive
00:16:45.029 --> 00:16:51.180
displacement , just recall the iterative scheme
of the Jacobi method in the earlier example.
00:16:51.180 --> 00:16:57.720
So, this was the iterative scheme of the Jacobi
method in the example which we have taken
00:16:57.720 --> 00:17:04.480
in case of Jacobi method. So, if you observe
here I have calculated from the first equation
00:17:04.480 --> 00:17:12.049
x 1 8 k plus 1 iteration when I am calculating
x 2 in k plus 1 iteration using the jacobi
00:17:12.049 --> 00:17:22.339
method I am using the approximation which
I have obtained for x 1 and x x 3 in kth iteration
00:17:22.339 --> 00:17:26.169
.
However if you observe since I have calculated
00:17:26.169 --> 00:17:32.129
x 1 in k plus 1 iterations, so I am having
a more updated value of this x 1 here when
00:17:32.129 --> 00:17:38.221
I am calculating x 2. Similarly when I am
calculating x 3 I am having more updated value
00:17:38.221 --> 00:17:46.259
of x 1 and x 2 those are from k plus 1 iteration;
however, in Jacobi method I am using the values
00:17:46.259 --> 00:17:51.700
from the kth iteration.
So what I can do instead of using the old
00:17:51.700 --> 00:17:58.150
values I can use the more updated values and
in that manner I can have a faster convergence.
00:17:58.150 --> 00:18:04.029
So, in gauss seidel method we use such type
of updated values.
00:18:04.029 --> 00:18:19.169
So, if we see the derivation of this method
then I am having gauss seidel method .
00:18:19.169 --> 00:18:32.200
So, again I am having n by n system ax equals
to b I will write matrix as the sum of 3 matrices
00:18:32.200 --> 00:18:40.309
L D and U, where L is lower triangular D is
diagonal and U is an upper triangular matrix
00:18:40.309 --> 00:18:48.899
into x equals to b .
Now, in this method what I will do I will
00:18:48.899 --> 00:18:57.669
take D plus L here and what I will take I
will take minus U into x in the right hand
00:18:57.669 --> 00:19:09.600
side. So, from here I can write x equals to
minus D plus L inverse into U into x plus
00:19:09.600 --> 00:19:20.010
D plus L inverse into b and the iterative
scheme can be set like this x at k plus 1
00:19:20.010 --> 00:19:25.049
means in the left hand side I am taking the
value in k plus 1 iteration , which equals
00:19:25.049 --> 00:19:39.330
to minus D plus L inverse U into x at kth
iteration plus D plus L inverse into b .
00:19:39.330 --> 00:19:50.859
So, this is the iterative scheme of the gauss
seidel method. So, here if you check the iteration,
00:19:50.859 --> 00:20:02.380
iteration matrix p comes out to be minus D
plus L then inverse of this sum U this is
00:20:02.380 --> 00:20:12.549
the iteration matrix p and the vector q is
D plus L inverse into b.
00:20:12.549 --> 00:20:25.231
. So, if you again take a 3 by 3 system like
a 1 1 x 1 plus a 1 2 x 2 plus a 1 3 x 3 equals
00:20:25.231 --> 00:20:45.779
to b 1 a 2 1 x 1 plus a 2 2 x 2 plus a 2 3
x 3 equals b 2 and a 3 1 x 1 plus a 3 2 x
00:20:45.779 --> 00:20:56.779
2 plus a 3 3 x 3 equals to b 3 . So, if I
need solve this system using the gauss seidel
00:20:56.779 --> 00:21:05.889
method then my iterative scheme will comes
like this . So, x 1 at k plus 1 iteration
00:21:05.889 --> 00:21:24.999
will be 1 upon a 1 1 b 1 minus a 1 2 x 2 at
kth iteration minus a 1 3 x 3 at kth iteration.
00:21:24.999 --> 00:21:36.850
Then I will take x 2 at k plus 1 iteration
this will become 1 upon a 2 2 b 2 minus a
00:21:36.850 --> 00:21:43.450
2 1 and please note that this is the change
from the Jacobi method , earlier in Jacobi
00:21:43.450 --> 00:21:49.600
method I have taken x 1 at kth iteration,
but here since I am having x 1 in k plus 1
00:21:49.600 --> 00:22:01.179
iteration available with me. So, I will have
x 1 at k plus 1 iteration minus a 2 3 x 3
00:22:01.179 --> 00:22:10.100
at kth iteration , and then x 3 in k plus
1 iteration this will become 1 upon a 3 3
00:22:10.100 --> 00:22:25.179
b 3 minus a 3 1 and I am having x 1 at k plus
1 iteration minus a 3 2 x 2 at k plus 1 iteration
00:22:25.179 --> 00:22:32.700
. Because now I am having x 1 and x 2 both
available at k k plus 1 iteration , so this
00:22:32.700 --> 00:22:40.370
is the scheme of the gauss seidel method.
So, consider the same example which we have
00:22:40.370 --> 00:22:46.840
taken earlier in the case of Jacobi method.
So, we will solve the same example using the
00:22:46.840 --> 00:22:53.850
gauss seidel method. So, according to whatever
just I have told I have told you according
00:22:53.850 --> 00:23:02.179
to that iterative process my iterative equations
becomes like this. So, x 1 at k plus 1 iteration
00:23:02.179 --> 00:23:08.889
will be 1 upon 4 8 minus 2 x 2 k minus 3 x
3 k which is similar as in case of Jacobi
00:23:08.889 --> 00:23:14.330
method .
Then I am having x 2 at k plus 1 iteration
00:23:14.330 --> 00:23:23.119
it will become 1 upon minus 5 minus 14 minus
3 x 1 k plus 1. So, please note this 1 this
00:23:23.119 --> 00:23:31.639
is the change from the Jacobi method minus
2 x 3 at kth iteration x 3 at k plus 1 iteration
00:23:31.639 --> 00:23:38.860
will become 1 upon 8 27 plus 2 x 1 k plus
1 minus 3 x 2 k plus 1.
00:23:38.860 --> 00:23:47.499
So, in this way if I start with 0 0 0 means
initial case for x 1 0 for x 2 0 and for x
00:23:47.499 --> 00:23:56.120
3 0 then , in the first iteration my x 1 become
becomes 2 x 2 becomes 4 and x 3 becomes 2
00:23:56.120 --> 00:24:04.299
point 3 7 5. Then in the second iteration
x 1 will become minus 1 point 7 8 1 x 2 becomes
00:24:04.299 --> 00:24:13.580
2 point 6 8 1 x 3 becomes 1 point 9 2 4. In
third equation x 1 becomes 0 point 7 8 4 x
00:24:13.580 --> 00:24:22.190
2 becomes 3 point 0 9 9 and x 3 becomes 2
point 0 1 7, these are the values of x 1 x
00:24:22.190 --> 00:24:27.620
2 x 3 in the fourth iteration.
Continuing in the same manner in ninth iteration
00:24:27.620 --> 00:24:37.220
we observed that x 1 is minus 1 x 2 is 3 x
3 is 2 in tenth iteration x 1 is minus 1 x
00:24:37.220 --> 00:24:44.639
2 is 3 x 3 is 2 which is same as we have obtained
in the ninth iteration, when we are taking
00:24:44.639 --> 00:24:48.010
accuracy up to 3 places after the decimal
.
00:24:48.010 --> 00:24:56.409
So, this is a actually the exact solution
also so what we have observed in Jacobi scheme.
00:24:56.409 --> 00:25:05.299
We have taken 46 iterations for converging
to this solution ; however, in the gauss seidel
00:25:05.299 --> 00:25:13.120
method we have obtained the same solution
means solution with same accuracy just in
00:25:13.120 --> 00:25:19.190
10 iterations. So, in this way we can say
the gauss seidel method is a better variant
00:25:19.190 --> 00:25:28.179
of the jacobi method , because it makes the
usage of successive displacements more
00:25:28.179 --> 00:25:34.679
updated values .
So, in this lecture we have learned the two
00:25:34.679 --> 00:25:41.899
iterative schemes those are very basic schemes
one is the Jacobi method, and the other one
00:25:41.899 --> 00:25:48.509
is gauss seidel method . In the next lecture
we will learn one more scheme called successive
00:25:48.509 --> 00:25:54.102
over relaxation, and then we will discuss
the convergence criteria and few results about
00:25:54.102 --> 00:26:03.090
the convergence of these three schemes, and
then we will go to non-stationary iterative
00:26:03.090 --> 00:26:12.450
methods like steepest descent conjugate gradients
and other krylov subspace methods for solving
00:26:12.450 --> 00:26:37.999
large and sparse linear systems so.
Thank you very much.