Lesson 69 — Newton-Raphson Method

$f(x) = x^2 - 2$, $x_0 = 1$. Apply 3 iterations of Newton-Raphson. Compare with $\sqrt{2} = 1.41421356\ldots$

$f(x) = x^2 - 5$, $x_0 = 2$. Apply 3 iterations to estimate $\sqrt{5}$.

$f(x) = x^3 - 2$, $x_0 = 1$. Apply 3 iterations to estimate $\sqrt[3]{2}$.

$f(x) = \cos x - x$, $x_0 = 1$. Apply 3 iterations to estimate the fixed point of $\cos$.

$f(x) = e^x - 2$, $x_0 = 1$. Apply 3 iterations to estimate $\ln 2$.

$f(x) = x \ln x - 1$, $x_0 = 2$. Approximate the root to 4 decimal places.

$f(x) = \sin x$, $x_0 = 3$. Numerically show that the iterations converge to $\pi$.

$f(x) = x^3 - x - 1$, $x_0 = 1.5$. Approximate the real root (plastic constant $\approx 1.3247$).

$f(x) = x^2 - x - 1$, $x_0 = 1.5$. Approximate the golden ratio $\phi = (1 + \sqrt{5})/2$.

$f(x) = \tan x - x$, $x_0 = 4.5$. Approximate the smallest positive root greater than $\pi$.

Show that Heron's formula $x_{n+1} = (x_n + a/x_n)/2$ for calculating $\sqrt{a}$ is exactly Newton-Raphson applied to $f(x) = x^2 - a$.

Generalize: what is the Newton iteration for calculating $\sqrt[n]{a}$? Apply for $n = 3$, $a = 8$, $x_0 = 2$ (2 steps).

Show that $x_{n+1} = x_n(2 - ax_n)$ calculates $1/a$ via Newton without any division operations. Apply for $a = 7$, $x_0 = 0.1$ (3 steps).

Minimize $g(x) = x^4 - 4x + 1$ by applying Newton-Raphson to $g'(x) = 0$, with $x_0 = 1.5$.

Cash flows: -1000, 300, 400, 500 (years 0, 1, 2, 3). The IRR $r$ is the root of $f(r) = -1000 + 300/(1+r) + 400/(1+r)^2 + 500/(1+r)^3 = 0$. Use Newton with $r_0 = 0.15$.

In Black-Scholes, given the market price $V_{\text{mkt}}$ of an option, explain how to use Newton-Raphson to find the implied volatility $\sigma$. What is the role of vega in the iteration?

In the van der Waals equation $(P + a/V^2)(V - b) = RT$, given $P$, $T$ (and gas constants), use Newton to find the molar volume $V$. Sketch the iteration.

Kepler's equation: $E - e \sin E = M$. For $e = 0.3$ (eccentricity) and $M = 1$ rad (mean anomaly), use Newton with $E_0 = 1$ to find the eccentric anomaly $E$ (4 iterations).

What behavior can Newton-Raphson exhibit when the initial guess $x_0$ is far from the root?

What is the most robust stopping criterion for Newton-Raphson?

Show that Newton-Raphson with $f(x) = x^3 - 2x + 2$ and $x_0 = 0$ cycles indefinitely between $0$ and $1$.

$f(x) = x^2$ (double root at $x = 0$), $x_0 = 1$. Show that Newton-Raphson converges only linearly, with ratio $1/2$.

$f(x) = x^{1/3}$ has a root at $x = 0$ but $f'(0)$ does not exist. What happens with Newton-Raphson? Calculate 4 iterations starting from $x_0 = 1$.

Apply the secant method ($x_0 = 1$, $x_1 = 2$) to $f(x) = x^2 - 2$ for 4 iterations. Compare with Newton (exercise 69.1).

$f(x) = x^3 - 3x + 1$ has 3 real roots. Apply Newton with $x_0 = 2$, then with $x_0 = -2$, then with $x_0 = 0.5$. Which root does each guess find?

Modified Newton for a double root: $x_{n+1} = x_n - 2f(x_n)/f'(x_n)$. Apply to $f(x) = (x-1)^2$, starting from $x_0 = 3$. Compare with the standard iteration.

Newton for optimization: show that applying Newton to $g'(x) = 0$ to minimize $g$ is equivalent to standard Newton with $f = g'$. Apply to minimize $g(x) = e^x - 3x$ with $x_0 = 0$.

For $f(z) = z^3 - 1$ in the complex plane, qualitatively describe the 3 Newton basins. On the real line, which root do $x_0 = 2$ and $x_0 = -0.5$ reach?

Prove the quadratic convergence of Newton-Raphson via Taylor expansion of order 2. Identify the constant $C = |f''(r)|/(2|f'(r)|)$.

Prove: if $f$ is convex increasing with a simple root $r$ and $x_0 > r$ with $f(x_0) > 0$, Newton-Raphson converges to $r$.

Generalize Newton-Raphson to $\vec{f}: \mathbb{R}^n \to \mathbb{R}^n$. Write the linear system to be solved at each step and identify the role of the Jacobian $J$.

Show that Heron's iteration $x_{n+1} = (x_n + a/x_n)/2$ converges quadratically to $\sqrt{a}$ for any $x_0 > 0$.