# Gaussian elimination

(Difference between revisions)
 Revision as of 22:23, 16 December 2005 (view source)Tsaad (Talk | contribs) (capitalized Phi)← Older edit Revision as of 22:30, 16 December 2005 (view source)Jasond (Talk | contribs) Newer edit → Line 1: Line 1: == Gauss Elimination == == Gauss Elimination == - We consider the system of linear equations '''$A\Phi = B$''' or
+ We consider the system of linear equations '''$A\phi = B$''' or
:$:[itex] \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:$
[/itex]
- By using the formula:
+ The solution to the original system is found via '''back substitution'''.  The solution to the last equation is + :$:[itex] - \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}'. -$
+ [/itex] - Solve the equation of the kth row for xk, then substitute back into the equation of the (k-1)st row to obtain a solution for  (k-1)st raw, and so on till k = 1. + + 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. - Return to [[Numerical methods | Numerical Methods]] +

## 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$.