Back to the on-screen lesson ·
Why a vanishing $g'$ at a simple root gives quadratic convergence, what the asymptotic constant is made of, and why a repeated root turns the method into bisection at greater cost.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to derive the quadratic rate of Newton's method from a Taylor expansion, name its asymptotic constant, say which hypothesis fails at a repeated root, compute the linear rate that results, and design the modified step that repairs it.
You can run Newton's method and you know it doubles the correct digits near a root. You also know the contraction theorem, which says a fixed-point iteration converges at rate $|g'(p)|$. Newton's method is a fixed-point iteration, and putting those two facts together is this lesson.
A root $r$ is simple when $f(r) = 0$ and $f'(r) \ne 0$, and has multiplicity $m$ when $f(x) = (x - r)^{m}h(x)$ with $h(r) \ne 0$. The asymptotic constant of a quadratic method is the $C$ in $|e_{n+1}| \approx C|e_n|^{2}$. The modified Newton step multiplies the ordinary one by the multiplicity.
Newton's method is the fixed-point iteration for $g(x) = x - \dfrac{f(x)}{f'(x)}$, and the quotient rule gives $g'(x) = \dfrac{f(x)f''(x)}{f'(x)^{2}}$. At a simple root the numerator vanishes and the denominator does not, so $g'(r) = 0$: the linear term of the convergence is not small, it is absent, and the next term of the Taylor expansion takes over. Expanding properly gives the sharp statement
$$e_{n+1} = \frac{f''(\xi)}{2f'(x_n)}\,e_n^{2} \;\longrightarrow\; \left|\frac{f''(r)}{2f'(r)}\right| e_n^{2},$$
so the order is two and the constant belongs to the function — large when a sharply bending curve crosses shallowly, which is the same geometry that makes the root ill conditioned. Every hypothesis in that derivation earns its place: $f''$ continuous supplies the remainder, $f'(r) \ne 0$ permits the division, and starting close enough is what keeps the constant bounded. Take away the simple root and the argument collapses in a specific way. At multiplicity $m$, $\dfrac{f}{f'} \approx \dfrac{x - r}{m}$, so each step removes only a fraction $\dfrac1m$ of the error and the method is linear with rate $1 - \dfrac1m$ — rate $\tfrac12$ at a double root, the same as bisection, for a great deal more work per step. Multiplying the step by $m$ restores the cancellation and the quadratic rate.
Another way: steps
Another way: picture
Draw the tangent at an iterate and follow it to the axis. At a simple root the curve pulls away from its tangent quadratically, and the gap between where the tangent lands and where the root is is that quadratic gap — which is the whole theorem in one picture. At a double root the curve touches the axis instead of crossing it; the tangent at a nearby point is nearly horizontal near the root and lands only halfway there, every time.
Quadratic convergence is quoted as a property of Newton's method rather than as the conclusion of a theorem with three hypotheses, and a slow run is then blamed on the implementation. The signature of a repeated root is a steady rate: the error falling by the same factor every step, indefinitely, with the residual falling too. Nothing looks broken, and nothing is — the hypothesis simply does not hold, and no amount of care in the code will make it.
$f(x) = x^{2} - 2$ at $r = \sqrt2$: $f'' = 2$, $f' = 2\sqrt2$, so $C = \dfrac{2}{2 \cdot 2\sqrt2} \approx 0.354$.
The constant from the function.
From $e_0 = 0.1$: $e_1 \approx 0.0035$, $e_2 \approx 4 \times 10^{-6}$, $e_3 \approx 6 \times 10^{-12}$.
Digits doubling.
$f(x) = (x - 3)^{2}$: the Newton step is $x - \tfrac{x - 3}{2}$, so $e_{n+1} = \tfrac12 e_n$.
Linear, rate a half.
The modified step doubles it: $x - 2\cdot\tfrac{x-3}{2} = 3$.
The root, in one step, from anywhere.
The root at $0$ has multiplicity $3$.
The rate is $1 - \tfrac13 = \tfrac23$.
Check it directly: the step is $x - \dfrac{x^{3}}{3x^{2}} = \tfrac23 x$, so the error really is multiplied by $\tfrac23$ every time.
Newton's method is the fixed-point iteration for $g(x) = x - \dfrac{f(x)}{f'(x)}$. At a simple root $r$ of $f$, what is $g'(r)$?
Answer:
Newton's method satisfies $e_{n+1} = 3\,e_n^{2}$ near a root, and the current error is $\dfrac{1}{13}$. Give the error after each of the next two steps, as a fraction.
| Steps taken | Error | |
|---|---|---|
| After one step | 1 | |
| After two steps | 2 |
Build the Taylor argument that Newton's method converges quadratically at a simple root.
This task has no paper form; do it on a device.
Newton's method is applied to $f(x) = (x - 6)^{2}$, whose root at $6$ is double. What happens?
A root has multiplicity $5$, and the modified step $x_{n+1} = x_n - c\,\dfrac{f(x_n)}{f'(x_n)}$ is used. Which constant $c$ restores the fast convergence, and what order does it restore?
Take $c = $ w, and the order returns to z.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Newton's method at a root of multiplicity $m$ converges linearly with rate $1 - \tfrac{1}{m}$. Match each multiplicity to what that gives.
| Rate zero, meaning quadratic rather than linear | Linear, halving the error each step | Linear, keeping two thirds of the error each step | Linear, keeping nine tenths: about a digit every twenty-two steps | |
|---|---|---|---|---|
| A simple root | ||||
| A double root | ||||
| A triple root | ||||
| A root of multiplicity ten |
You can derive and state the order of Newton's method and what a repeated root does to it. Say in your own words why quadratic convergence is not a property of the method alone.
8. Your turn: the rate of Newton's method on $f(x) = x^{3}$, step 3