Page 93 - Numerical methods for chemical engineering

Robust reduced-step Newton method 79

Robust reduced-step Newton method

In the study of the performance of Newton’s method for a simple 2-D system, we have seen
that far away from the solution, the update steps are large and lie in erratic directions. The
efficiency and robustness of Newton’s method (and quasi-Newton variations such as that of
Broyden) are improved dramatically through use of a reduced-step algorithm, in which only
a fraction of the update vector is accepted. The full update vector is generated by solving
the linear system
[k]

B x [k] =− f x [k] (2.74)
but now only a fraction α [k] ∈ [0, 1] of the full step is accepted,

[k+1] [k] [k] [k]
x = x + α x (2.75)
This fractional step is chosen such that the norm of the function vector at the new estimate
is smaller than at the old one, yielding the descent criterion

& & & [k] [k] & & &
f x [k+1] & = f x + α x [k] & < f x [k] & (2.76)
& & &
Since a solution x s has f (x s ) = 0, x s is a global minimum of f (x) . So as long as we are
decreasing the value of the norm, we feel that we are making good progress towards finding
a solution.
We now ask two questions:
2
Is there always some α [k] > 0 such that the descent criterion using the 2-norm, v = v · v,
2
is satisfied?
Under what conditions will this method find a limiting point that is not a solution?
To answer the first question, we use the path integral relation

' ε
[k] [k] [k] [k] [k] [k]
f x + ε x = f x + J x + s x x ds (2.77)
0
which we may approximate for very small ε by neglecting the variation in the Jacobian as
[k] [k] [k] [k] [k]
f x + ε x ≈ f x + εJ x x (2.78)
Taking the dot product of this equation with itself yields

&

&

· f x
& f x [k] + ε x [k] & 2 = f x [k] + εJ x [k] x [k] [k] + εJ x [k] x [k] (2.79)
2
Retaining the terms up to first order in ε yields
& [k] & 2 & & 2 [k] [k] [k]
f x + ε x [k] & f x [k] & + 2ε f x · J x x (2.80)
& ≈ &
2 2
[k]
[k] −1
Assuming B [k] is nonsingular, x [k] =−(B ) f (x ), and

& [k] & 2 & & 2 [k] [k] [k] −1 [k]
f x + ε x [k] & f x [k] & − 2ε f x · J x B f x (2.81)
& ≈ &
2 2