# Gaussian elimination

(Difference between revisions)
 Revision as of 20:31, 14 December 2005 (view source)Tsaad (Talk | contribs)m (Gauss elimination moved to Gaussian elimination)← Older edit Revision as of 20:37, 15 December 2005 (view source)Tsaad (Talk | contribs) (towards a uniform notation for linear systems : A*Phi = B)Newer edit → Line 1: Line 1: == Gauss Elimination == == Gauss Elimination == - We consider the system of linear equations '''$Ax = b$''' or
+ We consider the system of linear equations '''$A\cdot\phi = B$''' or
:$:[itex] \left[ \left[ Line 12: Line 12: \left[ \left[ \begin{matrix} \begin{matrix} - {x_1 } \\ + {\phi_1 } \\ - {x_2 } \\ + {\phi_2 } \\ . \\ . \\ - {x_n } \\ + {\phi_n } \\ \end{matrix} \end{matrix} \right] \right] Line 52: Line 52: \left[ \left[ \begin{matrix} \begin{matrix} - {x_1 } \\ + {\phi_1 } \\ - {x_2 } \\ + {\phi_2 } \\ . \\ . \\ - {x_n } \\ + {\phi_n } \\ \end{matrix} \end{matrix} \right] \right] Line 86: Line 86: By using the formula: By using the formula: :[itex] :[itex] - x_i = {1 \over {a_{ii}^' }}\left( {b_i^' - \sum\limits_{j = i + 1}^n {a_{ij}^' x_j } } \right) + \phi_i = {1 \over {a_{ii}^' }}\left( {b_i^' - \sum\limits_{j = i + 1}^n {a_{ij}^' \phi_j } } \right)$
[/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. 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.

## Gauss Elimination

We consider the system of linear equations $A\cdot\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_1^' } \\ . \\ {b_1^' } \\ \end{matrix} \right. \right]$

By using the formula:

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

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.