# The Newton-Raphson method in Banach spaces

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.

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.)

• Which mean value theorem do you use here: $f(y) - f(x) = - Df_{\xi} \cdot J_x \cdot f(x)$? Could you just write one or two more steps here? I have not seen any mean value theorems involving $J_x$. Thank you very much. Commented Jun 25, 2019 at 9:50
• The line seems wrong to me: $f(y) - f(x) = - Df_{\xi} \cdot J_x \cdot f(x)$. Let $f(x)=x$. If such identity is true, then $f(2)-f(1)=-f(1)$ which is obviously not true. What's wrong? Have I misunderstood something? Commented Jun 25, 2019 at 12:17
• Oh now I understand the "plugging in". But the standard calculus I mean value theorem does not seem to be true even for functions from $\mathbb R\to \mathbb R^2$. For example, let $f:t \to (\cos\frac{\pi}{2}t, \sin\frac{\pi}{2}t)$. Then $f(1)-f(0)=(-1,1)$, but none of $f'(t),t\in [0,1]$ takes the value $(-1,1)$. It takes the value $\frac{\pi}{2\sqrt2}(-1,1)$ in the middle instead. Commented Jun 25, 2019 at 13:45
• The calculus 1 mean value seems to only apply for real-valued functions. In Banach space shouldn't the mean value theorem be an inequality $\|f(a)-f(b)\|\leq\sup_{c\in [a,b]}{Df_c}$? Commented Jun 25, 2019 at 13:55
• Ah, sorry, forgot you were working on a Banach space for a while, let me rephrase that as an inequality. Commented Jun 25, 2019 at 13:59