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

Gaussian elimination

From CFD-Wiki

(Difference between revisions)
Jump to: navigation, search
(capitalized Phi)
Line 1: Line 1:
== Gauss Elimination ==
== Gauss Elimination ==
-
We consider the system of linear equations '''<math> A\Phi = B </math>''' or <br>
+
We consider the system of linear equations '''<math> A\phi = B </math>''' or <br>
:<math>  
:<math>  
\left[  
\left[  
Line 74: Line 74:
\begin{matrix}
\begin{matrix}
     {b_1^' }  \\  
     {b_1^' }  \\  
-
   {b_1^' }  \\  
+
   {b_2^' }  \\  
   .  \\
   .  \\
-
   {b_1^' }  \\  
+
   {b_n^' }  \\  
\end{matrix}
\end{matrix}
Line 84: Line 84:
</math> <br>
</math> <br>
-
By using the formula: <br>
+
The solution to the original system is found via '''back substitution'''.  The solution to the last equation is
 +
 
:<math>
:<math>
-
\phi_i  = {1 \over {a_{ii}^' }}\left( {b_i^'  - \sum\limits_{j = i + 1}^n {a_{ij}^' \phi_j } } \right)
+
\phi_n = b_n^'/a_{nn}'.
-
</math> <br>
+
</math>
-
Solve the equation of the k<sup>th</sup> row for x<sup>k</sup>, then substitute back into the equation of the (k-1)<sup>st</sup> row to obtain a solution for  (k-1)<sup>st</sup> raw, and so on till k = 1.
+
 +
This result may now be substituted into the second to last equation, allowing us to solve for <math>\phi_{n-1}</math>.  Repetition of this substitution process will give us the complete solution vector.  The back substitution process may be expressed as
 +
 +
:<math>
 +
\phi_i  = {1 \over {a_{ii}^' }}\left( {b_i^'  - \sum\limits_{j = i + 1}^n {a_{ij}^' \phi_j } } \right),
 +
</math>
-
----
+
where <math>i=n,n-1,\ldots,1</math>.
-
<i> Return to [[Numerical methods | Numerical Methods]] </i>
+

Revision as of 22:30, 16 December 2005

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