• Author / Uploaded
• kennethmsoriano

• Categories
• Ecuaciones
• Matriz (Matemáticas)
• Algoritmos y Estructuras de Datos
• Teoría de la matriz
• Matemáticas Aplicadas

Citation preview

Gauss Elimination ES 204 Numerical Methods in Engineering

How to solve small number of equations (n≤3) by graphical method? Doable for 2 linear equations by plotting them on Cartesian coordinates with one axis to x1 and the other to x2 For 3 equations, each equation is a plane in 3D coordinate system Point where 3 planes intersect is the solution Beyond 3 equations, graphical methods break down; little practical value

How to indicate singular and illconditioned systems graphically?

2 equations as parallel lines no solution; singular

2 equations are coincident hard to identify exact infinite number of solutions intersection point singular ill-conditioned sensitive to roundoff error

How to solve small number of equations (n≤3) by Cramer’s rule? Assume we have [A]{x} = {b} Each unknown is a fraction of 2 determinants with denominator D and numerator obtained from D by replacing the column of coefficients by constants b1, b2, . . . , bn Example:

Determinant of 2x2:

Cramer’s rule for 3x3 A matrix:

b11 a12 b21 a22 b a32 x1  31 a11 a12 a21 a22 a31 a32

a13 a23 a33 a13 a23 a33

a11 a21 a x2  31 b11 b21 b31

b12 b22 b32 a12 a22 a32

a13 a23 a33 a13 a23 a33

a11 a12 b13 a21 a22 b23 a a32 b33 x3  31 b11 a12 a13 b21 a22 a23 b31 a32 a33

Example: Cramer’s rule Use Cramer’s rule to solve

How to use Octave’s det function?

For more than three equations, Cramer’s rule becomes impractical Number of equations increases, determinants are time consuming to evaluate by hand/PC Singular systems have D = 0 Ill-conditioned systems have D near 0 or very small

How to solve small number of equations (n≤3) by elimination of unknowns? Noncomputer solution technique; combines equations ; popular method

Eliminate x1

Follow directly from Cramer’s rule

Method extremely tedious to be implemented manually

What is Naive Gauss Elimination? Multiply by a21/a11 Subtract to eliminate x1

Solve a general set of n equations

Modified 2nd equation

Repeat to eliminate x1 from 2nd to n equations (e.g. how to eliminate x1 in 3rd equation?) All equations from 2nd to n will be modified due to elimination of x1 pivot equation; a11 is the pivot element 1st step: eliminate x1 from 2nd to n equation (done!)  2nd step: eliminate x2 from 3rd to n equation

New set after x1 elimination

Now we use modified 2nd equation as pivot equation, and a’22 as pivot element

What is Naive Gauss Elimination? Multiply by a’32/a’22, then subtract to: Eliminates x2 in 3rd equation Eliminate x2 from 3rd to n equation using 2nd equation as pivot

New set after x1 elimination

Continue using the remaining pivot equations Final step is to use the (n − 1)th equation to eliminate the xn−1 term from the nth equation

New set after x2 elimination Prime symbol indicates number of modification FORWARD ELIMINATION Phase (upper triangular matrix)

What is Naive Gauss Elimination?

Your set of equations after forward elimination phase

Value of x from 1 to n-1 in terms of coefficients and constants BACK SUBSTITUTION Phase

Example: Naive Gauss Elimination  0.1   3x1  0.1x2  0.2 x3  7.85 3  

Solve x by Gauss elimination

 0.3   3x1  0.1x2  0.2 x3  7.85  3 

  0.190000   7.00333x2  0.293333x3  19.5617 7 . 00333  

New set after eliminating x1 in 2nd and 3rd equations

New set after eliminating x2 in 3rd equation (upper triangular form)

Example: Naive Gauss Elimination 3

b   a12 j x j 1 2

x2 

j 3 1 22

a

b21  a123 x3  a122

3

b   a10j x j 0 1

x1 

j 2 0 11

a



b10  a120 x2  a130 x3  a110



exact solution

Verification of numerical solution by substitution to original set 

How to implement Naive Gauss elimination in Octave? coefficient matrix A and right-hand-side vector b are combined as augmented matrix forward elimination - 2 nested loops outer loop moves down the matrix from one pivot row to the next

inner loop moves below the pivot row to each of the subsequent rows where elimination is to take place

What is pivoting? ”naive” – during elimination and back substitution phases, it is possible that a division by zero can occur pivot element is close to zero if magnitude of pivot element is small compared to other elements, round-off errors can be introduced partial pivoting – before normalization, determine the coefficient with the largest absolute value in the column below the pivot element Rows can then be switched so that the largest element is the pivot element

complete pivoting - If columns as well as rows are searched for the largest element and then switched

Example: Partial Pivoting Use Gauss elimination to solve Exact solution is x1 = 1/3 and x2 = 2/3 Multiplying first equation by 1/(0.0003) Eliminate x1 from the second equation Substitute back into the first equation

Result is very sensitive to the number of significant figures carried in the computation

Example: Partial Pivoting If the equations are solved in reverse order Forward elimination and substitution:

Results less sensitive to the number of significant figures due to partial pivoting

How to implement Gauss elimination with pivoting in Octave? Same code with GaussNaive except with the addition of the pivoting code

determine the largest available coefficient in the column below the pivot element using the max function

y is the largest element in the vector x, and i is the index corresponding to that element

How to evaluate determinant with Gauss elimination? Assume you are done with forward elimination on a 3x3 system

In general for a triangular form matrix: After forward elimination: With pivoting: p represents the number of times that rows are pivoted Determinant has value in assessing system condition (ill-conditioned; singular)

Example: Solution of a Tridiagonal System Solve the following tridiagonal system:

Transform the matrix to upper triangular form Multiply first equation by factor e2/f1 and subtract result from second equation

Notation

Creates a zero in place of e2 ;transforms other coefficients to new values

 g2 is unmodified because the element above it in the first row is zero

Perform a similar calculation for the third and fourth rows:

Example: Solution of a Tridiagonal System

upper triangular form Back substitution to generate the final solution

How to implement solution of tridiagonal system in Octave?

 algorithm does not include partial pivoting

Final notes: Computational effort for Gauss elimination is proportional to n3 Tridiagonal systems – proportional to n