Welcome to our community

Be a part of something great, join today!

Sufyan's question via email about solving a system with Gaussian Elimination and Partial Pivoting

Prove It

Well-known member
MHB Math Helper
Jan 26, 2012
1,403
We write the system as an augmented matrix

$\displaystyle \begin{align*} \left[ \begin{matrix} \phantom{-}1 & 4 & \phantom{-}1 & 0 & \phantom{-}5 \\ \phantom{-}1 & 6 & -1 & 4 & \phantom{-}7 \\ -1 & 2 & -9 & 2 & -9 \\ \phantom{-}0 & 1 & \phantom{-}2 & 0 & \phantom{-}4 \end{matrix} \right] \end{align*}$

In order to solve the system we must upper triangularise the matrix. As we do, the right hand column becomes matrix $\displaystyle \begin{align*} \mathbf{g} \end{align*}$.

As the elements in column 1 have a maximum magnitude of 1, there is no need to interchange any rows. So we apply R2 - R1 to R2 and R3 + R1 to R3, giving

$\displaystyle \begin{align*} \left[ \begin{matrix} \phantom{-}1 & 4 & \phantom{-}1 & 0 & \phantom{-}5 \\ \phantom{-}0 & 2 & -2 & 4 & \phantom{-}2 \\ \phantom{-}0 & 6 & -8 & 2 & -4 \\ \phantom{-}0 & 1 & \phantom{-}2 & 0 & \phantom{-}4 \end{matrix} \right] \end{align*}$

Now looking at the elements on or below the main diagonal in column 2, the element with the highest magnitude is in row 3, so we have to interchange rows 2 and 3.

$\displaystyle \begin{align*} \left[ \begin{matrix} \phantom{-}1 & 4 & \phantom{-}1 & 0 & \phantom{-}5 \\ \phantom{-}0 & 6 & -8 & 2 & -4\\ \phantom{-}0 & 2 & -2 & 4 & \phantom{-}2 \\ \phantom{-}0 & 1 & \phantom{-}2 & 0 & \phantom{-}4 \end{matrix} \right] \end{align*}$

Now we must apply R3 - (1/3)R2 to R3 and R4 - (1/6)R2 to R2.

$\displaystyle \begin{align*} \left[ \begin{matrix} \phantom{-}1 & 4 & \phantom{-}1 & \phantom{-}0 & \phantom{-}5 \\ \phantom{-}0 & 6 & -8 & \phantom{-}2 & -4\\ \phantom{-}0 & 0 & \phantom{-}\frac{2}{3} & \phantom{-}\frac{10}{3} & \phantom{-}\frac{10}{3} \\ \phantom{-}0 & 0 & \phantom{-}\frac{10}{3} & -\frac{1}{3} & \phantom{-}\frac{14}{3} \end{matrix} \right] \end{align*}$

Now looking at the elements on or below the main diagonal in column 3, the element with the highest magnitude is in row 4, so we must interchange rows 3 and 4.

$\displaystyle \begin{align*} \left[ \begin{matrix} \phantom{-}1 & 4 & \phantom{-}1 & \phantom{-}0 & \phantom{-}5 \\ \phantom{-}0 & 6 & -8 & \phantom{-}2 & -4\\ \phantom{-}0 & 0 & \phantom{-}\frac{10}{3} & -\frac{1}{3} & \phantom{-}\frac{14}{3}\\ \phantom{-}0 & 0 & \phantom{-}\frac{2}{3} & \phantom{-}\frac{10}{3} & \phantom{-}\frac{10}{3} \end{matrix} \right] \end{align*}$

Now we must apply R4 - (1/5)R3 to R4.

$\displaystyle \begin{align*} \left[ \begin{matrix} \phantom{-}1 & 4 & \phantom{-}1 & \phantom{-}0 & \phantom{-}5 \\ \phantom{-}0 & 6 & -8 & \phantom{-}2 & -4\\ \phantom{-}0 & 0 & \phantom{-}\frac{10}{3} & -\frac{1}{3} & \phantom{-}\frac{14}{3}\\ \phantom{-}0 & 0 & \phantom{-}0 & \phantom{-}\frac{17}{5} & \phantom{-}\frac{12}{5} \end{matrix} \right] \end{align*}$


We can now read off $\displaystyle \begin{align*} \mathbf{g} = \left[ \begin{matrix} \phantom{-}5 \\ -4 \\ \phantom{-}\frac{14}{3} \\ \phantom{-}\frac{12}{5} \end{matrix} \right] \end{align*}$ and solving for $\displaystyle \begin{align*} \mathbf{x} \end{align*}$ using back substitution we have

$\displaystyle \begin{align*} \frac{17}{5}\,x_4 &= \frac{12}{5} \\ x_4 &= \frac{12}{17} \\ \\ \frac{10}{3}\,x_3 - \frac{1}{3}\,x_4 &= \frac{14}{3} \\ \frac{10}{3}\,x_3 - \frac{4}{17} &= \frac{14}{3} \\ 10\,x_3 - \frac{12}{17} &= 14 \\ 10\,x_3 &= \frac{250}{17} \\ x_3 &= \frac{25}{17} \\ \\ 6\,x_2 - 8\,x_3 + 2\,x_4 &= -4 \\ 6\,x_2 - \frac{200}{17} + \frac{24}{17} &= -4 \\ 6\,x_2 &= \frac{108}{17} \\ x_2 &= \frac{18}{17} \\ \\ x_1 + 4\,x_2 + x_3 &= 5 \\ x_1 + \frac{72}{17} + \frac{25}{17} &= 5 \\ x_1 &= -\frac{12}{17} \end{align*}$


So the solution to the system is $\displaystyle \begin{align*} \mathbf{x} = \frac{1}{17}\,\left[ \begin{matrix} -12 \\ \phantom{-}18 \\ \phantom{-}25 \\ \phantom{-}12 \end{matrix} \right] \end{align*}$.