Engineering Analysis ENG 3420 Fall 2009Lecture 13Solving systems of linear equationsSolving systems of linear equations in MatlabSolving graphically systems of linear equationsDeterminant of the square matrix A=[aij]Determinants of several matricesProperties of the determinantsCramer’s RuleExample of the Cramer’s RuleGauss EliminationNaïve Gauss Elimination (cont)Complexity of Gauss eliminationPivotingPartial Pivoting ProgramTridiagonal systems of linear equationsTridiagonal system solverEngineering Analysis ENG 3420 Fall 2009Dan C. MarinescuOffice: HEC 439 BOffice hours: Tu-Th 11:00-12:0022Lecture 13Lecture 13 Last time:  Problem solving in preparation for the quiz Linear Algebra Concepts Vector Spaces, Linear Independence  Orthogonal Vectors, Bases Matrices Today Solving systems of linear equations (Chapter 9) Graphical methods Next Time Gauss eliminationSolving systems of linear equations Matrices provide a concise notation for representing and solvingsimultaneous linear equations:a11x1+ a12x2+ a13x3=b1a21x1+ a22x2+ a23x3= b2a31x1+ a32x2+ a33x3= b3a11a12a13a21a22a23a31a32a33⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ x1x2x3⎧ ⎨ ⎪ ⎩ ⎪ ⎫ ⎬ ⎪ ⎭ ⎪ =b1b2b3⎧ ⎨ ⎪ ⎩ ⎪ ⎫ ⎬ ⎪ ⎭ ⎪ [A]{x}={b}Solving systems of linear equations in Matlab Two ways to solve systems of linear algebraic equations [A]{x}={b}: Left-divisionx = A\b Matrix inversionx = inv(A)*b Matrix inversion only works for square, non-singular systems; it is less efficient than left-division.Solving graphically systems of linear equations For small sets of simultaneous equations, graphing them and determining the location of the intersection of the straight line representing each equation provides a solution. There is no guarantee that one can find the solution of system of linear equations:a) No solution existsb) Infinite solutions existc) System is ill-conditionedDeterminant of the square matrix A=[aij] Here the coefficient Aijof aijis called the cofactor of A  A cofactor is a polynomial in the remaining rows of A and can bedescribed as the partial derivative of A. The cofactor polynomial contains only entries from an (n-1)x (n-1) matrix Mijcalled a “minor”obtained from A by eliminating row i and column j.ininiiiiaAaAaAAA ....)det(||2211++==⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡==−−−−−−−−nnnnnnnnnnnnnnnnijaaaaaaaaaaaaaaaaaA,1,2,1,,11,12,11,1,21,22,21,2,11,12,11,1....................................][Determinants of several matrices Determinants for 1x1, 2x2, 3x3 matrices are: Determinants for square matrices larger than 3 x 3 are more complicated.1×1 a11=a112 × 2a11a12a21a22= a11a22− a12a213 × 3a11a12a13a21a22a23a31a32a33= a11a22a23a32a33− a12a21a23a31a33+ a13a21a22a31a32Properties of the determinants If we permute two rows of the rectangular matrix A then the sign of the determinant det(A) changes.  The determinant of the transpose of a matrix A is equal to the determinant of the original matrix. If two rows of A are identical then |A|=0Cramer’s Rule Consider the system of linear equations: [A]{x}={b} Each unknown in a system of linear algebraic equations may be expressed as a fraction of two determinants with denominator D and with the numerator obtained from D by replacing the column of coefficients of the unknown in question by the vector b consisting of constants b1, b2, …, bn.Example of the Cramer’s Rule Find x2in the following system of equations: Find the determinant D Find determinant D2 by replacing D’s second column with b Divide0.3x1+ 0.52x2+ x3=−0.010.5x1+ x2+1.9x3= 0.670.1x1+ 0.3x2+ 0.5x3=−0.44D =0.3 0.52 10.5 1 1.90.1 0.3 0.5= 0.311.90.3 0.5− 0.520.5 1.90.1 0.5+10.5 10.1 0.4=−0.00220649.044.01.067.05.015.01.09.15.001.05.044.09.167.03.05.044.01.09.167.05.0101.03.02=−+−−=−−=Dx2=D2D=0.0649−0.0022=−29.5Gauss Elimination Gauss elimination Æ a sequential process of removing unknowns from equations using forward elimination followed by back substitution. “Naïve” Gauss elimination Æ the process does not check for potential problems resulting from division by zero.Naïve Gauss Elimination (cont) Forward elimination Starting with the first row, add or subtract multiples of that row to eliminate the first coefficient from the second row and beyond. Continue this process with the second row to remove the second coefficient from the third row and beyond. Stop when an upper triangular matrix remains. Back substitution Starting with the last row, solve for the unknown, then substitute that value into the next highest row. Because of the upper-triangular nature of the matrix, each row will contain only one more unknown.function x=GaussNaive(A,b)ExA=[A b];[m,n]=size(A);q=size(b);if (m~=n) fprintf ('Error: input matrix is not square; n = %3.0f, m=%3.0f \n', n,m);Endif (n~=q) fprintf ('Error: vector b has a different dimension than n; q = %2.0f \n', q);endn1=n+1;for k=1:n-1for i=k+1:n factor=ExA(i,k)/ExA(k,k); ExA(i,k:n1)= ExA(i,k:n1)-factor*ExA(k,k:n1); EndEndx=zeros(n,1);x(n)=ExA(n,n1)/ExA(n,n);for i=n-1:-1:1 x(i) = (ExA(i,n1)-ExA(i,i+1:n)*x(i+1:n))/ExA(i,i);end>> C=[150 -100 0 ; -100 150 -50; 0 -50 50]C =150 -100 0-100 150 -500 -50 50>> d= [588.6; 686.7;784.8]d =588.6000686.7000784.8000>> x = GaussNaive(C,d)x =41.202055.917071.6130>> A=[1 1 1 0 0 0 ; 0 -1 0 1 -1 0 ; 0 0 -1 0 0 1 ; 0 0 0 0 1 -1 ; 0 10 -10 0 -15 -5 ; 5 -10 0 -20 0 0]A = 1 1 1 0 0 0 0 -1 0 1 -1 0 0 0 -1 0 0 -1 0 0 0 0 1 -1 0 10 -10 0 -15 -5 5 -10 0 -20 0 0b =0 0 0 0 0 200>> b=b'b =00000200>> x = GaussNaive(A,b) x =NaNNaNNaNNaNNaNNaNx=A\bx =6.1538-4.6154-1.5385-6.1538-1.5385-1.5385>> x=inv(A)*bx =6.1538-4.6154-1.5385-6.1538-1.5385-1.5385Complexity of Gauss elimination To solve an n x n system of linear equations by Gauss elimination we carry out the following number of operations:  Flops Æ floating-point operations. Mflops/sec number of floating point operation executed by a processor per second. Conclusions: As the system gets larger, the computation time increases greatly. Most of the effort is incurred in the elimination step.ForwardElimination2n33+ On2()BackSubstitutionn2+ On()Total2n33+ On2()Pivoting If a coefficient along the diagonal