1
$\begingroup$

I have $g(x) = \sqrt{1+\log(x)}$, I want to find the rate of convergence using fixed point iteration. I have confirmed that this is linearly convergent, because the absolute value of its derivative is less than $1$, but I want to know how fast it converges to $1$ (which is our fixed point).

How can I find the rate of convergence for : $x_{i+1} = \sqrt{1+\log(x_i)}$?

I have tried squaring both sides but wasn't able to weasel out a relationship between $x_{i+1}$ and $x_i$.

$\endgroup$
1
$\begingroup$

If you are near a root $r$ of $x-g(x)=0$ then let $x_n=r+\epsilon_n$. The linear approximation of the next iterate is $$x_{n+1}=r+\epsilon_{n+1}=g(x_n)=g(r+\epsilon_n)\approx g(r)+\epsilon_ng^{\prime}(r)=r+\epsilon_ng^{\prime}(r)$$ So the error $\epsilon$ just gets multiplied by $g^{\prime}(r)$ at each iteration with the result that $$\epsilon_n\approx\epsilon_0\left(g^{\prime}(r)\right)^n$$ Near the fixed point $r\approx0.450763652$, $$g^{\prime}(r)=\frac1{2r\sqrt{1+\ln r}}=\frac1{2r^2}=2.460776817>1$$ so we won't converge there. Near $r=1$, $g^{\prime}(r)=\frac12$ so $\epsilon_n\approx\frac{\epsilon_0}{2^n}$ provided our initial aproximation was close enough to $1$.

$\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.