Root Finding — Open Methods

Newton-Raphson Method

Newton-Raphson finds a root by iterating x_{n+1}=x_n-f(x_n)/f'(x_n). Apply to f(x)=cos(x)-x from x0=1: converges to the Dottie number 0.739085 in 3 steps.

Example

Use tangent-line updates to approach the root.

highlighted = computed this step

Step 1 — Set up

Start Newton's method from x 0 equals 1.

f(x)=cos⁡x−xx0=1f(x)= \cos x-x \quad x_{ 0 }= 1

Step 2 — Newton iteration 1

Add Newton iteration 1 to the table.

nx nff primex next11.000000−0.459698−1.8414710.750364\begin{array}{ccccc}\text{n} & \text{x n} & \text{f} & \text{f prime} & \text{x next} \\ \hlmath{1} & \hlmath{1.000000} & \hlmath{-0.459698} & \hlmath{-1.841471} & \hlmath{0.750364}\end{array}

Step 3 — Newton iteration 2

Add Newton iteration 2 to the table.

nx nff primex next11.000000−0.459698−1.8414710.75036420.750364−0.018923−1.6819050.739113\begin{array}{ccccc}\text{n} & \text{x n} & \text{f} & \text{f prime} & \text{x next} \\ 1 & 1.000000 & -0.459698 & -1.841471 & 0.750364 \\ \hlmath{2} & \hlmath{0.750364} & \hlmath{-0.018923} & \hlmath{-1.681905} & \hlmath{0.739113}\end{array}

Step 4 — Newton iteration 3

Add Newton iteration 3 to the table.

nx nff primex next11.000000−0.459698−1.8414710.75036420.750364−0.018923−1.6819050.73911330.739113−0.000046−1.6736330.739085\begin{array}{ccccc}\text{n} & \text{x n} & \text{f} & \text{f prime} & \text{x next} \\ 1 & 1.000000 & -0.459698 & -1.841471 & 0.750364 \\ 2 & 0.750364 & -0.018923 & -1.681905 & 0.739113 \\ \hlmath{3} & \hlmath{0.739113} & \hlmath{-0.000046} & \hlmath{-1.673633} & \hlmath{0.739085}\end{array}

Step 5 — Root estimate

After 3 iterations the root is about 0.739085.

x≈0.739085iters=3x\approx \hlmath{0.739085} \quad \text{iters}= 3
newton-raphson Given a starting point x0, each Newton step moves to x1=x0-f(x0)/f'(x0), tangent-line intersection with the x-axis. Converges quadratically near a simple root.