📊 Section 1 — Interactive Simulation
Pick a function and a starting point $x_0$. Watch the tangent line at $(x_n, f(x_n))$ slide down to the $x$-axis, giving the next iterate $x_{n+1} = x_n - f(x_n)/f'(x_n)$. Compare with bisection and the secant method.
Animation
Function Preset
Parameters
Display Options
Tips
• Press ▶ Step for one iteration; ⏩ Auto-run runs until convergence.
• Try x³−2x+2 with $x_0=0$ — Newton enters a 2-cycle and never converges.
• For multiple roots like $(x-1)^2$, convergence drops from quadratic to linear.
💡 Section 2 — The Idea, Step by Step
From a kitchen-table guess to quadratic convergence — the same idea, told three ways.
Start simple: smart guessing
Suppose you want $\sqrt{2}$ and have no calculator. Guess $1.5$. Square it: $1.5^2 = 2.25$ — a little too big, so $1.5$ is an overestimate. That means $2 \div 1.5 = 1.333$ must be an underestimate. The true answer is trapped between them, so just average the two: $(1.5 + 1.333)/2 = 1.4167$. That is already correct to three digits. Average again and you pin it down almost perfectly. Newton-Raphson is exactly this "guess, correct, repeat" instinct — made precise so it works for any equation, not just square roots.
Name the pieces: slide down the tangent
We are hunting for the $x$ where a curve $f(x)$ crosses zero — its root. From a guess $x_n$ we know two things: the height of the curve $f(x_n)$, and how steeply it is rising or falling, the slope $f'(x_n)$. Rather than follow the curved graph, we follow its straight tangent line down to the axis. The spot where that tangent hits zero is our next, better guess: $$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.$$ Try it on $f(x) = x^2 - 2$ (whose root is $\sqrt{2}$) starting from $x_0 = 2$: here $f(2) = 2$ and $f'(2) = 4$, so $x_1 = 2 - 2/4 = 1.5$ — the very same $1.5$ we reached by hand above. The formula simply automated the averaging.
Go deeper: why the digits double
Near a simple root $x^*$ (where $f(x^*) = 0$ but $f'(x^*) \neq 0$), a Taylor expansion shows the error $e_n = x_n - x^*$ obeys $\abs{e_{n+1}} \approx K\,\abs{e_n}^2$, with $K = f''(x^*)/\bigl(2f'(x^*)\bigr)$. Squaring the error every step means the number of correct digits roughly doubles per iteration — that is quadratic convergence, derived in full in the next section. The catch hides in the $f'$ in the denominator: if the slope is zero (a flat tangent, or a multiple root where $f$ and $f'$ vanish together) the method stalls or breaks, and a poor starting guess can make it diverge or fall into a cycle. In this sim the x₀ slider sets the first guess, tolerance ε decides how small $\abs{f}$ must get before it stops, and max iterations caps the runaway cases.
Try this in the sim above
• Choose the preset x³ − 2x + 2 with $x_0 = 0$ and step through: Newton bounces $0 \to 1 \to 0$ forever — a 2-cycle that never converges.
• Pick (x−1)², a multiple root, and watch the error only halve each step instead of squaring — quadratic convergence has degraded to linear.
• Switch to Compare All Three on $x^2 - 2$: Newton reaches machine precision in about 5 steps while bisection crawls. Open the error graph to see the gap.
📐 Section 3 — Method & Convergence Analysis
Derivation from Taylor expansion, conditions for convergence, and the quadratic rate.
Given a differentiable $f:\R\to\R$ and an initial guess $x_0$, define $$x_{n+1} \;=\; x_n - \frac{f(x_n)}{f'(x_n)} \quad (n = 0, 1, 2, \ldots),$$ provided $f'(x_n) \neq 0$. If $f(x^*)=0$, $f'(x^*)\neq 0$, and $x_0$ is sufficiently close to $x^*$, then $x_n \to x^*$ at quadratic rate: $\abs{x_{n+1}-x^*} \le C\abs{x_n - x^*}^2$.
In short: each step roughly squares the error, so the number of correct digits doubles per iteration.
Symbol Table
| Symbol | Meaning | Type |
|---|---|---|
| $f$ | Function whose root is sought | $\R\to\R$, twice differentiable |
| $f'$ | Derivative — slope of tangent at $x_n$ | Real-valued |
| $x_n$ | $n$-th iterate | Real, sequence |
| $x^*$ | Exact root: $f(x^*)=0$ | Real |
| $e_n$ | Error $x_n - x^*$ | Real, $\to 0$ if convergent |
| $p$ | Order of convergence | $\abs{e_{n+1}} \approx K\abs{e_n}^p$ |
| $K$ | Asymptotic error constant | Real, depends on $f''(x^*)/2f'(x^*)$ |
| $\eps$ | Stopping tolerance | Stop when $\abs{f(x_n)}<\eps$ or $\abs{x_n-x_{n-1}}<\eps$ |
Derivation — Geometric and Taylor
Simulation ↔ Symbol Mapping
slider x₀ | initial guess $x_0$ — first point on the curve |
slider tolerance ε | stopping criterion: stop when $\abs{f(x_n)} < \eps$ |
slider max iter | safety cap to prevent infinite loop on divergence |
readout xₙ, xₙ₊₁ | current iterate and Newton's next guess via $x - f(x)/f'(x)$ |
readout error | $\abs{x_n - x^*}$ — how far from the true root |
readout order p | empirical order from $\log\abs{e_{n+1}}/\log\abs{e_n}$ — should be 2 for simple roots |
graph error log | plot of $\log_{10}\abs{e_n}$ vs $n$ — straight line ⇒ linear; quadratic decay shows up as accelerating |
graph basin | colored 1D map: which root each $x_0$ converges to (Newton's fractal in 1D) |
Worked Example — Compute $\sqrt{2}$ via Newton
$f(x) = x^2 - 2$, $f'(x) = 2x$. Newton iteration: $x_{n+1} = x_n - \dfrac{x_n^2 - 2}{2x_n} = \dfrac{x_n + 2/x_n}{2}$ — the famous Babylonian / Heron's method.
Start with $x_0 = 2$.
$x_1 = (2 + 1)/2 = 1.5$, error $\approx 0.0858$ ($\sqrt{2}\approx 1.41421$)
$x_2 = (1.5 + 1.333\overline{3})/2 = 1.41666\overline{6}$, error $\approx 0.00245$
$x_3 = (1.41666\overline{6} + 2/1.41666\overline{6})/2 = 1.4142156862\ldots$, error $\approx 2.12\times 10^{-6}$
$x_4 = 1.41421356237\ldots$, error $\approx 1.6\times 10^{-12}$. Each step roughly squares the error: $0.086 \to 0.00245 \to 2\times 10^{-6} \to 10^{-12}$. $\boxed{\sqrt{2}\approx 1.41421356237.}$
❓ Section 4 — Frequently Asked Questions
Bisection only uses the sign of $f$ — it halves the interval per step, so the error shrinks by exactly $1/2$ each iteration: that's linear convergence. Newton uses the actual value and slope of $f$ at the current point, which is much more information. By Taylor's theorem, the tangent line approximates $f$ to first order, so the residual is $O(e^2)$ — quadratic. Geometrically, each Newton step lands on the tangent's $x$-intercept, which is much closer to the true root than just halving an interval. The cost: Newton requires $f'$ at every step, while bisection just needs $f$.
Key takeaway: bisection halves errors, Newton squares them. Quadratic beats linear once you're close enough.For each starting $x_0$ in a range, it runs Newton until convergence (or max iterations) and colors the pixel by which root it found — or marks it "diverged" / "cycled" in red if it failed. Functions with multiple real roots produce striped, often fractal-looking patterns: small changes in $x_0$ can land you at completely different roots. The boundary between basins is mathematically intricate (in 2D for complex Newton, it's the famous Newton fractal). For $f(x) = x^3 - x$, with roots at $-1, 0, 1$, basins interleave non-trivially: $x_0 = 0.45$ may go to root $0$, but $x_0 = 0.46$ may go to root $1$.
Key takeaway: which root Newton finds depends sensitively on $x_0$; basin boundaries can be fractal.Everywhere a nonlinear equation must be solved. Square root in CPUs: hardware uses Newton or its variant (Goldschmidt) for floating-point sqrt and divide. Optimization: minimizing a function $g$ means solving $g'(x)=0$ — Newton on the gradient gives the (multidim) Newton-Raphson optimizer; in ML this is "second-order optimization", and the BFGS approximation is the workhorse for medium-scale problems. Implicit ODE solvers: backward Euler at each step solves $x_{n+1} - h f(x_{n+1}, t_{n+1}) - x_n = 0$ via Newton. Compiler tricks: fast inverse square root in computer graphics. Statistics: maximum likelihood estimation of GLMs uses Iteratively Reweighted Least Squares — Newton in disguise. Robotics: inverse kinematics solves nonlinear position equations.
Key takeaway: every CPU sqrt, every IRLS regression, every backward-Euler ODE step is Newton-Raphson under the hood.For $f(x) = (x-r)^m$ with multiplicity $m \geq 2$, both $f(r) = 0$ and $f'(r) = 0$. The error recursion derivation in Step 5 had $K = f''(x^*)/(2f'(x^*))$, which becomes $0/0$. Direct analysis shows $e_{n+1} = (1 - 1/m) e_n + O(e_n^2)$ — i.e., linear convergence with rate $1 - 1/m$. For $m=2$, error halves per step (just like bisection). The fix is the modified Newton $x_{n+1} = x_n - m\,f(x_n)/f'(x_n)$ — multiply the correction by $m$. This restores quadratic convergence, but you need to know $m$. Alternatively, apply Newton to $f(x)/f'(x)$ which has only simple roots.
Key takeaway: at multiple roots, both $f$ and $f'$ vanish; Newton degrades to linear unless you multiply the step by the multiplicity.For Newton with quadratic convergence, $\abs{e_{n+1}} \approx K\abs{e_n}^2$. Taking logs: $\log\abs{e_{n+1}} \approx 2\log\abs{e_n} + \log K$. So if $\abs{e_0} = 10^{-1}$ and $K \sim 1$, you get $\abs{e_n} \approx 10^{-2^n}$ — at most 5 iterations to reach machine precision $\sim 10^{-16}$. Bisection needs $\log_2((b-a)/\eps) \approx 50$ iterations for the same precision. Secant method has order $\varphi \approx 1.618$ (golden ratio): $\abs{e_{n+1}} \approx K\abs{e_n}^{1.618}$ — slower than Newton but doesn't need $f'$. So Newton needs typically 5–7 iterations from a decent guess; bisection needs 30–50. The cost per iteration of Newton is one $f$ + one $f'$; bisection needs only one $f$.
Key takeaway: Newton ≈ 5 iterations, Secant ≈ 8, Bisection ≈ 50 to reach machine precision. Newton wins on count, not always on cost.For $\mathbf{F}: \R^n \to \R^n$ with Jacobian $J(\mathbf{x})$, Newton-Raphson is $\mathbf{x}_{n+1} = \mathbf{x}_n - J(\mathbf{x}_n)^{-1}\mathbf{F}(\mathbf{x}_n)$. To solve a system $\mathbf{F}(\mathbf{x})=\mathbf{0}$, you solve a linear system $J\Delta\mathbf{x} = -\mathbf{F}$ at each step — that's where most of the cost goes. For minimization of $g:\R^n\to\R$, set $\mathbf{F} = \nabla g$ — its Jacobian is the Hessian $H = \nabla^2 g$. So Newton's method for optimization is $\mathbf{x}_{n+1} = \mathbf{x}_n - H^{-1}\nabla g$ — solve a linear system involving the Hessian per step. Quasi-Newton methods (BFGS, L-BFGS) approximate $H^{-1}$ from gradient differences, avoiding the cost of Hessian computation. This is the foundation of unconstrained optimization in scientific computing and ML.
Key takeaway: multidim Newton = solve $J\Delta x = -F$. Apply to $\nabla g = 0$, you get the second-order optimizer at the heart of BFGS, Gauss-Newton, Levenberg-Marquardt.Newton's method is a fixed-point iteration. Define $g(x) = x - f(x)/f'(x)$. Then Newton is $x_{n+1} = g(x_n)$, and the fixed point of $g$ is the root of $f$ (since $g(x) = x \iff f(x) = 0$). The general theory of fixed-point iterations says: $x_n \to x^*$ if $x^*$ is an attracting fixed point, i.e.\ $\abs{g'(x^*)} < 1$. Compute $g'(x) = f(x)f''(x)/f'(x)^2$ — at the root $x^*$, $f(x^*)=0$, so $g'(x^*) = 0$. That zero derivative is exactly what gives quadratic convergence — fixed points with $g'(x^*)=0$ converge quadratically (this is a general fact). So Newton's quadratic rate isn't magic; it's the special case where the fixed-point iteration's derivative vanishes at the root.
Key takeaway: Newton = fixed-point iteration of $g(x) = x - f/f'$, designed so $g'(x^*) = 0$ — that's why it's quadratic.