OnderwijsLineaire Algebra – Matrices – Matrixfactorisaties
Een factorisatie van een matrix \(A\) is een vergelijking die \(A\) uitdrukt in een product van twee of meer matrices. Voorlopig bekijken we alleen de \(LU\) factorisatie.
De \(LU\) factorisatie
Laat \(A\) een \(m\times n\) matrix zijn die kan worden geveegd tot echelonvorm zonder rijverwisslingen. Dan kan \(A\) worden geschreven in de vorm \(A=LU\), waarbij \(L\) een \(m\times m\) benedendriehoeksmatrix is met alleen \(1\)-en op de hoofddiagonaaal en \(U\) een \(m\times n\) echelonvorm van \(A\). Zo'n factorisatie heet een \(LU\) factorisatie (of ontbinding). Merk op dat door (links) te vermenigvuldigen met \(L\) de echelonvorm \(U\) wordt getransformeerd naar \(A\).
Als \(A=LU\), dan kan de vergelijking \(A\mathbf{x}=\mathbf{b}\) geschreven worden als \(L(U\mathbf{x})=\mathbf{b}\). Met \(U\mathbf{x}=\mathbf{y}\) kan dan \(\mathbf{x}\) worden bepaald door het oplossen van de vergelijkingen \(L\mathbf{y}=\mathbf{b}\) en \(U\mathbf{x}=\mathbf{y}\). Los eerst \(L\mathbf{y}=\mathbf{b}\) op voor \(\mathbf{y}\) en los vervolgens \(U\mathbf{x}=\mathbf{y}\) op voor \(\mathbf{x}\). Elke vergelijking is gemakkelijk op te lossen omdat \(L\) en \(U\) driehoeksmatrices zijn.
Voorbeeld: Beschouw \(A\mathbf{x}=\mathbf{b}\) met \(A=\begin{pmatrix}-2&1&3\\1&-1&-2\\-1&2&1\end{pmatrix}\) en \(\mathbf{b}=\begin{pmatrix}-5\\3\\-6\end{pmatrix}\). Dan geldt (zonder rijverwisselingen):
\[A=\begin{pmatrix}-2&1&3\\1&-1&-2\\-1&2&1\end{pmatrix}\sim\begin{pmatrix}-2&1&3\\0&-\frac{1}{2}&-\frac{1}{2}\\0&\frac{3}{2}&-\frac{1}{2}\end{pmatrix} \sim\begin{pmatrix}-2&1&3\\0&-\frac{1}{2}&-\frac{1}{2}\\0&0&-2\end{pmatrix}=U.\]Dan is \(L=\begin{pmatrix}1&0&0\\a&1&0\\b&c&0\end{pmatrix}\). Merk op dat \(a\), \(b\) en \(c\) precies staan op de posities waar we nullen hebben gecreëerd bij het bepalen van de echelonvorm \(U\). De waarden van \(a\), \(b\) en \(c\) moeten nu tegengesteld zijn aan die waarden die we gebruikt hebben om de nul op de betreffende positie te krijgen. We concluderen dat \(a=-\frac{1}{2}\), \(b=\frac{1}{2}\) en \(c=-3\). Dan volgt dat \(L=\begin{pmatrix}1&0&0\\-\frac{1}{2}&1&0\\\frac{1}{2}&-3&1\end{pmatrix}\). Dit kan eenvoudig worden gechecked:
\[LU=\begin{pmatrix}1&0&0\\-\frac{1}{2}&1&0\\\frac{1}{2}&-3&1\end{pmatrix}\begin{pmatrix}-2&1&3\\0&-\frac{1}{2}&-\frac{1}{2}\\0&0&-2\end{pmatrix} =\begin{pmatrix}-2&1&3\\1&-1&-2\\-1&2&1\end{pmatrix}=A.\]Nu volgt (bovenaan beginnend):
\[L\mathbf{y}=\mathbf{b}:\quad\left(\left.\begin{matrix}1&0&0\\-\frac{1}{2}&1&0\\\frac{1}{2}&-3&1\end{matrix}\,\right|\,\begin{matrix}-5\\3\\-6\end{matrix}\right) \quad\Longrightarrow\quad\mathbf{y}=\begin{pmatrix}-5\\\frac{1}{2}\\-2\end{pmatrix}\]en vervolgens (onderaan beginnend):
\[U\mathbf{x}=\mathbf{y}:\quad\left(\left.\begin{matrix}-2&1&3\\0&-\frac{1}{2}&-\frac{1}{2}\\0&0&-2\end{matrix}\,\right|\,\begin{matrix}-5\\\frac{1}{2}\\-2\end{matrix}\right) \quad\Longrightarrow\quad\mathbf{x}=\begin{pmatrix}3\\-2\\1\end{pmatrix}.\]Merk op dat een permutatie van de rijen in het stelsel gegeven door \(A\mathbf{x}=\mathbf{b}\) mooiere berekeningen had opgeleverd. Soms is het niet eens mogelijk om de matrix \(A\) te vegen naar echelonvorm zonder rijverwisselingen zelfs als het stelsel \(A\mathbf{x}=\mathbf{b}\) oplosbaar is. In dat geval kan men in plaats van de gewone \(A=LU\) factorisatie een \(PA=LU\) factorisatie gebruiken, waarbij \(P\) een permutatiematrix is. Bijvoorbeeld, in ons voorbeeld: laat \(P=\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}\). Dan is \(PA\mathbf{x}=P\mathbf{b}\) equivalent met \(A\mathbf{x}=\mathbf{b}\) en
\[PA=\begin{pmatrix}1&-1&-2\\-1&2&1\\-2&1&3\end{pmatrix}\sim\begin{pmatrix}1&-1&-2\\0&1&-1\\0&-1&7\end{pmatrix} \sim\begin{pmatrix}1&-1&-2\\0&1&-1\\0&0&-2\end{pmatrix}=U\quad\Longrightarrow\quad L=\begin{pmatrix}1&0&0\\-1&1&0\\-2&-1&1\end{pmatrix}.\]Nu volgt (bovenaan beginnend):
\[L\mathbf{y}=P\mathbf{b}:\quad\left(\left.\begin{matrix}1&0&0\\-1&1&0\\-2&-1&1\end{matrix}\,\right|\,\begin{matrix}3\\-6\\-5\end{matrix}\right) \quad\Longrightarrow\quad\mathbf{y}=\begin{pmatrix}3\\-3\\-2\end{pmatrix}\]en vervolgens (onderaan beginnend):
\[U\mathbf{x}=\mathbf{y}:\quad\left(\left.\begin{matrix}1&-1&-2\\0&1&-1\\0&0&-2\end{matrix}\,\right|\,\begin{matrix}3\\-3\\-2\end{matrix}\right) \quad\Longrightarrow\quad\mathbf{x}=\begin{pmatrix}3\\-2\\1\end{pmatrix}.\]Laatst gewijzigd op 29 maart 2021
