Nonlinear equations and Newton methods

Let $(X,d)$ be a metric space (Metric space: $d(x,y)=0$ iff $x=y$, symmetry, and the triangle inequality; pseudometric and ultrametric), let $G:X\to X$ be a specified map, and choose an initial point $x_0\in X$, a residual tolerance $\epsilon \ge 0$, and an iteration budget $N\in {\mathbb{N}}_0$. A fixed point of $G$ is a point $x$ with $G(x)=x$. The procedure returns a point and a status as follows. For $k=0,1,\dots ,N$, compute the fixed-point residual $r_k:=d(G(x_k),x_k)$. If $r_k\le \epsilon$, return $(x_k,\mathtt{\text{residual-tolerance-met}},r_k,k)$. Otherwise, if $k=N$, return $(x_k,\mathtt{\text{iteration-budget-exhausted}},r_k,k)$. Otherwise set $x_{k+1}:=G(x_k)$ and continue.

A positive residual tolerance reports an approximate fixed point only; this definition asserts no convergence or error bound.

For admissible inputs of Fixed-point iteration with a residual stop and finite budget with budget $N\in {\mathbb{N}}_0$, every entered iterate belongs to $X$. The procedure uses at most $N$ updates and $N+1$ fixed-point residual evaluations and returns one of its stated statuses. Termination is in the model where each map evaluation, metric evaluation and comparison returns in finite time. These counts specify outer procedure operations and give no bound on the internal cost of evaluating the supplied map or metric.

Let $n\ge 1$, let $A:{\mathbb{R}}^n\to {\mathbb{R}}^n$ be a linear map, and let $r\in {\mathbb{R}}^n$ be a residual vector. If $A$ is not invertible in the sense of Invertible Euclidean linear maps, return $(\mathtt{\text{singular-jacobian}},\mathrm{\varnothing })$. If $A$ is invertible, return $(\mathtt{\text{correction}},s)$, where $s$ is the unique vector solving $As=-r\mathrm{.}$

Use the following exact-arithmetic procedure, with exact real zero tests. Represent $A$ by its matrix in the standard basis, with indices $0\le i,j<n$.

1. To compute the determinant of any matrix $M=(m_{ij})$ below, initialize $d=0$. Enumerate the permutations $\sigma$ of $\{0,\dots ,n-1\}$ in lexicographic order. For each, count its inversions $\nu (\sigma )=\mathrm{\#}\{(i,j):i<j,\sigma (i)>\sigma (j)\}$, multiply $p={\prod }_{i=0}^{n-1}{m}_{\sigma (i),i}$ in increasing index order, and add $(-1{)}^{\nu (\sigma )}p$ to $d$. The resulting $d$ is the determinant in For $n\ge 1$, the determinant over a commutative ring by the Leibniz formula, and $\mathrm{\mid }\det A\mathrm{\mid }$ for a real matrix.
2. Compute $d=\det (A)$ by step 1. If $d=0$, return $(\mathtt{\text{singular-jacobian}},\mathrm{\varnothing })$, using A finite square real matrix is invertible if and only if its determinant is nonzero for the invertibility test.
3. Otherwise, for $j=0,\dots ,n-1$, copy $A$ to $A_j$, replace column $j$ by $-r$, compute $d_j=\det (A_j)$ by step 1, and set $s_j=d_j\mathrm{/}d$. Return $(\mathtt{\text{correction}},s)$, the solution specified by Cramer's rule over a commutative ring: every solution satisfies $\det (A)x_j=\det (A_j(b))$, and a unit determinant gives the unique quotient formula over $\mathbb{R}$.

The output is a linear correction, not a claim that $r$ came from a nonlinear function or that applying the correction decreases a residual.

Let $n\ge 1$, let $U\subseteq {\mathbb{R}}^n$ be open, and let $F:U\to {\mathbb{R}}^n$ be $C^1$ in the sense of Continuously differentiable maps, local inverses, and local diffeomorphisms. Its Jacobian $J_F(x)$ is the matrix of first partial derivatives from The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case, and the matrix of $DF(x)$ in the standard basis is $J_F(x)$ by A total derivative computes every directional derivative, and its matrix is the Jacobian. For $x\in U$, supply increments $h=(h_0,\dots ,h_{n-1})\in {\mathbb{R}}^n$. For each standard basis vector $e_i$ with $0\le i<n$, the admissible stencil conditions are $h_i\mathrm{\ne }0$ and $x+h_i{e}_i\in U$.

If any admissibility condition fails, return invalid-stencil. Otherwise form the matrix $J_{h}F(x)$ column by column: $J_{h}F(x)e_i:=\frac{F(x+h_i{e}_i)-F(x)}{h_i},0\le i<n\mathrm{.}$ Return success and this matrix. Each evaluation point is in $U$. This procedure defines a forward-difference approximation; it asserts no accuracy or convergence guarantee.

Let $n\ge 1$, let $U\subseteq {\mathbb{R}}^n$ be open, let $F:U\to {\mathbb{R}}^n$ be $C^1$, and write $J(x)=DF(x)$ as a matrix in the standard basis. The matrix of $DF(x)$ agrees with the Jacobian matrix by A total derivative computes every directional derivative, and its matrix is the Jacobian. For a matrix $A$ let $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}:={\sup }_{\mathrm{\parallel }v{\mathrm{\parallel }}_2=1}\mathrm{\parallel }Av{\mathrm{\parallel }}_2$. Let $K\subseteq U$ be convex, let $x_{\ast },x\in K$, and suppose for some $L\ge 0$ that $\mathrm{\parallel }J(y)-J(z){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le L\mathrm{\parallel }y-z{\mathrm{\parallel }}_2(y,z\in K)\mathrm{.}$ Then $\mathrm{\parallel }F(x)-F(x_{\ast })-J(x)(x-x_{\ast }){\mathrm{\parallel }}_2\le \frac{L}{2}\mathrm{\parallel }x-x_{\ast }{\mathrm{\parallel }}_2^2\mathrm{.}$

Let $n\ge 1$, let $U\subseteq {\mathbb{R}}^n$ be open, and let each component $F_j:U\to \mathbb{R}$, $j<n$, be $C^2$ (twice continuously differentiable). Fix $x\in U$ and increments $h=(h_0,\dots ,h_{n-1})\in {\mathbb{R}}^n$ with $h_i\mathrm{\ne }0$ for every $i<n$. For each $i<n$, suppose an open interval $I_i\subseteq \mathbb{R}$ contains $[0,1]$ and $x+t{h}_i{e}_i\in U$ for every $t\in I_i$. Suppose finite constants $M_{ij}\ge 0$ satisfy $\mathrm{\mid }{\mathrm{\partial }}_{ii}{F}_j(x+t{h}_i{e}_i)\mathrm{\mid }\le M_{ij}(0\le t\le 1,j<n)\mathrm{.}$ Put $M_i:=({\sum }_{j<n}{M}_{ij}^2{)}^{1\mathrm{/}2}$ and $M:={\max }_{i<n}{M}_i$. Let $J_{h}F(x)$ be the forward-difference matrix of Forward-difference Jacobian on an open domain, let $J_F(x)$ be the Jacobian matrix of The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case. With the Euclidean operator norm on matrices, $\mathrm{\parallel }{J}_{h}F(x)-J_F(x){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \frac{M}{2}\mathrm{\parallel }h{\mathrm{\parallel }}_2\mathrm{.}$

Let $U\subseteq {\mathbb{R}}^n$ be open, $n\ge 1$, and let $F:U\to {\mathbb{R}}^n$ be $C^1$ (Continuously differentiable maps, local inverses, and local diffeomorphisms) with Jacobian $J_F$ as in The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case. The matrix of $DF(x)$ in the standard basis is $J_F(x)$ by A total derivative computes every directional derivative, and its matrix is the Jacobian. Inputs: $x_0\in U$, residual tolerance $\epsilon \ge 0$, and update budget $N\in {\mathbb{N}}_0$. Output: the last valid iterate and one of root, singular-jacobian, invalid-trial, or iteration-budget-exhausted.

For $k=0,1,\dots ,N$, in this order:

1. Compute $F(x_k)$. If $\mathrm{\parallel }F(x_k){\mathrm{\parallel }}_2\le \epsilon$, return $(x_k,\mathtt{\text{root}})$. Here root means the residual tolerance was met; it does not certify an exact zero when $\epsilon >0$.
2. If $k=N$, return $(x_k,\mathtt{\text{iteration-budget-exhausted}})$.
3. Call Newton correction for a square vector residual with $A=J_F(x_k)$ and $r=F(x_k)$. If it returns singular-jacobian, return $(x_k,\mathtt{\text{singular-jacobian}})$.
4. Let $s_k$ be its correction. If $x_k+s_k\mathrm{\notin }U$, return $(x_k,\mathtt{\text{invalid-trial}})$. Otherwise set $x_{k+1}=x_k+s_k$.

It makes no arbitrary-start, global-convergence, or discretization-error claim.

For admissible inputs of Finite-budget Newton for a square vector residual with budget $N\in {\mathbb{N}}_0$, every entered iterate lies in $U$. The procedure makes at most $N$ correction calls, at most $N$ accepted updates, and at most $N+1$ explicit outer residual evaluations. It returns a stated residual, singular-Jacobian, invalid-trial or budget status. Termination is in the exact-arithmetic model where residual and Jacobian evaluations, domain decisions and correction calls return in finite time. No convergence, tolerance-attainment or backend complexity claim follows.

Let $U\subseteq {\mathbb{R}}^n$ be open, $n\ge 1$, and let $F:U\to {\mathbb{R}}^n$ be $C^1$ (Continuously differentiable maps, local inverses, and local diffeomorphisms) with Jacobian $J_F$ as in The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case. The matrix of $DF(x)$ in the standard basis is $J_F(x)$ by A total derivative computes every directional derivative, and its matrix is the Jacobian. Define the residual merit $\mathrm{\Phi }(x):=\frac{1}{2}\mathrm{\parallel }F(x){\mathrm{\parallel }}_2^2$. Inputs: $x_0\in U$, residual tolerance $\epsilon \ge 0$, update budget $N\in {\mathbb{N}}_0$, sufficient-decrease parameter $\alpha \in (0,1)$, reduction factor $\beta \in (0,1)$, and finite backtrack budget $B\in {\mathbb{N}}_0$. Output: the last valid iterate and one of root, singular-jacobian, invalid-trial, line-search-exhausted, or iteration-budget-exhausted.

At iteration $k=0,1,\dots ,N$, apply these instructions in order:

1. Evaluate $F(x_k)$. If $\mathrm{\parallel }F(x_k){\mathrm{\parallel }}_2\le \epsilon$, return $(x_k,\mathtt{\text{root}})$. This status records the residual test only.
2. If $k=N$, return $(x_k,\mathtt{\text{iteration-budget-exhausted}})$.
3. Call Newton correction for a square vector residual with $A=J_F(x_k)$ and $r=F(x_k)$. If it returns singular-jacobian, return $(x_k,\mathtt{\text{singular-jacobian}})$. Otherwise let $s_k$ be its correction.
4. For $j=0,1,\dots ,B$, set $t={\beta }^j$ and trial $y=x_k+t{s}_k$. If $y\mathrm{\notin }U$, reject the trial and continue. If $y\in U$, evaluate $\mathrm{\Phi }(y)$ and accept the first trial satisfying $\mathrm{\Phi }(y)\le \mathrm{\Phi }(x_k)-\alpha t\mathrm{\parallel }F(x_k){\mathrm{\parallel }}_2^2\mathrm{.}$ On acceptance set $x_{k+1}=y$ and continue at iteration $k+1$.
5. If no trial was accepted, return $(x_k,\mathtt{\text{invalid-trial}})$ if every tested point was outside $U$; otherwise return $(x_k,\mathtt{\text{line-search-exhausted}})$.

The residual-merit test is defined directly for a vector root problem. A finite backtrack budget can return failure; no global convergence or quadratic-rate claim is made.

Use the same open domain, differentiability assumptions, initial point, residual tolerance and update budget as Finite-budget Newton for a square vector residual. Supply one increment vector $h=(h_0,\dots ,h_{n-1})$ with every $h_i\mathrm{\ne }0$ for $0\le i<n$. Output: the last valid iterate and one of root, invalid-stencil, singular-jacobian, invalid-trial, or iteration-budget-exhausted; every returned status is paired with the current last valid iterate.

For $k=0,1,\dots ,N$, in this order:

1. Evaluate $F(x_k)$. If $\mathrm{\parallel }F(x_k){\mathrm{\parallel }}_2\le \epsilon$, return $(x_k,\mathtt{\text{root}})$.
2. If $k=N$, return $(x_k,\mathtt{\text{iteration-budget-exhausted}})$.
3. Call Forward-difference Jacobian on an open domain at $(F,x_k,h)$. If it returns invalid-stencil, return $(x_k,\mathtt{\text{invalid-stencil}})$.
4. Otherwise call Newton correction for a square vector residual with $A=J_{h}F(x_k)$ and $r=F(x_k)$. If that correction is unavailable, return $(x_k,\mathtt{\text{singular-jacobian}})$. Otherwise let $s_k$ be the returned correction.
5. If the trial $x_k+s_k$ is outside $U$, return $(x_k,\mathtt{\text{invalid-trial}})$; otherwise set $x_{k+1}=x_k+s_k$ and continue.

The root status still means only $\mathrm{\parallel }F(x_k){\mathrm{\parallel }}_2\le \epsilon$. This approximate-Jacobian procedure has no quadratic-rate claim here.

Let $n\ge 1$, let $U\subseteq {\mathbb{R}}^n$ be open, and let $F:U\to {\mathbb{R}}^n$ be $C^2$, meaning $F$ is $C^1$ and its first derivative is itself continuously differentiable. Write $J(x)=DF(x)$ as a matrix in the standard basis. Let $x_{\ast }\in U$ satisfy $F(x_{\ast })=0$ and suppose $J(x_{\ast })$ is invertible. Suppose there are $R>0$ and $L\ge 0$ such that the closed Euclidean ball ${\bar{B}}_2(x_{\ast },R):=\{x\in {\mathbb{R}}^n:\mathrm{\parallel }x-x_{\ast }{\mathrm{\parallel }}_2\le R\}$ lies in $U$ and $\mathrm{\parallel }J(x)-J(y){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le L\mathrm{\parallel }x-y{\mathrm{\parallel }}_2(x,y\in {\bar{B}}_2(x_{\ast },R)),$ where $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}:={\sup }_{\mathrm{\parallel }v{\mathrm{\parallel }}_2=1}\mathrm{\parallel }Av{\mathrm{\parallel }}_2$. Then there are $r\in (0,R]$ and $K>0$ such that every $J(x)$ on ${\bar{B}}_2(x_{\ast },r)$ is invertible with $\mathrm{\parallel }J(x{)}^{-1}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le K$. Put $C:=KL\mathrm{/}2$ and choose $\rho \in (0,r]$ with $C\rho \le 1\mathrm{/}2$ (if $L=0$, any $\rho \le r$ works).

For every $x_0\in {\bar{B}}_2(x_{\ast },\rho )$, each update attempted by Finite-budget Newton for a square vector residual is defined, remains in this ball, and satisfies $\mathrm{\parallel }{x}_{k+1}-x_{\ast }{\mathrm{\parallel }}_2\le C\mathrm{\parallel }{x}_k-x_{\ast }{\mathrm{\parallel }}_2^2\mathrm{.}$ If the ordinary exact-Jacobian Newton recurrence is continued indefinitely, these estimates imply $x_k\to x_{\ast }$ with a quadratic error bound. A finite budget may stop before the residual tolerance is met; root status records only that tolerance, not an exact-zero certificate. This result gives no arbitrary-start or global-convergence guarantee.

Use the inputs and residual merit $\mathrm{\Phi }(x)=\frac{1}{2}\mathrm{\parallel }F(x){\mathrm{\parallel }}_2^2$ of Finite-budget residual-merit damped Newton. At any iterate where the procedure accepts a step $t>0$ with $F(x)\mathrm{\ne }0$, the accepted point $x_{+}=x+ts$ satisfies $\mathrm{\Phi }(x_{+})\le \mathrm{\Phi }(x)-\alpha t\mathrm{\parallel }F(x){\mathrm{\parallel }}_2^2<\mathrm{\Phi }(x)\mathrm{.}$ This statement concerns accepted steps only; it does not assert that a chosen finite backtrack budget will accept a trial.