Doolittle-decompositie
De Doolittle-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 L zijn de elementen op de hoofddiagonaal gelijk aan 1.
De methode werd in 1878 voorgesteld door Myrick H. Doolittle, een wiskundige verbonden aan de U.S. Coast and Geodetic Survey.[1]
Beschrijving
Via Gauss-eliminatie
Zij A een n×n matrix met elementen ai,j. De Doolittle-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 de elementen onder de hoofddiagonaal in de k-de kolom van U op nul gebracht. Dit gebeurt door rij k met de juiste factor te vermenigvuldigen en dan af te trekken van rij j, wat een nieuwe rij j geeft (j > k). De factoren zijn de verhoudingen van de elementen in rij j en k in kolom k. Die factoren, uj,k/uk,k, kopiëren we 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 P−1A = LU.
Rechtstreekse berekening
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. Maar deze vergelijkingen kan men zo rangschikken dat elke volgende vergelijking een nieuwe coëfficiënt geeft; bijvoorbeeld:
- of
- of enz.;
- of
- of enz.;
- of
- of enz.
Op deze manier kan men de coëfficiënten van L en U een voor een, rechtstreeks berekenen. Dit is de "compacte" vorm van de Doolittle-decompositie.
Rekenvoorbeeld
Gegeven:
We beginnen met als matrix L de eenheidsmatrix en U gelijk aan A:
Eerste stap
In de eerste stap zijn de factoren om de elementen onder de diagonaal in de eerste kolom van U op nul te krijgen, respectievelijk −1, 2 en −3. Die komen onder de diagonaal in de eerste kolom van L. In U vermenigvuldigen we de eerste rij met −1 en trekken die af van de tweede rij; dat wordt de nieuwe tweede rij; analoog voor de derde en vierde rij. Dit geeft als tussenstand:
(Men kan nagaan dat het product van deze twee matrices de oorspronkelijk matrix A is)
Tweede stap
Om de elementen onder de diagonaal in de tweede kolom van U op nul te krijgen moeten we van de derde rij van U de tweede rij van U vermenigvuldigd met −5 aftrekken, en van de vierde rij van U de tweede rij vermenigvuldigd met 8. Dit geeft:
Derde stap
In de laatste stap staat het enige overgebleven element onder de hoofddiagonaal van U in de derde kolom. Door de derde rij van U te vermenigvuldigen met 3 en af te trekken van de vierde rij wordt dit nul:
Daarmee is de decompositie van A in LU beëindigd. In dit geval was er geen verwisseling van rijen nodig.
Bemerkingen
Om een stelsel van lineaire vergelijkingen op te lossen gaat men als volgt te werk:
- Vorm de matrices en : . We noemen het (voorlopig onbekende) product .
- Los op door voorwaartse substitutie.
- Los op door achterwaartse substitutie.
Wanneer bijvoorbeeld , vinden we achtereenvolgens:
- waaruit
- waaruit
- waaruit
en:
- of
- waaruit
- waaruit
- waaruit
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 L te bewaren, die per definitie gelijk zijn aan 1. De rij-permutaties kunnen bijgehouden worden in een permutatievector van n elementen; als twee rijen verwisseld worden worden de corresponderende elementen in de permutatievector verwisseld. De Doolittle-decompositie gelijkt sterk op de Crout-decompositie. Dit is ook een LU-decompositie met dit verschil dat in een Crout-decompositie de elementen op de hoofddiagonaal van de bovendriehoeksmatrix U gelijk zijn aan 1.