Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Forcing term — where it appears

2 essays name this object, across one field. What follows is each of them, and the objects they name alongside it.

Also named here as inexact newton, quadratic convergence — the same set of essays touches all of them, so they are one junction rather than several.

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

Named alongside it

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

Conjugate gradientsFlop countInexact newtonKrylov subspaceNewton iterationQuadratic convergenceExact ground truthLinearisationStopping criterionWarm start

All concepts