The matrix that is ill, and the answer that is not
Assumes: What a network answers, and how the answer is checked · The answer that is perfect and absurd
Every figure on this site is a solved network, and every essay so far has treated the solve as exact. It is not. The matrix is assembled in double precision, eliminated in double precision, and back-substituted in double precision, and each of those steps rounds.
The question this essay is about is when that matters, and the answer is not either of the two numbers a solver reports.
This collection’s solver already reports two. It refuses a network whose smallest pivot has fallen below a part in of the matrix norm — that is how it declines a network with no answer, and the essay in this field on the network that is perfect and absurd is about the four networks it refuses. And the condition number, , is the classical measure of how much a matrix can amplify a perturbation. Neither predicts the error of a solve, and the two networks below are chosen so that each is wrong about one of them.
The first network: a healthy matrix and no correct digits
A Wheatstone bridge with three equal arms and one out by a fraction has an output of
— exactly, for any . Solved from the netlist by reading the two node voltages and subtracting, the answer agrees with that expression to five parts in at one per cent of imbalance, and to nothing at all at a part in : at that point the solved output is 33 per cent wrong, which is no correct significant figures.
Between those, the error rises by one decade for each decade the bridge is walked closer to balance. The bound drawn over the measurement is the round-off divided by the imbalance, , and the measurement stays under it at every one of fourteen decades and reaches within a factor of three of it.
Nothing in the matrix moves while this happens. The condition number is 505 at every imbalance, to four figures. The smallest pivot is two parts in a thousand of the matrix norm — nine orders above the at which this solver declines to answer. Both diagnostics report a network in perfect health throughout, and both are right about the matrix.
The loss is not in the matrix. It is in the quantity: the output of a nearly balanced bridge is the difference of two numbers that are nearly equal, and subtracting two nearly equal numbers destroys as many digits as they have in common. A solver that returns both node voltages to fifteen correct digits has done its job, and the difference of two such numbers that agree in fourteen of them has one.
The same algebra, written twice
The clearest evidence that the loss belongs to the quantity rather than to the solve is that a closed form can be made to lose it too.
The output above can equally be written , which is algebraically identical and involves no matrix at all. Evaluated in double precision it tracks the solve almost exactly: 2.1 per cent out at , everything gone by , and bounded by the same throughout.
The version this essay compares against — — has the same value and never subtracts two nearly equal numbers, so it is accurate to an ulp at every and can serve as the truth.
That is the whole lesson in one comparison. The digits are lost by the subtraction, not by the method, and a method that does not subtract does not lose them. A nodal solve has no choice: it computes potentials and the quantity wanted is a difference of them, so it inherits the cancellation whether or not the underlying problem has one.
There is a practical rule in it for anybody using a circuit simulator, and it is not “use a better solver”. It is: if the quantity wanted is small compared with the potentials it is made of, ask the netlist for it directly. Put a source in the branch and read its current; measure the difference as a difference, not as two absolutes. This collection does that everywhere already, for a different reason — the second route — and it happens to be the numerically stable choice as well.
The second network: a refused matrix and a perfect answer
The other direction is the one this collection has already met without naming.
A non-inverting amplifier’s closed-loop gain is , which stops depending on as soon as is large — that is what feedback is for. Sweep the gain block over fourteen decades and the matrix gets steadily worse: rises in proportion to , reaching at , and the smallest pivot falls to of the matrix norm.
At the pivot falls below and the solver refuses. One decade below that refusal, on a matrix a hundred times worse than any this collection normally solves, the answer it returns is exact — zero error, to the last bit, at every gain in the sweep.
The condition number’s own bound is not violated; it is simply enormous and useless. At , permits an error of , and the measured error is zero: the bound is eight orders above the truth. It is not wrong, it is answering a different question. It says how far the answer could move if the data moved anywhere at all, and the quantity being asked for does not depend on the number that is making the matrix ill.
So the refusal is conservative, by a wide margin, in this case. It is the right test for the question it was built to answer — does this network determine its node voltages — and it fires here on a network that determines them perfectly well, because the pivot ratio and the accuracy of a particular quantity are not the same thing.
What the two networks say together
Put beside each other, the two measurements make a single claim that is more useful than either.
A condition number is a property of the matrix. It bounds the error of the worst quantity the matrix could be asked for, over all right-hand sides. It is therefore correct and pessimistic for any particular quantity, and it can be enormous for a network whose answer is exact.
A pivot ratio is a property of one elimination. It detects the case where the matrix is singular or nearly so — where the network genuinely does not determine its answer — and it is the right test for refusing a network. It says nothing about accuracy on a network it accepts.
Neither is the error. The error is a property of the quantity, and it is governed by how much cancellation there is between the numbers the quantity is made of — which is visible in the problem long before any matrix is assembled. A bridge near balance is an ill-conditioned question asked of a well-conditioned matrix; a high-gain feedback loop is a well-conditioned question asked of an ill-conditioned matrix.
This site’s standing habit turns out to be the right response to both. Every quantity here is computed a second way that shares no arithmetic with the first, and the two are required to agree; two routes that agree to twelve digits have not both suffered the same cancellation, and two that disagree have found something. Neither diagnostic the solver reports would have caught the bridge.
What the condition number is measuring, if not this
It would be easy to read the above as “the condition number is useless”, and it is not — it is answering a question nobody asked here, and the question it answers is worth stating so that the tool can be used for it.
bounds the relative change in the solution vector for a relative change in the data, over all right-hand sides and all perturbations. It is a worst case in two senses at once: the worst quantity the matrix could be asked for, and the worst direction the data could move in. The feedback amplifier’s matrix really can amplify a perturbation by — perturb the gain block’s coefficient and the open-loop output moves enormously — and the reason the answer does not is that the quantity being read is the closed loop, which is precisely the direction the amplification does not act in.
That makes the right tool for a different job: deciding whether a network’s answers are sensitive to its components, which is a physical question rather than a numerical one. A matrix with has some quantity in it that moves by a part in ten thousand for a part in of change, and if a component tolerance of one per cent happens to point that way, that quantity is meaningless in a real circuit as well as in the arithmetic.
Which is a link between two things this collection treats separately. The tolerance essay in this field samples component values three thousand times to see what the spread does; the condition number bounds the same effect analytically, for free, in one number that is pessimistic and cheap. Neither replaces the other, and reading as “how bad is my arithmetic” is what makes it look useless.
Half the digits, at the square root of the round-off
There is one number in the bridge figure worth carrying away as a rule of thumb, and it is marked on the axis.
Double precision starts with about 15.95 decimal digits. The error of a difference is the round-off divided by the fractional size of the difference, so a quantity that is a fraction of the numbers it is made from keeps of them. Half the digits are gone when .
That is a number worth knowing because it is so much larger than people expect. A quantity that is a part in of the potentials around it — a microvolt read on a ten-volt rail, a milliohm of imbalance in a hundred-ohm bridge, a hundredth of a decibel of ripple on a filter designed at unity — has already lost half of double precision’s digits before anything else has gone wrong. It still has eight, which is usually plenty; the point is that the budget started at sixteen and is now at eight, and a second such subtraction downstream finishes it.
The collection has one place where this has already bitten and it is recorded in the filters field: the continued fraction that synthesises a doubly terminated ladder subtracts polynomials whose leading terms agree, loses digits at every step, and stalls entirely at order nine for a Butterworth. That is this essay’s arithmetic, applied recursively, and it is why that field’s sweep stops where it does.
What this changes about the rest of the collection
Three practices in this collection are justified by this essay rather than by the reasons originally given for them, and it is worth saying so.
Two routes. Every quantity here is computed twice by computations that share no arithmetic. The reason given has always been that a method can be wrong; the reason this essay adds is that a method can be right and lossy, and the two routes will lose different digits because they subtract different things. Where the collection reports twelve-digit agreement between a march and a closed form, it has established more than that both are correct — it has established that neither has met a cancellation.
Tolerances chosen against a measured floor. Several figures here assert an agreement to a tolerance that was bracketed rather than picked: tight enough to reject the smallest real failure, loose enough to accept the arithmetic’s own noise. The lower end of that bracket is what this essay computes. A quantity that is a part in of the potentials it is made of cannot be asserted to twelve digits, and a figure that tries will fail on a machine with a different summation order rather than on a circuit that changed.
Rescaling before rooting. The semiconductor field has a routine that rescales time before recovering poles, because a polynomial whose roots are at has coefficients spanning and a trim that compares them against the largest removes real terms. That is the same phenomenon in a different operation, and the fix — make the numbers comparable before subtracting them — is the same fix.
Where conditioning decides something, and where it does not
This page’s finding — that the condition number bounds an error rather than predicting one — is used in three places and refused in one. The answer that is perfect and absurd is the extreme: an answer exact to fifteen figures one step before the solver refuses the matrix outright. The digits the arithmetic did not have is the same measurement read as a loss of significance rather than as a bound. The band that does not close is where the conditioning of a synthesis, rather than of a solve, decides how many orders a structure can be built at. Every derivative, and the one that is zero is the exact sensitivity all of them would rather have, and What a network answers, and how the answer is checked is the pair of checks that catch what a condition number cannot.
What is checked
The bridge’s condition number is asserted not to move as the imbalance is swept, and its pivot ratio to stay four orders above the refusal threshold, so that both diagnostics are demonstrably blind to what follows. The error is asserted to be bounded by twelve units of round-off divided by the imbalance at every one of fourteen decades — which is the bound the figure draws — and to have consumed every digit at the smallest imbalance. The subtracting form of the closed form is asserted to obey the same bound and to have lost everything at the same place, which is the check that the loss is the cancellation and not the matrix.
On the amplifier, the solver is asserted to answer below a gain and refuse above it, so the boundary is in the picture; the last answer it gives is asserted to be right to the last bit; and the condition number’s bound is asserted to be at least eight orders above the measured error there.
What is not attempted here: an extended-precision solve, which would show both effects moving with the working precision rather than being properties of the networks; and an estimate of the condition number that is cheap enough to compute on every solve, since the one used here inverts the matrix column by column and costs solves rather than one.
The extended-precision solve, and what it settled
The first of those was attempted, and it is the digits the arithmetic did not have. Its result is the one that makes this essay’s two failures into two different objects rather than two sizes of one: an ill-conditioned problem stays ill-conditioned however many digits are used, and a well-conditioned one computed badly gets better, so adding digits is the experiment that tells them apart — and it is the only experiment that does, because from inside a single run the two are indistinguishable.
The verdicts are worth having here beside the measurements they explain. The bridge’s loss is entirely the arithmetic’s: it is a subtraction of two nearly equal numbers, the underlying problem is fine, and more digits recover the answer digit for digit. The ladder synthesis’s stall is mostly the data’s, and doubling the digits makes it worse — which is the uncomfortable result, and the one that says the order-nine limit is not waiting on a better implementation.
That distinction is what a condition number was supposed to supply and does not, which is this essay’s own finding stated from the other side. A condition number is a property of the matrix, and both of these failures happen to networks whose matrices are unremarkable — the bridge’s never moves at all while its answer loses a digit a decade. What separates a recoverable loss from a permanent one is a property of the problem, and the cheapest probe of it is to solve the same problem twice at two precisions.
Which is a satisfying place for this essay to end, because it began with a condition number that never moved while an answer lost a digit a decade. The instrument that was supposed to report the trouble reported nothing, and the instrument that does report it is not an instrument at all but an experiment — run it again with more digits — that costs a second solve and needs no theory.
Both of the networks measured here are ones the rest of the collection uses constantly, which is why the essay is worth its space rather than being a note about arithmetic. The bridge that is linear near one point walks a bridge towards balance as its whole subject, reporting departures at absolute; and how much of the amplifier gets through works with feedback gains where the solver’s refusal is one decade away. Neither essay’s numbers are affected — that is this one’s finding — and neither would have known if they were.
Part 1 on conditioning
One argument about Conditioning, and one of 3 essays on it so far, each part numbered by how much of the idea it assumes. What sits either side of it:
What links here
Essays that reach for this one mid-argument — the half of a link its own author cannot write down, the 8 sharing most with it of 15.
What this makes readable
Essays that name this one as a prerequisite.
The objects named here
The third axis, after the field and the idea: the things themselves, and every essay that touches each one.
BisectionClosed formComponent toleranceModel refusalModified nodal analysisNumerical errorSingular matrixVerification
- The number that was wrong bisection, closed form, numerical error, verification
- Ten seconds, and fifteen minutes closed form, component tolerance, verification
- The gap a derivative needs component tolerance, model refusal, numerical error
- A sum that is exact, and the estimate that is not numerical error, verification
- The best damping is not the one to build bisection, component tolerance
- The floor that outlives the arithmetic model refusal, numerical error