The condition number of linear systems

The condition number of linear systems#

The condition number reflects how sensitive a function evaluation $f (x + Δ x)$ is to changes in $Δ x$ . It doesn’t depend on the numerical method $\tilde{f}$ and shows how hard it is to evaluate $f$ numerically, no matter which method is used.

With this in mind, we now compute the condition number for linear systems of equations $A y = b$ with $A \in R^{n \times n}$ and $b \in R^{n}$ . We assume that $A$ is non-singular and $b \neq 0$ . We use $‖ \cdot ‖$ to denote both the vector norm on $R^{n}$ and the induced matrix norm on $R^{n \times n}$ .

We consider the following two problems:

Given a fixed $A$ , what is the local relative condition number $κ_{1} (b)$ of $f_{1} : R^{n} \to R^{n}$ , defined by $b \mapsto A^{- 1} b$ ?
Given a fixed $b$ , what is the local relative condition number $κ_{2} (A)$ of $f_{2} : R^{n \times n} \to R^{n}$ , defined by $A \mapsto A^{- 1} b$ ?

Conveniently, both questions can be answered with the same calculation. Let $Δ A$ and $Δ b$ be perturbations in $A$ and $b$ , and let $Δ y$ satisfy

(A + Δ A) (y + Δ y) = b + Δ b .

Then

\begin{array}{r} \begin{aligned} Δ y & = (A + Δ A)^{- 1} (- Δ A y + Δ b) \\ = {[A (I + A^{- 1} Δ A)]}^{- 1} (- Δ A y + Δ b) \\ = {(I + A^{- 1} Δ A)}^{- 1} A^{- 1} (- Δ A y + Δ b) . \end{aligned} . \end{array}

To continue, we use the following lemma, whose proof is given in the optional materials. It is a direct generalisation of a well-known result for scalars (i.e. $n = 1$ and the norm is the modulus) to the matrix setting.

Lemma 1 (Matrix-valued von Neumann series)

Let $‖ \cdot ‖$ be a submultiplicative matrix norm, and let $X \in R^{n \times n}$ with $‖ X ‖ < 1$ . Then $I - X$ is invertible and

(I - X)^{- 1} = \sum_{i = 0}^{\infty} X^{i}

with

‖ (I - X)^{- 1} ‖ \leq \frac{1}{1 - ‖ X ‖} .

Assuming that $Δ A$ is sufficiently small so that $‖ A^{- 1} Δ A ‖ < 1$ , we conclude from the lemma that

\begin{array}{r} \begin{aligned} \frac{‖ Δ y ‖}{‖ y ‖} & \leq \frac{‖ A^{- 1} ‖}{1 - ‖ A^{- 1} ‖ \cdot ‖ Δ A ‖} (‖ Δ A ‖ + \frac{‖ Δ b ‖}{‖ y ‖}) \\ \leq \frac{‖ A^{- 1} ‖ \cdot ‖ A ‖}{1 - ‖ A^{- 1} ‖ \cdot ‖ Δ A ‖} (\frac{‖ Δ A ‖}{‖ A ‖} + \frac{‖ Δ b ‖}{‖ b ‖}), \end{aligned} \end{array}

where in the last step we used that $‖ b ‖ = ‖ A y ‖ \leq ‖ A ‖ \cdot ‖ y ‖$ . To answer the first question above, let $Δ A = 0$ . Then $A Δ y = Δ b$ , and thus

\begin{array}{r} \begin{aligned} κ_{1} (b) = & lim_{δ \to 0} sup_{\binom{b, b + Δ b \in R^{n}}{0 < ‖ Δ b ‖ \leq δ}} \frac{‖ f_{1} (b + Δ b) - f_{1} (b) ‖_{R^{n}} / ‖ f_{1} (b) ‖_{R^{n}}}{‖ Δ b ‖_{R^{n}} / ‖ b ‖_{R^{n}}} = lim_{δ \to 0} sup_{\binom{b, Δ b \in R^{n}}{0 < ‖ Δ b ‖ \leq δ}} \frac{‖ Δ y ‖_{R^{n}} / ‖ y ‖_{R^{n}}}{‖ Δ b ‖_{R^{n}} / ‖ b ‖_{R^{n}}} \\ \leq & lim_{δ \to 0} sup_{\binom{b, Δ b \in R^{n}}{0 < ‖ Δ b ‖ \leq δ}} \frac{‖ A^{- 1} ‖ \cdot ‖ A ‖}{1 - ‖ A^{- 1} ‖ \cdot ‖ Δ A ‖} \leq ‖ A^{- 1} ‖ \cdot ‖ A ‖ . \end{aligned} \end{array}

Similarly, to answer the second question, let $Δ b = 0$ . Then $(A + Δ A) Δ y = Δ A y$ , and so

\begin{array}{r} \begin{aligned} κ_{2} (A) = & lim_{δ \to 0} sup_{\binom{A, A + Δ A \in R^{n \times n}}{0 < ‖ Δ A ‖ \leq δ}} \frac{‖ f_{2} (A + Δ A) - f_{2} (A) ‖_{R^{n \times n}} / ‖ f_{2} (A) ‖_{R^{n \times n}}}{‖ Δ A ‖_{R^{n \times n}} / ‖ A ‖_{R^{n \times n}}} \\ = & lim_{δ \to 0} sup_{\binom{A, A + Δ A \in R^{n \times n}}{0 < ‖ Δ A ‖ \leq δ}} \frac{‖ Δ y ‖_{R^{n \times n}} / ‖ y ‖_{R^{n \times n}}}{‖ Δ A ‖_{R^{n \times n}} / ‖ A ‖_{R^{n \times n}}} \leq ‖ A^{- 1} ‖ \cdot ‖ A ‖ . \end{aligned} \end{array}

Therefore, both condition numbers $A \mapsto A^{- 1} b$ and $b \mapsto A^{- 1} b$ are bounded above by $‖ A^{- 1} ‖ \cdot ‖ A ‖$ . This bound is sharp, as recorded by the following fact.

Fact: Condition number of linear systems

Assume that $A \in R^{n \times n}$ is non-singular and $b \in R^{n}$ is non-zero. Then

κ_{1} (b) = κ_{2} (A) = ‖ A^{- 1} ‖ \cdot ‖ A ‖ .

The condition number $κ_{r e l} (A)$ has an important interpretation. It measures how close the linear system is to being singular. More precisely,

min {\frac{‖ Δ A ‖_{2}}{‖ A ‖_{2}} : A + Δ A singular} = \frac{1}{κ_{r e l} (A)} .

We do not prove this result here.

Python skills#

You can compute the condition number of a matrix using the numpy.linalg.cond function. Here are a few examples:

import numpy as np

# Example 1: 2x2 matrix
A = np.array([[1, 1], [0, 0.01]])
cond_number = np.linalg.cond(A)
print(f"Condition number of A: {cond_number}")

# Example 2: 3x3 matrix
B = np.array([[1, 2, 3], [0, 5, 6], [7, 0, 9]])
cond_number_B = np.linalg.cond(B)
print(f"Condition number of B: {cond_number_B}")

# Example 3: Using different norms
C = np.array([[2, 3], [-1, 1]])
cond_number_C_1 = np.linalg.cond(C, 1)  # 1-norm
cond_number_C_inf = np.linalg.cond(C, np.inf)  # Infinity norm
cond_number_C_2 = np.linalg.cond(C, 2)  # 2-norm
print(f"Condition number of C (1-norm): {cond_number_C_1}")
print(f"Condition number of C (Infinity norm): {cond_number_C_inf}")
print(f"Condition number of C (2-norm): {cond_number_C_2}")

Self-check questions#

Question

Compute the $1 -$ norm condition number of

\begin{array}{r} A = (\begin{array}{c} 1 & 1 \\ 0 & ϵ \end{array}) \end{array}

as a function of $ϵ$ . What happens as $ϵ \to 0$ ?

Question (Sharp condition number)

Let

\begin{array}{r} A = (\begin{array}{rr} 5 & - 18 \\ - 5 & 19 \end{array}) . \end{array}

Compute local relative condition number $κ_{1}$ and find vectors $b$ , $Δ b$ such that $A (x + Δ x) = b + Δ b$ and

\frac{‖ Δ x ‖_{1}^{}}{‖ x ‖_{1}^{}} = κ_{1} \frac{‖ Δ b ‖_{1}^{}}{‖ b ‖_{1}^{}} .

Here $‖ \cdot ‖_{1}^{}$ denotes the $1$ -norm. Normalise your vectors so that $‖ x ‖_{1}^{} = 1$ and $‖ Δ b ‖_{1}^{} = 0.01$ .

Question (Sharp condition number)

Repeat for

\begin{array}{r} A = (\begin{array}{rrr} - 4 & 8 & - 7 \\ - 5 & 3 & 2 \\ - 3 & 3 & - 9 \end{array}), A^{- 1} = (\begin{array}{rrr} \frac{11}{78} & - \frac{17}{78} & - \frac{37}{234} \\ \frac{17}{78} & - \frac{5}{78} & - \frac{43}{234} \\ \frac{1}{39} & \frac{2}{39} & - \frac{14}{117} \end{array}) . \end{array}

Question

Let

\begin{array}{r} A = (\begin{array}{c} 2 & 1 \\ 1 & 2 \end{array}) . \end{array}

Compute $κ_{1} (A)$ , $κ_{\infty} (A)$ , $κ_{2} (A)$ , which denote here the condition numbers with respect to the $1$ -, $\infty$ - and $2$ -norm. Which is largest?

Question

Consider

\begin{array}{r} A = (\begin{array}{c} 1 & \frac{1}{2} \\ \frac{1}{2} & 1 \end{array}) . \end{array}

Its eigenvalues are $λ_{max} = 1.5$ and $λ_{min} = 0.5$ . Suppose we add a small perturbation $Δ A$ and consider no perturbation in $b$ (i.e. $Δ b = 0$ ). Estimate, using the $2$ -norm condition number, how large the relative perturbation $\frac{‖ Δ A ‖_{2}}{‖ A ‖_{2}}$ can be before $A + Δ A$ becomes close to singular.

The condition number of linear systems

Contents

The condition number of linear systems#

Python skills#

Self-check questions#

Optional material#