Newton-Raphson method for root finding

What is the method?

WHAT each piece means

$f(x_n)$ : how far above/below zero we currently are.
$f'(x_n)$ : the slope of the tangent at the current guess.
$f(x_n)/f'(x_n)$ : the horizontal distance the tangent travels to reach the axis.

Deriving it from scratch (tangent-line argument)

Formula Derivation

HOW: At the point $(x_n, f(x_n))$ , the tangent line has slope $f'(x_n)$ . Point–slope form: $y - f(x_n) = f'(x_n)\,(x - x_n)$ Why this step? The tangent is the best straight-line approximation of $f$ near $x_n$ , so its root approximates $f$ 's root.

Set $y = 0$ (we want where the tangent crosses the axis) and call that $x = x_{n+1}$ : $0 - f(x_n) = f'(x_n)\,(x_{n+1} - x_n)$ Why this step? The whole point is to find where the tangent equals zero — that's our next guess.

Divide by $f'(x_n)$ (allowed only if $f'(x_n)\neq 0$ ): $x_{n+1} - x_n = -\frac{f(x_n)}{f'(x_n)} \;\Rightarrow\; \boxed{x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}}$ Why this step? Solving for $x_{n+1}$ gives the recipe — no new assumption needed.

Alternative derivation (Taylor series — shows why it's so fast)

Expand $f$ near $x_n$ and demand $f(\text{root})=0$ : $0 = f(x_n) + f'(x_n)(r - x_n) + \tfrac{1}{2}f''(\xi)(r-x_n)^2$ Dropping the quadratic term and solving for $r$ gives the same formula. The discarded term is $O((r-x_n)^2)$ — this is the seed of quadratic convergence: the error roughly squares each step.

Figure — Newton-Raphson method for root finding

Worked Example 1 — compute $\sqrt{2}$

Solve $f(x)=x^2-2=0$ , so $f'(x)=2x$ . Iteration: $x_{n+1} = x_n - \frac{x_n^2-2}{2x_n} = \frac{x_n}{2} + \frac{1}{x_n}$ Why this step? Simplifying gives the classic "average your guess with $2/x$ " formula.

Start $x_0 = 1$ :

$x_1 = \tfrac{1}{2}+1 = 1.5$ — Why? plug $x_0=1$ in.
$x_2 = 0.75 + 0.6667 = 1.41667$ — Why? feed $x_1$ back in.
$x_3 = 1.41421568...$ — Why? one more pass; now correct to 6 digits.

True $\sqrt2 = 1.41421356...$ — compare $x_2=1.41667$ (3 correct digits: $1,4,1$ ) to $x_3=1.41421568$ (6 correct digits: $1,4,1,4,2,1$ ). The number of correct digits roughly doubled in one step (3→6), the signature of quadratic convergence.

Worked Example 2 — a transcendental root

Solve $f(x)=\cos x - x = 0$ , $f'(x) = -\sin x - 1$ . $x_{n+1} = x_n - \frac{\cos x_n - x_n}{-\sin x_n - 1}$ Start $x_0 = 1$ (radians):

$f(1)=0.5403-1=-0.4597$ , $f'(1)=-0.8415-1=-1.8415$ . Why? evaluate both at the guess.
$x_1 = 1 - \frac{-0.4597}{-1.8415} = 1 - 0.2497 = 0.7503$ .
$x_2 \approx 0.73911$ , $x_3 \approx 0.73909$ — converged to the Dottie number.

Worked Example 3 — when it MISBEHAVES

Solve $f(x)=x^3 - 2x + 2 = 0$ with $x_0 = 0$ . $f'(x)=3x^2-2$ , so $f'(0)=-2$ .

$x_1 = 0 - \frac{2}{-2} = 1$ .
$f(1)=1$ , $f'(1)=1$ , $x_2 = 1 - 1 = 0$ .
Back to $0$ ! The iteration cycles $0\to1\to0\to\cdots$ forever. Why this matters: Newton-Raphson is local, not guaranteed global.

Common mistake Steel-manning the classic errors

1. "It always converges if the root exists." Why it feels right: the tangent trick is so clean it seems foolproof. Fix: convergence needs a good enough starting guess and well-behaved $f'$ . Example 3 cycles; bad guesses can diverge.

2. "Just iterate, don't check $f'(x_n)$ ." Why it feels right: you rarely hit exactly a flat spot. Fix: if $f'(x_n)\approx 0$ , the tangent is nearly horizontal and shoots $x_{n+1}$ far away. Always guard against tiny derivatives.

3. "Quadratic convergence at every root." Why it feels right: we proved error squares. Fix: that proof assumed a simple root ( $f'(\text{root})\neq 0$ ). At a double root convergence drops to merely linear (errors halve, not square).

4. Sign slip: writing $x_{n+1}=x_n + f/f'$ . Fix: it's minus — you subtract the overshoot. Sanity check with $\sqrt2$ : $1 + 1/1 = 2$ moves away, while $1 - (-1)/2 = 1.5$ moves toward.

Recall Feynman: explain to a 12-year-old

Imagine the curve is a dark hill and you can only feel the slope right under your feet. You can't see where the ground hits sea level. So you pretend the hill keeps going perfectly straight (the slope you feel) and you walk to where that straight line touches sea level. You're not there yet, but you're closer. You feel the slope again, draw a new straight line, walk again. After a few walks you're standing almost exactly on the spot — and each walk cuts your remaining distance enormously, not just a little.

Flashcards

What is the Newton-Raphson update formula?

x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}

From what geometric object is the formula derived?

The tangent line at

(x_n, f(x_n))

, finding where it crosses the

x

-axis.

Why subtract

f/f'

rather than add?

You move against the current error: the term

f/f'

is the horizontal jump the tangent takes to reach zero.

What rate of convergence does NR have at a simple root?

Quadratic — the error roughly squares each step (number of correct digits doubles).

What condition can make NR blow up or oscillate?

f'(x_n) \approx 0

(near-horizontal tangent) or a poor starting guess; it can cycle or diverge.

At a double root, what happens to convergence?

It degrades from quadratic to linear.

Newton-Raphson iteration for

\sqrt a

via

f(x)=x^2-a

x_{n+1} = \tfrac{1}{2}\left(x_n + \tfrac{a}{x_n}\right)

What stopping criterion is typically used?

|x_{n+1}-x_n| < \varepsilon

|f(x_n)| < \varepsilon

Where does the quadratic-convergence guarantee come from?

The dropped Taylor term is

O((\text{error})^2)

, so the next error is proportional to the square of the current error.

Connections

Tangent line and linear approximation — NR is repeated linearization.
Taylor series — explains quadratic convergence.
Derivatives — definition and rules — supplies $f'$ .
Fixed-point iteration — NR is a special, fast fixed-point scheme $g(x)=x-f/f'$ .
Bisection method — slower but guaranteed; often combined with NR (safeguarded Newton).
Roots of polynomials — common application domain.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Newton-Raphson ka idea bahut simple hai. Tumhe $f(x)=0$ solve karna hai par algebra se nahi ho raha. Toh trick yeh hai: kisi bhi smooth curve ko zoom karke dekho toh woh apni tangent line jaisi dikhti hai. Straight line ka root nikalna trivial hai — bas dekho woh $x$ -axis ko kahan kaatti hai. Wahi tumhara next guess ban jaata hai. Phir wahan se nayi tangent, naya jump. Har baar tum root ke kaafi paas aate jaate ho.

Formula hai $x_{n+1} = x_n - f(x_n)/f'(x_n)$ . Yaad rakhne ka mantra: "New = Old minus Height-over-Slope". $f(x_n)$ tumhari current height hai (kitne upar/neeche ho zero se), $f'(x_n)$ slope hai. Minus sign zaroori hai — tum overshoot ko subtract karte ho, add nahi. Sign galat kiya toh root ke door bhaag jaoge.

Sabse mast baat: yeh method quadratic convergence deta hai (simple root par). Matlab correct digits har step mein roughly double ho jaate hain. $\sqrt2$ wale example mein dekha — $x_2=1.41667$ mein 3 correct digit, phir $x_3=1.41421568$ mein 6 correct digit (3 se 6, double!). Bohot fast! Taylor series se yeh samajh aata hai: jo error term hum drop karte hain woh error ka square hota hai, isliye agla error chhota chhota square hota jaata hai.

Par savdhaan: yeh local method hai. Agar starting guess kharaab hai, ya $f'(x_n)$ zero ke paas hai (flat tangent), toh iteration cycle kar sakti hai ya udd sakti hai — humne $x^3-2x+2$ wale example mein dekha jahan $0\to1\to0$ loop ban gaya. Aur double root par speed quadratic se sirf linear ho jaati hai. Toh good initial guess do, $f'$ ko check karo, aur tab Newton-Raphson tumhara sabse fast dost hai.

What is the method?

Deriving it from scratch (tangent-line argument)

Alternative derivation (Taylor series — shows why it's so fast)

Worked Example 1 — compute $\sqrt{2}$

Worked Example 2 — a transcendental root

Worked Example 3 — when it MISBEHAVES

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Calculus I — Limits & Derivatives

Connections