2

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.

Little Rookie
  • 1,176
  • Do you agree that $p_n$ is the error: $p_n=L-x_n$ where $x_n$ is the sequence and $L$ its limit ? – Jean Marie Mar 12 '17 at 00:09
  • i think you misunderstood the notion of $p_n$ used here, i have updated my question – Little Rookie Mar 12 '17 at 12:35
  • I don't think so. See the answer of @Michael who has the same interpretation as me. – Jean Marie Mar 12 '17 at 13:10
  • @JeanMarie Okay, what is $p_{n}$ and $x_{n}$ in your first comment?

    I have only defined one sequence.

     – Little Rookie Mar 12 '17 at 14:23
  • 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. – Jean Marie Mar 12 '17 at 15:23
  • @JeanMarie You still have not answered my question. Why use log(|pn+1|)/log(|pn|) ? why not other function? why not |pn+1|/|pn| ? im asking about the method, not the theory of fixed point iteration. i know the theory. – Little Rookie Mar 13 '17 at 04:09
  • As I said, see the answer by @Michael: log function by the fact that $log(a c^n)=log(a)+n log(c)$, giving a linear expression. – Jean Marie Mar 13 '17 at 07:50
  • A little (and last) remark : don't you think that there is a little misunderstanding in writing in your question $p_{n} = g(p_{n-1})$ which means that $p_n$ is for you the sequence and $\log(|p_{n+1}|)/\log(|p_{n}|)$ instead of $\log(|e_{n+1}|)/\log(|e_{n}|)$ where $e_n=L-p_n$ -the error sequence) – Jean Marie Mar 13 '17 at 07:57
  • All i need is more explanation on the simple code, instead of explaining how does fixed point iteration work. Can you read my question? – Little Rookie Mar 13 '17 at 08:26

1 Answers1

1

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.

Empy2
  • 50,853
  • I dont understand the formula, can u add more information please. – Little Rookie Mar 11 '17 at 17:00
  • 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. – Jean Marie Mar 12 '17 at 00:08