Nonlinear equations and Newton methods — Examples

The distance $d(u,v)=\mathrm{\mid }u-v\mathrm{\mid }$ is a metric by [F11], and $\mathbb{R}$ with it is complete by [F2]. This metric space is nonempty because $0\in \mathbb{R}$, as $\mathbb{R}$ is a field by [F11]. For all $u,v\in \mathbb{R}$, $\mathrm{\mid }G(u)-G(v)\mathrm{\mid }=\frac{1}{2}\mathrm{\mid }u-v\mathrm{\mid }$, so $G$ is a contraction with factor $q=1\mathrm{/}2$. Its fixed-point equation gives $x=1$, and [F3] gives convergence of the iterates from every $x_0$.

The recurrence $x_{k+1}=(x_k+1)\mathrm{/}2$ gives $x_k=1-2^{-k}(1-x_0)$ by induction. Hence $d(G(x_k),x_k)=2^{-(k+1)}\mathrm{\mid }1-x_0\mathrm{\mid }$, which tends to zero by [F5]; the finite-budget algorithm therefore meets any $\epsilon >0$ if allowed enough updates. For $\epsilon =0$ and $x_0\mathrm{\ne }1$, no finite iterate meets the test, so a finite budget returns iteration-budget-exhausted. Also [F4] gives $\mathrm{\mid }{x}_k-1\mathrm{\mid }\le 2^{-k}\mathrm{\mid }{x}_1-x_0\mathrm{\mid }\mathrm{/}(1-1\mathrm{/}2)=2^{-k}\mathrm{\mid }1-x_0\mathrm{\mid }$, agreeing with the exact formula.

For $x>0$, [F6] solves $2xs=-(x^2-2)$, so the exact Newton update in [F7] is $x_{+}=(x^2+2)\mathrm{/}(2x)$. Direct subtraction using [F10] gives $x_{+}-r=(x-r{)}^2\mathrm{/}(2x)$. If $\mathrm{\mid }x-r\mathrm{\mid }\le r\mathrm{/}2$, then $x\ge r\mathrm{/}2$ and $\mathrm{\mid }{x}_{+}-r\mathrm{\mid }\le \mathrm{\mid }x-r{\mathrm{\mid }}^2\mathrm{/}r\le \mathrm{\mid }x-r\mathrm{\mid }\mathrm{/}2$. Thus the ball of radius $r\mathrm{/}2$ is invariant and the error decreases at least linearly by a factor $1\mathrm{/}2$, with the sharper quadratic bound $\mathrm{\mid }{e}_{+}\mathrm{\mid }\le \mathrm{\mid }e{\mathrm{\mid }}^2\mathrm{/}r$.

At $a=1$, $F^{\mathrm{\prime }}(1)=2$ and the fixed-inverse map from [F9] with $y=0$ is $T_0(x)=x-\frac{1}{2}(x^2-2)$. Starting at $1$, it gives $T_0(1)=3\mathrm{/}2$ and $T_0(3\mathrm{/}2)=11\mathrm{/}8$. Updated-Jacobian Newton uses the [F6] correction at $x=3\mathrm{/}2$, where $F^{\mathrm{\prime }}(3\mathrm{/}2)=3$, and gives $x_2=17\mathrm{/}12$. Since $11\mathrm{/}8\mathrm{\ne }17\mathrm{/}12$, the fixed-inverse and updated-Jacobian maps differ; [F9] does not itself assert a Newton convergence theorem.

The start $x_0=3\mathrm{/}2$ lies in the radius-$r\mathrm{/}2$ ball of step 1.3 because $1<r<3$, which follows from $r^2=2$ and [F12]. Iteration gives $\mathrm{\mid }{x}_k-r\mathrm{\mid }\le 2^{-k}\mathrm{\mid }{x}_0-r\mathrm{\mid }\to 0$ by [F5]. Also $\mathrm{\mid }F(x_k)\mathrm{\mid }=\mathrm{\mid }{x}_k-r\mathrm{\mid }\mathrm{\mid }{x}_k+r\mathrm{\mid }$; since $\mathrm{\mid }{x}_k-r\mathrm{\mid }\le r\mathrm{/}2$, we have $0<x_k\le 3r\mathrm{/}2$ and hence $\mathrm{\mid }{x}_k+r\mathrm{\mid }\le 5r\mathrm{/}2$, so the residual tends to zero and any positive tolerance is eventually met if the update budget is large enough.

For the double-root residual $H(x)=(x-1{)}^2$ and any $x>1$, [F6] and [F7] give the Newton formula $x_{+}=x-(x-1{)}^2\mathrm{/}(2(x-1))=(x+1)\mathrm{/}2$, so $e_{+}:=x_{+}-1=e\mathrm{/}2$ for $e:=x-1>0$. Iterating gives $e_k=2^{-k}{e}_0\to 0$ by [F5]. Suppose a local quadratic bound held on some radius $\delta >0$, so $\mathrm{\mid }{e}_{+}\mathrm{\mid }\le C\mathrm{\mid }e{\mathrm{\mid }}^2$ for every $0<e<\delta$ and some finite $C\ge 0$. Since $e_{+}=e\mathrm{/}2$, it would require $1\mathrm{/}2\le Ce$ for every such $e$. If $C>0$, choose $0<e<\min \{\delta ,1\mathrm{/}(2C)\}$; if $C=0$, choose any $0<e<\delta$. Either choice contradicts the required inequality. Unlike the simple-root bound in step 1.3, $H^{\mathrm{\prime }}(1)=0$, so the simple-root hypothesis in [F8] fails.

For $F(x)=x^2-2$, the start $x_0=0$ lies outside the radius-$r\mathrm{/}2$ ball of step 1.3 because $r>0$. At $0$, $F(0)=-2$ and $F^{\mathrm{\prime }}(0)=0$, so [F6] returns the singular-jacobian status before any update, despite the two exact roots $\pm r$.