Page 92 - Numerical methods for chemical engineering

78 2 Nonlinear algebraic systems

Let B [k] be the current estimate of the Jacobian. We update the solution estimate by the
rule
[k]

B x [k] =− f x [k] (2.66)
x [k+1] ← x [k] + x [k]

At x [k+1] , we evaluate the function value f (x [k+1] ), but to obtain the new update by solving
the linear system

B [k+1] x [k+1] =− f x [k+1] (2.67)
we need a new Jacobian estimate B [k+1] .
[k]
[k]
Broyden’s method generates B [k+1] from B , f (x ), and f (x [k+1] ) using the path
integral formula
' 1
[k+1] [k] [k] [k] [k]
f x = f x + J x + s x x ds (2.68)
0
[k]
and its approximation for very small x , obtained by neglecting the variation in the
Jacobian,

[k+1] [k] [k+1] [k]
f x ≈ f x + J x x (2.69)
In Broyden’s method, we require that B [k+1] exactly satisfies this approximation:
[k+1] [k] [k+1] [k]
f x = f x + B x (2.70)

Using (2.64), this becomes
[k+1] [k] [k] [k+1] [k]
f x + B x = B x (2.71)
[k] T
2
T
We postmultiply by ( x ) and use the identity Bvv =|v| B to write

[k+1] [k] T 2 [k] 2 [k+1]
f x x + x [k] B = x [k] B (2.72)

[k] 2
Division by the scalar | x | yields the Broyden rank-one update rule
T
[k+1] [k]
f x x
B [k+1] = B [k] + (2.73)
2
x
[k]
To start, we typically use a crude approximation of the Jacobian such as B [0] = I. In general,
convergence is slower with Broyden’s method than with Newton’s method. Note, however,
that the quadratic convergence of Newton’s method is only obtained near the solution,
and that this update formula does not require the N additional function evaluations of the
finite difference approximation. This reduction in workload per Newton iteration makes
the Broyden method a popular choice when we do not supply a routine to evaluate the
Jacobian matrix analytically. For more information on quasi-Newton methods and Jacobian
estimation, consult Nocedal & Wright (1999).