3

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^\text{th}$ row of matrix $A$ and let $A^{(1)} A^{(2)}\ldots$ 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: $$ \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 - \tfrac{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^\text{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 - \tfrac{-1}{2}A^{(0)}_2 \\ A^{(1)}_3 &= A^{(0)}_3 - \tfrac{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 C.A.S. and it matched the solution for the Basic Method.

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

Rócherz
  • 3,976
CodeKingPlusPlus
  • 7,342

1 Answers1

3

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

ccorn
  • 9,803
  • 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
  • 2
    @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: http://math.stackexchange.com/questions/454411/proving-the-triangle-inequality-for-the-l-2-norm-x-2-sqrtx-12x-22-ld – CodeKingPlusPlus Jul 28 '13 at 23:15