At some point, our pivot may be zero. And since the pivot is the divisor in the factors that we build at each step, we cannot go on.
As a consequence of the above, Gauss without pivoting does not always work.
If we divide very different numbers between them, with a comparatively small denominator, we can have problems with the error.

The benefits of pivoting are:

We avoid zeros in the pivot position.
We avoid comparatively small values in the denominator (pivot), which are detrimental from the error point of view.

Exercise¶

Gaussian elimination¶

First, we build the augmented matrix.

Of all the elements below the pivot $\mathbf{{\color{red}1}}$, we choose the largest one, in this case $\mathbf{3}$. We swap its row with the row of the pivot.

$$ \begin{array}{c} r_{1}\\ r_{2}\\ r_{3} \end{array}\left(\begin{array}{rrr|r} \mathbf{{\color{red}1}} & 1 & 3 & -2\\ \mathbf{3} & 0 & 1 & -1\\ \mathbf{1} & -2 & 1 & -3 \end{array}\right) \begin{array}{l} r'_{1} & = & r_{3}\\ r'_{2} & = & r_{1}\\ & & \end{array} $$

We make zeros below the pivot $\mathbf{{\color{red}{3}}}$ performing row operations. We add the row of the pivot multiplied by a factor that has as denominator the pivot and, as numerator, the element under the pivot multiplied by $-1.$

$$ \begin{array}{c} r'_{1}\\[5pt] r'_{2}\\[10pt] r'_{3} \end{array}\left(\begin{array}{rrr|r} \mathbf{{\color{red}3}} & 0 & 1 & -1 \\[5pt] \mathbf{\color{blue}1}& 1 & 3 & -2\\[10pt] \mathbf{\color{ForestGreen}1} & -2 & 1 & -3 \end{array}\right)\begin{array}{rrl} r''_{1} & = & r'_{1}\\ r''_{2} & = & r'_{2}-\dfrac{\mathbf{\color{blue}1}}{\mathbf{{\color{red}3}}}r'_{1}\\ r''_{3} & = & r'_{3}-\dfrac{\mathbf{\color{ForestGreen}1}}{\mathbf{{\color{red}3}}}r'_{1} \end{array} $$

We choose the pivot between the elements below the pivot $\mathbf{{\color{red}{1}}}$ in the second column. We keep the largest in absolute value $\mathbf{-2}$ and swap the new pivot row with the previous one.

$$ \begin{array}{c} r''_{1}\\ r''_{2}\\ r''_{3} \end{array}\left(\begin{array}{rrr|r} 3 & 0 & 1 & -1\\ 0 & \mathbf{{\color{red}{1}}} & \frac{8}{3} & -\frac{5}{3}\\ 0 & \mathbf{-2} & \frac{2}{3} & -\frac{8}{3} \end{array}\right) \begin{array}{l} & &\\ r'''_{2} & = & r''_{3}\\ r'''_{3} & = & r''_{2}\\ \end{array} $$

We make zeros under the new pivot

$$ \begin{array}{c} r'''_{1}\\ r'''_{2}\\[5pt] r'''_{3} \end{array}\left(\begin{array}{rrr|r} 3 & 0 & 1 & -1\\[5pt] 0 & \mathbf{{\color{red}{-2}}} & \frac{2}{3} & -\frac{8}{3}\\[5pt] 0 & \mathbf{\color{blue}1}& \frac{8}{3} & -\frac{5}{3} \end{array}\right)\begin{array}{rrl} r''''_{1} & = & r'''_{1}\\ r''''_{2} & = & r'''_{2}\\ r''''_{3} & = & r'''_{3}-\dfrac{\mathbf{\color{blue}{+1}}}{\mathbf{{\color{red}{-2}}}}r'''_{2} \end{array} $$

And we already have an upper triangular matrix (with zeros below the main diagonal).

$$ \begin{array}{c} r''''_{1}\\ r''''_{2}\\ r''''_{3} \end{array}\left(\begin{array}{rrr|r} 3 & 0 & 1 & -1\\ 0 & -2 & \frac{2}{3} & -\frac{8}{3}\\ 0 & 0 & 3 & -3 \end{array}\right) $$

Backward substitution¶

Returning to the notation with equations, the triangular system is

$$ \begin{array}{rrrrrrr} & 3x & & & + & z & = & -1\\ & & - & 2y & + & (2/3)\,z & = & -8/3\\ & & & & & 3z & = & -3 \end{array} $$

From the last equation we solve for $z$ $$z = -1$$

From the second, for $y$

$$y =\frac{-8/3-2/3\,z}{-2}=\frac{-8/3+2/3}{-2}=\frac{-6/3}{-2}=1 $$

And from the first, for $x$

$$x = \frac{-1-z}{3}=\frac{-1-(-1)}{3}=0$$

And the solution of the system is

$$ \fbox{$x = 0 \quad y = 1 \quad z = -1$} $$

Contents

Introduction¶

Pivoting¶

Exercise¶

Gaussian elimination¶

Backward substitution¶