Verify numerically that the iterative method is cubically or linear convergent

332 Views Asked by At

Using a function of your choice, verify numerically that the iterative method

$$x_{n+1} =x_n − \dfrac{f(x_n)}{\sqrt{[f′(x_n)]^2 − \dfrac{f(x_n)}{f''(x_n)}}}$$

is cubically convergent at a simple root but only linearly convergent at a multiple root.

I have to use Matlab/python for this practice question. I have more exposure with python but I can manage with matlab. So to verify it can I use a function like $f(x)=g(x)^{h(x)}$ with $g(x)=(x-r)^n$ for $n$ being some power? Or what should I do next?

1

There are 1 best solutions below

0
On

Your formula looks wrong. It is the opposite of the Newton method if the derivative is negative at the root. A root finding method should not change when the function is changed by a constant factor, such a factor would not cancel in the given formula.

A halfway plausible corrected formula that is invariant under rescaling of $f$ and is a refinement of the Newton method would be $$ x_{n+1}=x_n+h_n=x_n-\frac{sign[f'(x_n)]f(x_n)}{\sqrt{f'(x_n)^2-f(x_n)f''(x_n)}} $$ With this formula you would get in the Taylor expansion \begin{align} f(x_n+h_n)&=f(x_n)+f'(x_n)h_n+\frac12f''(x_n)h_n^2+O(h_n^3)\\ &=\frac{f\left(f'^2-ff''\right)-|f'|f\sqrt{f'^2-ff''}+\frac12f''f^2}{f'^2-ff''}+O(f(x_n)^3)\\ &=f\frac{(f'^2-\frac12ff'')-|f'|\sqrt{f'^2-ff''}}{f'^2-ff''}+O(f(x_n)^3)\\ &=f\frac{\frac14f^2f''^2}{(f'^2-ff'')\left[(f'^2-\frac12ff'')+|f'|\sqrt{f'^2-ff''}\right]}+O(f(x_n)^3)\\ &=O(f(x_n)^3) \end{align} For simple roots the function value is proportional to the distance to the root, so that this computation establishes third order convergence.