Newton iteration in a Banach space ($N(p)=p-[D\Phi (p){]}^{-1}\Phi (p)$)

For a $C^2$ map $\Phi$ on a Banach space, define $N(p)=p-[D\Phi (p){]}^{-1}\Phi (p)$ wherever the bounded derivative is invertible. It solves the local affine approximation to $\Phi =0$. Every zero is a fixed point of $N$. Near a zero with invertible derivative, bounded inverses and a locally Lipschitz derivative give the quadratic Newton error bound in a Banach space.

// Target: numerical-analysis.bigb

The finite-dimensional Newton root-finding iteration for a vector equation $G(x)=0$. At a point with invertible Jacobian matrix, solve the displayed linear system. For $G=\nabla F$, its Jacobian matrix is the Hessian matrix, giving Newton's method in optimization. The update solves the affine first-order approximation $G(x_k)+DG(x_k)s_k=0$; it can converge to any nondegenerate critical point, including a saddle point.

A multivariable Newton iteration correction must solve the linear system $D\mathbf{f}(\mathbf{x})\mathbf{s}=-\mathbf{f}(\mathbf{x})$. It exists exactly when the right-hand side is in the image of the Jacobian matrix, and is unique when that Jacobian matrix is invertible. At a singular matrix, there may be either no corrections or several; singularity alone does not decide which. For finding a critical point of a scalar function $F$, use $\mathbf{f}=\nabla F$, so the Jacobian matrix is the Hessian matrix. Equal rows of the Hessian matrix with unequal corresponding gradient entries immediately make the correction equations inconsistent.

To solve $\Phi (p)=p$, let $J$ be a bounded approximation to $(D\Phi (p_0)-I{)}^{-1}$ and set $A(p)=p-J(\Phi (p)-p)$. Its derivative is $DA(p)=I-J(D\Phi (p)-I)$. Every fixed point of $\Phi$ is fixed by $A$; the converse holds when $J$ is injective. A good inverse approximation makes $A$ a contraction mapping even if $\Phi$ itself has an expanding direction.

// Target: analysis.bigb

Let $\Phi (\bar{p})=0$, $\Vert [D\Phi (p){]}^{-1}\Vert \le M$ and $\Vert D\Phi (p)-D\Phi (q)\Vert \le L\Vert p-q\Vert$ near $\bar{p}$. The integral Taylor remainder givesA small ball with $(ML/2)r<1$ is invariant under $N$. Iteration there converges at least quadratically, with $C{e}_{n+k}\le (C{e}_n{)}^{2^k}$ for $C=ML/2$.

// Target: numerical-analysis.bigb