ECE257ECE257 NumericalNumerical Methods Methods andandScientificScientific ComputingComputingLinear Algebraic EquationsLinear Algebraic EquationsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutTodayToday’’s class:s class:••Linear Algebraic EquationsLinear Algebraic Equations••Gaussian EliminationGaussian EliminationECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLinear Algebraic EquationsLinear Algebraic Equations••Solving for roots gave us solutions to equations ofSolving for roots gave us solutions to equations ofthe form:the form:••A more general problem would be to solve theA more general problem would be to solve thefollowing n equations simultaneouslyfollowing n equations simultaneously € f1x1, x2,K, xn( )= 0f1x1, x2,K, xn( )= 0Mfnx1, x2,K, xn( )= 0€ f x( )= 0ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLinear algebraic systemsLinear algebraic systems••A linear algebraic system is a system ofA linear algebraic system is a system ofequations where all the functions are linearequations where all the functions are linear € a11x1+ a12x2+ K + a1nxn− b1= 0a21x1+ a22x2+ K + a2nxn− b2= 0Man1x1+ an 2x2+ K + annxn− bn= 0ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLinear algebraic systemsLinear algebraic systems••Graphical solutionsGraphical solutions––Plot the functions and the solution is thePlot the functions and the solution is theintersection point of the functionsintersection point of the functions––For second order linear systems, eachFor second order linear systems, eachequation is a lineequation is a line––For third order linear systems each equationFor third order linear systems each equationis a planeis a planeECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of Connecticut••Example:Example:€ 3x1+ 2x2= 18−x1+ 2x2= 2From Numerical Methods for Engineers, Chapra and Canale, Copyright © The McGraw-Hill Companies, Inc.Linear Algebraic SystemsLinear Algebraic SystemsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLinear Algebraic SystemsLinear Algebraic Systems••Singular system (no solution)Singular system (no solution)From Numerical Methods for Engineers, Chapra and Canale, Copyright © The McGraw-Hill Companies, Inc.ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLinear Algebraic SystemsLinear Algebraic Systems••Singular system (infinite solutions)Singular system (infinite solutions)From Numerical Methods for Engineers, Chapra and Canale, Copyright © The McGraw-Hill Companies, Inc.ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLinear Algebraic SystemsLinear Algebraic Systems••Ill-conditioned systemIll-conditioned systemFrom Numerical Methods for Engineers, Chapra and Canale, Copyright © The McGraw-Hill Companies, Inc.ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLinear algebraic systemsLinear algebraic systems••Graphical methods work only for secondGraphical methods work only for secondand third order systemsand third order systems••Not preciseNot precise••Useful visualization toolUseful visualization toolECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutLinear algebraic equationsLinear algebraic equations••In matrix formIn matrix form••where A is a n x n matrix, and X and B arewhere A is a n x n matrix, and X and B aren x 1 vectors.n x 1 vectors.€ AX = B € a11a12L a1na21a21L a1nM M O Man1an 2L ann            x1x2Mxn            =b1b2Mbn           ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutMatricesMatrices••Definitions:Definitions:––Symmetric matrixSymmetric matrix––Diagonal matrixDiagonal matrix––Identity matrix (I)Identity matrix (I)ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutMatricesMatrices••DefinitionsDefinitions––Upper triangularUpper triangular––Lower triangularLower triangular––TridiagonalTridiagonal € aij= 0 if i > j € aij= 0 if i < j € aij= 0 if i − j > 1ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutMatricesMatrices••DefinitionsDefinitions––BandedBanded––TransposeTranspose € aijT= aji ∀i, j € aij= 0 if i − j > kECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutMatrix OperationsMatrix Operations••AdditionAddition••SubtractionSubtraction••MultiplicationMultiplication€ C = A + B ⇒ cij= aij+ bij€ C = AB ⇒ cij= aikbkjk=1n∑€ C = A − B ⇒ cij= aij− bijECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutMatricesMatrices••Data representationData representation––2-D array2-D array––1-D array1-D array––Array of pointersArray of pointers––Sparse matricesSparse matricesECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 9John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutMatrix multiplicationMatrix multiplication € Cnxl= AnxmBmxldouble A[n][m];double B[m][l];double C[n][l];for (int i=0; i<n; i++) {