2
$\begingroup$

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.

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

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

$\endgroup$
3
  • $\begingroup$ You are correct! and WooooW! What a waste of time typing all of that up. Well not a waste, just more TeX practice! $\endgroup$ – CodeKingPlusPlus Jul 28 '13 at 22:03
  • 1
    $\begingroup$ @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. $\endgroup$ – ccorn Jul 28 '13 at 22:36
  • $\begingroup$ If you are good with vector norms, check this question out: math.stackexchange.com/questions/454411/… $\endgroup$ – CodeKingPlusPlus Jul 28 '13 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.