Solving Ax = b gives wildly different x for tiny changes in b - what is going on?
answer
- sensitivity, not a coding bug
- inspect the matrix, not the solver
- two equations nearly saying the same thing
- relative error in, amplified error out
- one number bounds the amplification
basics
~20 sThe matrix is ill-conditioned, not the solver buggy. Its condition number - how much a relative change in b is magnified in x - is large, so noise in the last digits swings the answer.
solid answer
~50 sThis is ill-conditioning, a property of `A` itself rather than of your code. The condition number `cond(A) = ||A|| * ||A^-1||` bounds the amplification: the relative change in `x` can be as large as `cond(A)` times the relative change in `b`. Take `A = [[1, 1], [1, 1.0001]]`. With `b = (2, 2.0001)` the solution is `x = (1, 1)`; nudge the second entry to `2.0002`, a change of five parts in a hundred thousand, and the solution jumps to `x = (0, 2)`. The condition number here is on the order of 10^4. The two equations describe nearly parallel lines, so their crossing point slides far under a tiny nudge. No solver fixes this; the information simply is not in the data. You rescale columns to comparable units, remove near-duplicate columns, add a regularising term, or report that the quantity is not identified.
go deeper
Recall the term ill-conditioned and what it means in plain words: small changes in the inputs cause large changes in the answer, and that is a fact about the matrix rather than a mistake in the code.
Explain the amplification bound - relative error in the solution is at most the condition number times relative error in the right-hand side - and be able to name a concrete matrix where two near-identical rows produce it.
Diagnose it live: measure the conditioning, trace it to duplicated or badly scaled columns, apply rescaling or regularisation, and translate the condition number into how many digits of the answer are actually trustworthy.
Own the call on what to do when the data does not identify the answer - invest in better measurements, accept a regularised and slightly biased estimate, or decline to report the quantity - and set the standard for how sensitivity is communicated downstream.
## The symptom and the diagnosis You solve `Ax = b`, change one entry of `b` in its fifth decimal place, solve again, and get a completely different `x`. The first instinct is a bug. Usually there is none: the matrix is **ill-conditioned**, and the sensitivity you are seeing is a true property of the problem you posed. ## The condition number For an invertible `A`, the condition number is `cond(A) = ||A|| * ||A^-1||`, measured in whatever matrix norm you choose; in the 2-norm it equals the ratio of the largest to the smallest singular value of `A`. Its meaning is an amplification bound. If you perturb the right-hand side from `b` to `b + db` and the solution moves from `x` to `x + dx`, then ``` ||dx|| / ||x|| <= cond(A) * ||db|| / ||b|| ``` Relative error in, relative error out, multiplied by the condition number. It is always at least 1 - a perfectly conditioned matrix leaves relative error untouched. Note it depends only on `A`: scaling `b` by a thousand changes nothing. ## A worked example Let ``` A = [[1, 1], [1, 1.0001]] ``` With `b = (2, 2.0001)` the exact solution is `x = (1, 1)` - check both equations. Now perturb to `b = (2, 2.0002)`. Subtracting the first equation from the second gives `0.0001 * x2 = 0.0002`, so `x2 = 2` and `x1 = 0`. A relative change of about 0.005 percent in `b` produced a change of 100 percent in `x`. The condition number of this matrix is on the order of 10^4, which is exactly the amplification you observed. Geometrically the two equations are lines that are nearly parallel; where nearly-parallel lines cross is exquisitely sensitive to shifting either one. The same pathology at scale is the **Hilbert matrix**, whose entry in row i, column j is `1 / (i + j - 1)`. It is the textbook stress test: its condition number grows explosively with size, exceeding 10^12 by the time the matrix is 10 by 10, so a 10-by-10 Hilbert system is effectively unsolvable in double precision. ## The digits rule of thumb Double-precision arithmetic carries roughly 16 significant decimal digits. Solving with a stable factorization introduces relative error of about `cond(A)` times the machine precision, so you lose roughly `log10(cond(A))` digits of accuracy. A condition number near 10^8 leaves about 8 good digits - usually fine. Near 10^15 you have essentially none, and the computed answer is arbitrary. This is the fastest way to turn a condition number into a decision. ## It is the matrix, not the algorithm A crucial distinction in interviews: **stability** is a property of an algorithm, **conditioning** is a property of the problem. A backward-stable method gives you the exact answer to a slightly perturbed problem, which is the best any method can do - but if the problem itself amplifies perturbations by 10^10, so does the answer. Switching solvers, raising precision, or reordering operations addresses the algorithm side only. Diagnosing an unstable solve therefore starts by measuring the conditioning of `A`, not by rewriting the solve. ## What actually helps - **Rescale the columns.** Columns in wildly different units - pascals beside kelvin beside a column of ones - inflate the condition number for a purely cosmetic reason. Normalising columns to comparable ranges often buys back several digits. - **Remove redundancy.** Two columns encoding the same quantity, or one that is nearly a combination of others, is the usual real cause. Drop one or combine them. - **Regularise.** Adding a small positive amount to the diagonal trades a little bias for a dramatically better-conditioned system, and turns an unstable answer into a stable, slightly shrunk one. - **Change the measurement design.** If the equations genuinely do not pin down the unknowns, the honest fix is more informative data, not more arithmetic. - **Report the sensitivity.** A number you cannot trust to more than one digit should be delivered with that caveat rather than to six decimal places. ## Warning signs before you even solve Hugely different column magnitudes, columns you know are derived from one another, a solver emitting a near-singularity warning, or coefficients that flip sign when you add a handful of rows - all point at the same underlying condition. Treat them as evidence about the data, not as noise from the numerical library.
- With a condition number near 10^8, how many correct digits should you expect in double precision?About eight. Double precision carries roughly 16 significant digits, and a stable solve produces relative error of order the condition number times machine precision, so you lose about `log10(cond(A))` digits - here eight of the sixteen. That is usually acceptable. At 10^15 you have effectively no reliable digits left and should not report the answer as computed.
- Is ill-conditioning a property of the matrix or of the algorithm you use?Of the matrix - it describes how much the true solution moves when the data moves, before any arithmetic happens. Algorithms are judged by stability instead: a backward-stable method returns the exact solution of a slightly perturbed problem. Even a perfect algorithm on an ill-conditioned matrix inherits the amplification, so switching solvers or raising precision only postpones the problem.
- Does scaling the right-hand side b by 1000 change the conditioning of the system?No. The condition number is `||A|| * ||A^-1||` and involves only the matrix, so scaling `b` scales the solution proportionally and leaves relative sensitivity untouched. Scaling the *columns* of `A` is a different matter entirely: when columns sit on wildly different unit scales, rescaling them to comparable ranges genuinely lowers the condition number and buys real accuracy.
Locating a point by crossing two almost-parallel roads on a map. Shift either road by a hair and the crossing point slides down the street.
saying these in an interview costs you the question
- Assuming the instability is a bug in the solver
- Believing higher precision fixes an ill-conditioned problem
- Confusing algorithm stability with problem conditioning
- Thinking the condition number depends on the right-hand side b
- Reporting six decimal places from a badly conditioned solve
- Treating a near-singularity warning as harmless library noise