Flow Lab

Syllabus / Module 10: Numerical Methods for PDEs

Lesson 10.1

Finite Differences: Discretizing Derivatives

Grids, stencils, deriving FD formulas from Taylor series, truncation error, the discrete Laplacian, and grid convergence studies.

Written byClaude Sonnet

🌊
Why this matters for simulation: Every grid-based fluid solver (including Stam's) is built from these stencils.

By the end of this lesson you can…

  • Describe a grid function as a vector of samples and read a stencil as a row of weights applied to it.
  • Derive the forward, backward and central first-derivative formulas and the central second-derivative formula from Taylor series, with the leading truncation error and the order of each.
  • Solve the moment equations to find the weights of any stencil, and predict its order and error coefficient.
  • Build the 1D three-point and 2D five-point Laplacians as matrices, and say why the five-point stencil is the neighbour average minus the centre, over $h^2/4$.
  • Impose Dirichlet and Neumann conditions with known values and ghost cells, and explain why a one-sided Neumann condition costs a whole order.
  • Run a grid-convergence study: measure the observed order from errors at $h$, $h/2$, $h/4$, and recognise the round-off floor at tiny $h$.
On this page
·
  1. Grids and grid functions
  2. Deriving formulas from Taylor series
  3. Any stencil: the moment equations
  4. Measuring order, and the round-off floor
  5. The lab
  6. The 2D five-point Laplacian
  7. Boundary conditions
  8. From stencils to matrices
  9. Grid-convergence studies
  10. Computing it
  11. Concept checks
  12. Problems
  13. Key Takeaways

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 uxx≈(ui+1−2ui+ui−1)/Δx2u_{xx} \approx (u_{i+1} - 2u_i + u_{i-1})/\Delta x^2 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.

▶ Video Samples on a grid, stencils built from Taylor series, truncation error and order, the five-point Laplacian, ghost cells, and a convergence studycaptions only
Transcript
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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 hh and keep the function only at the points xi=ihx_i = ih. The list ui=u(xi)u_i = u(x_i) 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 (xi,yj)=(ih,jh)(x_i, y_j) = (ih, jh) and the grid function is a table ui,ju_{i,j}, 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 ff,

f(x+h)=f+hf′+12h2f′′+16h3f′′′+124h4f′′′′+⋯f(x+h) = f + hf' + \tfrac12 h^2 f'' + \tfrac16 h^3 f''' + \tfrac1{24}h^4 f'''' + \cdots

with everything on the right evaluated at xx. Solve for f′f':

f(x+h)−f(x)h=f′+12hf′′+16h2f′′′+⋯\frac{f(x+h) - f(x)}{h} = f' + \tfrac12 h f'' + \tfrac16 h^2 f''' + \cdots

This is the forward difference, and the first neglected term, 12hf′′\tfrac12 hf'', is its truncation error. It shrinks in proportion to hh: first order. Replace hh by −h-h to get the backward difference (f(x)−f(x−h))/h(f(x) - f(x-h))/h, with leading error −12hf′′-\tfrac12 hf''. The signs differ, so average the two samples’ information instead: subtract the expansions of f(x+h)f(x+h) and f(x−h)f(x-h). The even powers cancel and

f(x+h)−f(x−h)2h=f′+16h2f′′′+⋯\frac{f(x+h) - f(x-h)}{2h} = f' + \tfrac16 h^2 f''' + \cdots

the central difference: second order, and no more expensive. For the second derivative, add the two expansions. Now the odd powers cancel:

f(x+h)−2f(x)+f(x−h)h2=f′′+112h2f′′′′+⋯\frac{f(x+h) - 2f(x) + f(x-h)}{h^2} = f'' + \tfrac1{12}h^2 f'''' + \cdots

Worked example. Take f=sin⁡xf = \sin x at x=1x = 1, so f′=cos⁡1=0.5403f' = \cos 1 = 0.5403, f′′=−sin⁡1f'' = -\sin 1, f′′′=−cos⁡1f''' = -\cos 1. At h=0.01h = 0.01 the forward difference should err by about 12hf′′=−0.005sin⁡1=−4.207×10−3\tfrac12 hf'' = -0.005\sin 1 = -4.207\times10^{-3} and the central difference by 16h2f′′′=−9.005×10−6\tfrac16 h^2 f''' = -9.005\times10^{-6}. The lab below, in double precision, reports −4.216×10−3-4.216\times10^{-3} and −9.005×10−6-9.005\times10^{-6} (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 x+ojhx + o_jh, with offsets ojo_j such as −1,0,1-1, 0, 1, and look for weights wjw_j so that ∑jwjf(x+ojh)/hd≈f(d)(x)\sum_j w_j f(x + o_jh)/h^d \approx f^{(d)}(x). Expand every sample in a Taylor series. The coefficient of f(k)f^{(k)} is hkk!∑jwjojk\frac{h^k}{k!}\sum_j w_j o_j^k, so we need the moments mk=∑jwjojkm_k = \sum_j w_jo_j^k to equal d!d! for k=dk = d and zero for every other kk we can afford. With nn points we can impose k=0,…,n−1k = 0, \dots, n-1, a small linear system (a Vandermonde matrix) for the nn weights.

For offsets 0,1,20, 1, 2 and d=1d = 1: w0+w1+w2=0w_0 + w_1 + w_2 = 0, w1+2w2=1w_1 + 2w_2 = 1, w1+4w2=0w_1 + 4w_2 = 0 (the k=2k = 2 row, with the 12\tfrac12 divided out). The solution is w=(−32,2,−12)w = (-\tfrac32, 2, -\tfrac12): (−3f0+4f1−f2)/2h(-3f_0 + 4f_1 - f_2)/2h. The first moment that fails, mk≠m_k \ne its target, names the error: m3=−2m_3 = -2 here, so the error is m33!f′′′h2=−13h2f′′′\tfrac{m_3}{3!}f'''h^2 = -\tfrac13 h^2 f'''. In general, if kk is the first failing moment the error is mkk!f(k)hk−d\frac{m_k}{k!}f^{(k)}h^{k-d} and the order is p=k−dp = k - d. Symmetric stencils get a free bonus order. Take the central difference: its weights −12,0,12-\tfrac12, 0, \tfrac12 satisfy k=0,1,2k = 0, 1, 2 (three equations, and the k=2k=2 one holds by symmetry), the first failure is k=3k = 3, and the order is 3−1=23 - 1 = 2. Adding ±2\pm2 gives the five-point formula (f−2−8f−1+8f1−f2)/12h(f_{-2} - 8f_{-1} + 8f_1 - f_2)/12h with weights 112,−23,0,23,−112\tfrac1{12}, -\tfrac23, 0, \tfrac23, -\tfrac1{12}, error −130h4f(5)-\tfrac1{30}h^4f^{(5)}: fourth order.

Measuring order, and the round-off floor

You can measure the order instead of trusting the derivation. If the error is e(h)≈Chpe(h) \approx Ch^p then e(h)/e(h/2)≈2pe(h)/e(h/2) \approx 2^p, so

pobs=log⁡2e(h)e(h/2).p_{\text{obs}} = \log_2 \frac{e(h)}{e(h/2)} .

This is the step-halving test of 4.1 Local Error, Global Error & Order, now on a derivative. For the central difference of sin⁡\sin at x=1x = 1 the errors are 9.0×10−49.0\times10^{-4}, 2.25×10−42.25\times10^{-4}, 5.63×10−55.63\times10^{-5} for h=0.1,0.05,0.025h = 0.1, 0.05, 0.025: ratios 4.004.00, so pobs=2.00p_{\text{obs}} = 2.00.

Shrinking hh forever does not keep helping. Each sample f(x+ojh)f(x + o_jh) carries a relative rounding error of about ε≈1.1×10−16\varepsilon \approx 1.1\times10^{-16}, and the formula divides the sum by hdh^d, so round-off contributes roughly ε∑∣wj∣∣f∣/hd\varepsilon\sum|w_j||f|/h^d: it grows as hh shrinks, like 1/h1/h for a first derivative and 1/h21/h^2 for a second. The truncation error ChpCh^p 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

h∗=(ε∑∣wj∣ ∣f∣∣Cf(k)∣)1/(p+d).h_* = \left(\frac{\varepsilon \sum|w_j|\,|f|}{|C f^{(k)}|}\right)^{1/(p+d)} .

For the central difference of sin⁡\sin at 11 this gives h∗=1.0×10−5h_* = 1.0\times10^{-5}, with a best error near 9×10−129\times10^{-12} (the playground prints errors of 1.1×10−111.1\times10^{-11} at 10−510^{-5} and 2.8×10−112.8\times10^{-11} at 10−610^{-6}, climbing from there). The forward difference bottoms out near h∗=2×10−8h_* = 2\times10^{-8} at about 9×10−99\times10^{-9}. The five-point formula has h∗=1.5×10−3h_* = 1.5\times10^{-3} and best error 9×10−149\times10^{-14}: higher order lets you use a bigger step and get a better answer. The second derivative is worse, h∗=2.7×10−4h_* = 2.7\times10^{-4} and best error 5×10−95\times10^{-9}, because 1/h21/h^2 amplifies round-off more.

The lab

◆ Interactive Tick grid points, read the weights, and watch the error against h on a log-log plot

Loading simulation…

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 hh, h/2h/2, h/4h/4 whose fitted slope is in the readout.

  1. Central, sin⁡x\sin x at x=1x=1, h=0.01h = 0.01. Weights −12,0,12-\tfrac12, 0, \tfrac12. The readout predicts the error 16f′′′h2=−9.005×10−6\tfrac16f'''h^2 = -9.005\times10^{-6} and the computed error agrees; fitted slope 2.002.00.
  2. Forward. Same hh: weights −1,1-1, 1, predicted −4.207×10−3-4.207\times10^{-3} against computed −4.216×10−3-4.216\times10^{-3}, slope 1.001.00.
  3. Five-point. Weights 112,−23,0,23,−112\tfrac1{12}, -\tfrac23, 0, \tfrac23, -\tfrac1{12}, error −1.801×10−10-1.801\times10^{-10} at h=0.01h = 0.01 and slope 4.004.00.
  4. Slide hh left to 10−510^{-5} and below. The curve leaves the slope line and follows the red line up; the readout gives the h∗h_* quoted above.
  5. Change the function to sin⁡8x\sin 8x. Now the central difference errs by 0.1200.120, 0.03080.0308, 0.007740.00774 at h=0.1,0.05,0.025h = 0.1, 0.05, 0.025 (slopes 1.971.97, 1.991.99), but the forward difference is wrong by 2.882.88 at h=0.1h = 0.1 and still 0.780.78 at h=0.025h = 0.025: the constant CC is huge, and the asymptotic regime starts at a much smaller hh. The five-point formula gives 0.01470.0147, 9.75×10−49.75\times10^{-4}, 6.18×10−56.18\times10^{-5}.
  6. Build your own. Choose the second derivative and tick 0,+1,+20, +1, +2: weights 1,−2,11, -2, 1, but order 11 (error coefficient 1⋅f′′′h1\cdot f'''h). Now also tick −1-1: the weight on +2+2 comes out exactly 00, and you are back at the central formula. For f′f', ticking −1,0,+1,+2-1, 0, +1, +2 gives weights −13,−12,1,−16-\tfrac13, -\tfrac12, 1, -\tfrac16 and order 33.

The 2D five-point Laplacian

Apply the second-difference formula in xx and in yy and add:

∇2u≈ui+1,j+ui−1,j+ui,j+1+ui,j−1−4ui,jh2.\nabla^2 u \approx \frac{u_{i+1,j} + u_{i-1,j} + u_{i,j+1} + u_{i,j-1} - 4u_{i,j}}{h^2}.

The truncation error is 112h2(uxxxx+uyyyy)\tfrac1{12}h^2(u_{xxxx} + u_{yyyy}), second order. Factor out the 44:

∇2u≈4h2(14(uE+uW+uN+uS)⏟neighbour average−ui,j).\nabla^2 u \approx \frac{4}{h^2}\Big(\underbrace{\tfrac14(u_E + u_W + u_N + u_S)}_{\text{neighbour average}} - u_{i,j}\Big).

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 4/h24/h^2. It is why Laplace’s equation says “every value is the average of its neighbours”, and why one explicit heat step u+r(sum−4u)u + r(\text{sum} - 4u) with r=14r = \tfrac14 is the Jacobi sweep. Check numerically: for u=sin⁡xsin⁡yu = \sin x\sin y at (1,1)(1,1) the exact value is −2sin⁡21=−1.41615-2\sin^2 1 = -1.41615; the stencil gives −1.41497-1.41497 at h=0.1h = 0.1 and −1.41585-1.41585 at h=0.05h = 0.05, errors 1.18×10−31.18\times10^{-3} and 2.95×10−42.95\times10^{-4}, a ratio of 4.04.0, and the prediction h212⋅2sin⁡21=1.18×10−3\tfrac{h^2}{12}\cdot2\sin^21 = 1.18\times10^{-3} at h=0.1h=0.1 matches.

The stencil ignores the diagonal neighbours: it treats xx and yy 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 (uu 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 u′′=fu'' = f with u0=au_0 = a, (u2−2u1)/h2=f1−a/h2(u_2 - 2u_1)/h^2 = f_1 - a/h^2. No accuracy is lost.

Neumann (u′=gu' = g given). The boundary value is now unknown, so we need the equation at x0x_0 itself, which needs a value u−1u_{-1} 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: (u1−u−1)/2h=g(u_1 - u_{-1})/2h = g, so u−1=u1−2hgu_{-1} = u_1 - 2hg. Substitute it into the ordinary stencil at x0x_0:

u′′(x0)≈u−1−2u0+u1h2=2u1−2u0−2hgh2.u''(x_0) \approx \frac{u_{-1} - 2u_0 + u_1}{h^2} = \frac{2u_1 - 2u_0 - 2hg}{h^2}.

With g=0g = 0 (insulated) this is the end-node rule u0←u0+2r(u1−u0)u_0 \leftarrow u_0 + 2r(u_1 - u_0) of the heat lesson: now you know where the 22 came from. The tempting shortcut, enforcing (u1−u0)/h=g(u_1 - u_0)/h = g directly, uses a first-order formula, and a first-order error at one node spreads through the solution. Test on u′′=exu'' = e^x on [0,1][0,1] with u′(0)=1u'(0) = 1, u(1)=eu(1) = e (exact u=exu = e^x): the ghost-cell version has maximum error 3.5×10−33.5\times10^{-3} at N=8N = 8 and 1.38×10−51.38\times10^{-5} at N=128N = 128, observed order 2.002.00; the one-sided version starts at 6.6×10−26.6\times10^{-2} and has observed order 1.001.00 at N=128N = 128. 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 aa and bb: u′′≈2a(a+b)uL+2b(a+b)uR−2abuu'' \approx \frac{2}{a(a+b)}u_{L} + \frac{2}{b(a+b)}u_{R} - \frac{2}{ab}u (the moment-equation solution for offsets −a,0,b-a, 0, b). It is only first order, with error 13(b−a)u′′′\tfrac13(b - a)u''', checked numerically.

From stencils to matrices

Stack the grid function into a vector u=(u1,…,un)\mathbf u = (u_1, \dots, u_n) with Dirichlet ends. Applying the three-point stencil at every point is multiplication by

A=1h2(−211−21⋱⋱⋱1−2),h=1n+1,A = \frac{1}{h^2}\begin{pmatrix} -2 & 1 & & \\ 1 & -2 & 1 & \\ & \ddots & \ddots & \ddots \\ & & 1 & -2 \end{pmatrix}, \qquad h = \frac1{n+1},

so “differentiate twice” has become u↦Au\mathbf u \mapsto A\mathbf u and the BVP u′′=fu'' = f the linear system Au=fA\mathbf u = \mathbf f. In 2D the unrolled vector has n2n^2 entries and the matrix is A⊗I+I⊗AA\otimes I + I\otimes A (np.kron in code), five nonzeros per row.

The matrix is also the doorway to 1.5 Eigenvectors & Eigenvalues. Its eigenvectors are sampled sines sin⁡(kπxi)\sin(k\pi x_i), and its eigenvalues have a closed form,

λk=−4h2sin⁡2kπh2,k=1,…,n.\lambda_k = -\frac{4}{h^2}\sin^2\frac{k\pi h}{2}, \qquad k = 1, \dots, n.

The exact operator multiplies sin⁡kπx\sin k\pi x by −(kπ)2-(k\pi)^2; the grid uses a smaller number. For n=7n = 7, h=18h = \tfrac18: λ1=−9.743\lambda_1 = -9.743 against −π2=−9.870-\pi^2 = -9.870, but λ7=−246.26\lambda_7 = -246.26 against −(7π)2=−483.6-(7\pi)^2 = -483.6. Smooth modes are resolved, wiggly ones are not. The largest magnitude is always close to 4/h24/h^2 (256256 against 246.26246.26 at n=7n=7; 6553665536 against 65526.165526.1 at n=127n = 127). Remember 4/h24/h^2: 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 hh, h/2h/2, h/4h/4 and watching the changes still tests it. First do it with a known solution: u′′=−π2sin⁡πxu'' = -\pi^2\sin\pi x, u(0)=u(1)=0u(0) = u(1) = 0, exact u=sin⁡πxu = \sin\pi x. The maximum errors for n=7,15,31,63n = 7, 15, 31, 63 interior points are 1.295×10−21.295\times10^{-2}, 3.219×10−33.219\times10^{-3}, 8.036×10−48.036\times10^{-4}, 2.008×10−42.008\times10^{-4}, with observed orders 2.0082.008, 2.0022.002, 2.00052.0005. The discretization error has the same order as the truncation error.

In 2D, the Poisson problem with u=x2(1−x)2y2(1−y)2u = x^2(1-x)^2y^2(1-y)^2 has errors 2.18×10−42.18\times10^{-4}, 5.44×10−55.44\times10^{-5}, 1.36×10−51.36\times10^{-5} for n=7,15,31n = 7, 15, 31 and observed order 2.002.00. (A tempting test is u=sin⁡πxsin⁡πyu = \sin\pi x\sin\pi y, 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, 0.012950.01295 at n=7n = 7: 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

🐍 PythonLab: observed orders, the round-off floor and the five-point Laplacian
⌘/Ctrl + Enter

The lab prints the central and five-point errors above (observed order 2.002.00), the central error bottoming out near 10−510^{-5} and rising after, the Laplacian errors 1.18×10−31.18\times10^{-3} and 2.95×10−42.95\times10^{-4}, and the n=7n=7 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 n≤31n \le 31 is small.

🧪 Coding exerciseExercise: build the 1D and 2D Laplacian and verify second order
⌘/Ctrl + Enter

Concept checks

✅ Concept check

The central difference for $f'$ has error $9.0\times10^{-4}$ at $h = 0.1$. About what error do you expect at $h = 0.05$?

✅ Concept check

You solve a PDE on grids with $h = 0.1, 0.05, 0.025$ and get maximum errors $8.0\times10^{-3}$, $4.0\times10^{-3}$, $2.0\times10^{-3}$. What is wrong, if the scheme was designed to be second order?

✅ Concept check

Use the stencil $f(x), f(x+h), f(x+2h)$ for $f''$. Its weights are $1, -2, 1$ over $h^2$, the same as the central formula, just shifted. What is its order?

✅ Concept check

The five-point Laplacian at a point with $h = 0.1$ has centre weight, in units of $1/h^2$, equal to $-4$. What is the centre weight itself?

Problems

✏️ Pen & paperA one-sided formula from moments●○○

Find the weights for f′(x)f'(x) using f(x−2h),f(x−h),f(x)f(x-2h), f(x-h), f(x), and the order of the formula.

Show worked solution

Offsets −2,−1,0-2, -1, 0 with weights a,b,ca, b, c. Moment equations: a+b+c=0a + b + c = 0, −2a−b=1-2a - b = 1, 4a+b=04a + b = 0 (from k=2k = 2, with 12\tfrac12 divided out). Adding the last two gives 2a=12a = 1, so a=12a = \tfrac12, b=−2b = -2, c=32c = \tfrac32. The formula is (f−2−4f−1+3f0)/2h(f_{-2} - 4f_{-1} + 3f_0)/2h, the mirror image of the forward one. The k=3k = 3 moment is −8a−b=−4+2=−2≠0-8a - b = -4 + 2 = -2 \ne 0, so the error is −26h2f′′′=−13h2f′′′\tfrac{-2}{6}h^2 f''' = -\tfrac13h^2f''' and the order is 22. (This is the formula for the right edge of a domain.)

✏️ Pen & paperReading a convergence table●●○

A code gives maximum errors 3.2×10−33.2\times10^{-3}, 8.1×10−48.1\times10^{-4}, 2.0×10−42.0\times10^{-4} at h=0.1,0.05,0.025h = 0.1, 0.05, 0.025. Compute both observed orders and predict the error at h=0.0125h = 0.0125.

Show worked solution

log⁡2(3.2/0.81)=log⁡23.95=1.98\log_2(3.2/0.81) = \log_2 3.95 = 1.98 and log⁡2(8.1/2.0)=log⁡24.05=2.02\log_2(8.1/2.0) = \log_2 4.05 = 2.02. Both are near 22: second order. Predict 2.0×10−4/4=5×10−52.0\times10^{-4}/4 = 5\times10^{-5}. Three grids matter: a third that continues the slope rules out a pre-asymptotic accident.

✏️ Pen & paperThe Laplacian as an average●●○

At an interior point the neighbours are uE=2u_E = 2, uW=1u_W = 1, uN=3u_N = 3, uS=2u_S = 2, the centre is 1.51.5, and h=0.1h = 0.1. Compute the five-point Laplacian two ways, then say what one Jacobi update would do.

Show worked solution

Direct: (2+1+3+2−6)/0.01=2/0.01=200(2 + 1 + 3 + 2 - 6)/0.01 = 2/0.01 = 200. By average: the average is 8/4=28/4 = 2, and 4h2(2−1.5)=400×0.5=200\tfrac4{h^2}(2 - 1.5) = 400\times0.5 = 200. They agree. The centre sits below the average, so the Laplacian is positive. A Jacobi update replaces the centre by the average, 22, which makes the Laplacian there zero, as Laplace’s equation demands.

✏️ Pen & paperWhere the heat limit comes from●●●

(a) Explicit Euler for u˙=αAu\dot{\mathbf u} = \alpha A\mathbf u is stable when Δt λ≥−2\Delta t\,\lambda \ge -2 for every eigenvalue λ\lambda of αA\alpha A. Use λmin⁡≈−4α/h2\lambda_{\min} \approx -4\alpha/h^2 to recover the limit of the heat lesson. (b) Compute the largest step for air momentum diffusion, ν=1.47×10−5\nu = 1.47\times10^{-5} m2^2/s (from memory), on a 11 cm grid, h=0.01h = 0.01 m.

Show worked solution

(a) The most negative eigenvalue is −4αh2sin⁡2nπh2≈−4αh2-\tfrac{4\alpha}{h^2}\sin^2\tfrac{n\pi h}{2}\approx -\tfrac{4\alpha}{h^2}, so Δt⋅4α/h2≤2\Delta t\cdot4\alpha/h^2 \le 2, i.e. r=αΔt/h2≤12r = \alpha\Delta t/h^2 \le \tfrac12. (b) Δt≤h2/(2ν)=10−4/(2.94×10−5)=3.4\Delta t \le h^2/(2\nu) = 10^{-4}/(2.94\times10^{-5}) = 3.4 s. At 55 mm it falls to 0.850.85 s, at 11 mm to 3434 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 ±12hf′′\pm\tfrac12hf''), the central first derivative is second order (16h2f′′′\tfrac16h^2f'''), and the central second derivative is second order (112h2f′′′′\tfrac1{12}h^2f'''').
  • Weights for any stencil come from the moment equations; the first moment that fails names the error and the order p=k−dp = k - d. Symmetry buys an extra order.
  • The 2D five-point Laplacian is 4h2\tfrac4{h^2} times (neighbour average minus centre), second order, with error h212(uxxxx+uyyyy)\tfrac{h^2}{12}(u_{xxxx} + u_{yyyy}).
  • Dirichlet values move to the right-hand side; Neumann conditions use a ghost cell u−1=u1−2hgu_{-1} = u_1 - 2hg. A one-sided Neumann row drops the whole solution to first order.
  • Stencils are matrices: the 1D matrix has eigenvalues −4h2sin⁡2kπh2-\tfrac4{h^2}\sin^2\tfrac{k\pi h}2, close to −4/h2-4/h^2 at the top.
  • Measure the observed order log⁡2(e(h)/e(h/2))\log_2(e(h)/e(h/2)) on a refinement sequence; below h≈10−5h \approx 10^{-5} round-off, growing like 1/hd1/h^d, takes over.
  • Next, explicit time-stepping for the heat equation: write uxxu_{xx} as the matrix AA, march u˙=αAu\dot{\mathbf u} = \alpha A\mathbf u in time (the method of lines), and see that the r≤12r \le \tfrac12 limit you met in the heat lesson is the Euler stability limit applied to the eigenvalues of AA.
Finished this lesson?

Mark it complete to track your progress (saved in this browser). Reading every section does this for you.

Where this leads

These later lessons build directly on this one: