Convergence of Newton's method for Banach spaces

160 Views Asked by At

Let $F:U\subset V\rightarrow V$ be a $C^1$ function in a Banach space such that $F(x_*)=0$ and $DF(x_*)$ is invertible. I want to prove that there exists $r>0$ such that if $x_0\in B(x_*,r)$ then the sequence $x_n=x_{n-1}-DF(x_{n-1})^{-1}(F(x_n))$ converges to $x_*$.

To do this first I argue that since $x\rightarrow DF(x)$ is continous and the set of invertible operators in $L(V)$ is open, I can find $r_*>0$ such that $x\in\overline{U_0}=\overline{B(x,r_*)}\subset U$ implies $DF(x)$ invertible. With this done, I can define $G:\overline{U_0}\rightarrow V$ by $G(x)=x-DF(x)^{-1}(F(x))$. If I prove that $G(\overline{U_0})\subset \overline{U_0}$ and that $G$ is a contraction, then it is finished since $x_*$ is a fixed point.

If instead of letting $DF(x)^{-1}$ change we fix $DF(x_*)^{-1}$ in the sequence above, I can use the mean value theorem to prove the above statements, my problem when $DF^{-1}$ can change with $x$. I wasn't able to find the way yet. Could anyone help me?

1

There are 1 best solutions below

1
On

The bounded inverse theorem shows that $F'(x^*)^{-1}$ is bounded.

Since $F$ is differentiable at $x^*$, for any $\epsilon>0$ there is some $\delta>0$ such that if $\|x-x^*\| < \delta$ then $\|F(x)-F(x^*)-F'(x^*)(x-x^*)\| \le \epsilon \|x-x^*\|$.

A standard result is that if $A$ is invertible and $\|A^{-1}H\| < 1$ then $A+H$ is invertible and $\|(A+H)^{-1}\| \le {\|A^{-1}\| \over 1-\|A^{-1}H\| }$.

$F'$ is continuous and invertble at $x^*$. Letting $A=F'(x^*)$ and $H=F'(x)-F'(x^*)$ we see that there is some $M>0$ and $\delta' >0$ such that if $\|x-x^*\|< \delta'$ then $\|F'(x)^{-1}\| \le M$.

Now choose $\delta''>0$ such that (i) $\delta'' \le \delta'$, (ii) the first condition holds with $\epsilon = {1 \over 4}M$ and $\|F'(x)-F'(x^*)\| < {1 \over 4}M$ when $\|x-x^*\| < \delta'''$.

Let $\phi(x) = x-F'(x)^{-1}F(x)$. Then \begin{eqnarray} \phi(x)-x^* &=& x-x^* - F'(x)^{-1} F(x) \\ &=& x-x^* - F'(x)^{-1} (F(x) -F(x^*))\\ &=& F'(x)^{-1}(F'(x)(x-x^*) - (F(x) -F(x^*))\\ &=& F'(x)^{-1}((F'(x)-F'(x^*))(x-x^*) + F'(x^*)(x-x^*)- (F(x) -F(x^*))\\ \end{eqnarray} Hence $\| \phi(x)-x^* \| \le M ({1 \over 4 M} \|x-x^*\| + {1 \over 4 M} \|x-x^*\| ) \le {1 \over 2} \|x-x^*\|$

In particular, $\|x_{n+1}-x^*\| \le {1 \over 2} \|x_n-x^*\|$.

Note: This result is different to the Newton Kantorovich theorem which gives conditions under which the $x^*$ will exist. In the above case, the existence of $x^*$ is assumed a priori.