# Gaussian Elimination with Scaled Row Pivoting for numerical methods

I am solving a system first with basic Gaussian Elimination, and then Gaussian Elimination with scaled row pivoting (used in numerical methods)

Basic Gaussian Elimination on the system $Ax=b$: \begin{equation} \begin{pmatrix}-1& 1& -4 \\ 2& 2& 0 \\ 3& 3& 2 \end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} = \begin{pmatrix}0\\1\\\frac{1}{2}\end{pmatrix} \end{equation}

Let $A_i$ denote the $i^{th}$ row of matrix $A$ and let $A^{(1)} A^{(2)}...$ denote the matrix after the first, second and so forth elementary row operations. Note that
$A^{0} =A$.

Compute the following elementary row operations: \begin{align} A^{(1)}_2 =& A^{(0)}_2 - (-2)A^{(0)}_1 \\ A^{(1)}_3 =& A^{(0)}_3 - (-3)A^{(0)}_1 \end{align}

This yields: This yields: \begin{equation} \begin{pmatrix}-1& 1& -4 \\ 0& 4& -8 \\ 0& 6& -10 \end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} = \begin{pmatrix}0\\1\\-1\end{pmatrix} \end{equation}

Compute: \begin{equation} A^{(2)}_3 = A^{(1)}_3 - (\frac{3}{2})A^{(1)}_2\end{equation} This yields: \begin{equation} \begin{pmatrix}-1& 1& -4\\ 0& 4& -8\\ 0& 0& 2\end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}= \begin{pmatrix}0\\1\\-1\end{pmatrix} \end{equation} Thus we have: \begin{equation} x=\begin{pmatrix}\frac{5}{4}\\ \frac{-3}{4}\\ \frac{-1}{2}\end{pmatrix}\end{equation}

Now I will solve the same system with Scaled Row Pivoting. The $i^{th}$ element of the list $S$ will denote the maximum element in row $i$ in matrix $A$. $P$ will denote the order of the rows. Initially we have: \begin{equation} S = (4, 2, 3) \\ P = (2, 1, 3) \end{equation} Swap rows $1$ and $2$ since row $2$ has the maximum pivot relative to its row: \begin{equation} \begin{pmatrix}2&2&0\\ -1&1&-4\\ 3& 3& 2\end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} = \begin{pmatrix}1\\0\\\frac{1}{2}\end{pmatrix} \end{equation} Now compute the following elementary row operations w.r.t the ordering given by $p$: \begin{align} A^{(1)}_1 =& A^{(0)}_1 - (\frac{-1}{2})A^{(0)}_2 \\ A^{(1)}_3 =& A^{(0)}_3 - (\frac{3}{2})A^{(0)}_2 \end{align} This yields: \begin{equation} \begin{pmatrix}2&2&0\\ 0&2&-4\\ 0&0&2\end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}= \begin{pmatrix}1\\\frac{1}{2}\\-1 \end{pmatrix} \end{equation} Now using back substitution to solve for $x$ we get: \begin{equation} x=\begin{pmatrix}\frac{-1}{4}\\\frac{3}{4}\\\frac{-1}{2}\end{pmatrix} \end{equation} Clearly, I must have made a mistake along the way since the solutions for both methods are not the same! I know that the scaled pivoting is incorrect as I checked my solution in a CAS and it matched the solution for the Basic Method.

Please show me what I have done wrong in the scaled pivoting algorithm.

• Check $x_2$ from your second back substitution. – ccorn Jul 28 '13 at 21:58

## 1 Answer

You miscomputed $x_2$ in the back substitution of the row-pivoted system, that's the origin of the discrepancy.

• You are correct! and WooooW! What a waste of time typing all of that up. Well not a waste, just more TeX practice! – CodeKingPlusPlus Jul 28 '13 at 22:03
• @CodeKingPlusPlus: Your expenses in efforts to accurately describe the problem have been my savings in efforts to find the error. In that sense, thanks, and anytime again. – ccorn Jul 28 '13 at 22:36
• If you are good with vector norms, check this question out: math.stackexchange.com/questions/454411/… – CodeKingPlusPlus Jul 28 '13 at 23:15