Numerical Linear Algebra
where the algebra stops being the arithmetic
When the problem arrives again

A fit wins where the steps were few

The line through the last two answers of a sequence of solves amplifies their stored error by √5, and the parabola through the last three by √19. A least-squares line through five amplifies it by 1.05 and a parabola through six by 1.79, and on a straight path both beat their interpolants at every tolerance: 12 inner steps against 17 at 10⁻¹⁴. On a bent path they lose, by exactly the ratio of their truncation constants, and they lose in the runs that cost a hundred steps rather than ten. Over thirty runs no fitted start beats the parabola through three, and the best of eight starts chosen per run saves 58 steps out of 1,212.
23 min read 6 figures Measured, not assumedIdentical algebra, different arithmeticWhose fault is it

Worth reading first: The problem that arrives again · A warm start is degree zero.

A computation that solves the same kind of problem again and again, each member a small step along a parameter from the last, can start each solve from a guess built out of the answers it already has. The problem that arrives again listed the stored answers among the things a sequence carries from member to member, and the order a batch arrives in found that they are worth most when neighbouring members are neighbours in the parameter. A warm start is degree zero found that the previous answer is a poor guess and the line through the last two a very good one, thirteen times cheaper in inner steps. A straight path has nothing for a parabola to fit found why the parabola through the last three did not do better still: the path was straight, so the line was exact, and the parabola paid its larger amplification of the stored answers’ error for nothing. Bend the path and the parabola wins at tight tolerances. The degree the history chooses then priced the choice between them: over thirty runs of bend and tolerance, always taking the line costs 456 inner steps more than the better of the two, and always taking the parabola costs 33.

All of those starts are interpolants. The line passes through the last two answers and the parabola through the last three, so each uses as few stored answers as its degree allows, and each carries whatever error those answers hold straight into the guess. The obvious alternative uses more of them. A straight line fitted by least squares to the last five answers does not pass through any of them, and so averages their errors rather than extrapolating them.

That is a trade, and it is the trade every smoothing method makes. A fit through more points amplifies noise less and misses a curve by more. This essay measures the trade exactly — both halves of it have closed forms — and then measures where on this family of sequences each half wins. The answer is lopsided in a way the closed forms do not show: the fits win on the runs that were cheap anyway, and lose on the runs where the steps are.

Every start is a fixed combination of stored answers

Suppose the last m answers are stored at parameter values one drift step apart, and the next is wanted one step further on. Put the most recent answer at 0 and the earlier ones at −1,−2,…,−(m−1)-1, -2, \ldots, -(m-1). Fit a polynomial of degree d to them by least squares and evaluate it at +1+1. Because the fit is linear in the data, the result is a fixed combination ∑jwjx−j\sum_j w_j x_{-j} of the stored answers, and the weights depend only on d and m.

For the interpolants these are the familiar coefficients: (2,−1)(2, -1) for the line through two, and (3,−3,1)(3, -3, 1) for the parabola through three. For the least-squares line through three answers the weights are (43,13,−23)(\tfrac{4}{3}, \tfrac{1}{3}, -\tfrac{2}{3}); through four, (1,12,0,−12)(1, \tfrac12, 0, -\tfrac12); through five, (0.8,0.5,0.2,−0.1,−0.4)(0.8, 0.5, 0.2, -0.1, -0.4). Every set sums to one, which is what makes a constant path come out exact; every line reproduces a straight path exactly, and every parabola a quadratic one.

Two numbers describe each set completely for the question at hand.

The amplification is the Euclidean norm of the weights. If every stored answer carries an independent error of size ν, the start carries an error of about ∥w∥ ν\|w\|\,\nu. For the line through two that is 5≈2.24\sqrt 5 \approx 2.24; for the line fitted to five it is 1.05. For the parabola through three it is 19≈4.36\sqrt{19} \approx 4.36, and for the parabola fitted to six, 1.79.

The truncation constant is how far the start misses a path that is one degree too curved for it. For a line that is a quadratic path, for a parabola a cubic one, and the constant is measured in units of that path’s second or third difference. The line through two misses a quadratic by 2; fitted to three, by 3.33; to four, by 5; to five, by 7. The parabola through three misses a cubic by 6; fitted to four, by 10.5; to five, by 16.8; to six, by 25.2.

What a start built from stored answers amplifies and what it misses: the norm of its coefficients against its truncation constant, for lines and parabolas through or fitted to more answersEach point is one fixed combination of the last m stored answers that predicts the next one. Horizontally, the Euclidean norm of its coefficients, which multiplies the error the stored answers carry. Vertically, how far it misses a path that is exactly quadratic (for the lines) or cubic (for the parabolas), in units of that path's second or third difference. line through 2: coefficients 2.00, -1.00, norm 2.24, miss 2.00; line fitted to 3: coefficients 1.33, 0.33, -0.67, norm 1.53, miss 3.33; line fitted to 4: coefficients 1.00, 0.50, 0.00, -0.50, norm 1.22, miss 5.00; line fitted to 5: coefficients 0.80, 0.50, 0.20, -0.10, -0.40, norm 1.05, miss 7.00; parabola through 3: coefficients 3.00, -3.00, 1.00, norm 4.36, miss 6.00; parabola fitted to 4: coefficients 2.25, -0.75, -1.25, 0.75, norm 2.78, miss 10.50; parabola fitted to 5: coefficients 1.80, 0.00, -0.80, -0.60, 0.60, norm 2.14, miss 16.80; parabola fitted to 6: coefficients 1.50, 0.30, -0.40, -0.60, -0.30, 0.50, norm 1.79, miss 25.20.11.522.533.544.50510152025amplification of the stored error, norm of the coefficientstruncation constant23453456lines, by answers usedparabolas, by answers usedeach extra answer moves a point up and to the leftthe interpolants sit at the bottom right
Fig. 1 Eight fixed combinations of stored answers: the norm of each one’s coefficients, which multiplies the stored error, against its truncation constant on a path one degree too curved for it. Lines and parabolas are drawn separately, labelled by how many stored answers they use.

Each extra stored answer moves a point up and to the left: less amplification, more truncation. The interpolants sit at the bottom right of their curves. For the lines the trade is steep at first — going from two answers to three cuts the amplification by a third for two-thirds more truncation — and flattens after. For the parabolas it is the same shape at larger numbers, and fitting a parabola to six answers brings its amplification below the line through two.

This is the same arithmetic as a smoothing filter, and the same trade choosing without knowing made with a regularisation parameter: a smaller variance paid for with a larger bias. What the figure cannot say is which half matters on a real sequence, because that depends on how large the stored error is against how curved the path is — and the stored error is set by the solve tolerance, while the curvature is set by the problem.

On a straight path every fit wins

The sequence is the one the earlier essays measured. Each member is a nonlinear system of 120 unknowns — a symmetric positive definite matrix with condition number 10410^4 plus a small cubic term — whose exact root moves with the parameter t along a known path. It is solved by a chord iteration that keeps one Cholesky factor for four members, as a factorisation kept past its date found worthwhile, and stops when the relative residual falls below the tolerance. Twenty members are walked at a drift of 0.02. The path is t⋅s1+csin⁡(3t) s2t \cdot s_1 + c \sin(3t)\, s_2 for two fixed random directions, so c=0c = 0 is a straight path and larger c bends it.

Inner steps over twenty members from four extrapolated starts, against the solve tolerance — a straight pathThe drifting sequence of 120 unknowns, drift 0.02, factorisation rebuilt every four members; roots on a straight line. 10⁻⁶: line through 2 11, line fitted to 5 4, parabola through 3 17, parabola fitted to 6 9; 10⁻⁸: line through 2 12, line fitted to 5 6, parabola through 3 16, parabola fitted to 6 10; 10⁻¹⁰: line through 2 12, line fitted to 5 8, parabola through 3 14, parabola fitted to 6 9; 10⁻¹²: line through 2 17, line fitted to 5 9, parabola through 3 23, parabola fitted to 6 15; 10⁻¹⁴: line through 2 17, line fitted to 5 12, parabola through 3 23, parabola fitted to 6 15.a straight pathline through 2, at 10⁻¹⁴17line fitted to 5, at 10⁻¹⁴12parabola through 3, at 10⁻¹⁴23parabola fitted to 6, at 10⁻¹⁴1510⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶050100150relative residual tolerance of every solveinner steps over twenty membersline through 2line fitted to 5parabola through 3parabola fitted to 6tighter to the lefteach point is a whole run of twenty
Fig. 2 Inner steps over twenty members against the solve tolerance, from the line through two answers, the line fitted to five, the parabola through three and the parabola fitted to six. The dial bends the path, from straight to a bend of 10−110^{-1}.

On the straight path the line fitted to five is the cheapest start at every tolerance. At 10−610^{-6} it takes 4 inner steps over the twenty members against the line through two’s 11; at 10−1010^{-10}, 8 against 12; at 10−1410^{-14}, 12 against 17. The parabola fitted to six beats the parabola through three by a similar margin, 15 against 23 at 10−1410^{-14}, and beats even the line through two, whose amplification it undercuts.

On this path the fits have nothing to lose. A straight path has no second difference, so every line is exact and the truncation constant multiplies zero. What is left is the stored error, and every fit amplifies it less.

It does not amplify it less by as much as the coefficient norms promise. The median start of the line fitted to five is 0.57 times as far from the root as the line through two’s at 10−1410^{-14}, where the norms predict 0.47, and at 10−1010^{-10} it is only a fifth closer. The norms assume the stored errors are independent, and they are not: every member is started from an extrapolation of the ones before, stopped at the same tolerance, and solved with the same factor for four members at a time, so neighbouring errors share a direction. A fit averages independent errors down and correlated ones much less.

On a bent path the truncation constant is the whole story

Turn the dial to a bend of 10−410^{-4} and the order reverses at tight tolerances. At 10−1410^{-14} the parabola through three takes 75 steps, the parabola fitted to six 92, the line through two 105 and the line fitted to five 115.

The distance of each start from the root says why, and says it exactly.

How far each line starts from the next root against the solve tolerance, through or fitted to more stored answers — a path bent by 10⁻⁴The median over members of the relative distance between the start and the member's exact root, on logarithmic axes, with the tolerance itself drawn as a dashed line. 10⁻⁶: line through 2 2.97·10⁻⁶, line fitted to 3 9.84·10⁻⁷, line fitted to 4 1.34·10⁻⁶, line fitted to 5 1.69·10⁻⁶; 10⁻⁸: line through 2 5.09·10⁻⁷, line fitted to 3 8.49·10⁻⁷, line fitted to 4 1.3·10⁻⁶, line fitted to 5 1.73·10⁻⁶; 10⁻¹⁰: line through 2 5.21·10⁻⁷, line fitted to 3 8.73·10⁻⁷, line fitted to 4 1.32·10⁻⁶, line fitted to 5 1.77·10⁻⁶; 10⁻¹²: line through 2 5.19·10⁻⁷, line fitted to 3 8.71·10⁻⁷, line fitted to 4 1.31·10⁻⁶, line fitted to 5 1.77·10⁻⁶; 10⁻¹⁴: line through 2 5.19·10⁻⁷, line fitted to 3 8.71·10⁻⁷, line fitted to 4 1.31·10⁻⁶, line fitted to 5 1.77·10⁻⁶.10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶10⁻⁵relative residual tolerance of every solvemedian distance of the start from the rootline through 2line fitted to 3line fitted to 4line fitted to 5a start that follows the tolerance is limited by the stored answersa flat one by the path
Fig. 3 The median distance of each line’s start from the next root against the solve tolerance, on a path bent by 10−410^{-4}, through two answers and fitted to three, four and five, on logarithmic axes, with the tolerance itself dashed.

At loose tolerances the four lines follow the tolerance down, and there the fits are closer: at 10−610^{-6} the line fitted to three starts at 9.8×10−79.8 \times 10^{-7} against the line through two’s 3.0×10−63.0 \times 10^{-6}. The step counts at that tolerance do not follow the medians — 13 steps for the line through two and 20 for the fit to three — and nothing here explains why; the median leaves out the first few members, where a fit has not yet stored enough answers and starts from the line instead. From 10−810^{-8} on all four go flat, each at its own floor, and the floors are 5.2×10−75.2 \times 10^{-7}, 8.7×10−78.7 \times 10^{-7}, 1.3×10−61.3 \times 10^{-6} and 1.8×10−61.8 \times 10^{-6}. Their ratios to the first are 1.67, 2.50 and 3.46. The ratios of the truncation constants are 3.33/2=1.673.33/2 = 1.67, 5/2=2.55/2 = 2.5 and 7/2=3.57/2 = 3.5. Below 10−810^{-8} each line’s start is its truncation error and nothing else, and the constant computed from the weights predicts where the floor lies to two figures.

The parabolas behave the same way one derivative up. Their floors at a bend of 10−410^{-4} are 9.5×10−99.5 \times 10^{-9}, 1.6×10−81.6 \times 10^{-8}, 2.3×10−82.3 \times 10^{-8} and 3.8×10−83.8 \times 10^{-8}, in ratios 1.68, 2.42 and 4.0 against the constants’ 1.75, 2.8 and 4.2. The agreement is looser because the path sin⁡3t\sin 3t has a fourth derivative as well, which the cubic constant does not account for.

Once a start sits on its floor, tightening the tolerance adds inner steps in proportion to the number of digits between the floor and the tolerance, and a floor 3.5 times higher costs roughly half a digit’s worth of steps on every member. That is the whole of the fits’ loss on a bent path: they trade a reduction in the amplification, which no longer matters once the stored error is far below the floor, for an increase in the truncation, which is the floor.

Inner steps over twenty members from four extrapolated starts, against the solve tolerance — a path bent by 10⁻⁴The drifting sequence of 120 unknowns, drift 0.02, factorisation rebuilt every four members; roots on a line bent by 10⁻⁴·sin 3t. 10⁻⁶: line through 2 13, line fitted to 5 21, parabola through 3 17, parabola fitted to 6 8; 10⁻⁸: line through 2 23, line fitted to 5 23, parabola through 3 22, parabola fitted to 6 22; 10⁻¹⁰: line through 2 39, line fitted to 5 44, parabola through 3 26, parabola fitted to 6 28; 10⁻¹²: line through 2 71, line fitted to 5 74, parabola through 3 43, parabola fitted to 6 55; 10⁻¹⁴: line through 2 105, line fitted to 5 115, parabola through 3 75, parabola fitted to 6 92.a path bent by 10⁻⁴line through 2, at 10⁻¹⁴105line fitted to 5, at 10⁻¹⁴115parabola through 3, at 10⁻¹⁴75parabola fitted to 6, at 10⁻¹⁴9210⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶050100150relative residual tolerance of every solveinner steps over twenty membersline through 2line fitted to 5parabola through 3parabola fitted to 6tighter to the lefteach point is a whole run of twenty
Fig. 4 Inner steps against the solve tolerance, the same four starts, on a path bent by 10−410^{-4}.

Which start is best, cell by cell

Lines and parabolas each through or fitted to up to six answers make eight fixed starts. On each of thirty runs — six bends from 0 to 10−110^{-1} and five tolerances from 10−610^{-6} to 10−1410^{-14} — one of them is cheapest.

The best of eight extrapolated starts in each cell of bend and tolerance, and how many steps it saves over the better interpolantTwenty-member runs at drift 0.02. Lines and parabolas through the fewest answers (L2, P3) or fitted by least squares to more (L3 to L5, P4 to P6). Each cell names the start with the fewest inner steps, its steps, and in brackets the saving over the better of L2 and P3. c = 0: L5 4 (7), L5 6 (6), L4 8 (4), L4 9 (8), L5 12 (5); c = 10⁻⁵: L4 6 (6), P5 13 (5), P4 24 (1), P3 30 (0), P3 59 (0); c = 10⁻⁴: P6 8 (5), P5 20 (2), P3 26 (0), P3 43 (0), P3 75 (0); c = 0.001: P4 12 (5), P4 22 (1), P3 29 (0), P3 58 (0), P3 93 (0); c = 0.01: P5 18 (2), P3 24 (0), P3 42 (0), P3 73 (0), P3 109 (0); c = 0.1: P4 20 (1), P3 27 (0), P3 58 (0), P3 93 (0), P3 133 (0).best start, its steps, and the saving over the better interpolanttol 10⁻⁶tol 10⁻⁸tol 10⁻¹⁰tol 10⁻¹²tol 10⁻¹⁴straightL5 4 (−7)L5 6 (−6)L4 8 (−4)L4 9 (−8)L5 12 (−5)bend 10⁻⁵L4 6 (−6)P5 13 (−5)P4 24 (−1)P3 30P3 59bend 10⁻⁴P6 8 (−5)P5 20 (−2)P3 26P3 43P3 75bend 0.001P4 12 (−5)P4 22 (−1)P3 29P3 58P3 93bend 0.01P5 18 (−2)P3 24P3 42P3 73P3 109bend 0.1P4 20 (−1)P3 27P3 58P3 93P3 133a least-squares fit is bestan interpolant is bestL: line, P: parabola, number: answers usedbend: c in c·sin 3t
Fig. 5 For each bend and tolerance, the start of the eight with the fewest inner steps over twenty members, those steps, and in brackets how many fewer than the better of the two interpolants. L is a line and P a parabola; the number is how many stored answers it uses.

A least-squares fit is the best start in fourteen of the thirty cells, and they form one corner of the map: every cell of the straight path, and the loose-tolerance cells of the bent ones. There the stored error is at least comparable with the truncation error, and a start that averages it wins. Which fit wins moves with the bend in the way the trade figure predicts. On the straight path it is a line through four or five. With a slight bend it becomes a parabola, through five or six at a bend of 10−410^{-4}, because a line fitted to many points on a bent path has a large truncation constant and a parabola has none at second order.

In the other sixteen cells the parabola through three is the best start, and adding answers to the parabola never helps — 75, 80, 87, 92 steps at a bend of 10−410^{-4} and 10−1410^{-14}, in order of the answers used.

The brackets in the fit corner are small. The largest saving anywhere is eight steps, on the straight path at 10−1210^{-12}, where the line through two takes 17 and the line fitted to four 9. The fourteen savings add to 58 steps.

The totals, and why the corner is cheap

Total inner steps over thirty runs of bend and tolerance, for eight fixed extrapolated starts and for the best per runSix bends from 0 to 10⁻¹ and five tolerances from 10⁻⁶ to 10⁻¹⁴, twenty members each. line through 2: 1669; line fitted to 3: 1705; line fitted to 4: 1741; line fitted to 5: 1772; parabola through 3: 1245; parabola fitted to 4: 1283; parabola fitted to 5: 1367; parabola fitted to 6: 1382; better of the two interpolants, per run: 1212; best of all eight, per run: 1154.line through 21669line fitted to 31705line fitted to 41741line fitted to 51772parabola through 31245parabola fitted to 41283parabola fitted to 51367parabola fitted to 61382better of the two interpolants, per run1212best of all eight, per run1154every fit loses to its interpolant in totalthe costly runs are the bent, tight ones
Fig. 6 Total inner steps over the thirty runs of bend and tolerance, for each of the eight fixed starts, for the better of the two interpolants chosen per run, and for the best of all eight chosen per run.

Summed over the grid, no fixed start beats the parabola through three, at 1,245 steps. The fitted parabolas take 1,283, 1,367 and 1,382; the lines take 1,669 through two and 1,705 to 1,772 fitted. Every fit is worse in total than the interpolant of its own degree. The better of the two interpolants chosen per run — the target the previous essay’s rules were chasing — takes 1,212. The best of all eight chosen per run takes 1,154.

So a rule that could pick any of the eight starts perfectly on every run would improve on a perfect choice between the two interpolants by 58 steps in 1,212, under five per cent. The previous essay’s cheapest imperfect rule already came within 11 steps of 1,212, and its residual rule matched it on 29 runs in 30 for 135 steps’ worth of residual evaluations.

The asymmetry is in where the steps are. The cells a fit wins are the cells where the start is limited by stored error, and the stored error is limited by the tolerance, so the start is already close: those runs take between 4 and 24 steps. The cells an interpolant wins are the cells where the start is limited by the path’s curvature at a tight tolerance, and those take between 24 and 133 steps. A fit saves a fraction of a small number and costs a fraction of a large one. Ten of the fourteen fit cells save five steps or fewer, from runs of twenty-four steps or fewer; the most expensive run on the grid, 133 steps, is one where adding a sixth answer to the parabola would cost 17 more.

The same trade in other places

The trade itself is not special to extrapolation. A basis built from the points fitted polynomials to noisy data and found that the fit moves with the noise by an amount set by the basis and the points, which is the same amplification factor seen from the other side. The answer the last window left found a sliding least-squares window whose natural warm start — the previous window’s answer — was three orders worse than a fresh solve on a stream with any noise in it; there too the stored answer carried an error that the next problem could not use.

What this family adds is the asymmetry between the two halves. Which half wins depends on a ratio of stored error to curvature, and the cost of losing depends on the curvature alone. A method that minimises the expected distance of the start from the root — which is what a smoothing fit does — is optimising the wrong quantity when the cost is the logarithm of that distance summed over runs of very different lengths.

What a code should do

Keep the interpolants and choose between them, as the previous essay’s rules do. The parabola through three is the right default when nothing is known about the path; the line through two is the better choice on a path close to straight, and the previous essay’s free rule is built to detect those runs.

A least-squares fit is worth considering only where both conditions hold: the path is close enough to straight that its curvature is below the stored error, and the tolerance is loose enough that the stored error is the limit. In that corner, fitting a line to four or five answers roughly halves the steps. But those are runs of ten steps or fewer over twenty members, and a code that took the fit everywhere would pay for it many times over on the runs that matter.

What this rests on

One family of nonlinear sequences with 120 unknowns and a condition number of 10410^4; a chord iteration with a factor kept for four members; twenty members at a drift of 0.02; bends csin⁡3tc \sin 3t with c from 0 to 10−110^{-1}; tolerances from 10−610^{-6} to 10−1410^{-14}; lines and parabolas through or fitted to at most six stored answers, at equal parameter spacing. The amplification and truncation constants are exact for equally spaced points. The step counts are deterministic for a given run. Unequal spacing, weighted fits, and higher degrees are not measured.

The claim that has to fail

The claim is that the least-squares line through five answers is the better start because it amplifies stored error less than the line through two. Over the thirty runs it takes 1,772 inner steps against the line through two’s 1,669. The refusal is fed the claim that the fitted line takes fewer, and fails.

Still open: fits in the rule, weights that decay, and correlated error

A residual rule over better candidates. The previous essay’s residual rule chose between the line through two and the parabola through three. The map above suggests a better pair on this family: the line fitted to four or five and the parabola through three, which between them hold or come within a step of the best start in 25 of the 30 cells. Whether a residual rule over that pair reaches the best-of-eight total of 1,154, and whether the free rule’s threshold still means anything when one candidate is a fit, is one sweep of the same grid.

Weights that decay with age. A least-squares fit counts the oldest stored answer as heavily as the newest, which is where its truncation constant comes from. A weighted fit whose weights fall with age sits between the interpolant and the flat fit on the trade figure, and could be tuned to the stored error if the stored error were known — which the last correction of each member estimates for free.

The correlation. On the straight path the fits help less than their coefficient norms predict, and the explanation offered is that the stored errors are correlated from member to member. Measuring that correlation directly — the error of each stored answer against the error of the one before — would say how much of the amplification figure survives contact with a real sequence, and whether a rebuilt factorisation, which starts a fresh chord iteration, breaks it.

Where this goes next

010203040run, by bend then tolerancesteps beyond the better fixed degreestraightbend 10⁻⁵bend 10⁻⁴bend 0.001bend 0.01bend 0.1● second difference ■ residual at both ○ wrong fixed degreethirty runs: steps beyond the better degreesecond difference: runs matching the better degree, of 3026second difference: worst excess, steps5residual at both: runs matching the better degree, of 3029residual at both: extra residuals, in steps4.5wrong fixed degree: worst excess, steps35zero is the better degree, known in advanceeach group of five is one bend The degree the history chooses A sequence of solves can start each member from the line through its last two answers or the parabola through its last three, and which is better depends on how much its path bends — which a code does not know. Over thirty runs of bend and tolerance, always taking the line costs 456 inner steps more than the better choice; always taking the parabola costs 33. A free rule reading the stored answers closes that to 11. A rule that evaluates the residual at both starts picks the better one on 29 runs of 30, and pays 135 steps for the evaluations. 10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶050100150200250relative residual tolerance of every solveinner steps over twenty membersprevious answerline, last twoparabola, last threea straight path, twenty members, drift 0.02tolerance 10⁻⁶: previous answer62tolerance 10⁻⁶: line11tolerance 10⁻⁶: parabola17tolerance 10⁻¹⁰: previous answer160tolerance 10⁻¹⁰: line12tolerance 10⁻¹⁰: parabola14tolerance 10⁻¹⁴: previous answer261tolerance 10⁻¹⁴: line17tolerance 10⁻¹⁴: parabola23tighter to the lefteach point is a whole run of twenty A straight path has nothing for a parabola to fit The line through the last two answers beat the parabola through the last three on a drifting sequence, and the reason offered was that the parabola amplifies the stored answers' error. Tightening the solve tolerance from 10⁻⁶ to 10⁻¹⁴ should have reversed that, and it does not: the line needs 7 to 18 inner steps over twenty members at every tolerance and the parabola 14 to 23. The sequence's roots move along a straight line, so the line is exact and there is nothing else to fit. Bend the path by a part in ten thousand and the parabola wins below 10⁻⁹, by 105 steps to 75 at 10⁻¹⁴. 08162432404810⁻¹10²10⁵10⁸10¹¹10¹⁴10¹⁷10²⁰degreeκ of the design matrix1/u: past this a double holds nothingmonomialsChebyshevArnoldi on the pointsκ at degree 48monomials1.5·10¹⁷Chebyshev1.6·10⁷Arnoldi on the points1200 two intervals with a gap between themthree bases for one space of polynomials A basis built from the points A polynomial fit computed in monomials and in an orthogonal basis gives the same curve on exact data, and the valley essay drew the two lying on top of each other. Add 0.1% noise and they separate — by 1.7·10⁻⁵ at degree 40 and 0.004 at degree 48 — because the fitted curve moves with the basis by its condition number times the rounding times the residual. Chebyshev polynomials keep that small only on points spread like their weight; on a sample with a hole in it they reach κ = 1.55·10⁷. A basis orthogonalised against the sample points themselves stays at 1 on every set.

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 errorCholesky factorisationExtrapolationFlop countLeast-squaresNewton iterationStopping criterionWarm start