Foundations: Algorithms, Approximation & Error

the discretize-then-solve workflow

The discretize-then-solve workflow is the master recipe of computational mathematics: you cannot hand a continuous problem to a computer, so first you turn it into a finite system of algebraic equations (discretize), and then you solve that finite system with numerical linear algebra or iteration (solve). Almost every real simulation — heat flow, fluid dynamics, structural stress, option pricing — follows this two-stage path.

Concretely, the continuous problem (say a differential equation on a region) is approximated on a finite grid or mesh: each derivative becomes a finite difference, each integral a quadrature sum, the unknown function a finite list of values at the nodes. This replaces 'find a function satisfying a differential equation' with 'find a vector x satisfying A x = b' (or, for a nonlinear problem, a nonlinear system to be tackled by Newton's method). Discretizing introduces discretization (truncation) error, controlled by the grid spacing h; solving the resulting algebraic system introduces round-off error and, if iterative, iteration error. The two stages are conceptually separate even when a code interleaves them: one error comes from the grid, the other from the arithmetic and the solver.

Seeing the workflow as two stages keeps the error budget honest and tells you where to push. If the answer is inaccurate, ask which stage is to blame: too coarse a grid (refine to cut discretization error — an order-of-accuracy study confirms it falls at the right rate) or an inaccurate or unstable solve (better solver, tighter tolerance, more stable algorithm). It also explains why so much of the subject is about solving A x = b fast and stably: that linear (or nonlinear) solve is the inner engine that the outer discretization repeatedly calls. A caution: refining the grid forever is not free — finer grids mean far more unknowns and more arithmetic, so cost and accumulated round-off rise even as discretization error falls.

To solve the 1D heat equation, replace the second derivative on a grid by (u_{i-1} - 2 u_i + u_{i+1})/h^2 at each node (discretize), assembling a tridiagonal A x = b; then solve it in O(n) with the Thomas algorithm (solve). Grid spacing controls discretization error; the solver controls round-off.

Continuous problem to finite algebraic system (discretize), then numerical solve — two stages, two separate error sources.

The two stages have separate, separately controllable errors: discretization error from the grid (shrink by refining h) and solver/round-off error from the arithmetic. Diagnose poor accuracy by deciding which stage is at fault before changing anything.

Also called
discretize-then-solvemodel-discretize-solve離散化-求解先離散再求解