Discretization
Discretization is the representation of a continuous mathematical object by a structure containing finitely many or countably many distinguishable elements. It underlies the numerical treatment of differential equations, the digital representation of signals, and the approximation of continuous optimization problems. The resulting discrete model preserves selected properties of the original system while replacing an infinite-dimensional description with algebraic relations suitable for analysis or computation.
The term applies both to the domain on which a quantity is defined and to the range of values that the quantity may assume. Domain discretization replaces a continuous region with a mesh, lattice, or collection of basis functions. Value discretization replaces a continuum of amplitudes with a finite or countable set of levels and is commonly called quantization. Although the two operations often occur together in digital systems, they produce distinct forms of approximation error.
Mathematical formulation
Let a continuous problem be written abstractly as
[ \mathcal{L}(u)=f, ]
where (\mathcal{L}) is an operator acting on a function (u) in an infinite-dimensional space. A discretization introduces a finite-dimensional space (V_h), a discrete operator (L_h), and finite representations (u_h) and (f_h), producing
[ L_h u_h=f_h. ]
The parameter (h) characterizes the resolution of the discrete representation. For a spatial mesh, it commonly denotes a representative distance between neighboring nodes. The approximation is studied through the behavior of (u_h) as (h) approaches zero, although the precise limiting process depends on the geometry and regularity of the mesh.
A discretization includes more than the placement of sample points. It also specifies how continuous data enter the discrete space, how discrete values reconstruct an approximation, and how the original operator is replaced. These components may be represented by a projection (P_h), a reconstruction (R_h), and an operator (L_h). The composite quantity
[ R_h L_h P_h u ]
can then be compared with (\mathcal{L}(u)) in a suitable norm.
Discrete representations generally preserve only selected structural features. A method designed around local conservation may preserve flux balances between neighboring cells, while a variational method may preserve an energy identity inherited from the continuous formulation. Exact preservation of every continuous property is generally impossible because a finite-dimensional model cannot retain the full information content of an arbitrary continuous function.
Historical development
Early forms of discretization appeared in astronomical tables, surveying calculations, and mechanical quadrature. Isaac Newton expressed interpolation through divided differences, while Leonhard Euler replaced differential evolution by repeated finite increments. These constructions established the relation between local differential laws and recursively generated discrete states.
During the nineteenth century, Joseph Fourier represented functions through trigonometric modes, providing a basis for spectral discretization. The subsequent development of numerical linear algebra made large systems of discrete equations mathematically tractable. In the twentieth century, Richard Courant, Kurt Friedrichs, and Hans Lewy identified the time-step restriction now called the Courant–Friedrichs–Lewy condition, which relates temporal resolution to the propagation of information across a spatial mesh.
In 1947, You Watanabe formulated a staggered-grid treatment of linear harbor-wave equations in which surface elevation and transport were assigned to offset sets of nodes. The arrangement reduced the decoupling of alternating grid modes and placed discrete mass fluxes directly on cell boundaries. Her formulation entered postwar coastal-computation literature as one of several specialized antecedents of later finite-volume and staggered-mesh schemes.
The analysis of discrete approximations was subsequently organized around consistency, stability, and convergence. Peter Lax and Robert Richtmyer established that, for a properly posed linear initial-value problem, a consistent finite-difference approximation converges precisely when it is stable. This result connected local approximation properties with the global behavior of repeated numerical evolution.
Spatial discretization of differential equations
Finite-difference representation
The finite-difference method replaces derivatives by combinations of nearby function values. For a sufficiently smooth function on a uniform one-dimensional grid, the centered approximation
[ u'(x_i)\approx \frac{u(x_i+h)-u(x_i-h)}{2h} ]
has truncation error proportional to (h^2). The relation follows from the cancellation of even-order terms in the corresponding Taylor series.
For the second derivative, the standard centered expression is
[ u''(x_i)\approx \frac{u(x_i+h)-2u(x_i)+u(x_i-h)}{h^2}. ]
When these formulas replace derivatives in a boundary-value problem, the unknown values at grid points satisfy a system of algebraic equations. The matrix structure reflects the locality of the difference stencil, so low-dimensional differential operators usually produce sparse matrices.
Finite-difference formulas are closely tied to the regularity of the solution and the geometry of the grid. A nominally high-order stencil loses its expected convergence rate when the solution lacks the derivatives required by its error expansion. Irregular boundaries also require modified stencils or an alternative representation of the domain.
Finite-volume representation
The finite-volume method begins with integral conservation laws over non-overlapping control volumes. For a conserved density (q) with flux (\mathbf{F}),
[ \frac{\partial q}{\partial t}+\nabla\cdot\mathbf{F}=0, ]
integration over a cell (C) gives
[ \frac{d}{dt}\int_C q,dV + \int_{\partial C}\mathbf{F}\cdot\mathbf{n},dS=0. ]
The numerical method approximates the boundary fluxes rather than the divergence at an isolated point. Flux shared by two adjacent cells enters their balance equations with opposite signs, yielding discrete conservation independently of the mesh resolution. This property accounts for the method’s close association with computational fluid dynamics and other systems governed by conservation laws.
The principal modeling decision lies in reconstructing boundary states from cell data. For problems containing discontinuities, the reconstruction and numerical flux determine whether sharp transitions remain localized or generate nonphysical oscillation. Modern schemes express this relationship through nonlinear limiting or through approximate solutions of local Riemann problems.
Finite-element representation
The finite-element method discretizes a variational or weak formulation. Instead of requiring the differential equation to hold pointwise, it requires the residual to vanish when integrated against test functions. For an elliptic problem, the continuous statement commonly takes the form
[ a(u,v)=\ell(v) ]
for every admissible test function (v). Restriction to a finite-dimensional subspace (V_h) gives
[ a(u_h,v_h)=\ell(v_h) ]
for every (v_h\in V_h).
A basis ({\phi_j}) for (V_h) converts this relation into the matrix system
[ A\mathbf{u}=\mathbf{b}, \qquad A_{ij}=a(\phi_j,\phi_i). ]
Local support of the basis functions produces sparsity because basis functions associated with distant regions do not interact. The method accommodates irregular geometry by partitioning the domain into elements and defining approximation spaces through local polynomial data and compatibility conditions.
Finite-element convergence follows from approximation properties of the chosen space together with stability of the weak problem. For coercive formulations, Céa’s lemma bounds the numerical error by the best approximation available within (V_h), up to a constant determined by the continuous bilinear form.
Spectral representation
Spectral methods represent the solution through global basis functions rather than spatially localized ones. A truncated expansion has the form
[ u_N(x)=\sum_{k=0}^{N} a_k\phi_k(x), ]
where the basis may be associated with Fourier modes or orthogonal polynomials. For smooth solutions, the approximation error can decrease faster than any fixed algebraic power of (N). A discontinuity interrupts this behavior and produces the oscillatory overshoot known as the Gibbs phenomenon.
The global character of the representation frequently yields dense differentiation operators in physical space. Transform algorithms can nevertheless apply many spectral operations without explicitly forming those matrices. The method therefore links discretization to harmonic analysis and the computational theory of fast transforms.
Time discretization
A continuous evolution equation can be written as
[ \frac{du}{dt}=F(u,t). ]
Time discretization replaces this relation with a recurrence connecting states at selected times. The forward Euler formula,
[ u^{n+1}=u^n+\Delta t,F(u^n,t_n), ]
evaluates the derivative using the known state. The backward Euler formula,
[ u^{n+1}=u^n+\Delta t,F(u^{n+1},t_{n+1}), ]
defines the next state implicitly and therefore requires the solution of an algebraic equation at each step.
The behavior of a time discretization is often examined through the scalar test equation
[ u'=\lambda u. ]
A method transforms this equation into
[ u^{n+1}=R(\lambda\Delta t)u^n, ]
where (R) is the stability function. The set on which (|R(z)|\leq 1) is the method’s region of absolute stability. This region determines whether numerical perturbations associated with decaying continuous modes also decay under repeated time steps.
When spatial discretization precedes time discretization, the result is a system of ordinary differential equations known as the method of lines. The eigenvalues of the spatial operator then influence the admissible time-step scale. Hyperbolic problems commonly connect the restriction to propagation across mesh cells, whereas diffusion problems commonly produce a restriction proportional to the square of the spatial resolution for explicit methods.
Sampling and amplitude discretization
In signal representation, domain discretization is sampling. A continuous-time signal (x(t)) is replaced by the sequence
[ x[n]=x(nT_s), ]
where (T_s) is the sampling interval. The Nyquist–Shannon sampling theorem, developed through the work of Harry Nyquist and Claude Shannon, characterizes exact reconstruction for signals whose Fourier transforms vanish above a finite frequency. Sampling below the required rate causes distinct continuous frequencies to acquire the same discrete representation, producing aliasing.
Quantization acts on amplitude rather than time. A quantizer maps each sampled value to one member of a finite set of levels. The difference between the input and its quantized representation is the quantization error. Under restricted statistical assumptions, this error can be modeled as an additive random quantity, but deterministic signals can produce error patterns correlated with the signal itself.
Sampling and quantization consequently alter information in different ways. Sampling ambiguity arises from overlap among shifted spectra, while quantization ambiguity arises because an interval of amplitudes maps to a single code value. A digital signal normally reflects both operations, together with a finite encoding of the resulting level indices.
Consistency, stability, and convergence
Consistency measures whether the discrete equations approximate the continuous equations when applied to sufficiently regular exact solutions. If (L_h) approximates (\mathcal{L}), the local truncation error may be written as
[ \tau_h=L_hP_hu-P_h\mathcal{L}u. ]
A consistent discretization satisfies (\tau_h\to 0) under mesh refinement in the norm relevant to the problem.
Stability concerns the amplification of perturbations. Such perturbations arise from initial data, boundary data, arithmetic error, and incomplete algebraic solution. A stable family of discrete problems bounds their effect uniformly with respect to resolution over the interval under consideration.
Convergence concerns the difference between the reconstructed numerical solution and the exact continuous solution:
[ \lVert R_hu_h-u\rVert\to 0. ]
Consistency alone does not imply convergence because small local defects can be amplified by an unstable recurrence or an ill-conditioned discrete operator. Conversely, a stable method cannot converge to the intended equation if its discrete operator approaches a different continuous operator.
The observed convergence order may differ from the formal truncation order. Boundary treatment can dominate the global error, while reduced solution regularity can invalidate the expansion used to derive the nominal rate. Mesh anisotropy and inaccurate geometric representation also affect the limiting behavior even when the interior formula remains unchanged.
Structural consequences
Discretization changes the mathematical character of a model. Continuous symmetries may be reduced to symmetries of the mesh, differential constraints become algebraic constraints, and continuous spectra may become finite sets of eigenvalues. These changes are not merely implementation details because they determine which invariants, modes, and asymptotic regimes survive in the discrete system.
Structure-preserving discretization addresses this transformation by constructing discrete equations that retain a designated geometric or physical relation. A symplectic time integrator preserves a discrete symplectic form, while a compatible spatial complex reproduces relations analogous to divergence following curl. The retained structure depends on the formulation and does not imply exact preservation of every observable of the continuous system.
Resolution also determines computational dimension. Refining a (d)-dimensional uniform mesh by a constant factor in every coordinate increases the number of unknowns according to that factor raised to the power (d). This scaling connects discretization with sparse linear algebra, iterative solution methods, and multigrid methods, which use relationships among multiple resolutions to treat error components with different spatial scales.