Back to the on-screen lesson ·
How far the solution of $Ax = b$ moves when the data does, why the determinant and the entry sizes say nothing about it, and why a small residual is not a small error.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to compute a matrix condition number in a chosen norm, derive the perturbation bound it appears in, say why scaling and the determinant do not affect it, and read it as the relative distance to the nearest singular matrix.
You have solved linear systems by elimination and by factorisation, and you have a condition number for a scalar problem. A linear system is a problem with a matrix for its data, and this lesson is the same construction carried over to it.
A matrix norm measures how much a matrix can stretch a vector; the infinity norm $\|A\|_\infty$ is the largest absolute row sum and the two-norm $\|A\|_2$ is the largest singular value. The condition number is $\kappa(A) = \|A\|\,\|A^{-1}\|$, in whichever norm is being used. The residual of a candidate solution $\tilde{x}$ is $r = b - A\tilde{x}$. A matrix is ill conditioned when $\kappa$ is large, and singular when it has no inverse.
Perturb the right-hand side of $Ax = b$. Subtracting the two systems gives $A\,\delta x = \delta b$, so $\|\delta x\| \le \|A^{-1}\|\,\|\delta b\|$; and $b = Ax$ gives $\|b\| \le \|A\|\,\|x\|$. Multiplying,
$$\frac{\|\delta x\|}{\|x\|} \;\le\; \|A\|\,\|A^{-1}\| \; \frac{\|\delta b\|}{\|b\|},$$
and the factor in front is the condition number $\kappa(A)$. Three of its properties do most of the work. It is never below $1$, because $\|A\|\,\|A^{-1}\| \ge \|I\| = 1$. It is unchanged by scaling, because the two norms move oppositely — so the size of the entries, and the determinant, say nothing about it. And in the two-norm it equals $\sigma_1/\sigma_n$, the ratio of the largest singular value to the smallest, which makes $1/\kappa_2(A)$ exactly the relative distance from $A$ to the nearest singular matrix. The practical consequence is the one that catches people: the residual $r = b - A\tilde{x}$ can be at the level of rounding while the error in $\tilde{x}$ is enormous, because the residual is a backward error and $\kappa$ is what converts it into a forward one.
Another way: steps
Another way: picture
The unit circle is carried by $A$ to an ellipse. The long axis is $\sigma_1$ and the short one $\sigma_n$, and $\kappa_2$ is how much longer the first is than the second — how squashed the ellipse is, not how big. A rotation gives a circle and $\kappa_2 = 1$; a matrix on the edge of singularity gives an ellipse that has nearly collapsed to a line segment, and the direction it has collapsed in is the direction a small change in $b$ moves the solution enormously.
A small determinant is read as ill conditioning, and a small residual is read as an accurate solution. Neither follows. $\mathrm{diag}(10^{-6}, 10^{-6})$ has a determinant of $10^{-12}$ and a condition number of $1$; the Hilbert matrix has entries no larger than one and a condition number past $10^{13}$. And a backward stable solver always returns a small residual — that is what backward stability means — so a small residual is evidence about the solver and no evidence at all about the answer.
$A = \begin{pmatrix} 1 & 1 \\ 1 & 1.0001 \end{pmatrix}$: $\|A\|_\infty = 2.0001$.
The larger row sum.
$A^{-1} = 10^{4}\begin{pmatrix} 1.0001 & -1 \\ -1 & 1 \end{pmatrix}$, so $\|A^{-1}\|_\infty \approx 2 \times 10^{4}$.
Nearly singular.
$\kappa_\infty \approx 4 \times 10^{4}$: expect to lose four or five digits, whatever method is used.
The problem's verdict.
For that $A$, $\tilde{x} = (2, -1)$ against the true $(1, 0)$ when $b = (1, 1)$: an error of order one.
The answer is wrong.
Its residual is $b - A\tilde{x} = (0, 0.0001)$ — small.
The equation is nearly satisfied.
Small residual, large error, and $\kappa$ is the whole of the explanation.
Backward small, forward large.
$\|A\|_\infty = 8$, the larger entry.
$A^{-1} = \mathrm{diag}(1/8, 1/2)$, so $\|A^{-1}\|_\infty = 1/2$.
$\kappa_\infty = 8 \times \tfrac12 = 4$: mild, and unchanged if both entries are multiplied by a thousand.
What is $\kappa_\infty(A)$ for $A = \begin{pmatrix} 32 & 0 \\ 0 & 3 \end{pmatrix}$? Give a fraction if it is not a whole number.
Answer:
Give $\kappa_\infty$ of each diagonal matrix, as a fraction where it is not a whole number.
| Diagonal entries | Condition number | |
|---|---|---|
| The matrix itself | 26, 2 | |
| Every entry doubled | 52, 4 | |
| Both entries the larger one | 26, 26 |
Match each matrix to its condition number in the two-norm.
| One: no stretching in any direction | A million: one direction is squashed | Infinite: the matrix is singular | One: enormous entries, but every direction treated alike | |
|---|---|---|---|---|
| A rotation of the plane | ||||
| $\mathrm{diag}(1, 10^{-6})$ | ||||
| A matrix whose second row is twice its first | ||||
| $\mathrm{diag}(10^{6}, 10^{6})$ |
Put the five steps that derive $\dfrac{\|\delta x\|}{\|x\|} \le \kappa(A)\dfrac{\|\delta b\|}{\|b\|}$ into order.
Number the steps in order (write the number in the box):
An invertible matrix has $\kappa_2(A) = 26$. What is the smallest relative perturbation $\|\Delta\|_2/\|A\|_2$ that can make $A + \Delta$ singular? Give a fraction.
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Select every statement that is true of $\kappa(A) = \|A\|\,\|A^{-1}\|$ for an invertible $A$.
This task has no paper form; do it on a device.
You can compute and interpret a matrix condition number and state the perturbation bound. Say in your own words why a backward stable solver always returns a small residual and sometimes returns a bad answer.
8. Your turn: the infinity-norm condition number of $\mathrm{diag}(8, 2)$, step 3