Jacobi iterative method

The Jacobi method is a iterative method of solving the square system of linear equations.

1. Solving System of Equations using Jacobi Iterative Method Luckshay Batra [email protected]

2. About the Method The Jacobi method is a iterative method of solving the square system of linear equations. This methods makes two assumptions (i) the system given by has a unique solution and (ii) the coefficient matrix A has no zeros on its main diagonal, namely, a 11 , a 22 , a 33 are non-zeros. Basic Idea of the Method : In Jacobi we solve these equations for x 1 , x 2, x 3. We solve I st equation for x 1 , II nd equation for x 2 , ans so on to obtain the rewritten equations as : Then make an initial guess of the solution . Substitute these values into the right hand side the of the rewritten equations to obtain the first approximation This accomplishes one iteration. In the same way, the second approximation is computed by substituting the first approximation’s x-values into the right hand side of the rewritten equations. By repeated iterations, we form a sequence of approximations For each generate the components generate the components of from by for i=1,2,3,... 1

3. Jacobi Method in Matrix Form : Consider to solve nXn size system of linear equations Ax=b with We split A into D x = (L + U )x + b Ax=b is transformed into (D-L-U)x=b, Assume D -1 exists and x (k+1) =D -1 (L+U)x (k) +D -1 b 2 or x (k+1) =Hx (k) +c Then, x=D -1 (L+U)x+D -1 b And the matrix form of Jacobi iterative method is where H=D -1 (L+U) and c=D -1 b. k=1,2,3,... Limitation of the Method Inflexible : For many matrices they don't converge. In general these methods are applicable only for special matrices something like “strong diagonal" or matrices with non-zero diagonal entries. Even if they converge, they find only one solution. Usually they perform badly for degenerate matrices (we just learned them for regular square matrices, but again, there are generalizations). Large Set-Up Time : The Jacobi method cannot immediately begin producing results. Before it can begin its iteration, a matrix −D −1 (L+U) must be computed. For large input matrices, this may not be a trivial operation, as it takes O(n2) time to perform this matrix multiplication. The result is a significant lag before any results can be output.

4. 3 Algorithm Step 1 : Input the coefficient matrix “A”, vector “b”, tolerance level “tol”, initial approximation “x”, number of iterations “n”. Step 2 : Step 3 : Decompose the coefficient matrix into Diagonal Matrix “D”, Lower Triangular Matrix “L” and Upper Triangular Matrix “U”. Calculate the values of H= −D −1 (L+U) and c= D −1 b . Step 4 : For k = 1, k ≤ n, do steps 5,6,7. Step 5 : x (k+1) =H*x (k) +c Calculate and B=max|x (k+1) - x (k) | Step 6 : Step 7 : If B<tol, then Output : “Method Successful.” Output : “ Condition max|x (k+1) - x (k) | < tol was met after k iterations.” Output : Solution of system of equations after k iterations. End. Else, calculate the next iteration k=k+1. Step 8 : If B>tol or k>n Output : “Maximum number of iterations reached without satisfying tolerance condition.” Output : Value of x for k iterations performed.

5. 4 Matlab Code Function Code : function jacobi(A, b,tol,x,n) D=diag(diag(A)); L=tril(-A,-1); U=triu(-A,1); H=inv(D)*(L+U); c=inv(D)*b; k=1; while k<=n x(:,k+1)=H*x(:,k)+c; B=max(abs(x(:,k+1)-x(:,k))); if B<tol disp('Jacobi Method was successful') disp('Condition max|x^(k+1)-x^(k)|<tol was met after k iterations'); disp(k); disp('x = ');disp(x(:,k+1)); break end k = k+1; end if B>tol||k>n disp('Maximum number of iterations reached without satisfying tolerance condition:') disp(x'); end Program Code : disp('Jacobi Method for Solving System of Linear Equations') A=input('Enter the coefficient matrix A : '); b=input('Enter the right hand side vector b : '); tol=input('Enter tolerance level : '); x=input('Enter initial approximation : '); n=input('No. of iterations : '); jacobi(A,b,tol,x,n)

6. Examples 1. Consider the system of equations 0.2x 1 + 0.1x 2 +x 3 +x 4 = 1 0.1x 1 + 4x 2 -x 3 +x 4 - x 5 = 2 x 1 - x 2 + 60x 3 -2x 5 = 3 x 1 + x 2 + 8x 4 +4x 5 =4 -x 2 -2 x 3 +4x 4 +700x 5 =5 with initial guess x (0) =[0000 0] T . Tolerance = 0.00005 Solution in Matlab 2 4 700] >> jacobimethodfinalinputsolve Jacobi Method for Solving System of Linear Equations Enter the coefficient matrix A : [0.2 0.1 1 1 ; 0.1 4 -1 1 -1 ; 1 -1 60 -2 ; 1 1 8 4 ; -1 - Enter the right hand side vector b : [ 1 ; 2 ; 3 ; 4 ; 5 ] Enter tolerance level : 0.00005 Enter initial approximation : [ 0 ; 0 ; 0 ; 0 ; 0] No. of iterations : 91 Jacobi Method was successful Condition max|x^(k+1)-x^(k)|<tol was met after k iterations 91 x = 7. 8 597 0.4229 -0.0736 -0.5406 0.0106 2. Consider the system of equations 2x 1 - x 2 = 7 -x 1 + 2x 2 - x 3 = 1 -x 2 + 2x 3 =3 with initial guess x (0) =[0 0 0] T . Tolerance = 1x10 -4 Solution in Matlab >> jacobimethodfinalinputsolve Jacobi Method for Solving System of Linear Equations Enter the coefficient matrix A : [2 -1 0 ; -1 2 -1 ; 0 -1 2] Enter the right hand side vector b : [7 ; 1 ; 3] Enter tolerance level : 0.0001 Enter initial approximation : [0 ; 0 ; 0] No. of iterations : 100 Jacobi Method was successful Condition max|x^(k+1)-x^(k)|<tol was met after k iterations 31 x = 6. 4 999 5.9998 4.4999 5

7. 3. Consider the system of equations 2.55509x 1 + 0.85822x 2 + 0.92679x 3 + 0.23732x 4 + 0.17628x 5 = 0.66360 0.38558x 1 + 2.55646x 2 + 0.40726x 3 + 0.88843x 4 + 0.89019x 5 = 0.04431 0.44825x 1 + 0.37596x 2 + 2.21124x 3 + 0.61538x 4 + 0.61754x 5 = 0.00939 0.53346x 1 + 0.29330x 2 + 0.23489x 3 + 2.51195x 4 + 0.57504x 5 = 0.48425 0.33918x 1 + 0.58728x 2 + 0.93330x 3 + 0.45368x 4 + 2.98108x 5 = 0.66024 with initial guess x (0) =[0.21771 0.08108 0.65971 0.68427 0.72107] T . Tolerance = 4x10 -3 Solution in Matlab >> jacobimethodfinalinputsolve Jacobi Method for Solving System of Linear Equations Enter the coefficient matrix A : [ 2.55509 0.85822 0.92679 0.23732 0.17628 ; 0.38558 2.55646 0.40726 0.88843 0.89019 ; 0.44825 0.37596 2.21124 0.61538 0.61754 ; 0.53346 0.29330 0.23489 2.51195 0.57504 ; 0.33918 0.58728 0.93330 0.45368 2.98108 ] Enter the right hand side vector b : [0.66360 ; 0.04431; 0.00939; 0.48425; 0.66024] Enter tolerance level : 0.00001 Enter initial approximation : [0.21771; 0.08108; 0.65971; 0.68427; 0.72107] No. of iterations : 80 Jacobi Method was successful Condition max|x^(k+1)-x^(k)|<tol was met after k iterations 67 x = 0. 3 252 -0.1265 -0.1331 0.0968 0.2363 6