Numerical method

This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. Please help to improve this article by introducing more precise citations. (September 2016) (Learn how and when to remove this template message)

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[edit]

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

${\displaystyle M=\left\{M_{n}\right\}_{n\in \mathbb {N} }=\left\{F_{n}(x_{n},y_{n})=0\right\}_{n\in \mathbb {N} },}$

with ${\displaystyle F_{n}:X_{n}\times Y_{n}\rightarrow \mathbb {R} }$, ${\displaystyle x_{n}\in X_{n}}$ and ${\displaystyle y_{n}\in Y_{n}}$ for every ${\displaystyle n\in \mathbb {N} }$. 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.^[1]

Consistency[edit]

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

${\displaystyle \lim F_{n}(x,y)=F(x,y)=0,\quad \quad \forall (x,y)\in S.}$

When ${\displaystyle F_{n}=F,\forall n\in \mathbb {N} }$ on ${\displaystyle S}$ the method is said to be strictly consistent.^[1]

Convergence[edit]

Denote by ${\displaystyle \ell _{n}}$ a sequence of admissable perturbations of ${\displaystyle x\in X}$ for some numerical method ${\displaystyle M}$ (i.e. ${\displaystyle x+\ell _{n}\in X_{n}\forall n\in \mathbb {N} }$) and with ${\displaystyle y_{n}(x+\ell _{n})\in Y_{n}}$ the value such that ${\displaystyle F_{n}(x+\ell _{n},y_{n}(x+\ell _{n}))=0}$. A condition which the method has to satisfy to be a meaningful tool for solving the problem ${\displaystyle F(x,y)=0}$ is convergence:

${\displaystyle {\begin{aligned}&\forall \varepsilon >0,\exists n_{0}(\varepsilon )>0,\exists \delta _{\varepsilon ,n_{0}}{\text{ such that}}\\&\forall n>n_{0},\forall \ell _{n}:\|\ell _{n}\|<\delta _{\varepsilon ,n_{0}}\Rightarrow \|y_{n}(x+\ell _{n})-y\|\leq \varepsilon .\end{aligned}}}$0,\exists n_{0}(\varepsilon )>0,\exists \delta _{\varepsilon ,n_{0}}{\text{ such that}}\\&\forall n>n_{0},\forall \ell _{n}:\|\ell _{n}\|<\delta _{\varepsilon ,n_{0}}\Rightarrow \|y_{n}(x+\ell _{n})-y\|\leq \varepsilon .\end{aligned}}}"/>

One can easily prove that the point-wise convergence of ${\displaystyle \{y_{n}\}_{n\in \mathbb {N} }}$ to ${\displaystyle y}$ implies the convergence of the associated method.^[1]

References[edit]