ECE257ECE257 NumericalNumerical Methods Methods andandScientificScientific ComputingComputingLinear Algebraic EquationsLinear Algebraic EquationsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 10John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutTodayToday’’s class:s class:••Linear Algebraic EquationsLinear Algebraic Equations••LU DecompositionLU DecompositionECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 10John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLinear Algebraic EquationsLinear Algebraic Equations••Gaussian Elimination works well for solving linearGaussian Elimination works well for solving linearsystems of the form:systems of the form:••What if you have to solve the linear system severalWhat if you have to solve the linear system severaltimes, with changing B vectors?times, with changing B vectors?••Then, Gaussian elimination becomes tediousThen, Gaussian elimination becomes tedious••Instead, use a method that separates outInstead, use a method that separates outtransformations on A from transformations on Btransformations on A from transformations on B€ AX = BECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 10John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLU DecompositionLU Decomposition••Assume that A can be factorized into the product ofAssume that A can be factorized into the product ofan upper triangular matrix and a lower triangularan upper triangular matrix and a lower triangularmatrixmatrix € A = LU =l110 0 L 0l21l220 L 0l31l32l33L 0M M M O Mln1ln 2ln 3L lnn                u11u11u13L u1n0 u22u23L u2n0 0 u33L u3nM M M O M0 0 0 L unn               ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 10John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLU DecompositionLU Decomposition••Substitute the factorization into the linear systemSubstitute the factorization into the linear system€ ⇒LD = BUX = D   € ⇒ LUX = B€ AX = B••We have transformed the problem into two stepsWe have transformed the problem into two steps––Factorize Factorize AA into into LL and and UU––Solve the two subproblemsSolve the two subproblems••LY=BLY=B••UX=YUX=YECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 10John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLU DecompositionLU Decomposition••The upper triangular matrix comes from ForwardThe upper triangular matrix comes from Forwardeliminationelimination € a11x1+ a12x2+ K + a1nxn= b1a21x1+ a22x2+ K + a2nxn= b2Man1x1+ an 2x2+ K + annxn= bn••Eliminate xEliminate x11 from row 2 from row 2––Multiply row 1 by Multiply row 1 by ll2121=a=a2121/a/a1111••This time keep track of the multiplier factorsThis time keep track of the multiplier factors € a21a11a11x1+a21a11a12x2+ K +a21a11a1nxn=a21a11b1ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 10John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLU DecompositionLU Decomposition••Populate the L matrix with the multiplierPopulate the L matrix with the multiplierfactors used during forward eliminationfactors used during forward elimination € L =1 0 0 L 0l211 0 L 0l31l321 L 0M M M O Mln1ln 2ln 3L 1                € l21=a21a11,l31=a31a11,l32=a'32a'22,L,lij=aij( j−1)ajj( j−1),ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 10John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLU DecompositionLU Decomposition••Construct the Construct the LL and and UU matrices matrices••Solve for the Solve for the DD vector using forward vector using forwardsubstitutionsubstitution••Solve for the Solve for the XX vector using backward vector using backwardsubstitutionsubstitution€ di= bi− lijdjj=1i−1∑ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 10John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLU DecompositionLU Decomposition••ExampleExample€ 3.0 −0.1 −0.20.1 7.0 −0.30.3 −0.2 10.0          x1x2x31          =7.85−19.371.4          ••Factorize A using forward eliminationFactorize A using forward elimination€ 3.0 −0.1 −0.20.1 7.0 −0.30.3 −0.2 10.0          € 3.0 −0.1 −0.20 7.0033 −0.29330.3 −0.2 10.0          1 0 00.033 1 01          € 3.0 −0.1 −0.20 7.0033 −0.29330 −0.19 10.02          1 0 00.033 1 00.1 1         ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 10John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLU DecompositionLU Decomposition••ExampleExample€ U =3.0 −0.1 −0.20 7.0033 −0.29330 0 10.012          L =1 0 00.033 1 00.1 −0.02713 1         ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 10John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLU DecompositionLU Decomposition••ExampleExample€ LD = B€ 1 0 00.033 1 00.1 −0.02713 1          d1d2d3          =7.85−19.371.4          € d1= 7.85€ d2= −19.3 − 0.0333 7.85( )= −19.5617€ d3= 71.4 − 0.1 7.85( )− −0.02713( )−19.5617( )= 70.0843ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 10John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLU DecompositionLU Decomposition••ExampleExample€ UX = D€ 3.0 −0.1 −0.20 7.0033 −0.29330 0 10.012          x1x2x3          =7.85−19.561770.0843          € x3=70.084310.012= 7€ x2=−19.5617 − −0.2933( )7.0( )7.0033= −2.5€ x3=7.85 − −0.1( )2.5( )− −0.2( )7.0( )3.0= 3.0ECE 257 Numerical Methods and Scientific