2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – Ma Joad
    Commented Jun 25, 2019 at 9:50
  • $\begingroup$ 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? $\endgroup$
    – Ma Joad
    Commented Jun 25, 2019 at 12:17
  • $\begingroup$ 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. $\endgroup$
    – Ma Joad
    Commented Jun 25, 2019 at 13:45
  • $\begingroup$ 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}$? $\endgroup$
    – Ma Joad
    Commented Jun 25, 2019 at 13:55
  • $\begingroup$ Ah, sorry, forgot you were working on a Banach space for a while, let me rephrase that as an inequality. $\endgroup$ Commented Jun 25, 2019 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.