Skip to main content

Subsection 6.4.3 Numerical stability of linear solve via LU factorization

Let us now combine the results from Subsection 6.4.1 and Subsection 6.4.2 into a backward error result for solving \(A x = y \) via LU factorization and two triangular solves.

We refer the interested learner to the proof in the previously mentioned papers [6] [7].

Homework 6.4.3.1.

The question left is how a change in a nonsingular matrix affects the accuracy of the solution of a linear system that involves that matrix. We saw in Subsection 1.4.1 that if

\begin{equation*} A x = y \mbox{ and } A ( x + \delta\!x ) = y + \delta\!y \end{equation*}

then

\begin{equation*} \frac{\| \delta\!x \|}{\| x \|} \leq \kappa( A ) \frac{\| \delta\!y \|}{\| y \|} \end{equation*}

when \(\| \cdot \| \) is a subordinate norm. But what we want to know is how a change in \(A \) affects the solution:

\begin{equation*} A x = y \mbox{ and } ( A + \Delta\!A ) ( x + \delta\!x ) = y \end{equation*}

then

\begin{equation*} \frac{\| \delta\!x \|}{\| x \|} \leq \frac{\kappa( A ) \frac{\| \Delta\!A \|}{\| A \|}} {1 - \kappa( A ) \frac{\| \Delta\!A \|}{\| A \|}}. \end{equation*}

Prove this!

Solution
\begin{equation*} A x = y \mbox{ and } ( A + \Delta\!A ) ( x + \delta\!x ) = y \end{equation*}

implies that

\begin{equation*} ( A + \Delta\!A ) ( x + \delta\!x ) = A x \end{equation*}

or, equivalently,

\begin{equation*} \Delta\!A x + A \delta\!x + \Delta\! A \delta\!x = 0. \end{equation*}

We can rewrite this as

\begin{equation*} \delta\! x = A^{-1} ( - \Delta\!A x - \Delta\! A \delta\!x ) \end{equation*}

so that

\begin{equation*} \| \delta\! x \| = \| A^{-1} ( - \Delta\!A x - \Delta\! A \delta\!x ) \| \leq \| A^{-1} \| \| \Delta\!A \| \| x \| + \| A^{-1} \| \| \Delta\! A \| \| \delta\!x \|. \end{equation*}

This can be rewritten as

\begin{equation*} ( 1 -\| A^{-1} \| \| \Delta\!A \| ) \| \delta\!x \| \leq \| A^{-1} \| \| \Delta\!A \| \| x \| \end{equation*}

and finally

\begin{equation*} \frac{\| \delta\!x \|}{ \| x \| } \leq \frac{\| A^{-1} \| \| \Delta\!A \| } { 1 -\| A^{-1} \| \| \Delta\!A \| } \end{equation*}

and finally

\begin{equation*} \frac{\| \delta\!x \|}{ \| x \| } \leq \frac{\| A \| \| A^{-1} \| \frac{\| \Delta\!A \|}{ \| A \|} } { 1 -\| A \| \| A^{-1} \| \frac{\| \Delta\!A \|}{ \| A \|} }. \end{equation*}

The last homework brings up a good question: If \(A \) is nonsingular, how small does \(\Delta\!A \) need to be for it to be nonsingular?

Proof by contradiction.

Assume that \(A \) is nonsingular,

\begin{equation} \frac{\| \Delta\!A \|}{\| A \|} \lt \frac{1}{\kappa( A )}. \label{assumption}\tag{6.4.5} \end{equation}

and \(A + \Delta\!A \) is singular. We will show this leads to a contradition.

Since \(A + \Delta\!A \) is singular, there exists \(x \neq 0 \) such that \(( A + \Delta\!A ) x = 0 \text{.}\) We can rewrite this as

\begin{equation*} x = - A^{-1} \Delta\!A x \end{equation*}

and hence

\begin{equation*} \| x \| = \| A^{-1} \Delta\!A x \| \leq \| A^{-1} \| \| \Delta\!A \| \| x \|. \end{equation*}

Dividing both sides by \(\| x \| \) yields

\begin{equation*} 1 \leq \| A^{-1} \| \| \Delta\!A \| \end{equation*}

and hence \(\frac{1}{\| A^{-1} \|} \leq \| \Delta\! A \|\) and finally

\begin{equation*} \frac{1}{\| A \| \| A^{-1} \|} \leq \frac{\| \Delta\! A \|}{\| A \|}, \end{equation*}

which contradicts (6.4.5) since \(\| A \| \| A^{-1} \| = \kappa(A) \text{.}\)