| [ Front | phdwiki | Index ] | Updated May 28, 2009 |
|
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.
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.
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.
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$.
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$.
[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 & Sons, 1985.
[Str93] Strang, Gilbert. Introduction to Linear Algebra. Wellesly-Cambridge Press, 1993.
[Wat91] Watkins, David. S. Fundamentals of matrix computations. John Wiley & Sons, 1991.
rainbow
-->