Broyden-Householder algorithm

Like the Broyden-Householder method, Kubicek algorithm is based on Householder s identity.19... 

Instead of applying Householder s formula, the calculation of an inverse of the jacobian may be avoided altogether by use of the algorithm proposed by Bennett for updating the LU factors of the jacobian matrix. Example 4-9 will show that fewer numerical operations are required to compute the LU factors than are required to compute the inverse of a matrix. Bennett s algorithm is applied to the Broyden equations as follows. 

Less time is consumed by procedure 3 than by procedure 1. Calculation of the LU factors of the matrix J in step 2 of procedure 3 requires approximately n3/3 operations, whereas the calculation of the inverse of J in step 2 of procedure 2 requires approximately n3 operations, where the matrix J is a square matrix of order n. To update the LU factors in step 6 of procedure 3 by use of Bennett s algorithm requires approximately In2 operation, whereas approximately 3n2 operations are required to update the inverse of J by use of Householder s formula as proposed by Broyden in step 6 of procedure 2. 

After the Broyden correction for the independent variables has been computed, Broyden proposed that the inverse of the jacobian matrix of the Newton-Raphson equations be updated by use of Householder s formula. Herein lies the difficulty with Broyden s method. For Newton-Raphson formulations such as the Almost Band Algorithm for problems involving highly nonideal solutions, the corresponding jacobian matrices are exceedingly sparse, and the inverse of a sparse matrix is not necessarily sparse. The sparse characteristic of these jacobian matrices makes the application of Broyden s method (wherein the inverse of the jacobian matrix is updated by use of Householder s formula) impractical. 

In this algorithm, Broyden s method is applied by updating the jacobian matrices by use of Householder s formula.13 Let J0 be the initial approximation of the jacobian matrix with which the iterative procedure is started. Then... 

An algorithm is given elow for solving the Newton-Raphson equations by use of only the LU factorization of J0 and the Broyden update terms given by Eqs. (5-29), (5-30), and (5-31). As shown in App. 5-1, this algorithm is based on the successive application of Householder s formula to Eq. (5-29). 

---