Prev
Unit 2 · Nonlinear Equations
Newton's Method and the Secant Method
65m100 XP
Next
🔍Nonlinear Equations

Newton's Method and the Secant Method

Linearisation, quadratic convergence, failure modes, the secant method and safeguarded Newton

Cambridge, 1669
Isaac Newton is 26. In a manuscript he calls De analysi, circulated among a few mathematicians and not printed until 1711, he sets himself a cubic: y3−2y−5=0y^3 - 2y - 5 = 0 He guesses y=2y = 2, which is close: 8−4−5=−18 - 4 - 5 = -1. He writes y=2+py = 2 + p, substitutes, and gets p3+6p2+10p−1=0p^3 + 6p^2 + 10p - 1 = 0. Since pp is small, p3p^3 and 6p26p^2 are smaller still. He drops them. What remains is linear: 10p−1=010p - 1 = 0, so p=0.1p = 0.1. Now y=2.1y = 2.1. He substitutes again, drops the small powers again, and gets a correction of −0.0054-0.0054. Then another. Each correction is roughly the square of the last. Twenty-one years later Joseph Raphson published a cleaner version that worked directly with the original equation instead of rebuilding a new polynomial each time. Thomas Simpson extended it in 1740 to general functions and to systems of two equations. The method carries Newton's and Raphson's names, and every quadratically convergent algorithm since is a descendant.
Newton's move — throw away the nonlinear terms because the correction is small — is linearisation, and it is the most important idea in numerical analysis. In modern language: near a guess xkx_k, Taylor's theorem gives
g(xk+p)=g(xk)+g′(xk) p+12g′′(ξ) p2.g(x_k + p) = g(x_k) + g'(x_k)\,p + \tfrac12 g''(\xi)\,p^2.
Drop the last term, set the rest to zero and solve for pp.
xk+1=xk−g(xk)g′(xk)x_{k+1} = x_k - \frac{g(x_k)}{g'(x_k)}

Newton's method. Geometrically: follow the tangent line at (x_k, g(x_k)) down to where it crosses zero.

💡Quadratic convergence
Let ek=xk−x∗e_k = x_k - x^* be the error, with g(x∗)=0g(x^*) = 0 and g′(x∗)≠0g'(x^*) \ne 0. Expanding gg about x∗x^* and substituting into the Newton step gives ek+1≈g′′(x∗)2 g′(x∗) ek2.e_{k+1} \approx \dfrac{g''(x^*)}{2\,g'(x^*)}\,e_k^2. The new error is proportional to the square of the old one. If ek=10−5e_k = 10^{-5}, then ek+1e_{k+1} is around 10−1010^{-10}: the number of correct digits roughly doubles every step. Bisection adds a fixed 0.3 digits per step; Newton multiplies the digits by two.
Derivation
Why the error is squared
Expand gg about the current iterate xkx_k, evaluate at the root x∗x^*, and keep the exact Taylor remainder (lesson 1-3):
0=g(x∗)=g(xk)+g′(xk)(x∗−xk)+12g′′(ξ)(x∗−xk)2.0 = g(x^*) = g(x_k) + g'(x_k)(x^* - x_k) + \tfrac12 g''(\xi)(x^* - x_k)^2.
Divide by g′(xk)g'(x_k), which is not zero near a simple root:
0=g(xk)g′(xk)+(x∗−xk)+g′′(ξ)2g′(xk)(x∗−xk)2.0 = \frac{g(x_k)}{g'(x_k)} + (x^* - x_k) + \frac{g''(\xi)}{2g'(x_k)}(x^* - x_k)^2.
The Newton step says g(xk)/g′(xk)=xk−xk+1g(x_k)/g'(x_k) = x_k - x_{k+1}. Substitute it, and the first two terms become x∗−xk+1x^* - x_{k+1}:
xk+1−x∗=g′′(ξ)2g′(xk) (xk−x∗)2that isek+1=g′′(ξ)2g′(xk) ek2.x_{k+1} - x^* = \frac{g''(\xi)}{2g'(x_k)}\,(x_k - x^*)^2 \qquad\text{that is}\qquad e_{k+1} = \frac{g''(\xi)}{2g'(x_k)}\,e_k^2.
This is exact. As xk→x∗x_k \to x^*, ξ\xi and xkx_k both approach x∗x^* and the factor approaches the constant C=g′′(x∗)/(2g′(x∗))C = g''(x^*)/(2g'(x^*)). The derivation also shows when Newton fails: the division needed g′(xk)≠0g'(x_k) \ne 0, and the conclusion is only useful once ∣C ek∣<1|C\,e_k| < 1 — that is, close enough to the root.
📐Newton's cubic, digit by digit
From y0=2y_0 = 2, with g(y)=y3−2y−5g(y) = y^3 - 2y - 5 and g′(y)=3y2−2g'(y) = 3y^2 - 2, the iterates are 2.0, 2.1, 2.0945681211, 2.0945514817 and 2.0945514815423265, with correct digits of 1.3, 2.6, 5.1, 10.1 — doubling, exactly as the theory says. The constant g′′/(2g′)=6y∗/(2(3y∗2−2))≈0.563g''/(2g') = 6y^*/(2(3y^{*2}-2)) \approx 0.563 predicts e3≈0.563×(1.66×10−5)2=1.55×10−10e_3 \approx 0.563 \times (1.66\times10^{-5})^2 = 1.55\times10^{-10}; the measured value is 1.56×10−101.56\times10^{-10}.
If I have seen further it is by standing on the shoulders of Giants.
– Isaac Newton, letter to Robert Hooke (1675)
How Newton fails. The derivation assumed a good guess and a nonzero slope. Remove either and the method can misbehave badly:
  • A flat tangent. If g′(xk)≈0g'(x_k) \approx 0, the tangent is nearly horizontal and the next iterate is thrown far away. For the nozzle equation below, the slope is exactly zero at the throat, M=1M = 1.
  • Divergence. For g(x)=arctan⁡xg(x) = \arctan x, the root is 0, but from any ∣x0∣>1.39|x_0| > 1.39 each iterate is further out than the last, alternating in sign.
  • Cycles. For x3−2x+2x^3 - 2x + 2 starting at 0, Newton goes to 1 and straight back to 0, forever.
  • Multiple roots. At a double root g′(x∗)=0g'(x^*) = 0 too; convergence becomes linear, gaining only a fraction of a digit per step.
Newton's convergence is local: guaranteed only once you are close enough. How close depends on the function.
The secant method. Newton needs g′g'. Sometimes you have no formula for it — gg might be the output of a simulation. Replace the tangent with the secant line through the last two iterates:
xk+1=xk−g(xk) xk−xk−1g(xk)−g(xk−1).x_{k+1} = x_k - g(x_k)\,\dfrac{x_k - x_{k-1}}{g(x_k) - g(x_{k-1})}.
This is false position without the bracket: it always uses the two newest points, so nothing gets stuck. The error now satisfies ek+1≈C ek ek−1e_{k+1} \approx C\,e_k\,e_{k-1}, and the order of convergence pp solves p2=p+1p^2 = p + 1:
p=1+52≈1.618p = \frac{1+\sqrt5}{2} \approx 1.618

The secant method's order of convergence is the golden ratio. Each step costs one function evaluation instead of Newton's two (g and g′), so per evaluation the secant method is often faster than Newton.

Derivation
From ek+1≈Cekek−1e_{k+1} \approx C e_k e_{k-1} to the golden ratio
The error relation. Near the root write g(x)≈g′e+12g′′e2g(x) \approx g'e + \tfrac12 g''e^2, with e=x−x∗e = x - x^* and g′g', g′′g'' evaluated at x∗x^*. The secant slope through the last two points is then
g(xk)−g(xk−1)xk−xk−1≈g′+12g′′ (ek+ek−1),\frac{g(x_k) - g(x_{k-1})}{x_k - x_{k-1}} \approx g' + \tfrac12 g''\,(e_k + e_{k-1}),
a slightly wrong tangent. Put it into the secant step xk+1=xk−g(xk)/slopex_{k+1} = x_k - g(x_k)/\text{slope}, subtract x∗x^*, divide top and bottom by g′g' and write C=g′′/(2g′)C = g''/(2g'):
ek+1≈ek−ek+Cek21+C(ek+ek−1).e_{k+1} \approx e_k - \frac{e_k + C e_k^2}{1 + C(e_k + e_{k-1})}.
For small errors 1/(1+ϵ)≈1−ϵ1/(1 + \epsilon) \approx 1 - \epsilon, so to second order
ek+1≈ek−(ek+Cek2)(1−Cek−Cek−1)=ek−ek−Cek2+Cek2+Cekek−1=C ek ek−1.e_{k+1} \approx e_k - (e_k + Ce_k^2)\big(1 - Ce_k - Ce_{k-1}\big) = e_k - e_k - Ce_k^2 + Ce_k^2 + Ce_ke_{k-1} = C\,e_k\,e_{k-1}.
The order. Suppose the method has order pp: ∣ek+1∣≈A∣ek∣p|e_{k+1}| \approx A|e_k|^p for every kk. Then also ∣ek∣≈A∣ek−1∣p|e_k| \approx A|e_{k-1}|^p, so ∣ek−1∣≈(∣ek∣/A)1/p|e_{k-1}| \approx (|e_k|/A)^{1/p}. Substitute both into the error relation:
A∣ek∣p≈∣C∣ ∣ek∣ (∣ek∣A)1/p.A|e_k|^p \approx |C|\,|e_k|\,\Big(\frac{|e_k|}{A}\Big)^{1/p}.
For this to hold as ek→0e_k \to 0 the powers of ∣ek∣|e_k| on the two sides must agree: p=1+1/pp = 1 + 1/p, or p2−p−1=0p^2 - p - 1 = 0. Its positive root is p=(1+5)/2≈1.618p = (1 + \sqrt5)/2 \approx 1.618.
Measuring it. The same assumption gives ek+1/ek≈(ek/ek−1)pe_{k+1}/e_k \approx (e_k/e_{k-1})^p for consecutive ratios; taking logarithms, p≈log⁡(ek+1/ek)/log⁡(ek/ek−1)p \approx \log(e_{k+1}/e_k)/\log(e_k/e_{k-1}) — the estimator used in the callout below and in the lab.
🕰Measuring order from data
If ek+1≈Cekpe_{k+1} \approx C e_k^p, then p≈log⁡(ek+1/ek) / log⁡(ek/ek−1)p \approx \log(e_{k+1}/e_k)\,/\,\log(e_k/e_{k-1}). In double precision the secant method reaches machine precision in about six steps — too few for the estimate to settle. Run it in 300-digit arithmetic and the estimates go 1.50, 1.67, 1.60, 1.625, 1.615, 1.619, 1.618, 1.618… homing in on the golden ratio. You will do exactly that in the lab.
💡Safeguarded Newton
Production root finders combine the two worlds: keep a bracket [a,b][a, b], try a Newton (or secant) step, and accept it only if it lands inside the bracket. If it does not, or if it fails to shrink the bracket enough, take a bisection step instead. Then update the bracket using the sign of gg at the new point. Near the root every Newton step is accepted and you get quadratic convergence. Far from it, bisection keeps you safe. scipy.optimize.newton does not do this; rtsafe in Numerical Recipes and brentq (with interpolation instead of derivatives) do.
📐The rocket nozzle
In a converging–diverging nozzle the isentropic area ratio fixes the Mach number: AA∗=1M[2γ+1(1+γ−12M2)]γ+12(γ−1)\dfrac{A}{A^*} = \dfrac{1}{M}\left[\dfrac{2}{\gamma+1}\left(1 + \dfrac{\gamma-1}{2}M^2\right)\right]^{\frac{\gamma+1}{2(\gamma-1)}} For A/A∗=2.5A/A^* = 2.5 and γ=1.4\gamma = 1.4 there are two answers: a subsonic M=0.2395M = 0.2395 upstream of the throat and a supersonic M=2.4428M = 2.4428 downstream. Newton from M0=0.2M_0 = 0.2 finds the first in 5 steps; from M0=2M_0 = 2 it finds the second in 6. From M0=1M_0 = 1 it cannot even start — the slope of A/A∗A/A^* is zero at the throat. The physics decides which root you want; your starting guess must respect it.
💡Where you will use this
Rocket Propulsion: exit Mach from area ratio, chamber temperature from an energy balance, shock positions. Orbital Mechanics: Kepler's equation E−esin⁡E=ME - e\sin E = M is solved by Newton in every orbit propagator. Aircraft Engines: turbomachinery matching. Structures: nonlinear finite-element analysis is Newton's method on millions of unknowns, and its convergence plots are the doubling digits of this lesson.
📚Further reading
  • Michael Heath, Scientific Computing: An Introductory Survey (2nd ed.; SIAM Classics 2018), chapter 5, 'Nonlinear Equations' — Newton, secant and safeguarded methods with their convergence rates.
  • C. T. Kelley, Solving Nonlinear Equations with Newton's Method (SIAM, 2003) — a short, practical book on making Newton work in real codes.
  • Tjalling Ypma, 'Historical development of the Newton–Raphson method', SIAM Review 37(4), 531–551 (1995) — what Newton, Raphson and Simpson actually wrote.
↓But there is a problem
Newton converges spectacularly when it converges and goes badly wrong when it does not. We have seen the symptoms — cycles, divergence, sudden jumps — but not the cause. Here is an experiment you can do on any scientific calculator. Set it to radians, type any number, and press cos over and over. Whatever you start from, the display settles on 0.739085… and stays there. Why that number? Why does the calculator converge at all? And why does it take dozens of presses, when Newton takes four?