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 en een bovendriehoeksmatrix In de matrix 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 een -matrix met elementen De Crout-decompositie is formeel gezien een Gauss-eliminatie. Het algoritme begint dan met als de -eenheidsmatrix en gelijk aan In stappen wordt herleid tot een bovendriehoeksmatrix en tot een benedendriehoeksmatrix, zodanig dat het matrixproduct steeds gelijk blijft aan

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

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

Rechtstreekse berekening[bewerken]

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

enz. (dit is de eerste kolom van )
of
of enz. (dit vervolledigt de eerste rij van )
of
of enz. (dit vervolledigt de tweede kolom van )

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

Rekenvoorbeeld[bewerken]

Gegeven:

We beginnen met als matrix de eenheidsmatrix en gelijk aan

Eerste stap[bewerken]

In de eerste stap delen we de eerste rij van 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 nul zijn. De getallen 3, −3, 6 en 9 kopiëren we naar de eerste kolom van die dus een kopie wordt van de eerste kolom van Dit geeft als tussenstand:

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

Tweede stap[bewerken]

Om het elementen op de hoofddiagonaal in de tweede kolom van op een te krijgen moeten we de tweede rij van delen door −2. Om de rest van de tweede kolom van op nul te krijgen moeten we de tweede rij van 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 die is dus een kopie van de tweede kolom van vanaf de tweede rij. Dit geeft:

Derde stap[bewerken]

In de derde stap delen we de derde rij van 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

Vierde stap[bewerken]

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

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

Opmerkingen[bewerken]

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

  1. Vorm de matrices en : . We noemen het (voorlopig onbekende) product .
  2. Los op door voorwaartse substitutie.
  3. Los op door achterwaartse substitutie.

Als bijvoorbeeld vinden we achtereenvolgens:

  • of
  • waaruit
  • waaruit
  • waaruit

en:

  • waaruit
  • waaruit
  • waaruit

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

Externe links[bewerken]