§3.8 Nonlinear Equations

The equation to be solved is

where $z$ is a real or complex variable and the function $f$ is nonlinear. Solutions are called roots of the equation, or zeros of $f$. If $f(z_0)=0$ and $f^{\prime }(z_0)\ne 0$, then $z_0$ is a simple zero of $f$. If $f(z_0)=f^{\prime }(z_0)=\mathrm{\cdots }=f^{(m-1)}(z_0)=0$ and $f^{(m)}(z_0)\ne 0$, then $z_0$ is a zero of $f$ of multiplicity $m$; compare §1.10(i).

Sometimes the equation takes the form

and the solutions are called fixed points of $\varphi$.

Equations (3.8.1) and (3.8.2) are usually solved by iterative methods. Let $z_1,z_2,\mathrm{\dots }$ be a sequence of approximations to a root, or fixed point, $\zeta$. If

for all $n$ sufficiently large, where $A$ and $p$ are independent of $n$, then the sequence is said to have convergence of the $p$th order. (More precisely, $p$ is the largest of the possible set of indices for (3.8.3).) If $p=1$ and , then the convergence is said to be linear or geometric. If $p=2$, then the convergence is quadratic; if $p=3$, then the convergence is cubic, and so on.

An iterative method converges locally to a solution $\zeta$ if there exists a neighborhood $N$ of $\zeta$ such that $z_n\to \zeta$ whenever the initial approximation $z_0$ lies within $N$.

This is an iterative method for real twice-continuously differentiable, or complex analytic, functions:

If $\zeta$ is a simple zero, then the iteration converges locally and quadratically. For multiple zeros the convergence is linear, but if the multiplicity $m$ is known then quadratic convergence can be restored by multiplying the ratio $f(z_n)/f^{\prime }(z_n)$ in (3.8.4) by $m$.

For real functions $f(x)$ the sequence of approximations to a real zero $\xi$ will always converge (and converge quadratically) if either:

• (a)

  $f(x_0)f^{\prime \prime }(x_0)>0$ and $f^{\prime }(x)$, $f^{\prime \prime }(x)$ do not change sign between $x_0$ and $\xi$ (monotonic convergence).

• (b)

  , $f^{\prime }(x)$, $f^{\prime \prime }(x)$ do not change sign in the interval $(x_0,x_1)$, and $\xi \in [x_0,x_1]$ (monotonic convergence after the first iteration).

The polynomial

has $n$ zeros in $ℂ$, counting each zero according to its multiplicity. Explicit formulas for the zeros are available if $n\le 4$; see §§1.11(iii) and 4.43. No explicit general formulas exist when $n\ge 5$.

After a zero $\zeta$ has been computed, the factor $z-\zeta$ is factored out of $p(z)$ as a by-product of Horner’s scheme (§1.11(i)) for the computation of $p(\zeta )$. In this way polynomials of successively lower degree can be used to find the remaining zeros. (This process is called deflation.) However, to guard against the accumulation of rounding errors, a final iteration for each zero should also be performed on the original polynomial $p(z)$.

Newton’s rule is the most frequently used iterative process for accurate computation of real or complex zeros of analytic functions $f(z)$. Another iterative method is Halley’s rule:

This is useful when $f(z)$ satisfies a second-order linear differential equation because of the ease of computing $f^{\prime \prime }(z_n)$. The rule converges locally and is cubically convergent.

Initial approximations to the zeros can often be found from asymptotic or other approximations to $f(z)$, or by application of the phase principle or Rouché’s theorem; see §1.10(iv). These results are also useful in ensuring that no zeros are overlooked when the complex plane is being searched.

For an example involving the Airy functions, see Fabijonas and Olver (1999).

For fixed-point methods for computing zeros of special functions, see Segura (2002), Gil and Segura (2003), and Gil et al. (2007a, Chapter 7). For describing the distribution of complex zeros of solutions of linear homogeneous second-order differential equations by methods based on the Liouville–Green (WKB) approximation, see Segura (2013).

Suppose $f(z)$ also depends on a parameter $\alpha$, denoted by $f(z,\alpha )$. Then the sensitivity of a simple zero $z$ to changes in $\alpha$ is given by

Thus if $f$ is the polynomial (3.8.8) and $\alpha$ is the coefficient $a_j$, say, then

For moderate or large values of $n$ it is not uncommon for the magnitude of the right-hand side of (3.8.14) to be very large compared with unity, signifying that the computation of zeros of polynomials is often an ill-posed problem.

For fixed-point iterations and Newton’s method for solving systems of nonlinear equations, see Gautschi (1997a, Chapter 4, §9) and Ortega and Rheinboldt (1970).

The convergence of iterative methods

for solving fixed-point problems (3.8.2) cannot always be predicted, especially in the complex plane.

Consider, for example, (3.8.9). Starting this iteration in the neighborhood of one of the four zeros $\pm 1,\pm \mathrm{i}$, sequences $\{z_n\}$ are generated that converge to these zeros. For an arbitrary starting point $z_0\in ℂ$, convergence cannot be predicted, and the boundary of the set of points $z_0$ that generate a sequence converging to a particular zero has a very complicated structure. It is called a Julia set. In general the Julia set of an analytic function $f(z)$ is a fractal, that is, a set that is self-similar. See Julia (1918) and Devaney (1986).