Row pivoting

• Remedy for instability: perform row pivoting so that $a_{kk}$ is always the largest entry in the column.
• Since $l_{ij}=a_{ij}/a_{jj}$, row pivoting guarantees that $|l_{ij}|\le 1$.

With row pivoting, our factorization looks like

$$PA=LU$$

where $P$ is a permutation of the rows of $A$. $P$ is key for the existence of the LU factorization.

• Note that although $L$ is bounded by definition, there is no guarantee for $U$.
• In most practical cases, this algorithm is very accurate.
• This factorization exists for all square matrices.
• This factorization is unique for all matrices such that $\det (A[1:k,1:k])\ne 0$ for all $1\le k\le n-1$.

Let’s apply row pivoting to our previous case:

$$\begin{array}{c}A=\left(\begin{array}{cc}ϵ& 1\\ 1& \pi \end{array}\right),PA=\left(\begin{array}{cc}1& \pi \\ ϵ& 1\end{array}\right)\\ L=\left(\begin{array}{cc}1& 0\\ ϵ& 1\end{array}\right),U=\left(\begin{array}{cc}1& \pi \\ 0& 1-ϵ\pi \end{array}\right),PA=LU\end{array}$$

This new factorization is backward stable and accurate.

Stability of the LU factorization, Forward and backward error, Backward error analysis for LU