Back to the on-screen lesson ·
Following the tangent to the axis, the quadratic rate it gives near a simple root, and the three hypotheses that rate depends on.
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 carry out Newton's method step by step, explain why it roughly doubles the correct digits near a simple root, and name the conditions under which it slows down, divides by zero or fails to converge at all.
You can differentiate, you know that the tangent at a point is the best straight line through it, and you have seen that a fixed-point iteration whose derivative vanishes at the fixed point converges unusually fast. Newton's method is the map built to make that derivative vanish.
A root is simple when $f'$ is not zero there, and repeated or multiple when it is. Convergence is quadratic when the new error is proportional to the square of the old one. The correction is $\dfrac{f(x)}{f'(x)}$, the amount the step moves by; the basin of attraction of a root is the set of starting points from which the iterates reach it.
Replace $f$ by its tangent at the current guess and solve that instead: $x_{k+1} = x_k - \dfrac{f(x_k)}{f'(x_k)}$. Read as a fixed-point iteration, the map is $g(x) = x - \dfrac{f}{f'}$, whose derivative is $\dfrac{f f''}{(f')^{2}}$ — and that is zero at a simple root, because $f$ is. The linear term in the error therefore vanishes and the quadratic one takes over: $e_{k+1} \approx \dfrac{f''(r)}{2f'(r)} e_k^{2}$. The number of correct digits roughly doubles each step, so four or five steps take a rough guess to full precision. Every part of that sentence has a condition attached. Simple root: at a double root $f'$ vanishes too, the constant is not finite, and the rate falls to a halving per step. Near: from a distant start the tangent is a poor model and the iterate can be thrown anywhere, including into a cycle. A non-zero slope at the iterate: land on a stationary point and the step divides by zero. A production root finder therefore keeps a bracket and falls back to bisection whenever a Newton step leaves it — speed where the hypotheses hold, safety where they do not.
Another way: picture
Stand on the curve at your guess, lay a straight edge along it, and slide down to where the edge crosses the axis. Where the curve is close to straight you land almost exactly on the root; on a nearly flat part the edge is almost horizontal and flings you a long way off.
Another way: steps
Quadratic convergence is often remembered as a property of Newton's method. It is a property of Newton's method applied to a simple root from a close enough start, and when either condition fails the method still runs, still produces iterates, and still looks as if it is working. A run that is crawling at a double root and a run that is racing at a simple one are indistinguishable from the outside unless the errors themselves are watched — which is why a careful implementation records the ratio of successive corrections.
$f(x) = x^{2} - 2$ gives the step $x - \dfrac{x^{2}-2}{2x} = \dfrac{x}{2} + \dfrac{1}{x}$.
Average the guess with $2$ over the guess.
From $x_0 = 1$: $1.5$, $1.41\overline{6}$, $1.4142157$, then $1.4142136$.
Four steps to seven digits.
The errors are about $0.09$, $0.0025$, $2 \times 10^{-6}$, $10^{-12}$ — each roughly the square of the one before.
This is what quadratic looks like.
$f(x) = \arctan x$ has its only root at $0$ and flattens far out.
The tangent gets almost horizontal.
From $x_0 = 2$ the iterates grow: $-3.5$, $14$, $-279$, and away.
Each tangent overshoots more.
From $x_0 = 1$ they converge quickly. Same function, same method, and the start decides.
Local means local.
$f(1) = -7$ and $f'(x) = 3x^{2}$, so $f'(1) = 3$.
The step is $1 - \dfrac{-7}{3} = \dfrac{10}{3}$.
A long way past the root $2$ — the tangent at $1$ is a poor model, and the next steps will come back.
Newton's method is run on $f(x) = x^{2} - 5$ from $x_0 = 3$. Fill in the value and the slope at each iterate, and the iterate the step produces. Give fractions where the value is not a whole number.
| Iterate | Value of f | Slope there | Next iterate | |
|---|---|---|---|---|
| At the start | 3 | |||
| After one step | 7/3 |
Newton's method has been run $4$ times on a smooth $f$ and the iterates are settling down. Which statement about the method is correct?
Put one step of Newton's method into order, inside a loop allowed at most $26$ iterations.
Number the steps in order (write the number in the box):
Newton's method is started near $6$ in four situations. Match each to what the method does.
| The correct digits roughly double each step | The error is merely halved each step, for two evaluations | The step is undefined, because the correction divides by zero | A cycle: the iterates repeat for ever and approach nothing | |
|---|---|---|---|---|
| A simple root at $6$, started close to it | ||||
| A double root, as in $(x - 6)^{2}$ | ||||
| An iterate landing exactly on a stationary point of $f$ | ||||
| A start from which the iterates return to where they were two steps ago |
Newton's method is applied to $f(x) = (x - 5)^{2}$. Each step multiplies the error by what constant factor? Give a fraction.
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
One step of Newton's method on $f(x) = x^{2} - 26$ from $x_0 = 5$. Give $x_1$, and then $f(x_1)$. Write each as a fraction where it is not a whole number.
$x_1 = $ x1 and $f(x_1) = $ f1
You can run Newton steps, say what the method promises and where, and name its failure modes. Say in your own words why the quadratic rate is a statement about the root as much as about the method.
8. Your turn: one Newton step on $f(x) = x^{3} - 8$ from $x_0 = 1$, step 3