Page 94 - Numerical methods for chemical engineering

80 2 Nonlinear algebraic systems

i te ve is d wni at e ver ste
r tis initia int w e wi
ind a ase stin

stin wit
at int || f || 2 , f(x) = 0
t nt a stin
since f (x) ≠ 0 || f || 2 = 0

Figure 2.12 The reduced-step norms reduction method may also find a local minimum of the norm
that is not a solution.

[k]
Now, if the exact Jacobian is used, B [k] = J , then J x [k] B [k] −1 = I and
&
&
&
&

&

f x
&
&
& f x [k] + ε x [k] & 2 ≈ & [k] & 2 − 2ε f x [k] · f x [k] = (1 − 2ε) f x [k] & 2
2 2 2
(2.82)
2
2
[k]
[k]
For 0 <ε 1, f (x [k] + ε x ) < f (x ) ; therefore, when using the exact
2 2
Jacobian, there always exists some very small, positive value of the fractional step length that
results in a decrease of the norm, and so it will be possible always to find some α [k] ∈ [0, 1]
that satisfies the descent criterion. Even if we do not use the exact Jacobian, but only an
[k]
[k] −1
approximation of it, as long as the matrix J(x )(B ) exists and is positive-definite, it
is possible to find an α [k] ∈ [0, 1] that satisfies the descent criterion.
We now consider the second question. As Figure 2.12 demonstrates, merely reducing
the norm of the cost function is not sufficient to ensure that we end up at a solution, since
we could find instead a local minimum in the cost function that is not a solution (the norm
value is nonzero).
We can identify the condition necessary for such a “false solution” through the relation
2 T
∇ f = 2J f (2.83)
2
T
At a flat point in the 2-norm, we must have J f = 0, and the only way that this can occur
T
if we are not at a solution is if det(J ) = det(J) = 0.
With reduced-step Newton algorithms, one of two results generally occurs. Either we
converge to a solution (eventually), or the method locates a “false solution” where the
Jacobian is singular. If the latter occurs, the iterations stop since we cannot solve the linear
update equations and we must start again using a different initial guess.
The backtracking weak line search method
A common method to generate the fractional step length in a reduced-step algorithm is
the backtracking weak line search. First, we attempt to take the full Newton step. If this