Newton root-finding iteration ($t_{r+1}=t_r-F(t_r)/F^{\prime }(t_r)$)

The Newton root-finding iteration seeks a zero of a function $F$ by repeatedly solving its tangent line approximation. At a current guess $t_r$ with derivative $F^{\prime }(t_r)\ne 0$, setGeometrically, follow the tangent line to the horizontal axis, then return to the function graph for the next tangent line. Close to a suitable zero of a function, the error becomes dramatically smaller.^[ref]

For a concrete square root calculation, take the polynomial $F(t)=t^2-2$ and start at $t_0=1$. The Newton root-finding iteration becomes $t_{r+1}=(t_r+2/t_r)/2$, givingThe errors use the unrounded iterates. After the first step, each iterate overestimates $\sqrt{2}$, and the exact identityexhibits quadratic convergence: once close, the number of correct decimal digits roughly doubles per step. This speed makes the Newton root-finding iteration useful when accurate derivatives are available.

Global convergence requires additional care. For the polynomial $F(x)=x^3-2x+2$, starting at $x_0=0$ gives $F(0)=2$, $F^{\prime }(0)=-2$, hence $x_1=1$. Then $F(1)=1$, $F^{\prime }(1)=1$ gives $x_2=0$. The sequence repeats $0,1,0,1,\dots$ forever, although a real polynomial root lies in $(-2,-1)$ by the intermediate value theorem. Neither point in the cycle is a zero of a function, and neither has zero derivative. A maintained sign-changing interval and fallback bisection method can protect a root solver from unsuitable Newton steps.

A secant-updating method for a vector equation $F(x)=0$, named for Charles George Broyden. Solve $B_k{d}_k=-F(x_k)$, choose $x_{k+1}=x_k+{\alpha }_k{d}_k$, and form $s_k=x_{k+1}-x_k$, $y_k=F(x_{k+1})-F(x_k)$. For a nonzero step the displayed “good Broyden” update satisfies $B_{k+1}{s}_k=y_k$, learning the Jacobian matrix action along the observed step rather than evaluating a new full Jacobian matrix.

The update also has a least-change characterization in the Frobenius norm. Write $u=y_k-B_k{s}_k$. Any correction $E$ satisfying $E{s}_k=u$ has squared row norms bounded below by $u_i^2/\Vert s_k{\Vert }^2$, by the Cauchy-Schwarz inequality. Summing these bounds gives $\Vert E{\Vert }_F^2\ge \Vert u{\Vert }^2/\Vert s_k{\Vert }^2$, with equality for $E=u{s}_k^{\mathsf{T}}/\Vert s_k{\Vert }^2$. This proves the rank-one correction is the least-change update satisfying the secant constraint. Superlinear convergence needs local regularity and suitable initialization; it is not a global consequence of this algebraic identity.^[ref]

Suppose $f\in C^2([a,r])$, $f(r)=0$, $f^{\prime }\ge m>0$ and $-K\le f^{\prime \prime }<0$. Starting at $x_0\in [a,r)$, the Newton root-finding iteration remains below $r$ and increases strictly to it. To prove this, assume $x_n<r$. Strict increase of $f$ gives $f(x_n)<0$, so the Newton step is positive. Taylor's theorem between $x_n$ and $r$ gives, with $e_n=x_n-r$,Its coefficient is negative and at least $-K/(2m)$, proving both the stated error bound and $x_n<x_{n+1}<r$. Mathematical induction establishes the invariant. The increasing bounded iterates have a limit $L\le r$; continuity in $x_{n+1}-x_n=-f(x_n)/f^{\prime }(x_n)$ forces $f(L)=0$, hence $L=r$. The error bound supplies local quadratic convergence.

If a sufficiently smooth function has the form $f(x)=(x-\alpha {)}^{m}q(x)$ with $m>1$ and $q(\alpha )\ne 0$, then the Newton root-finding iteration satisfiesThus the ratio of successive nonzero errors tends to $(m-1)/m$: the usual iteration has only linear convergence. Cancelling the common factor in $f/f^{\prime }$ produces a continuous extension at the multiple root, although the original quotient is undefined there. An implementation should stop upon finding an exact zero of a function.

For the quadratic polynomial $f(x)=(x-a{)}^2-b^2$ with $b>0$, consider the Newton root-finding iteration towards the polynomial root $x_{\ast }=a+b$. If $x_k\ne a$, its signed error $e_k=x_k-x_{\ast }$ satisfiesIndeed the iteration for $u_k=x_k-a$ is $u_{k+1}=(u_k+b^2/u_k)/2$, and subtracting $b$ yields $(u_k-b{)}^2/(2u_k)$. This exact identity explains quadratic convergence near the simple polynomial root. If an initial error is asymptotic to $C{\epsilon }^m$ and $x_k-a\to b\ne 0$ as $\epsilon \to 0$, one step changes its leading power to $2m$ and its coefficient to $C^2/(2b)$.

Let $F$ be twice continuously differentiable on an interval around a zero of a function $t_{\ast }$, with $|F^{\prime }(t)|\ge m>0$ and $|F^{\prime \prime }(t)|\le M$ there. Choose a closed interval $[t_{\ast }-\rho ,t_{\ast }+\rho ]$ inside that interval with $M\rho /(2m)<1$. Starting inside it makes the Newton root-finding iteration well defined, keeps it inside, and gives the displayed quadratic convergence bound for $e_r=t_r-t_{\ast }$. The nonzero derivative and sufficiently close start are essential hypotheses. The scalar estimate follows from the Taylor remainder argument in MIT's root-finding notes.^[ref]

For a short proof outline, apply Taylor's theorem between $t_r$ and $t_{\ast }$; subtract the defining tangent line equation. The linear error cancels, leaving $e_{r+1}=F^{\prime \prime }({\xi }_r)e_r^2/(2F^{\prime }(t_r))$. The displayed bound shrinks the error and preserves the chosen interval. If $F^{\prime \prime }(t_{\ast })\ne 0$, the error ratio tends to $|F^{\prime \prime }(t_{\ast })/(2F^{\prime }(t_{\ast }))|$; if it vanishes, convergence can be faster.

For the strictly convex polynomial $f(x)=x^2/2+x^4/4$, applying Newton root-finding iteration to $f^{\prime }(x)=x+x^3$ givesThe unique minimum is at zero. For any sufficiently small nonzero initial point, the errors satisfy $|x_{k+1}|/|x_k{|}^3\to 2$, so the order is cubic, not merely quadratic. This provides a simple counterexample to treating the usual quadratic convergence theorem as an upper bound on possible orders. In general, the quadratic coefficient for Newton optimization near a nondegenerate stationary point is $f^{(3)}(x_{\ast })/(2f^{\prime \prime }(x_{\ast }))$; when it vanishes, a higher order is possible.

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

Let $f\in C^2([a,b])$ have $f^{\prime },f^{\prime \prime }>0$ and $f(a)<0<f(b)$. Its unique root $r$ lies in $(a,b)$. Starting Newton root-finding iteration at $b$, strict convexity puts the tangent root strictly between $r$ and the current iterate, so the iterates decrease to $r$. Taylor expansion about the current iterate gives $e_{n+1}=f^{\prime \prime }({\xi }_n)e_n^2/[2f^{\prime }(x_n)]$, where $e_n=x_n-r$ and ${\xi }_n\in (r,x_n)$. Continuity proves the displayed positive asymptotic constant and quadratic convergence.