Gaussian elimination
From CFDWiki
(Capital Phi represents a vector, lowercase phi represents an element in that vector) 
(→Algorithm) 

(8 intermediate revisions not shown)  
Line 1:  Line 1:  
== Description ==  == Description ==  
  We consider the system of linear equations '''<math> A\  +  We consider the system of linear equations '''<math> A\phi = b </math>''' or <br> 
:<math>  :<math>  
\left[  \left[  
Line 60:  Line 60:  
</math> <br>  </math> <br>  
  After performing elementary  +  After performing elementary row operations the '''augmented matrix''' is put into the upper triangular form: <br> 
:<math>  :<math>  
Line 103:  Line 103:  
:: for i:=k+1 step until n do <br>  :: for i:=k+1 step until n do <br>  
::: <math>m = {{a_{ik} } \over {a_{kk} }} </math> <br>  ::: <math>m = {{a_{ik} } \over {a_{kk} }} </math> <br>  
  ::: for j:=  +  ::: for j:= 1 step until n do <br> 
:::: <math> a_{ij}=a_{ij}ma_{kj}</math> <br>  :::: <math> a_{ij}=a_{ij}ma_{kj}</math> <br>  
::: end loop (j) <br>  ::: end loop (j) <br>  
Line 110:  Line 110:  
: end loop (k) <br>  : end loop (k) <br>  
Back substitution phase  Back substitution phase  
  : for k:=n stepdown until 1 do <br>  +  : for k:= n stepdown until 1 do <br> 
  :: for i:=  +  :: for i:= 1 step until k1 do <br> 
  ::: <math>  +  ::: <math>b_i=b_ia_{ik}/a_{kk}b_{k}</math> <br> 
:: end loop (i) <br>  :: end loop (i) <br>  
:: <math>\phi_{k}=b_{k}/a_{kk}</math><br>  :: <math>\phi_{k}=b_{k}/a_{kk}</math><br>  
Line 118:  Line 118:  
== Important Considerations ==  == Important Considerations ==  
  Gaussian elimination is best used for relatively small, relatively full systems of equations. If properly used, it should outperform most iterative methods for these systems. As the system to be solved becomes larger, the overhead associated with the more complicated iterative methods becomes less of an issue, and the iterative methods should outperform Gaussian Elimination. For sparse  +  Gaussian elimination is best used for relatively small, relatively full systems of equations. If properly used, it should outperform most iterative methods for these systems. As the system to be solved becomes larger, the overhead associated with the more complicated iterative methods becomes less of an issue, and the iterative methods should outperform Gaussian Elimination. For sparse systems, the use of Gaussian elimination is complicated by the possible introduction of more nonzero entries (fillin). In any case, it is important to keep in mind that the basic algorithm is vulnerable to accuracy issues, including (but not limited to) the distinct possibility of division by zero at various places in the solution process. In practice, it is best to employ safeguards against such problems (e.g. pivoting). 
+  
+  ==External link==  
+  *[http://en.wikipedia.org/wiki/Gaussian_elimination Wikipedia's article ''Gaussian elimination''] 
Latest revision as of 15:08, 22 August 2007
Contents 
Description
We consider the system of linear equations or
To perform Gaussian elimination starting with the above given system of equations we compose the augmented matrix equation in the form:
After performing elementary row operations the augmented matrix is put into the upper triangular form:
The solution to the original system is found via back substitution. The solution to the last equation is
This result may now be substituted into the second to last equation, allowing us to solve for . Repetition of this substitution process will give us the complete solution vector. The back substitution process may be expressed as
where .
Algorithm
Forward elimination phase
 for k:= 1 step until n1 do
 for i:=k+1 step until n do

 for j:= 1 step until n do

 end loop (j)


 end loop (i)
 for i:=k+1 step until n do
 end loop (k)
Back substitution phase
 for k:= n stepdown until 1 do
 for i:= 1 step until k1 do

 end loop (i)

 for i:= 1 step until k1 do
 end loop (k)
Important Considerations
Gaussian elimination is best used for relatively small, relatively full systems of equations. If properly used, it should outperform most iterative methods for these systems. As the system to be solved becomes larger, the overhead associated with the more complicated iterative methods becomes less of an issue, and the iterative methods should outperform Gaussian Elimination. For sparse systems, the use of Gaussian elimination is complicated by the possible introduction of more nonzero entries (fillin). In any case, it is important to keep in mind that the basic algorithm is vulnerable to accuracy issues, including (but not limited to) the distinct possibility of division by zero at various places in the solution process. In practice, it is best to employ safeguards against such problems (e.g. pivoting).