Skip to main content

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

\begin{equation*} T_2(x) = f(a) + f'(a) (x-a) + \frac{f''(a)}{2}(x-a)^2 \end{equation*}

The critical point of this polynomial is found by equating \(T_2'\) to zero: since

\begin{equation*} T_2'(x) = f'(a) + f''(a)(x-a) \end{equation*}

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

\begin{equation} g(x) = f(a) + \alpha(x-a) + \beta(x-a)(x-b)\label{eq-newton-form-parabola}\tag{31.1.1} \end{equation}

from where we can find \(g'(x) = \alpha + \beta(2x - a- b)\text{,}\) hence

\begin{equation} x = \frac{a+b}{2} - \frac{\alpha}{2\beta}\label{eq-crit-point-interp}\tag{31.1.2} \end{equation}

The coefficients \(\alpha, \beta\) are determined from \(g(b) = f(b)\) and \(g(c) = f(c)\text{,}\) namely

\begin{equation} \alpha = \frac{f(b)-f(a)}{b-a},\quad \beta = \frac{f(c) - f(a) - \alpha(c-a)}{(c-a)(c-b)}\label{eq-coeffs-newton-parabola}\tag{31.1.3} \end{equation}

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{.}\)

Solution
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.