Numerical Linear Algebra
where the algebra stops being the arithmetic
Structure, and the solver that cannot see it

The condition number of the model

Describe a 40×40 Toeplitz matrix by its 1,600 entries and its condition number is 78,800. Describe it by the one number it actually contains and the condition number is 61.9. The three decades in between are not an approximation or a bound — they are what κ has been over-stating, and the drop is not where the linear algebra is.
27 min read 22 figures Whose fault is itMeasured, not assertedTwo routes to a numberWhere the algebra stops being the arithmetic

Worth reading first: A nearby problem of the wrong kind · A limit the matrix never reaches · The condition number is an amplifier.

A condition number answers a question of the form: if the data moves by this much, how much can the answer move? The answer depends on what “the data” is allowed to be, and κ(A) makes one particular choice — the data is all n² entries and they may move independently.

For a Toeplitz matrix that is the wrong choice, and this essay measures how wrong.

One 40×40 matrix described four ways, with its condition number and its backward error at eachThe matrix is ρ^|i−j| at ρ = 0.999, where κ = 7.878·10⁴. Described as n² entries its condition number is that; as 79 constant diagonals it is 3.301·10⁴; as the 40 a symmetric Toeplitz matrix has, 3.178·10⁴; and as the one number ρ that the matrix actually holds, 61.88. The backward error of the same computed solution runs the other way — 2.01·10⁻¹⁷, 1.15·10⁻¹⁴, 5.62·10⁻¹² — and at the last rung there is none: no ρ whatever has the computed answer as its exact solution, and the closest one leaves 99 per cent of the residual unexplained. The drop that matters is the last one, and it is not a linear-algebra structure at all.110¹10²10³10⁻¹⁸10⁻¹⁴10⁻¹⁰10⁻⁶10⁻²10²10⁶numbers that describe the matrixcondition number, and backward errordensetoeplitzsymmetricρ aloneno such problemcondition numberbackward errorone matrix, four descriptionsκ, all n² entries7.9·10⁴as one number, ρ62backward error, unconstrained2·10⁻¹⁷as a symmetric Toeplitz matrix5.6·10⁻¹²fewer numbers, better conditionedand no nearby problem left
Fig. 1 One matrix described four ways. The condition number falls as the description shrinks; the backward error rises; and the last rung’s backward error is not a number.

The ladder

Take the same 40×40 Kac–Murdock–Szegő matrix as the previous essay, at ρ = 0.999, where κ = 7.88·10⁴. It can be described at four levels of tightness, each a subset of the one above.

As 1,600 entries. Every entry independent. This is what κ assumes.

As 79 constant diagonals. A general Toeplitz matrix, 2n − 1 numbers.

As 40 numbers. A symmetric Toeplitz matrix, which is what this one is.

As one number. ρ, which is the whole content of ρ^|i−j|.

Both quantities are monotone along that ladder by construction — a smaller set of perturbations can do less damage and can explain less — so the interesting question is not the direction but where along the ladder each of them moves.

The condition numbers

1,600 entries 78,800 79 diagonals 33,000 40 numbers 31,800 one number 61.9

Two facts, and the second is the one worth having.

Constant diagonals buy a factor of 2.5. Going from “any perturbation” to “a Toeplitz perturbation” — which is the structural restriction the whole subject is named after — takes the condition number from 78,800 to 33,000. Imposing the symmetry as well takes it to 31,800, which is nothing.

The last rung buys three decades. From 31,800 to 61.9, a factor of 513, for the step from “forty numbers” to “one number”.

One 40×40 matrix described four ways, with its condition number and its backward error at eachThe matrix is ρ^|i−j| at ρ = 0.9, where κ = 284.2. Described as n² entries its condition number is that; as 79 constant diagonals it is 145.9; as the 40 a symmetric Toeplitz matrix has, 140.5; and as the one number ρ that the matrix actually holds, 1.65. The backward error of the same computed solution runs the other way — 1.84·10⁻¹⁷, 7.29·10⁻¹⁵, 8.74·10⁻¹⁴ — and at the last rung there is none: no ρ whatever has the computed answer as its exact solution, and the closest one leaves 100 per cent of the residual unexplained. The drop that matters is the last one, and it is not a linear-algebra structure at all.110¹10²10³10⁻¹⁸10⁻¹⁴10⁻¹⁰10⁻⁶10⁻²10²10⁶numbers that describe the matrixcondition number, and backward errordensetoeplitzsymmetricρ aloneno such problemcondition numberbackward errorone matrix, four descriptionsκ, all n² entries348as one number, ρ1.7backward error, unconstrained1.8·10⁻¹⁷as a symmetric Toeplitz matrix8.7·10⁻¹⁴fewer numbers, better conditionedand no nearby problem left
Fig. 2 At ρ = 0.9, where κ is smaller and the shape of the ladder is identical.
One 40×40 matrix described four ways, with its condition number and its backward error at eachThe matrix is ρ^|i−j| at ρ = 0.9999, where κ = 7.977·10⁵. Described as n² entries its condition number is that; as 79 constant diagonals it is 3.343·10⁵; as the 40 a symmetric Toeplitz matrix has, 3.218·10⁵; and as the one number ρ that the matrix actually holds, 613.2. The backward error of the same computed solution runs the other way — 1.56·10⁻¹⁷, 7.49·10⁻¹⁵, 1.5·10⁻¹¹ — and at the last rung there is none: no ρ whatever has the computed answer as its exact solution, and the closest one leaves 100 per cent of the residual unexplained. The drop that matters is the last one, and it is not a linear-algebra structure at all.110¹10²10³10⁻¹⁸10⁻¹⁴10⁻¹⁰10⁻⁶10⁻²10²10⁶numbers that describe the matrixcondition number, and backward errordensetoeplitzsymmetricρ aloneno such problemcondition numberbackward errorone matrix, four descriptionsκ, all n² entries8·10⁵as one number, ρ613backward error, unconstrained1.6·10⁻¹⁷as a symmetric Toeplitz matrix1.5·10⁻¹¹fewer numbers, better conditionedand no nearby problem left
Fig. 3 And at ρ = 0.9999. Pushing the family towards its singular limit moves κ by decades and moves the shape of the ladder not at all.

That the shape does not move is what makes it a finding rather than a coincidence. Across the whole family the first two rungs are worth a factor of about two and the last is worth three decades, and the ratio between the first rung and the third stays at 0.40 at every ρ from 0.5 to 0.999.

κ of the ρ = 0.9 Toeplitz family, against the limit it never reachesThe condition number of the n×n section of the Kac–Murdock–Szegő matrix ρ^|i−j| at ρ = 0.9, plotted against the size on logarithmic axes, with Szegő's asymptotic value ((1+ρ)/(1−ρ))² = 361 drawn as a horizontal line. The measured curve climbs towards it from below and reaches 96.0% of it at n = 128.10¹10²10²size ncondition numberlimit 361measureda limit, as a fraction of itselfreached at n = 1280.96still to go0.04κ at n = 8, as a fraction0.31every point is below the line and none of them is on itthe limit is not a value
Fig. 4 The family’s κ approaching a limit from below, which is the axis all of the above sits on.

Which is the wrong place for the drop to be

The natural expectation is that the structural restriction — the constant diagonals — is where the benefit lives. It is the restriction a numerical analyst would name, it is the one that defines the class of matrix, and it is the one that buys the fast algorithm.

It buys a factor of two and a half in the conditioning.

The restriction that buys three decades is the one a modeller would name: the matrix is not “a Toeplitz matrix”, it is “ρ to the power of the separation”, and the thing that could be wrong about it is ρ. That is not a linear-algebra structure at all. It is a statement about where the numbers came from.

There is a version of this that everybody already knows and does not connect: the condition number of a matrix depends on the units its rows and columns are measured in, and equilibrating changes it by decades. That is the same observation — a change of units is a restriction of the perturbations to those that respect the units — and this collection has an essay on it, and a second on the componentwise condition number that scaling cannot move.

What this ladder adds is that the sequence continues past scaling. Units are one restriction; the structure is another; the parametrisation is a third; and the last one is worth more than the two before it put together.

Two condition numbers of one 8×8 system, as its rows are put into different unitsFour curves against the spread of the row units, in decades. κ_∞ of the scaled matrix rises from 9.83 to 1.9·10¹⁰ while the componentwise condition number stays at 6.98 throughout — the same system, the same solution, and one of the two numbers is a fact about the units. Hilbert's two numbers are drawn flat beside them at 3.4·10¹⁰ and 1.2·10¹⁰: a matrix whose sensitivity no scaling repairs.0246810110²10⁴10⁶10⁸10¹⁰10¹²spread of the row units (decades)condition numberκ_∞(DA)cond(DA)Hilbert κ_∞Hilbert condone system, two numbersκ_∞ at no spread9.8κ_∞ at 10 decades1.9·10¹⁰cond, either end7Hilbert, equilibrated1.3·10¹⁰the solution is the same at every spreadand one of these curves knows it
Fig. 5 The units doing that work, from the scaling field: the same matrix and the same answer, and a condition number that moves by decades.
Two perturbation bounds and the error that was measured, on a 12×12 matrix spread over 8 decades of unitsThree curves against the size of an entrywise relative perturbation. The normwise bound κ_∞·ε is a valid bound and sits 3.7·10⁷ times above the componentwise one cond(A, x)·ε, which is also a bound and is nearly attained by the worst of forty random perturbations at each size.10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1relative size of the entrywise perturbationrelative forward errorκ_∞ · εcond(A,x) · εmeasuredboth bounds holdκ_∞(A)3.1·10⁸cond(A, x)8.5ratio of the bounds3.7·10⁷both curves above the data are boundsand only one of them is a measurement
Fig. 6 And the condition number that does not move under a change of units, because the two diagonal factors cancel entry by entry.

How the structured number is computed

It is worth writing out, because the definition is the whole of why the answer means what it means.

The solution of Ax = b is a function of A. Restrict A to move only within a set of admissible perturbations — a linear space, spanned by matrices E₁ … E_p — and the derivative of x in the direction E_k is −A⁻¹E_k x. Assemble those p vectors as the columns of a matrix, weight each so that a unit coefficient corresponds to a unit change in ‖ΔA‖, and the largest amplification any admissible perturbation can produce is the 2-norm of what results.

Multiply by ‖A‖ and divide by ‖x‖ and it is a relative-to-relative number, comparable with κ.

Three consequences fall straight out.

With no restriction it is κ. If the admissible set is everything, the assembled matrix is A⁻¹ times an isometry and its norm is ‖A⁻¹‖, so the whole expression is ‖A‖‖A⁻¹‖. That is the top rung and it is a check on the machinery rather than a result.

It depends on b. Unlike κ, the structured condition number is a property of the system and not of the matrix alone, because the derivative involves x. That is not a defect: a restricted perturbation does its damage in specific directions, and whether those directions matter depends on where the answer is.

And it is a supremum that is attained. The direction achieving it is the leading singular vector of the assembled matrix, which means the number is a worst case that can be exhibited rather than a bound. Every claim above about what κ over-states is a claim about a perturbation somebody could construct.

How much a perturbation of the right-hand side is amplified, κ = 10⁶The cumulative distribution of the amplification factor over two hundred random perturbation directions, with the condition number marked as the upper limit.110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ
Fig. 7 The unrestricted version of the same supremum, drawn in the error field.

And the backward error runs the other way

The same ladder, with the previous essay’s quantity on it:

1,600 entries 2.0·10⁻¹⁷ 79 diagonals 1.15·10⁻¹⁴ 40 numbers 5.6·10⁻¹² one number none

Restricting the perturbations makes the problem better conditioned and makes the backward error worse, and at the bottom rung the backward error is not merely worse — there is no perturbation of the model that explains the computed answer at all.

That is a trade with no free end, and it is worth stating in the form a reader can use.

Describing a problem more tightly is a claim about what can vary. The reward is that less can go wrong: the answer is less sensitive because fewer things are allowed to move. The price is that fewer things being allowed to move makes it harder for anything to explain a computed answer, and past some point nothing does.

Both halves are the same statement about the same set, read from two directions. The set of admissible perturbations is small; a small set contains no large damage, and it also contains no explanation.

Backward error with and without the structure, for Levinson and for elimination, n = 12Both solvers are backward stable on this family by the usual measure: the smallest perturbation of any kind that explains either answer stays below 3.1·10⁻¹⁷ at every ρ, and the two curves are indistinguishable. Insisting the perturbation be a symmetric Toeplitz matrix — the kind of object the problem was posed with — lifts both by orders, and at ρ = 0.999 Levinson's rises by a factor of 2.48·10⁶. Neither number is alarming in absolute terms; what is worth carrying is that the reassuring one is the one that is reported, and the two are not measuring the same thing.10⁻³10⁻²10⁻¹110⁻¹⁹10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹1 − ρbackward errorLevinson, Toeplitzelimination, ToeplitzLevinson, any kindelimination, any kindat ρ = 0.999Levinson, any perturbation3.1·10⁻¹⁷Levinson, Toeplitz only7.6·10⁻¹¹the ratio between them2.5·10⁶diagonal defect of the first0.97the number that is reportedand the number that is asked about
Fig. 8 The backward-error half measured along the family rather than along the ladder, from the previous essay.
The two perturbations that make one computed solution exact, on a 12×12 Toeplitz systemA Kac–Murdock–Szegő matrix at ρ = 0.95, solved by Levinson's recursion. Every backward-error claim on this site says the computed answer solves a nearby problem exactly, and the nearby problem is the top matrix: the smallest perturbation of any kind, 2.18·10⁻¹⁷ relative, rank one, and constant along 0.98 of the way to none of its diagonals. The bottom matrix is the smallest perturbation that is itself a symmetric Toeplitz matrix — the same kind of object the problem was posed with — and it is 3.72·10⁻¹², larger by a factor of 1.71·10⁵. Both explain the same computed answer exactly. Only one of them is a problem anybody could have posed.the smallest perturbation of any kind — 2.18·10⁻¹⁷the smallest Toeplitz one — 3.72·10⁻¹²both exact for the same x̂smallest of any kind2.2·10⁻¹⁷smallest Toeplitz one3.7·10⁻¹²the price of the constraint1.7·10⁵diagonal defect, unconstrained0.98an exact answer to a nearby problemof a kind nobody posed
Fig. 9 And what the two perturbations look like as matrices, which is where the difference between them is visible rather than numerical.

What the last rung means in practice

The one-parameter rung is not an abstraction. A great many matrices in computation are one or two numbers wide.

A Kac–Murdock–Szegő matrix is a correlation length. A discretised Laplacian is a grid spacing. A convection–diffusion stencil is a Péclet number. A Tikhonov-regularised system is a regularisation parameter and the original data. A finite-element mass matrix is a density and a mesh. In all of these the entries are computed from a handful of numbers by a formula, and the entries cannot move independently because nothing that produced them can move them independently.

So the useful question for such a matrix is not what κ says. It is: how sensitive is the answer to the numbers the model actually contains? That is a derivative with respect to a parameter, it costs one solve per parameter, and for a one-parameter family it costs one solve.

At ρ = 0.999 it comes out at 61.9. The answer to a system whose condition number is 78,800 is sensitive to the number the matrix is made of at the level of two significant figures lost, not five.

−εu″ + u′ = 0 on 31 points, ε = 0.01, cell Péclet 1.563Three solutions of a boundary-layer problem on the same grid. The exact one rises monotonically from 0 to 1 with a layer of width ε at the right-hand end. The central-difference answer alternates at every point and leaves [0, 1] at 11 of the 31 of them, by as much as 0.2195. The upwind answer is monotone at every Pe.00.250.50.75100.250.50.751xuexactcentral differencesupwindthe oscillation is exact‖Ax − b‖/‖b‖ for the central answer1.2·10⁻¹⁶values outside [0, 1]11worst excursion0.22the dashed lines are 0 and 1, which the equation guaranteesno solver was involved
Fig. 10 One of those parameters in the field where it decides everything, from the convection essays.
Two filters on one sum, λ = 0.01The weight each term of the solution is given, against its index. Truncation is a step: one for the first 26 terms and zero after. Tikhonov is σ²/(σ² + λ²), which falls smoothly through the same place. The unregularised solution is the constant one, which is why it divides noise by a σ of 1.7·10⁻¹³.081624324048566400.250.50.751index kfilter factor fₖno regularisation: fₖ = 1truncationTikhonovthe same sum, three weightsTikhonov, relative error0.11truncation, relative error0.11no filter at all5.5·10⁸both filters are one expression with a different weightfₖ = 1 is the catastrophe
Fig. 11 And another, from regularisation: a single number that decides which components of an answer survive.
The L-curve, and where four rules put λThe norm of the solution against the norm of its residual, on logarithmic axes, as λ sweeps eight decades. The curve has a corner: to the left of it the noise is being amplified and to the right the signal is being thrown away. Four points are marked — the three rules that use only the data, and the oracle, which requires the exact answer and is not a method.10⁻²10⁻¹110¹10²10³10⁴‖Ax − b‖‖x‖the oraclediscrepancyL-curvegeneralisedscored against a truth none hasoracle, relative error0.11discrepancy principle, as a multiple1.1L-curve corner, as a multiple2.3generalised cross-validation, as a multiple1the oracle needs the exact answer and is not a methodit is the reference the others are scored on
Fig. 12 And the published rules for choosing it, scored against a truth that exists because the problem was constructed.

The ladder is not always this shape

One measurement is worth adding because it bounds the finding rather than extending it.

Along the whole family — ρ from 0.5 to 0.999, κ from 8.9 to 78,800 — the ratio between the structured condition number at the symmetric-Toeplitz rung and κ is 0.40, and it does not move. Four decades of conditioning, and the benefit of the constant diagonals is the same 40 per cent throughout.

That is a negative result about a hope this essay could have been written to support: the idea that structure is worth more as the problem gets harder. On this family it is worth exactly as much at κ = 9 as at κ = 78,800, which means the structural restriction is not fighting the ill-conditioning at all. It is removing a fixed fraction of a fixed kind of damage.

The last rung is different: the factor of 513 there does grow with ρ, because what it removes is precisely the near-singular direction the family is heading towards. That is the difference between a restriction that happens to exclude some perturbations and one that excludes the perturbations that matter, and it is only visible by sweeping.

The spectrum of C⁻¹T against T's own, n = 64, ρ = 0.8Two sorted spectra on a linear vertical axis. The unpreconditioned Toeplitz matrix spreads its eigenvalues across its whole range; the preconditioned operator puts 97% of them within a tenth of 1, with 0 below zero.08162432404856640123456789index, sortedeigenvalueT aloneC⁻¹Teigenvalues, not singular valuesfraction within 0.1 of 10.97eigenvalues below zero0λ_min of the preconditioner0.11the dashed line is 1, where the cluster formsthe solid line is zero
Fig. 13 The other thing the structure buys, which is genuinely worth more as the problem grows: a spectrum a preconditioner can cluster.
Conjugate gradient steps on the ρ = 0.9 Toeplitz familyIteration count against the matrix size, drawn on a logarithmic size axis. Unpreconditioned: 20, 35, 54, 82, 117. With the wrapped circulant: 20, 45, 26, 7, 4. With the averaged one: 7, 9, 10, 10, 9, which is the O(1) the theory promises and the wrapped one does not deliver until its smallest eigenvalue has become positive.10²020406080100120size niterationsno preconditionerwrapped (Strang)averaged (T. Chan)both are circulant approximations‖C − T‖/‖T‖, averaged0.21‖C − T‖/‖T‖, wrapped0.29smallest eigenvalue, wrapped, n = 16-0.4one of them is positive definiteand it is the one that is nearer
Fig. 14 And the two circulant preconditioners this collection compared, which is the structure being used for the purpose it is best at.

The caution, which is large

Everything above says κ over-states the danger. It over-states it only for the perturbations the restriction excludes, and there is one source of perturbation that respects no restriction at all.

Rounding error is not structured. When a solver forms a quantity from the entries of a Toeplitz matrix, the errors it makes are independent per operation, and the perturbation they correspond to is a general matrix. That is precisely the previous essay’s finding read from this side: the explaining perturbation is not Toeplitz because the arithmetic that produced it does not know the matrix is.

So the two halves of this pair say something more precise together than either says alone.

If the uncertainty in the data is structured — a mis-measured ρ, a mesh spacing known to three digits, a correlation length estimated from data — then the structured condition number is the right number and κ is over-stating by three decades.

If the uncertainty is the arithmetic — rounding, an approximate solve, a truncated iteration — then it is unstructured, κ is the right number, and the structured one is a statement about a kind of error that is not occurring.

Most real problems have both, in unknown proportion, which is the honest end of this. What can be said is that computing only κ answers the second question and is routinely quoted as though it answered the first.

How much a perturbation of the right-hand side is amplified, κ = 10¹⁰The cumulative distribution of the amplification factor over two hundred random perturbation directions, with the condition number marked as the upper limit.110¹10²10³10⁴10⁵10⁶10⁷10⁸10⁹10¹⁰10¹¹10¹²00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10¹⁰worst found 7.6·10⁹6×6, 200 directionsmedian reaches 0.29 of κ
Fig. 15 The quantity being over-stated, and what it is for: an amplifier, applied to whatever the algorithm’s own error happened to be.
Backward error, forward error and the condition number, with measured valuesTwo boxes at the top — the problem posed and the nearby problem the algorithm answered exactly — and two answers below them, with the distances between all four labelled by numbers from a Hilbert solve.the problem you posedA = H12b = A·(1, 2, …, 12)the problem it answered exactlyA + δA, b + δb‖δ‖ / ‖A‖ = 1.8·10⁻¹⁷the answer you wantedx = (1, 2, …, 12), exactlythe answer you gotx̂, wrong by 0.02 relativebackward error 1.8·10⁻¹⁷forward error 0.02κ = 1.8·10¹⁶κ · η = 0.33, and the measured forward error is 0.02.The algorithm is not at fault. The problem is.H12, LU with partial pivotingresidual and error differ
Fig. 16 And the identity it sits in, which is where the two kinds of uncertainty above enter separately.

One number a modeller could ask for

If only one thing came out of this pair it would be a quantity worth naming, because it has no name and it is one solve.

For a matrix generated from parameters θ by a formula, the parameter sensitivity of the answer is

‖A‖ · ‖A⁻¹ (∂A/∂θ) x‖ ⁄ (‖∂A/∂θ‖ ‖x‖)

which is one derivative, one solve, and two norms. For a one-parameter family it is a scalar. For a handful of parameters it is a small matrix whose largest singular value is the worst case and whose singular vectors say which combination of the parameters the answer is sensitive to — which is information κ cannot carry at all, because κ has no parameters in it.

That last part is the reason to bother. A modeller told “κ is 10⁵” learns that the problem is hard. A modeller told “the answer moves by 62 units per unit of relative change in ρ, and by nothing in the other three parameters” learns which measurement to go back and improve.

It is the same distinction this collection drew between a normwise and a componentwise condition number, one level further out: the normwise number describes the matrix, the componentwise one describes the entries, and this one describes the model.

Two perturbation bounds and the error that was measured, on a 8×8 matrix spread over 0 decades of unitsThree curves against the size of an entrywise relative perturbation. The normwise bound κ_∞·ε is a valid bound and sits 2.1 times above the componentwise one cond(A, x)·ε, which is also a bound and is nearly attained by the worst of forty random perturbations at each size.10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻¹⁵10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷relative size of the entrywise perturbationrelative forward errorκ_∞ · εcond(A,x) · εmeasuredboth bounds holdκ_∞(A)9.8cond(A, x)4.8ratio of the bounds2.1both curves above the data are boundsand only one of them is a measurement
Fig. 17 The middle member of that sequence, from the scaling field, where the entries rather than the matrix are what is allowed to move.

Two routes to the ladder

The condition numbers here are computed as norms of a Jacobian: the derivative of the solution with respect to each admissible perturbation direction, assembled into a matrix and measured. The backward errors are computed as constrained minimisations over the same directions. The two use the same basis and nothing else in common, and they are dual — one is the largest damage a unit perturbation can do, the other is the smallest perturbation that does a given damage.

They can be checked against each other at the ends. At the dense rung the condition number must equal ‖A‖‖A⁻¹‖ and the backward error must equal Rigal and Gaches’s ‖r‖/(‖A‖‖x̂‖), both of which have closed forms, and both agree to the last digits. At the one-parameter rung the backward error must be infeasible whenever the residual has a component outside a one-dimensional subspace, which is what the feasibility check reports.

A ladder whose ends are pinned by closed forms is a ladder whose middle is worth reading.

The exact solution of a 13×13 Hilbert system beside the computed oneTwo columns of numbers: the exact answer, which is the integers one to thirteen, and the answer double-precision elimination returns, with the number of correct digits beside each.H13 x = b, b formed exactly so that x = (1, 2, …, 13)12345678910111213exact1.00002.00003.00133.97865.18864.993010.46720.048921.2657-2.575319.21478.906013.5113computed6.6 correct digits4.8 correct digits3.4 correct digits2.3 correct digits1.4 correct digit0.8 correct digitno correct digitsno correct digitsno correct digitsno correct digitsno correct digits0.6 correct digit1.4 correct digitbackward error2.2·10⁻¹⁷κ = 1.7·10¹⁸The algorithm solved a neighbouring problem perfectly. That problem's answer is this one.right-hand side built in BigInt rationalsthe truth is known
Fig. 18 The site’s standing requirement, in its original form.
The smallest eigenvalue of each circulant, ρ = 0.95Smallest eigenvalue against the matrix size on a linear vertical axis with zero marked. The wrapped circulant runs -0.6548, -0.4258, -0.1730, -0.0128, 0.0242 — negative at the small sizes and crossing zero by n = 256. The averaged one runs 0.0431, 0.0382, 0.0332, 0.0295, 0.0276: falling towards zero and never reaching it.10²0size nsmallest eigenvaluezerowrapped (Strang)averaged (T. Chan)an average of positives is positivewrapped, n = 16-0.65averaged, n = 160.043averaged, n = 2560.028a choice between two diagonals can be negativean average of them cannot
Fig. 19 And the structure field’s own closed form, which is what made this family the one to use.

The refusal

The assertion is fed the one-parameter basis asked for without its parameter.

The basis at that rung is the single matrix dA/dρ, whose entries are |i − j|·ρ^(|i−j|−1), and it is not defined without ρ. The tempting behaviour is to return a zero matrix and carry on, which produces a perturbation set containing nothing — and a perturbation set containing nothing has a condition number of zero and a backward error of infinity, both of which look like this essay’s findings taken to their limit and neither of which is a fact about any matrix.

That is the failure worth guarding here rather than anywhere else, because the finding at that rung is already that the condition number is small and the backward error is absent. A bug that produced the same shape would be indistinguishable from the result.

One 40×40 matrix described four ways, with its condition number and its backward error at eachThe matrix is ρ^|i−j| at ρ = 0.99, where κ = 6988. Described as n² entries its condition number is that; as 79 constant diagonals it is 2939; as the 40 a symmetric Toeplitz matrix has, 2829; and as the one number ρ that the matrix actually holds, 6.798. The backward error of the same computed solution runs the other way — 4.53·10⁻¹⁷, 2.56·10⁻¹⁴, 7.51·10⁻¹³ — and at the last rung there is none: no ρ whatever has the computed answer as its exact solution, and the closest one leaves 100 per cent of the residual unexplained. The drop that matters is the last one, and it is not a linear-algebra structure at all.110¹10²10³10⁻¹⁸10⁻¹⁴10⁻¹⁰10⁻⁶10⁻²10²10⁶numbers that describe the matrixcondition number, and backward errordensetoeplitzsymmetricρ aloneno such problemcondition numberbackward errorone matrix, four descriptionsκ, all n² entries7012as one number, ρ6.8backward error, unconstrained4.5·10⁻¹⁷as a symmetric Toeplitz matrix7.5·10⁻¹³fewer numbers, better conditionedand no nearby problem left
Fig. 20 At ρ = 0.99 the ladder has the same two rungs doing the work and the same one doing almost none.
The two perturbations that make one computed solution exact, on a 10×10 Toeplitz systemA Kac–Murdock–Szegő matrix at ρ = 0.9, solved by Levinson's recursion. Every backward-error claim on this site says the computed answer solves a nearby problem exactly, and the nearby problem is the top matrix: the smallest perturbation of any kind, 1.72·10⁻¹⁷ relative, rank one, and constant along 0.88 of the way to none of its diagonals. The bottom matrix is the smallest perturbation that is itself a symmetric Toeplitz matrix — the same kind of object the problem was posed with — and it is 1.01·10⁻¹³, larger by a factor of 5834. Both explain the same computed answer exactly. Only one of them is a problem anybody could have posed.the smallest perturbation of any kind — 1.72·10⁻¹⁷the smallest Toeplitz one — 1.01·10⁻¹³both exact for the same x̂smallest of any kind1.7·10⁻¹⁷smallest Toeplitz one10⁻¹³the price of the constraint5834diagonal defect, unconstrained0.88an exact answer to a nearby problemof a kind nobody posed
Fig. 21 And the objects the backward-error half of the ladder is measuring, drawn.
One 40×40 matrix described four ways, with its condition number and its backward error at eachThe matrix is ρ^|i−j| at ρ = 0.9999, where κ = 7.977·10⁵. Described as n² entries its condition number is that; as 79 constant diagonals it is 3.343·10⁵; as the 40 a symmetric Toeplitz matrix has, 3.218·10⁵; and as the one number ρ that the matrix actually holds, 613.2. The backward error of the same computed solution runs the other way — 1.56·10⁻¹⁷, 7.49·10⁻¹⁵, 1.5·10⁻¹¹ — and at the last rung there is none: no ρ whatever has the computed answer as its exact solution, and the closest one leaves 100 per cent of the residual unexplained. The drop that matters is the last one, and it is not a linear-algebra structure at all.110¹10²10³10⁻¹⁸10⁻¹⁴10⁻¹⁰10⁻⁶10⁻²10²10⁶numbers that describe the matrixcondition number, and backward errordensetoeplitzsymmetricρ aloneno such problemcondition numberbackward errorone matrix, four descriptionsκ, all n² entries8·10⁵as one number, ρ613backward error, unconstrained1.6·10⁻¹⁷as a symmetric Toeplitz matrix1.5·10⁻¹¹fewer numbers, better conditionedand no nearby problem left
Fig. 22 And at ρ = 0.9999, where κ has moved by a decade and the shape of the ladder has not.

What is next

Every zero in this collection’s current run so far has arrived on its own: a divisor going to zero, a curvature changing sign, an eigenvalue leaving for infinity, a determinant that was identically zero before anybody looked. The last two essays are about the other half, and it is the half a program actually contains — the zeros that are never met and are always written down, by somebody, in a comparison against a constant.

Where this goes next

the smallest perturbation of any kind — 1.89·10⁻¹⁷the smallest Toeplitz one — 2.65·10⁻¹³both exact for the same x̂smallest of any kind1.9·10⁻¹⁷smallest Toeplitz one2.7·10⁻¹³the price of the constraint1.4·10⁴diagonal defect, unconstrained0.97an exact answer to a nearby problemof a kind nobody posed A nearby problem of the wrong kind A good algorithm returns the exact answer to a nearby problem. A hundred and eighteen essays have measured the distance and not one has asked what the nearby problem looks like. On a Toeplitz system it is a rank-one matrix that is constant along none of its diagonals — and the smallest one that is Toeplitz is two and a half million times larger. 10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1relative size of the entrywise perturbationrelative forward errorκ_∞ · εcond(A,x) · εmeasuredboth bounds holdκ_∞(A)1.9·10⁸cond(A, x)4.8ratio of the bounds4·10⁷both curves above the data are boundsand only one of them is a measurement A condition number scaling cannot move Skeel's componentwise condition number is invariant under any row scaling — exactly, before any norm is taken, because two diagonal factors cancel entry by entry. It is never larger than the normwise one and can be arbitrarily smaller, and the ratio between them is a diagnostic for which kind of ill-conditioning a matrix has. 110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ The condition number is an amplifier κ is usually introduced as a definition and then quoted. It is a measurement: perturb the input by a known amount, look at how much the output moves, and the largest ratio you can find is the number.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Backward errorComponentwise condition numberCondition numberEquilibrationExact inverseParametrisationPerturbation theoryStructured perturbationToeplitz matrix