MATH/APPM 4650
Class notes, February 1

Newton's Method

We saw last time that we can solve an algebraic equation f(x) = 0 by transforming it into a fixed-point problem for g(x) = x + f(x).

At the end, we mentioned one can also apply a function, like g(x) = x + h( f(x) ), which will work if h(0) = 0.

Iterating such a g will converge as long as |g'(p)| < 1.

If x_n+1 = g(x_n), then if g'(p) ≠ 0, then |x_n+1 - p| ∼ |g'(p)| |x_n - p|. So the error E_n=x_n - p converges to 0 like a geometric series: if C = g'(p), then E_n ∼ E₀ Cⁿ.

A good choice for g was discovered by Newton: g(x) = x - f(x)/f'(x). In this case, we can compute that if f(p) = 0 and f'(p) ≠ 0, then g'(p) = 1 - f'(p) / f'(p) + f(p) f''(p) / f'(p)² = 1 - 1 + 0 = 0. Since g'(p) = 0, we have even faster convergence.

The algorithm for Newton's method:
It's the same as for fixed-point iteration. Just use
newX = oldX - F(oldX)/F'(oldX). Observe that you should never simplify this, even if you can, for the same reason that in the bisection method, one should always use A + (B-A)/2 instead of (A+B)/2.
The second number is a small correction.



The geometry of Newton's method:

1. Start with an approximation x_n.
2. Draw the tangent line to the graph of f at that x.
3. Then x_n+1 is the point where that tangent line crosses the axis.

Analysis of Newton's method:
If x_n ∼ p, then
    x_n+1 = g(x_n)
           ∼ g(p) + g'(p) (x_n - p) + 1/2 g''(p) (x_n - p)²
           ∼ p + 1/2 f''(p)/f'(p) (x_n - p)².

So if C = 1/2 f''(p)/f'(p), then x_n+1 - p ∼ C (x_n - p)². Hence the error E_n = |x_n - p| converges to zero like E_n = 1/C (CE₀)²ⁿ. Much faster!



Of course, the algorithm for this is basically the same as the general fixed-point iteration algorithm from Section 2.2.

We just need to be able to compute f'! This may be difficult.
(For example, if f is only known at a few points, it's easy to interpolate other values of f, but hard to approximate the derivative.)

---

The Secant Method:
The secant method is used when the derivative is hard to compute. It comes from approximating the derivative with the slope of a secant.
f'(x_n) ∼ [ f(x_n) - f(x_n-1) ] / [x_n - x_n-1].

Geometry of the secant method:
So the algorithm is x_n+1 = x_n - f(x_n) * [x_n - x_n-1] / [ f(x_n) - f(x_n-1) ].
It's now a two-step algorithm, which means you need to specify both x₀ and x₁.

It's also slower than Newton's method. The error formula looks like E_n+1 ∼ C E_n E_n-1. This looks something like the Fibonacci sequence.

So the error is something like E_n ∼ 1/C (CE₀)^1.62n.

---

The advantage of Newton's method and the secant method over bisection is if they work, they're much faster.

The disadvantage of both Newton's method and the secant method is there's no guarantee they converge.

A compromise is the Regula Falsi method, also called the method of false position.

1. Start with a and b such that f(a) and f(b) have opposite signs. (Like bisection.)
2. Instead of letting m be the midpoint, choose m = a - f(a) * [b - a] / [f(b) - f(a) ]. (Like secant.)
3. m is always between a and b. Check the sign of f(m). (Like bisection.)
   1. If f(m)=0, stop.
   2. If f(m) and f(a) have the same sign, the new a is m. (The new b is the old b.)
   3. If f(m) and f(b) have the same sign, the new b is m. (The new a is the old a.)
4. Repeat with the new a and b.

Disadvantages:

• Requires two initial approximations that bound the root.
• Slower than Newton's method or the secant method.
• The interval may not shrink. (See for example here.

Advantages:

• Always have an upper and lower bound.
• Will definitely converge.
• Faster than bisection.

The algorithm is exactly the same as the bisection algorithm, except for the determination of m.