Skip to main content

Subsection 5.3.4 Solving A x = y via LU factorization with pivoting

Given nonsingular matrix \(A \in \C^{m \times n} \text{,}\) the above discussions have yielded an algorithm for computing permutation matrix \(P \text{,}\) unit lower triangular matrix \(L \) and upper triangular matrix \(U \) such that \(P A = L U \text{.}\) We now discuss how these can be used to solve the system of linear equations \(A x = y \text{.}\)

Starting with

\begin{equation*} A x = b \end{equation*}

where nonsingular matrix \(A \) is \(n \times n \) (and hence square),

  • Overwrite \(A \) with its LU factorization, accumulating the pivot information in vector \(p \text{:}\)

    \begin{equation*} [ A, p ] :=\mbox{LUpiv}( A ). \end{equation*}

    \(A \) now contains \(L \) and \(U \) and \(\widetilde P( p ) A = L U \text{.}\)

  • We notice that \(A x = b \) is equivalent to \(\widetilde P( p ) A x = \widetilde P( p ) b \text{.}\) Thus, we compute \(y := \widetilde P( p ) b.\) Usually, \(y \) overwrites \(b \text{.}\)

  • Next, we recognize that \(\widetilde P( p ) A x = y\) is equivalent to \(L \begin{array}[t]{c} \underbrace{(U x)}\\ z \end{array} = y \text{.}\) Hence, we can compute \(z \) by solving the unit lower triangular system

    \begin{equation*} L z = y \end{equation*}

    and next compute \(x \) by solving the upper triangular system

    \begin{equation*} U x = z. \end{equation*}
login