Information Technology Reference
In-Depth Information
(h) Suppose x
0
2. Show that
x
k
2
(4.200)
for k
0,wherex
k
is generated by (
4.196
).
(i) Recall that
e
k
D
x
k
2:
(4.201)
Use (
4.200
) to argue that
j
e
k
j D
x
k
2;
(4.202)
since x
0
2.
(j) Use (
4.196
) to show that
e
k
2x
k
j
e
kC1
j D
:
(4.203)
(k) Use (
4.200
) to conclude that
1
4
e
k
j
e
kC1
j
:
(4.204)
How does this result compare with your computational results in (b)?
We will now derive a result stating that the convergence of Newton's method,
under certain assumptions, is quadratic. This result shows that the quadratic con-
vergence encountered in numerous exercises above are not just a coincidence; we
have quadratic convergence for a whole class of problems. On the other hand, our
derivation will also give us some hints about when the method can get into trouble.
Before we start the analysis, let us just recall that for a smooth function f ,we
have
f.x/
D
f.a/
C
.x
a/f
0
.a/
C
1
2
.x
a/
2
f
00
./;
(4.205)
where is a number in the interval bounded by x and a, see (1.30) on page 7. We
consider the problem of solving the equation
f.x/
D
0
(4.206)
using Newton's method,
f.x
k
/
f
0
.x
k
/
;
x
kC1
D
x
k
(4.207)
