Skip to content
Tutorials Center
My learning

Topics

Lesson 49 of 62 ยท Eigenvalues and Decompositions

Numerical Linear Algebra Pitfalls

Learn why floating-point linear algebra goes wrong: rounding, ill-conditioned systems, the Hilbert matrix, unstable algorithms, and sparse matrices in SciPy.

On paper, linear algebra is exact. On a computer, every number is stored with about 16 significant digits, and every operation rounds. Most of the time this does not matter. But sometimes a perfectly valid formula returns garbage, a matrix that should be invertible is reported singular, or an answer with a tiny residual is still far from the truth.

This lesson gives you the vocabulary and the instincts for those moments. You will see what floating point does, what a condition number measures, how the Hilbert matrix makes systems nearly impossible to solve, why some algorithms are unstable even for good problems, and how sparse matrices save memory and time when most entries are zero. It builds on the SVD and on Solving Systems with NumPy.

Two different sources of trouble

Bad problem Ill-conditioned: tiny input changes, huge output changes.
Bad algorithm Unstable: it amplifies rounding even for good problems.

A good algorithm cannot rescue a bad problem, but a bad algorithm can ruin a good one.

1 / 2

Floating-point basics

NumPy uses 64-bit floating-point numbers by default (float64). They have a relative precision of about 2.2e-16, called machine epsilon: np.finfo(float).eps. Two consequences matter everywhere:

  • Rounding. Most decimal fractions, such as 0.1, have no exact binary form, so results like 0.1 + 0.2 are not exactly 0.3. Compare floats with a tolerance (np.isclose, np.allclose), never with ==.
  • Cancellation. Subtracting two nearly equal numbers wipes out the leading digits they share, leaving mostly rounding noise. The relative error of the result can be enormous even though each input was accurate.

For matrices, this means an entry that "should be zero" may show up as 1e-17, and a matrix that "should be singular" may have a determinant like 1e-16 instead of 0. Use rank and conditioning tools with tolerances, not exact tests.

Python Rounding, cancellation and exact zeros

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 correct ratio in the cancellation loop is 1, and you can see how fast the computed value drifts away. The nine entries in A were chosen so that row 3 minus row 2 equals row 2 minus row 1 (a true rank of 2), yet the determinant printed is a tiny nonzero number. The singular values show the truth clearly: one of them is at rounding level, and matrix_rank counts it as zero by using a tolerance.

Condition numbers

Most of the damage comes from the problem itself, not the algorithm. The condition number of a matrix, cond(A) = s_max / s_min (the ratio of the largest to the smallest singular value, see the SVD lesson), measures how sensitive the solution of A x = b is to small changes in b or A. As a rule of thumb, the relative error in x can be up to cond(A) times the relative error in the data.

A double-precision computer starts with a relative error around 1e-16 from rounding alone. So if cond(A) is 1e10, expect to lose about 10 of your 16 digits, leaving about 6 correct ones. When cond(A) approaches 1e16, none are left, and the matrix is singular for all practical purposes.

Be careful with two common misunderstandings:

  • The determinant is not a measure of conditioning. Multiply a 10 x 10 identity by 0.001 and the determinant is 1e-30, yet the matrix is perfectly conditioned (cond = 1).
  • A small residual ||A x - b|| does not prove x is accurate. For an ill-conditioned matrix, a badly wrong x can still satisfy the equation almost exactly.

The Hilbert matrix

The Hilbert matrix has entries H[i, j] = 1 / (i + j + 1). It is symmetric, positive definite and perfectly invertible in theory, and it is the classic example of an ill-conditioned matrix: its columns are nearly parallel, so every new row adds very little independent information. The condition number grows roughly exponentially with n.

Here is an experiment. Choose a known answer x = [1, 1, ..., 1], compute b = H x, then ask NumPy to solve for x again and compare.

Python Solving Hilbert systems of growing size

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.

Read the table from top to bottom. The residual stays near rounding level for every n, so by that measure every solve "worked". But the error in x climbs steadily with the condition number: for n = 12 it is about 0.6, which is no longer a rounding error: the solution is visibly off even though the residual looks perfect (here cond(H) is already past 1/eps). This is the difference between a small residual and a small error, and it is why you should look at np.linalg.cond (or at least matrix_rank and the singular values) whenever a solution matters. NumPy will warn you for exactly singular matrices, but it does not warn you here.

An ill-conditioned problem cannot be fixed by a cleverer algorithm. The data does not contain enough information to recover the answer to full precision. The remedies are to change the problem: collect better-spread data, rescale columns, or add regularization (such as ridge regression, which you will meet in the linear regression project).

Stable and unstable algorithms

An algorithm is numerically stable if it gives close to the exact answer for a nearby problem, so rounding errors do not snowball. The same mathematical formula can be implemented stably or unstably.

A famous example is least squares. The normal equations A^T A x = A^T b are correct on paper (Least Squares), but forming A^T A squares the condition number: cond(A^T A) = cond(A)^2. A matrix with cond = 1e8 becomes 1e16, and double precision cannot see the information any more. Algorithms based on QR or the SVD work on A directly and keep cond(A). That is why np.linalg.lstsq uses the SVD.

Python Normal equations versus an orthogonal method

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 data here are exact, so the true coefficients are 1, 2, ..., 10, and any loss of accuracy comes only from the algorithm. The normal equations lose far more digits than QR or the SVD, which stay close to the best the problem allows. (The exact digits you see depend on the platform's math library, but the gap between the methods does not.)

Some other habits that follow from the same principle:

  • Prefer np.linalg.solve(A, b) to np.linalg.inv(A) @ b: it is faster, and it is usually at least as accurate.
  • Prefer np.linalg.slogdet to np.linalg.det when the determinant might overflow or underflow, as discussed in Determinants.
  • Prefer modified Gram-Schmidt or Householder QR (np.linalg.qr) to classical Gram-Schmidt, as in Gram-Schmidt and QR.
  • Use eigh for symmetric matrices instead of eig, to guarantee real values and orthogonal vectors.
  • Rescale columns that have wildly different units before solving or fitting.

Sparse matrices

Many matrices from real problems are mostly zeros: a graph's adjacency matrix, a finite-difference grid, a table of word counts. Storing all the zeros wastes memory (a 10,000 x 10,000 float matrix is 800 MB) and multiplying by them wastes time.

scipy.sparse stores only the nonzero entries. The three formats you will use most are:

  • CSR (compressed sparse row): fast row slicing and matrix-vector products. The usual choice for computation.
  • CSC (compressed sparse column): fast column slicing, preferred by many direct solvers.
  • COO (coordinate): a simple list of (row, column, value) triples, handy for building a matrix and then converting.

Sparse matrices support @ for products and scipy.sparse.linalg has solvers (spsolve) and partial eigenvalue and SVD routines (eigsh, svds) that never form the dense matrix.

Python A tridiagonal system, dense versus sparse

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 sparse matrix stores about three numbers per row instead of 2,000 (5,998 nonzeros in all), which is hundreds of times less memory (about 400 times here). Note that conditioning still applies: this second-difference matrix has a condition number that grows with n, so sparse does not mean safe. Sparse formats also differ from dense arrays in one important way: do not convert them back with .toarray() for large matrices, because that allocates the whole dense array.

Sparse is only worth it when the matrix is really sparse, roughly 1 percent nonzero or less. For a matrix that is half full, the index overhead makes sparse storage bigger and slower than a plain array.

A short checklist

When a linear algebra result looks odd, run through these questions:

  1. Did you compare floats with ==? Use np.allclose.
  2. What is np.linalg.cond(A)? Is it close to 1 / eps (about 4.5e15)?
  3. Are you using inv, a determinant test or A^T A where solve, rank or QR would be safer?
  4. Is the input symmetric (use eigh) or sparse (use scipy.sparse)?
  5. Could the data be rescaled so that columns have similar size?

You now have the tools to compute reliably. Put them to work in the first project, Principal Component Analysis.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a condition number of 1e12 for a matrix A suggest when solving A x = b in double precision?

    Relative errors in x can be as large as cond(A) times the relative error in the data, and rounding alone starts around 1e-16.
  2. 2. After solving an ill-conditioned system you find ||A x - b|| is tiny. What can you conclude?

    The residual measures how well x satisfies the equation, not how close x is to the true solution. The gap is controlled by cond(A).
  3. 3. Why are the normal equations a risky way to solve least squares?

    cond(A^T A) = cond(A)^2, so digits are lost twice as fast. QR and SVD methods avoid forming A^T A.
  4. 4. A matrix has 5 nonzero entries out of 25 million. What is the best way to store it?

    Sparse formats store only the nonzero entries and their positions, which saves both memory and computation.
  5. 5. Which statement about the determinant and conditioning is correct?

    0.001 times the identity has a tiny determinant but condition number 1. Use the singular value ratio instead.

Summary

  • Floating-point numbers have about 16 significant digits (np.finfo(float).eps is about 2.2e-16); compare with tolerances and expect cancellation to destroy digits.
  • cond(A) = s_max / s_min tells you how much data errors can be amplified; roughly log10(cond) digits are lost.
  • A small residual does not mean a small error, and the determinant is not a conditioning measure.
  • The Hilbert matrix shows an ill-conditioned problem: the solve "succeeds" while the answer becomes meaningless.
  • Stable methods (solve, QR, SVD) beat unstable ones (inv, normal equations, classical Gram-Schmidt) on the same problem.
  • Use scipy.sparse (CSR, CSC, COO) and scipy.sparse.linalg when most entries are zero.

Next, apply the decompositions to real data in Project: Principal Component Analysis.