Update Methods and their Numerical Stability

In numerical continuation methods, we are usually confronted with the problem of solving linear equations such as(16.1.1)$$Ax = y$$at each step. Update methods can be applied when the matrix A is only slightly modified at each subsequent step. This is in particular the case for the update algorithms of chapter 7 and for the PL algorithms of chapters 12–15. As we have noted in those chapters, the modification of A is of the form(16.1.2)$${\tilde A}: = A + (a - Ae)e*,$$where e is some vector of unit length. For example, see (12.4.4), if e denotes the ith unit basis vector, then the above formula indicates that the ith column of A is replaced by the column a. Similar formulae arise via Broyden’s update in chapter 7, see (7.2.3). In order to solve linear equations such as (16.1.1), it is usually necessary to decompose A. In the present chapter we show that by making use of (16.1.2), such a decomposition can be cheaply updated in order to obtain a decomposition of Ã. A simple example is provided by (12.4.6) where a certain right inverse of A was updated at each step. However, as was pointed out there, this update is not always stable, see Bartels & Golub (1968–69). Thus, the question arises whether cheap numerically stable updates of a decomposition are possible.