Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Discretisation error — where it appears

The part of a computed answer's error that comes from replacing a continuous problem by a finite one, before any noise or rounding enters. It shrinks as the grid is refined, and on an ill-posed problem the refinement that shrinks it also admits components the data cannot support.

Named by 4 essays across 2 fields — each of them below, with the objects they name alongside it.

1216202428323640444810⁻¹110¹10²grid points nrelative error against the continuous signalbest truncation, 0.117best grid: n = 26best K = 28with noisenoise-freeno λ anywhere in this curvebest grid, error0.13best truncation, error0.12κ on the best grid61grid where it has doubled34every point is an unregularised solvethe grid chose the truncation

The grid was the first filter

A continuous deconvolution discretised on n points and solved with no regularisation at all is not unregularised. Its error against the continuous signal is least at 24, 26 and 34 points for noise of 1%, 0.1% and 0.01% per sample — beside best truncations of 24, 28 and 32 components on a 64-point grid — and within 4 to 16 per cent of their error. The grid's own filter factors sum to n exactly and fall through a half at k = n. Choosing the grid was choosing a truncation, before anybody chose a λ.

regularisation · Regularisation 10141822263034384210⁻¹10⁻⁰.⁵110⁰.⁵grid points nrelative error against the continuous signalsampled kernel, hatsintegrated, hatsintegrated, spline0.1% noise, no λsampled kernel, hats, best0.13integrated, hats, best0.12integrated, spline, best0.12truncation of 64 points0.12same nodal unknowns, same databetter at representing the noise too

A better discretisation is a weaker filter

A coarse grid's error has two sources — how well the discrete operator approximates the integral, and how well the grid's function represents the answer — and the grid essay could not separate them. Changed one at a time they separate: integrating the kernel against the hat functions takes a fifth off the 12-point error, reading the answer as a cubic spline takes 15 per cent more, and both roughly double the condition number on every grid. At 0.1% noise the spline discretisation's unregularised solve on 26 points reaches the best truncation of a 64-point grid to 0.3%. At 1% it is worse than the crude grid.

regularisation · Regularisation 1220283644526068768492100101214161820grid points nrelative error against the continuous signal, per centsampled kernel, hatsintegrated, hatsintegrated, splinespline, no λ1% noise per sample, median of sixteen drawssampled kernel, hats: 16 points0.18integrated, hats: 16 points0.16integrated, spline: 16 points0.16sampled kernel, hats: 96 points0.14integrated, hats: 96 points0.14integrated, spline: 96 points0.14spline, no λ, its best grid0.15dotted: the 96-point answerevery point is a grid with its own λ

The grid on which the discretisation stops mattering

Without regularisation, integrating the blur's kernel against cubic splines beat sampling it at 0.1% noise and lost to it at 1%. Give each discretisation its own best λ on every grid and the difference shrinks to nothing where grids are fine — 0.17, 0.28 and 0.20 per cent apart on 96 points at the three noise levels, with every discretisation choosing the same λ — and stays at 17 to 18 per cent on 16 points. The choice between them is a choice of how coarse a grid can be: at 0.1% noise the integrated discretisations reach the fine-grid answer on 26 points and the sampled one needs 40.

regularisation · Regularisation 00.250.50.75100.51xuexact & tunedupwindcentralone of these is exacttuned, worst nodal error2.4·10⁻¹⁷upwind, worst nodal error0.14central, points outside [0, 1]16exact at every nodeand only at the nodes

The diffusion that makes the answer exact

Upwinding adds h/2 of artificial diffusion. Central differencing adds none. Add ε·ξ·Pe with ξ = coth(Pe) − 1/Pe and the computed solution is the exact one at every grid point, to 2.4·10⁻¹⁷ — at every Péclet number, on the problem it was derived from and on no other.

iterative · Convection

Named alongside it

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

Condition numberDeconvolutionDiscretisationFilter factorsIll-posed problemQuadratureRegularisationTruncated SVDArtificial diffusionBoundary layerConvection diffusionM-matrix

All concepts