Nonlinear equation solving begins with two basic paradigms: topological bracketing and contraction-based iteration.
Root-finding problem
Definition. Given \(F:X\to Y\), the nonlinear equation problem is to find \(x\) such that \(F(x)=0\). In one dimension this can sometimes be solved by bracketing; in higher dimensions one usually needs local linearization or fixed-point structure.
Bisection theorem
Theorem. If \(f\) is continuous on \([a,b]\) and \(f(a)f(b)\le0\), bisection produces intervals of length \((b-a)2^{-k}\) containing a root. It is slow but globally reliable under only continuity and a sign change.
Fixed-point iteration
Definition. A fixed-point method rewrites \(F(x)=0\) as \(x=G(x)\) and iterates \(x_{k+1}=G(x_k)\). The same equation can lead to stable or unstable iterations depending on the chosen \(G\).
Contraction mapping theorem
Theorem. If \(G\) maps a complete metric space into itself and \(d(Gx,Gy)\le qd(x,y)\) with \(q\lt1\), then \(G\) has a unique fixed point and the iteration converges linearly to it.
Aitken acceleration
Remark. When a scalar fixed-point iteration converges linearly, sequence acceleration can estimate and remove the leading geometric error. Acceleration is useful only when the underlying iteration is already in its asymptotic regime.
Bisection as a certified method
Theorem. If \(f\) is continuous on \([a_0,b_0]\) and \(f(a_0)f(b_0)\le0\), bisection produces nested intervals containing a root with \[ b_k-a_k=2^{-k}(b_0-a_0). \] The midpoint error is at most \[ |x_k-x^*|\le2^{-k-1}(b_0-a_0). \]
Proof. The intermediate value theorem puts a root in the initial bracket. At each step, one half retains a sign change, so induction preserves a root and halves length. Any point in the interval is within its length of the midpoint; the sharper half-length bound follows.
Bisection is linearly convergent but globally reliable. It handles nondifferentiability and multiple roots as long as a sign change exists; an even-multiplicity root may not bracket.
Contraction iteration
Theorem. If \(g:[a,b]\to[a,b]\) and \[ |g(x)-g(y)|\le q|x-y|, \qquad q<1, \] then \(x_{k+1}=g(x_k)\) converges to the unique fixed point, with \[ |x_k-x^*|\le q^k|x_0-x^*| \le\frac{q^k}{1-q}|x_1-x_0|. \]
Local differentiability with \(|g'(x^*)|<1\) gives local linear convergence. If \(g'(x^*)=0\) and the first nonzero derivative is order \(p\), convergence can be order \(p\). Algebraically equivalent rearrangements \(f(x)=0\iff x=g(x)\) can have entirely different fixed-point behavior.
A posteriori stopping
For a contraction, \[ |x_k-x^*| \le\frac{q}{1-q}|x_k-x_{k-1}|. \] This is a certified a posteriori bound when \(q\) is known. Stopping only when \(|f(x_k)|\) is small requires a lower bound on \(|f'|\) or inverse conditioning: \[ |x_k-x^*|\le\frac{|f(x_k)|}{m} \quad\text{if }|f'|\ge m>0 \] between \(x_k\) and the root.
Safeguarded hybrids
Brent-type methods maintain a bracket while attempting secant or inverse- quadratic steps. A proposed fast step is accepted only when it stays safely inside the bracket and gives sufficient progress; otherwise bisection is used. This combines global certification with superlinear local speed.