# 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{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}$$

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{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}$$

Compute: $$A^{(2)}_3 = A^{(1)}_3 - (\frac{3}{2})A^{(1)}_2$$ This yields: $$\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}$$ Thus we have: $$x=\begin{pmatrix}\frac{5}{4}\\ \frac{-3}{4}\\ \frac{-1}{2}\end{pmatrix}$$

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: $$S = (4, 2, 3) \\ P = (2, 1, 3)$$ Swap rows $1$ and $2$ since row $2$ has the maximum pivot relative to its row: $$\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}$$ 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{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}$$ Now using back substitution to solve for $x$ we get: $$x=\begin{pmatrix}\frac{-1}{4}\\\frac{3}{4}\\\frac{-1}{2}\end{pmatrix}$$ 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

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