Section 31.1 Successive parabolic interpolation
Recall that Newton's method for root-finding, namely \(x = a - f(a)/f'(a)\text{,}\) has a geometric interpretation: draw a tangent line to \(y = f(x)\) at \(x = a\text{,}\) and use the intersection of that line with the horizontal axis as the new \(x\)-value. This geometric construction naturally led to the secant method: just replace a tangent line by a secant line. Is there a geometric interpretation for minimization using Newton's method, that is \(x = a - f'(a)/f''(a)\text{?}\)
Yes, there is. Let \(T_2\) be the Taylor polynomial at \(x = a\) of degree 2, namely
The critical point of this polynomial is found by equating \(T_2'\) to zero: since
we get \(x = a - f'(a)/f''(a)\text{.}\) Therefore, the logic of minimization by Newton's method is to draw a “tangent parabola” at \(x=a\) and use its critical point (hopefully a minimum) as the new \(x\)-value.
Having made this geometric observation, we can eliminate derivatives from the picture by constructing a “secant parabola” instead, which is a parabola passing through three points on the graph of a function. Following the logic of the secant method, we should replace the “oldest” of the three points used to construct the parabola by the critical point of this parabola. The process repeats until it (hopefully) converges to a point of minimum. This is the method of successive parabolic interpolation.
How to find the critical point of parabola passing through points \((a, f(a))\text{,}\) \((b, f(b))\text{,}\) \((c, f(c))\text{?}\) Newton interpolating polynomial is one way: it provides the interpolating polynomial in the form
from where we can find \(g'(x) = \alpha + \beta(2x - a- b)\text{,}\) hence
The coefficients \(\alpha, \beta\) are determined from \(g(b) = f(b)\) and \(g(c) = f(c)\text{,}\) namely
Example 31.1.1. Minimize by successive parabolic interpolation.
Minimize \(f(x) = x^4 - 3 x^2 + x + 1\) using successive parabolic interpolation with initial triple of points \(a, b, c = -2, 0, 2\text{.}\)
f = @(x) x.^4 - 3*x.^2 + x + 1; a = -2; b = 0; c = 2; max_tries = 10000; for k = 1:max_tries alpha = (f(b)-f(a))/(b-a); beta = (f(c)-f(a)-alpha*(c-a))/((c-a)*(c-b)); x = (a+b)/2 - alpha/(2*beta); a = b; b = c; c = x; if max([a b c]) - min([a b c]) < 1e-6 break end end if k < max_tries fprintf('Found x = %g with f(x) = %g after %d steps\n', c, f(c), k); else disp('Failed to converge') end
As Example 31.1.1 shows, parabolic interpolation can converge to a local maximum. Indeed, a closer look shows it does not distinguish between \(f\) and \(-f\text{,}\) so it can maximize just as well as minimize (same issue as with Newton's method). So this method should be used in combination with another one, so that when the interpolated parabola is not acceptable (is “upside down”), we fall back on the second method.