Codex @codex  0

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.

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 $f(x,y)=x^4-4xy+2y^2+4$, the Newton step equations imply $y_{n+1}=x_{n+1}$. Solving the remaining equation gives the displayed scalar recurrence, defined when $3x_n^2\ne 1$. Around $(1,1)$ its error factors exactly asThus any well-defined sequence converging to $(1,1)$ has quadratic convergence, or reaches that point exactly in finitely many steps. The scalar asymptotic error constant is $3/2$; the Euclidean norm error constant on the diagonal is $3/(2\sqrt{2})$. Around $(-1,-1)$, replacing $x$ by $-x$ gives the corresponding conclusion.

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)$.

An iteration of a map has linear convergence to its limit when its nonzero errors $e_k=x_k-\alpha$ satisfy $|e_{k+1}|/|e_k|\to \rho$ for some $0<\rho <1$. The error eventually shrinks by approximately the same factor at each step. This is exact order of convergence one, in contrast to quadratic convergence.

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.

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.

For $c>0$ and $a_0>0$, the displayed recurrence relation stays positive and satisfiesAfter the first step, $a_n^2\ge c$, so $a_{n+1}-a_n=(c-a_n^2)/(2a_n)\le 0$. The bounded monotone sequence theorem gives a limit of a sequence $L\ge 0$; the inequality $L^2\ge c>0$ makes $L$ positive, and passage to the limit of a sequence in the recurrence relation gives $L^2=c$. This proves existence of the positive square root without assuming it in the construction. Once $s=\sqrt{c}$ is known, the exact error identity $a_{n+1}-s=(a_n-s{)}^2/(2a_n)$ explains the eventual quadratic convergence.

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.

At a current approximation $p$, Taylor's theorem replaces $\Phi (p+h)=0$ by the affine equation $\Phi (p)+D\Phi (p)h=0$. Solving this equation gives the Newton iteration in a Banach spaceThe inverse is a bounded linear inverse by the bounded inverse theorem. The displayed operator is defined where the derivative is invertible, in particular on the specified open domain; the hypotheses do not supply a globally defined Newton operator on all of $\mathcal{X}$. If $\Phi (\bar{p})=0$ with $\bar{p}$ in that domain, then $N(\bar{p})=\bar{p}$.

For quadratic convergence, choose a sufficiently small neighbourhood of $\bar{p}$. Continuity of the inverse derivative and of $D^2\Phi$ gives constants $M,L$ there such thatPut $e=p-\bar{p}$ and $B(p)=[D\Phi (p){]}^{-1}$. The quadratic Newton error bound in a Banach space follows from the integral remainder:soTake a closed radius-$r$ ball lying in the neighbourhood with $Cr<1$. This inequality maps the ball into itself and makes errors tend to zero. More explicitly, for $e_n=\Vert p_n-\bar{p}\Vert$, induction gives $C{e}_{n+j}\le (C{e}_n{)}^{2^j}$. Hence every sufficiently close initial point converges to $\bar{p}$ at least quadratically; special maps can converge still faster.

For a fixed-point equation, apply the same method to $F(p)=\Phi (p)-p$. Wherever $D\Phi (p)-I$ is invertible, the exact adapted map isEvery fixed point of $\Phi$ is fixed by $A$, and conversely on this domain. This additional invertibility condition is distinct from invertibility of $D\Phi$; for example, $D\Phi =I$ is invertible but $D\Phi -I=0$ is not.

For certification, a frozen Newton correction for a fixed-point equation is often more useful. Choose a bounded, injective approximate inverse $J$ of $D\Phi (p_0)-I$ and setAgain $A_J(p)=p$ if and only if $\Phi (p)=p$. A well-chosen $J$ makes the corrected operator contract even if the original operator has an expanding direction. The subsequent contraction mapping argument requires the stated derivative and residual bounds; it does not assume that arbitrary inverse approximations provide them.

Write $r=\sqrt{a}>0$ and subtract it from the iteration:This is an Exact Newton error identity for a quadratic. If $x_n>r$, then $x_n>0$ and $e_n>0$, so $e_{n+1}>0$. Induction from $x_0>r$ proves $x_n>r$ for every $n$. Also $x_{n+1}-x_n=(a-x_n^2)/(2x_n)<0$, so the iterates decrease while remaining above the root. Their limit must satisfy $L=(L+a/L)/2$, hence $L=r$. The squared error numerator explains the ensuing quadratic convergence.

Use the Exact Newton error identity for a quadratic to expose the cancellation without a long quotient expansion. Put $e_k=x_k-x_{\ast }$. Since $f(x_{\ast })=0$, direct expansion givesFrom part (ii), $e_1=\frac{1}{2}{\epsilon }^2+O({\epsilon }^3)$ and $x_1-\epsilon \to 1$. It follows thatThus the stronger result isThe vanishing lower-order terms are a concrete instance of quadratic convergence: to leading order, this step squares the previous error.

A local minimizer of a differentiable function on ${\mathbb{R}}^N$ necessarily satisfies $\boxed{\nabla f(x_{\ast })=0}$. A sufficient condition for a strict local minimum is $\boxed{\nabla f(x_{\ast })=0,{\nabla }^{2}f(x_{\ast })\text{ positive definite}}$. Indeed, the second-order Taylor expansion has a strictly positive quadratic term that dominates its $o(\Vert x-x_{\ast }{\Vert }^2)$ remainder near $x_{\ast }$.

For Newton's method, solve $H_n{s}_n=-g_n$ with $H_n={\nabla }^{2}f(x_n)$, $g_n=\nabla f(x_n)$, and set $x_{n+1}=x_n+s_n$. A positive-definite Hessian makes this a descent direction; general Hessians may need modification or a separate line search for a globally useful method.

The sequence is q-quadratically convergent if there is $C<\infty$ such that $\Vert x_{n+1}-x_{\ast }\Vert \le C\Vert x_n-x_{\ast }{\Vert }^2$ eventually. Sufficient local hypotheses are $\nabla f(x_{\ast })=0$, a nonsingular $H_{\ast }={\nabla }^{2}f(x_{\ast })$, a Lipschitz continuous Hessian near $x_{\ast }$, and $x_0$ sufficiently close. For convergence to a local minimum take $H_{\ast }$ positive definite. Near $x_{\ast }$, inverse Hessians are uniformly bounded, and integration along the error segment givesA Hessian Lipschitz constant $L_H$ yields $\Vert x_{n+1}-x_{\ast }\Vert \le \frac{1}{2}{L}_H\Vert H_n^{-1}\Vert \Vert x_n-x_{\ast }{\Vert }^2$. Choosing a sufficiently small invariant neighborhood proves quadratic convergence. Continuous second derivatives alone do not guarantee this quadratic rate; the Lipschitz hypothesis supplies the needed remainder bound.

Let $e_k=x_k-x_{\ast }$, with $f^{\prime }(x_{\ast })=0$, $f^{\prime \prime }(x_{\ast })\ne 0$. Taylor expansion givesDivision in the Newton update yieldsThus convergence is generically quadratic when that coefficient is nonzero. With a locally Lipschitz second derivative and nonzero $f^{\prime \prime }(x_{\ast })$, the weaker estimate $|e_{k+1}|\le C|e_k{|}^2$ also proves local quadratic convergence.

“Quadratic at best” is false as a universal upper bound. If the displayed coefficient vanishes, the order can be higher. For example $f(x)=x^2/2+x^4/4$ has a minimum at zero, and its Newton optimization update is $x_{k+1}=2x_k^3/(1+3x_k^2)$, which has cubic convergence. For a nondegenerate quadratic objective the method reaches the stationary point in one step. The expansion proves the standard generic quadratic statement while retaining and correcting the source's stronger wording explicitly.

After the first update, the sequence lies in $[\sqrt{a},x_1]$ and is nonincreasing. The monotone convergence theorem for sequences gives a limit $L\ge \sqrt{a}$. The update is continuous on this interval, so passing to the limit givesPositivity forces $\boxed{x_n\to \sqrt{a}\text{ for every }{x}_0>0}$. If an iterate reaches the root exactly, the constant tail gives the same conclusion. The Exact Newton error identity for a quadratic here is $x_n-\sqrt{a}=(x_{n-1}-\sqrt{a}{)}^2/(2x_{n-1})$, also showing quadratic convergence once the error is small.

Since $f^{\prime }(x)=2x-2$, Newton's method becomesFor $x_n>2$, subtraction from $2$ givesAlso $x_n-x_{n+1}=x_n(x_n-2)/(2(x_n-1))>0$. Hence $2<x_{n+1}<x_n$. Equivalently, the positive excess above $2$ is multiplied by the function from part (c): $x_{n+1}-2=g(x_n)(x_n-2)$, with $0<g(x_n)<1/2$.

Thus the iterates form a decreasing sequence bounded below by $2$. By the monotone convergence theorem for sequences they have a limit $\ell \ge 2$. Passing to the limit in the continuous update gives $2\ell (\ell -1)={\ell }^2$, or $\ell (\ell -2)=0$. Therefore $x_n\to 2$. The exact error formula also shows quadratic convergence near this root.

On $I=[1,7/5]$, $f^{\prime }<0$ and $f^{\prime \prime }<0$, since $x^2<2$. Hence $|f^{\prime }|$ increases and has minimum $|f^{\prime }(1)|=14$. Alsowith equality at $x=1$. Therefore

There is a unique root $r$ in $I$: $f(1)=2>0$, $f(7/5)=-5.678464<0$, and the function is strictly decreasing. Moreover $f(6/5)=-1.382016<0$, so $r<6/5=x_0$.

It remains to justify that the iteration stays where the error estimate applies. Because $f$ is a concave function, its graph lies below each tangent line. At any $x\in [r,6/5]$, the tangent has nonpositive value $f(x)$ at $x$, negative slope, and nonnegative value at $r$. Its zero $N(x)=x-f(x)/f^{\prime }(x)$ therefore satisfiesBy mathematical induction, the Newton root-finding iteration stays in $[r,6/5]$ and decreases to some limit $L\ge r$. Continuity in $x_{k+1}-x_k=-f(x_k)/f^{\prime }(x_k)$ implies $f(L)=0$, so uniqueness gives $L=r$.

Now the supplied error bound applies at every step:This proves at least quadratic convergence, with an invariant interval and a nonvanishing derivative explicitly established.

For iterates approaching ${\mathbf{x}}_{\ast }$, write $e_k=\Vert {\mathbf{x}}_k-{\mathbf{x}}_{\ast }\Vert$. Exact order of convergence $p$ means $e_{k+1}/e_k^p\to C$ for a finite constant $C>0$, with nonzero errors. Thus quadratic convergence has $p=2$, and cubic convergence has $p=3$. The weaker eventual bound $e_{k+1}\le C{e}_k^p$ means at least order $p$. Finite termination is a separate case.^[ref]

The assertion about being always faster is false. For example, the fixed-point iterations with errors $e_{k+1}=e_k^2$ and $d_{k+1}=50d_k^3$ have exact quadratic convergence and cubic convergence, respectively. Starting both at $0.1$, their next errors are $0.01$ and $0.05$: the cubic convergence method is worse on that step, although both converge. Error constants, starting points, and work per step all matter. The higher order of convergence describes asymptotic behavior within a convergence region, not a uniform comparison of all computations.

Apply the mean value theorem, the first-order case of Taylor's theorem, to $f^{\prime }$ between $0$ and $x>1$. It yieldsAlso $f(3/2)\ge -5+9/2+9/4=7/4>0$, so the initial point is to the right of the root $x^{\ast }$. For an increasing strictly convex function, its tangent at a point to the right of a root meets the axis between that root and the point. Hence the exact Newton root-finding iteration remains in $[x^{\ast },3/2]$ and decreases towards $x^{\ast }$.

On every relevant interval, $|f^{\prime \prime }|<3$ and $f^{\prime }>5$, so the stated quadratic convergence bound gives, with $e_n=|x_n-x^{\ast }|$,Iterating the bound givesThus four Newton corrections suffice to reduce the exact-iteration error bound below the floating-point spacing scale. The quadratic convergence doubles the approximate number of correct digits at each late step. Beyond this point further corrections cannot reliably improve a generic floating-point answer. This is a bound on useful accuracy under the usual stable-evaluation model, not a claim that the data specify the exact iteration at which every implementation must stagnate.

Let $T(x)$ be the weighted average on the right, and define $F$ and $\Phi =\log F$ as in part (i). Their explicit gradient identity isTherefore the displayed equation is exactly the stationary point equation for the strongly convex $\Phi$. It has one solution, which is the unique minimizer from part (i). Reuse the BFGS iteration, withThe gradient is explicit, the weights can again be scaled by their largest exponent, and the usual full-memory BFGS assumptions give local superlinear convergence.

Simply setting $x_{n+1}=T(x_n)$ is not automatically a convergent fixed-point iteration. Differentiating the normalized weights giveswhose operator norm need not be below $1$. For example, in one dimension with centres $-1,1$, $T(x)=-\tanh (2x)$ and $T^{\prime }(0)=-2$: the desired fixed point is locally repelling for that naive iteration. If exact second derivatives are affordable, multivariable Newton iteration on $x-T(x)=0$ is another valid choice, with Jacobian matrix $I-J_T$ as given above and local quadratic convergence.