6.2 LU Factor Update

Similar algorithms exist for updating LU decompositions of A. If U is upper triangular and L is unit lower triangular, an element uij from U is related to the elements uiju^{\prime}_{ij} and did^{\prime}_{i} of the LDU decomposition as follows.

uij=uijdiu_{ij}=u^{\prime}_{ij}d^{\prime}_{i} (66)

The recurrence relations of the inner loop of Algorithm 8 must change to reflect this relationship. The following statement updates the z vector for a unit upper triangular U.

zj=zj-quijz_{j}=z_{j}-q{u}^{\prime}_{ij} (67)

If U is upper triangular, the statement becomes

zj=zj-puijδz_{j}=z_{j}-p\frac{u_{ij}}{\delta} (68)

where δ\delta is the value of uii before it was changed during stage i of the procedure. Along the same lines, the factor update statement

uij=uij+β2zju^{\prime}_{ij}=u^{\prime}_{ij}+{\beta}_{2}{z}_{j} (69)


uijuii=uijδ+β2zj\frac{u_{ij}}{u_{ii}}=\frac{{u}_{ij}}{\delta}+{\beta}_{2}{z}_{j} (70)

Solving for the updated value of uij yields

uij=uii(uijδ+β2zj)u_{ij}=u_{ii}(\frac{{u}_{ij}}{\delta}+{\beta}_{2}{z}_{j}) (71)

Taking these observations into consideration and pulling operations on constants out of the inner loop, Algorithm 9 updates U based on a rank one change to A.

Algorithm 9: LU Factor Update
for i=1,,ni=1,\cdots,n
    uii=uii+αpqu_{ii}=u_{ii}+\alpha pq
    β2=αq\beta_{2}=\alpha q
    for j=i+1,,nj=i+1,\cdots,n
        uij=δuij+β2zju_{ij}=\delta u_{ij}+\beta_{2}z_{j}

If U is unit upper triangular and L is lower triangular, a similar algorithm is derived from the observation that lij of L and lijl^{\prime}_{ij}, did^{\prime}_{i} of the LDU decomposition are related as follows.

lij=lijdjl_{ij}=l^{\prime}_{ij}d^{\prime}_{j} (72)

The resulting algorithm deviates from Algorithm 8 in a manner that parallels Algorithm 9.