Ch20.1: Pivoting Strategies

Why are there gates around cemeteries?

 Because people are dying to get in!

\[ \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} } \]

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} \)

• 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 \)

• 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 \))

• 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 \)