4.8.14Numerical Methods

Error analysis of finite differences

1,421 words6 min readdifficulty · medium3 backlinks

WHAT are we approximating?


HOW: derive the truncation error from scratch

Everything comes from Taylor's theorem about xx: f(x+h)=f(x)+hf(x)+h22f(x)+h36f(x)+f(x+h)=f(x)+hf'(x)+\frac{h^2}{2}f''(x)+\frac{h^3}{6}f'''(x)+\cdots

Forward difference

Why this step? Subtract f(x)f(x) and divide by hh — exactly what the formula does. f(x+h)f(x)h=f(x)+h2f(x)+h26f(x)+\frac{f(x+h)-f(x)}{h}=f'(x)+\frac{h}{2}f''(x)+\frac{h^2}{6}f'''(x)+\cdots So D+f(x)f(x)=h2f(x)+O(h2)=O(h).D_+f(x)-f'(x)=\frac{h}{2}f''(x)+O(h^2)=\boxed{O(h)}. Why this matters: the leading error is h\propto hfirst order accurate. The exact remainder (Lagrange form) is h2f(ξ)\dfrac{h}{2}f''(\xi) for some ξ(x,x+h)\xi\in(x,x+h).

Central difference

Write both expansions: f(x+h)=f(x)+hf+h22f+h36f+f(x+h)=f(x)+hf'+\tfrac{h^2}{2}f''+\tfrac{h^3}{6}f'''+\cdots f(xh)=f(x)hf+h22fh36f+f(x-h)=f(x)-hf'+\tfrac{h^2}{2}f''-\tfrac{h^3}{6}f'''+\cdots Why subtract? The even-power terms (ff, ff'') cancel, leaving only odd ones: f(x+h)f(xh)=2hf(x)+h33f(x)+f(x+h)-f(x-h)=2hf'(x)+\frac{h^3}{3}f'''(x)+\cdots Divide by 2h2h: D0f(x)f(x)=h26f(x)+O(h4)=O(h2).D_0f(x)-f'(x)=\frac{h^2}{6}f'''(x)+O(h^4)=\boxed{O(h^2)}. Why this matters: the cancellation kills the O(h)O(h) term → second order. Halving hh cuts truncation error by ~4.


HOW: where rounding error comes in

The machine doesn't store f(x)f(x) exactly; it stores f~(x)=f(x)+δ\tilde f(x)=f(x)+\delta, where δεmf(x)|\delta|\le \varepsilon_m |f(x)| and εm2.2×1016\varepsilon_m\approx 2.2\times10^{-16} (double precision machine epsilon).

For the central formula, the computed numerator carries error up to 2ε2\varepsilon where ε=εmf\varepsilon=\varepsilon_m\,|f|, so: εround2ε2h=εh.\varepsilon_{\text{round}}\lesssim \frac{2\varepsilon}{2h}=\frac{\varepsilon}{h}. Why 1/h1/h? We divide a roundoff that does not shrink by a tiny hh → it blows up. This is catastrophic cancellation: f(x+h)f(x+h) and f(xh)f(x-h) are almost equal, so subtracting loses significant digits.

Optimal step — derive by minimizing

Why differentiate? The minimum of E(h)E(h) is where E(h)=0E'(h)=0. E(h)=h3M3εh2=0  h3=3εM3E'(h)=\frac{h}{3}M_3-\frac{\varepsilon}{h^2}=0\ \Rightarrow\ h^3=\frac{3\varepsilon}{M_3} hopt=(3εM3)1/3ε1/36×106\boxed{h_{\text{opt}}=\left(\frac{3\varepsilon}{M_3}\right)^{1/3}\sim \varepsilon^{1/3}\approx 6\times10^{-6}} At that point Eε2/31011E\sim \varepsilon^{2/3}\approx 10^{-11}not machine precision! For forward difference you get hoptε1/2108h_{\text{opt}}\sim\varepsilon^{1/2}\approx10^{-8}, Eε1/2E\sim\varepsilon^{1/2}.

Figure — Error analysis of finite differences

Worked examples


Common mistakes


Recall Feynman: explain to a 12-year-old

Imagine measuring a hill's steepness by walking two steps apart and seeing how much higher you got. Big steps give a rough answer (you miss the hill's curve) — that's truncation error. Tiny steps should be perfect... but your ruler can only read so many digits, so when the two heights are almost the same, the tiny difference is mostly measurement junk — that's rounding error. There's a "just right" step size, not too big, not too small. Stepping across your point (one ahead, one behind) is cleverer than only stepping forward, because the errors on each side cancel.


Active recall

Leading truncation error of the forward difference?
h2f(ξ)\frac{h}{2}f''(\xi), i.e. O(h)O(h).
Leading truncation error of the central difference?
h26f(ξ)\frac{h^2}{6}f'''(\xi), i.e. O(h2)O(h^2).
Why is central difference more accurate than forward?
Subtracting f(xh)f(x-h) from f(x+h)f(x+h) cancels the even-power Taylor terms (ff, ff''), removing the O(h)O(h) term.
How does rounding error scale with hh for central difference?
As ε/h\varepsilon/h — it grows as h0h\to 0 (catastrophic cancellation + division by small hh).
What is the optimal step for central difference?
hopt(3ε/M3)1/3ε1/36×106h_{\text{opt}}\sim(3\varepsilon/M_3)^{1/3}\sim\varepsilon^{1/3}\approx 6\times10^{-6} in double precision.
Why is "smaller hh always better" wrong?
Total error is U-shaped; below hopth_{\text{opt}} rounding error ε/h\varepsilon/h dominates and total error increases.
Halving hh for an O(h2)O(h^2) scheme changes the error by what factor?
It multiplies the error by 1/41/4 (since Eh2E\propto h^2).
What is catastrophic cancellation here?
Subtracting two nearly-equal function values loses significant digits, leaving relative error ε/h\sim\varepsilon/h.
Best achievable accuracy for central difference (double precision)?
ε2/31011\sim\varepsilon^{2/3}\approx 10^{-11}, not full machine precision.

Connections

  • Taylor's Theorem — the engine behind every truncation term.
  • Forward and Backward Difference Operators
  • Central Difference Operator
  • Floating Point Arithmetic and Machine Epsilon
  • Catastrophic Cancellation
  • Richardson Extrapolation — cancels the leading truncation term to boost the order.
  • Numerical Differentiation
  • Order of Accuracy

Concept Map

approximated by

expand f x plus h

subtract, divide by h

subtract expansions

even terms cancel

truncation error

truncation error

shrinks as h to 0

grows as h to 0

causes

scales as eps over h

minimize E prime h equals 0

True derivative f prime x

Finite difference quotient

Taylor theorem

Forward difference O h

Central difference O h2

Second order accuracy

Truncation error

Total error E h

Rounding error

Machine epsilon

Catastrophic cancellation

Optimal step h

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, jab hum derivative f(x)f'(x) ko computer pe nikalte hain, toh limit nahi le sakte — bas ek chhota hh daal dete hain. Isse do tarah ke error aate hain. Pehla, truncation error: humne Taylor series ki tail kaat di, isliye answer thoda galat. Forward difference mein yeh error O(h)O(h) hota hai, lekin central difference mein f(x+h)f(x+h) aur f(xh)f(x-h) ko subtract karne se even terms (ff, ff'') cancel ho jaate hain, aur error O(h2)O(h^2) ban jaata hai — yaani bahut accurate. Yaad rakho: "Forward is First, Central Catches Curvature."

Dusra enemy hai rounding error. Computer har number ko sirf 16 digit tak store karta hai (machine epsilon ε1016\varepsilon\approx10^{-16}). Jab hh bahut chhota ho jaata hai, toh f(x+h)f(x+h) aur f(xh)f(x-h) almost barabar ho jaate hain — unko subtract karne pe significant digits gayab ho jaate hain. Isko catastrophic cancellation kehte hain, aur yeh error ε/h\varepsilon/h ki tarah badhta hai jaise h0h\to0.

Toh dono ko jodo: total error E(h)=h26M3+εhE(h)=\frac{h^2}{6}M_3+\frac{\varepsilon}{h}. Yeh ek U-shape banata hai. Bahut bada hh → truncation zyada; bahut chhota hh → rounding zyada. Beech mein ek sweet spot hai, hoptε1/36×106h_{opt}\sim\varepsilon^{1/3}\approx6\times10^{-6}. Galti yeh hai ki students sochte hain "hh jitna chhota utna achha" — yeh galat hai! Us point ke baad answer kharab hone lagta hai. Isliye sahi hh choose karna ek skill hai, aur Richardson extrapolation jaise tricks se hum accuracy aur badha sakte hain.

Test yourself — Numerical Methods

Connections