Skip to main content

Subsection 1.4.1 Conditioning of a linear system

A question we will run into later in the course asks how accurate we can expect the solution of a linear system to be if the right-hand side of the system has error in it.

Formally, this can be stated as follows: We wish to solve \(A x = b \text{,}\) where \(A \in \C^{m \times m} \) but the right-hand side has been perturbed by a small vector so that it becomes \(b + \delta\!b\text{.}\)

Remark 1.4.1.1.

Notice how the \(\delta \) touches the \(b \text{.}\) This is meant to convey that this is a symbol that represents a vector rather than the vector \(b \) that is multiplied by a scalar \(\delta \text{.}\)

The question now is how a relative error in \(b \) is amplified into a relative error in the solution \(x \text{.}\)

This is summarized as follows:

\begin{equation*} \begin{array}{r c l l} A x \amp = \amp b \amp \mbox{ exact equation } \\ A ( x + \delta\!x ) \amp = \amp b + \delta\!b ~~~~~~~ \amp \mbox{ perturbed equation } \\ \end{array} \end{equation*}

We would like to determine a formula, \(\kappa( A, b, \delta\!b ) \text{,}\) that gives us a bound on how much a relative error in \(b \) is potentially amplified into a relative error in the solution \(x \text{:}\)

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

We assume that \(A \) has an inverse since otherwise there may be no solution or there may be an infinite number of solutions. To find an expression for \(\kappa( A, b, \delta\!b ) \text{,}\) we notice that

\begin{equation*} \begin{array}{r c l} A x + A \delta\!x \amp = \amp b + \delta\!b \\ A x \phantom{+ A \delta\!x } \amp = \amp b \hspace{0.25in} -\\ \hline A \delta\!x \amp = \amp \phantom{b} \phantom{+} \delta\!b \end{array} \end{equation*}

and from this we deduce that

\begin{equation*} \begin{array}{r c l} A x \amp = \amp b \\ \delta\!x \amp = \amp A^{-1} \delta\!b. \end{array} \end{equation*}

If we now use a vector norm \(\| \cdot \| \) and its induced matrix norm \(\| \cdot \| \text{,}\) then

\begin{equation*} \begin{array}{r c l} \| b \| \amp = \amp \| A x \| \leq \| A \| \| x \| \\ \| \delta\!x \| \amp = \amp \| A^{-1} \delta\!b \| \leq \| A^{-1} \| \| \delta\!b \| \end{array} \end{equation*}

since induced matrix norms are subordinate.

From this we conclude that

\begin{equation*} \frac{1}{\| x \|} \leq \| A \| \frac{1}{\| b \|} \end{equation*}

and

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

so that

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

Thus, the desired expression \(\kappa( A, b, \delta\!b ) \) doesn't depend on anything but the matrix \(A \text{:}\)

\begin{equation*} \frac{\| \delta\!x \|}{\| x \|} \leq \begin{array}[t]{c} \underbrace{ \| A \| \| A^{-1} \| } \\ \kappa( A ) \end{array} \frac{\| \delta\!b \|}{\| b \|}. \end{equation*}
Definition 1.4.1.2. Condition number of a nonsingular matrix.

The value \(\kappa( A ) = \| A \| \| A^{-1} \| \) is called the condition number of a nonsingular matrix \(A \text{.}\)

A question becomes whether this is a pessimistic result or whether there are examples of \(b \) and \(\delta\!b \) for which the relative error in \(b \) is amplified by exactly \(\kappa( A ) \text{.}\) The answer is that, unfortunately, the bound is tight.

  • There is an \({\widehat x} \) for which

    \begin{equation*} \| A \| = \max_{\| x \| = 1} \| A x \| = \| A {\widehat x} \|, \end{equation*}

    namely the \(x \) for which the maximum is attained. This is the direction of maximal magnification. Pick \(\widehat b = A {\widehat x} \text{.}\)

  • There is an \(\widehat {\delta\!b} \) for which

    \begin{equation*} \| A^{-1} \| = \max_{\| x \| \neq 0} \frac{\| A^{-1} x \|}{\| x \|} = \frac{\| A^{-1} \widehat{\delta\!b} \|}{\| \widehat{\delta\!b} \|}, \end{equation*}

    again, the \(x \) for which the maximum is attained.

It is when solving the perturbed system

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

that the maximal magnification by \(\kappa( A ) \) is observed.

Homework 1.4.1.1.

Let \(\| \cdot \| \) be a vector norm and corresponding induced matrix norm.

TRUE/FALSE: \(\| I \| = 1 \text{.}\)

Answer

TRUE

Solution
\begin{equation*} \| I \| = \max_{\| x \| = 1} \| I x \| = \max_{\| x \|=1} \| x \| = 1 \end{equation*}
Homework 1.4.1.2.

Let \(\| \cdot \| \) be a vector norm and corresponding induced matrix norm, and \(A \) a nonsingular matrix.

TRUE/FALSE: \(\kappa( A ) = \| A \| \| A^{-1} \| \geq 1 \text{.}\)

Answer

TRUE

Solution
\begin{equation*} \begin{array}{l} 1 \\ ~~~=~~~~ \lt \mbox{ last homework } \gt \\ \| I \| \\ ~~~=~~~~ \lt A \mbox{ is invertible } \gt \\ \| A A^{-1} \| \\ ~~~\leq ~~~~ \lt \| \cdot \| \mbox{ is submultiplicative } \gt \\ \| A \| \| A^{-1} \|. \end{array} \end{equation*}
Remark 1.4.1.3.

This last exercise shows that there will always be choices for \(b \) and \(\delta\!b \) for which the relative error is at best directly translated into an equal relative error in the solution (if \(\kappa( A ) = 1 \)).

login