《数值分析》课程PPT教学课件（Numerical Analysis）Chapter 5 The direct solution of system of linear equations

Chapter 5 The direct solution ofsystem of linear equations$ 1 the introduction of practical problem$ 2 the gauss elimination method$ 3 the triangular decomposition of matrixs 4 the chasing method$ 5 the norm of matrixs and vectors$ 6 the conditions and error analyses aboutsystem of linear equations上页下页返回

上页 下页 返回 §1 the introduction of practical problem Chapter 5 The direct solution of system of linear equations §3 the triangular decomposition of matrixs §4 the chasing method §5 the norm of matrixs and vectors §6 the conditions and error analyses about system of linear equations §2 the gauss elimination method

S1theintroductionofpracticalproblem20BAC39WWi1.3Look at an actual problem firstly.高2QWIn the circuitdiagram,20250Vvolts0bythe law of Kirchhoff:710Any nodeinthecircuit.F4030at any instant, the outflow (inflow) all current algebra of the node iszero all the time.With G as a reference point, the current satisfy linear equations below:5i +5iz = Vi-i-i=02i4-3i, = 0i-i-i = 0上页5iz-7i,-2i4=0下页返回

上页 下页 返回 §1 the introduction of practical problem Look at an actual problem firstly. In the circuit diagram, Any node in the circuit, With G as a reference point, the current satisfy linear equations below:          − − = − − = − = − − = + = 5 7 2 0 0 2 3 0 0 5 5 2 3 4 1 2 3 4 5 3 4 5 1 2 i i i i i i i i i i i i i V by the law of Kirchhoff: at any instant, the outflow (inflow) all current algebra of the node is zero all the time

The problems of solving linear equations show up in many practical problems,For example: structure analysis, network analysis, geodesy, data analysis,optimizationProblemetc.The problems of solving linear equations also show up in many mathematicalproblems.For example: three spline, the least square method, nonlinear equation,differentialequations,thefiniteelementmethod.The methods of sloving the system of linear equations take up a importantplace in numberical analysisThe methods of sloving the system of linearequations as follows:上页下页返圆

上页 下页 返回 For example: structure analysis, network analysis, geodesy, data analysis, optimizationProblem etc. ➢ The problems of solving linear equations show up in many practical problems, ➢The problems of solving linear equations also show up in many mathematical problems. For example: three spline, the least square method, nonlinear equation,differential equations,the finite element method. The methods of sloving the system of linear equations take up a important place in numberical analysis. The methods of sloving the system of linear equations as follows:

Ifthereis a system of linearequations withn unkownsaix +ax2 +...+anx, =ba21xi +a22x +... +a2nx, = b,anix+an2x2+...+amx, =bExpressed in matrixs and vectors, the above system of equations can be rewritten as:Ax = bwhere:b,xiana12dinb2X2a1a22annb=A=x=..b.上页xnanlan2ann下页返回

上页 下页 返回 If there is a system of linear equations with n unkowns 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 n n n n n n nn n n a x a x a x b a x a x a x b a x a x a x b  + + + =   + + + =     + + + = Expressed in matrixs and vectors, the above system of equations can be rewritten as: Ax b = where: 11 12 1 21 22 2 1 2 n n n n nn a a a a a a A a a a     =         1 2 n x x x x     =         1 2 n b b b b     =        

When det(A) + O, the system of linear equations have the unique solution.The methods of sloving the system of linear equations :(1)Direct solution:mainly for the coefficient matrixs of linear equations arelower order dense matrix and some large sparse matrixs;(2)Iterative method : mainly for the solutions of linear equations with largesparse matrixs.上页下页返圆

上页 下页 返回 ➢The methods of sloving the system of linear equations : When det( ) 0 A  , the system of linear equations have the unique solution. （2） Iterative method : mainly for the solutions of linear equations with large sparse matrixs. （1）Direct solution:mainly for the coefficient matrixs of linear equations are lower order dense matrix and some large sparse matrixs;

s2Gauss EliminationsloluteAx =blGaussordereliminationidea:Thegoal of forward elimination is to-transform the coefficientmatrix into anupper triangular matrixTwo steps:1.Forward Elimination2.Back SubstitutionAx= bForthis system oflinearequations:if det(A) O The elementary row transformation of the augmented matrix:a(1)6()ainaacbCrecorded?A=(A,b)(A(I)=........上页am)q()g(1)6(1)下页n2nnn返圆

上页 下页 返回 slolute Ax b   = 1、Gauss order elimination idea: The goal of forward elimination is to transform the coefficient matrix into an upper triangular matrix 。 = §2 Gauss Elimination For this system of linear equations: Ax = b The elementary row transformation of the augmented matrix: A = (A,b)             = (1) (1) (1) 2 (1) 1 (1) 2 (1) 2 (1) 2 2 (1) 2 1 (1) 1 (1) 1 (1) 1 2 (1) 1 1 n n n n n n n a a a b a a a b a a a b        ( , ) (1) (1) A b recorded = i f det(A)  0 Two steps: 1. Forward Elimination 2. Back Substitution

if a 0Elimination:(1)aliiDefinning line multiplier:i=2,3,..,nmi1row(i) - row(1) × m1, thus :a(2 = a" - mnal)i,j=2,3,..,nb(2) = b(1) - m,b(1)i= 2,3,..,nall爱..aL0福(A(1),b(1)) →(A(2),b(2)) =....·bSalq(2)0上页?nn下页返回

上页 下页 返回             = (2) (2) (2) 2 (2) 2 (2) 2 (2) 2 2 (1) 1 (1) 1 (1) 1 2 (1) 1 1 0 0 n n n n n n a a b a a b a a a b        ( , ) (2) (2) A b 0 (1) if a11  Definning line multiplier: i n a a m i i 2,3, , (1) 1 1 (1) 1 1 = =  ( ) (1) , : 1 row i row m thus −  i (1) 1 1 (2) (1) aij = aij −mi a j (1) 1 1 (2) (1) bi = bi − mi b i, j = 2,3,  , n i = 2,3,  ,n ( , ) (1) (1) A b Elimination:

if all) =O because det(A)±0Thus : there are more than one element that isnot O in the first colum of Aif al) + O,thus : exchange the first row's positon of(A(), b()with the ith row's position,then :e lim ination.aa(1)6(1))ain(2)(2)(2)bs0a22a2nand.··det(0)+0(2)6(2)(2)0aCn21nnso,after k -lth step,(A), b())will as follows :上页下页返圆

上页 下页 返回 0 ( 1 ) if a11 = because det(A)  0 not in the first colum of A Thus there are more than one element that is 0: ' , : lim . 0, : ' ( , ) 1 (1) (1) (1) 11 with the i t h row s position then e ination if ai  thus exchange the first row s positon of A b   (2) (2) (2) 2 (2) 2 (2) 2 (2) 2 2 ( 1 ) 1 ( 1 ) 1 ( 1 ) 1 2 ( 1 ) 1 1 00 n n n n nn a a b a a b a a a b       and det( • )  0 , 1 ,( , ) : (1) (1) so after k − t h step A b will as follows

allaa)aa)·(A(1),b(1)) →(A(k),b(k))(k)(k)Rqaknkk(k)(k)6(k)Definning line multiplier:Oanknnnai=k+l,...,nmik(k)aikdet() +0ith row - k thxmik,thus :(k+1)(k)(k)i,j=k+1,...,na-mikaij11i=k+1,..,n= b(*) - mxb(l)上页b(k+1) 下页返回

上页 下页 返回                   = ( ) ( ) ( ) ( ) ( ) ( ) (2) 2 (2) 2 (2) 2 2 (1) 1 (1) 1 (1) 1 2 (1) 1 1 k n k n n k n k k k k kn k kk n n a a b a a b a a b a a a b             ( , ) (k ) (k ) ( , ) A b (1) (1) A b det(•)  0 Definning line multiplier: i k n a a m k kk k i k i k 1, , ( ) ( ) = = +  ith row k th m ,thus: −  i k ( 1) ( ) (k ) ik kj k ij k aij = a −m a + ( 1) ( ) (k ) i k k k i k bi = b − m b + i, j = k + 1,  , n i = k + 1,  ,n

Afterk =n -1 steps,(A,b()will as follows :q.(1+a12Oin11aa(A(1),b(1)) →(A(n),b(n)) :·b(n)q(n)nnnbecause : det(A) ± 0we can know: al ± Oi=1,2,.,nso,the upper triangular equationsA(n)x = b(n) has the unique soiution上页The solution of Ax = b is :下页返回

上页 下页 返回             = ( ) ( ) (2) 2 (2) 2 (2) 2 2 (1) 1 (1) 1 (1) 1 2 (1) 1 1 n n n n n n n a b a a b a a a b      ( , ) (1) (1) A b 1 ,( , ) : (1) (1) Afterk = n− steps A b will as follows ( , ) (n) (n) A b because : det(A)  0 we can know a i n i i i : 0 1,2, , ( )  =  The solution of Ax = b is ： so the uppertriangular equationsA x b has the unique soiution (n) (n) , =