Numerical conditioning and root finding

Definition Let $f$ be continuously differentiable on an open interval containing a root $x_*$ of the equation $f(x) = b$, and suppose $f'(x_*) \ne 0$. By the inverse function theorem, for data $\tilde b$ near $b$ the equation $f(x) = \tilde b$ has a unique solution $x(\tilde b)$ near $x_*$, and

The absolute condition number of the root is $\kappa_{\text{abs}} = 1/\lvert f'(x_*) \rvert$. When $b \ne 0$ and $x_* \ne 0$, the relative condition number is

To first order a change $\Delta b$ in the data moves the root by $\Delta x \approx \Delta b / f'(x_*)$, so $\lvert \Delta x \rvert \approx \kappa_{\text{abs}} \lvert \Delta b \rvert$ and $\lvert \Delta x / x_* \rvert \approx \kappa_{\text{rel}} \lvert \Delta b / b \rvert$. Conditioning is a property of the problem, the map from data to solution, and it is defined in exact arithmetic before any algorithm is chosen. Which of the two numbers is informative depends on how the uncertainty in the data is measured.

Definition An algorithm returns a computed value $\hat x$ for the data $b$. Its forward error is $\lvert \hat x - x_* \rvert$, and its residual is $f(\hat x) - b$, the mismatch in the equation. Since $\hat x$ solves $f(x) = b + \bigl(f(\hat x) - b\bigr)$ exactly, the size of the residual is the absolute backward error of $\hat x$, the change in the data for which $\hat x$ is an exact root. An algorithm is backward stable when every answer it computes is the exact answer for data that differ from the given data by a relative amount of the order of the unit roundoff, the largest relative rounding error of the arithmetic. Stability is a property of the algorithm. To first order, a backward-stable algorithm applied to a problem with relative condition number $\kappa_{\text{rel}}$ has a relative forward error of at most about $\kappa_{\text{rel}}$ times its relative backward error. A rigorous link between residual and forward error comes from the mean value theorem. If $f$ is differentiable on an interval $I$ that contains $\hat x$ and $x_*$, and $\lvert f'(x) \rvert \ge m > 0$ for every $x$ in $I$, then

because $f(\hat x) - b = f(\hat x) - f(x_*) = f'(\xi)(\hat x - x_*)$ for some $\xi$ between them. Without a lower bound on the derivative, a small residual says nothing about the forward error.

Definition In IEEE double precision with rounding to nearest, a real number $a$ in the normal range is stored as $\hat a = a(1 + \delta_a)$ with $\lvert \delta_a \rvert \le u = 2^{-53} \approx 1.11 \times 10^{-16}$, and each basic operation returns its exact result rounded in the same way. If $a$ and $c$ are stored with such relative errors, then

so the relative error of the difference can be as large as $u(\lvert a \rvert + \lvert c \rvert)/\lvert a - c \rvert$. This loss of relative accuracy when nearly equal rounded numbers are subtracted is called cancellation. The subtraction adds at most one rounding of its own. The damage comes from the errors already present in its inputs, which the subtraction exposes. The cure is to rewrite the formula so that the small quantity is computed without the subtraction. Multiplying by the conjugate gives the identity

valid for every real $x$, whose right side involves no cancellation when $x \ge 0$.

Definition Let $f$ be continuous on $[a_0, b_0]$ with $f(a_0)\, f(b_0) < 0$. For $n = 0, 1, 2, \dots$ compute the midpoint $c_n = (a_n + b_n)/2$. If $f(c_n) = 0$, stop. Otherwise keep the half on which the sign changes, setting $[a_{n+1}, b_{n+1}] = [a_n, c_n]$ when $f(a_n)\, f(c_n) < 0$ and $[a_{n+1}, b_{n+1}] = [c_n, b_n]$ otherwise. By the intermediate value theorem every bracket contains a root. The brackets are nested with widths $(b_0 - a_0)/2^n$, so they shrink to a single point $x_*$, which is a root by continuity, and in exact arithmetic

Hence $n \ge \log_2\bigl((b_0 - a_0)/\varepsilon\bigr) - 1$ halvings guarantee an error of at most $\varepsilon$, one binary digit per step. The method needs no derivative. A sign change proves that a root exists, not that it is unique, and uniqueness needs another argument such as strict monotonicity. In floating point the bracket stops shrinking once its endpoints are neighboring doubles, because their midpoint then rounds to one of them.

Definition For a differentiable $f$ and an iterate with $f'(x_n) \ne 0$, Newton’s method sets the tangent line $f(x_n) + f'(x_n)(x - x_n)$ equal to zero, which gives

A sequence converges to $x_*$ quadratically when its errors $e_n = x_n - x_*$ satisfy $\lvert e_{n+1} \rvert \le M e_n^2$ for some constant $M$ and all large $n$, so that once $M \lvert e_n \rvert$ is small the number of correct digits roughly doubles at each step. The basic local result follows from Taylor’s theorem. Let $f$ be twice continuously differentiable on an open interval containing a simple root $x_*$, meaning $f(x_*) = 0$ and $f'(x_*) \ne 0$. Expanding $f$ about $x_n$ with the Lagrange remainder and evaluating at $x_*$, where $f(x_*) = 0$, gives

for some $\xi_n$ between $x_n$ and $x_*$, and dividing by $f'(x_n)$ gives

Choose $\delta > 0$ so that $f' \ne 0$ on $I = [x_* - \delta, x_* + \delta]$ and $M\delta < 1$, where $M$ is the maximum of $\lvert f'' \rvert$ on $I$ divided by twice the minimum of $\lvert f' \rvert$ on $I$. Then every start in $I$ gives $\lvert e_{n+1} \rvert \le M e_n^2 \le M\delta \lvert e_n \rvert$, so the iterates stay in $I$ and converge to $x_*$ quadratically, with $e_{n+1}/e_n^2 \to f''(x_*)/\bigl(2 f'(x_*)\bigr)$ as long as no iterate lands exactly on the root. The theorem is local. It says nothing about a distant start, and its hypothesis $f'(x_*) \ne 0$ excludes repeated roots.

Definition Write $N(x) = x - f(x)/f'(x)$ for the Newton map. A Newton cycle of period $p \ge 2$ is a set of distinct points $z_0, \dots, z_{p-1}$, none of them a root and each with $f'(z_k) \ne 0$, such that $N(z_k) = z_{k+1}$ for $k < p - 1$ and $N(z_{p-1}) = z_0$. An iteration started on a cycle never converges. For twice continuously differentiable $f$,

and a cycle is attracting when the product of the values $\lvert N'(z_k) \rvert$ over the cycle is less than $1$. Starts near an attracting cycle are drawn into it rather than to a root. A safeguarded method keeps a sign-change bracket, accepts a Newton step only when it lands inside the current bracket, and bisects otherwise. It keeps the containment of bisection, and near a simple root it typically regains the speed of Newton’s method.