Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Quadratic convergence — where it appears

Doubling the number of correct digits at each step. Newton's method has it near a root and not before, so a method's asymptotic rate says nothing about the steps that get it there.

Named by 5 essays across one field — each of them below, with the objects they name alongside it.

10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110⁻⁴10⁻³10⁻²10⁻¹1inner tolerance η, relative residual of the linear solvedistance from the root after the stepd² = 0.00138distance before the step, 0.03721093547231126the number by each point is the iterations it costeleven decades, one landing placedistance before the step0.037its square0.0014where η = 10⁻³ lands0.0025where η = 10⁻¹⁴ lands0.0025iterations for the first354iterations for the second1126the accuracy that is thrown awaymeasured against a root that is known

The accuracy that is thrown away

A Newton step is the exact answer to a linearised problem, and the linearisation is wrong at second order. So there is a floor under how close the step can land, the floor is the square of where it started, and eleven decades of inner tolerance below it buy the same four digits at four times the price.

sequence · Inexact newton 0123456789101110⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110³Newton steptolerance asked for, and iterations paiditerations paidtolerance asked forouter residualthe adaptive policy, step by stepNewton steps10inner iterations, total1009first step's cost1last step's cost271final outer residual3.4·10⁻¹¹the rule reads the last two residualsand asks for nothing it cannot use

A tolerance that reads its own residual

The cheapest constant forcing term costs 980 inner iterations and arrives with a hundred times the forward error of the dearest, which costs 9,358. A rule that sets each step's tolerance from the ratio of the last two residuals costs 1,009 and arrives with neither problem — and it is not a constant, so it does not appear on the curve the constants are compared on.

sequence · Inexact newton total inner iterationscold at η = 1e-107016scaled warm start6837unscaled728910⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10³10³.⁵10⁴forcing term ηinner iterationsthe previous stepstarted at zerothe previous step, scaledthree curves within eight per cent of each otherand the unscaled guess is the worst of the three

A guess worth two per cent

The previous Newton step looks like a free guess at the next one, and it is worth nothing. Started from it unscaled, the inner solve costs 4 to 61 per cent more than starting from zero, because the guess is 15 to 209 times too large. Scaled by the ratio of the two residual norms it is the right size and halves the starting residual — which buys a constant handful of inner iterations, not a share, because conjugate gradients costs the logarithm of its tolerance.

sequence · Inexact newton what one line doesinner work saved, worst case0.09best case0.27forward error cost, worst263610⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴outer toleranceforward errorerror, with the floorerror, without itinner work, rescaledthe grey diagonal is the residual the test asked forboth runs meet it and one is far more accurate

One line that buys a quarter of the run

The adaptive forcing rule has a floor on it that no published statement of the rule carries: do not solve a step to an accuracy the outer loop will not use. Removing it costs 9 to 27 per cent of the whole inner run. Keeping it costs between 23 and 2,600 times the forward error — accuracy the residual test never asked for and both runs satisfy the test either way. The line is a trade between a residual and an error, and which of the two the caller meant decides whether it is a saving.

sequence · Inexact newton tol 10⁻⁸unguarded inner iterations1109c = 1, error ÷ unguarded497910⁻²10⁻¹110¹10⁻¹110¹10²10³10⁴10⁵c, the floor's constantover the unguarded runerror ÷ unguardedinner iterations ÷ unguardedopen dots: the run did not convergea trade with no knee, and then a cliff

A floor with a cliff at one

Inexact Newton's adaptive forcing rule is used with a floor: never ask the inner solve for less than c times the outer tolerance, relative to the current residual, with c a half. Swept from a hundredth to ten, the constant trades with no knee at all — the forward error rises in proportion to c, the inner work falls by a few per cent a decade — and then, just past one, the run stops converging: at c = 3 it hits the outer limit on four problems of five, having asked every step for less than the stopping test needs. And the accuracy the floor gives up at c = ½ is no planning number: across five problems and four tolerances it runs from nothing to a factor of 48,000.

sequence · Inexact newton

Named alongside it

The objects these essays reach for when they reach for this one.

Conjugate gradientsForcing termInexact newtonNewton iterationFlop countExact ground truthKrylov subspaceStopping criterionForward errorLinearisationResidualWarm start

All concepts