Calculus · Applications of derivatives
There is no formula for the root of \(x^3 + x - 1 = 0\) that a student would want to use, and none at all for \(x = \cos x\). Yet a calculator finds both in a fraction of a second. How? By starting from a rough guess and improving it step by step. This post presents the classical methods for that (chords, tangents, iteration, plus the graphical method and bisection), explains why they work, and shows how fast each one converges.
Every method below starts from an interval \([a, b]\) that contains exactly one root of
\[ f(x) = 0. \tag{1} \]Why: \( f(a)f(b) < 0 \) means \(f\) changes sign, so by continuity it crosses zero at least once (the intermediate value theorem). And \(f' \ne 0\) means \(f\) is strictly monotone (post on extrema), so it can cross zero at most once.
Throughout the post we use one running example, from the post on mean value theorems:
Before the classical methods, the simplest one of all: halve the interval, keep the half where \(f\) changes sign, repeat. After \(n\) steps the root is trapped in an interval of length \( \frac{b - a}{2^n} \).
| Step | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Interval | [0.5, 1] | [0.5, 0.75] | [0.625, 0.75] | [0.625, 0.6875] | [0.65625, 0.6875] | [0.671875, 0.6875] |
Bisection always works (it needs only continuity and a sign change) but is slow: each step gains one binary digit, so about 3.3 steps per decimal digit. The methods that use the derivative are much faster.
Idea: replace the curve on \([a, b]\) by the straight line (chord) through \( A(a, f(a)) \) and \( B(b, f(b)) \), and take the point where the chord crosses the \(x\)-axis as the new approximation.
Where the formula comes from: the chord has slope \( \frac{f(b) - f(a)}{b - a} \). Starting at height \(f(a)\) and moving \(\varepsilon_1\) to the right, it reaches zero when \( f(a) + \frac{f(b) - f(a)}{b - a}\varepsilon_1 = 0 \). Solving for \(\varepsilon_1\) gives the formula. The method is also known as regula falsi ("rule of false position"): it pretends, falsely, that the function is linear between the two points.
| \(n\) | \(\alpha_n\) | \(f(\alpha_n)\) | actual error |
|---|---|---|---|
| 1 | 0.5 | −0.375 | 0.18 |
| 2 | 0.6363636 | −0.1059354 | 0.046 |
| 3 | 0.6711957 | −0.0264283 | 0.011 |
| 4 | 0.6796616 | −0.0063755 | 0.0027 |
| 5 | 0.6816910 | −0.0015254 | 0.00064 |
| 6 | 0.6821758 | −0.0003642 | 0.00015 |
How do we know the error without knowing \(\xi\)? By Lagrange's theorem, \( f(\alpha_n) = f(\alpha_n) - f(\xi) = f'(c)(\alpha_n - \xi) \), so
\[ |\alpha_n - \xi| \le \frac{|f(\alpha_n)|}{m}, \qquad m = \min_{[a, b]}|f'(x)|. \]In the example \( f'(x) = 3x^2 + 1 \ge 1 \), so \( m = 1 \): after step 6 the error is at most \( 0.00036 \). (Actually it is \(0.00015\); the estimate is honest but cautious.)
Idea: instead of the chord, follow the tangent at one end point down to the \(x\)-axis. Near the root the tangent is an excellent approximation of the curve (post on the differential), so this should be much more accurate.
Where the formula comes from: the tangent at \( (a, f(a)) \) is \( Y - f(a) = f'(a)(X - a) \) (post on tangents). Setting \(Y = 0\) gives exactly \( X = a - \frac{f(a)}{f'(a)} \). In the post on tangents this was the subtangent: Newton's step moves exactly one subtangent towards the root.
Which end to start from? Here \(a\) stands for whichever endpoint satisfies \( f(a)f''(a) > 0 \) (Fourier's condition): the end where the curve bends towards the axis. From that end the tangent always meets the axis between the root and the starting point, so all the approximations stay inside the interval and approach the root monotonically. From the other end the first tangent may overshoot far outside the interval.
| \(n\) | \(\beta_n\) | actual error |
|---|---|---|
| 1 | 0.75 | 6.8 · 10⁻² |
| 2 | 0.6860465 | 3.7 · 10⁻³ |
| 3 | 0.6823396 | 1.2 · 10⁻⁵ |
| 4 | 0.6823278039 | 1.2 · 10⁻¹⁰ |
By Taylor's formula (previous post), expanding \(f\) around \(\beta_n\) at the root:
\[ 0 = f(\xi) = f(\beta_n) + f'(\beta_n)(\xi - \beta_n) + \frac{f''(c)}{2}(\xi - \beta_n)^2. \]Dividing by \(f'(\beta_n)\) and using the definition of \(\beta_{n+1}\):
\[ \xi - \beta_{n+1} = -\frac{f''(c)}{2f'(\beta_n)}(\xi - \beta_n)^2, \qquad\text{so}\qquad |\xi - \beta_{n+1}| \le \frac{M}{2m}|\xi - \beta_n|^2, \]with \( M = \max|f''| \), \( m = \min|f'| \). The new error is proportional to the square of the old one: quadratic convergence. Once the error is small, the number of correct digits roughly doubles at every step, exactly as in the table (\(10^{-2} \to 10^{-3} \to 10^{-5} \to 10^{-10}\)).
Besides these two procedures, the method of iteration is often used, after bringing equation (1) to the form
\[ x = \varphi(x). \]Pick a starting value \(x_0\) and compute
\[ x_1 = \varphi(x_0), \quad x_2 = \varphi(x_1), \quad \dots, \quad x_{n+1} = \varphi(x_n). \]If the sequence converges to some \(\xi\) (and \(\varphi\) is continuous), then \( \xi = \varphi(\xi) \): the limit is a root. Such a \(\xi\) is called a fixed point of \(\varphi\).
Why: by Lagrange's theorem, \( x_{n+1} - \xi = \varphi(x_n) - \varphi(\xi) = \varphi'(c)(x_n - \xi) \), so each step multiplies the error by at most \(q\). If \( |\varphi'| > 1 \) near the root, the error grows instead, and the iteration runs away.
For orientation, a graphical procedure is often used first: it shows how many roots there are and roughly where. The trick is to rewrite \(f(x) = 0\) as \( g(x) = h(x) \), with two functions whose graphs are easy to draw, and look for the intersections.
| Method | Needs | Speed | Reliability |
|---|---|---|---|
| Bisection | continuity, sign change | slow: error halves each step | always converges |
| Chords (regula falsi) | sign change, \(f' \ne 0\) | linear: error shrinks by a constant factor | always converges (root stays bracketed) |
| Newton (tangents) | \(f'\), good start (\(f f'' > 0\)) | quadratic: digits double each step | can diverge from a bad start |
| Iteration \(x = \varphi(x)\) | \( |\varphi'| < 1 \) near the root | linear, factor \(\approx |\varphi'(\xi)|\) | depends on the choice of \(\varphi\) |
In practice the methods are combined: a graph or bisection to isolate the root and get a safe starting point, then Newton to polish it to full precision in a few steps. Another classical combination uses chords and tangents together: since they approach the root from opposite sides (Figure 1), the root is always trapped between \(\alpha_n\) and \(\beta_n\), which gives a free error bound.
| Method | Formula |
|---|---|
| Isolation | \( f(a)f(b) < 0 \), \( f' \ne 0 \) on \((a, b)\) \(\Rightarrow\) exactly one root |
| Chords | \( \alpha_1 = a - \frac{f(a)}{f(b) - f(a)}(b - a) \), then repeat on the subinterval with a sign change |
| Newton | \( \beta_{n+1} = \beta_n - \frac{f(\beta_n)}{f'(\beta_n)} \), start where \( f f'' > 0 \) |
| Iteration | \( x_{n+1} = \varphi(x_n) \), converges if \( |\varphi'| \le q < 1 \) |
| Error bound (any method) | \( |x_n - \xi| \le \frac{|f(x_n)|}{m} \), \( m = \min|f'| \) |
| Newton's error | \( |\xi - \beta_{n+1}| \le \frac{M}{2m}|\xi - \beta_n|^2 \) |
Try each one before opening the solution. More solved problems from this topic are in Differential Calculus.
\( f(2) = -1 < 0 \), \( f(3) = 16 > 0 \), and \( f'(x) = 3x^2 - 2 > 0 \) on \([2, 3]\). (This is the equation Newton himself used to demonstrate his method.)
\( \alpha_1 = 2 - \frac{-1}{16 - (-1)}\cdot 1 = 2 + \frac{1}{17} \approx 2.0588 \).
\( f''(x) = 6x > 0 \); \( f(3) > 0 \), so start at \(3\): \( \beta_1 = 3 - \frac{16}{25} = 2.36 \), \( \beta_2 = 2.36 - \frac{f(2.36)}{f'(2.36)} \approx 2.36 - \frac{3.4241}{14.709} \approx 2.1272 \). (The root is \(2.0945515\dots\))
\( f(x) = x^3 - a \): \( x_{n+1} = x_n - \frac{x_n^3 - a}{3x_n^2} = \frac13\Big(2x_n + \frac{a}{x_n^2}\Big) \). From \(2\): \( 2.1667 \), \( 2.15450 \), \( 2.154435 \) (true: \(2.1544347\)).
The root is near \(0.567\); \( |\varphi'(x)| = e^{-x} \approx 0.567 < 1 \) there. Yes, it converges (oscillating). The limit \(0.5671432\dots\) is called the omega constant.
The convex curve \(y = e^x\) and the line \(y = x + 2\) intersect twice: once for \(x < 0\) (near \(-1.84\)) and once for \(x > 0\) (near \(1.15\)).
We need \( \frac{1}{2^n} < 10^{-6} \), i.e. \( 2^n > 10^6 \): \( n = 20 \). Newton needs only four steps for a much better result.
All the methods in this post replace a hard question ("where is the root?") by a sequence of easy ones. The chord pretends the function is a straight line between two points; the tangent pretends it is its own tangent line near one point; iteration turns the equation into a rule for improving a guess. The derivative is what makes them fast: it measures how far to move (Newton), how reliable the result is (\( |f(x_n)|/m \)), and whether an iteration will converge at all (\( |\varphi'| < 1 \)). That is how every calculator and computer actually solves equations.
Related posts: the mean value theorems (error estimates), tangents and normals (the geometry of Newton's step), and Taylor's formula (why Newton converges quadratically).