Skip to content

Lesson 41: Interpolation and Gradient-Based One-Dimensional Methods

41.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Derive and apply the three-point quadratic interpolation formula for a minimum.
  2. Apply Newton–Raphson to \(f'(x)=0\) and recognise its quadratic convergence.
  3. Apply the secant method and explain why it needs no second derivative.
  4. Compare the orders of convergence of the methods in Lessons 38–41.
  5. Explain why practical codes safeguard fast methods with a bracketing method.

41.2 From Elimination to Interpolation

Elimination methods (Lessons 38–40) use only the ordering of function values: they ask "which of these two is smaller?" and throw away everything else the numbers contain. They pay for that robustness with linear convergence — the interval shrinks by a constant factor each step.

Interpolation methods instead use the magnitudes, fitting a simple model to the data and jumping to that model's minimum. When \(f\) is smooth this is dramatically faster; when it is not, the model can be badly wrong and the method can diverge.

Family Information used Convergence order \(p\) Robustness
Golden section comparisons only \(1\) (linear, ratio \(0.618\)) very high
Quadratic interpolation three function values \(\approx1.3\) moderate
Secant (on \(f'\)) two derivative values \(1.618\) (superlinear) moderate
Newton–Raphson (on \(f'\)) \(f'\) and \(f''\) \(2\) (quadratic) low

Order of convergence. If \(e_k=|x_k-x^{*}|\) and \(e_{k+1}\approx Ce_k^{\,p}\), then \(p\) is the order. \(p=1\) multiplies the accuracy by a constant each step; \(p=2\) doubles the number of correct digits each step.

41.3 Quadratic Interpolation (Powell's Method)

Fit a parabola through three points and minimise it.

Given \(x_1<x_2<x_3\) with values \(f_1,f_2,f_3\), the fitted parabola \(q(x)=a+bx+cx^{2}\) has its minimum at \(\bar x=-b/2c\), which works out to

Result 1 (three-point formula). $\(\boxed{\ \bar x=\frac12\cdot \frac{(x_2^{2}-x_3^{2})f_1+(x_3^{2}-x_1^{2})f_2+(x_1^{2}-x_2^{2})f_3} {(x_2-x_3)f_1+(x_3-x_1)f_2+(x_1-x_2)f_3}\ }\tag{2.1}\)$

The algorithm. Compute \(\bar x\); evaluate \(f(\bar x)\); keep the three points among \(\{x_1,x_2,x_3,\bar x\}\) that bracket the lowest value; repeat.

Requirement. The denominator vanishes when the three points are collinear in \((x,f)\), and the formula returns a maximum if the fitted parabola opens downward. Both are detected by checking that \(f_2<f_1\) and \(f_2<f_3\) — i.e. that the middle point is the lowest of the three. Always check this before trusting (2.1).

41.4 Newton–Raphson

A minimum of \(f\) is a root of \(f'\), so apply Newton's root-finding iteration to \(f'\):

Result 2 (Newton's method for optimisation). $\(\boxed{\ x_{k+1}=x_k-\frac{f'(x_k)}{f''(x_k)}\ }\tag{3.1}\)$

Interpretation. Expand \(f\) to second order about \(x_k\):

\[f(x)\approx f(x_k)+f'(x_k)(x-x_k)+\tfrac12f''(x_k)(x-x_k)^{2}\]

and minimise this quadratic exactly. Newton's method fits a parabola using derivative information and jumps to its vertex — the same idea as §2 with derivatives instead of extra points.

Convergence and its failures

Theorem. If \(f''(x^{*})\ne0\) and \(x_0\) is close enough to \(x^{*}\), Newton's method converges quadratically: \(e_{k+1}\approx Ce_k^{2}\).

But the guarantee is local, and three failures are common:

Failure Cause Symptom
Converges to a maximum (3.1) solves \(f'=0\), which maxima also satisfy \(f''<0\) at the answer
Divergence \(x_0\) too far away; the local quadratic model is wrong iterates fly off
Division by zero \(f''(x_k)=0\) (an inflection) overflow

Two standard safeguards: reject any step with \(f''\le0\) (it is not a descent step for a minimisation), and fall back to bisection or golden section whenever the Newton step leaves the known bracket. Every production code does both.

41.5 The Secant Method

Newton needs \(f''\), which may be unavailable or expensive. Replace it by a finite difference of two successive gradients:

\[f''(x_k)\approx\frac{f'(x_k)-f'(x_{k-1})}{x_k-x_{k-1}}\]

Result 3 (secant method). $\(\boxed{\ x_{k+1}=x_k-f'(x_k)\,\frac{x_k-x_{k-1}}{f'(x_k)-f'(x_{k-1})}\ }\tag{4.1}\)$

  • Needs two starting points and only first derivatives.
  • Convergence order is \(p=\dfrac{1+\sqrt5}{2}=1.618\) — the golden ratio again, arising here from the recursion \(p^{2}=p+1\) satisfied by the error exponents.
  • Cost per iteration is half of Newton's, so on functions where \(f''\) is as expensive as \(f'\), secant is usually the faster method in wall-clock terms even though its order is lower.

The multivariable generalisation of this trick — approximating the Hessian from successive gradients — is the quasi-Newton idea (BFGS, DFP), the workhorse of modern optimisation software.

41.6 Solved Problems

Running example: \(f(x)=x^{2}+\dfrac{54}{x}\), with

\[f'(x)=2x-\frac{54}{x^{2}},\qquad f''(x)=2+\frac{108}{x^{3}},\qquad x^{*}=3,\ f(3)=27.\]

Problem 1 — Newton–Raphson from a poor start

Apply Newton's method from \(x_0=1\).

Solution. \(x_{k+1}=x_k-\dfrac{2x_k-54/x_k^{2}}{2+108/x_k^{3}}\).

\(k\) \(x_k\) \(f'(x_k)\) \(f''(x_k)\) \(f(x_k)\) error \(\lvert x_k-3\rvert\)
0 1.0000000 \(-52.00000\) 110.0000 55.00000 \(2.00\)
1 1.4727273 \(-21.95166\) 35.8109 38.83559 \(1.53\)
2 2.0857156 \(-8.24176\) 13.9031 30.24060 \(9.14\times10^{-1}\)
3 2.6785179 \(-2.16967\) 7.6200 27.33486 \(3.21\times10^{-1}\)
4 2.9632490 \(-0.22325\) 6.1507 27.00409 \(3.68\times10^{-2}\)
5 2.9995461 \(-0.00272\) 6.0018 27.00000 \(4.54\times10^{-4}\)
6 2.9999999 \(-0.0000004\) 6.0000 27.00000 \(6.87\times10^{-8}\)
\[\boxed{x^{*}=3.0000000\text{ to 7 decimals in 6 iterations}}\]

Reading the convergence. Look at the last three errors:

\[3.68\times10^{-2}\ \to\ 4.54\times10^{-4}\ \to\ 6.87\times10^{-8}\]

Each is roughly the square of the one before, times a constant: \((3.68\times10^{-2})^{2}=1.35\times10^{-3}\), and \(4.54\times10^{-4}/1.35\times10^{-3}=0.33\); \((4.54\times10^{-4})^{2}=2.06\times10^{-7}\), and \(6.87\times10^{-8}/2.06\times10^{-7}=0.33\). The constant \(C\approx1/3\) is stable — textbook quadratic convergence, and the number of correct digits doubles at each of the last three steps (\(1\to3\to7\)).

But note the early behaviour. From \(x_0=1\) the first three steps are slow, because the quadratic model built at \(x=1\) (where \(f''=110\)) is a poor picture of a function whose curvature at the optimum is only \(6\). Newton is fast only in the neighbourhood of the answer. Compare golden section, which needed \(7\) evaluations to reach an interval of \(0.22\) where Newton reached \(10^{-7}\) — but golden section could never have diverged.

Problem 2 — Newton from the other side

Repeat from \(x_0=5\).

Solution.

\(k\) \(x_k\) \(f'(x_k)\) error
0 5.0000000 \(+7.84000\) \(2.00\)
1 2.2625698 \(-6.02334\) \(7.37\times10^{-1}\)
2 2.7944632 \(-1.32615\) \(2.06\times10^{-1}\)
3 2.9853001 \(-0.08863\) \(1.47\times10^{-2}\)
4 2.9999277 \(-0.00043\) \(7.23\times10^{-5}\)
5 3.0000000 \(-0.0000000\) \(1.74\times10^{-9}\)
\[\boxed{\text{Converged in 5 iterations}}\]

Interpretation. Note the overshoot at step 1: from \(x_0=5\), where \(f'>0\), the step is \(-7.84/2.864=-2.74\), landing at \(2.26\) — well past the minimum. Newton's method does not respect brackets and routinely jumps over the answer. Here that was harmless (the function is convex and the iterate stayed positive), but a single overshoot to \(x\le0\) would have been fatal, since \(f\) is undefined there.

This is exactly why safeguarding matters. A production line search runs Newton but keeps a bracket, and any step landing outside it is replaced by a golden-section step. The result converges quadratically when Newton behaves and never worse than linearly when it does not.

Problem 3 — The secant method

Apply the secant method with \(x_0=1\), \(x_1=5\).

Solution. \(x_{k+1}=x_k-f'(x_k)\dfrac{x_k-x_{k-1}}{f'(x_k)-f'(x_{k-1})}\), with \(f'(1)=-52\), \(f'(5)=7.84\).

\(k\) \(x_{k-1}\) \(x_k\) \(x_{k+1}\) \(f'(x_{k+1})\) error
1 1.0000000 5.0000000 4.4759358 \(+6.25645\) \(1.48\)
2 5.0000000 4.4759358 2.4054033 \(-4.52212\) \(5.95\times10^{-1}\)
3 4.4759358 2.4054033 3.2740896 \(+1.51071\) \(2.74\times10^{-1}\)
4 2.4054033 3.2740896 3.0565581 \(+0.33311\) \(5.66\times10^{-2}\)
5 3.2740896 3.0565581 2.9950249 \(-0.02990\) \(4.98\times10^{-3}\)
6 3.0565581 2.9950249 3.0000933 \(+0.00056\) \(9.33\times10^{-5}\)
7 2.9950249 3.0000933 3.0000002 \(+0.0000009\) \(1.55\times10^{-7}\)
\[\boxed{x^{*}=3.0000002\text{ after 7 iterations}}\]

Reading the convergence. The errors \(5.66\times10^{-2}\to4.98\times10^{-3}\to9.33\times10^{-5}\to1.55\times10^{-7}\) satisfy \(e_{k+1}\approx Ce_k^{1.618}\): for instance \((9.33\times10^{-5})^{1.618}=4.6\times10^{-7}\), and the observed \(1.55\times10^{-7}\) is of that order. Superlinear but not quadratic, exactly as the theory predicts.

Cost comparison with Newton.

Iterations to \(10^{-7}\) \(f'\) evaluations \(f''\) evaluations
Newton (from \(x_0=1\)) 6 6 6
Secant (from \(1,5\)) 7 7 0

If \(f''\) costs as much as \(f'\), Newton spends \(12\) derivative evaluations to secant's \(7\). The secant method is nearly always the better buy when second derivatives are not free — which is the normal situation, and the reason quasi-Newton methods dominate practice.

Problem 4 — Quadratic interpolation

Starting from the bracket \(\{1.5,\ 2.5,\ 4.5\}\) found in Lesson 38, apply quadratic interpolation.

Solution. With \(f(1.5)=38.25\), \(f(2.5)=27.85\), \(f(4.5)=32.25\), the middle point is lowest ✓, so (2.1) applies.

Iteration 1. Numerator and denominator of (2.1):

\[N=(2.5^{2}-4.5^{2})(38.25)+(4.5^{2}-1.5^{2})(27.85)+(1.5^{2}-2.5^{2})(32.25)\]
\[=(-14)(38.25)+(18)(27.85)+(-4)(32.25)=-535.5+501.3-129=-163.2\]
\[D=(2.5-4.5)(38.25)+(4.5-1.5)(27.85)+(1.5-2.5)(32.25)=-76.5+83.55-32.25=-25.2\]
\[\bar x=\tfrac12\cdot\frac{-163.2}{-25.2}=3.23810,\qquad f(3.23810)=27.16173\]
Iteration Three points \(\bar x\) \(f(\bar x)\) error
1 \(1.50000,\ 2.50000,\ 4.50000\) 3.23810 27.16173 \(2.38\times10^{-1}\)
2 \(2.50000,\ 3.23810,\ 4.50000\) 3.05687 27.00958 \(5.69\times10^{-2}\)
3 \(2.50000,\ 3.05687,\ 3.23810\) 3.01557 27.00072 \(1.56\times10^{-2}\)
4 \(2.50000,\ 3.01557,\ 3.05687\) 3.00414 27.00005 \(4.14\times10^{-3}\)
5 \(2.50000,\ 3.00414,\ 3.01557\) 3.00115 27.00000 \(1.15\times10^{-3}\)
\[\boxed{x\approx3.00115\text{ after 5 iterations}}\]

Interpretation — a real weakness on display. The error ratios are \(0.239,\ 0.274,\ 0.265,\ 0.278\) — constant, i.e. merely linear convergence, not the \(p\approx1.3\) the method is capable of. The cause is visible in the table: the stale point \(2.50000\) never leaves the working set, because it always sits on the far side of the current best. The parabola is therefore always fitted to two nearby points and one distant one, which is a poor local model.

The fix used in real implementations (Brent's method) is to force the retained points to shrink towards the optimum, and to fall back on golden section whenever the interpolation step is not making adequate progress. Brent's method combines exactly the three ideas of Lessons 40 and 41 — golden section for safety, quadratic interpolation for speed, and a bracket for a guarantee — and is the default line search in most scientific libraries.

Problem 5 — Choosing and safeguarding

Summarise all five one-dimensional methods on this problem, and state a practical recommendation.

Solution. All started from information equivalent to the interval \([1,5]\) or the bracket \(\{1.5,2.5,4.5\}\).

Method Info needed Evaluations to \(\lvert x-3\rvert<10^{-4}\) Order Can it fail?
Interval halving \(f\) only \(31\) 1 no
Golden section \(f\) only \(22\) 1 no
Fibonacci \(f\) only, \(n\) fixed \(22\) 1 no
Quadratic interpolation 3 values of \(f\) 5–8 (here 5 gave \(10^{-3}\)) \(\approx1.3\) yes — collinear or downward parabola
Secant \(f'\) 6 1.618 yes — divergence
Newton–Raphson \(f'\) and \(f''\) 5 2 yes — divergence, maxima, \(f''=0\)

Recommendation.

  1. Bracket first (Lesson 38). Without a bracket nothing can be guaranteed.
  2. Inside the bracket, try the fast method — quadratic interpolation if only values are available, Newton or secant if derivatives are.
  3. Safeguard every step: if the proposed point falls outside the bracket, or fails to reduce the interval by a reasonable factor, take a golden-section step instead.
  4. Stop at the noise floor of \(f\). Chasing \(10^{-12}\) on a function known to \(10^{-6}\) is meaningless.

The general principle of numerical optimisation. Fast methods are fast locally and dangerous globally; robust methods are safe everywhere and slow. The right answer is never to choose one but to combine them: use the fast method by default and the robust method as a guarantee. Brent's method for line search, and trust-region methods in several variables, are both instances of exactly this pattern.

41.7 Practice Problems

  1. Apply two Newton steps to \(f(x)=x^{4}-4x\) from \(x_0=2\). (Answer: \(f'=4x^3-4\), \(f''=12x^2\); \(x_1=2-28/48=1.41667\), \(x_2=1.41667-7.3773/24.0833=1.11053\); exact \(x^{*}=1\))
  2. Why can Newton's method converge to a maximum? Give a function and a starting point where it does. (Answer: it solves \(f'=0\), which maxima satisfy too; e.g. \(f=-x^{2}\) from any \(x_0\) converges in one step to the maximum at \(0\))
  3. Apply one secant step to \(f(x)=x^{2}-4x+7\) with \(x_0=0\), \(x_1=1\). (Answer: \(f'=2x-4\); \(x_2=1-(-2)\frac{1-0}{-2-(-4)}=2\) — the exact minimum, since \(f'\) is linear and the secant is exact for a linear function)
  4. Fit a parabola through \((0,5)\), \((1,2)\), \((3,8)\) and find its minimum by (2.1). (Answer: \(N=(1-9)5+(9-0)2+(0-1)8=-40+18-8=-30\); \(D=(1-3)5+(3-0)2+(0-1)8=-10+6-8=-12\); \(\bar x=\tfrac12(-30/-12)=1.25\))
  5. A function is known only to \(\pm10^{-4}\) from a simulation. Which of the six methods above should not be used, and why?

41.8 Summary

  • Quadratic interpolation fits a parabola to three points and jumps to its vertex, formula (2.1). Check that the middle point is the lowest before using it.
  • Newton–Raphson: \(x_{k+1}=x_k-\dfrac{f'(x_k)}{f''(x_k)}\) — fits a parabola from derivatives. Quadratic convergence (correct digits double), but only locally: it can diverge, converge to a maximum, or divide by zero.
  • Secant: replaces \(f''\) by a finite difference of gradients. Order \(1.618\), no second derivatives, so usually the better buy in real cost. Its multivariable version is the quasi-Newton family.
  • Orders: elimination \(1\), interpolation \(\approx1.3\), secant \(1.618\), Newton \(2\).
  • Fast is local, robust is global. Interpolation methods can stall (Problem 4's stale point) or diverge; elimination methods never fail but never accelerate.
  • Always bracket, always safeguard, always stop at the noise floor. Brent's method — golden section plus quadratic interpolation inside a maintained bracket — is the practical answer and the default in scientific libraries.

Next lesson: L42 — Unconstrained multivariable optimisation: steepest descent, Newton's method and conjugate gradients.

Practise now: unit4-nlp-search-lab.html → Interpolation Lab: watch the fitted parabola move at each iteration, with Newton, secant and golden section racing on the same function.