Testwiki:Property proposal/convergence rate

Template:TranslateThis

Motivation

Well-posed numerical methods (theoretically) converge to the exact solution as $n\to a$. For discretized methods, $n$ is the grid size of the discretization and $n\to \mathrm{\infty }$. For iterative methods, $n$ could be the number of iterations and $n\to \mathrm{\infty }$. Alternatively, for iterative numerical methods for solving differential equations, $n$ is the tiem-step size and $n\to 0$. In each case, there is an upper bound on the on the error of the method as a function of $n$ as $n\to a$. It would be useful to have methods categorized according to this property.

Specifically, I am proposing that we add a property whose subject is the big-O order of convergence for the method. That is, we would set <order of convergence> <g(n)> where g(n) is a function such $f(x)=O(g(x))\text{ as }x\to a$ if $\underset{x\to a}{\mathrm{lim\; sup}}\left|\frac{f(x)}{g(x)}\right|<\mathrm{\infty }$

There are a lot of definitions that are used similarly, so I'm going to list them here and we'll try to sort them out.

• Rate of convergence: if a sequence converges linearly, $\mu :=\underset{k\to \mathrm{\infty }}{\lim }\frac{|x_{k+1}-L|}{|x_k-L|}$ is called the rate of convergence
• If a sequence converges to a limit, then r

The following excerpt from [1] provides clear definitions of order and rate of convergences.

"whether this iteration will converge, and, if so, the rate of convergence. Specifically we use the following to represent how quickly the error \(e_{n}=x_{n}-x^{*}\) converges to zero: $\underset{n\to \mathrm{\infty }}{\lim }\frac{\left|e_{n+1}\right|}{{\left|e_n\right|}^p}=\underset{n\to \mathrm{\infty }}{\lim }\frac{|x_{n+1}-x^{*}|}{{|x_n-x^{*}|}^p}=\mu$ Here \(p \geq 1\) is called the order of convergence, the constant \(\mu\) is the rate of comergence or asymptotic error constant."

I think it makes sense to create an order of convergence (OC) property, but not a rate of convergence (RC). The reason for this, is that OC is (1) a much more important property of an algorithm and (2) there will only be (in practice) a limited number of values. We'll have logarithmically, sublinear, linear, quadratic, cubic, quartic, and maybe a few more. Whereas RC could be any real number.

The-erinaceous-one (talk) 07:47, 31 July 2020 (UTC)