Numerical method

Short description: Mathematical tool to algorithmically solve equations

In numerical analysis, a numerical method is a mathematical tool designed to solve numerical problems. The implementation of a numerical method with an appropriate convergence check in a programming language is called a numerical algorithm.

Mathematical definition

Let [math]\displaystyle{ F(x,y)=0 }[/math] be a well-posed problem, i.e. [math]\displaystyle{ F:X \times Y \rightarrow \mathbb{R} }[/math] is a real or complex functional relationship, defined on the cross-product of an input data set [math]\displaystyle{ X }[/math] and an output data set [math]\displaystyle{ Y }[/math], such that exists a locally lipschitz function [math]\displaystyle{ g:X \rightarrow Y }[/math] called resolvent, which has the property that for every root [math]\displaystyle{ (x,y) }[/math] of [math]\displaystyle{ F }[/math], [math]\displaystyle{ y=g(x) }[/math]. We define numerical method for the approximation of [math]\displaystyle{ F(x,y)=0 }[/math], the sequence of problems

[math]\displaystyle{ \left \{ M_n \right \}_{n \in \mathbb{N}} = \left \{ F_n(x_n,y_n)=0 \right \}_{n \in \mathbb{N}}, }[/math]

with [math]\displaystyle{ F_n:X_n \times Y_n \rightarrow \mathbb{R} }[/math], [math]\displaystyle{ x_n \in X_n }[/math] and [math]\displaystyle{ y_n \in Y_n }[/math] for every [math]\displaystyle{ n \in \mathbb{N} }[/math]. The problems of which the method consists need not be well-posed. If they are, the method is said to be stable or well-posed.

Consistency

Necessary conditions for a numerical method to effectively approximate [math]\displaystyle{ F(x,y)=0 }[/math] are that [math]\displaystyle{ x_n \rightarrow x }[/math] and that [math]\displaystyle{ F_n }[/math] behaves like [math]\displaystyle{ F }[/math] when [math]\displaystyle{ n \rightarrow \infty }[/math]. So, a numerical method is called consistent if and only if the sequence of functions [math]\displaystyle{ \left \{ F_n \right \}_{n \in \mathbb{N}} }[/math] pointwise converges to [math]\displaystyle{ F }[/math] on the set [math]\displaystyle{ S }[/math] of its solutions:

[math]\displaystyle{ \lim F_n(x,y+t) = F(x,y,t) = 0, \quad \quad \forall (x,y,t) \in S. }[/math]

When [math]\displaystyle{ F_n=F, \forall n \in \mathbb{N} }[/math] on [math]\displaystyle{ S }[/math] the method is said to be strictly consistent.

Convergence

Denote by [math]\displaystyle{ \ell_n }[/math] a sequence of admissible perturbations of [math]\displaystyle{ x \in X }[/math] for some numerical method [math]\displaystyle{ M }[/math] (i.e. [math]\displaystyle{ x+\ell_n \in X_n \forall n \in \mathbb{N} }[/math]) and with [math]\displaystyle{ y_n(x+\ell_n) \in Y_n }[/math] the value such that [math]\displaystyle{ F_n(x+\ell_n,y_n(x+\ell_n)) = 0 }[/math]. A condition which the method has to satisfy to be a meaningful tool for solving the problem [math]\displaystyle{ F(x,y)=0 }[/math] is convergence:

[math]\displaystyle{ \begin{align} &\forall \varepsilon \gt 0, \exist n_0(\varepsilon) \gt 0, \exist \delta_{\varepsilon, n_0} \text{ such that} \\ &\forall n \gt n_0, \forall \ell_n : \| \ell_n \| \lt \delta_{\varepsilon,n_0} \Rightarrow \| y_n(x+\ell_n) - y \| \leq \varepsilon. \end{align} }[/math]

One can easily prove that the point-wise convergence of [math]\displaystyle{ \{y_n\} _{n \in \mathbb{N}} }[/math] to [math]\displaystyle{ y }[/math] implies the convergence of the associated method is function.

See also

• Numerical methods for ordinary differential equations
• Numerical methods for partial differential equations