[Content_Types].xml
_rels/.rels
matlab/document.xml
matlab/output.xml
metadata/coreProperties.xml
metadata/mwcoreProperties.xml
metadata/mwcorePropertiesExtension.xml
metadata/mwcorePropertiesReleaseInfo.xml
Iterative Methods: Gauss-Seidel Method In this livescript, you will learn how To use the Gauss-Seidel method to solve systems of linear equations One issue with the Jacobi method is that because [N] is the matrix of all the off-diagonal elements, the updated values of x_{i} are not used in the computation of the next iterate. To see what I mean by this, let’s use an iterative method to solve the system of equations 2x-3y+5z=10 4x+7y-2z=-5 2x-4y+25z=31 Equation 1. again. For the Jacobi method, the iterative procedure is given by \pmatrix{2 & 0 & 0 \cr 0 & 7 & 0 \cr 0 & 0 & 25}
\pmatrix{x^{(k+1)}_{1} \cr x^{(k+1)}_{2} \cr x^{(k+1)}_{3}}
=
–
\pmatrix{0 & -3 & 5 \cr 4 & 0 & -2 \cr 2 & -4 & 0}
\pmatrix{x^{(k)}_{1} \cr x^{(k)}_{2} \cr x^{(k)}_{3}}
+
\pmatrix{10 \cr -5 \cr 31} along with the initial guess x_{0}=(1,0,0)^{T} . Thus we have \pmatrix{2 & 0 & 0 \cr 0 & 7 & 0 \cr 0 & 0 & 25}
\pmatrix{x^{(1)}_{1} \cr x^{(1)}_{2} \cr x^{(1)}_{3}}
=
–
\pmatrix{0 & -3 & 5 \cr 4 & 0 & -2 \cr 2 & -4 & 0}
\pmatrix{1 \cr 0 \cr 0}
+
\pmatrix{10 \cr -5 \cr 31} The first equation is given by 2 x_{1}^{(1)}=0\times x_{1}^{(0)}+3\times x_{2}^{(0)}-5\times x_{3}^{(0)}+10 There’s not much we can do with this equation as we haven’t computed any update values. But with the second equation 7 x_{2}^{(1)}=-4\times x_{1}^{(0)}+0\times x_{2}^{(0)}+2\times x_{3}^{(0)}-5 we already know x_{1}^{(1)} , and in principle it should be closer to the exact solution than x_{1}^{(0)} . Thus, it stands to reason that we should used this updated value to compute x_{1}^{(1)} . Let’s make that modification, and for convinence move all the updated values to one side 4\times x_{1}^{(1)}+7 x_{2}^{(1)}=0\times x_{2}^{(0)}+2\times x_{3}^{(0)}-5 Finally, with the third equation, we have 25 x_{3}^{(1)}=-2\times x_{1}^{(0)}+4\times x_{2}^{(0)}+0\times x_{3}^{(0)}+31 Part 1: (a) Using the updated values x_{1}^{(1)} and x_{2}^{(1)} , show that the previous equation may be written as 2\times x_{1}^{(1)}-4\times x_{2}^{(1)}+25 \times x_{3}^{(1)}=0\times x_{3}^{(0)}+31 Therefore, our iterative formula becomes 2 x_{1}^{(1)}=0\times x_{1}^{(0)}+3\times x_{2}^{(0)}-5\times x_{3}^{(0)}+10 4\times x_{1}^{(1)}+7 x_{2}^{(1)}=0\times x_{2}^{(0)}+2\times x_{3}^{(0)}-5 2\times x_{1}^{(1)}-4\times x_{2}^{(1)}+25 \times x_{3}^{(1)}=0\times x_{3}^{(0)}+31 Equation 2. (b) Show that in matrix form, the iterative procedure becomes \pmatrix{2 & 0 & 0 \cr 4 & 7 & 0 \cr 2 & -4 & 25}
\pmatrix{x^{(1)}_{1} \cr x^{(1)}_{2} \cr x^{(1)}_{3}}
=
–
\pmatrix{0 & -3 & 5 \cr 0 & 0 & -2 \cr 0 & 0 & 0}
\pmatrix{1 \cr 0 \cr 0}
+
\pmatrix{10 \cr -5 \cr 31} (c) Show that this system satisfies [A]=[M]-[N] . In general, if we choose [M]
=
\pmatrix{a_{11} & & \cr a_{21} & a_{22} & \cr a_{31} & a_{32} & a_{33} \cr \vdots & & & \ddots
\cr a_{n1} & & \cdots & & a_{nn}} and [N]
=
\pmatrix{& -a_{12} & -a_{13} & \cdots & -a_{1n} \cr & & -a_{23} & & \vdots \cr & & & \ddots \cr & & & & -a_{n-1,n} \cr & } we obtain what is known as the Gauss-Seidel method . To obtain the lower triangular part of the matrix [A] , MATLAB has the function \texttt{tril} . Thus, we have A = [2 -3 5;4 7 -2;2 -4 25];
M = tril(A)
N = M-A
c = [10;-5;31];
x = [1;0;0]; And so, the iterative process is given by x = M^-1*(N*x+c) (d) Run this line of code a couple of times to convice yourselves that it converges to the exact solution \{x\}=(1,-1,1)^{T} . To automate the process, modifying the code from \textit{ENGR20005\_Workshop3p3.mlx} gives A = [2 -3 5;4 7 -2;2 -4 25];
c = [10;-5;31];
M = tril(A)
N = M-A
x = [1;0;0];
i = 1;
tol = 10^-6;
fprintf(‘ x1 x2 x3 \n’)
fprintf(‘%10.7f %10.7f %10.7f\n’,x(1),x(2),x(3))
while norm(A*x-c,2)>tol
x = M^-1*(N*x+c);
fprintf(‘%10.7f %10.7f %10.7f\n’,x(1),x(2),x(3))
i = i+1;
end
fprintf(‘Iteration was completed in %d iterations’,i) What we see here is that by applying the Gauss-Seidel method, we significantly reduced the number of iterations required for the method to converge.
manual code ready 0.4 true false A = [2 -3 5;4 7 -2;2 -4 25]; 0 53 53 false false M = tril(A) 1 54 54 false false N = M-A 2 55 55 false false c = [10;-5;31]; 3 57 57 false true x = [1;0;0]; 4 58 58 true true x = M^-1*(N*x+c) 5 61 61 true false A = [2 -3 5;4 7 -2;2 -4 25]; 6 65 65 false false c = [10;-5;31]; 7 66 66 false false M = tril(A) 8 68 68 false false N = M-A 9 69 69 false false x = [1;0;0]; 10 71 71 false false i = 1; 11 72 72 false false tol = 10^-6; 12 73 73 false false fprintf(‘ x1 x2 x3 \n’) 13 75 75 false false fprintf(‘%10.7f %10.7f %10.7f\n’,x(1),x(2),x(3)) 14 76 76 false false while norm(A*x-c,2)>tol
x = M^-1*(N*x+c);
fprintf(‘%10.7f %10.7f %10.7f\n’,x(1),x(2),x(3))
i = i+1;
end 15 78 82 false true fprintf(‘Iteration was completed in %d iterations’,i) 16 84 84 true true A 17 86 86
2020-03-19T12:50:30Z 2020-03-31T11:53:53Z
application/vnd.mathworks.matlab.code MATLAB Code R2019b
9.7.0.1183724 c08b55d4-a0f2-4063-82b1-44c54fec3b18
9.7.0.1296695
R2019b
Update 4
Jan 20 2020
3546228467