A perturbation that moves every coefficient

The backward error of a computed eigenpair of λ²M + λC + K is the smallest perturbation of the polynomial that makes the pair exact. Every published formula computes the same one:

η  =  ‖P(λ)x‖ ÷ ( (|λ|²‖M‖ + |λ|‖C‖ + ‖K‖) · ‖x‖ )

with the three coefficient norms in the denominator, added together. That number answers a specific question — how far is this from exact, if all three coefficients are equally open to being wrong — and it is the right question when all three are data.

They are frequently not all data.

Where the coefficients come from #

A quadratic eigenvalue problem from a damped structure has three matrices with three different histories.

The three coefficient norms are the same quantities the scaling essay moves apart, and their provenance differs.

M is a discretisation. It is known to whatever accuracy the mesh has, its entries are integrals of basis functions, and it is often exactly right in the sense that matters — a lumped mass matrix is a diagonal of known quantities.

K comes from measured material properties. Moduli, thicknesses, stiffnesses. It has real uncertainty in it, of a size somebody could state.

C is very often a model. Rayleigh damping sets C = αM + βK for two scalars chosen to match two observed decay rates. Modal damping assigns a ratio per mode. In neither case is C a measurement of anything; it is a device.

So asking “how far is the computed answer from exact under a perturbation of all three” prices a perturbation of C that nobody would accept as a description of the physics — the perturbed C would not be a Rayleigh damping matrix at all, and a nearby problem of the wrong kind is the essay about exactly that objection in the structured setting.

The restricted question is: how far from exact, if only the coefficient one is willing to move may move?

The ratio has a closed form and it is not a constant #

Charging the same residual to less data can only raise the quotient, so a restricted backward error is never smaller. How much larger has a closed form:

$$\frac{\eta_K}{\eta_{\text{all}}} = \frac{|\lambda|^2 \|M\| + |\lambda| \, \|C\| + \|K\|}{\|K\|}$$

which contains |λ|². So it is not a property of the polynomial — it is a different number at every eigenvalue.

Measured on an eight-mass overdamped chain, whose sixteen eigenvalues run from −0.01997 to −7.417 and whose coefficient norms are 2.83, 19.89 and 6.78:

restriction    factor at the smallest |λ|    at the largest
K only               1.059                       45.7
M only               1.99                     6,370

The K-only restriction costs six per cent at one end of the spectrum and a factor of forty-six at the other. The M-only restriction costs a factor of two at one end and three and a half orders at the other.

Sweeping the chain length shows one of those two factors is a property of the chain and the other is not.

The K-only ceiling is the same number at every size and the M-only ceiling is not. Across chains of 4, 6, 8, 10 and 14 masses the K-only factor’s maximum is 45.73, 45.73, 45.7, 45.64 and 45.56 — four significant figures, unmoved — while the M-only maximum runs 717.5, 2,449, 6,370, 1.385·10⁴ and 4.68·10⁴, growing by a factor of 65.

The closed form says why, and it is worth reading off it rather than fitting. The ratio is (|λ|²‖M‖ + |λ|‖C‖ + ‖K‖)/‖K‖ for K-only and the same numerator over |λ|²‖M‖ for M-only. The K-only ceiling is reached at the largest |λ|, where the numerator is dominated by |λ|²‖M‖ — and on this family the largest eigenvalue and the norms move together, so the quotient is pinned. The M-only ceiling is reached at the smallest |λ|, where the numerator is ‖K‖ and the denominator is |λ|²‖M‖, and the smallest eigenvalue of a longer chain goes to zero. So one restriction has a cost bounded independently of the problem’s size and the other has a cost that grows without limit — which is the practically useful form of “it is not a constant”, and is not visible at a single n.

Every one of those factors is checked against the two backward errors computed separately, and the closed form matches to 10⁻⁸ at every eigenvalue. It is a formula being verified rather than quoted.

The perturbation is built, not bounded #

A backward error formula is a ratio of two norms, and a ratio of two norms is a claim about a perturbation that exists. This field builds it.

For an allowed set of coefficients, the minimal perturbation puts

$$\Delta X = -\frac{\alpha_X}{d} \cdot \frac{r \, x^{\mathsf T}}{\|x\|^2}$$

with r the residual, α_X the coefficient’s weight and d the sum of the allowed weights. The perturbed polynomial then annihilates the pair exactly, and the library assembles it, evaluates it, and checks.

The check has a floor and the floor is instructive. Evaluating λ²Mx + λCx + Kx in binary64 commits a rounding of about u·(|λ|²‖M‖ + |λ|‖C‖ + ‖K‖)·‖x‖ — which is exactly the quantity the backward error divides by. So the residual of the perturbed polynomial cannot be driven below one unit roundoff’s worth of that denominator, and a check written as a ratio to the original residual reports 7.7·10⁻⁴ on a construction that is exact.

Measured against the floor instead, the worst case over thirty-six constructions — three restrictions on twelve pairs — is 0.34 floors. The construction is exact to the level at which its own correctness can be evaluated, which is the honest statement and is what the assertion checks.

That distinction is worth carrying. A verification whose tolerance is “zero” fails on every exact construction whose verification involves cancellation, and the useful tolerance is the arithmetic’s own resolution at that magnitude — which is computable rather than guessed.

Why the weights are the norms and not something else #

The denominator of the standard formula is a weighted sum of coefficient norms rather than a plain one, and the weights — |λ|², |λ|, 1 — are worth deriving rather than accepting, because the whole essay is about what happens when the sum is truncated.

The perturbed polynomial is (λ²(M + ΔM) + λ(C + ΔC) + (K + ΔK))x = 0, so the perturbations enter multiplied by λ², λ and 1 respectively. A perturbation of M of size δ therefore contributes |λ|²δ to the residual it can absorb; the same-sized perturbation of K contributes δ. So at a large eigenvalue, M is the coefficient with leverage, and at a small one it is K.

That is why the M-only ratio spans three and a half orders where the K-only one spans one and a half. The M-only ratio is (|λ|²‖M‖ + |λ|‖C‖ + ‖K‖)/(|λ|²‖M‖), which at the small end of the spectrum is dominated by ‖K‖/(|λ|²‖M‖) — a ratio of 6,370 when |λ| is 0.02. Restricting to a coefficient with no leverage at that eigenvalue is charging the residual to something that could barely have caused it.

The general rule, and it is the operational form of the whole essay: restrict to the coefficient that has leverage at the eigenvalue in question, or accept a factor. For the low modes of a damped structure that is K; for the high ones it is M; and a single restriction applied across a whole spectrum is the wrong restriction at one of its ends.

Where leverage changes hands #

That rule implies a threshold and does not name one, and the threshold has a closed form that this collection already has a name for. The two ratios are D/‖K‖ and D/(|λ|²‖M‖) for the same denominator D, so they are equal exactly when |λ|²‖M‖ = ‖K‖:

|λ|*  =  √(‖K‖ / ‖M‖)

which is γ, the scaling parameter the scaling essay uses to balance the outer coefficients. That is not a coincidence — balancing means γ²‖M‖ = ‖K‖, which is the same equation written for a different purpose. The number that balances the coefficients is the number at which leverage changes hands, and after scaling the crossover sits at |λ| = 1.

On the eight-mass chain ‖M‖ = 2.828 and ‖K‖ = 6.782, so γ = 1.5485 — and this spectrum has a gap exactly there:

Every eigenvalue below the gap prefers K, every one above prefers M, and the predicted crossover falls inside the empty band between them. The two groups an overdamped spectrum separates into are separated by the same number that decides which coefficient could have caused the residual — which is the tropical-root arithmetic of the scaling essay arriving in the backward-error field, from a different direction and about a different question.

And the penalty for choosing wrongly is not symmetric. At the smallest eigenvalue, restricting to M rather than K costs a factor of 6,014; at the largest, restricting to K rather than M costs 23. The expensive mistake is charging a residual to the coefficient with no leverage at the small end — which is the end a structural problem usually cares about, and the end where a single restriction chosen for the whole spectrum is most likely to be the wrong one.

There is a practical procedure in that, and it needs no eigenvalues to state. The three coefficient norms are computable before anything runs; γ is one square root of their ratio; and any eigenvalue a caller is interested in is either above or below it. So the choice of restriction is decidable in advance for a band of the spectrum, which is how a structural problem is usually posed — the lowest twenty modes, or everything under a cutoff frequency — rather than eigenvalue by eigenvalue.

The one case that needs care is a band straddling γ, and the table says what it costs: the ratios are smallest near the crossover, 2.65 and 2.23 on either side of the gap here, so a band containing γ is the band where either restriction is cheap. The rule is therefore easier than it looks. Restrict to K below γ, to M above it, and stop worrying near it — the region where the choice is difficult is the region where it does not matter, which is the reverse of the usual arrangement and worth having said.

The same answers, two verdicts #

A backward error is read against a tolerance. So the practical consequence of the ratios above is that one set of computed answers is accepted and rejected by two readings of the same number.

At a change of units of 10⁴, on the same sixteen pairs:

tolerance    stable, all three    without C    K only    M only
10⁻¹³             0                  0           0         0
10⁻¹¹             8                  7           0         7
10⁻⁹             16                 16          16        10

At 10⁻¹¹ eight pairs are stable under the whole polynomial and none is stable under K alone. At 10⁻⁹ every pair is stable under all three and under K alone, and six are not under M alone.

Nothing about the computation differs between the columns. The same eigenpairs, from the same linearisation, from the same run. What differs is which perturbations the reader is willing to accept as a description of the problem — a modelling decision — and it moves the verdict on half the spectrum.

Why the change of units does not change the ratio #

One measurement went the way it had to and is worth recording because it confirms the arithmetic rather than the modelling.

The scaling essay in this field is about a change of units γ that multiplies M by γ², C by γ and leaves K alone — which moves the coefficient norms apart by decades and is worth ten orders in the forward error of a badly scaled problem.

It does not move the ratio here at all. At γ = 1, 10² and 10⁴ the K-only factor spans 1.059 to 45.686 identically, to every digit. The reason is that the ratio is a quotient of weights, γ scales the weights and the eigenvalues in compensating ways, and the whole expression is invariant.

That is the right behaviour and it is a check on the measurement: a quantity that is supposed to be about the structure of the perturbation should not move when the units do. A condition number scaling cannot move is the essay about quantities that fail this test, and this one passes it.

What to report #

The restricted backward error is not a new quantity to compute — it is the standard one with a different denominator, so it costs a division. What it needs is a decision about what goes in the denominator, and that decision belongs to whoever knows where the matrices came from.

State the allowed set. “Backward stable at 10⁻¹⁴” is incomplete. “Backward stable at 10⁻¹⁴ against perturbations of M, C and K” and “at 4·10⁻¹³ against perturbations of K alone” are two statements about one run, both true, and only the second answers a question about the structure.

Report the factor, not only the number. The ratio between the restricted and unrestricted errors is available in closed form from three norms and one eigenvalue, before either error is computed, and it says which end of the spectrum a restriction will bite at.

And be careful reading a tolerance. The table above is one set of answers passing at one reading and failing at another. A tolerance chosen against the unrestricted number and applied to a problem where only one coefficient is free is a tolerance that is too loose by up to three orders — at one end of the spectrum, and by six per cent at the other.

What a structured restriction is not #

It is worth marking the boundary between this measurement and the structure field’s, because the two answer questions that sound the same.

A structured backward error asks for the smallest perturbation of a given form — Toeplitz, symmetric, positive — that makes the pair exact. Its denominator is the same; what changes is that the perturbation is restricted to a subspace of matrices, and computing it requires an optimisation over that subspace rather than a formula.

The restriction here is coarser and cheaper. It says nothing about the shape of ΔK, only that ΔM and ΔC are zero. So it is a restriction to a coordinate subspace of the three-coefficient space, which is why the minimal perturbation still has a closed form and why the ratio is a quotient of weights rather than the output of a minimisation.

Those two are composable and this field measures only one of them. A perturbation restricted to K and required to be symmetric is a further restriction, its backward error is at least this one, and the structure field’s measurement says the further factor is usually small — the structure never hurts by more than a modest constant. So the ordering of the three quantities is known even where only two are computed, which is the useful thing to take from having both fields.

Where this sits among the site’s backward errors #

Three quantities are now in play for one computed pair, and it is worth separating them.

The linearisation’s backward error asks how far the computed pair is from exact for the 2n × 2n matrix the solver actually ran on. A backward-stable answer to a problem nobody asked is the essay about it, and the answer is that it is always tiny and always about the wrong object.

The quadratic’s backward error asks the same about the polynomial, unrestricted. That is the standard published quantity and it is what most of this field measures.

The restricted backward error asks it against a subset of the coefficients. It is never smaller, it is not a fixed multiple of the second, and the multiple is a function of the eigenvalue.

The same three-way separation appears in the approximation committed before the arithmetic, where the third quantity is not a backward error at all. Three numbers, one computation, and each answers a different question about what would have to be wrong for the answer to be right. The site’s whole vocabulary for error rests on the observation that a wrong answer has an author; this is the observation that who counts as an author is a choice, and that the choice changes the verdict on half a spectrum.

The refusals, and why there are three #

Three assertions in this library are fed cases they must reject, and each one closes off a reading that a careless implementation would take.

A backward error with no coefficient allowed to move. The denominator is then zero, and the correct answer is that the question is malformed rather than that the error is infinite. A routine that returned infinity would be reporting a number where there is none.

The claim that a restriction can lower a backward error. Charging one residual to less data can only raise the quotient, so η_restricted ≥ η_all always. That is trivial to prove and easy to violate in code — a denominator assembled from the wrong weights, or a residual recomputed against the restricted polynomial rather than the original — and the assertion is fed a spectrum and required to find no counterexample.

And the claim that the restriction costs a fixed factor. This is the essay’s own finding turned into a refusal: a routine that computed the ratio once and applied it across a spectrum would be wrong by three orders at one end, and the assertion is handed a spectrum whose ratios span forty-three and required to reject the claim that they are all within one per cent of each other.

Each of those runs on every build. The second and third are the interesting ones, because both would otherwise be invisible: a restricted backward error that is too small looks like good news, and a constant factor looks like a simplification. Neither throws, neither is caught by a residual, and both are the kind of claim this site’s habit exists to make impossible to keep.

One line to add to a solver’s output #

The cheapest form of everything above is a single extra line, and it needs three norms the solver has already computed and one eigenvalue it has just produced.

restriction factor to X  =  (|λ|²‖M‖ + |λ|‖C‖ + ‖K‖) ÷ (the allowed part)

Printed beside each eigenpair, it tells a reader immediately how much a restriction would cost at that eigenvalue — before either backward error is computed, and without any decision about which restriction is the right one. A reader who knows their damping matrix is a model reads the M-and-K column; one who trusts everything reads none of them.

That is the site’s habit applied to a modelling decision rather than to an arithmetic one: print the number that says how much the decision is worth, and let the person who knows the answer make it.