Condition Number

Introduction

We analyse the solution to the linear system

\[ A \boldsymbol{x} = \boldsymbol{b}, \label{linear-system}\]

when the operator $\boldsymbol{A}$ and the data $\boldsymbol{b}$ are perturbed.

These errors creep in due to computer floating point round-off and inaccurate measurement of $\boldsymbol{b}$.

We see that, for certain $A$-matrices, even small perturbations of $\boldsymbol{b}$ may lead to large variations in the solution. This is a problem inherent to the matrix $A$, and cannot be addressed by using a different solution method.

We also define the condition number of $A$, which quantifies this sensitivity of the system output to input variations.

Output sensitivity to variations in $A$

Instead of solving $\ref{linear-system}$, we now look at

\[ (A + \Delta A) \boldsymbol{\hat{x}} = \boldsymbol{b} \label{perturbed-A} \]

where $\boldsymbol{\hat{x}} = \boldsymbol{x + \Delta x}$ is the perturbed result.

We expand $\ref{perturbed-A}$ to

\[ A \boldsymbol{x} + \Delta A \boldsymbol{x} + A \boldsymbol{\Delta x} + \Delta A \boldsymbol{\Delta x} = \boldsymbol{b} \]

and since $A \boldsymbol{x} = \boldsymbol{b}$

\[ \begin{eqnarray} \Delta A \boldsymbol{x} + A \boldsymbol{\Delta x} + \Delta A \Delta \boldsymbol{x} &=& 0 \\ \Longrightarrow A \boldsymbol{\Delta x} &=& -\Delta A ( \boldsymbol{x} + \boldsymbol{\Delta x}) \\ \boldsymbol{\Delta x} &=& - A^{-1} \Delta A ( \boldsymbol{x} + \boldsymbol{\Delta x}) \\ \Vert\boldsymbol{\Delta x}\Vert &=& \Vert A^{-1} \Delta A ( \boldsymbol{x} + \boldsymbol{\Delta x}) \Vert . \end{eqnarray} \]

Norms have the property that $\Vert x y \Vert \leq \Vert x \Vert \cdot \Vert y \Vert$, therefore \[ \begin{eqnarray} \Vert\boldsymbol{\Delta x}\Vert &\leq& \Vert A^{-1} \Vert \cdot \Vert \Delta A \Vert \cdot \Vert \boldsymbol{x} + \boldsymbol{\Delta x} \Vert \\ \frac{ \Vert\boldsymbol{\Delta x}\Vert } { \Vert \boldsymbol{x} + \boldsymbol{\Delta x} \Vert } &\leq& \Vert A^{-1} \Vert \cdot \Vert \Delta A \Vert \\ &=& \Vert A^{-1} \Vert \Vert A \Vert \frac{ \Vert \Delta A \Vert } { \Vert A \Vert } = \kappa(A) \frac{ \Vert \Delta A \Vert } { \Vert A \Vert } \label{A-perturbed} \end{eqnarray} \]

The quantity $\kappa(A)$ is known as the condition number of A.

Output sensitivity to variations in $\boldsymbol{b}$

A similar process is followed to analyse the system sensitivity to perturbations in $\boldsymbol{b}$:

\[ A \boldsymbol{\hat{x}} = \boldsymbol{b} + \boldsymbol{\Delta b} \]

with $\boldsymbol{\hat{x}} = \boldsymbol{x} + \boldsymbol{\Delta x}$. In other words, a perturbation in $\boldsymbol{b}$ leads to a perturbation $\boldsymbol{\Delta x}$ in the solution.

Since $A \boldsymbol{x} = \boldsymbol{b}$, \[ \begin{eqnarray} A ( \boldsymbol{\boldsymbol{x}} + \boldsymbol{\Delta x} ) &=& \boldsymbol{b} + \boldsymbol{\Delta b} \\ A \boldsymbol{\Delta x} &=& \boldsymbol{\Delta b} \\ \boldsymbol{\Delta x} &=& A^{-1} \boldsymbol{\Delta b} \\ \Vert \boldsymbol{\Delta x} \Vert &\leq& \Vert A^{-1} \Vert \cdot \Vert \boldsymbol{\Delta b} \Vert \label{abs-error} \\ \end{eqnarray} \]

We now exploit the relation \[ A \boldsymbol{x} = \boldsymbol{b} \Longrightarrow \Vert A \Vert \cdot \Vert \boldsymbol{x} \Vert \geq \Vert \boldsymbol{b} \Vert \Longrightarrow \Vert \boldsymbol{x} \Vert \geq \frac{ \Vert \boldsymbol{b} \Vert } { \Vert A \Vert } \]

to write $\ref{abs-error}$ in terms of relative errors \[ \begin{eqnarray} \frac{ \Vert \boldsymbol{\Delta x} \Vert }{ \Vert \boldsymbol{x} \Vert} &\leq& \Vert A^{-1} \Vert \Vert A \Vert \frac {\Vert \boldsymbol{\Delta b} \Vert }{\Vert \boldsymbol{b} \Vert} \\ &=& \kappa(A) \frac {\Vert \boldsymbol{\Delta b} \Vert }{\Vert \boldsymbol{b} \Vert}. \label{b-perturbed} \end{eqnarray} \]

From $\ref{A-perturbed}$ and $\ref{b-perturbed}$ we see that, whenever $A$ is significantly perturbed or the condition number is large, the solution may differ significantly from the $\boldsymbol{x}$ required.

Example

For a given system,

\[ A \boldsymbol{x} = \boldsymbol{b} \]

we have $\kappa(A) = 10^l$. The vector $\boldsymbol{b}$ is represented as an IEEE floating point number, so that

\[ \frac{ \Vert \boldsymbol{\Delta b} \Vert }{\Vert \boldsymbol{b} \Vert} \approx 10^{-16}. \]

According to $\ref{b-perturbed}$, we have

\[ \frac{ \Vert \boldsymbol{\Delta x} \Vert }{\Vert \boldsymbol{x} \Vert} \leq 10^{l - 16} \]

In other words, we may lose $l$ decimals of precision due to the conditioning of $A$.

Perturbations in both $A$ and $\boldsymbol{b}$

The expression for the error when both $A$ and $\boldsymbol{b}$ are perturbed, as taken from

[Hig87] Higham, Nicolas J. A survey of condition number estimation for triangular matrices. MIMS EPrint: 2007.10, 1987.

is \[ \frac{\Vert \boldsymbol{ \Delta x } \Vert}{\Vert \boldsymbol{x} \Vert} \leq \frac{\kappa(A)}{1 - \kappa(A) \Vert \Delta A \Vert / \Vert A \Vert} \left[ \frac{\Vert \boldsymbol{\Delta b} \Vert}{\Vert \boldsymbol{b} \Vert} + \frac{\Vert \boldsymbol{\Delta A} \Vert}{\Vert \boldsymbol{A} \Vert} \right] \]

provided that $\kappa(A) \Vert \Delta A \Vert / \Vert A \Vert < 1$.

References

[Hig87] Higham, Nicolas J. A survey of condition number estimation for triangular matrices. MIMS EPrint: 2007.10, 1987.

[JIJ85] Jain, M. K., S.R.K. Iyengar and R.K. Jain. Numerical methods for scientific and engineering application. John Wiley &amp; Sons, 1985.

[Str93] Strang, Gilbert. Introduction to Linear Algebra. Wellesly-Cambridge Press, 1993.

[Wat91] Watkins, David. S. Fundamentals of matrix computations. John Wiley &amp; Sons, 1991.


IanKnot rainbow -->