Graphics Reference
In-Depth Information
The Newton-Raphson approach would start with a guess
z
0
= (x
0
,y
0
) and then, using
equation (4.15), generate a sequence of points
z
k
= (x
k
,y
k
) satisfying
(
)
¢
()
=-
()
z
-
z
p
z
qz
p
,
(4.17)
k
+
1
k
k
k
where p¢(
z
) is the Jacobian matrix
∂
∂
∂
∂
p
x
p
y
Ê
ˆ
()
z
Á
Á
Á
˜
˜
˜
¢
()
=
p
z
.
()
z
Ë
¯
If p¢(
z
) had an inverse, the one could solve equation (4.17) for
z
k+1
and one would then
have a nice formula for generating the sequence of points
z
k+1
, which would hopefully
converge to a solution to equation (4.16). Unfortunately, the 2 ¥ 3 matrix p¢(
z
) obvi-
ously does not have an inverse, but one can use the Moore-Penrose inverse instead to
get the equation
(
)
-
1
(
)
-=-
()
(
)
¢
()
¢
()
¢
()
T
T
z
z
pz
pp pp
z
z
z
.
(4.18)
k
+
1
k
k
k
k
k
For an application of this approach to determine the intersection of two surfaces see
[AbdY96].
Next, how do we detect and deal with problems encountered by the Newton-
Raphson method? In general, one case where we have problems is when the gradient
of a function f is zero. In that case, we would really need to analyze the Hessian of f.
To avoid some of these difficulties, many other iterative methods have been developed.
The basic situation is the following: We are trying to generate a sequence of points
x
k
, where
x
=-
x
l
d
.
k
+
1
k
k
k
In other words, the approach involved
(1) choosing a direction of search
d
k
, and
(2) carrying out a linear search in that direction (specified by l
k
).
This is a “hill-climbing”-type problem. Looking at it that way leads to a steepest
descent method (Cauchy, 1847) which chooses
=—
()
d
l
f
x
,
l
>
0
(4.19)
k
k
k
k
This method is recommended when
x
0
is far from the root or a local critical point
and then to use the Newton-Raphson iteration on
—=
f
0
when one gets close.
