0
$\begingroup$

So, I'm currently studying Newton method used for finding the 0's of a function, however my professor has only announced that the speed of this algorithm can be more than quadratic, however I'm wondering when this happens, since in the demonstration used by him to explain the quadratic case, there is no evidence about the "more than quadratic"

Using Taylor and Lagrange
$f(\xi)=f(x_n)+f'(x_n)(\xi-x_n)+\frac{f''(z_n)}{2}(\xi-x_n)^2$

$-\frac{f(x_n)}{f'(x_n)}=\xi-x_n+\frac{f''(z_n)}{2f'(x_n)}(\xi-x_n)^2$

$x_{n+1}-x_n=\xi-x_n+\frac{f''(z_n)}{2f'(x_n)}(\xi-x_n)^2$

$e_{n+1}=\left|x_{n+1}-\xi\right|=c_ne_n^2 \quad \text{with} \quad c_n=\frac{1}{2}\frac{\left|f''(z_n)\right|}{\left|f'(x_n)\right|}$

Can someone please tell me when (example) the order of the convergence is cubic, and why?=

$\endgroup$
1
  • 1
    $\begingroup$ Just to see an example that converges faster, consider $f(x)=x$. $\endgroup$ – plop Aug 18 '20 at 17:35
2
$\begingroup$

Since you asked specifically about cubic, consider $f(x)=x+x^3$.

The Newton iteration would be $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{x_n+x_n^3}{1+3x_n^2}=\frac{2x_n^3}{1+3x_n^2}$$

It converges to the root $x=0$. So, for $1-3|x_n|^2>1/2$,

$$\epsilon_{n+1}=|x_{n+1}-0|=\frac{2|x_n|^3}{|1+3x_n^2|}\leq \frac{2|x_n|^3}{1-3|x_n|^2}\leq 4|x_n-0|^3=4\epsilon_n^3$$

$\endgroup$
2
  • $\begingroup$ so we can say that a function that has all the derivates from 2 to N-1 equals to 0, and the N-th not 0, then it will have N as convergence velocity? $\endgroup$ – Berto99 Aug 18 '20 at 20:21
  • $\begingroup$ @Berto99 In general the convergence depends also on the initial point. You don't specify in your comment where are the properties that you mention satisfied. Is it at a point, or everywhere? If you just want a family of examples you can take $f(x)=x+x^r$, with $r>1$. You will get convergence of order $r$. $\endgroup$ – plop Aug 18 '20 at 20:32
1
$\begingroup$

Look at your expression for the error, and extend the base series one more term: If $f''(\xi) = 0$, the convergence is (at least) cubic.

$\endgroup$
2
  • $\begingroup$ so we can say that a function that has all the derivates from 2 to N-1 equals to 0, and the N-th not 0, then it will have N as convergence velocity? $\endgroup$ – Berto99 Aug 18 '20 at 20:21
  • $\begingroup$ But extending the Taylor series will work really? I will get $f''(x_n) * (xi-x_n)$, and $f''(x_n)$ is not 0, so it doesn't cancel out $\endgroup$ – Berto99 Aug 18 '20 at 20:26

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.