Gaussian elimination
From CFD-Wiki
(→Algorithm) |
|||
| Line 99: | Line 99: | ||
== Algorithm == | == Algorithm == | ||
| - | + | Forward elimination phase | |
| + | : for k:= 1 step until n-1 do <br> | ||
| + | :: for i:=k+1 step until n do <br> | ||
| + | ::: <math>m = {{A_{ik} } \over {A_{kk} }} </math> <br> | ||
| + | ::: for j:=k+1,3 <br> | ||
| + | :::: <math> A_{ij}=A_{ij}-mA_{kj}</math> <br> | ||
| + | ::: end loop (j) <br> | ||
| + | ::: <math>b_i=b_i-mb_k</math> <br> | ||
| + | :: end loop (i) <br> | ||
| + | : end loop (k) <br> | ||
| + | Back substitution phase | ||
| + | : for k:=n stepdown until 1 do <br> | ||
| + | :: for i:=k+1 step until n <br> | ||
| + | ::: <math>b_k=b_k-A_{ki}b_{i}</math> <br> | ||
| + | :: end loop (i) <br> | ||
| + | :: <math>\phi_{k}=b_{k}/A_{kk}</math><br> | ||
| + | : end loop (k) | ||
== Important Considerations == | == Important Considerations == | ||
Gaussian elimination is best used for relatively small, relatively full systems of equations. If properly used, it will outperform iterative methods for these systems. However, it is important to keep in mind that the basic algorithm is vulnerable to accuracy issues. In practice, it is best to employ safeguards against such problems (e.g. pivoting). | Gaussian elimination is best used for relatively small, relatively full systems of equations. If properly used, it will outperform iterative methods for these systems. However, it is important to keep in mind that the basic algorithm is vulnerable to accuracy issues. In practice, it is best to employ safeguards against such problems (e.g. pivoting). | ||
Revision as of 22:59, 16 December 2005
Description
We consider the system of linear equations 
or
![\left[
\begin{matrix}
{a_{11} } & {a_{12} } & {...} & {a_{1n} } \\
{a_{21} } & {a_{22} } & . & {a_{21} } \\
. & . & . & . \\
{a_{n1} } & {a_{n1} } & . & {a_{nn} } \\
\end{matrix}
\right]
\left[
\begin{matrix}
{\phi_1 } \\
{\phi_2 } \\
. \\
{\phi_n } \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
{b_1 } \\
{b_2 } \\
. \\
{b_n } \\
\end{matrix}
\right]](/W/images/math/a/4/d/a4dada28dd7a85c53604dc331829fc4e.png)
To perform Gaussian elimination starting with the above given system of equations we compose the augmented matrix equation in the form:
![\left[
\begin{matrix}
{a_{11} } & {a_{12} } & {...} & {a_{1n} } \\
{a_{21} } & {a_{22} } & . & {a_{21} } \\
. & . & . & . \\
{a_{n1} } & {a_{n1} } & . & {a_{nn} } \\
\end{matrix}
\left|
\begin{matrix}
{b_1 } \\
{b_2 } \\
. \\
{b_n } \\
\end{matrix}
\right.
\right]
\left[
\begin{matrix}
{\phi_1 } \\
{\phi_2 } \\
. \\
{\phi_n } \\
\end{matrix}
\right]](/W/images/math/4/7/e/47e9bee10079eb1421bd67e9bd451eaf.png)
After performing elementary raw operations the augmented matrix is put into the upper triangular form:
![\left[
\begin{matrix}
{a_{11}^' } & {a_{12}^' } & {...} & {a_{1n}^' } \\
0 & {a_{22}^' } & . & {a_{2n}^' } \\
. & . & . & . \\
0 & 0 & . & {a_{nn}^' } \\
\end{matrix}
\left|
\begin{matrix}
{b_1^' } \\
{b_2^' } \\
. \\
{b_n^' } \\
\end{matrix}
\right.
\right]](/W/images/math/d/c/0/dc0b0d3482afa7d527b8f29f7fd72ea0.png)
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 n-1 do
- for i:=k+1 step until n do
-
- for j:=k+1,3
-
- 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:=k+1 step until n
-
- end loop (i)
-
- for i:=k+1 step until n
- end loop (k)
Important Considerations
Gaussian elimination is best used for relatively small, relatively full systems of equations. If properly used, it will outperform iterative methods for these systems. However, it is important to keep in mind that the basic algorithm is vulnerable to accuracy issues. In practice, it is best to employ safeguards against such problems (e.g. pivoting).
