Information Technology Reference
In-Depth Information
4.3
Newton's Method
We observed above that we can solve nonlinear algebraic equations of the form
f.x/
D
0
(4.40)
by just searching in a simple and systematic manner. This is fine if you only need to
solve the equation once or a few times. But in applications where variants of such
equations need to be solved billions of times, we need methods that converge faster
than the bisection method.
As discussed above, we search for a value x
such that
f.x
/
D
0;
(4.41)
and we often know a point x
0
close to x
. As mentioned above, this is the case for
nonlinear equations of the form
u
nC1
t g.
u
nC1
/
D
u
n
;
(4.42)
where we know that the unknown
u
nC1
is quite close to
u
n
, which is given. We can
also assume that in a small region around x
, the function f
D
f.x/ has only one
zero and that the derivative is always non-zero in this region. By a Taylor series
expansion around the given point x
D
x
0
,wehave
f.x
0
C
h/
D
f.x
0
/
C
hf
0
.x
0
/
C
.h
2
/:
(4.43)
O
So, for small values of h,wehave
f.x
0
C
h/
f.x
0
/
C
hf
0
.x
0
/:
(4.44)
Now we want to choose the step h such that f.x
0
C
h/
0. We can do that by
choosing h such that
f.x
0
/
C
hf
0
.x
0
/
D
0;
(4.45)
and consequently
h
D
f.x
0
/
f
0
.x
0
/
:
(4.46)
We can now define
f.x
0
/
f
0
.x
0
/
:
x
1
D
x
0
C
h
D
x
(4.47)
