Gaussian elimination

Gaussian elimination is an algorithm in linear algebra for determining the solutions of a system of linear equations. First we do a forward elimination: Gaussian elimination reduces a given system to either triangular. Next, we do a backward elimination to solve the linear system

Problem

We want to solve the following linear system of $n$ equations with $n$ unknowns $x_{1}, x_{2}, \dots, x_{n}$ :

{\begin{matrix} a_{12} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} = b_{2} \\ ⋮ \\ a_{n 1} x_{1} + a_{n 2} x_{2} + \dots + a_{n n} x_{n} = b_{n} \end{matrix}

In the matrix form, we have

A x = b

with

A x = (\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{array}) (\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}) = (\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix}) = b

Example of resolution

Consider the following system:

{\begin{array}{cccccccl} x_{1} & + & 2 x_{2} & + & 2 x_{3} & = & 2 & L_{1} \\ x_{1} & + & 3 x_{2} & - & 2 x_{3} & = & - 1 & L_{2} \\ 3 x_{1} & + & 5 x_{2} & + & 8 x_{3} & = & 8 & L_{3} \end{array}

with

A = (\begin{array}{ccc} 1 & 2 & 2 \\ 1 & 3 & - 2 \\ 3 & 5 & 8 \end{array}), x = (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}), b = (\begin{matrix} 2 \\ - 1 \\ 8 \end{matrix})

First step of the Gaussian elimination: we eliminate $x_{1}$ in the lines $L_{2}$ and $L_{3}$ :

{\begin{array}{cccccccl} x_{1} & + & 2 x_{2} & + & 2 x_{3} & = & 2 & L_{1} \\ x_{2} & - & 4 x_{3} & = & - 3 & L_{2} \leftarrow L_{2} - L_{1} \\ - x_{2} & + & 2 x_{3} & = & 2 & L_{3} \leftarrow L_{3} - 3 L_{1} \end{array}

Second step of the Gaussian elimination: we eliminate $x_{2}$ in the line $L_{3}$ :

{\begin{array}{cccccccl} x_{1} & + & 2 x_{2} & + & 2 x_{3} & = & 2 & L_{1} \\ x_{2} & - & 4 x_{3} & = & - 3 & L_{2} \\ - & 2 x_{3} & = & - 1 & L_{3} \leftarrow L_{3} + L_{2} \end{array}

By backward elimination we solve the linear system, we get the solution $x$ :

x = (\begin{matrix} 3 \\ - 1 \\ 1 / 2 \end{matrix})

Gaussian Elimination algorithm: forward elimination and triangular form

k = 1, \dots, n - 1 {\begin{cases} a_{i j}^{(k + 1)} = a_{i j}^{(k)} & i = 1, \dots, k & j = 1, \dots, n \\ a_{i j}^{(k + 1)} = 0 & i = k + 1, \dots, n & j = 1, \dots, k \\ a_{i j}^{(k + 1)} = a_{i j}^{(k)} - \frac{a_{i k}^{(k)} a_{k j}^{(k)}}{a_{k k}^{(k)}} & i = k + 1, \dots, n & j = k + 1, \dots, n \\ b_{i}^{(k + 1)} = b_{i}^{(k)} & i = 1, \dots, k \\ b_{i}^{(k + 1)} = b_{i}^{(k)} - \frac{a_{i k}^{(k)} b_{k}^{(k)}}{a_{k k}^{(k)}} & i = k + 1, \dots, n \end{cases}

Let $U$ the triangular upper matrix, we have

U = (u_{i j})_{1 \leq i, j \leq n} = (a_{i j}^{(n)})_{1 \leq i, j \leq n}

Gaussian Elimination algorithm: backward elimination

Now the matrix $A$ is in triangular form $U$ , we can solve:

U x = b^{(n)}

with $b^{(n)}$ the second member after the same operations than $U$ .

We use a backward elimination for solving $U x = b^{(n)}$ :

{\begin{cases} x_{n} = \frac{y_{n}}{u_{n n}} = \frac{y_{n}}{a_{n n}^{(n)}}; \\ x_{i} = \frac{1}{u_{i i}} (y_{i} - \sum_{j = i + 1}^{n} u_{i j} x_{j}) = \frac{1}{a_{i i}^{(n)}} (y_{i} - \sum_{j = i + 1}^{n} a_{i j}^{(n)} x_{j}) & \forall i = n - 1, n - 2, \dots, 1. \end{cases}

Problem

Example of resolution

Gaussian Elimination algorithm: forward elimination and triangular form

Gaussian Elimination algorithm: backward elimination

Articles in the same category