Engineering Analysis ENG 3420 Fall 2009 Dan C Marinescu Office HEC 439 B Office hours Tu Th 11 00 12 00 Lecture 19 Last time Midterm solutions and discussions Today Today The inverse of a matrix Iterative methods for solving sytems of linear equations Gauss Siedel Jacobi Next Time Relaxation Non linear systems Lecture 19 2 The inverse of a square If A is a square matrix there is another matrix A 1 called the inverse of A for which A A 1 A 1 A I The inverse can be computed in a column by column fashion by generating solutions with unit vectors as the right hand side constants 1 A x1 0 0 0 A x 2 1 0 A 1 x1 x2 0 A x 3 0 1 x3 Canonical base of an n dimensional vector space 100 000 010 000 001 000 000 100 000 010 000 001 The response of a linear system The response of a linear system to some stimuli can be found using the matrix inverse Interactions response stimuli Ar s 1 1 A Ar A s 1 A A I 1 r A s Gauss Seidel Method The Gauss Seidel method is the most commonly used iterative method for solving linear algebraic equations A x b The method solves each equation in a system for a particular variable and then uses that value in later equations to solve later variables For a 3x3 system with nonzero elements along the diagonal for example the jth iteration values are found from the j 1th iteration using b1 a12 x2j 1 a13 x3j 1 x a11 j 1 b2 a21 x1j a23 x3j 1 x a22 j 2 b3 a31 x1j a32 x2j x a33 j 3 Jacobi Iteration The Jacobi iteration is similar to the Gauss Seidel method except the j 1th information is used to update all variables in the jth iteration a b Gauss Seidel Jacobi Convergence The convergence of an iterative method can be calculated by determining the relative percent change of each element in x For example for the ith element in the jth iteration xij xij 1 a i 100 j x The method is ended when i all elements have converged to a set tolerance Diagonal Dominance The Gauss Seidel method may diverge but if the system is diagonally dominant it will definitely converge Diagonal dominance means n aii aij j 1 j i Relaxation To enhance convergence an iterative program can introduce relaxation where the value at a particular iteration is made up of a combination of the old value and the newly calculated value xinew xinew 1 xiold where is a weighting factor that is assigned a value between 0 and 2 0 1 underrelaxation 1 no relaxation 1 2 overrelaxation Nonlinear Systems Nonlinear systems can also be solved using the same strategy as the Gauss Seidel method solve each system for one of the unknowns and update each unknown using information from the previous iteration This is called successive substitution Newton Raphson Nonlinear systems may also be solved using the Newton Raphson method for multiple variables For a two variable system the Taylor series approximation and resulting Newton Raphson equations are f1 i f x2 i 1 x2 i 1 i x1 x2 f1 i 1 f1 i x1 i 1 x1 i f2 i f2 i f2 i 1 f2 i x1 i 1 x1 i x2 i 1 x2 i x1 x2 f2 i f f2 i 1 i x2 x2 x1 i 1 x1 i f1 i f2 i f1 i f2 i x1 x2 x2 x1 f1 i f2 i f1 i f2 i x1 x1 x2 i 1 x2 i f1 i f2 i f1 i f2 i x1 x2 x2 x1 f1 i