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 and U is related to the elements $u^{\prime}_{ij}$ and $d^{\prime}_{i}$ of the LDU decomposition as follows.

$$u_{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.

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

If U is upper triangular, the statement becomes

$$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

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

becomes

$$\frac{u_{ij}}{u_{ii}}=\frac{{u}_{ij}}{\delta}+{\beta}_{2}{z}_{j}$$ (70)

Solving for the updated value of uij yields

$$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,\cdots,n$
    $\delta=u_{ii}$
    $p=y_{i}$
    $q=z_{i}$
    $u_{ii}=u_{ii}+\alpha pq$
    $\beta_{2}=\alpha q$
    $q=\displaystyle\frac{q}{\delta}$
    $\delta=\displaystyle\frac{u_{ii}}{\delta}$
    $\alpha=\displaystyle\frac{\alpha}{\delta}$
    for $j=i+1,\cdots,n$
        $y_{j}=y_{j}-pl_{ji}$
        $z_{j}=z_{j}-qu_{ij}$
        $l_{ji}=l_{ji}+\beta_{1}y_{j}$
        $u_{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 $l^{\prime}_{ij}$, $d^{\prime}_{i}$ of the LDU decomposition are related as follows.

$$l_{ij}=l^{\prime}_{ij}d^{\prime}_{j}$$ (72)

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