Networks, and how a solve is checked

The matrix that is ill, and the answer that is not

Every other essay here treats the solve as exact, and it is not. A bridge walked towards balance loses one digit per decade of imbalance and has none left at a part in 10¹⁵ — on a matrix whose condition number never moves and whose smallest pivot stays four orders above the threshold this solver refuses at. A feedback amplifier does the opposite: the solver declines to answer at a gain of 10⁹, one decade after it returned an answer that was exact to the last bit.

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 101210^{12} 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, κ=MM1\kappa = \|M\|\,\|M^{-1}\|, 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.

Fourteen decades of imbalance, fourteen digits gone, and a matrix in perfect healthcomputed by solving, not by drawing. A Wheatstone bridge walked towards balance, with the relative error of the solved output against a closed form that cannot lose digits. The condition number of the nodal matrix is 505.0 at every imbalance and the smallest pivot is 2.0e-3 of the matrix norm — orders above the 1e-12 at which this solver refuses to answer at all. Neither number moves, and the answer still loses one digit per decade of imbalance, reaching 33% at δ = 1e-15. The bound drawn over it is the round-off divided by the imbalance, which the measurement stays under at every point. The third curve is the same closed form written as ½ − 1/(2+δ) — algebraically identical, and it loses its digits at the same rate, which is where the loss lives: in the subtraction of two nearly equal numbers, not in the matrix.imbalance of the bridge, δrelative error of the answer10⁻¹⁵10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹no correct digitshalf the digits at δ = √εthe solve, the bound, and the closed form that subtractsarm resistance1 kΩcondition number505.0, at every δpivot ratio2.0e-3…the solver refusesbelow 1e-12round-off1.11e-16δ = 1e-88.3e-6% outδ = 1e-121.4e-1% outδ = 1e-1533% outdigits left there0.5solved, then checked — a solve against a closed form that cannot cancelno correct digits below δ = 1e-15
Fig. 1 A bridge walked towards balance, with the error of the solved output against a closed form that cannot lose digits. The condition number is 505 at every point on the axis and the smallest pivot never moves; the answer loses a digit per decade all the way to having none.

The first network: a healthy matrix and no correct digits

A Wheatstone bridge with three equal arms and one out by a fraction δ\delta has an output of

δ2(2+δ)\frac{\delta}{2(2+\delta)}

— exactly, for any δ\delta. Solved from the netlist by reading the two node voltages and subtracting, the answer agrees with that expression to five parts in 101510^{15} at one per cent of imbalance, and to nothing at all at a part in 101510^{15}: 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, ε/δ\varepsilon/\delta, 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 101210^{-12} 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.

A network solved, and checked: a bridge, which no series-parallel reduction reaches. Node potentials from modified nodal analysis. The branch currents are then recomputed from each element's own law and summed at every node; the residual is 2.7e-16 of the largest current in the circuit, which is floating-point rounding and nothing else.
Fig. 2 The operation being audited: a bridge assembled from element stamps and solved, with the currents rebuilt from the element laws and summed at every node. That check passes at every imbalance in this essay, including the ones where the answer has no correct digits.
A 350 Ω bridge, with ideal leads. The straight line is the expression every textbook gives, Vδ/4; the curve is the solve. They part company at half the fractional change — 0.498% at 1.0% — so the tangent is worth one per cent only up to 2.020%. Driving the bridge from a current source instead halves the departure at every point and moves that edge to 4.040%.
Fig. 3 The circuit in question as an instrument, from the applied field, where a bridge near balance is the whole point: the closer to balance it is operated, the more of this essay applies to reading it.

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 121/(2+δ)\tfrac{1}{2} - 1/(2+\delta), 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 δ=1014\delta = 10^{-14}, everything gone by 101510^{-15}, and bounded by the same ε/δ\varepsilon/\delta throughout.

The version this essay compares against — δ/2(2+δ)\delta/2(2+\delta) — has the same value and never subtracts two nearly equal numbers, so it is accurate to an ulp at every δ\delta 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.

Fourteen decades of imbalance, fourteen digits gone, and a matrix in perfect health. computed by solving, not by drawing. A Wheatstone bridge walked towards balance, with the relative error of the solved output against a closed form that cannot lose digits. The condition number of the nodal matrix is 52.77 at every imbalance and the smallest pivot is 2.0e-2 of the matrix norm — orders above the 1e-12 at which this solver refuses to answer at all. Neither number moves, and the answer still loses one digit per decade of imbalance, reaching 33% at δ = 1e-15. The bound drawn over it is the round-off divided by the imbalance, which the measurement stays under at every point. The third curve is the same closed form written as ½ − 1/(2+δ) — algebraically identical, and it loses its digits at the same rate, which is where the loss lives: in the subtraction of two nearly equal numbers, not in the matrix.
Fig. 4 Arms of a hundred ohms. The condition number is 52.77 throughout and the answer is 33% wrong at a perturbation of 10⁻¹⁵ — the same 33% the kilohm bridge gives at κ = 505.0. The same algebra written twice: ten times the condition number, the identical error.
Fourteen decades of imbalance, fourteen digits gone, and a matrix in perfect health. computed by solving, not by drawing. A Wheatstone bridge walked towards balance, with the relative error of the solved output against a closed form that cannot lose digits. The condition number of the nodal matrix is 5.025e+6 at every imbalance and the smallest pivot is 2.0e-7 of the matrix norm — orders above the 1e-12 at which this solver refuses to answer at all. Neither number moves, and the answer still loses one digit per decade of imbalance, reaching 11% at δ = 1e-15. The bound drawn over it is the round-off divided by the imbalance, which the measurement stays under at every point. The third curve is the same closed form written as ½ − 1/(2+δ) — algebraically identical, and it loses its digits at the same rate, which is where the loss lives: in the subtraction of two nearly equal numbers, not in the matrix.
Fig. 5 The same bridge with arms of ten megohms instead of a kilohm. The condition number is now five million — ten thousand times worse — and every error on the curve is identical. κ moves and the answer does not.

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 A/(1+Aβ)A/(1+A\beta), which stops depending on AA as soon as AβA\beta is large — that is what feedback is for. Sweep the gain block over fourteen decades and the matrix gets steadily worse: κ\kappa rises in proportion to AA, reaching 1.8×10121.8\times10^{12} at A=108A = 10^8, and the smallest pivot falls to 1.11×10121.11\times10^{-12} of the matrix norm.

At A=109A = 10^9 the pivot falls below 101210^{-12} 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 A=108A = 10^8, κε\kappa\varepsilon permits an error of 2×1042\times10^{-4}, 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.

The solver refuses the matrix one decade after the answer was still exact. computed by solving, not by drawing. A non-inverting amplifier whose gain block is swept over fourteen decades, with the relative error of the solved closed-loop gain against A/(1 + Aβ), and the condition number's own bound κ·ε drawn over it. The matrix gets steadily worse — κ rises in proportion to the gain, and at A = 1e+9 the smallest pivot falls below the part in 1e-12 of the matrix norm at which this solver declines to answer. The answer never loses a digit: at A = 1e+8, one decade below the refusal, κ·ε permits an error of 2.0e-4 and the measured error is zero to the last bit. The bound is not wrong, it is answering a different question — how far the answer could move if the data moved, rather than whether this quantity depends on the number that is making the matrix ill. A closed-loop gain does not, which is what feedback is for.
Fig. 6 The gain sweep, with the condition number’s bound drawn over the measured error. The bound rises; the error does not; the refusal fires where the matrix crosses a threshold rather than where any answer went wrong.
Fourteen decades of imbalance, fourteen digits gone, and a matrix in perfect health. computed by solving, not by drawing. A Wheatstone bridge walked towards balance, with the relative error of the solved output against a closed form that cannot lose digits. The condition number of the nodal matrix is 5.025e+4 at every imbalance and the smallest pivot is 2.0e-5 of the matrix norm — orders above the 1e-12 at which this solver refuses to answer at all. Neither number moves, and the answer still loses one digit per decade of imbalance, reaching 33% at δ = 1e-15. The bound drawn over it is the round-off divided by the imbalance, which the measurement stays under at every point. The third curve is the same closed form written as ½ − 1/(2+δ) — algebraically identical, and it loses its digits at the same rate, which is where the loss lives: in the subtraction of two nearly equal numbers, not in the matrix.
Fig. 7 A hundred kilohms: κ = 5.025×10⁴, and 33% wrong at the same perturbation. Four decades of conditioning between this and the hundred-ohm case, and the error is identical to two figures — which is the second network’s message: a refused matrix and a perfect answer are not a contradiction, because the condition number bounds what could go wrong rather than reporting what did.

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.

Fourteen decades of imbalance, fourteen digits gone, and a matrix in perfect health. computed by solving, not by drawing. A Wheatstone bridge walked towards balance, with the relative error of the solved output against a closed form that cannot lose digits. The condition number of the nodal matrix is 14.92 at every imbalance and the smallest pivot is 5.0e-1 of the matrix norm — orders above the 1e-12 at which this solver refuses to answer at all. Neither number moves, and the answer still loses one digit per decade of imbalance, reaching 11% at δ = 1e-15. The bound drawn over it is the round-off divided by the imbalance, which the measurement stays under at every point. The third curve is the same closed form written as ½ − 1/(2+δ) — algebraically identical, and it loses its digits at the same rate, which is where the loss lives: in the subtraction of two nearly equal numbers, not in the matrix.
Fig. 8 And arms of one ohm, where the matrix is in perfect health: κ = 14.92, and the answer is 11% wrong. What the two networks say together is the uncomfortable half of numerical analysis — the best-conditioned bridge on the slider has a smaller error than the worst by only three times, over five decades of condition number, so the condition number is not a prediction of anything and a design that trusts it as one is trusting a bound.

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.

κ\kappa 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 101210^{12} — 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 κ\kappa 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 κ=1012\kappa = 10^{12} has some quantity in it that moves by a part in ten thousand for a part in 101610^{16} 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 κ\kappa 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 δ\delta of the numbers it is made from keeps log10(1/ε)log10(1/δ)\log_{10}(1/\varepsilon) - \log_{10}(1/\delta) of them. Half the digits are gone when δ=ε=1.5×108\delta = \sqrt{\varepsilon} = 1.5\times10^{-8}.

That is a number worth knowing because it is so much larger than people expect. A quantity that is a part in 10810^8 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 10910^{9} 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 3×1053\times10^5 has coefficients spanning (3×105)n(3\times10^5)^n 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 nn 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 10910^{-9} 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