Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 37 ยท Linear Systems

Matrix Norms and Condition Numbers

Understand vector and matrix norms, the condition number of a matrix, the Hilbert matrix example, and how the residual differs from the true error when solving Ax = b.

When you solve A x = b on a computer, the data in A and b are never exact, and the arithmetic adds rounding errors. How wrong can x be? The answer depends on one number attached to the matrix: its condition number. A system with a huge condition number is "nearly singular" and loses digits no matter how good the algorithm is.

To state this precisely we first need a way to measure the size of vectors and matrices. That tool is the norm.

Vector norms

A norm โ€–vโ€– assigns a size to a vector. The three common ones:

Norm Formula Name
โ€–vโ€–โ‚ `sum of v_i
โ€–vโ€–โ‚‚ sqrt(sum of v_iยฒ) 2-norm (Euclidean length)
โ€–vโ€–โˆž `max v_i

Matrix norms

A matrix norm measures how much a matrix can stretch a vector. The induced norm is

โ€–Aโ€– = max over x โ‰  0 of โ€–A xโ€– / โ€–xโ€–

Special cases that are easy to compute:

  • โ€–Aโ€–โ‚ is the maximum absolute column sum.
  • โ€–Aโ€–โˆž is the maximum absolute row sum.
  • โ€–Aโ€–โ‚‚ is the largest singular value of A.
  • The Frobenius norm โ€–Aโ€–_F is the square root of the sum of all squared entries (it is not induced, but is convenient).
Python Compute norms by hand and with NumPy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A useful property: โ€–A xโ€– โ‰ค โ€–Aโ€– โ€–xโ€– for any vector, and โ€–A Bโ€– โ‰ค โ€–Aโ€– โ€–Bโ€– for products.

The condition number of a matrix

The condition number of an invertible matrix is

ฮบ(A) = โ€–Aโ€– โ€–Aโปยนโ€–

It is at least 1 (equal to 1 for orthogonal matrices) and is infinite for a singular matrix. In the 2-norm it equals the ratio of the largest to the smallest singular value, ฯƒ_max / ฯƒ_min.

It controls how input perturbations affect the solution. If you solve A x = b but b is perturbed by ฮดb, then

โ€–ฮดxโ€– / โ€–xโ€– โ‰ค ฮบ(A) ร— โ€–ฮดbโ€– / โ€–bโ€–

A relative error 1e-16 in b (just rounding) may therefore become a relative error about ฮบ(A) ร— 1e-16 in x. As with function conditioning, you lose about log10 ฮบ(A) digits.

Python Perturbing b in well- and ill-conditioned systems

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same relative disturbance of 1e-10 in b barely affects the well-conditioned system but is magnified by about seven orders of magnitude in the Hilbert-matrix solution, exactly as ฮบ predicted.

The Hilbert matrix

The Hilbert matrix H_ij = 1/(i + j - 1) is the classic ill-conditioned example. It arises naturally when you fit polynomials to data using the monomials 1, x, xยฒ, ... on [0, 1]. Its condition number grows exponentially with size.

Python Condition number of Hilbert matrices

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

By n = 12 the condition number exceeds 1e16, which is beyond what double precision can handle: the computed solution contains no correct digits at all, although the algorithm (LU with partial pivoting) is backward stable. This is a property of the problem. The remedy is to reformulate: use orthogonal polynomials (such as Chebyshev) instead of monomials, as you will see in the interpolation and fitting chapter.

Residual versus error

In practice you check a solution by its residual r = b - A xฬ‚. A small residual does not guarantee a small error:

โ€–x - xฬ‚โ€– / โ€–xโ€– โ‰ค ฮบ(A) ร— โ€–rโ€– / โ€–bโ€–

A backward stable solver always produces a tiny residual (about 1e-16 relative), even for ill-conditioned problems. So with a large ฮบ, you can have an excellent residual and a bad answer at the same time.

Python Small residual, wrong answer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The residual is near machine precision, yet the error is huge. Residuals measure consistency, not accuracy.

flowchart TD
    A["Solve A x = b"] --> B["Compute residual"]
    B --> C{"Residual small?"}
    C -->|"no"| D["Bug or unstable method"]
    C -->|"yes"| E["Estimate cond(A)"]
    E --> F{"cond(A) large?"}
    F -->|"yes"| G["x may be inaccurate:<br/>lose about log10(cond) digits"]
    F -->|"no"| H["Trust x"]

A checklist for trusting a linear solve: residual first, then condition number.

Practical advice

  • Compute np.linalg.cond(A) (2-norm) or the cheaper estimate np.linalg.cond(A, 1) when you suspect trouble. SciPy's scipy.linalg.solve can warn about ill-conditioning.
  • A tiny determinant does not mean ill-conditioning (scaling a matrix by 1e-10 changes the determinant hugely but not ฮบ). Use ฮบ, not det.
  • Scale rows and columns so entries are of similar size before solving ("equilibration").
  • When the problem is ill-conditioned, change the formulation, add regularization or use higher precision rather than hoping for a better algorithm.

The condition number also governs iterative methods: the more ill-conditioned the matrix, the slower they converge. The next lesson shows how.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the induced infinity norm of a matrix?

    ||A||_inf is the largest sum of absolute values along any row; the 1-norm uses columns.
  2. 2. What does a condition number of 1e8 mean for a solve in double precision?

    The relative error is amplified by up to kappa, about 1e8 times 1e-16 = 1e-8.
  3. 3. A solver returns x with a tiny residual b - A x. What can you conclude if cond(A) = 1e15?

    Error can be as large as kappa times the relative residual.
  4. 4. Is the determinant a good measure of ill-conditioning?

    det(c A) = c^n det(A), while kappa(c A) = kappa(A).
  5. 5. Which matrix is the classic example of severe ill-conditioning?

    The Hilbert matrix's condition number grows exponentially with its size.

Summary

  • Norms measure the size of vectors and matrices; โ€–Aโ€–โ‚ is the max column sum, โ€–Aโ€–โˆž the max row sum, โ€–Aโ€–โ‚‚ the largest singular value.
  • ฮบ(A) = โ€–Aโ€– โ€–Aโปยนโ€– bounds the amplification of relative errors in solving A x = b; expect to lose about log10 ฮบ digits.
  • The Hilbert matrix shows how fast ฮบ can grow.
  • A small residual does not imply a small error when ฮบ is large.
  • Use cond, not det, to diagnose trouble and reformulate rather than hoping for a better algorithm.

Next: Jacobi and Gauss-Seidel Methods