Square linear systems

We initially consider the linear system

$$\mathbf{A}\mathbf{x}=\mathbf{b},$$ (1.25)

where $\mathbf{A}\in\mathbb{R}^{n\times n}$ is nonsingular and $\mathbf {x}$ represents the exact solution of the problem.

Suppose that the right-hand-side vector is affected by a perturbation $\delta\mathbf{b}$, and denote the solution of the perturbed system by $\tilde{\mathbf{x}}$. We therefore have

$$\mathbf{A}\tilde{\mathbf{x}} = \tilde{\mathbf{b}} = \mathbf{b}+\delta\mathbf{b}.$$ (1.26)

Since the unperturbed system satisfies $\mathbf{A}\mathbf{x}=\mathbf{b}$, subtracting the two equations gives

$$\mathbf{A}(\tilde{\mathbf{x}}-\mathbf{x}) = \delta\mathbf{b}.$$ (1.27)

Defining the perturbation of the solution as

$$\delta\mathbf{x} = \tilde{\mathbf{x}}-\mathbf{x},$$ (1.28)

we therefore obtain

$$\mathbf{A}\delta\mathbf{x} = \delta\mathbf{b}.$$ (1.29)

When $\mathbf{A}$ is square and invertible, we can finally write

$$\delta\mathbf{x} = \mathbf{A}^{-1}\delta\mathbf{b}.$$ (1.30)

The norm of the error in the solution can therefore be bounded by

$$\Vert\delta\mathbf{x}\Vert \leq \Vert\mathbf{A}^{-1}\Vert\,\Vert\delta\mathbf{b}\Vert.$$ (1.31)

To compare the relative error in the solution with the error in the data, we also observe that

$$\vert\mathbf{b}\vert = \vert\mathbf{A}\mathbf{x}\vert \leq \vert\mathbf{A}\vert,\vert\mathbf{x}\vert.$$ (1.32)

Combining the two relations gives

$$\boxed{ \frac{\vert\delta\mathbf{x}\vert}{\vert\mathbf{x}\ve... ...ert \frac{\vert\delta\mathbf{b}\vert}{\vert\mathbf{b}\vert} }.$$ (1.33)

The product

$$\kappa(\mathbf{A}) = \vert\mathbf{A}\vert,\vert\mathbf{A}^{-1}\vert$$ (1.34)

is defined as the condition number of the matrix $\mathbf{A}$. It therefore provides an upper bound on the factor by which a relative perturbation in the data can be amplified in the solution.

The condition number depends on the norm used. In what follows, unless otherwise specified, the Euclidean norm $\vert\cdot\vert _2$ is used. In this case, if $\sigma_1$ and $\sigma_n$ are, respectively, the largest and smallest singular values of $\mathbf{A}$, then

$$\boxed{ \kappa_2(\mathbf{A}) = \frac{\sigma_1}{\sigma_n} }.$$ (1.35)

This relation immediately shows the role of the SVD: a small singular value identifies a direction in which the system is weakly constrained and in which a perturbation of the data can produce a relatively large change in the solution.

If $\mathbf{A}$ is singular, at least one singular value is zero and the condition number is set to

$$\kappa_2(\mathbf{A})=\infty.$$ (1.36)

The condition number has several important properties:

• $\kappa(\mathbf{A})=\kappa(\mathbf{A}^{-1})$;
• $\kappa(c\mathbf{A})=\kappa(\mathbf{A})$ for every $c\neq0$;
• $\kappa(\mathbf{A})\geq1$;
• in the 2-norm,

  
  

  $$\kappa_2(\mathbf{A}) = \frac{\sigma_1}{\sigma_n};$$
  
  

• if $\mathbf{A}$ is orthogonal, then

  
  

  $$\kappa_2(\mathbf{A})=1.$$
  
  

A value of $\kappa$ close to unity therefore indicates that the problem is not very sensitive to perturbations, whereas large values indicate greater sensitivity.