NLA MT25, LU factorisation
Flashcards
Suppose $A \in \mathbb R^{5 \times 5}$ and has an LU factorisation. @Describe how you can interpret the LU factorisation as writing $A$ as a sum of rank-1 matrices.
We rewrite $A$ as
\[\begin{aligned} A &= \begin{bmatrix} * \\ * \\ * \\ * \\ * \end{bmatrix} \begin{bmatrix} * & * & * & * \end{bmatrix} + \begin{bmatrix} * & * & * & * \\ * & * & * & * \\ * & * & * & * \\ * & * & * & * \end{bmatrix} \\ &= \underbrace{ \begin{bmatrix} * \\ * \\ * \\ * \\ * \end{bmatrix} \begin{bmatrix} * & * & * & * \end{bmatrix} } _ {L _ 1 U _ 1} + \underbrace{ \begin{bmatrix} 0 \\ * \\ * \\ * \\ * \end{bmatrix} \begin{bmatrix} 0 & * & * & * \end{bmatrix} } _ {L _ 2 U _ 2} + \begin{bmatrix} * & * & * & * \\ * & * & * & * \\ * & * & * & * \end{bmatrix} \\ &= \cdots \end{aligned}\]So that we have
\[\begin{aligned} A &= \begin{bmatrix} * \\ * \\ * \\ * \\ * \end{bmatrix} \begin{bmatrix} * & * & * & * & * \end{bmatrix} + \begin{bmatrix} 0 \\ * \\ * \\ * \\ * \end{bmatrix} \begin{bmatrix} 0 & * & * & * & * \end{bmatrix} + \begin{bmatrix} 0 \\ 0 \\ * \\ * \\ * \end{bmatrix} \begin{bmatrix} 0 & 0 & * & * & * \end{bmatrix} + \begin{bmatrix} 0 \\ 0 \\ 0 \\ * \\ * \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 & * & * \end{bmatrix} + \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ * \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 & 0 & * \end{bmatrix} \\ &= L _ 1 U _ 1 + L _ 2 U _ 2 + L _ 3 U _ 3 + L _ 4 U _ 4 + L _ 5 U _ 5 \\ & = [L _ 1, L _ 2, \ldots, L _ 5] \begin{bmatrix} U _ 1 \\ U _ 2 \\ \vdots \\ U _ 5 \end{bmatrix} \\ &= \color{red}{ \begin{bmatrix} * \\ * & * \\ * & * & * \\ * & * & * & * \\ * & * & * & * & * \end{bmatrix} } \color{blue}{ \begin{bmatrix} * & * & * & * & * \\ & * & * & * & * \\ & & * & * & * \\ & & & * & * \\ & & & & * \end{bmatrix} } \end{aligned}\]@Prove that any nonsingular matrix $A$ has a pivoted LU decomposition.
@todo.
Stability analysis
@State a (nonexaminable) result about the backward stability of computing the LU factorisation of a matrix.
\[\frac{ \vert \vert \hat L \hat U - A \vert \vert }{ \vert \vert L \vert \vert \, \vert \vert U \vert \vert } = \epsilon\]
where $\epsilon$ is machine precision.
We have the result that the LU factorisation of the matrix has the following backwards stability properties:
\[\frac{ \vert \vert \hat L \hat U - A \vert \vert }{ \vert \vert L \vert \vert \, \vert \vert U \vert \vert } = \epsilon\]
Under what conditions will $\hat x$ be a backward stable solution to $LUx = b$?
\[\vert \vert L \vert \vert \, \vert \vert U \vert \vert = O( \vert \vert A \vert \vert )\]