Ch3.2.1 Part 3: Pivoting Strategies

I just went to an emotional wedding.

Even the cake was in tiers.

What do you call a belt made out of watches?

A waist of time.

\[ \scriptsize{ \begin{array} {llll} a_{ij}^{(k)} & = & a_{ij}^{(k-1)}, & 1 \leq i \leq k-1, & 1 \leq j \leq n+1 \\ a_{ij}^{(k)} & = & 0, & k \leq i \leq n, & 1 \leq j \leq k-1 \\ a_{ij}^{(k)} & = & a_{ij}^{(k-1)} - m_{i,k-1} \cdot a_{k-1,j}^{(k-1)}, & k \leq i \leq n, & k \leq j \leq n+1 \\ m_{i,k-1} & = & \frac{a_{i,k-1}^{(k-1)}}{a_{k-1,k-1}^{(k-1)}}, & {a_{k-1,k-1}^{(k-1)}} \neq 0 & k \leq i \leq n \end{array} } \]

• When performing Gaussian elimination, we construct multipliers \( m_{jk} \), where

\[ m_{jk} = \frac{a_{jk}}{a_{kk}^{(k)}} \]

• Note that \( |m_{jk}| >> 1 \) whenever \( |a_{kk}^{(k)}| << |a_{jk}| \).
• Round-off error when \( a_{kj}^{(k)} \) was computed is multiplied by \( m_{jk} \) when computing \( a_{ij}^{(k+1)} \), which compounds the error.

\[ a_{ij}^{(k+1)} = a_{ij}^{(k)} - m_{ik} \cdot a_{kj}^{(k)} \]

When back solving, if \( a_{kk}^{(k)} \cong 0 \), then any error in numerator is greatly enlarged.

\[ \small{ \begin{aligned} x_n & = \frac{a_{n,n+1}^{(n)}}{a_{n,n}^{(n)}} \\ x_i & = \frac{ a_{i,n+1}^{(n)}-a_{i,n}^{(n)}x_n-a_{i,n-1}^{(n)}x_{n-1} -\ldots-a_{i,i+1}^{(n)}x_{i+1} } {a_{i,i}^{(n)}} \\ & = \frac{ a_{i,n+1}^{(n)}- \sum_{j \, = \, i+1}^n a_{i,j}^{(n)}x_j }{a_{i,i}^{(n)}}, \,\, i = n-1, n-2, \ldots, 1 \end{aligned} } \]

Consider the system of equations

\[ \matrix{ 0.003000 x_1 & + & 59.14 x_2 & = & 59.17 \\ 5.291x_1 & - & 6.130 x_2 & = & 46.78 } \]

The exact solution is \( x_1 = 10, \, x_2 = 1 \).

Using machine arithmetic with four digit rounding:

\[ \small{ \begin{aligned} & \begin{bmatrix} 0.003000 & 59.14 & 59.17 \\ 5.291 & 6.130 & 46.78 \end{bmatrix} \underrightarrow{R_2 = R_2 - m_{21} R_1} \\ \\ & \begin{bmatrix} 0.003000 & 59.14 & 59.17 \\ 0 & -104300 & -104400 \end{bmatrix} m_{21} = \frac{5.291}{0.003000} \cong 1764 \end{aligned} } \]

\[ \small{ \begin{aligned} -6.130-(1764)(59.14) & = -6.130-104322.96 \\ & \cong -6.130 - 104300 = -104293.87 \\ & \cong -104300 \\ 46.78 - (1764)(59.17) &= 46.78-104375.88 \\ & \cong 46.78-104400 = -104353.22 \\ & \cong -104400 \end{aligned} } \]

Using machine arithmetic with four digit rounding:

\[ \small{ \begin{aligned} & \begin{bmatrix} 0.003000 & 59.14 & 59.17 \\ 0 & -104300 & -104400 \end{bmatrix} \\ \\ x_2 & = \frac{-104400}{-104300} \cong 1.001 \\ x_1 & = \frac{59.17-(59.14)(1.001)}{0.003000} = \frac{59.17-59.20}{0.003000} = -10.00\\ \end{aligned} } \]

Actual answer: \( x_1 = 1, x_2 = 10\, \) (200% relative error for \( x_2 \))

Recall from the previous slide:

\[ \small{ \begin{aligned} x_2 & = \frac{-104400}{-104300} \cong 1.001 \\ x_1 & = \frac{59.17-(59.14)(1.001)}{0.003000} = \frac{59.17-59.20}{0.003000} = -10.00\\ \end{aligned} } \]

The 0.001 error in \( x_2 \) is multiplied by \( \small{59.14/0.003000 \cong 20,000} \)

(Ab <- matrix(c(0.003,5.291,59.14,-6.130,59.17,46.78),2))

      [,1]  [,2]  [,3]
[1,] 0.003 59.14 59.17
[2,] 5.291 -6.13 46.78

rrefmatrix(Ab)

     [,1] [,2] [,3]
[1,]    1    0   10
[2,]    0    1    1

refmatrix(Ab)

      [,1]       [,2]       [,3]
[1,] 0.003      59.14      59.17
[2,] 0.000 -104309.38 -104309.38

rrefmatrix(Ab)

     [,1] [,2] [,3]
[1,]    1    0   10
[2,]    0    1    1

Using machine arithmetic with four digit rounding:

Using machine arithmetic with four digit rounding:

Using machine arithmetic with four digit rounding:

• To avoid the problem of a small pivot \( a_{kk}^{(k)} \), we can search for a larger pivot in a different row and perform a row interchange.
• This is called partial pivoting.

\[ \small{ \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & | & a_{1,n+1} \\ a_{21} & a_{22} & \cdots & a_{2n} & | & a_{2,n+1} \\ \vdots & \vdots & \ddots & \vdots & | & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} & | & a_{n,n+1} \end{bmatrix} } \]

• For example, in the first column, look for

\[ \max \{ |a_{i1}| : 1\leq i \leq n \} \]

Consider again the system of equations

\[ \matrix{ 0.003000 x_1 & + & 59.14 x_2 & = & 59.17 \\ 5.291x_1 & - & 6.130 x_2 & = & 46.78 } \]

For this system, we start with a row switch:

\[ \small{ \begin{aligned} & \begin{bmatrix} 0.003000 & 59.14 & 59.17 \\ 5.291 & 6.130 & 46.78 \end{bmatrix} \\ \\ \underrightarrow{R_2 \leftrightarrow R_1} & \begin{bmatrix} 5.291 & 6.130 & 46.78 \\ 0.003000 & 59.14 & 59.17 \end{bmatrix} \end{aligned} } \]

Using machine arithmetic with four digit rounding:

\[ \small{ \begin{aligned} & \begin{bmatrix} 5.291 & 6.130 & 46.78 \\ 0.003000 & 59.14 & 59.17 \end{bmatrix} \underrightarrow{R_2 = R_2 - m_{21} R_1} \\ \\ & \begin{bmatrix} 5.291 & -6.130 & 46.78 \\ 0 & 59.14 & 59.14 \end{bmatrix} m_{21} = \frac{0.003000}{5.291} \cong 0.0005670 \end{aligned} } \]

Using machine arithmetic with four digit rounding:

\[ \small{ \begin{aligned} & \begin{bmatrix} 5.291 & -6.130 & 46.78 \\ 0 & 59.14 & 59.14 \end{bmatrix} \\ \\ x_2 & = \frac{59.14}{59.14} =1.000 \\ x_1 & = \frac{46.78+(6.130)(1.000)}{5.291} = \frac{52.91}{5.291} = 10.00 \\ \end{aligned} } \]

Actual answer: \( x_1 = 1, x_2 = 10 \)

refmatrix(Ab)

      [,1]     [,2]     [,3]
[1,] 5.291 -6.13000 46.78000
[2,] 0.000 59.14348 59.14348

rrefmatrix(Ab)

     [,1] [,2] [,3]
[1,]    1    0   10
[2,]    0    1    1

• Partial pivoting doesn't always work, as seen next.
• Consider the related system of equations, where the previous first row has been scaled by 10,000.

\[ \matrix{ 30.00 x_1 & + & 591400 x_2 & = & 591700 \\ 5.291x_1 & - & 6.130 x_2 & = & 46.78 } \]

• This system does not need a row switch, since

\[ \max \{ |a_{i1}| : 1\leq i \leq n \} = a_{11} = 30.00 \]

Using machine arithmetic with four digit rounding:

\[ \small{ \begin{aligned} & \begin{bmatrix} 30.00 & 591400 & 591700 \\ 5.291 & 6.130 & 46.78 \end{bmatrix} \underrightarrow{R_2 = R_2 - m_{21} R_1} \\ \\ & \begin{bmatrix} 30.00 & 591400 & 591700 \\ 0 & -104300 & -104400 \end{bmatrix} m_{21} = \frac{5.291}{30.00} \cong 0.1764 \end{aligned} } \]

Using machine arithmetic with four digit rounding:

\[ \small{ \begin{aligned} & \begin{bmatrix} 30.00 & 591400 & 591700 \\ 0 & -104300 & -104400 \end{bmatrix} \\ \\ x_2 & = \frac{-104400}{-104300} \cong 1.001 \\ x_1 & = \frac{591700-(591400)(1.001)}{30.00} \cong \frac{591700-592000}{30.00} = -10.00\\ \end{aligned} } \]

Actual answer: \( x_1 = 1, x_2 = 10\, \) (200% relative error for \( x_2 \))

refmatrix(Ab)

     [,1]      [,2]      [,3]
[1,]   30  591400.0  591700.0
[2,]    0 -104309.4 -104309.4

rrefmatrix(Ab)

     [,1] [,2] [,3]
[1,]    1    0   10
[2,]    0    1    1

• For a given row \( k \), define

\[ \small{s_k = \max_{1\leq j \leq n} |a_{kj}| } \]

• For row switch, select first possible row \( p \) below row \( k \) with

\[ \small{ \frac{|a_{pk}|}{s_p} = \max_{k \leq i \leq n} \frac{|a_{ik}|}{s_i} } \]

\[ \small{ \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & | & a_{1,n+1} \\ a_{21} & a_{22} & \cdots & a_{2n} & | & a_{2,n+1} \\ \vdots & \vdots & \ddots & \vdots & | & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} & | & a_{n,n+1} \end{bmatrix} } \]

Consider again the system of equations

\[ \small{ \matrix{ 30.00 x_1 & + & 591400 x_2 & = & 591700 \\ 5.291x_1 & - & 6.130 x_2 & = & 46.78 } } \]

From lines 3 and 4 below, we will need to perform \( R_1 \leftrightarrow R_2 \):

\[ \small{ \begin{aligned} s_1 & = \max_{1\leq j \leq 2} |a_{1j}| =591400 \\ s_2 & = \max_{1\leq j \leq 2} |a_{2j}| = 6.130 \\ \frac{|a_{11}|}{s_1} & = \frac{30.00}{591400} \cong 0.00005073 \\ \frac{|a_{21}|}{s_2} & = \frac{5.291}{6.130} \cong 0.8631 \end{aligned} } \]

Using machine arithmetic with four digit rounding:

\[ \small{ \begin{aligned} & \begin{bmatrix} 5.291 & 6.130 & 46.78 \\ 30.00 & 591400 & 591700 \end{bmatrix} \underrightarrow{R_2 = R_2 - m_{21} R_1} \\ \\ & \begin{bmatrix} 5.291 & -6.130 & 46.78 \\ 0 & 591400 & 591400 \end{bmatrix} m_{21} = \frac{30.00}{5.291} \cong 5.670 \end{aligned} } \]

Using machine arithmetic with four digit rounding:

\[ \small{ \begin{aligned} & \begin{bmatrix} 5.291 & -6.130 & 46.78 \\ 0 & 591400 & 591400 \end{bmatrix} \\ \\ x_2 & = \frac{591400}{591400} =1.000 \\ x_1 & = \frac{46.78+(6.130)(1.000)}{5.291} = \frac{52.91}{5.291} = 10.00\\ \end{aligned} } \]

Actual answer: \( x_1 = 1, x_2 = 10 \)

refmatrix(Ab)

      [,1]      [,2]      [,3]
[1,] 5.291     -6.13     46.78
[2,] 0.000 591434.76 591434.76

rrefmatrix(Ab)

     [,1] [,2] [,3]
[1,]    1    0   10
[2,]    0    1    1