Back Substitution to solve the linear system First, w a1X1+a12X2+a133+…+a1wxw=b a2x2 +a23x3+.+anx=b2 a33X3+…+a3wxy=b3 aN-1N-IXN-I+aN-I.NXN bN-1 dNNXN bN XN-1 bN-1-aN-I.NXN aN-1.N-1 Algorithm: Finally, xn=balum 1=4-(a2+a13西+…+4) b-(∑akk) k=2 x=6-∑4gxyh4,i=n-12,1 41 1 华南师范大学数学科学学院谢卿玲
Back Substitution to solve the linear system 华南师范大学数学科学学院 谢骊玲 ◼ First, N N N b x a = 11 2 1 1 11 1 12 2 13 3 1 1 ( ) ( ) a b a x a b a x a x a x x n k k k n n − = − + + + = = N−1,N−1 N−1 N−1,N N = N−1 a x + a x b a b - a x x N N N N N N N 1, 1 1 1, 1 − − − − − = Finally, NN N N N N N N N N a x b a x a x b a x a x a x b a x a x a x a x b = + + = + + + = + + + + = 33 3 3 3 22 2 23 3 2 2 11 1 12 2 13 3 1 1 ,… = − = − = = + , 1,...,2,1 1 x (b u x )/u i n x b /u ii n j i i i ij j n n nn Algorithm:
Upper-Triangular Linear Systems The condition that a is essential because the back-substitu- tion algorithm involves division by ak If this requirement is not fulfilled,either no solution exists or infinitely many solution exist. Thm.2.2.If the NXN matrix 4=[a]is either upper or lower triangular,then dct(=a,aa…aw=ia 华南师范大学数学科学学院谢删玲
Upper-Triangular Linear Systems ◼ The condition that akk≠0 is essential because the back-substitution algorithm involves division by akk. If this requirement is not fulfilled, either no solution exists or infinitely many solution exist. ◼ Thm. 2.2. If the N×N matrix A=[aij] is either upper or lower triangular, then 华南师范大学数学科学学院 谢骊玲 11 22 1 det( ) N NN ii i A a a a a = = =
Gaussian Elimination Two linear systems of dimension NXN are said to be equivalent provided that their solution sets are the same. When elementary transformations are applied to a given system, the solution sets do not change. A scheme for solving a general system AX-B of N equations and N unknowns is to construct an equivalent upper-triangular system UX=Y that can be solved by the back-substitution algorithm. 华南师范大学数学科学学院谢珊玲
Gaussian Elimination ◼ Two linear systems of dimension N×N are said to be equivalent provided that their solution sets are the same. ◼ When elementary transformations are applied to a given system, the solution sets do not change. ◼ A scheme for solving a general system AX=B of N equations and N unknowns is to construct an equivalent upper-triangular system UX=Y that can be solved by the back-substitution algorithm. 华南师范大学数学科学学院 谢骊玲
Gaussian Elimination A simple example: The back-substitution algorithm 3x1+2x2=7 is now used to find the 4x1+x2=1 unknowns The variable x is eliminated from the second equation by 2=5 substracting from it 4/3 times and the first equation.We arrive ×5 at the equivalent system: =-1 3 3x1+2x2=7 5 25 3= 3 华南师范大学数学科学学院谢骝玲
Gaussian Elimination ◼ A simple example: ◼ The variable x1 is eliminated from the second equation by substracting from it 4/3 times the first equation. We arrive at the equivalent system: ◼ The back-substitution algorithm is now used to find the unknowns and 华南师范大学数学科学学院 谢骊玲 4 1 . 3 2 7 1 2 1 2 x x x x + = + = . 3 25 3 5 3 2 7 2 1 2 − = − + = x x x 2 x = 5 1 7 2 5 1. 3 x − = = −
Gaussian Elimination It is efficient to store all the coefficients of the linear system AX=B in an array of dimension NX(N+1).The coefficients of B are stored in column N+1 of the array(i.e., b).Each row contains all the coefficients necessary to represent an equation in the linear system.The augmented matrix is denoted [AB]and the linear system is represented as follows: 411+a12X2+413x3+…+anxn=b a21X1+a22X3+a23X3+…+a2mXn=b2 a31X1+a32X2+a333+…+a3nxn=b amx +an2X2 +an3x3+..+amnxn =bn The system can be solved by performing row operations on the augmented matrix [AB].The variables xk are placeholders for the coefficients and can be omitted until the end of the calculation. 华南师范大学数学科学学院谢卿玲
Gaussian Elimination ◼ It is efficient to store all the coefficients of the linear system AX=B in an array of dimension N×(N+1). The coefficients of B are stored in column N+1 of the array(i.e., ak,N+1 =bk ). Each row contains all the coefficients necessary to represent an equation in the linear system. The augmented matrix is denoted [A|B] and the linear system is represented as follows: ◼ The system can be solved by performing row operations on the augmented matrix [A|B]. The variables xk are placeholders for the coefficients and can be omitted until the end of the calculation. 华南师范大学数学科学学院 谢骊玲 . 1 1 2 2 3 3 31 1 32 2 33 3 3 3 21 1 22 2 23 3 2 2 11 1 12 2 13 3 1 1 n n n nn n n n n n n n n a x a x a x a x b a x a x a x a x b a x a x a x a x b a x a x a x a x b + + + + = + + + + = + + + + = + + + + =