CFD Online Logo CFD Online URL
www.cfd-online.com
[Sponsors]
Home > Wiki > Gaussian elimination

Gaussian elimination

From CFD-Wiki

Revision as of 22:30, 16 December 2005 by Jasond (Talk | contribs)
Jump to: navigation, search

Gauss Elimination

We consider the system of linear equations  A\phi = B 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]

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]

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]

The solution to the original system is found via back substitution. The solution to the last equation is


\phi_n = b_n^'/a_{nn}'.

This result may now be substituted into the second to last equation, allowing us to solve for \phi_{n-1}. Repetition of this substitution process will give us the complete solution vector. The back substitution process may be expressed as


\phi_i  = {1 \over {a_{ii}^' }}\left( {b_i^'  - \sum\limits_{j = i + 1}^n {a_{ij}^' \phi_j } } \right),

where i=n,n-1,\ldots,1.

My wiki