Crout-decompositie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De Crout-decompositie is een algoritme voor de LU-decompositie van een vierkante niet-singuliere matrix in een benedendriehoeksmatrix L en een bovendriehoeksmatrix U. In de matrix U zijn de elementen op de hoofddiagonaal gelijk aan 1.

De methode is genoemd naar Prescott Durand Crout, wiskundige aan het Massachusetts Institute of Technology die ze in 1941 beschreef.[1]

Beschrijving[bewerken]

Via Gauss-eliminatie[bewerken]

Zij A een n×n matrix met elementen ai,j. De Crout-decompositie is formeel gezien een Gauss-eliminatie. Het algoritme begint dan met als L de n×n-eenheidsmatrix en U gelijk aan A. In n-1 stappen wordt U herleid tot een bovendriehoeksmatrix en L tot een benedendriehoeksmatrix, zodanig dat het matrixproduct LU steeds gelijk blijft aan A.

In de k-de stap worden het elementen op de hoofddiagonaal in de k-de kolom van U op een gebracht en de elementen eronder op nul. Dit gebeurt door rij k te delen door het het pivot-element uk,k. Deze waarde kopiëren we in de corresponderende positie in matrix L. Daarna vermenigvuldigen we de k-de rij met uj,k en trekken ze dan af van rij j, wat een nieuwe rij j geeft met nul in de k-de kolom (j > k). De factoren, uj,k, kopiëren we eveneens in de corresponderende kolom van L.

Indien U een element uk,k op de hoofddiagonaal heeft dat nul is, gaat dit natuurlijk niet op. In dat geval moet de rij k verwisseld worden met een onderliggende rij j waarin uj,k niet nul is. De verwisseling gebeurt ook in L. De verwisselingen kunnen bijgehouden worden in een permutatiematrix P. In het begin is P de eenheidsmatrix. Wanneer twee rijen in U en L verwisseld worden, worden dezelfde rijen in P verwisseld. De decompositie is dan niet langer A = LU maar A = PLU.

Rechtstreekse berekening[bewerken]

Indien men rekening houdt met de specifieke structuur van L en U, kan men de coëfficiënten ervan een voor een berekenen. Immers als men het matrixproduct A = LU uitschrijft, verkrijgt men een stelsel van n×n lineaire vergelijkingen in de n×n onbekende coëfficiënten van L en U. Deze vergelijkingen kan men zo rangschikken dat elke volgende vergelijking een nieuwe coëfficiënt geeft; bijvoorbeeld:

 a_{1,1} = l_{1,1}, a_{2,1}  = l_{2,1} \dots
(dit is de eerste kolom van L)
 a_{1,2} = l_{1,1} u_{1,2} of u_{1,2} = \frac{a_{1,2}}{a_{1,1}}
  a_{1,3} = l_{1,1} u_{1,3} of u_{1,3} = \frac{a_{1,3}}{a_{1,1}} \dots
(dit vervolledigt de eerste rij van U)
 a_{2,2} = l_{2,1}u_{1,2} + l_{2,2} of l_{2,2} = a_{2,2} - l_{2,1} u_{1,2}
 a_{3,2} = l_{3,1} u_{1,2} + l_{3,2} of l_{3,2} = a_{3,2} - l_{3,1}u_{1,2} enz.;
(dit vervolledigt de tweede kolom van L)

Op deze manier kan men afwisselend een kolom van L en een rij van U rechtstreeks berekenen. Dit is de "compacte" vorm van de Crout-decompositie.

Rekenvoorbeeld[bewerken]

Gegeven:
A =
\begin{pmatrix}
     3 & -7 & -2 &  2 \\
    -3 &  5 &  1 &  0 \\
     6 & -4 &  0 & -5 \\
    -9 &  5 & -5 & 12 \\
\end{pmatrix}

We beginnen met als matrix L de eenheidsmatrix en U gelijk aan A:

L U = \begin{pmatrix}
     1 & 0 & 0 &  0 \\
    0 &  1 &  0 &  0 \\
     0 & 0 &  1 & 0 \\
    0 &  0 & 0 & 1 \\
\end{pmatrix}
\begin{pmatrix}
     3 & -7 & -2 &  2 \\
    -3 &  5 &  1 &  0 \\
     6 & -4 &  0 & -5 \\
    -9 &  5 & -5 & 12 \\
\end{pmatrix}

Eerste stap[bewerken]

In de eerste stap delen we de eerste rij van U door 3, en daarna vermenigvuldigen we de eerste rij achtereenvolgens met -3, 6, 9 en trekken ze af van de tweede, derde en vierde rij zodat de elementen onder de diagonaal in de eerste kolom van U nul zijn. De getallen 3, -3, 6 en 9 kopiëren we naar de eerste kolom van L, die dus een kopie wordt van de eerste kolom van U. Dit geeft als tussenstand:

L U = \begin{pmatrix}
     3 & 0 & 0 &  0 \\
    -3 &  1 &  0 &  0 \\
     6 & 0 &  1 & 0 \\
    -9 &  0 & 0 & 1 \\
\end{pmatrix}
\begin{pmatrix}
    1 & -7/3 & -2/3 &  2/3 \\
    0 &  -2 &  -1 &  2 \\
    0 & 10 &  4 & -9 \\
    0 &  -16 & -11 & 18 \\
\end{pmatrix}

(Men kan nagaan dat het product van deze twee matrices de oorspronkelijk matrix A is)

Tweede stap[bewerken]

Om het elementen op de hoofddiagonaal in de tweede kolom van U op een te krijgen moeten we de tweede rij van U delen door -2. Om de rest van de tweede kolom van U op nul te krijgen moeten we de tweede rij van U vermenigvuldigen met 10 en -16 en aftrekken van de derde resp; de vierde rij. De waarden -2, 10 en -16 gaan naar de tweede kolom van L ; die is dus een kopie van de tweede kolom van U vanaf de tweede rij. Dit geeft:

L U = \begin{pmatrix}
     3 & 0 & 0 &  0 \\
    -3 &  -2 &  0 &  0 \\
     6 & -10 &  1 & 0 \\
    -9 &  -16 & 0 & 1 \\
\end{pmatrix}
\begin{pmatrix}
    1 & -7/3 & -2/3 &  2/3 \\
    0 &  1 &  1/2 &  -1 \\
    0 & 0 &  -1 & 1 \\
    0 & 0 & -3 & 2 \\
\end{pmatrix}

Derde stap[bewerken]

In de derde stap delen we de derde rij van U door -1. Daarna vermenigvuldigen we de derde rij met -3 en trekken ze af van de vierde rij. De factoren -1 en -3 kopiëren we naar de derde kolom van L:

L U = \begin{pmatrix}
     3 & 0 & 0 &  0 \\
    -3 &  -2 &  0 &  0 \\
     6 & -10 &  -1 & 0 \\
    -9 &  -16 & -3 & 1 \\
\end{pmatrix}
\begin{pmatrix}
    1 & -7/3 & -2/3 &  2/3 \\
    0 &  1 &  1/2 &  -1 \\
    0 & 0 &  1 & -1 \\
    0 & 0 & 0 & -1 \\
\end{pmatrix}

Vierde stap[bewerken]

In de vierde en laatste stap rest ons enkel het element in de linker benedenhoek van U op een te brengen, door het te delen door -1, en die waarde te kopiëren naar L. Dit geeft als eindresultaat:

L U = \begin{pmatrix}
     3 & 0 & 0 &  0 \\
    -3 &  -2 &  0 &  0 \\
     6 & -10 &  -1 & 0 \\
    -9 &  -16 & -3 & -1 \\
\end{pmatrix}
\begin{pmatrix}
    1 & -7/3 & -2/3 &  2/3 \\
    0 &  1 &  1/2 &  -1 \\
    0 & 0 &  1 & -1 \\
    0 & 0 & 0 & 1 \\
\end{pmatrix}

Daarmee is de decompositie van A in LU beëindigd. In dit geval was er geen verwisseling van rijen nodig.

Bemerkingen[bewerken]

Om een stelsel van lineaire vergelijkingen Ax = B op te lossen gaat men als volgt te werk:

  1. Vorm de matrices L en U: L U x  = B. We noemen y het (voorlopig onbekende) product U x.
  2. Los L y = B op door voorwaartse substitutie.
  3. Los U x = y op door achterwaartse substitutie.

Wanneer bijvoorbeeld B={\begin{pmatrix} -36 & 20 & 2 & -34 \end{pmatrix}}^T, vinden we achtereenvolgens:

  • 3 y_1 = -36 of y_1 = -12
  • -3 y_1 -2 y_2 = 20 waaruit y_2 = 8
  • 6 y_1 +10 y_2 - y_3 = 2 waaruit  y_3 = 6
  • -9 y_1 -16 y_2 - 3 y_3 - y_4 = -34 waaruit  y_4 = -4

en:

  •  x_4 = y_4 = -4
  •  x_3 - x_4 = y_3 = 6 waaruit  x_3 = 2
  •   x_2  + \tfrac{x_3}{2} - x_4 = y_2 = 8 waaruit  x_2 = 3
  •  x_1 - \tfrac{7 x_2}{3} - \tfrac{2 x_3}{3} + \tfrac{2 x_4}{3} = y_1 = -12 waaruit  x_1 = -1

Indien deze methode in een computerprogramma wordt geïmplementeerd, is het niet nodig om twee afzonderlijke matrices voor L en U te gebruiken. Ze kunnen compact in een enkele matrix bewaard worden (daarvoor kan zelfs de matrix A dienen als deze mag overschreden worden). Het is immers niet nodig om de elementen op de hoofddiagonaal van U te bewaren, die per definitie gelijk zijn aan 1. De rij-permutaties kunnen bijgehouden worden in een permutatievector van n elementen 1 tot en met n; als twee rijen verwisseld worden worden de corresponderende elementen in de permutatievector verwisseld.

De Crout-decompositie gelijkt sterk op de Doolittle-decompositie. Dit is ook een LU-decompositie met dit verschil dat in een Doolittle-decompositie de elementen op de hoofddiagonaal van de benedendriehoeksmatrix L gelijk zijn aan 1.

Externe links[bewerken]

Bronnen, noten en/of referenties
  1. Prescott D. Crout. "A Short Method for Evaluating Determinants and Solving Systems of Linear Equations With Real or Complex Coefficients " (1941), Transactions of the American Institute of Electrical Engineers, vol. 60 nr. 12, blz. 1235–1240. DOI:10.1109/T-AIEE.1941.5058258