Chapter 6Iterative Methods forSolving Linear Equationss1 Importing the practical problems2 The basic iterative methodss3 Convergence of iterative methodss4 Over-relaxation iterative method
Chapter 6 Iterative Methods for Solving Linear Equations §1 Importing the practical problem §2 The basic iterative methods §3 Convergence of iterative methods §4 Over-relaxation iterative method
s1 Importing the Practical ProblemFor the numerical solution of the boundary-value problem ofPoisson eguation on a sguare domain:au,au=f(x,y), 0<x,y<1Oxu(0, y) = u(1, y) = u(x,0) =u(x,1) = 0And solving it by finite variance.By decomposition of the solution domain, setting up thedifferentialequation on each domain:4u, -ui-,j -ui,j -uij---uij+ =h? fj,1<i,j≤NThematrix formof thedifferentialeguationsis:Au=fwhere Ae R(NxN)x(N), u, e RxN
§1 Importing the Practical Problem For the numerical solution of the boundary-value problem of Poisson equation on a square domain: 2 2 2 2 ( ) ( , ), 0 , 1 (0, ) (1, ) ( ,0) ( ,1) 0 u u f x y x y x y u y u y u x u x + = = = = = And solving it by finite variance. By decomposition of the solution domain, setting up the differential equation on each domain: 2 1, 1, , 1 , 1 4 , 1 , ij i j i j i j i j ij u u u u u h f i j N − − − − = − + − + The matrix form of the differential equations is: Au f = where ( ) ( ) , , N N N N N N A R u f R
Solving by Gaussian elimination methodSuccessive elementary row operations of the coefficientmatrix must be performed.WhenN isvery large,the computation will be great,and the occupation of the computer resources willbeverylarge
Solving by Gaussian elimination method and the occupation of the computer resources will be very large. Successive elementary row operations of the coefficient matrix must be performed. the computation will be great, When N is very large
Thus, for the linear eguations:Ax = bWe should look for more economic and more suitablenumericalmethod.The iterative method is a good basic method.The basic idea of the iterative method is constructing avectorsequence which convergences tothe solution.That is, setting up a calculating rule from the existingapproximate solution to the new approximate solution.By different calculatingrules,we can get differentiterativemethods
We should look for more economic and more suitable numerical method. The iterative method is a good basic method. The basic idea of the iterative method is constructing a vector sequence which convergences to the solution. That is, setting up a calculating rule from the existing approximate solution to the new approximate solution. By different calculating rules, we can get different iterative methods. Thus, for the linear equations: Ax = b
To solve the Ax = bRewriting Ax=b in the equivalentform:x=Bx+fand establishing iterations: x(k+) - Bx(k) + f.IdeaStarting from the initialvalue x(), we get thesequence [x(k)} .Setting Ae Rnxn,be R",xeR",If we transformthe linear equationsAx=bintox = Bx + fwhere BeR"x",f eR",xe R"Obviously, the two equation systems have the same solutions.We call the two equations systems equivalent
To solve the Ax b = Idea Obviously, the two equation systems have the same solutions. We call the two equations systems equivalent. Rewriting in the equivalent form: , and establishing iterations: . Starting from the initial value , we get the sequence . A x b = x B x f = + ( 1) ( ) k k x B x f + = + (0) x ( ) { }k x , , n n n n A R b R x R If we transform the linear equations x = Bx + f Ax = b into Setting , , , n n n n B R f R x R where
Forthelinearequation system:x=Bx+fwe adoptthefollowing steps:x(0) into the right side of thetaking the initial vector xequations,thengettingx(1) = Bx(0) + fand soon, we obtainx(2) = Bx(1) + fx(k+1) = Bx(k) + f (k = 0,1,2,..)This method called the iteration method, the above process isknownas theiterativeprocess.The iterative method produces a sequence: [x(*)]°.is, limx(k) = x, then the iterativeIf its limit exist, that is,kvomethod is convergent, otherwise, divergent
For the linear equation system: x = Bx + f This method called the iteration method, the above process is known as the iterative process. The iterative method produces a sequence: . 0 ( ) { } k x If its limit exist, that is, , then the iterative method is convergent, otherwise, divergent. ( ) * limx x k k = → (1) (0) x Bx f = + and so on, we obtain we adopt the following steps: x = Bx + f (2) (1) ( 1) ( ) k k x Bx f + = + (k = 0,1,2, ) taking the initial vector into the right side of the equations, then getting (0) x
If the iterative sequence ( x(*) is convergent: lim x(k) = x,k->o0then takinglimiton both sides oftheiterativeformatx(k+1) =Bx(k) +f ,we can get: x* = Bx* + fIt is equivalent to Ax" = b. Thus the vector sequence ( x()} isconvergent to the solution vector x *of the equations Ax =b.The calculation accuracy of this method is controllable.especially suitable for solving the equations system withlarge sparse coefficient matrix.Research Howto build theiterativeformat?eontents The convergence condition of the vector sequence?The convergence speed? The error estimation?
The calculation accuracy of this method is controllable, especially suitable for solving the equations system with large sparse coefficient matrix. Research contents How to build the iterative format? The convergence condition of the vector sequence? The convergence speed? The error estimation? . * * x B x f = + then taking limit on both sides of the iterative format ( 1) ( ) k k x B x f + = + If the iterative sequence is convergent: ( ) { } k x * It is equivalent to A x b = convergent to the solution vector of the equations . x* A x b = . Thus the vector sequence is ,we can get: ( ) { } k x ( ) * lim , k k x x → =
s2 The basic iterative methods1. The Jacobi MethodThe general form of the linear eguations system is:(a11X +a12X2 +...+ainXn =b)a21X1 +a22X2 +...+ a2nXn = b2aniX +an2X2 +. ±anXn = b,Setting au, ±O (i=l,2,...,n) , we can solve x, according tothe above formula:1[b - (a12x2 +... + ainxn)]X11an1[b2 -(a21x1 +a23X3 +... + a2nxn)]X2a22
1. The Jacobi Method §2 The basic iterative methods [ ( )] 1 1 1 2 2 1 1 1 1 n n b a x a x a x = − ++ The general form of the linear equations system is: 11 1 12 2 1 b1 a x a x a x + ++ n n = 21 1 22 2 2 b2 a x a x a x + ++ n n = n n nn n bn a 1 x1 + a 2 x2 ++ a x = [ ( )] 1 2 2 1 1 2 3 3 2 2 2 2 n n b a x a x a x a x = − + ++ 0 ( 1,2, , ) ii Setting a i n = , we can solve according to i x the above formula:
And so on,the linear eguations can be turned into:=-二(b-Zar,x) =x +二(b-Zar,x)?x.alal层1j=11(b-21La2x=x2+(b2X2a2,x,)a22a22厦j=1一(b, -Cax,=x,+=(b,-Zajx,)二x,aiaii万j=1之1(bnCamx)=x, +1(b,-Zamx,)x.-nannj=1Qj=1nnjtn
( ) 1 1 1 1 1 1 1 1 = = − n j j j j b a x a x And so on, the linear equations can be turned into: ( ) 1 2 1 2 2 2 2 2 = = − n j j j j b a x a x ( ) 1 1 = = − n j i j i ij j ii i b a x a x ( ) 1 1 = = − n j n j n nj j n n n b a x a x ( ) 1 1 1 1 11 1 = = + − n j j j b a x a x ( ) 1 1 2 2 22 2 = = + − n j j j b a x a x ( ) 1 1 = = + − n j i ij j ii i b a x a x ( ) 1 1 = = + − n j n nj j nn n b a x a x
Conducting iterative process of the equations:x(k+1) = x(k) +1(b, -Zayx()aiij=1(i=1,2,...,n;k =0,1,2,..)Setting D=diag(ai1,a22,",an)then the above formula is transformedinto the matrix form:x(k+1) = x(k) + D-1(b - Ax(k))x(+1) = x(k) - D-1 Ax(k) + D-1b1x(k+1) = D-1(D - A)x(k) + D-1b
( ) 1 1 ( 1) ( ) ( ) = + = + − n j k i i j j i i k i k i b a x a x x Conducting iterative process of the equations: (i = 1,2, ,n;k = 0,1,2, ) then the above formula is transformed into the matrix form: ( ) (k 1) (k ) 1 (k ) x = x + D b − Ax + − x x D Ax D b (k +1) (k ) −1 (k ) −1 = − + x D D A x D b (k 1) 1 (k ) 1 ( ) + − − = − + 11 22 ( , , , ) D diag a a a = nn Setting