One simple code to find the order of convergence of a fixed point iteration on Matlab is as following,

for each $n=0,1,2,...$

calculate $\log(|p_{n+1}|)/\log(|p_{n}|)$

The calculated value for each $n$ will converge to the order of convergence.

Note: $p_{0}\in \mathbb{R}$, $p_{n} = g(p_{n-1})$, where we are finding the fixed point of function $g$.

Question: I understand the idea of order of convergence, but i don't understand how this method works.

Please help me on this method. Thank you.

  • $\begingroup$ Do you agree that $p_n$ is the error: $p_n=L-x_n$ where $x_n$ is the sequence and $L$ its limit ? $\endgroup$ – Jean Marie Mar 12 '17 at 0:09
  • $\begingroup$ i think you misunderstood the notion of $p_n$ used here, i have updated my question $\endgroup$ – Little Rookie Mar 12 '17 at 12:35
  • $\begingroup$ I don't think so. See the answer of @Michael who has the same interpretation as me. $\endgroup$ – Jean Marie Mar 12 '17 at 13:10
  • $\begingroup$ @JeanMarie Okay, what is $p_{n}$ and $x_{n}$ in your first comment? I have only defined one sequence. $\endgroup$ – Little Rookie Mar 12 '17 at 14:23
  • $\begingroup$ This is precisely your problem ... You have to consider "the" original sequence and a secondary sequence defined as the gap between this sequence and its limit, the "error sequence". Let us take the classical sequence $x_{n+1}=\dfrac12(x_n+\dfrac{2}{x_n})$ with limit $\sqrt{2}$, $log(x_{n+1})/log(x_n) \to \dfrac{1/2}{1/2}1$ when $n \to \infty$ whereas it is a method of order 2 (Newton)... And more generaly, every convergent sequence will give you a limit equal to 1 !!! It is only if you take $p_n:=L-x_n$ (the "error") that $ln(|p_{n+1}|)/ln(|p_n|)$ that you will have a limit equal to 2. $\endgroup$ – Jean Marie Mar 12 '17 at 15:23

Sometimes, the error halves at each step, or reduces, roughly, by the same factor.
$p_{n+1}\approx cp_n$, so the error will be $p_n\approx c^{-n}$.
That is first-order. In your formula, it becomes $$(n+1)\log c/(n\log c)=(n+1)/n\to1$$ An example of this sort of convergence is $\cos\cos\cos\cos\cos 1$ which converges to 0.739

Sometimes, the error squares at each step, so the number of correct digits after the decimal point, doubles at each step. Newton's method is usually like this. Then $p_{n+1}\approx c(p_n)^2$. Your formula becomes $$(\log c+2\log p_n)/\log p_n\to2$$ when $p_n$ gets small and $\log p_n$ gets large and negative. So this is second-order.

  • $\begingroup$ I dont understand the formula, can u add more information please. $\endgroup$ – Little Rookie Mar 11 '17 at 17:00
  • $\begingroup$ Globally correct answer but you have to take care to imprecisions like your first equation for example should be $p_n\approx p_0 c^n$ (with a positive exponent). And to your mathematical style: for example, you shouldn't write $\cos \cos \cos \cos 1$ but $x_n=\cos(x_{n-1})$ with $x_0=1$, etc. $\endgroup$ – Jean Marie Mar 12 '17 at 0:08

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.