Noise the growth amplifies

A worst case is as fragile as its margin put two large growth factors under Gaussian noise. Wilkinson’s matrix, whose growth of 5.5·10¹¹ rests on exact ties between candidate pivots, lost it to noise at the last digit of a double. The multiple-shooting matrix from a boundary-value problem, whose growth of 1.1·10⁴ rests on partial pivoting choosing a −1 over a transfer-matrix entry of 0.99436, kept it up to noise of 10⁻⁸ and then lost it along a straight line: 4.8·10³ at 10⁻⁶, 536 at 10⁻⁵, 54 at 10⁻⁴, 5.8 at 10⁻³. The median growth times the noise, divided by the margin of 5.6·10⁻³, stayed between one half and four thirds at every step size tried.

It read that line as noise reversing the comparison: a perturbation larger than the margin can reverse it, each reversal breaks the chain the growth rides on, and larger noise reverses one sooner. It also noted, in its list of what was not measured, that the noise it used filled every zero of a matrix that is almost all zeros, and that noise confined to the entries the problem has might behave differently.

It behaves so differently that the explanation does not survive. At 10⁻⁵ the noise is five hundred times smaller than the margin; it cannot reverse a comparison decided by five thousandths directly. Something is making it larger.

Four ways to perturb one matrix #

The shooting matrix for 40 steps of 0.3 has 82 rows and 6,724 entries, of which 244 are nonzero: two boundary rows with two ones each, and 80 continuity rows each carrying two entries of the transfer matrix E and one −1. Four perturbations of it:

Every entry, the earlier measurement: Gaussian noise of standard deviation σ added to all 6,724 entries, zeros included.

Nonzeros only: the same noise added to the 244 nonzero entries, the zeros left zero. This is a matrix with the problem’s own structure and slightly wrong numbers in it.

Relative, per entry: every entry multiplied by 1 + σ·N(0, 1), which leaves zeros zero and perturbs each nonzero in proportion to its size — the model of rounding or of a measurement quoted to a fixed number of digits.

One error in E: a single random perturbation of the 2 × 2 transfer matrix, of standard deviation σ, applied identically in all 40 continuity blocks. That is what a slightly wrong discretisation of the differential equation does: every step uses the same wrong propagator.

Noise in the nonzeros does nothing below the margin #

Under noise in the nonzeros only, every one of thirty draws keeps a growth of 1.1·10⁴ at every noise level up to 10⁻³ — at 10⁻⁵, where dense noise leaves a median of 536, and at 10⁻³, where it leaves 5.8. The relative model is the same. Both lose the growth between 10⁻³ and 10⁻²: at 3.2·10⁻³, a little over half the margin, the median is 2.7 for noise in the nonzeros and 13.7 for relative noise, with the worst of thirty draws still at 860 and 6,800. From 10⁻² on, all three models that perturb entry by entry sit at about 2.

That is the behaviour the margin predicts for the noise that can reverse a comparison by itself. The comparison at each continuity step is |$E_{11}$| against |−1|, and nothing below the margin can change its outcome. It changes abruptly once the noise is comparable to the margin, not along a line.

The line belongs to dense noise alone, and the difference between the two is 6,480 zeros.

Where the zeros enter #

Following one factorisation under dense noise says where. Partial pivoting on the noise-free matrix makes its interchanges at particular steps. Under noise of 10⁻⁵ the first step at which the noisy factorisation makes a different choice is, on three draws, step 46, 48 and 51 of 82 — well along the chain, where the growth has already reached hundreds — and at every one of them the row chosen is the transfer-matrix row, entry 0.9944, over the −1 row.

The −1 in the chosen column has not been perturbed by 10⁻⁵ at that step. It has been perturbed by 10⁻⁵ times the growth. The noise in a zero entry of an earlier row sits in the column the growing entry is being carried along, and every elimination step that carries the growth forward carries that noise forward with it, multiplied by the same factors. By the time the elimination reaches a step where the accumulated growth is G, the candidates in the pivot column carry perturbations of about σ·G, and the comparison flips when σ·G is a fraction of the margin.

The product that stays put #

That explanation makes a sharp prediction. If the chain breaks where σ times the growth accumulated reaches a fixed fraction of the margin, then σ times the growth at the step before the first reversal, divided by the margin, should not depend on σ.

It does not. At a step of 0.3 the median product is between 0.37 and 0.48 across seven noise levels from 10⁻⁶ to 10⁻³ — three decades of σ, over which the growth reached at the break falls from about 2,400 to about 2. At a step of 0.2 it is between 0.31 and 0.37, and at 0.1 between 0.18 and 0.23. At every step it is flat, and at every step it is below one.

So the law the earlier measurement found — median growth about the margin divided by σ — is this product rearranged. The growth stops where σ·G reaches a constant times the margin, so G is that constant times margin over σ. What was wrong was not the law but the mechanism attached to it: the noise that reverses the comparison is σ amplified by the growth, and the growth is limiting itself by amplifying the noise that ends it.

The constant also explains the earlier puzzle about step sizes. The earlier measurement found the median growth times σ over margin between 0.50 and 0.66 at a step of 0.1 and higher at 0.3, and offered two readings without separating them. The product here moves the same way — 0.2 at a step of 0.1, 0.33 at 0.2, 0.43 at 0.3 — which is consistent with the step-size dependence lying in how much amplified noise a pivot candidate collects: a finer shooting grid has three times as many rows feeding noise into the same stretch of the chain, and a smaller product means the comparison flips at a smaller σ·G.

The two constants are related and not equal, and the relation is worth a sentence. The earlier product uses the final growth, which includes whatever growth the chain accumulates after the first reversal and before a second one; the product here uses the growth at the first reversal, and it sits lower — 0.43 against the earlier 0.74 to 1.35 at a step of 0.3 — by roughly the factor the chain still manages to climb after it first breaks. That is the second of the two readings the earlier measurement offered, now with the quantity that separates it from the first.

What the amplification says about the tie #

Wilkinson’s matrix fits the same account with its margin set to zero. Its candidates are exactly equal, so no amplified noise is needed: the first comparison already has nothing to amplify against, and noise at the last digit decides it. A partition decided in the last digit is the same fact in a different algorithm — a discrete choice between exactly equal quantities is a choice made by the rounding.

A margin changes that in two ways the tie cannot. It sets a floor below which unamplified noise does nothing, which is why noise in the nonzeros leaves the shooting matrix alone. And it makes the noise that does act grow with the very quantity being measured, so the growth a noisy factorisation reports is not an independent reading of the matrix but the point at which the matrix’s own growth and the noise balanced. A code that reports a growth factor under dense perturbation is largely reporting margin over noise, and learns little about the matrix that the margin did not already say. What the growth costs is a separate question, and the exact answer to a nearby problem is where that is measured here: in backward error, which is what a growth of 1.1·10⁴ actually spends.

It also says which of the repairs measured so far is the real one. A pivot that searches one row and one column keeps the shooting matrix’s growth below 2 with no noise at all, because a rule that searches the pivot’s row as well as its column does not settle the chain’s comparison by a margin of five thousandths in the first place. Perturbing the matrix until partial pivoting chooses differently is a repair only for noise that fills zeros, and a real computation does not produce that noise. The swap that is not optional was the first reminder in these essays that a pivot rule’s choice is invisible in the answer’s shape; here it is invisible to every perturbation a computation actually makes, and visible only to one it does not.

One error in E decides the whole chain at once #

The fourth model is the one a user of multiple shooting actually faces. A transfer matrix computed by a numerical integrator is not exact; it is wrong by the integrator’s error, and wrong the same way at every step.

With a consistent error of standard deviation 10⁻² — nearly twice the margin — the growth is decided by which side of one the perturbed $E_{11}$ lands on. All 9 of the forty draws that move $E_{11}$ up by more than the margin, past one, lose the growth entirely: their growth factors are between 1.89 and 1.99. Of the 12 draws that move it down by more than the margin, 11 keep a growth above a third of 1.1·10⁴. Of the 19 that move it by less than the margin in either direction, 15 keep it, and which of those lose it is left to the perturbation of E’s other three entries, which a scatter against $E_{11}$ alone does not resolve.

There is no median line here to fit. A consistent error does not reverse comparisons one at a time along the chain; it moves every comparison the same way at once, so the chain either holds everywhere or breaks at the first step. Under the median-growth summary it reads as 21 of thirty draws keeping the growth at 10⁻² and 7 at 10⁻¹·⁵, but the individual draws are all or nothing.

That changes what “robust” means for the shooting matrix’s worst case. Rounding, measurement error and a noisy right-hand side — the perturbations that fill no zeros and differ entry by entry — do nothing to it until they reach the margin. An integrator’s error does nothing to it unless it moves $E_{11}$ past one, and then removes it completely. And the dense noise of a smoothed analysis, the model under which the worst case looked fragile along a line, is the only one of the four that no computation on this matrix actually produces.

The same at a finer step #

At a step of 0.2 the picture keeps its shape and moves with the margin. The noise-free growth is the same 1.1·10⁴, because the interval is the same. Dense noise leaves a median of 1,190 at 10⁻⁵ and 10.9 at 10⁻³, about twice the step-0.3 values, as the larger margin predicts. Noise in the nonzeros keeps every draw at the full growth to 10⁻³. The consistent error keeps the growth on 24 of thirty draws at 10⁻² and 14 at 10⁻¹·⁵ — more than at a step of 0.3, because a larger margin needs a larger error to push $E_{11}$ past one.

What this changes about the fragile and the robust #

The earlier measurement’s conclusion was that the constructed worst case is fragile and the worst case from practice is robust, and that conclusion stands with more force than it had. Wilkinson’s ties are broken by any noise at all, because a tie has no margin to amplify noise against. The shooting matrix’s growth is removed only by noise the elimination has already amplified, and noise that the elimination cannot amplify — noise that stays out of the zeros — does nothing to it until it is as large as the margin itself.

What changes is the smoothed analysis’s model, and it is worth being precise about the claim. Smoothed analysis of Gaussian elimination bounds the expected growth of a matrix perturbed by dense Gaussian noise, and its bounds are about that model. For a sparse matrix whose growth rides a chain through its structure, dense noise is not a small perturbation of the problem but a different problem — one whose every zero is a coupling the original did not have, and whose couplings sit exactly where the growth will amplify them. A perturbation model that respects the zeros is the one that describes what a real shooting computation does, and under it the growth is as robust as the margin says.

The growth a boundary-value problem supplies found the switch at $E_{11}$ = 1 as a function of the step; the consistent-error measurement is the same switch reached by a wrong E rather than by a different step. The bound that is never attained put the gap between the 2ⁿ⁻¹ bound and practice at eleven orders; this measurement says that inside the practice, the part that behaves like the bound is not the part that noise can find.

What this rests on #

One boundary-value problem, y′ = My with M = [[−1/6, 1], [1, −1/6]], over an interval of 12, at steps of 0.3 and 0.2, with thirty draws per noise level and model; the amplification measured at steps of 0.1, 0.2 and 0.3. The first departure from the noise-free pivot sequence is found by comparing whether each step interchanges rows, which detects the first reversal and not every later one. The consistent-error scatter is forty draws at one noise level.

The amplification argument is read from the flatness of a product across three decades and from the pivot choices at the first departure; it is not a bound. A proof would have to follow the noise in each zero through the elimination’s multipliers, and the constant in front — 0.2 to 0.43 across the steps — is measured, not derived.

The claim that has to fail #

The claim is the earlier measurement’s law stated without its hidden hypothesis: a growth that rests on a margin falls as the margin over the noise, whatever the noise perturbs. Fed noise of 10⁻⁴ in the nonzeros only, where margin over noise is 56, and required to show a growth times noise over margin below two, it fails: the median growth is still 1.1·10⁴ and the product is 195. The dense sweep beside it, at the same noise, gives 54 and a product near one, and that pair is the measurement.

Still open: recording the margin, and a matrix with several margins #

A margin a factorisation records. The amplification law says the noise that can remove growth at a given step is about the margin there divided by the growth reached there, and a partial-pivoting scan finds the second-largest candidate for nothing. Whether the smallest such ratio over the steps that come before most of the growth predicts, from one factorisation, the noise that removes it — and whether it can tell a tie from a margin on a matrix nobody has looked at — is measured in a margin the factorisation records.

Several growing modes. A system with several growing modes has a transfer matrix with several diagonal entries near one and several chains of growth sharing columns. Dense noise amplified along one chain lands in another’s comparisons, and whether the amplification law still holds with one constant, or whether the chains break each other, is a matrix with more structure than this one.

The integrator’s error, measured rather than modelled. The consistent error here is a random perturbation of E. An actual integrator’s error in exp(hM) has a direction set by its order and by M, and whether that direction moves $E_{11}$ towards one or away from it decides, by this measurement, whether the computed growth is the true one or 2.