Networks, and how a solve is checked

The digits the arithmetic did not have

The rung below bounded this site's own arithmetic and found two boundaries it could not attribute: a bridge with no correct figures left at an imbalance of 10⁻¹⁵, and a filter synthesis that stalls at order 14. 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. The bridge's loss is entirely the arithmetic's. The synthesis's is mostly the data's, and doubling the digits makes it worse.

18 min read 8 figures Two routes to a number Refused, not extrapolated Every model has an edge

Assumes: The matrix that is ill, and the answer that is not · What a network answers, and how the answer is checked

The rung below this one turned the site’s instruments on the site’s own arithmetic and found two boundaries.

A bridge walked towards balance loses one decimal digit per decade of imbalance and has none left at 10⁻¹⁵ — 33 per cent wrong — on a matrix whose condition number is 505 at every point and whose smallest pivot stays four orders above the threshold the solver refuses at. And a ladder synthesis stalls: the continued fraction that peels off one element at a time subtracts polynomials whose leading coefficients cancel, and when they are long enough the cancellation removes more digits than double precision has. Order 14 for a Chebyshev; order 9 for a Butterworth.

Both were reported as boundaries. Neither was attributed, and the distinction matters more than it looks:

an ill-conditioned problem stays ill-conditioned however many digits are used — the answer is genuinely sensitive to the data, and no arithmetic repairs that;
a well-conditioned problem computed badly gets better with more digits, because the loss was manufactured by the algorithm rather than present in the question.

Adding digits is the experiment that separates them. This rung has the digits.

Sixteen more digits move the boundary by sixteen decades and leave it exactly where it was. computed by solving, not by drawing. The rung below's bridge, walked towards balance and solved twice: once in double precision and once with a pair of doubles carrying about 31 decimal digits, against a closed form that cannot lose any. The 33 per cent error at an imbalance of 10⁻¹⁵ becomes 7.0e-18 — so that loss was the arithmetic's and not the network's, which is what the rung below could not say. Each arithmetic's error is its own round-off divided by the imbalance, drawn as the two straight lines, so the second boundary is the first one moved by exactly the extra digits. The condition number is 505 in both cases and at every point, which is the diagnostic being blind twice over. — Fig. 1 The rung below’s bridge, solved twice: in double precision and with a pair of doubles carrying about 31 decimal digits, against a closed form that cannot lose any. Each arithmetic’s error is its own round-off divided by the imbalance, drawn as the two straight lines.

Two doubles that behave as one number

A double-double is a pair, $(\mathrm{hi}, \mathrm{lo})$ , whose exact sum is the value and whose magnitudes do not overlap: $\mathrm{lo}$ is at most half an ulp of $\mathrm{hi}$ . The pair carries about 31 decimal digits where one double carries 16.

The arithmetic is exact-transformation arithmetic and is two identities plus bookkeeping. twoSum(a, b) returns the sum of two doubles and the rounding error it made — which is itself exactly representable as a double, which is the whole trick. twoProd(a, b) does the same for a product, by splitting each operand into 26-bit halves whose products are exact.

Nothing in it approximates higher precision. The pair is exact at every step and the only rounding is the final renormalisation, which is why the identity that catches a wrong implementation immediately is

(1 + \varepsilon) - 1 = \varepsilon\ \text{exactly}

for an $\varepsilon$ of $10^{-25}$ , far below anything a double can hold beside a one. It does, and the check is in the site’s gate.

Division and square root are Newton corrections rather than exact transformations, so they are accurate to the pair rather than to its last bit — which is why every check written against this arithmetic is written to $10^{-30}$ and not to $10^{-32}$ . The cost is about twenty times, not four: every multiplication is two splits, four products and a dependent chain that nothing pipelines.

The bridge: entirely the arithmetic

Solve the bridge’s nodal system with the same elimination, the same partial pivoting and the same back-substitution, with a pair instead of a double, and compare against the closed form $\delta/2(2+\delta)$ that has no subtraction in it.

imbalance	double	the pair
10⁻⁹	8.3 × 10⁻⁸	7.9 × 10⁻²⁵
10⁻¹²	8.9 × 10⁻⁵	2.6 × 10⁻²¹
10⁻¹⁵	0.332	7.0 × 10⁻¹⁸
10⁻²⁴	1	2.8 × 10⁻⁹
10⁻³¹	1	0.023

The 33 per cent is entirely the arithmetic’s. The same network, asked the same question, answered by the same algorithm with more digits, comes back right to seven parts in a thousand million million million. The problem was never ill-conditioned in any sense that mattered; the loss was manufactured by subtracting two nearly equal numbers, and giving the subtraction more digits to work with gives the answer back.

And the pair has a boundary of its own, in exactly the same place, sixteen decades along. Both arithmetics obey one law — the relative error is that arithmetic’s own round-off divided by the imbalance — which is the two straight lines the measurements sit on. The second boundary is the first one moved by precisely the extra digits, which is the strongest possible statement that nothing else is going on.

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 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. — Fig. 2 The rung below’s measurement, for the comparison: the same bridge in double precision alone, with the condition number and the pivot ratio that stay in perfect health throughout.

The condition number is 505 in both cases and at every point, and it is now blind twice over: it did not predict the double’s failure and it does not predict the pair’s success either. What predicts both is one number that is not a property of the matrix at all — how nearly equal the two quantities being subtracted are.

The ladder: mostly the data, and the digits make it worse

The other boundary does not behave the same way, and the way it fails to is the finding.

Give the continued-fraction expansion the pair’s arithmetic, leave the poles where they are — computed in ordinary double precision, which is what a real design starts from — and set the threshold below which a leading coefficient is called zero to the pair’s own precision.

It stalls at order 1.

That is not a bug and it is worth following, because it is the most useful thing in this essay. The expansion works by subtracting polynomials whose leading terms cancel; the degree drops because the leading coefficient becomes zero. With double-precision inputs it does not become zero — it becomes $3\times10^{-16}$ , which is the input’s own error, and in double arithmetic that is indistinguishable from zero and gets rounded away. In the pair it is a real number, faithfully preserved, and the degree never drops.

More digits than the data has do not make an algorithm better. They make it hold on to the error.

Fig. 3 The highest order that synthesises the designed response, against the threshold below which a leading coefficient is called zero. Drag it between the two families — the shape is different for each and the reason is in the reflection zeros.

Three quantities, and the arithmetic is the least of them

Sweeping the threshold turns one number into a picture, and there are three things in it rather than one.

threshold	Chebyshev, the pair	Butterworth, the pair	Butterworth, exact roots
10⁻⁹	25	10	18
10⁻¹¹	18	8	18
10⁻¹³	11	6	16
10⁻¹⁵	5	2	16
10⁻¹⁸	2	0	14
10⁻²⁸	0	0	7

Against a shipped double-precision limit of 13 for the Chebyshev and 8 for the Butterworth.

The threshold is a real quantity and nobody had noticed. It is the number that says what “zero” means, it appears in the code as 1e-11, and every column above falls monotonically as it tightens. It is neither the arithmetic’s precision nor the data’s; it has to sit between them, and the shipped constant turns out to be very nearly the best available with double-precision data — a fact about that constant that was never established.

For the Chebyshev the arithmetic was part of it. With the threshold loosened to what the data supports, the pair reaches order 25 against the double’s 13.

For the Butterworth it was not. The pair with the same roots reaches 10 against 8 — nothing worth having. What the Butterworth needs is better roots, and the third column says how much: computing its poles from the pair’s own $\pi$ and its own sine, so that they are right to 31 digits rather than to 16, takes the same arithmetic from 8 to 18.

The rung below explained the five-order gap between the two families by the reflection zeros — a Butterworth’s are all at the origin, so $E - F$ cancels its leading term exactly and every subsequent step starts with fewer digits. That explanation is right and it is not the whole of it: the gap is also that a Butterworth’s poles are exactly known and a Chebyshev’s are not, so only one of the two has a data problem that can be fixed at all.

Twice the digits buys nothing; exact roots buy 10 orders. computed by solving, not by drawing. The highest butterworth order whose ladder synthesis produces the designed response, against the threshold below which a leading coefficient is treated as zero, for a pair of doubles carrying 31 decimal digits with double-precision roots and with roots computed exactly. The shipped double-precision synthesis reaches order 8. The pair reaches 10 at its best threshold and 0 at its own precision, worse than a double, because with only sixteen digits of data the extra digits preserve the input's error where a double would have rounded it away. Given roots that are exactly right, the same arithmetic reaches 18. Three quantities decide this and the arithmetic is the least of them. — Fig. 4 The Butterworth column, where twice the digits buys nothing with double-precision roots and ten orders with exact ones. The two curves are the same arithmetic given different data.

Where the exact roots come from

Making a Butterworth pole exact needs a little transcendental arithmetic and it is worth saying which.

A Butterworth pole is $e^{i\theta}$ at an angle that is a rational multiple of π, so there is nothing approximate about it: with a pair’s worth of π and a pair’s worth of sine it is right to 31 digits. The sine is argument reduction to a quadrant and then a Taylor series on $|x| \le \pi/4$ , which converges to 32 digits in about a dozen terms. π itself is a constant rather than a computation, because every series for it would need this arithmetic to evaluate.

Checked the way this collection checks things: $\sin^2 + \cos^2 - 1$ comes back at $-4\times10^{-33}$ , and every pole’s $|p|^2 - 1$ at the same, which is the pair’s own floor.

A Chebyshev pole is not that. Its real and imaginary parts are $\sinh$ and $\cosh$ of $\operatorname{asinh}(1/\varepsilon)/n$ , and $\varepsilon$ is $\sqrt{10^{r/10} - 1}$ for a ripple $r$ in decibels — a transcendental function of a transcendental function of a decimal number. Making that exact is a different project, and it is why the third column of the table exists for one family only.

That is the honest boundary of this rung, and it is a boundary of the same kind as everything else here: not “the arithmetic runs out” but “the data does, and for this family there is nowhere better to get it from”.

The Butterworth ladder at order 5, expanded rather than looked up. computed by solving, not by drawing. The element values are the successive quotients of a continued-fraction expansion of (E+F)/(E−F), where E is the filter's own pole polynomial and F carries its reflection zeros. They are the numbers in every filter design table, and they agree with the closed form 2·sin((2k−1)π/2n) to twelve digits. The termination is 1.0000 times the source resistance, as an odd-order design must be. — Fig. 5 What the synthesis produces, from the filters field’s own essay: the g-values a continued fraction returns, which reproduce every published table to twelve digits. Every order in this essay’s tables is required to reproduce its design response as well, because a ladder of positive values whose response is wrong is the failure a positivity test cannot see.

What twenty times slower is worth

The cost is worth a paragraph because it decides where this belongs, and the answer is “as an instrument, and almost never in the site”.

Every multiplication in the pair is two splits, four products and a dependent chain of adds. Every division is two divisions and two multiplications. Nothing pipelines, because each step needs the previous step’s rounding error. Measured against the same code in double, it is about twenty times slower — not four, which is the number people guess from “twice the digits”.

Against that, consider what it would buy the site’s own solver. Every figure here solves networks whose answers are wanted to three or four significant figures for a drawing, and whose worst measured disagreement between two independent routes is $10^{-12}$ . The arithmetic is not the limit on anything this collection draws — and the two places it was a limit are both measurements about arithmetic rather than about circuits.

So the pair stays where it is: a way of asking what the arithmetic costs, in a file that nothing in the built site imports. That is the right place for an instrument that is twenty times slower and answers one question. The alternative — running everything in it, on the argument that more digits cannot hurt — is exactly the reasoning the ladder synthesis refutes.

The general shape, which is not about circuits

Three failures of numerical arithmetic appear in this collection and it is worth naming them together, because they look alike from a distance and want different repairs.

A cancellation subtracts two nearly equal numbers and keeps their difference. The information was there and the algorithm threw it away. More digits recover it exactly, and so does rewriting the algebra: the bridge’s closed form written as $\delta/2(2+\delta)$ loses nothing in double precision at any imbalance, and the same algebra written as $\tfrac12 - 1/(2+\delta)$ loses everything at the same place the solve does.

An amplification has a genuinely sensitive answer — a small change in the data makes a large change in the result — and no arithmetic helps, because the question itself is the problem. The rung below’s feedback amplifier, whose condition number reaches $1.8\times10^{12}$ , is that shape.

A threshold is neither: a decision, taken inside the algorithm, about what counts as zero. It is invisible in every diagnostic, it does not appear in any error bound, and on the ladder synthesis it is worth more orders than either of the other two.

The rung below found the first and the second and named them well. The third is this rung’s, and it is the one that had no name at all — it was a constant on line 78.

What this says about the two boundaries the rung below drew

Both boundaries were real and both were drawn in the right place. What this rung adds is what each is a boundary of, and they turn out to be different kinds of thing:

The bridge’s boundary belongs to the arithmetic. It moves when the arithmetic does, exactly as far as the arithmetic moves, and the network is not ill-conditioned in any sense that a solver can act on.
The ladder’s belongs mostly to the data, partly to the algorithm’s own threshold, and least to the arithmetic. Doubling the digits without doubling the data’s digits makes it worse.

Which is a general statement worth having, and it is not the one that gets made. “Use higher precision” is the standard advice for a numerical difficulty and it is right about a third of the time. The other two thirds are: give the algorithm better inputs, or tell it what zero means.

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 rung below’s other network, which fails in the opposite direction: a feedback amplifier whose condition number rises with the gain block. Swept over fifteen decades of it, the solver answers to a gain of 10⁸ with no error at all and refuses from 10⁹ — one decade between an exact answer and a declined one, with nothing in between. Nothing in this essay changes it, because a refusal on a pivot ratio is a test of the matrix rather than of the answer.

An order-8 cascade at 10 kΩ: no impedance level meets 0.1 dB at all. computed by solving, not by drawing. A 10.0 kHz unity-gain Butterworth of order 8, 4 Sallen-Key sections in cascade, realised at seven impedance levels three decades apart, with every resistance multiplied and every capacitance divided by the same factor. The design is exactly invariant: the solved magnitudes agree to 4.4e-15 of each other across all seven and every frequency in the passband, which is the last bits of a double rather than a good approximation. The realisation is not, because two of its quantities do not scale — 50 Ω of amplifier output resistance and 2 pF of stray capacitance to everywhere — and they bind at opposite ends. No impedance level meets 0.1 dB at all: the least departure any of them allows is 0.1138 dB at 1000 Ω; at this setting it is 0.284 dB at 11.8 kHz. The consideration that does not appear on either axis is noise: the resistors' density goes as √R, so across the six decades drawn the noise moves by 1000 times and points at the low end of the band. — Fig. 7 And the argument that met this boundary from the other side, from the filters field: a ladder’s realisable impedance band, whose sweep stops at order 14 for a reason that was reported as arithmetic and is now known to be a threshold and a set of poles. Drawn here at the eighth order, where the departure between the design and its realisation is 0.2837 dB at the best impedance level available — so the band has closed against a tenth of a decibel before any question of arithmetic arises.

The three places conditioning decides something

A condition number bounds an error rather than predicting one, and this collection meets that distinction three times. The answer that is perfect and absurd is the extreme case — a matrix the solver refuses and an answer that was exact to fifteen figures a step earlier. A ladder is not a cascade is where conditioning stops being about arithmetic and becomes about components, and Every derivative, and the one that is zero is where the sensitivity that underlies both is computed exactly rather than estimated. The derivative of a root carries the same machinery to the poles themselves, and Exact outside and wrong within is the reminder that a well-conditioned answer to the wrong question is still the wrong answer.

What is checked

The arithmetic is checked before anything is built on it, on the identities that catch a wrong implementation immediately: $(1 + 10^{-25}) - 1$ must return $10^{-25}$ exactly; $3 \times (1/3) - 1$ and $(\sqrt2)^2 - 2$ must return zero; and $\sin^2 + \cos^2 - 1$ must land on the pair’s own floor rather than on a double’s.

The bridge carries the finding as two assertions rather than one. At the rung below’s worst case the double must be more than ten per cent wrong and the pair better than $10^{-12}$ — which is the attribution, and either half alone would be a weaker claim. And nine decades further on, where the double has lost everything, the pair is required to still be right to a part in a million.

The synthesis carries three. The pair at its own precision must do worse than the double, which is the counter-intuitive half and the one a casual reading would have got backwards; at its best threshold it must do at least as well; and the limit must fall monotonically as the threshold tightens, which is what establishes the threshold as a third quantity rather than a tolerance. For the Butterworth, exact roots are required to more than double the order.

Every order counted as a success has to produce the designed response, not merely a ladder of positive numbers, because a loose threshold produces plausible ladders that are not the filter — and a positivity test passes them.

What is not done: the complex solver, which is still double precision everywhere the site uses it — this file’s solve is real, because both networks the rung below bounded are at direct current and a complex pair would be four times the work for no extra answer. The Chebyshev poles, for the reason above. And nothing here is used in the built site’s own arithmetic: it is an instrument for asking what the arithmetic costs, not a replacement for it.

What the two verdicts mean downstream

The bridge and the ladder both stall, the diagnosis separates them, and each verdict lands on an essay that had left the question open.

The matrix that is ill, and the answer that is not is the bridge’s, and the verdict is the good one: the loss is entirely the arithmetic’s, so a bridge walked to a part in $10^{15}$ is a measurement this collection could make with more digits and chooses not to. That matters because the essay’s own finding — a condition number that never moves and a smallest pivot four orders above the refusal threshold, on a network losing a digit a decade — reads as a warning about the solver until this experiment says which half of the pair is at fault.

The floor that outlives the arithmetic is the ladder’s, and the verdict is the unwelcome one. Its extrapolation to order thirty-two is stated as an extrapolation because the synthesis stalls at order nine for a Butterworth and fourteen for a Chebyshev, and it names extended precision as the thing that would settle whether the floor continues along the same line. It would not. The loss is mostly the data’s, doubling the digits makes it worse, and the stall is a property of the problem rather than of its implementation.

The asymmetry between the two verdicts is the reason the experiment is worth its cost. A recoverable loss is a decision about how much arithmetic to buy; an unrecoverable one is a boundary, and belongs with the frequencies and amplitudes this collection collects rather than with its errata.

And it is a boundary of an unusual kind, worth noting beside the edges that are lengths and the rest: its axis is neither a frequency nor an amplitude nor a size but an order, and the quantity that fails is not the circuit but the procedure that produces it. A ninth-order ladder exists and behaves perfectly; what does not exist is a way of computing its element values from a reflection polynomial in double precision.

Part 2 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: