2

Let $f\in C^2$ and $x^*$ be a simple root of $f$, i.e. $f(x^*)=0\wedge f'(x^* )\ne 0$. Further, let $U(x^*):=\left\{x : |x-x^* |\le r\right\}$ for some $r>0$ and

$\;\;\;\;\;\;\;\;\;\;\displaystyle y^{(n)}:=x^{(n)}-\frac{f(x^{(n)})}{f'(x^{(n)})}\;,\;\;\;x^{(n+1)}:=y^{(n)}-\frac{f(y^{(n)})}{f'(x^{(n)})}$

describe the two-stage Newton method. I want to show that $\left(x^{(n)}\right)_{n\in\mathbb{N}_0}$ converges locally with order $3$ to $x^*$.

Proof $\;\;\;f\in C^1$ and $f'(x^*)\ne 0$ $\Rightarrow$ there exists a neighbourhood $U'(x^*)\subset U(x^*)$ such that

$\;\;\;\;\;\;\;\;\;\;|f'(x)|>0\;\;\;\forall x\in U'(x^*)$

Let $x^{(n+1)}\in U'(x^*)$. By using the mean-value theorem for differentiation, it holds

$\;\;\;\;\;\;\;\;\;\;\left|x^{(n+1)}-x^*\right|\le \left|y^{(n)}-x^*\right|\left|1-\frac{f'(\xi)}{f'(x^{(n)})}\right|$

for some $\xi\in (y^{(n)},x^*)$ and

$\;\;\;\;\;\;\;\;\;\;\left|1-\frac{f'(\xi)}{f'(x^{(n)})}\right|\le L_1\in (0,1)$

is satisfiable. Now, we can proceed in the same way with $y^{(n)}$ to obtain

$\;\;\;\;\;\;\;\;\;\;|y^{(n)}-x^*|\le \left|x^{(n)}-x^*\right|\left|1-\frac{f'(\zeta)}{f'(x^{(n)})}\right|$

for some $\zeta\in (x^{n)},x^*)$ and

$\;\;\;\;\;\;\;\;\;\;\left|1-\frac{f'(\zeta)}{f'(x^{(n)})}\right|\le L_2\in (0,1)$

is satisfiable, too. Taking everything into account we get

$\;\;\;\;\;\;\;\;\;\;|x^{(n+1)}-x^*|\le L_1|y^{(n)}-x^*|\le L_1L_2|x^{(n)}-x^*|$

However, while this is beautiful, it only leads to linear convergence. I've missed to use $f\in C^2$. What can I conclude from that and how will it help to show the convergence of order 3?

0xbadf00d
  • 13,422

1 Answers1

1

I could not figure the solution in - like half an hour to this. But you can improve your result to be at least of order 2, the same as the unmodified newton method. Consider your last line: $|y_n -x^*|$ $y_n$ is the simple newton method.
Expand the function $f$ into a Taylor series up to order 2 with lagrangian remainder at $x_k$
$f(x)=f(x_k)+f'(x_k)(x-x_k)+f''(\xi)(x-x_k)^2/2$
Now evaluate this at $x=x^*$ using the assumption that $f$ has a root there.
Then expand $|y_n-x^*|$ and solve the evaluated taylor expansion for an appropriate term.

Thus you will have shown that the method is at least of order 2.

I will look into the remainder of the task later today.

Nox
  • 634
  • Thanks for your answer. Do you think one could prove the convergence of order 3 at all? Taylor polynomial is a good point. I thought about that too, but wasn't able to figure out how it could help. – 0xbadf00d Jan 14 '14 at 15:31
  • It is. In fact, as far as I recall the proof, that if $\phi$ is an FPI of order $k$ and $\psi$ is an FPI of order $p$, then $\psi\circ\phi$ is an FPI of order $k+p$ is given in a book by Collatz "Functional analysis and numerical mathematics". For a second attempt at the solution see the edit above. – Nox Jan 14 '14 at 22:05