Diagonal dominance and pivoting

The order of equations, and therefore rows in the matrix, is obviously arbitrary, but this may break Gauss Elimination.

E.g.: a system with augmented matrix

\[\begin{split} \begin{bmatrix} 2 & -1 & 0 & 1\\ -1 & 2 & -1 & 0\\ 0 & -1 & 1 & 0\\ \end{bmatrix}\end{split}\]

will work with our GE scheme, but the same system reordered,

\[\begin{split} \begin{bmatrix} 0 & -1 & 1 & 0\\ -1 & 2 & -1 & 0\\ 2 & -1 & 0 & 1\\ \end{bmatrix}\end{split}\]

will fail due to the \(0\) in the element of the first row. The remedy is to swap rows 3 and 1 to match the first example.

Permutation matrix

Swapping rows in matrix algebra is achieved via a permutation matrix (row swap of the identity matrix).

To swap rows 3 and 1, we would use:

\[\begin{split} P = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{bmatrix}\end{split}\]

Diagonal dominance

More generally, if the diagonal element is small we will encounter roundoff error:

\[\begin{split} \begin{bmatrix} \epsilon & -1 & 1 & 0\\ -1 & 2 & -1 & 0\\ 2 & -1 & 0 & 1\\ \end{bmatrix}\end{split}\]

after the first pass leads to:

\[\begin{split} \begin{bmatrix} \epsilon & -1 & 1 & 0\\ -1 & 2 -1/\epsilon & -1 + 1/\epsilon & 0\\ 2 & -1 -1/\epsilon& + 1/\epsilon & 1\\ \end{bmatrix}\end{split}\]

from which we immediately see the danger as \(\epsilon \rightarrow 0\)!

Thus, we don’t want the diagonal to have \(0\) s or small numbers. This motivates the definition of diagonal dominance.

A matrix is said to be diagonally dominant if each diagonal is larger, in absolute value, than the sum of the other elements in the row.

\(|A_{ii}| \ge \sum_{j=1,j \ne i}^{n} |A_{ij}|\)

Example: Which is diagonally dominant?

a) $\( \begin{bmatrix} -2 & 4 & -1 \\ -1 & -1 & 3 \\ 4 & -2 & 1 \\ \end{bmatrix}\)$

b) $\( \begin{bmatrix} 4 & -2 & 1 \\ -2 & 4 & -1 \\ -1 & -1 & 3 \\ \end{bmatrix}\)$

Importance of diagonal dominance

It can be shown that if a matrix is diagonally dominant, it will not benefit from pivoting!

Diagonal dominance contributes generally to numerical stability and accuracy through minimizing roundoff error propogation. This result extends beyond Gauss elimination, and will also be a criteria for matrix factorization methods and the efficient convergence of iterative methods.