Every PDE solver in this module, and Stam’s fluid solver too, starts by replacing a derivative with arithmetic on a handful of stored numbers. In 9.2 The Heat (Diffusion) Equation we wrote and in 9.6 Laplace's Equation: Rectangles & Disks we averaged four neighbours, both on trust. This lesson earns them: we derive each formula from Taylor series, find how wrong it is and how that shrinks with the spacing, turn stencils into matrices, handle the domain’s edges, and finish with the measurement habit that separates a working solver from a plausible one, the grid-convergence study.
Transcript
- Every solver in this module starts by replacing a derivative with arithmetic on stored numbers. Keep the function only at the points x i equals i h: a grid function. A derivative becomes a stencil, a short list of weights applied to nearby entries, the same at every point. In 2D, the grid function is a table.
- Where do the weights come from? Taylor series. Expand f of x plus h and solve for f prime: that is the forward difference, plus a first neglected term, a half h f double prime. That is the truncation error. It shrinks like h: first order.
- Subtract the expansions of f of x plus h and f of x minus h and the even powers cancel: the central difference, error one sixth h squared f triple prime, second order. Add them instead and the odd powers cancel, giving the second derivative, with error one twelfth h squared times the fourth derivative.
- Test it on sine at x equals 1 with h equal to 0.01. Forward errs by minus 4.216 times 10 to the minus 3, order 1.00. Central: minus 9.005 times 10 to the minus 6, order 2.00. Five-point: minus 1.801 times 10 to the minus 10, order 4. Taylor predicted these errors.
- One recipe handles every stencil. Demand that the moments m k equal d factorial at k equals d, and zero otherwise. Offsets 0, 1 and 2 give weights minus three halves, 2, minus one half. The first failing moment names the error; the order is k minus d. Offsets plus and minus 2 give the five-point formula, fourth order.
- Or measure the order. If the error is about C h to the p, halving h divides it by 2 to the p. For the central difference, the errors 9.0 times 10 to the minus 4, 2.25 times 10 to the minus 4 and 5.63 times 10 to the minus 5 have ratios of 4.00, so p equals 2.00.
- But round-off bites. Truncation falls with h while round-off, divided by h, rises, so the error is a V. For the central difference it bottoms out near h equal to 1.0 times 10 to the minus 5, with error near 9 times 10 to the minus 12. Higher order lets you use a bigger step and get a better answer.
- In 2D, add the second differences in x and y: the four neighbours minus 4 times the centre, over h squared. Factor out the 4 and it is the neighbour average minus the centre, times 4 over h squared. For sine x sine y at 1, 1, errors of 1.18 times 10 to the minus 3 and 2.95 times 10 to the minus 4 at h equals 0.1 and 0.05 give a ratio of 4.0.
- At an edge a stencil has no neighbours. Dirichlet values are known, so they move to the right-hand side. For Neumann, invent a ghost cell beyond the edge, valued so the central formula gives the slope g, and substitute it into the ordinary stencil. For g equal to 0 this is the heat lesson's end-node rule, and now you know where the 2 came from.
- Does it matter? Solve u double prime equals e to the x with u prime of 0 equal to 1. The ghost cell gives maximum error 3.5 times 10 to the minus 3 at N equals 8 and 1.38 times 10 to the minus 5 at N equals 128: order 2.00. A one-sided row starts at 6.6 times 10 to the minus 2, with order 1.00. One row costs a full order.
- Stack the grid function into a vector and the stencil becomes a matrix. Its eigenvectors are sampled sines, with eigenvalues minus 4 over h squared times sine squared of k pi h over 2. For n equals 7, lambda 1 is -9.743 against -9.870, but lambda 7 is -246.26 against -483.6: smooth modes are resolved, wiggly ones are not. The largest magnitude sits near 4 over h squared: 256.
- With no exact answer you refine the grid and watch the error; first, try a known one. For n equals 7, 15, 31 and 63, the maximum errors are 1.295 times 10 to the minus 2, 3.219 times 10 to the minus 3, 8.036 times 10 to the minus 4 and 2.008 times 10 to the minus 4: order 2. If you miss your designed order, suspect a boundary row first.
- Stam's solver is built from these stencils, with solid walls as Neumann ghost cells. To recap: Taylor series gives each formula and order, moments give any stencil, the five-point Laplacian is the neighbour average, ghost cells keep walls second order, and the observed order catches bugs.
- Next, explicit heat. Write u x x as the matrix A and march in time. Its most negative eigenvalue is near minus 4 over h squared, so explicit Euler needs delta t times lambda no less than minus 2. That is the r at most one half limit you met in the heat lesson.
Grids and grid functions
Choose a spacing and keep the function only at the points . The list is a grid function: a vector with one entry per grid point. Everything that follows is arithmetic on this vector. A derivative, which needs a limit, becomes a stencil: a short list of weights applied to nearby entries, the same weights at every point. In 2D the points are and the grid function is a table , which we can also unroll into one long vector.
Two words to keep straight. The truncation error of a formula is its distance from the true derivative when handed exact samples of a smooth function: the cut-off Taylor tail. The discretization error of a solver is the distance of the computed grid values from the true solution. The first predicts the second, but they are different numbers, and we measure both.
Deriving formulas from Taylor series
The tool is 2.4 Taylor Series in One and Several Variables: for a smooth ,
with everything on the right evaluated at . Solve for :
This is the forward difference, and the first neglected term, , is its truncation error. It shrinks in proportion to : first order. Replace by to get the backward difference , with leading error . The signs differ, so average the two samples’ information instead: subtract the expansions of and . The even powers cancel and
the central difference: second order, and no more expensive. For the second derivative, add the two expansions. Now the odd powers cancel:
Worked example. Take at , so , , . At the forward difference should err by about and the central difference by . The lab below, in double precision, reports and (the forward one is a hair off because the next term is not zero). Taylor predicted the computed error.
Any stencil: the moment equations
A better recipe handles all cases at once. Pick sample points , with offsets such as , and look for weights so that . Expand every sample in a Taylor series. The coefficient of is , so we need the moments to equal for and zero for every other we can afford. With points we can impose , a small linear system (a Vandermonde matrix) for the weights.
For offsets and : , , (the row, with the divided out). The solution is : . The first moment that fails, its target, names the error: here, so the error is . In general, if is the first failing moment the error is and the order is . Symmetric stencils get a free bonus order. Take the central difference: its weights satisfy (three equations, and the one holds by symmetry), the first failure is , and the order is . Adding gives the five-point formula with weights , error : fourth order.
Measuring order, and the round-off floor
You can measure the order instead of trusting the derivation. If the error is then , so
This is the step-halving test of 4.1 Local Error, Global Error & Order, now on a derivative. For the central difference of at the errors are , , for : ratios , so .
Shrinking forever does not keep helping. Each sample carries a relative rounding error of about , and the formula divides the sum by , so round-off contributes roughly : it grows as shrinks, like for a first derivative and for a second. The truncation error falls, the round-off error rises, and the total error is a V on a log-log plot with a jagged floor on its left. They meet at
For the central difference of at this gives , with a best error near (the playground prints errors of at and at , climbing from there). The forward difference bottoms out near at about . The five-point formula has and best error : higher order lets you use a bigger step and get a better answer. The second derivative is worse, and best error , because amplifies round-off more.
The lab
The top strip shows the weights the moment equations give for the ticked points; below is the double-precision error, the dashed red round-off model, and three dots at , , whose fitted slope is in the readout.
- Central, at , . Weights . The readout predicts the error and the computed error agrees; fitted slope .
- Forward. Same : weights , predicted against computed , slope .
- Five-point. Weights , error at and slope .
- Slide left to and below. The curve leaves the slope line and follows the red line up; the readout gives the quoted above.
- Change the function to . Now the central difference errs by , , at (slopes , ), but the forward difference is wrong by at and still at : the constant is huge, and the asymptotic regime starts at a much smaller . The five-point formula gives , , .
- Build your own. Choose the second derivative and tick : weights , but order (error coefficient ). Now also tick : the weight on comes out exactly , and you are back at the central formula. For , ticking gives weights and order .
The 2D five-point Laplacian
Apply the second-difference formula in and in and add:
The truncation error is , second order. Factor out the :
That is the reading from 2.11 The Laplacian & Vector Identities made exact: the discrete Laplacian is the neighbour average minus the centre, scaled by . It is why Laplace’s equation says “every value is the average of its neighbours”, and why one explicit heat step with is the Jacobi sweep. Check numerically: for at the exact value is ; the stencil gives at and at , errors and , a ratio of , and the prediction at matches.
The stencil ignores the diagonal neighbours: it treats and separately, so (from memory) it is slightly anisotropic, an effect that shows up in wave problems later.
Boundary conditions
A stencil needs neighbours, and at the edge there are none. Two cases.
Dirichlet ( given). The boundary values are known, so they are not unknowns; the one in the first interior row moves to the right-hand side: for with , . No accuracy is lost.
Neumann ( given). The boundary value is now unknown, so we need the equation at itself, which needs a value that is not on the grid. The ghost cell is a fictitious point beyond the edge, whose value we choose to satisfy the boundary condition with the central formula: , so . Substitute it into the ordinary stencil at :
With (insulated) this is the end-node rule of the heat lesson: now you know where the came from. The tempting shortcut, enforcing directly, uses a first-order formula, and a first-order error at one node spreads through the solution. Test on on with , (exact ): the ghost-cell version has maximum error at and at , observed order ; the one-sided version starts at and has observed order at . The whole answer falls a full order because of one boundary row.
When a boundary cuts between grid points, as with the disk of the last lesson, the stencil has arms of unequal length and : (the moment-equation solution for offsets ). It is only first order, with error , checked numerically.
From stencils to matrices
Stack the grid function into a vector with Dirichlet ends. Applying the three-point stencil at every point is multiplication by
so “differentiate twice” has become and the BVP the linear system . In 2D the unrolled vector has entries and the matrix is (np.kron in code), five nonzeros per row.
The matrix is also the doorway to 1.5 Eigenvectors & Eigenvalues. Its eigenvectors are sampled sines , and its eigenvalues have a closed form,
The exact operator multiplies by ; the grid uses a smaller number. For , : against , but against . Smooth modes are resolved, wiggly ones are not. The largest magnitude is always close to ( against at ; against at ). Remember : it is the stiffness of 4.5 Stability Regions & Stiffness, and the next lesson turns it into a time-step limit.
Grid-convergence studies
A real solver has no exact answer to compare with, but solving on grids , , and watching the changes still tests it. First do it with a known solution: , , exact . The maximum errors for interior points are , , , , with observed orders , , . The discretization error has the same order as the truncation error.
In 2D, the Poisson problem with has errors , , for and observed order . (A tempting test is , but it is an exact eigenvector of the grid matrix, so its error is just the eigenvalue error and is identical to the 1D numbers above, at : a good fact, a bad test.)
If you cannot reproduce the order you designed, there is a bug in the stencil, the boundary row, or the right-hand side; suspect a boundary condition first.
Computing it
The lab prints the central and five-point errors above (observed order ), the central error bottoming out near and rising after, the Laplacian errors and , and the eigenvalues twice, from the matrix and from the closed form. Dense matrices, built with plain NumPy, are fine at these sizes. Real solvers store only the five nonzeros per row (scipy.sparse is the usual tool); this lesson stays dense because is small.
Concept checks
Problems
Find the weights for using , and the order of the formula.
Show worked solution
Offsets with weights . Moment equations: , , (from , with divided out). Adding the last two gives , so , , . The formula is , the mirror image of the forward one. The moment is , so the error is and the order is . (This is the formula for the right edge of a domain.)
A code gives maximum errors , , at . Compute both observed orders and predict the error at .
Show worked solution
and . Both are near : second order. Predict . Three grids matter: a third that continues the slope rules out a pre-asymptotic accident.
At an interior point the neighbours are , , , , the centre is , and . Compute the five-point Laplacian two ways, then say what one Jacobi update would do.
Show worked solution
Direct: . By average: the average is , and . They agree. The centre sits below the average, so the Laplacian is positive. A Jacobi update replaces the centre by the average, , which makes the Laplacian there zero, as Laplace’s equation demands.
(a) Explicit Euler for is stable when for every eigenvalue of . Use to recover the limit of the heat lesson. (b) Compute the largest step for air momentum diffusion, m/s (from memory), on a cm grid, m.
Show worked solution
(a) The most negative eigenvalue is , so , i.e. . (b) s. At mm it falls to s, at mm to ms.
Key Takeaways
- A grid function is a vector of samples; a finite-difference formula is a stencil, a row of weights, applied at every point.
- Taylor series gives each formula and its error: forward and backward first derivatives are first order (error ), the central first derivative is second order (), and the central second derivative is second order ().
- Weights for any stencil come from the moment equations; the first moment that fails names the error and the order . Symmetry buys an extra order.
- The 2D five-point Laplacian is times (neighbour average minus centre), second order, with error .
- Dirichlet values move to the right-hand side; Neumann conditions use a ghost cell . A one-sided Neumann row drops the whole solution to first order.
- Stencils are matrices: the 1D matrix has eigenvalues , close to at the top.
- Measure the observed order on a refinement sequence; below round-off, growing like , takes over.
- Next, explicit time-stepping for the heat equation: write as the matrix , march in time (the method of lines), and see that the limit you met in the heat lesson is the Euler stability limit applied to the eigenvalues of .