# Newton's Method and Banach Fixed Point Theorem

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$?

• 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. – Paul Sinclair Nov 16 '15 at 3:18
• Your derivative of $f$ is incomplete. The derivative of the term $x$ is $1$ and does not vanish. – LutzL Nov 17 '15 at 9:30

## 1 Answer

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.