Lecture 4: Newton s Method

Newton’s Method

Newton’s (or the Newton-Raphson) method is one of the most powerful and well-known numerical methods for solving a root-?nding problem. There are many ways of introducing Newton’s method.

Suppose that f ? C2[a, b]. Let p0 ? [a, b] be an approximation to p such that f ’( p0) ? 0 and | p ? p0| is “small.” Consider the ?rst Taylor polynomial for f (x) about p0 and evaluated at x = p.
f (p)=f (p0)+(p-p0) f ’( p0)+?(p-p0)?^2/2 f ( p_0)
Since f (p) = 0, this equation gives
0 = f (p0) + (p-p0) f ’( p0)+?(p-p_0)?^2/2 f ( p_0)
|p-p0| is small , so ?(p-p_0)?^2 is smaller. Then
0 ? f (p0) + (p-p0) f ’( p0)
solving for p, gives
p ? p0 - (f (p_0) )/(f ’( p_0))? p1
This sets the stage for Newton’s method, which starts with an initial approximation p0 and generates the sequence

p_n=p_(n-1)-f(p_(n-1) )/(f (p_(n-1) ) ) ,n?1

Theorem:
Let f ? C2[a, b]. If p ? (a, b) is such that f ( p) = 0 and f ‘ ( p)? 0, then there exists a ? > 0 such that Newton’s method generates a sequence ?{ p_n}?_(n=1)^?
converging to p for any initial approximation p0 ? [p ? ?, p + ?].