Newton’s Method and Other

The goal is to find where the graph crosses the x-axis. We start with a guess of x0 = 1. Plugging
that back into the equation for y, we get y0 = 12 ? 3 = ?2, which isn’t very close to 0.
Our next guess is x1, where the tangent line to the function at x0 crosses the x-axis. The equation
for the tangent line is:
y ? y0 = m(x ? x0)
When the tangent line intercepts the x-axis, y = 0, so
?y0 = m(x1 ? x0)
y0 ?
m
= x1 ? x0
y0 x1 = x0 ?
m
Remember: m is the slope of the tangent line to y = f(x) at the point (x0, y0).
1
In terms of f:
y0 = f(x0)
m = f?(x0)
Therefore,
f(x0)
x1 = x0 ?
f?(x0)
x1
x0 x2
Figure 2: Illustration of Newton’s Method, Example 1.
In our example, f(x) = x2 ? 3, f?(x) = 2x. Thus,
(x0 2
? 3) 1 3
x1 = x0 ? 2x
= x0 ? 2x0 +
2x0
1 3
x1 = x0 +
2 2x0
The main idea is to repeat (iterate) this process:
1 3
x2 = x1 +
2 2x1
1 3
x3 = x2 +
2 2x2
and so on. The procedure approximates
?
3 extremely well.
2
Lecture 13 18.01 Fall 2006
x
Example 1 considered the particular case of
f(x) = x2 ? 3
f(xk) 1 3
xk+1 = xk ?
f?(xk)
= ... =
2xk +
2xk
Now, we define
x = lim xk (xk ? x as k ? ?)
k??
To evaluate x in Example 1, take the limit as k ? ? in the equation
1 3
xk+1 = xk +
2 2xk
3
Lecture 13 18.01 Fall 2006
This yields
1 3 1 3 1 3
x¯ =
2x¯ +
2¯x
=? x ? 2x =
2x
=? 2x =
2x
=? x2 = 3
which is just what we hoped: x =
?
3.
Warning 1. Newton’s Method can find an unexpected root.
Example: if you take x0 = ?1, then xk ? ?
?
3 instead of +
?
3. This convergence to an unexpected
root is illustrated in Fig.