1
$\begingroup$

Given the fixed point iteration function $g(x)=e^{-x}$, I want to find the order of convergence of $g$. (I know yet that the iteration method converges to the fixed point for every starting point).

Now, the definition of order of convergence is the following:

An iterative method is said to converge at the fixed point with order $a\geq 1$ if $\displaystyle{\lim\limits_{i \rightarrow \infty}\frac{|x_{i+1}-\bar{x}|}{|x_i -\bar{x}|^a}}=\alpha \in \mathbb{R}_+$ (some textbooks require that if $a=1$ then $\alpha \in (0,1]$.

My guess is that the iterative method is linearly convergent, meaning $a=1$, my guess is because the derivative of $g(x)$ is never zero. Also, if I try to picture graphic of the method, then it seems to converge quite rapidly, more than I would expect from a linear order convergence (which, I think, is something pretty slow, or at least slower than quadratic convergence or more, $a\geq 2$).

$\endgroup$
  • $\begingroup$ The fixed point is $W(1)$ using the Lambert-W function. $\endgroup$ – LutzL Dec 3 '17 at 21:18
1
$\begingroup$

The asymptotic convergence rate is based on the derivative of $g$ at the fixed point. You don't know the fixed point exactly, but you can give a simple interval bound for it using the intermediate value theorem. This bound will tell you that the derivative is nonzero at the fixed point, which implies linear convergence. Specifically $\alpha$ is the absolute value of the derivative at the fixed point.

(By the way, I'd advise you to take a look at weaker versions of the definition of the order of convergence. That one, although it is intuitive, is almost never actually applicable.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.