The Newton-Raphson method in Banach spaces

Question

I am not sure if this question is too easy for mathoverflow - please tell me to remove this question if it is too e before any downvotes. I have asked this on MSE (Link), but it received only a few comments and no answers.

Note: the screenshot at the bottom is where my question comes from.

This question is quite different from other versions of conditions of convergence of Newton iteration. For example, Kantorovich theorem.

I am now analysing the Newton-Raphson iteration in general Banach spaces $E,F$. Let $x_0\in E$, and let $f:B_t(x_0)\to F$ be a differentiable function. ($B$ denotes an open ball with radius $t$.) $L(E,F)$ is the set of linear mapping from $E$ to $F$.

By definition, $f$ is differentiable at $x$ with derivative $Df_x\in L(E,F)$ (which is a linear functional from $E$ to $F$) if $\exists r(h),f(x+h)=f(x)+Df_x(h)+r(h)$, where $r(h)/\|h\|\to 0$ as $h\to 0$.

To make it simple, I assume that there exist $s>0$ such that

• $\|f(x_0)\|\leq t/(2s)$
• If $x,y\in B_t(x_0)$ then $\|Df_x-Df_y\|\leq 1/(2s)$
• $\forall x\in B_t(x_0),\exists J_x\in L(F,E)$ such that $J_xDf_x=Df_xJ_x=I_E$ and $\|J_x\|\leq s$.

---

Now let's work on the iteration. Let's fix $x\in B_t(x_0)$. Set $x_n=x_{n-1}-J_x(f(x_{n-1}))$. In real analysis course, we often take $x=x_{n-1}$, but here I have to fix $x$ to be anything in $B_t(x_0)$. Just assume for a moment that $\forall x\in B_t(x_0)$. I will explain why later.

Firstly I have to show that $x_n$ converges. Now I can use the inequality $$ \|f(a)-f(b)-T(a-b)\|\leq \|a-b\|\sup_{c\in [a,b]} \|Df_c-T\|, $$ where $[a,b]$ is the line segment joining $a,b$, and $T\in L(E,F)$.

To use this inequality, we define $g(y)=J_x(f(y))$, so $x_n=x_{n-1}-g(x_{n-1})$, and $Dg_y=J_xDf_y$.(The reason why I cannot set $x=x_{n-1}$ is that if I do it that way, then $g(y)=J_y(f(y))$, and I cannot find the derivative of $g$ in this case.) Since $x$ is fixed, we can assume there is NO $x$ dependence in $g$. Therefore, $$ \|x_{n+1}-x_{n}\|=\|f(x_{n})-f(x_{n-1})-(x_{n}-x_{n-1})\|\\ \leq \|x_{n}-x_{n-1}\|\sup_{c\in [x_n,x_{n-1}]} \|Dg_c-I\|\\=\|x_{n}-x_{n-1}\|\sup_{c\in [x_n,x_{n-1}]} \|J_xDf_c-J_xDf_x\|\\ \leq \|x_{n}-x_{n-1}\|\|J_x\|\|Df_c-Df_x\|\\ \leq \frac{1}{2} \|x_{n}-x_{n-1}\|. $$ Also, $$ \|x_1-x_0\|=\|J_x(f(x_0))\|\leq t/2 $$ The conclusion is $\|x_n-x_{n-1}\|\leq t/2^n$.

My question: is it really OK to let $x$ be anything fixed in $B_t(x_0)$? Does that really work? If it is wrong, how can I fix it?

---

To prove that $f(x_n)$ converges to zero, I feel that I should prove something like $\|f(x_n)\|\leq t/(2^{n+1}s)$(Suggested in a book of real analysis). I try to start by considering this: $$ \|f(x_n)\|\leq \|Df_x\|\|x_{n+1}-x_n\| $$ but it goes nowhere. From $\|J_x\|\leq s$ we cannot obtain an upper bound on $Df_x$.

So how can I prove $\|f(x_n)\|\leq t/(2^{n+1}s)$?

---

It should be clear that $x_n$ is a Cauchy sequence - but it might not converge into $B_t(x_0)$ - is that a problem?

It is a long question, so if I have made mistakes please point it out.

Please look at the following screenshot if the above is not clear.

---

Source of my problem: A course in mathematical analysis (screenshot)

Here is a theorem of Kantorovich which is related but not the same.

Answer 1

You don't need to fix an arbitrary $x$.

Indeed you would have a problem in that you know nothing about the derivative of the mapping $x \mapsto J_x(f(x))$: but the key is to realize that you only wanted the derivative as a way to control a difference. Using a derivative is somewhat wasteful, especially as you already have assumed something about the difference $Df_y - Df_x$. So the trick is to try to use the hypothesized difference instead of a derivative and see where this gets you.

---

Consider the following: let $$ y := x - J_x \cdot f(x).\tag{0}$$

Considering $x$ as a fixed parameter, let us consider the function $$ G(z;x) = f(z) - f(x) - Df_x\cdot (z - x) $$ Notice that $$ G(x;x) = f(x) - f(x) - 0 = 0 $$ and for $y$ defined as in equation (0) $$ G(y;x) = f(y) - f(x) + Df_x \cdot J_x \cdot f(x) = f(y) $$

Now apply the mean value inequality to the $z$ variable in $G(z;x)$, treating $x$ as fixed, on the segment connecting $x$ to $y$. $$ \| G(y;x) - G(x;x) \| \leq \|y - x\| \cdot \sup_{\xi \in [x,y]} \|DG_\xi\| $$ The quantity $DG$ we evaluate explicitly as $DG_\xi = Df_\xi - Df_x$. And our computations above gives us the estimate $$ \| f(y) \| \leq \|J_x \cdot f(x) \| \sup_{\xi \in [x,y]} \|Df_\xi - Df_x\| \tag{A} $$

Lemma Under the assumptions given in the OP concerning the function $f$ and $J_x$, if $\|x - x_0\| \leq t(1 - 2^{-k})$ and $\|f(x)\| \leq t / 2^{k+1} s$, then $y$ (as defined by formula (0)) satisfies

• $\|y - x_0\| \leq t(1 - 2^{-k-1})$
• $\|f(y) \| \leq t / 2^{k+2} s$

Proof:

For the first statement, notice that $\|y - x\| \leq \|J_x\| \cdot \|f(x)\| \leq t / 2^{k+1}$ since by assumption $x \in B_t(x_0)$. By triangle inequality the first claim follows, which also implies $y \in B_t(x_0)$. By convexity of $B_t(x_0)$ we note that the entire segment $[x,y]$ lies in $B_t(x_0)$.

Therefore we can control $Df_\xi - Df_x$ in formula (A), which yields $$ \|f(y) \| \leq \frac{1}{2s} \cdot s \cdot \|f(x)\| \leq \frac{t}{2^{k+2}s} $$ And the claims are proved.

The hypotheses of the Lemma holds for $x = x_0$ with $k = 0$. By induction it then holds for $x_n$ defined by $x_n = x_{n-1} - J_{x_{n-1}} \cdot f(x_{n-1})$.

As part of the construction clearly the sequence $x_n$ is Cauchy. In fact the construction shows that $\| \lim x_n - x_0 \| \leq t$. (If you want the inequality to be strict, you need one of the assumed inequalities in the hypotheses to also be a strict one.)