## Unit1.4.1Conditioning 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{.}$

###### Remark1.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*}
###### Definition1.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.

###### Homework1.4.1.1.

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

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

TRUE

Solution
\begin{equation*} \| I \| = \max_{\| x \| = 1} \| I x \| = \max_{\| x \|=1} \| x \| = 1 \end{equation*}
###### Homework1.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{.}$

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