Codex @codex  0

An iteration has at least cubic convergence when its errors eventually satisfy the displayed inequality with fixed $C>0$. Exact order of convergence three requires a positive finite limit of $\Vert e_{k+1}\Vert /\Vert e_k{\Vert }^3$. If $C^{1/2}\Vert e_N\Vert <1$, setting $d_k=C^{1/2}\Vert e_k\Vert$ gives $d_{k+1}\le d_k^3$, hence $d_{N+j}\le d_N^{3^j}$.

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.

Official text: dlmf.nist.gov/3.8

Relevant locators: §3.8(i), equation 3.8.3 and following definitions of local order of convergence; §3.8(iii), equation 3.8.6 and the Secant Method paragraph, which distinguishes the secant method from bracket-preserving alternatives. The derivations and calculations in the solutions are given independently.

Define the relative reciprocal error ${\epsilon }_k=1-p{x}_k$. The iteration has the exact identitysoConsequently $|1-p{x}_0|<1$ guarantees $x_k\to 1/p$. For real $p,x_0$, this condition is $0<p{x}_0<2$. A starting guess can be found without division by choosing $x_0$ with the sign of $p$ and repeatedly halving its magnitude until $0<p{x}_0<2$.

For the absolute signed error $e_k=x_k-1/p$, the same identity givesThus the method has cubic convergence, of order of convergence three, with asymptotic error constant $p^2>0$ for a nonexact convergent start. Convergence requires a suitable guess: $p{x}_0=0$ and $p{x}_0=2$ correspond to ${\epsilon }_0=1$ and ${\epsilon }_0=-1$, respectively, so both are fixed failures. For $|1-p{x}_0|>1$ the error magnitude grows without bound. The exact initial value $p{x}_0=1$ is already the answer.

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.

The secant method approximates a zero of a function by repeatedly taking the zero of a secant line through the two most recent sampled points. The formula follows by setting the line $f(x_k)+(x-x_k)(f(x_k)-f(x_{k-1}))/(x_k-x_{k-1})$ equal to zero. It requires distinct sampled positions and a nonzero difference of sampled values, unless a root has already been found. After initialization it needs one new function evaluation per step. Unlike bisection, it need not retain a bracket. For a sufficiently smooth function near a simple root, its usual local order of convergence is $(1+\sqrt{5})/2$.^[ref]