Method – Gaussian elimination.

Method

Gaussian elimination is a method of solving a system of linear equations. Given a set of $n$ equations with $n$ variables,

$begin{array}{ccccccccc} a_1 x_{1} &+& a_2 x_{2} & + & ... & + & a_n x_{n} & = & A\\ b_1 x_{1} &+& b_2 x_{2} & + & ... & + & b_n x_{n} & = & B \ vdots& & vdots & & & & vdots \ c_1 x_{1} &+& c_2 x_{2} & + & ... & + & c_n x_{n} & = & C end{array}$

Where $A$ , $B$ and $C$ are real numbers. We rearrange the above system of equations into the form,

$begin{array}{cccccccccc} x_{1} & = & cfrac{A}{a_1} & - & cfrac{a_2}{a_1} x_{2} & - & ... & - & cfrac{a_n}{a_1} x_{n} \ x_{2} & = & cfrac{B}{b_2} & - & cfrac{b_1}{b_2} x_{1} & - & ... & - & cfrac{b_n}{b_2} x_{n} \ vdots& & & vdots & & & vdots \ x_{n} & = & cfrac{C}{c_n} & - & cfrac{c_2}{c_n} x_{1} & - & ... & - & cfrac{c_{n-1}}{c_n} x_{n} end{array}$

The above system of rearranged equations can be rewritten in the form

$mathbf{x_{i+1}} = mathbf{Gx_i} + mathbf{h}$

Where $mathbf{x_{i+1}}$ , $mathbf{h}$ , $mathbf{x_i}$ are vectors, and $mathbf{G}$ is a matrix. Using some initial guess vector $mathbf{V} = (x'_1, x'_2, ..., x'_n)$ , the values of $mathbf{x_{i+1}}$ converge to the solutions of the system of equations.

Convergence

The Gauss-Jacobi method for a set of linear equations of the form

$mathbf{Ax} = mathbf{b}$

is guaranteed to converge if $mathbf{A}$ is diagonally dominant. This does not imply however that if $mathbf{A}$ is not diagonally dominant that the method will fail, as diagonal dominance is a sufficient but not necessary condition.