title: Cholesky-decompositie
text: De Cholesky-decompositie van een positief-definiete Hermitische matrix, of in het reële geval, een positief-definiete symmetrische matrix, is een LU-decompositie van de vorm:
  
   
  
  waarin  een benedendriehoeksmatrix is.  is de getransponeerde matrix van .  noemt men de Choleskyfactor van .
  
  De Cholesky-decompositie is genoemd naar de Franse militaire officier en wiskundige André-Louis Cholesky (1875-1918), die kort voor het einde van de Eerste Wereldoorlog sneuvelde. Het is niet exact bekend wanneer Cholesky zijn methode bedacht. Hij publiceerde ze zelf niet; ze werd wel indirect bekend dankzij een artikel van commandant Benoît in het Bulletin géodesique van 1924, waarin hij het "procédé du commandant Cholesky" beschreef. Later is een manuscript van Cholesky uit 1910 gevonden waarin hij zijn methode gedetailleerd beschrijft, onder de titel "Sur la résolution numérique des Systèmes d'équations linéaires."
  
  Methode 
  De Cholesky-factor van een -matrix  kan met het volgende algoritme recursief berekend worden in  stappen. Elke stap levert een kolom van  op.
  
  De vergelijking  wordt uitgeschreven als:
   
  
  Hieruit wordt de eerste kolom van  bepaald:
    (het element op de diagonaal)
    (dit is de rest van de kolom).
  
  Rest nog de onbekende matrix , die volgt uit de vergelijking:
   
  ( is het kruisproduct van de kolomvector en de rijvector )
  
  Dit is opnieuw een vergelijking van de vorm , maar nu met een matrix die een kolom en een rij minder telt. Het bovenstaande kan nu herhaald worden om de eerste kolom van  te vinden, wat de tweede kolom van  is, en zo verder tot er een 1x1-matrix overblijft.
  
  De methode van Cholesky is numeriek stabiel. In de Cholesky-decompositie hoeft men geen rijen of kolommen te verwisselen om te voorkomen dat men een pivotgetal nul bekomt. Maar de volgorde waarin de kolommen en rijen worden geëlimineerd, kan wel een grote invloed hebben op de looptijd van het algoritme. Dit is zeker zo als de matrix schaarsbezet is (een ijle matrix met veel nullen). Om de symmetrie te behouden moet men in de Cholesky-methode steeds rijen samen met de corresponderende kolommen verwisselen. Hiervoor houdt men een permutatiematrix  bij, zodat de decompositie wordt uitgedrukt als:
   
  
  Door een zorgvuldige keuze van de eliminatievolgorde kan men een Cholesky-factor  bekomen die zeer schaarsbezet is en snel berekend kan worden (zie verder bij Grafentheoretische interpretatie).
  
  Voorbeeld 
  We zoeken de decompositie van de matrix
  
  Eerste stap 
   
  
  De eerste kolom van  wordt:
   
   
   
  
  De 2x2-matrix voor de volgende stap is
  
  Tweede stap 
  De tweede stap gaat op dezelfde manier als de eerste stap:
   
   
  
  Blijft over de matrixvergelijking met 1×1-matrices:
  
  Derde en laatste stap 
  Uit de vorige vergelijking volgt eenvoudigweg dat
   
  
  De Cholesky-decompositie van  is dus
  
  Symmetrische vorm 
  De symmetrische vorm van de Cholesky-decompositie is:
  
   
  
  Hierin is  een benedendriehoeksmatrix met 1 op de hoofddiagonaal, en  is een diagonaalmatrix.
  
  Uit
   
  
  volgt
   .
  
  De elementen in  zijn de kwadraten van de elementen op de hoofddiagonaal van . De kolommen van  zijn gelijk aan de kolommen van  gedeeld door de elementen op de hoofddiagonaal van .
  
  In het bovenstaande voorbeeld wordt dit
   
  
  Dus
  
  Oplossen van een stelsel vergelijkingen 
  Om een stelsel van lineaire vergelijkingen  op te lossen via Cholesky-decompositie gaat men als volgt te werk:
   Bereken de matrix  en los  op in twee stappen:
   los eerst  op met voorwaartse substitutie;
   los dan  op met achterwaartse substitutie.
  
  Inverse matrix 
  De diagonaalelementen van de driehoeksmatrix  zijn verschillend van nul. Dat betekent dat  inverteerbaar is. De determinant ervan is gelijk aan het product van de elementen op de hoofddiagonaal. 
  
  De inverse matrix van  wordt dan gegeven door:
   
  
  De inverse matrix van een benedendriehoeksmatrix is ook een benedendriehoeksmatrix en kan snel, element per element, berekend worden met een recursieformule.
  
  Interpretatie met grafen 
  Elke symmetrische vierkante -matrix  kan beschouwd worden als de bogenmatrix van een graaf  met  knopen: er is een zijde tussen de knopen  en  als het matrixelement  verschilt van nul.
  
  Merk op: de elementen op de diagonaal van  komen overeen met een lus in elke knoop; deze worden verder niet meer beschouwd (ze zijn toch steeds verschillend van nul).
  
  De buren van knoop  zijn de knopen die door een zijde verbonden zijn met 
  
  De Cholesky-decompositie kan men nu beschrijven als een opeenvolging van eliminaties van een knoop uit  zodat een reeks eliminatiegrafen ontstaat met telkens een knoop minder:
   
  
  De -de stap in de decompositie correspondeert met de afleiding van  uit  door verwijdering van de knoop  en van de zijden die in die knoop samenkomen. Indien nodig moeten nieuwe zijden worden toegevoegd, zodat de buren van knoop  paarsgewijs verbonden zijn. Deze nieuwe zijden noemt men "opvulling" (fill-in).
  
  De nul/niet-nul-structuur van de Choleskyfactor  kan men uit de opeenvolgende eliminatiegrafen afleiden: de elementen in de -de kolom van  die verschillen van nul, staan op de rijen met de nummers van de buren van knoop  in de graaf  Het element op de diagonaal komt daar nog bij.
  
  Men wenst de hoeveelheid opvulling zo laag mogelijk te houden en  het aantal nulelementen in  zo hoog mogelijk. Dat vermindert het latere rekenwerk en dit is vooral belangrijk voor zeer grote maar schaarsbezette ijle matrices, die bijvoorbeeld in de eindige-elementenmethode voorkomen. Men kan dit beïnvloeden door de rijen en kolommen in de matrix  geschikt te rangschikken vooraleer de Cholesky-decompositie te maken, zoals het volgende voorbeeld duidelijk maakt:
  
  Voorbeeld
  
  Alternatief 1 
  Stel de matrix  heeft de volgende nul/niet-nul-structuur
   
  
  De corresponderende graaf is:
  
  In de eerste eliminatiestap verwijderen we knoop 1 en de zijden 1-3 en 1-4:
  
  Knoop 1 heeft als buren 3 en 4 en omdat deze niet verbonden zijn, moeten we de graaf opvullen met een nieuwe zijde 3-4. Dit geeft de volgende eliminatiegraaf:
  
  Knoop 2 heeft buren 5 en 6; dit betekent dat in de tweede kolom van de Choleskyfactor  de elementen in rijen 5 en 6 niet nul zijn (naast die op de diagonaal). Knoop 2 en kde zijden 2-6 en 2-5 worden geëlimineerd en er moet een nieuwe zijde 5-6 worden toegevoegd, wat als resultaat oplevert:
  
  Knoop 3 heeft buren 4 en 5. De eliminatie van knoop 3 vereist opnieuw de opvulling met een zijde 4-5:
  
  Knoop 4 heeft als enige buur 5; er is geen opvulling nodig. De volgende eliminatiestappen zijn eenvoudig:
  
  en ten slotte
  
  De nul/niet-nul-structuur van de Choleskyfactor van  is bijgevolg:
  
   
  
  Er zijn in totaal 3 "fill-in" zijden toegevoegd en er zijn zeven nul-elementen in  beneden de diagonaal.
  
  Alternatief 2 
  Neem ter vergelijking volgende matrix met als nul/niet-nul-structuur:
  
   
  
  Matrix  is afgeleid uit ' door rijen en kolommen 3 te verwisselen met 4, en 2 met 6. De corresponderende graaf is:
  
  De eerste eliminatiestap is dezelfde als in alternatief 1. We verwijderen knoop 1 en de zijden 1-3 en 1-4:
  
  Hier moeten we ook een nieuwe zijde 3-4 toevoegen. Dit geeft de volgende eliminatiegraaf:
  
  Knoop 2 heeft een enkele buur, 6. De eliminatie van knoop 2 vereist dus geen opvulling:
  
  Hetzelfde geldt voor knoop 3, met als enige buur 4:
  
  De eliminatie van knopen 4 en 5 verloopt verder analoog als in alternatief 1, zonder dat er opvulling nodig is:
  
  en ten slotte
  
  De nul/niet-nul-structuur van de Choleskyfactor van  is:
  
   
  
  Er is in dit geval slechts 1 "fill-in"-zijde toegevoegd en er zijn negen nul-elementen in  tegenover zeven in het eerste alternatief.
  
  De grafentheoretische analyse van de Cholesky-decompositie werd voor het eerst gedetailleerd uitgevoerd door Donald J. Rose in zijn doctoraatsthesis aan de Harvard-universiteit uit 1970. Het bepalen van een optimale volgorde van de vergelijkingen om de fill-in te minimaliseren (het minimum-fill-problem) is een NP-volledig probleem waarvoor verschillende algoritmen ontwikkeld zijn.
  
  Men spreekt over een perfecte eliminatie-volgorde wanneer er geen enkele nieuwe kant moet toegevoegd worden in de eliminatie. Een graaf heeft een perfecte eliminatie-volgorde als en slechts als het een chordale graaf is (dit is een getriangulariseerde graaf). In een chordale graaf heeft elke cyclus van lengte 4 of meer een koorde, dit is een kant tussen twee niet-opeenvolgende knopen in de cyclus. Het minimum fill-in problem is equivalent aan het vinden van het minimumaantal kanten dat men aan een graaf moet toevoegen om er een chordale graaf van te maken.
  
  De matrix  uit het bovenstaande voorbeeld en zijn bijhorende graaf konden zonder opvulling en met een perfecte eliminatie-volgorde verwerkt door in plaats van de volgorde 1-2-3-4-5-6, de volgorde 4-1-3-5-2-6 te nemen.
  
  Matrixdecompositie