# Workbook 7 — Newton's method by hand
> [!abstract] The problem
> Newton's method refines a root guess along the tangent line: $x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$.
> For $f(x)=x^2-1$ ($f'(x)=2x$) with $x_0=2$: **(a)** write the iteration explicitly, **(b)** compute $x_1,x_2,x_3$ as exact fractions, and **(c)** identify the root and track how fast the error shrinks.
---
## (a) The iteration for this $f$
Substitute $f(x)=x^2-1$ and $f'(x)=2x$:
$x_{n+1} = x_n - \frac{x_n^2-1}{2x_n} = \frac{2x_n^2-(x_n^2-1)}{2x_n} = \frac{x_n^2+1}{2x_n} = \boxed{\tfrac12\!\left(x_n+\frac{1}{x_n}\right)}.$
The Newton step collapses to "**average $x_n$ with $1/x_n$**." (This is the classic [Babylonian](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Heron's_method) square-root iteration; here it is computing $\sqrt{1}=1$.)
## (b) Three steps by hand
$x_1 = \tfrac12\!\left(2+\tfrac12\right) = \frac{5}{4},\qquad
x_2 = \tfrac12\!\left(\tfrac54+\tfrac45\right) = \frac{41}{40},\qquad
x_3 = \tfrac12\!\left(\tfrac{41}{40}+\tfrac{40}{41}\right) = \frac{3281}{3280}.$
Numerically $2 \to 1.25 \to 1.025 \to 1.000305$.
> [!example]- The same, the long way (for checking)
> $x_0=2$: $f=3,\ f'=4$, so $x_1 = 2-\tfrac34 = \tfrac54$.
> $x_1=\tfrac54$: $f=\tfrac{9}{16},\ f'=\tfrac52$, so $x_2 = \tfrac54-\tfrac{9/16}{5/2} = \tfrac54-\tfrac{9}{40} = \tfrac{41}{40}$.
> $x_2=\tfrac{41}{40}$: $f=\tfrac{81}{1600},\ f'=\tfrac{41}{20}$, so $x_3 = \tfrac{41}{40}-\tfrac{81/1600}{41/20} = \tfrac{41}{40}-\tfrac{81}{3280} = \tfrac{3281}{3280}$.
## (c) The root and the rate
The iterates approach the root $\boxed{x^\ast = 1}$ (the positive root of $x^2-1$; the other root $-1$ is on the far side of $x_0=2$). Track the error $e_n=|x_n-1|$:
| $n$ | $x_n$ | $e_n=\lvert x_n-1\rvert$ | $e_n/e_{n-1}^2$ |
|---|---|---|---|
| 0 | $2$ | $1$ | — |
| 1 | $5/4$ | $1/4$ | $0.25$ |
| 2 | $41/40$ | $1/40$ | $0.40$ |
| 3 | $3281/3280$ | $1/3280$ | $0.49$ |
The error roughly **squares** each step (the digit count of accuracy doubles), and $e_n/e_{n-1}^2$ settles toward a constant $\approx\tfrac12$. This is [**quadratic convergence**](https://en.wikipedia.org/wiki/Newton%27s_method#Analysis): near a simple root, $e_{n+1}\approx\dfrac{f''(x^\ast)}{2f'(x^\ast)}\,e_n^2$, and here $\dfrac{f''}{2f'}=\dfrac{2}{2\cdot 2}=\tfrac12$ at $x^\ast=1$.
---
# Sanity checks and context
## Common pitfalls
> [!warning] Watch out for these
> - **Keep exact fractions.** Rounding early hides the clean $\tfrac54,\tfrac{41}{40},\tfrac{3281}{3280}$ pattern and the exact $e_n/e_{n-1}^2$ ratios.
> - **It converges to $1$, not $-1$.** Newton follows the tangent from $x_0=2$ toward the nearer root.
> - **Quadratic $\ne$ "halving."** Each step roughly *squares* the error (doubles the correct digits), far faster than a linear method that only shrinks it by a fixed factor.
## Checkpoint questions
1. Simplify the Newton iteration for $f(x)=x^2-a$. What averaging rule do you get, and what does it compute?
2. Starting from $x_0=2$, how many correct digits does $x_3$ have? Predict $x_4