This might be a dumb question, but I want to see how Newton's method can be understood in the context of Banach fixed point theorem (BFPT):

A closed subset of a complete metric space is complete. If $f:A\to A$ is is differentiable on a closed subset $A\subseteq\mathbb{R}$ and $|f'(x)|<1$ for all $x\in A$, then $g$ is a contraction, and by Banach fixed point theorem, has a unique attracting fixed point $x^*$.

We want to approximate the zero of a function $g$ defined on $A$. Now if the contraction map is given by $f(x)=x-\frac{g(x)}{g'(x)}$, then clearly $f(x^*)=x^*\implies x^*$ is a root of $g$. Such a $x^*$ exists, is unique and attracting by BFPT.

What are the conditions on $g$ needed for $f$ to be a contraction? Clearly we need $g'(x)\neq 0$ in $A$ for $f$ to be defined. What else? We also need that $f$ must map $A$ to $A$, and $|f'(x)|<1$ for sufficiency. We have $|f'(x)|=|\frac{g(x)g''(x)-g'^2(x)}{g'^2(x)}|=\frac{|g(x)g''(x)-g'^2(x)|}{g'^2(x)}$. I'm stuck here: how to show (or impose sufficient conditions on $g$ such that) $|f'(x)|<1$ and $f$ maps $A$ to $A$?

  • 1
    $\begingroup$ Since you need $g$ differentiable, you don't want to do this on an arbitrary closed subset of $\Bbb R$. Let $A$ be an interval. Secondly, your $|f'|$ condition only requires $g' \ne 0$, not $g''$. And for solving the inequality, consider first the case when $g, g', g''$ are all positive. Once you have that, it may shed some light on what happens when they are allowed to be negative. $\endgroup$ – Paul Sinclair Nov 16 '15 at 3:18
  • 1
    $\begingroup$ Your derivative of $f$ is incomplete. The derivative of the term $x$ is $1$ and does not vanish. $\endgroup$ – LutzL Nov 17 '15 at 9:30

The conceptual problem here is that you assume that you already know the root and just analyze the convergence speed.

However, the important part of the Banach fixed-point theorem is that it provides existence of a solution under some general assumptions. The analogue for Newton's method is the Newton-Kantorovich theorem.

In simplified form it states that if you have a domain $D$ and a Lipschitz constant $L$ for the first derivative (or a bound for the second), and start at a point $x_0$ with step $s_0=-F'(x_0)^{-1}F(x_0)$ and if the ball $B=B(x_0+s_0,\|s_0\|)$ is completely contained in $D$ and $$ L·\|F'(x_0)^{-1}\|^2·\|F(x_0)\|<\frac12 $$ then there is a solution to $F(x)=0$ contained in $B$ and the convergence to it is quadratic.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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