title: Crout-decompositie
text: 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, een wiskundige aan het Massachusetts Institute of Technology die de methode in 1941 heeft beschreven.
  
  Beschrijving
  
  Via Gauss-eliminatie 
  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 
  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 maakt de eerste rij van  volledig.
    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.
  
  Voorbeeld 
  Gegeven is de matrix:
   
  
  Neem als matrix  de eenheidsmatrix en  gelijk aan .
  
  Eerste stap 
  Deel de eerste rij van  door 3, en vermenigvuldig de eerste rij achtereenvolgens met −3, 6, 9 en trek ze af van de tweede, derde en vierde rij zodat de elementen onder de diagonaal in de eerste kolom van  nul worden. 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 
  Om het element op de hoofddiagonaal in de tweede kolom van  op een te krijgen, moet de tweede rij van  gedeeld worden door −2. Om de rest van de tweede kolom van  op nul te krijgen, moet de tweede rij van  achtereenvolgens vermenigvuldig worden met 10 en −16, en afgetrokken van de derde, respectievelijk 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 
  In de derde stap wordt de derde rij van  gedeeld door −1, waarna de derde rij vermenigvuldig wordt met −3 en afgetrokken van de vierde rij. De factoren −1 en −3 gaan naar de derde kolom van :
  
  Vierde stap 
  In de vierde en laatste stap moet alleen nog het element in de linker benedenhoek van  op een gebracht worden, 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 
  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.
  
  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.
  
  Websites 
   Cholesky, Doolittle and Crout Factorization
  
  Matrixdecompositie