Section 31.1 Deriving Newton’s Method
We start from an initial guess \(x_0\) and rely on a Taylor expansion of \(f\text{,}\) truncated to first order, to estimate where \(f(x) = 0\text{:}\)
The idea is to follow the tangent line to \(f\) at our current guess down to where it crosses the \(x\)-axis, and use that as our next, hopefully better, guess. Repeating this generally walks us toward the true root \(x^*\) very quickly:
\(f(x_1) \approx f(x_0) + (x_1 - x_0) f'(x_0) = 0\)
Solving for \(x_1\) gives:
\(\displaystyle x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}\)
and, more generally, we iterate:
\(\displaystyle x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}\)
If we are lucky, this converges quickly! Note that Newton’s method does not always converge— a poor initial guess, or a derivative that is zero (or close to zero) somewhere along the way, can cause trouble.
We want to find the root of \(f(x) = x^3 - 8\text{,}\) starting from the initial guess \(x_0 = 10\text{.}\) Since Newton’s method needs both \(f(x)\) and \(f'(x)\) at every step, we’ll write a function with the prototype
void poly(double x, double *f, double *df); that computes both at once, writing its results back through pointers:
