# Gaussian elimination

(Difference between revisions)
 Revision as of 07:40, 27 September 2005 (view source)Zxaar (Talk | contribs)← Older edit Revision as of 07:55, 27 September 2005 (view source)Zxaar (Talk | contribs) Newer edit → Line 28: Line 28: \right] \right] [/itex] [/itex] + 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} + {x_1 } \\ + {x_2 } \\ + . \\ + {x_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:
+ :$+ x_i = {1 \over {a_{ii}^' }}\left( {b_i^' - \sum\limits_{j = i + 1}^n {a_{ij}^' x_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.

## Gauss Elimination

We consider the system of linear equations $Ax = 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} {x_1 } \\ {x_2 } \\ . \\ {x_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} {x_1 } \\ {x_2 } \\ . \\ {x_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:

$x_i = {1 \over {a_{ii}^' }}\left( {b_i^' - \sum\limits_{j = i + 1}^n {a_{ij}^' x_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.