Finite Difference Methods for PDEs

Every pixel of the Laplacian filter in OpenCV is a finite difference. Climate simulation is a PDE on a 0.5°×0.5° grid. Fluid rendering in games is Navier-Stokes discretized with finite differences and solved on GPU.

• **Image processing:** Laplacian and Sobel operators are second-order finite difference stencils; cv2.Laplacian uses the 5-point stencil
• **Climate models:** atmospheric equations discretized on a spherical grid; CFL limits the time step by the speed of sound
• **GPU fluid simulation:** pressure solved by Poisson equation each frame; CUDA sparse matrix implementation

Предварительные знания

• Stiff Systems

Finite Difference Stencils

The finite difference method replaces derivatives with difference quotients on a regular grid. Accuracy order is determined by how well the approximation reproduces the Taylor series.

**Basic stencils (step h):** **First derivative:** Forward: (uᵢ₊₁ − uᵢ) / h + O(h) Backward: (uᵢ − uᵢ₋₁) / h + O(h) Central: (uᵢ₊₁ − uᵢ₋₁) / (2h) + O(h²) **Second derivative:** (uᵢ₋₁ − 2uᵢ + uᵢ₊₁) / h² + O(h²) ← Laplacian stencil **Coefficients** derived by substituting Taylor series into the stencil.

Finite differences appear in image processing: the **Laplacian operator** ∇²I = (Iᵢ₋₁,ⱼ + Iᵢ₊₁,ⱼ + Iᵢ,ⱼ₋₁ + Iᵢ,ⱼ₊₁ − 4Iᵢ,ⱼ)/h² detects edges-it is the same 5-point Laplacian stencil!

Heat Equation: FTCS and Crank-Nicolson

The heat equation ∂u/∂t = α ∂²u/∂x² is the simplest PDE. The FTCS scheme (Forward-Time Central-Space) is explicit: computes uⁿ⁺¹ from uⁿ. The Crank-Nicolson scheme is implicit, unconditionally stable, and second-order in time.

**FTCS (explicit):** uᵢⁿ⁺¹ = uᵢⁿ + r·(uᵢ₋₁ⁿ − 2uᵢⁿ + uᵢ₊₁ⁿ) where r = α·Δt / Δx² **CFL stability condition:** r ≤ 1/2 **Crank-Nicolson (implicit, O(Δt²)):** uᵢⁿ⁺¹ − r/2·(uᵢ₋₁ⁿ⁺¹ − 2uᵢⁿ⁺¹ + uᵢ₊₁ⁿ⁺¹) = uᵢⁿ + r/2·(uᵢ₋₁ⁿ − 2uᵢⁿ + uᵢ₊₁ⁿ) Tridiagonal system per step-O(n) Thomas algorithm!

CFL Condition and 2D Poisson Equation

The Courant-Friedrichs-Lewy (CFL) condition is the key stability constraint for explicit PDE schemes. Physical meaning: numerical information propagation speed must not be slower than physical speed. The Poisson equation −∇²u = f is an elliptic PDE with no time dependence-solved once.

**CFL condition (wave equation):** C = c·Δt / Δx ≤ 1 where c is wave speed. **For heat equation:** r = α·Δt / Δx² ≤ 1/2 **2D Poisson equation:** −(∂²u/∂x² + ∂²u/∂y²) = f(x,y) 5-point stencil → sparse linear system of size N² × N². For N = 1000: 10⁶ × 10⁶ matrix-sparse methods only!

**GPU fluid simulation.** The Poisson equation for pressure is solved every frame in incompressible fluid simulation. On GPU, an iterative solver (multigrid) performs sparse SpMV in parallel across thousands of cores.

Key Ideas

• **Stencils:** first derivative O(h) or O(h²), second derivative O(h²); coefficients from Taylor series
• **FTCS:** explicit heat scheme; stability condition r = αΔt/Δx² ≤ 1/2
• **Crank-Nicolson:** implicit, O(Δt²), unconditionally stable; tridiagonal system per step
• **Poisson equation:** 5-point stencil → sparse N²×N² system; sparse solvers only

Related Topics

Finite differences generate stiff systems and sparse matrices:

• Stiff Systems — PDE discretization produces stiff ODE systems; CFL is the stability condition for explicit methods
• Finite Element Method — FEM generalizes FD to irregular meshes; the same stiffness matrix assembly operations apply

Вопросы для размышления

• Why does Crank-Nicolson achieve second-order accuracy in time despite mixing implicit and explicit terms?
• How does the CFL condition change for the 2D heat equation on a square grid?
• Can finite differences handle image processing on irregular boundaries?

Связанные уроки

• de-07