Networks, and how a solve is checked

Where the matrix is worst, and where the answer is not

When a solve stops being exact has been answered with two networks at direct current. Swept along the frequency axis, a resistive chain's nodal matrix has a condition number of 4.00×10³ at direct current and 1.59×10⁷ at 964 Hz — a maximum at the band edge, at no ripple peak and at no feature the response has. It predicts nothing. The solution vector is right to three units of round-off everywhere, the response taken out of it loses four decades into the stopband, and the same filter written at 400 kΩ instead of 10 Ω has a condition number 1.4×10⁹ times larger and returns the same twelve digits.

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

Assumes: The matrix that is ill, and the answer that is not · What a network answers, and how the answer is checked · The same filter a thousand times larger

The two rungs below this one put the site’s own arithmetic on trial and both did it at direct current. The matrix that is ill, and the answer that is not walked a bridge towards balance and found a condition number that never moved while the answer lost a digit a decade. The digits the arithmetic did not have gave the same bridge thirty-one decimal digits and attributed the loss.

Both networks are resistive and both are solved at $s = 0$ . So is every other use of the condition number in this collection — the machinery takes a complex frequency and has never been handed one that is not zero, which means nothing here has asked how well posed a network is as a function of frequency, on the axis every other page is organised around.

A ladder at direct current and the same ladder at its band edge are not the same matrix, and until now nothing said so.

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. 1 The rung below’s bridge, for the comparison. Fourteen decades of imbalance, fourteen digits gone, a condition number of 505.0 at every point and a smallest pivot four orders above the threshold the solver refuses at. Both diagnostics are flat and the answer is 33 per cent wrong at the end.

The three terms, and the two of them nobody had read

The classical account of a solve has three quantities in it and this site has been computing all three since the first commit.

The residual is what can be measured without knowing the answer: how nearly the returned vector satisfies the system it was given, $\|M\hat{x} - b\|_\infty / \|b\|_\infty$ . It is attached to every solution.

The condition number turns that into a statement about the answer: a relative perturbation of $\varepsilon$ in the data can move the solution by $\kappa\varepsilon$ , so $\kappa$ is what converts a backward error into a forward one.

The growth factor is the term in the middle, and it is the one that decides whether the residual was earned. Gaussian elimination is backward stable only in so far as it does not manufacture large intermediate entries, and the site’s solver returns the largest entry it creates as a fraction of the largest it started with — from every solve, since the first commit, into a variable nothing read.

Three quantities, all present, never once on the same axis.

The sweep

Inside the passband the matrix is worst at the edge, and at no ripple peak. computed by solving, not by drawing. The condition number of a 5th-order Chebyshev filter's nodal matrix at every frequency from a hundredth of its cutoff to ten times it. It is 4.004e+3 at direct current, rises to 1.5868e+7 at 964.0 Hz — located by golden section rather than read off the sweep — falls to 4.970e+6 at 1520 Hz and rises again through the stopband. The maximum is above every ripple peak (the highest is at 897.9 Hz) and within 3.6 per cent of the half-power frequency: the worst-conditioned place in the passband is where the filter stops passing and starts blocking, which is a place the response curve has no feature at. It is a local maximum: above the band κ climbs again, reaching 2.702e+7 at ten times the cutoff, because the susceptances in the matrix grow with the frequency and κ counts them. Nothing about any of these numbers says whether a digit is actually lost anywhere. — Fig. 2 The condition number of a fifth-order Chebyshev ladder’s nodal matrix at every frequency from a hundredth of its cutoff to ten times it. 4.004×10³ at direct current, a maximum of 1.5868×10⁷ at 964.04 Hz located by golden section, a minimum of 4.970×10⁶ at 1520 Hz, and 2.702×10⁷ at ten times the cutoff.

The number moves by four orders of magnitude across the band, and it has a definite shape: a rise of nearly four decades from direct current, a maximum, a dip, and then a climb that does not stop.

That shape is the first thing the sweep buys, because a single number at $s = 0$ cannot have one. Every condition number quoted anywhere in this collection until now is the leftmost point of that curve, and the leftmost point is 4.004×10³ against a maximum of 1.5868×10⁷ — the least representative value on the axis, by nearly four decades, and the only one that had ever been measured.

The maximum is at 964.04 Hz. The ladder’s ripple peaks are at 554.90 and 897.85 Hz and its half-power frequency is 1000 Hz by construction, so the worst-conditioned place inside the passband is above every peak and 3.6 per cent below the cutoff. It is the band edge — the place where the ladder stops passing and starts blocking — and it is a place the response curve has no feature at, no name for, and no specification written about.

The dip and the climb after it are a different thing and it is worth separating them immediately. Above 1520 Hz the condition number rises again in proportion to the frequency, because the susceptances $\omega C$ in the matrix do, and $\kappa$ counts every entry it is given. That part of the curve is not about the ladder at all.

Inside the passband the matrix is worst at the edge, and at no ripple peak. computed by solving, not by drawing. The condition number of a 9th-order Chebyshev filter's nodal matrix at every frequency from a hundredth of its cutoff to ten times it. It is 6.006e+3 at direct current, rises to 4.5067e+7 at 985.7 Hz — located by golden section rather than read off the sweep — falls to 5.080e+6 at 1520 Hz and rises again through the stopband. The maximum is above every ripple peak (the highest is at 967.2 Hz) and within 1.4 per cent of the half-power frequency: the worst-conditioned place in the passband is where the filter stops passing and starts blocking, which is a place the response curve has no feature at. It is a local maximum: above the band κ climbs again, reaching 2.784e+7 at ten times the cutoff, because the susceptances in the matrix grow with the frequency and κ counts them. Nothing about any of these numbers says whether a digit is actually lost anywhere. — Fig. 3 The same measurement on a ninth-order ladder. The maximum has moved to 985.68 Hz — 1.4 per cent below the cutoff against 3.6 at fifth order — and grown to 4.5067×10⁷. The direct-current value has moved from 4.004×10³ to 6.006×10³, which is one extra ladder section.

The maximum walks towards the cutoff as the order rises: 964.04 Hz at fifth order, 977.24 at seventh, 985.68 at ninth, against 897.9, 946.4 and 967.2 Hz for the top ripple peak in each case. It is tracking the edge and not the peak, and the peak is chasing it. That is a fact about where a ladder’s matrix is least comfortable and it is worth knowing before any of it is discounted — because the next three sections discount most of it.

The three terms do not agree about anything

Three instruments on one axis, and no two of them agree. computed by solving, not by drawing. Everything a solve of a 5th-order ladder reports about itself, at every frequency. The condition number rises from 5.790e+4 to 2.702e+7 across the sweep, with a local maximum at the band edge on the way. The residual — how nearly the returned answer satisfies the system it was given — is under 5.6e-17 everywhere and falls from 5.55e-17 in the passband to 3.37e-19 in the stopband, which is the opposite direction from κ. The growth factor, the largest entry the elimination creates as a fraction of the largest it started with, never exceeds 7.43e-2, so the elimination manufactures nothing and the residual is earned. And the same matrices equilibrated — rows and columns scaled to unit largest entry — have a condition number between 9.25 and 337.5 — between 1.7e+2 and 2.9e+6 times smaller than the raw number, and the ratio itself moves across the band. The largest quantity on the picture is the one that is mostly units. — Fig. 4 Everything a solve reports about itself, at every frequency. κ rises from 5.790×10⁴ to 2.702×10⁷. The residual is under 5.6×10⁻¹⁷ everywhere and falls from 5.55×10⁻¹⁷ in the passband to 3.37×10⁻¹⁹ in the stopband. The growth factor never exceeds 7.43×10⁻². The fourth curve is the same matrices with their rows and columns scaled to unit largest entry.

The residual moves the opposite way from the condition number. It is largest in the passband, at 5.55×10⁻¹⁷, and smallest deep in the stopband, at 3.37×10⁻¹⁹ — falling by a factor of 165 across a sweep in which $\kappa$ rises by a factor of 467. Whatever the two are measuring, they are not measuring the same difficulty.

The reason it falls is not mysterious and it is worth saying, because it is the same reason the whole essay turns on. The residual is the largest row of $M\hat{x} - b$ against the largest entry of $b$ , and $b$ has a one-volt source in it and nothing else of any size. Deep in the stopband every node voltage past the first section is orders below a volt, so every product being formed and every rounding being made in those rows is small in absolute terms — and the residual is an absolute measure normalised by a right-hand side that has not changed. A backward error that shrinks because the answer shrank is not a solve getting better. It is the same instrument reading a different quantity, and it is exactly the distinction the forward measurement below is about.

The growth factor never reaches a tenth. Over the whole sweep the largest entry the elimination creates is 7.43×10⁻² of the largest entry it started with, so the elimination manufactures nothing and the residual it reports is earned rather than an artefact of an unstable pivot sequence. That is the term that would have said the answer was not entitled to its residual, and it says the opposite, everywhere. It costs nothing to know and nothing had asked.

And the fourth curve is where most of $\kappa$ goes.

Most of a condition number is the units it is written in

Scale each matrix’s rows and columns to unit largest entry, alternately, until it stops moving, and take the condition number of the result. That is not a better solver and it is not offered as one: it is the measurement that separates a matrix that is genuinely ill from one that is merely written in mixed units.

A modified-nodal row is Kirchhoff’s current law and its entries are conductances, in siemens. A branch-current row is a constitutive relation and its entries are $\pm 1$ . The two live in the same matrix — that is the whole design of the method, what a network answers is about why — and an impedance level therefore enters the condition number without entering the circuit.

Equilibrated, the same matrices run between 9.25 and 337.5 across the whole sweep, against a raw $\kappa$ reaching 2.702×10⁷: between 1.7×10² and 2.9×10⁶ times smaller, with the ratio itself moving by four orders across the band. The largest quantity on the picture is the one that is mostly units.

The equilibrated curve also runs the other way from the raw one, and the direction is the finding rather than a detail. It is largest at low frequency — 337.5 at 10 Hz, falling to 9.25 at ten times the cutoff — so once the units are taken away, the ladder’s matrix is least well posed exactly where its answer is most certain: in the flat part of the passband, where the response is one half by construction and the two routes agree to two units of round-off. At direct current the reactances leave the matrix altogether, the inductor rows read $v = 0$ and the capacitors carry no entry at all, and what is left is a purely resistive system; a little way above it the reactive entries are present and tiny, and a matrix holding entries several decades apart is what a condition number counts. None of that is a difficulty with the circuit.

One feature survives the scaling and it is the interesting one. The equilibrated number falls monotonically from 337.5 at low frequency to 9.25 in the stopband — except at the band edge, where it dips to 16.19 and rises again to 50.45 at 949 Hz. The band-edge maximum is the part of the curve that is about the network. Everything else in the raw sweep is the matrix’s units.

Nine decades of condition number, one answer

The same filter, one answer, and a condition number nine decades wide. computed by solving, not by drawing. One 5th-order Chebyshev ladder written at eight impedance levels from 10 Ω to 400 kΩ, measured at 964 Hz where its matrix is worst. The condition number runs from 1.838e+3 to 2.535e+12 — a factor of 1.4e+9 — and the response is 0.438134764076 at every one of them, identical to the last bits. Scale each matrix's rows and columns to unit largest entry and the condition number is 51.179 to 51.612 throughout: 0.85 per cent, against nine orders. A nodal row is in siemens and a branch-current row is dimensionless, so an impedance level enters the condition number without entering the circuit. The refusal is not cosmetic, though: the smallest pivot falls as the square of the level and crosses this solver's threshold at 696 kΩ, above which the same filter has no answer at all. — Fig. 5 One fifth-order Chebyshev ladder written at eight impedance levels from 10 Ω to 400 kΩ, all measured at 964 Hz. The condition number runs from 1.838×10³ to 2.535×10¹² — a factor of 1.4×10⁹ — and the response is 0.438134764076 at every one of them. Equilibrated, all eight sit between 51.179 and 51.612.

Multiplying every resistance by a factor and dividing every capacitance by it produces the same filter, exactly: the same poles, the same response, the same everything a reader of the schematic would care about, which is the subject the same filter a thousand times larger is written about from the design side.

Its condition number changes by 1.4×10⁹.

Its answer does not change at all. The response is 0.438134764076 at 10 Ω, at 1 kΩ and at 400 kΩ, and the largest disagreement between the double-precision solve and a thirty-one-digit one is 12.3 units of round-off at any level on the axis. Equilibrated, the eight matrices differ by 0.85 per cent — which is the correct answer, because they are one network.

So the condition number of a nodal matrix is very nearly a measurement of the engineer’s choice of impedance level. Quoting it as a property of the circuit is the same error as quoting a resistance in ohms and calling it a shape.

The vector is exact and the answer taken out of it is not

None of the above says the arithmetic is safe, and the way it is not safe has nothing to do with any of the three terms.

The passband agreement is the calibration and it comes before the finding, for the reason every two-route measurement here does: two arithmetics that disagree by a decade somewhere are only attributable if there is a place they must agree. In the passband the response is of the same size as the vector it belongs to, and the two routes agree to 2.54×10⁻¹⁶ — two and a half units of round-off. That entitles the stopband number to be quoted.

The stopband number is four decades worse and the mechanism is arithmetic rather than numerical. A filter’s input node is one volt and its output node at ten times the cutoff is 6.78×10⁻⁷ of it. The vector’s error is a few round-offs of the vector’s largest component, which is the input; taken as a fraction of a component seven decades smaller, the same absolute error is 1.6×10⁻¹⁰. The measurement sits under that line at every frequency and never exceeds 1.78 times it.

Nothing has gone wrong. A well-solved vector has a small component in it and the small component is the answer, which is the same shape as the bridge in the rung below — a difference of two nearly equal numbers — arriving with no subtraction written anywhere, because the ladder does the cancellation on its own.

What κ·ε is worth, and what it is a property of

The condition number’s own bound holds at every point of every sweep here. It is also never approached, and by how much it is not approached turns out to depend on nothing about the network.

The vector is exact and the answer taken out of it is not. computed by solving, not by drawing. The same 5th-order ladder at 100 kΩ solved twice at every frequency — once in double precision, once in a pair of doubles carrying 31 decimal digits, sharing the netlist and the assembly and nothing else. The whole solution vector is right to 5 units of round-off at every point, and does not care what κ is doing. The response — one component of that vector — goes from 3.34e-16 in the passband to 1.34e-12 at 10000 Hz. Nothing has gone wrong with the solve: a filter's output node is small while its input node is one, so the error the vector carries as a whole is a large fraction of the component being read. The line over the measurements is the round-off divided by the response, and no point exceeds 2.20 times it anywhere on the axis. The condition number's own bound κ·ε holds and is never approached: it is 3.00e-5 at 10000 Hz against 1.34e-12 measured, a factor of 2.2e+7 — and that factor is a property of the impedance level the ladder was written at rather than of the ladder, because κ bounds the vector and the vector is exact. — Fig. 7 The identical measurement on the identical filter written at 100 kΩ instead of 1 kΩ. κ is now 2.702×10¹¹ rather than 2.702×10⁷ and κ·ε at 10 kHz is 3.00×10⁻⁵ against a measured 1.34×10⁻¹²; at 50 Ω the same bound is 7.66×10⁻¹² against 6.69×10⁻¹³. The error itself has barely moved.

At 50 Ω the classical bound over-predicts the loss by a factor of 11. At 1 kΩ by 2.8×10³. At 100 kΩ by 2.2×10⁷. The measured error is 6.69×10⁻¹³, 1.06×10⁻¹² and 1.34×10⁻¹² — the same number three times, at three condition numbers seven decades apart.

So $\kappa\varepsilon$ is not a bad bound. It is a correct bound on a quantity nobody asked about — the solution vector, which is exact — and its slack is a measurement of the units. The number that does predict the loss is the round-off divided by the response, which contains no matrix at all.

This is the same verdict the answer that is perfect and absurd reached from the other side: a solver’s diagnostics answer whether the matrix determines its unknowns, which is a different question from whether the unknown being read is worth reading.

The edge, which is a size

The refusal is not cosmetic and it is on the same axis.

This solver declines a network whose smallest pivot has fallen below a part in $10^{12}$ of the matrix norm. On a ladder that pivot ratio falls as the square of the impedance level — 4.84×10⁻⁷ at 1 kΩ, 4.84×10⁻⁹ at 10 kΩ, 4.84×10⁻¹¹ at 100 kΩ — and crosses the threshold at 696 kΩ, located by bisection on the level rather than extrapolated from the slope.

Above that, the same fifth-order Chebyshev has no answer at all. Its response is unchanged, its poles are unchanged, the components are ones that can be bought, and a 700 kΩ termination is an entirely ordinary thing to build a filter around. What has failed is not the filter but the arithmetic’s ability to be handed it in those units — which is what makes this an edge of the kind every model has an edge collects, and an unusual one, because its axis is neither a frequency nor an amplitude but an impedance level.

The practical consequence is one line: scale a network to a kilohm before solving it, and the seven decades of condition number and the refusal both go away.

That line is worth one more sentence of care, because it is a statement about the solver and not about the design. Nothing says a 700 kΩ ladder is a bad filter; the components exist, the response is the designed one, and a solve at a kilohm followed by a scaling of the answer gives every number a designer wants. What the threshold is protecting against is a matrix in which the pivot the elimination reaches for has become indistinguishable from the entries it is eliminating against, and on a nodal matrix that happens for a reason that has nothing to do with whether the network determines its own node voltages — which it does, at 700 kΩ, as certainly as it does at ten ohms. A refusal that fires on units is a refusal that will one day decline something real, and the way to stop it is to normalise the network before handing it over rather than to loosen the threshold.

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. 8 The rung below’s other network, which meets the same threshold from the other direction: a feedback amplifier the solver refuses at a gain of 10⁹, one decade after returning an answer exact to the last bit. The refusal is a test of the matrix and the exactness is a property of the quantity.

What it does not say

It does not say a condition number is useless. It says it is a property of a matrix rather than of a network, and a matrix is a network plus a choice of units and a choice of unknowns. Equilibrated, it is a real quantity with a real shape — a band-edge maximum of 50.45 riding on a monotone fall from 337.5 to 9.25 — and that shape is worth having.

It does not say the double-double result generalises. Every measurement here is on a doubly terminated Chebyshev ladder, whose termination the two resistors a ladder was designed between shows is what makes its passband maxima structural; a network whose output node is not small compared with its input — an amplifier, or the loaded divider of the divider and its load — has no cancellation of this kind and loses nothing in a stopband it does not have.

And it does not overturn the rung below. That essay’s verdict on the ladder synthesis — the floor that outlives the arithmetic is where it lands — was that the loss belongs to the data rather than to the arithmetic, and nothing here touches it. The synthesis works on polynomials and this works on matrices, and the two failures are unrelated in everything but the word.

The one thing it does bear on is the habit that produced it. A ladder’s sensitivity apparatus, measured in the direction a response is most sensitive to, takes derivatives of solves at frequencies scattered through the passband — including at the band edge, where $\kappa$ is at its worst. Those derivatives agree between two routes that share no arithmetic, to seven decimal figures, which is exactly the evidence this essay says $\kappa$ could not have given.

The number worth carrying

A ladder’s nodal matrix is worst conditioned at its band edge, which is a place the response has no feature at, and the number there is 1.59×10⁷. The same filter written at 400 kΩ instead of 10 Ω has a condition number 1.4×10⁹ times larger and gives twelve identical digits. The residual falls where the condition number rises. The elimination never creates an entry a tenth the size of the one it started with. And the actual loss — four decades of it, into the stopband — is predicted by none of the three and by one quantity that mentions no matrix: the round-off divided by the response.

The habit that goes with it is the same one one step computed twice applies to a transient. A diagnostic that has never been swept along the axis the subject is organised around has not been tested; it has been quoted. Sweeping it costs one loop, and the first thing it usually reveals is what the number is a property of.

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