Source: Oxford Part A, A7 Numerical Analysis, A13759W1, 24 June 2021; parent PDF pages 128–131, paper pages 1–4. These original solutions cover all three questions, all nine lettered parts and all twenty-one answer units, including every optional question. Each question carries 25 marks; the examination counted the best two answers. The local truncation error in Question 3(a) is divided by the step size. In Question 3(c), the leading coefficient of a genuine -step linear multistep method is understood to be nonzero.
For and every real ,
where was used. The mean value theorem therefore proves Lipschitz continuity in with constant .
Let . The explicit Euler method and the exact-solution identity from part (i) give
Using the requested local truncation error bound , including at , yields
Iteration and the finite geometric series give
Since and ,
Keeping the stronger bound from part (i) improves the same proof to . The requested inequality follows already from the weaker bound.
Source: Oxford Part A, A7 Numerical Analysis, A13759W1, 23 June 2023; parent PDF pages 135–137, paper pages 1–3. These original solutions cover all three questions and all eleven lettered subparts. In Question 1(d), the unrefined Gershgorin discs alone are inconclusive for the shift ; a further exact calculation resolves it. In Question 2(c), clearing denominators produces a linear system whose solution need not define a rational interpolant at every interpolation node. Question 3 uses the paper's normalized convention for the local truncation error.
Work on a fixed finite interval . Write , , and use the paper's normalized local truncation error
Assume has bounded continuous derivatives through order three on this interval, with and . Assume also that the Jacobian matrix has operator norm at most on the segments joining to the endpoint averages. For a scalar equation this last hypothesis is simply there.
Two symmetric estimates separate the errors. By Taylor's theorem applied to about , the linear term integrates to zero on , giving
Likewise the two linear terms in the endpoint expansions cancel, and their second-order remainders give
The derivative bound on gives a Lipschitz condition in its second variable. Since , the triangle inequality now yields
The constant is independent of and as long as the steps remain in the fixed interval. This implicit midpoint consistency bound proves numerical consistency of order two. The corresponding unnormalized residual is ; the two powers conventionally called local truncation error differ because the paper divides by the step size. If local error instead means the error of an exactly solved numerical step started at , the small-step Lipschitz condition gives the bound as well.
Fix the following normalization of the local truncation error, also called the consistency error: insert a smooth exact solution into the linear multistep method and divide the residual by ,
Thus the unscaled defect is . Consistency of a numerical method means that uniformly over mesh points in each fixed interval for every sufficiently smooth exact solution. Write the characteristic polynomials of a linear multistep method as
By Taylor's theorem, consistency of a numerical method is equivalent to
or and .
Second-order accuracy means for smooth solutions, equivalently an unscaled local truncation error . In addition to the two consistency conditions, its order conditions require
An order of a numerical method of exactly two additionally requires that the next order condition fails. These statements concern the local defect; a second-order global error requires stability and suitably accurate starting values as well.
Substitute a smooth exact solution into the linear multistep method and expand about . Its residual is
Consistency of a numerical method requires the coefficients of and to vanish. Therefore and , giving the unique choice
For this choice the next coefficient is , so the residual is . The normalized local truncation error, obtained by dividing the residual by , is . Hence the method has order one.
Use the normalized local truncation error
The Taylor theorem expansions about are
Substitution gives exactly
Thus the theta method has order two exactly for , and otherwise order one, as a statement about the method on a sufficiently smooth class of problems. The leading term vanishes at one half, and a function with nonzero third derivative shows that the next term does not vanish universally. As usual, a uniform order estimate assumes bounded relevant derivatives; mere existence of on the open interval gives the stated pointwise remainders but not, by itself, a uniform bound. Special exact solutions can of course have zero truncation error even for a first-order method.
Put . Subtracting the numerical update from the exact update with its local truncation error gives
The Lipschitz condition in the solution variable and the triangle inequality imply
The assumed positive denominator permits division. With and , repeated substitution of this Lipschitz one-step error bound yields
Here because , so the displayed geometric series quotient is well defined. For implicit steps, the same condition makes the scalar update map a contraction mapping, ensuring a unique numerical next value.
In the normalization used by the supplied coefficient expansion, the local truncation error of the linear multistep method is
The nonzero sum in the denominator is an explicit hypothesis. Consistency of a numerical method requires uniformly on a fixed finite time interval for every sufficiently smooth exact solution as . Equivalently, the two polynomial identities are
These follow by inserting constant and affine functions, or by setting the first two Taylor coefficients to zero.
The five-point equations for the Poisson equation are
with prescribed boundary values. If , an interior maximal value is at most the average of its four neighbours. Since no neighbour exceeds the maximum, equality forces all four to equal it. Repeating along adjacent nodes propagates that value to the boundary. Thus the discrete maximum principle gives , in particular the usual positive-maximum bound with zero included.
For an error estimate assume the exact solution has bounded continuous fourth partial derivatives up to the boundary. The local truncation error then satisfies by the Taylor theorem. Put , so and on boundary nodes. The Discrete Poisson barrier on a square
satisfies exactly, on the grid boundary, and . Set . Then , with nonpositive boundary values. Applying the discrete maximum principle twice gives
For nonzero smooth Dirichlet boundary data , impose at the boundary nodes. The error still vanishes there, so the same argument and order apply, under the same fourth-derivative regularity of the exact solution. Smooth boundary values alone do not remove every possible corner-regularity issue.
Define the one-step local truncation error as the defect obtained by inserting the exact solution into an update:
For a smooth solution, Taylor's theorem and give
Thus for the one-step defect convention. The leading derivative can also be written by the chain rule.
Some conventions instead call the truncation error. That normalized local truncation error is , so under the normalized convention. Both describe the same Euler one-step defect; neither should be confused with an unqualified global error claim.
Consider a one-step stencil with new-level coefficients , and at offsets , and old-level coefficients , at offsets . For , its exact-solution residual starts at fourth degree with coefficient . Thus its normalized local truncation error is third order at fixed nonzero Courant number, except at the exact-shift values ; zero gives the zero-step identity. For its Fourier symbol, . Uniformly invertible stable steps occur for , or .
Richardson extrapolation 2026-10-14
Richardson extrapolation improves an approximation by combining two resolutions so that their leading truncation errors cancel. The useful surprise is that the size of that leading error need not be known: its scaling under refinement is enough. This lets an existing finite difference method or quadrature rule produce a more accurate answer from two runs, without first deriving a new method from scratch.
Suppose approximates a fixed limit as the positive resolution parameter tends to zero, with an asymptotic expansion
Here is known, is independent of , and denotes Big O notation. The same asymptotic expansion, with the same , must describe both and . Nested grids make it natural to reuse samples, although nesting itself does not establish this error model. Define the linear combination
The weights sum to one, preserving , while . Thus Richardson extrapolation gives : the next available term in the asymptotic expansion determines the improved order. Justin Solomon's numerical analysis text develops this cancellation for finite differences and applies it to numerical integration.[ref]
Geometrically, regard the approximation as a function of . Its first two terms are a straight line . The two computed points lie at positive ; extending the line through them to gives . This is why the operation is extrapolation: it estimates a value outside the sampled parameter interval. The remaining curvature corresponds to the uncancelled terms of the asymptotic expansion.
Worked example: a centered derivative of sine. For the smooth function , the exact derivative at is . The centered difference quotient, a central finite difference, is
The Taylor series of sine gives the signed truncation error
Thus , and . Halving divides the leading truncation error by four. Combining the two centered difference quotients with Richardson extrapolation gives
Indeed, the coefficient becomes ; the coefficient vanishes. This is the even-power case of Richardson extrapolation discussed in Persson's authored lecture notes.[ref]
For and , the actual computations are
The absolute error drops from about for to for , an improvement by roughly a factor of 498. Refining again gives , whose absolute error is about . The refined truncation errors decrease by nearly four for and nearly sixteen for , reflecting their second and fourth orders.
Figure 1.
Centered sine derivative errors: second order before Richardson extrapolation and fourth order after cancellation
. Source. Details.
The logarithmic scale on each axis turns power laws into straight lines. The dashed reference curves are and , the magnitudes of the leading truncation errors. The plotted errors are computed with 70-digit decimal arithmetic, rather than clipped to a display floor; this isolates the asymptotic expansion from roundoff error.
Worked example: integrating an exponential. Approximate the definite integral of the exponential function on :
For numerical integration, the composite trapezoidal rule adds the areas of trapezoids between successive samples; this is the quadrature use of the endpoint average that also occurs in the ODE trapezoidal rule. On equal intervals, with , define
Summing the geometric series gives . Expanding the exponential function near zero yields
The leading truncation error again has , . On the uniform nested grids with and intervals, Richardson extrapolation therefore gives
This linear combination is exactly composite Simpson's rule on the finer grid, whose spacing is . On each coarse panel, an old endpoint receives weight and the new midpoint weight ; shared old endpoints receive weight . These are the usual Simpson's rule weights multiplied by . The equivalence is explained directly in LeMesurier's university notes.[ref]
For two coarse panels and four fine panels,
The absolute errors are about , and , respectively. Reusing the fine-grid samples makes Richardson extrapolation especially attractive here: the resulting Simpson's rule needs no samples beyond those already used by .
Figure 2.
Exponential quadrature on nested grids: trapezoidal areas, reused sample nodes, and the fourth-order Simpson combination
. Source. Details.
When the improvement is justified. Richardson extrapolation requires the stated asymptotic expansion and the correct positive . If the actual leading exponent is , its coefficient after combination is , so the leading truncation error generally remains. Merely knowing does not supply a common coefficient or a higher-order remainder. A discontinuity of a function, a singular endpoint, or unrelated changes between grids can invalidate the assumed asymptotic expansion; refinement alone does not guarantee improvement for every numerical problem.
Roundoff error and errors in the sampled values survive the cancellation of truncation error. If the coarse and fine values have absolute perturbations bounded by , the perturbation in is bounded by ; for this is . In floating-point arithmetic, a centered difference quotient can also amplify sample errors through division by , so an indefinitely smaller need not be more accurate. Persson's notes describe this balance between truncation error and roundoff error.[ref]
The same cancellation idea appears in step-doubling error estimation. For an order- one-step method for an ordinary differential equation, two half steps each contribute local truncation error of order , so their accumulated leading local error has ratio to one full step. This explains the denominator there; the appropriate exponent follows from that local error model, rather than automatically from a generic use of Richardson extrapolation.
Simpson multistep method 2026-10-14
Integrating a quadratic interpolant of the derivative over two steps gives this linear multistep method, which has order four. Its local truncation error is and its zero-stability polynomial is , with simple roots . The Dahlquist equivalence theorem therefore gives fourth-order convergence with sufficiently accurate starts. This attains the even two-step first Dahlquist barrier. Its undamped parasitic zero-step mode need not have favorable long-time absolute stability; finite-time convergence and stiff damping are separate requirements.
Strang splitting Created 2026-09-28 Updated 2026-11-05
For finite matrices , Strang splitting approximates the evolution by
It advances the dynamics for a half step, the dynamics for a full step, and the dynamics for a half step. Expanding the three matrix exponentials gives
so the one-step local truncation error is . Bounded propagation on a fixed time interval gives global error . The identity expresses time symmetry. Commuting matrices make the product exact.[ref]
The finite-matrix assumptions are relevant when the method is applied after a spatial semidiscretization. Error constants can depend on the spatial mesh through commutators. A fixed-matrix second-order argument alone does not prove an error estimate uniform over increasingly fine spatial grids.
For , write an amplification root as . Its equation is . The roots have modulus one and a positive frequency-uniform separation exactly for , giving L2 norm stability through a uniformly bounded diagonalization. At either endpoint the Nyquist symbol has a repeated unit root and a Jordan block, producing linear growth. The normalized local truncation error is generally second order; at and exactly sampled characteristics solve the recurrence, although the latter parameter is unstable for arbitrary perturbations.