maths2u
PhysicsMathsChemistryBiology
Tier
⌕ Search ⌘K
Theorem

Convergence of Newton's method

T-115Home MU-308Threads change
Statement

Let \( f : I \to \mathbb{R} \) be a function on an open interval \( I \subseteq \mathbb{R} \), and suppose \( f \in C^2(I) \). Let \( \alpha \in I \) be a simple root of \( f \), i.e. \( f(\alpha) = 0 \) and \( f'(\alpha) \neq 0 \). Define the Newton iteration \[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}, \qquad n = 0, 1, 2, \dots \] Then there exists \( \delta \gt 0 \) such that for every \( x_0 \in (\alpha - \delta, \alpha + \delta) \) the sequence \( (x_n) \) is well-defined (i.e. \( f'(x_n) \neq 0 \) for all \( n \)), remains in \( I \), converges to \( \alpha \), and satisfies, for some constant \( M \gt 0 \) independent of \( n \), \[ |x_{n+1} - \alpha| \leq M |x_n - \alpha|^2 \quad \text{for all } n \geq 0, \] i.e. the convergence is (at least) quadratic. If in addition \( f \in C^3(I) \) and \( f''(\alpha) \neq 0 \), the order of convergence is exactly \( 2 \), with asymptotic error constant \[ \lim_{n \to \infty} \frac{x_{n+1} - \alpha}{(x_n - \alpha)^2} = \frac{f''(\alpha)}{2 f'(\alpha)}. \]

Why it matters

Newton's method is the archetype of a self-correcting iterative scheme: once you are close enough to a root, the number of correct decimal digits roughly doubles at every step, which is spectacularly faster than the linear convergence of bisection or the fixed-point iteration \( x_{n+1} = g(x_n) \) with \( |g'(\alpha)| \in (0,1) \). This theorem is the theoretical justification for why Newton-type methods dominate numerical root-finding, nonlinear least squares, interior-point optimisation, and implicit ODE solvers — anywhere a nonlinear equation must be solved to machine precision cheaply.

It also illustrates a recurring pattern in numerical analysis: local convergence results trade a strong hypothesis (a good starting guess) for a strong conclusion (quadratic rate), and the proof mechanism — bounding the iteration map's derivative near the fixed point — is the same mechanism used throughout fixed-point theory.

Hypotheses
\( f \in C^2(I) \) near \( \alpha \). Counterexample: take \( f(x) = x|x| \), which is \( C^1 \) but not \( C^2 \) at \( \alpha = 0 \) (its second derivative doesn't exist there). Newton's method still converges here, but the standard quadratic bound below cannot be derived from a Taylor expansion with Lagrange remainder because that remainder needs \( f'' \) to exist and be bounded near \( \alpha \); with only Lipschitz \( f' \) one recovers quadratic convergence via a weaker argument, but with less regularity than that (e.g. \( f' \) merely continuous) linear or no guaranteed rate can occur. \( \alpha \) is a simple root: \( f'(\alpha) \neq 0 \). Counterexample: \( f(x) = x^2 \) at \( \alpha = 0 \). Here \( f'(0) = 0 \), the iteration becomes \( x_{n+1} = x_n - \frac{x_n^2}{2x_n} = \frac{x_n}{2} \), and one gets only linear convergence with rate \( \frac12 \), not quadratic — the theorem's conclusion genuinely fails, it does not merely become harder to prove. \( x_0 \) sufficiently close to \( \alpha \) (local hypothesis). Counterexample: for \( f(x) = \arctan(x) \) (root at \( 0 \), simple), starting far enough away — e.g. \( x_0 \) near \( \pm 1.392 \dots \) — the iteration enters a stable 2-cycle and never converges to \( 0 \) at all; quadratic convergence is only a local guarantee, and no global basin-of-attraction statement is asserted. \( f'' \) bounded on a neighbourhood of \( \alpha \) (built into \( f \in C^2(I) \), \( I \) open). If \( f'' \) is unbounded arbitrarily close to \( \alpha \) — e.g. \( f(x) = x + x^{7/3}\sin(1/x) \) suitably regularised at \(0\) so that \(f\) stays \(C^1\) but \(f''\) oscillates unboundedly near the root — the Lagrange-remainder bound used in Step 4 of the proof has no uniform constant \(M\), and quadratic convergence can degrade to a merely superlinear rate.
Proof
1
Since \( f'(\alpha) \neq 0 \) and \( f' \) is continuous on \( I \) (as \( f \in C^2(I) \subseteq C^1(I) \)), there exists \( \delta_1 \gt 0 \) with \( [\alpha - \delta_1, \alpha + \delta_1] \subseteq I \) and \( f'(x) \neq 0 \) for all \( x \in [\alpha - \delta_1, \alpha + \delta_1] \).
Continuity of \( f' \) plus \( f'(\alpha) \neq 0 \): the sign-preserving property of continuous functions gives a neighbourhood on which \( f' \) stays away from \( 0 \) (take \( \delta_1 \) so small that \( |f'(x) - f'(\alpha)| \lt |f'(\alpha)|/2 \) on the interval, by continuity at \( \alpha \)). A
2
On \( [\alpha-\delta_1,\alpha+\delta_1] \), \( f' \) is continuous and nonvanishing, and \( f'' \) is continuous (hence bounded on this compact interval, by the extreme value theorem); set \[ m = \min_{|x-\alpha|\leq \delta_1} |f'(x)| \gt 0, \qquad K = \max_{|x-\alpha|\leq \delta_1} |f''(x)|. \]
Extreme value theorem applied to the continuous functions \( |f'| \) and \( |f''| \) on the compact set \( [\alpha-\delta_1,\alpha+\delta_1] \); \( m \gt 0 \) because \( f'\) is nonvanishing there by Step 1. A
3
For any \( x \in [\alpha-\delta_1,\alpha+\delta_1] \) with \( f'(x) \neq 0 \), define the Newton map \( N(x) = x - \dfrac{f(x)}{f'(x)} \). Then \[ N(x) - \alpha = x - \alpha - \frac{f(x) - f(\alpha)}{f'(x)} = \frac{f'(x)(x-\alpha) - \big(f(x)-f(\alpha)\big)}{f'(x)}. \]
Algebraic rearrangement, using \( f(\alpha) = 0 \) to insert it into the numerator; purely definitional manipulation of \( N \). A
4
By Taylor's theorem with Lagrange remainder applied to \( f \) about the point \( x \) (valid since \( f \in C^2 \)), there exists \( \xi \) strictly between \( x \) and \( \alpha \) with \[ f(\alpha) = f(x) + f'(x)(\alpha - x) + \tfrac12 f''(\xi)(\alpha-x)^2. \] Rearranging: \[ f'(x)(x-\alpha) - \big(f(x)-f(\alpha)\big) = -\tfrac12 f''(\xi)(\alpha - x)^2 = \tfrac12 f''(\xi)(x-\alpha)^2. \]
Taylor's theorem with Lagrange remainder (mean value form) requires \( f \) twice differentiable on the interval spanned by \( x,\alpha \), which holds since \( x,\alpha \in [\alpha-\delta_1,\alpha+\delta_1] \subseteq I \) and \( f \in C^2(I) \). This is the crux where the hypothesis \( f \in C^2 \) is consumed. C
5
Combining Steps 3 and 4: \[ N(x) - \alpha = \frac{f''(\xi)}{2f'(x)}(x-\alpha)^2, \quad\text{so}\quad |N(x)-\alpha| \leq \frac{K}{2m}(x-\alpha)^2 \] for all \( x \in [\alpha-\delta_1,\alpha+\delta_1] \), using the bounds \( |f''(\xi)| \leq K \) (as \( \xi \) also lies in \( [\alpha-\delta_1,\alpha+\delta_1] \) by the intermediate-value placement of \( \xi \)) and \( |f'(x)| \geq m \) from Step 2.
Direct substitution and the triangle-inequality bound \( |a/b| \leq |a|/m \) when \( |b|\geq m \); \( \xi\) lies between \(x\) and \(\alpha\), both in the interval, so \(\xi\) is too, justifying the use of \(K\). B
6
Set \( M = \dfrac{K}{2m} \) and choose \( \delta = \min\!\left(\delta_1,\ \dfrac{1}{2M}\right) \) (if \( M = 0 \), i.e. \( f'' \equiv 0 \) on the interval, take \( \delta = \delta_1 \); the bound below then reads \(|x_{n+1}-\alpha| \le 0\), an even stronger conclusion). For \( x_0 \in (\alpha-\delta,\alpha+\delta) \), Step 5 gives \[ |N(x_0) - \alpha| \leq M|x_0-\alpha|^2 = M|x_0-\alpha|\cdot|x_0-\alpha| \lt M\cdot\frac{1}{2M}\cdot\delta = \tfrac12 \delta \lt \delta. \]
Choosing \( \delta \) small enough that \( M\delta \lt \tfrac12 \) makes the map \( N \) a self-map of \( (\alpha-\delta,\alpha+\delta) \): this is the standard trick for turning a local quadratic bound into an invariant, shrinking neighbourhood. B
7
By induction: if \( x_n \in (\alpha-\delta,\alpha+\delta) \) then \( f'(x_n) \neq 0 \) (Step 1), so \( x_{n+1}=N(x_n) \) is well-defined, and by Step 6, \( x_{n+1} \in (\alpha-\delta,\alpha+\delta) \) also, with \[ |x_{n+1}-\alpha| \leq M|x_n-\alpha|^2. \] Since \( x_0 \in (\alpha-\delta,\alpha+\delta) \) by assumption, the whole sequence \( (x_n) \) is well-defined and stays in \( (\alpha-\delta,\alpha+\delta) \subseteq I \), and the quadratic bound holds for every \( n \geq 0 \).
Mathematical induction on \( n \), base case \( x_0\) given, inductive step is exactly Step 6 applied to \(x_n\) in place of \(x_0\) (the argument in Step 6 used only that \(x_0\) lies in the interval, so it applies verbatim to any \(x_n\) in the interval). A
8
Let \( e_n = |x_n - \alpha| \). Then \( e_{n+1} \leq M e_n^2 \), so \( M e_{n+1} \leq (Me_n)^2 \), and by induction \( M e_n \leq (Me_0)^{2^n} \). Since \( e_0 \lt \delta \leq \frac{1}{2M} \) (when \(M\gt0\)), \( Me_0 \lt \tfrac12 \), so \( (Me_0)^{2^n} \to 0 \) as \( n \to \infty \); hence \( e_n \to 0 \), i.e. \( x_n \to \alpha \).
Iterating the recursive inequality \(e_{n+1}\le Me_n^2\) (a standard "doubling exponent" estimate for quadratically convergent sequences) and using \(0 \le Me_0 \lt 1\) so that the geometric-in-the-exponent sequence \((Me_0)^{2^n}\) tends to \(0\). B
9
For the exact order-2 claim: assume additionally \( f \in C^3(I) \) and \( f''(\alpha) \neq 0 \). From Step 5's identity (before bounding), \[ \frac{x_{n+1}-\alpha}{(x_n-\alpha)^2} = \frac{f''(\xi_n)}{2f'(x_n)}, \] where \( \xi_n \) lies between \( x_n \) and \( \alpha \). As \( n \to \infty \), \( x_n \to \alpha \) (Step 8) forces \( \xi_n \to \alpha \) too (squeeze), and by continuity of \( f'' \) and \( f' \) (using \(f \in C^3 \subseteq C^2\), and \(f'\) continuous with \(f'(\alpha)\neq0\)), \[ \lim_{n\to\infty}\frac{x_{n+1}-\alpha}{(x_n-\alpha)^2} = \frac{f''(\alpha)}{2f'(\alpha)} \neq 0, \] which is precisely the definition of convergence of exact order \(2\) (a finite nonzero asymptotic error constant).
Continuity of \(f''\) and \(f'\) at \(\alpha\) together with the squeeze theorem for \(\xi_n\); the nonvanishing of the limit uses \(f''(\alpha)\neq0\) and \(f'(\alpha)\neq0\), which is exactly why order strictly greater than 2 is excluded when \(f''(\alpha)\neq0\) — the error constant does not degenerate to \(0\). C
Result
x_0 \text{ near a simple root } \alpha \ \Longrightarrow\ |x_{n+1}-\alpha| \leq M|x_n-\alpha|^2, \quad x_n \to \alpha

Reading. If you start Newton's method close enough to a root where the derivative is nonzero, the iterates converge to that root, and the error at each step is bounded by a constant times the square of the previous error — informally, the number of correct digits roughly doubles every iteration once you're close.

Scope. This is a strictly local result: it says nothing about which starting points lead to convergence at all (the basin of attraction can be a complicated fractal set, cf. Newton fractals for complex polynomials), and it requires a simple root and \(C^2\) regularity. It does not apply as stated to multiple roots, to systems of equations without modification (though a vector analogue holds via the Jacobian, using the same Taylor-remainder mechanism), or to points where \(f'\) vanishes anywhere in the relevant neighbourhood.

Corollaries & converses
  • Corollary (digit-doubling). If \( Me_n \leq 10^{-k} \) then \( Me_{n+1} \leq 10^{-2k} \): the number of accurate digits (relative to the scale set by \(M\)) at least doubles each step once the iteration is in the quadratic regime.
  • Corollary (finite basin radius bound). Any \( \delta \) satisfying \( \delta \leq \delta_1 \) and \( M\delta \lt 1 \) (as constructed in Step 6) certifies quadratic convergence from every \(x_0\) in \((\alpha-\delta,\alpha+\delta)\); this gives a computable, if often pessimistic, radius of guaranteed convergence.
  • Corollary (Newton–Kantorovich, stated without proof here). An analogous quantitative local convergence theorem holds for systems \(F:\mathbb{R}^n\to\mathbb{R}^n\), replacing \(f'(\alpha)\neq0\) by invertibility of the Jacobian \(DF(\alpha)\), with the same Taylor-remainder mechanism generalised via a Lipschitz bound on \(DF\).
  • Converse fails. The converse — "quadratic convergence of some root-finding iteration implies it is (asymptotically) Newton's method" — is false in general: many iterations (e.g. Halley's method restricted to certain degenerate cases, or ad hoc modified schemes) can exhibit quadratic convergence to a root without coinciding with Newton's iteration; quadratic order is a rate property, not a characterisation of the specific map.
  • Not conversely true that closeness is necessary in a fixed quantitative sense. The theorem only guarantees some \(\delta \gt 0\) exists; it does not assert that every \(x_0\) outside a particular computed \(\delta\)-ball fails to converge — often the true basin of attraction is much larger than any \(\delta\) produced by this proof's bookkeeping.
Fails without
  • Simple root dropped: \( f(x) = x^2 \), \( \alpha = 0 \). Newton's iteration reduces to \( x_{n+1} = x_n/2 \), giving only linear convergence with rate \( \tfrac12 \), for every choice of \( x_0 \neq 0 \) — the quadratic bound \( |x_{n+1}| \leq M x_n^2 \) is false for any fixed \(M\) once \(x_n\) is small enough that \(x_n \gt 1/(2M)\)... more directly, \(x_{n+1}/x_n^2 = 1/(2x_n) \to \infty\), so no finite \(M\) works near \(0\).
  • \(C^2\) regularity dropped: \( f(x) = x + 2x^2\sin(1/x) \) for \(x\neq0\), \(f(0)=0\), modified/truncated near \(0\) so that \(f\) is differentiable with \(f'(0)=1\neq0\) but \(f'\) fails to be continuous at \(0\) (a classic pathological differentiable-but-not-\(C^1\) construction). Then \(f'\) oscillates through \(0\) infinitely often near the root, so the "nonvanishing of \(f'\) on a neighbourhood" step (Step 1) fails outright, and Newton's iteration can fail to converge, or converge only erratically, for starting points arbitrarily close to \(0\).
  • Local hypothesis (closeness of \(x_0\)) dropped: \( f(x) = \arctan x \), root \( \alpha = 0\), simple, \(f \in C^\infty\). Starting from \( x_0 \approx 1.3917\ldots \) (a known unstable-cycle threshold), the iteration enters a periodic 2-cycle and never converges to \(0\); for \(|x_0|\) even larger, iterates diverge to \(\pm\infty\). Quadratic convergence is real once you're in the basin, but the theorem asserts nothing about starting points outside it.
Common errors
  • Believing Newton's method is globally quadratically convergent for any \(C^2\) function from any starting point — the theorem is purely local; global behaviour requires separate analysis (e.g. convexity arguments, or a global Newton–Kantorovich bound).
  • Applying the quadratic-rate conclusion at a multiple root without checking \(f'(\alpha)\neq0\) first — students often quote "Newton is quadratic" reflexively even when \(f(x)=(x-\alpha)^2 g(x)\) with \(g(\alpha)\neq0\), where the true rate is linear with constant \(\tfrac12\) (or, with the modified iteration \(x_{n+1}=x_n - m\,f(x_n)/f'(x_n)\) for known multiplicity \(m\), quadratic can be restored — but that is a different, modified method).
  • Confusing the error \(|x_n-\alpha|\) with the residual \(|f(x_n)|\): these have the same convergence order under the theorem's hypotheses (since \(f'(\alpha)\neq0\) makes them comparable near \(\alpha\)), but numerically they behave differently and a small residual does not by itself certify a small error, especially for ill-conditioned \(f\).
  • Treating the constant \(M\) from the proof (built from \(K/2m\)) as sharp or as the actual observed error constant — the true asymptotic constant is \(f''(\alpha)/(2f'(\alpha))\) (Step 9), which can be much smaller than the crude worst-case \(M = K/(2m)\) from the compactness argument.
  • Forgetting to check \(f'(x_n)\neq 0\) is only guaranteed inside the constructed neighbourhood \((\alpha-\delta,\alpha+\delta)\); if a computed iterate accidentally leaves this neighbourhood (e.g. due to a poor initial guess or rounding), the next Newton step can divide by a near-zero derivative and blow up, even though "the theorem's hypotheses held at \(x_0\)".
Discussion

Newton's method predates its modern convergence theory by centuries: Newton (1669) and Raphson (1690) developed the algebraic iteration for polynomials, but the clean quadratic-convergence estimate via Taylor's theorem is a much later, 19th–20th century, rigorous packaging of the idea — Cauchy's work on iterative methods and later numerical analysts (e.g. Fourier, and in the 20th century Kantorovich, whose 1948–1950s theorem gives a fully quantitative, non-asymptotic version requiring no prior knowledge of \(\alpha\)) put it on firm footing. The proof given here is the "local" version, assuming a root already exists near \(x_0\); the Newton–Kantorovich theorem instead gives sufficient conditions on \(f\) and \(x_0\) alone (no prior knowledge of \(\alpha\)) that simultaneously guarantee existence of a root and quadratic convergence to it.

The mechanism of proof — express the iteration map's deviation from the fixed point as (essentially) the second-order Taylor remainder — is a special case of a much more general principle: for a fixed-point iteration \(x_{n+1}=g(x_n)\) with \(g(\alpha)=\alpha\), the order of convergence equals the order of the first nonvanishing derivative of \(g\) at \(\alpha\). Newton's map \(N(x) = x - f(x)/f'(x)\) satisfies \(N'(\alpha) = 0\) exactly when \(f'(\alpha)\neq0\) (a short computation from the quotient rule), which is the deeper reason quadratic convergence appears: Newton's method is precisely the fixed-point iteration engineered to kill the linear term.

This connects Newton's method to the broader family of higher-order root-finders (Halley's method, third order; general Householder methods, order \(k\)) which are constructed by killing successively more derivatives of the iteration map at \(\alpha\), at the cost of needing more derivatives of \(f\) per step — illustrating a recurring efficiency trade-off in numerical analysis between per-step cost and asymptotic rate.

A subtlety worth flagging: quadratic convergence is an asymptotic statement, and the neighbourhood \(\delta\) for which it kicks in can be extremely small relative to floating-point precision or the scale of the problem, so that in finite-precision arithmetic one can observe several iterations of merely linear-looking behaviour before the asymptotic regime "switches on" — the theorem guarantees the rate eventually, not from the first step, and pairing it with a global convergence safeguard (e.g. a damped or bisection-hybrid Newton method) is standard engineering practice precisely because of this gap between asymptotic and observed behaviour. Common misconception: that "quadratic convergence" means the error is squared at every step from the very first iteration — it is only an eventual, asymptotic bound once \(x_n\) is inside the basin identified by the proof.

Worked examples
1
Find \( \sqrt{2} \) via Newton's method applied to \( f(x) = x^2 - 2 \), and verify quadratic convergence numerically. Here \( f'(x) = 2x \), and at \( \alpha = \sqrt2 \), \( f'(\alpha) = 2\sqrt2 \neq 0 \): a simple root, and \( f \in C^\infty \), so the theorem applies.
Checking the hypotheses of the theorem before using it: \(f\in C^2\) trivially (polynomial), simple root confirmed by \(f'(\sqrt2)\neq0\). A
2
The iteration is \( x_{n+1} = x_n - \dfrac{x_n^2-2}{2x_n} = \dfrac12\left(x_n + \dfrac{2}{x_n}\right) \) (the classical Babylonian/Heron method). Take \( x_0 = 1.5 \).
Direct substitution of \(f,f'\) into the Newton formula. A
3
Compute: \( x_1 = \tfrac12(1.5 + 2/1.5) = 1.41\overline{6} \); \( x_2 = \tfrac12(1.41\overline6 + 2/1.41\overline6) \approx 1.414215686 \); \( x_3 \approx 1.414213562373095 \). Since \( \sqrt2 = 1.414213562373095\ldots \), the errors are \(e_0\approx0.0858\), \(e_1\approx0.00245\), \(e_2\approx2.1\times10^{-6}\), \(e_3\approx4.5\times10^{-12}\).
Direct numerical iteration; note the number of correct digits: \(1,\,2,\,5,\,11\) — roughly doubling, matching the theorem's guaranteed rate \(e_{n+1}\le Me_n^2\). A
4
By Step 9 of the proof, the asymptotic constant should be \( \dfrac{f''(\alpha)}{2f'(\alpha)} = \dfrac{2}{2\cdot2\sqrt2} = \dfrac{1}{2\sqrt2} \approx 0.3536 \). Check: \( e_2/e_1^2 \approx 2.1\times10^{-6}/(0.00245)^2 \approx 0.35 \). Matches to two significant figures.
Verifying the theoretical asymptotic constant from Step 9 against the observed ratio \(e_{n+1}/e_n^2\), confirming order exactly \(2\) (not higher, not lower). B
x_n \to \sqrt2, \quad \text{correct digits double each step, matching } M \approx \tfrac{1}{2\sqrt2}
1
Consider \( f(x) = e^x - 2 \), whose unique root is \( \alpha = \ln 2 \approx 0.693147 \). Here \( f'(x) = e^x \), so \( f'(\alpha) = 2 \neq 0 \): simple root, \(f\in C^\infty\), theorem applies with basin radius to be estimated.
Hypothesis check as in Example 1; here we additionally use the theorem's Step 6 construction to get an explicit, if crude, guaranteed radius \(\delta\). A
2
On \( J = [\alpha - 0.5, \alpha+0.5] \approx [0.193, 1.193] \): \( f'(x) = e^x \in [e^{0.193}, e^{1.193}] \approx [1.213, 3.297] \), so \( m \approx 1.213 \); \( f''(x) = e^x \) also, so \( K \approx 3.297 \). Thus \( M = K/(2m) \approx 3.297/2.426 \approx 1.359 \).
Applying Steps 1–2 of the proof concretely: computing \(m,K\) as extrema of \(|f'|,|f''|\) on a chosen compact sub-interval around \(\alpha\). B
3
Step 6 requires \( \delta \leq \min(0.5,\, 1/(2M)) = \min(0.5,\ 0.368) = 0.368 \). So the proof certifies quadratic convergence for any \( x_0 \in (\alpha-0.368,\ \alpha+0.368) \approx (0.325,\ 1.061) \).
Direct application of the explicit \(\delta\)-formula constructed in Step 6 of the proof to this concrete \(f\). B
4
Take \( x_0 = 1.0 \in (0.325,1.061) \). Iteration \( x_{n+1} = x_n - (e^{x_n}-2)/e^{x_n} = x_n - 1 + 2e^{-x_n} \): \( x_1 = 1 - 1 + 2e^{-1} \approx 0.735759\); \( x_2 \approx 0.735759 - 1 + 2e^{-0.735759} \approx 0.694039\); \( x_3 \approx 0.693147...\) matching \(\ln2\) to 6+ decimal places. Errors \(e_0\approx0.3069\), \(e_1\approx0.0426\), \(e_2\approx0.000892\), \(e_3\lesssim10^{-6}\) — again the digit count roughly doubles, consistent with the certified \(\delta\)-neighbourhood.
Direct numerical computation of the iterates, cross-checked against the guaranteed basin from Step 3. A
x_n \to \ln 2, \quad \text{convergence certified quadratic on } (0.325,\,1.061) \text{ by the explicit proof bound}
Problems
  1. Show directly, without invoking the general theorem, that for \( f(x) = x^2 - a \) (\(a\gt0\)) the Newton iterate satisfies \( x_{n+1} - \sqrt a = \dfrac{(x_n-\sqrt a)^2}{2x_n} \), and deduce quadratic convergence for any \( x_0 \gt 0 \).
    Solution With \(f(x)=x^2-a\), \(f'(x)=2x\), so \(x_{n+1} = x_n - \dfrac{x_n^2-a}{2x_n} = \dfrac{x_n^2+a}{2x_n}\). Then \[x_{n+1}-\sqrt a = \frac{x_n^2+a - 2x_n\sqrt a}{2x_n} = \frac{(x_n-\sqrt a)^2}{2x_n}.\] For \(x_0\gt0\), one checks inductively \(x_n\gt0\) for all \(n\) (since the right side of the recursion, for \(x_n\gt0\), is a positive quantity — in fact \(x_n \geq \sqrt a\) for all \(n\geq1\) by AM-GM, \(\tfrac12(x_n + a/x_n)\ge\sqrt a\)). Hence for \(n\geq1\), \(2x_n \geq 2\sqrt a\), giving \(|x_{n+1}-\sqrt a| \le \dfrac{1}{2\sqrt a}(x_n-\sqrt a)^2\), a direct quadratic bound with \(M=1/(2\sqrt a)\), matching the general theorem's conclusion (this is exactly Worked Example 1 with general \(a\)).
  2. Let \( f(x) = x^3 - x \), with simple roots at \(-1, 0, 1\). Verify the hypotheses of the theorem hold at \( \alpha=1 \), and compute the theorem's asymptotic error constant there.
    Solution \(f\in C^\infty\), \(f'(x)=3x^2-1\), so \(f'(1)=2\neq0\): simple root, hypotheses hold. \(f''(x)=6x\), so \(f''(1)=6\). By Step 9, the asymptotic constant is \(\dfrac{f''(1)}{2f'(1)} = \dfrac{6}{4} = 1.5\). So near \(\alpha=1\), \(x_{n+1}-1 \approx 1.5\,(x_n-1)^2\) once \(n\) is large.
  3. Explain precisely why the theorem's proof breaks down for \( f(x)=x^{4/3} \) at \( \alpha = 0\) (note \(f'(0)=0\) does not even hold in the usual polynomial sense — check differentiability), and determine the actual behaviour of Newton's method here.
    Solution \(f(x)=x^{4/3} = |x|^{4/3}\,\mathrm{sgn}(x)\) is \(C^1\) with \(f'(x) = \tfrac43 x^{1/3}\) (extended continuously, \(f'(0)=0\)), so \(\alpha=0\) is not a simple root: \(f'(0)=0\) fails the theorem's key hypothesis outright (Step 1 cannot even produce a neighbourhood where \(f'\neq0\), since \(f'(0)=0\) itself). Newton's iteration is \(x_{n+1} = x_n - \dfrac{x_n^{4/3}}{\tfrac43 x_n^{1/3}} = x_n\left(1-\tfrac34\right) = \tfrac14 x_n\), giving only linear convergence with rate \(\tfrac14\) — consistent with the general fact (Hypotheses section, root-multiplicity discussion) that non-simple/degenerate roots destroy the quadratic rate.
  4. (Multiple root, modified Newton.) For \(f(x) = (x-2)^2(x+1)\), the root \(\alpha=2\) has multiplicity \(2\). Show plain Newton converges only linearly there, then show that the modified iteration \(x_{n+1} = x_n - 2\,\dfrac{f(x_n)}{f'(x_n)}\) restores quadratic convergence (you may assume, or briefly justify, that near a root of multiplicity \(m\), \(f(x)/f'(x) \approx (x-\alpha)/m\)).
    Solution Near \(\alpha=2\) write \(f(x) = (x-\alpha)^2 h(x)\) with \(h(x)=x+1\), \(h(\alpha)=3\neq0\). Then \(f'(x) = 2(x-\alpha)h(x) + (x-\alpha)^2h'(x) = (x-\alpha)\big[2h(x)+(x-\alpha)h'(x)\big]\), so \[\frac{f(x)}{f'(x)} = \frac{(x-\alpha)h(x)}{2h(x)+(x-\alpha)h'(x)} \xrightarrow[x\to\alpha]{} \frac{(x-\alpha)\cdot h(\alpha)}{2h(\alpha)} = \frac{x-\alpha}{2}\] to leading order (a first-order Taylor expansion of the bracket), matching the general \(m=2\) case \(f(x)/f'(x)\approx (x-\alpha)/m\). Hence plain Newton gives \(x_{n+1}-\alpha \approx (x_n-\alpha) - \tfrac12(x_n-\alpha) = \tfrac12(x_n-\alpha)\): linear convergence, rate \(\tfrac12\), exactly as the multiplicity-\(m\) formula \((m-1)/m\) predicts for \(m=2\). For the modified iteration, \(x_{n+1}-\alpha \approx (x_n-\alpha) - 2\cdot\tfrac12(x_n-\alpha) = 0 + O((x_n-\alpha)^2)\): the leading linear term cancels exactly (because we scaled by the true multiplicity \(m=2\)), leaving a genuinely quadratic remainder, confirming quadratic convergence is restored by this modification — this is the standard trick alluded to in Common Errors.
  5. Using the explicit construction in the proof (Steps 1–6), find concrete constants \(m, K, M\) and a certified radius \(\delta\) for \(f(x) = \sin x\) at the root \(\alpha=\pi\), and check numerically that Newton's method from \(x_0 = \pi - 0.3\) obeys the certified bound for at least the first two iterations.
    Solution \(f(x)=\sin x\), \(f'(x)=\cos x\), \(f''(x)=-\sin x\). At \(\alpha=\pi\): \(f'(\pi)=\cos\pi=-1\neq0\), simple root. On \(J=[\pi-0.5,\pi+0.5]\), \(|\cos x|\) attains its minimum at the endpoints: \(|\cos(\pi\pm0.5)| = |\!-\!\cos(0.5)| = \cos(0.5)\approx0.8776\), so \(m\approx0.8776\); \(|\sin x|\) attains its maximum on \(J\) at the endpoints too (since \(\sin\) is decreasing away from \(\pi/2\) here): \(|\sin(\pi\pm0.5)| = \sin(0.5)\approx0.4794\), so \(K\approx0.4794\). Thus \(M = K/(2m) \approx 0.4794/1.7552 \approx 0.2732\), and \(\delta=\min(0.5,\,1/(2M))=\min(0.5,\,1.830)=0.5\). So the theorem certifies quadratic convergence, with \(|x_{n+1}-\pi|\le 0.2732\,|x_n-\pi|^2\), for any \(x_0\in(\pi-0.5,\pi+0.5)\). Take \(x_0=\pi-0.3\approx2.8416\), so \(e_0=0.3\). Predicted bound: \(e_1 \le 0.2732\times0.09 = 0.02459\). Actual iteration: \(x_1 = x_0 - \sin(x_0)/\cos(x_0) = x_0 - \tan(x_0)\). Numerically \(\tan(2.8416)\approx-0.30934\)... computing directly: \(\sin(2.8416)\approx0.29552\), \(\cos(2.8416)\approx-0.95533\), so \(x_1 = 2.8416 - (0.29552/-0.95533) = 2.8416+0.30934 \approx 3.15094\). Then \(e_1 = |3.15094-\pi|\approx0.00935\), which indeed satisfies \(e_1\approx0.00935 \le 0.02459\), confirming the certified bound. A second step gives \(e_2 \lesssim 0.2732\times(0.00935)^2\approx2.4\times10^{-5}\), consistent with the doubling-digits pattern.