ALAFF Conditioning of a linear system

Subsection 1.4.1 Conditioning of a linear system

fit width

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$ ).