Cholesky nedbrydning - Cholesky decomposition

I lineær algebra , den Cholesky-dekomposition eller Cholesky faktorisering (udtales / ʃ ə l ɛ s k i / shə- LES -kee ) er en nedbrydning af en hermitisk , positiv-bestemt matrix i produktet af en lavere triangulære matrix og dens konjugat transponere , hvilket er nyttigt til effektive numeriske løsninger, f.eks. Monte Carlo -simuleringer . Det blev opdaget af André-Louis Cholesky for rigtige matricer. Når den er anvendelig, er den Cholesky nedbrydning omtrent dobbelt så effektiv som LU nedbrydningen til løsning af systemer af lineære ligninger .

Udmelding

Cholesky-nedbrydningen af ​​en hermitisk positiv-bestemt matrix A er en nedbrydning af formen

${\ displaystyle \ mathbf {A} = \ mathbf {LL} ^{*},}$

hvor L er en lavere trekantet matrix med reelle og positive diagonale firmaer, og L * betegner konjugerede transponerede af L . Hver hermitisk positiv-bestemt matrix (og dermed også enhver reelt værdsat symmetrisk positiv-bestemt matrix) har en unik Cholesky-nedbrydning.

Det omvendte holder trivielt: Hvis A kan skrives som LL * for nogle inverterbare L , lavere trekantede eller på anden måde, så er A hermitisk og positiv bestemt.

Når A er en reel matrix (dermed symmetrisk positiv-bestemt), kan faktoriseringen skrives

${\ displaystyle \ mathbf {A} = \ mathbf {LL} ^{\ mathsf {T}},}$

hvor L er en reel lavere trekantet matrix med positive diagonale poster.

Positive semidefinite matricer

Hvis en hermitisk matrix A kun er positiv semidefinit, i stedet for positiv bestemt, så har den stadig en dekomponering af formen A = LL *, hvor de diagonale poster i L må være nul. Nedbrydningen behøver ikke at være unik, f.eks .:

${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}} = \ mathbf {L} \ mathbf {L} ^{*}, \ quad \ quad \ mathbf {L} = {\ begin {bmatrix } 0 & 0 \\\ cos \ theta & \ sin \ theta \ end {bmatrix}}.}$

Men hvis rangen A er r , så er der en unik lavere trekantet L med nøjagtigt r positive diagonale elementer og n - r kolonner, der indeholder alle nuller.

Alternativt kan nedbrydningen gøres unik, når et svingbart valg er løst. Formelt, hvis A er en n × n positiv semidefinit matrix af rang r , så er der mindst en permutationsmatrix P sådan, at PAP ^T har en unik nedbrydning af formen PAP ^T = LL ^* med , hvor L ₁ er en r × r nedre trekantet matrix med positiv diagonal. ${\ displaystyle \ mathbf {L} = {\ begin {bmatrix} \ mathbf {L} _ {1} & 0 \\\ mathbf {L} _ {2} & 0 \ end {bmatrix}}}$

LDL -nedbrydning

En nært beslægtet variant af den klassiske Cholesky -nedbrydning er LDL -nedbrydningen,

${\ displaystyle \ mathbf {A} = \ mathbf {LDL} ^{*},}$

hvor L er en trekantet (unitriangulær) matrix i den nedre enhed , og D er en diagonal matrix. Det vil sige, at de diagonale elementer i L skal være 1 på bekostning af indførelse af en yderligere diagonal matrix D i nedbrydningen. Den største fordel er, at LDL -nedbrydningen kan beregnes og bruges med stort set de samme algoritmer, men undgår at udtrække kvadratrødder.

Af denne grund kaldes LDL-nedbrydningen ofte den kvadratrodfrie Cholesky- nedbrydning. For rigtige matricer har faktoriseringen formen A = LDL ^T og omtales ofte som LDLT -dekomponering (eller LDL ^T -dekomponering eller LDL ′). Det er nært forbundet med eigendecomposition af reelle symmetriske matricer , A = QΛQ ^T .

LDL -nedbrydningen er relateret til den klassiske Cholesky -nedbrydning af formen LL * som følger:

${\ displaystyle \ mathbf {A} = \ mathbf {LDL} ^{*} = \ mathbf {L} \ mathbf {D} ^{1/2} \ venstre (\ mathbf {D} ^{1/2} \ højre) ^{*} \ mathbf {L} ^{*} = \ mathbf {L} \ mathbf {D} ^{1/2} \ venstre (\ mathbf {L} \ mathbf {D} ^{1/2 } \ højre)^{*}.}$

I modsætning hertil i betragtning af den klassiske Cholesky nedbrydning af en positiv bestemt matrix, hvis S er en diagonal matrix, der indeholder hoveddiagonalen af , kan et A nedbrydes som hvor ${\ displaystyle \ mathbf {A} = \ mathbf {C} \ mathbf {C} ^{*}}$${\ displaystyle \ mathbf {C}}$${\ displaystyle \ mathbf {L} \ mathbf {D} \ mathbf {L} ^{*}}$

${\ displaystyle \ mathbf {L} = \ mathbf {C} \ mathbf {S} ^{-1}}$ (dette skalerer hver kolonne for at lave diagonale elementer 1),

${\ displaystyle \ mathbf {D} = \ mathbf {S} ^{2}.}$

Hvis A er positiv bestemt, er de diagonale elementer i D alle positive. Positiv semidefinite A , en eksisterer nedbrydning, hvor antallet af ikke-nul elementer på diagonalen D er præcis rang af A . Nogle ubestemte matricer, for hvilke der ikke findes nogen Cholesky-dekomponering, har en LDL-dekomponering med negative poster i D : det er tilstrækkeligt, at de første n −1 førende hovedmindre i A er ikke ental. ${\ displaystyle \ mathbf {L} \ mathbf {D} \ mathbf {L} ^{*}}$

Eksempel

Her er den Cholesky nedbrydning af en symmetrisk reel matrix:

${\ displaystyle {\ begin {align} \ left ({\ begin {array} {*{3} {r}} 4 & 12 & -16 \\ 12 & 37 & -43 \\-16 & -43 & 98 \\\ end {array}} \ højre) = \ venstre ({\ begin {array} {*{3} {r}} 2 & 0 & 0 \\ 6 & 1 & 0 \\-8 & 5 & 3 \\\ slut {array}} \ højre) \ venstre ({\ begin {array} { *{3} {r}} 2 & 6 & -8 \\ 0 & 1 & 5 \\ 0 & 0 & 3 \\\ slut {array}} \ højre). \ End {align}}}$

Og her er dens LDL ^T -nedbrydning:

${\ displaystyle {\ begin {align} \ left ({\ begin {array} {*{3} {r}} 4 & 12 & -16 \\ 12 & 37 & -43 \\-16 & -43 & 98 \\\ end {array}} \ højre) & = \ venstre ({\ begin {array} {*{3} {r}} 1 & 0 & 0 \\ 3 & 1 & 0 \\-4 & 5 & 1 \\\ slut {array}} \ højre) \ venstre ({\ begin {array} {*{3} {r}} 4 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 9 \\\ slut {array}} \ højre) \ venstre ({\ begin {array} {*{3} {r}} 1 & 3 & -4 \\ 0 & 1 & 5 \\ 0 & 0 & 1 \\\ slut {array}} \ højre). \ End {align}}}$

Ansøgninger

Cholesky -nedbrydningen bruges hovedsageligt til den numeriske løsning af lineære ligninger . Hvis A er symmetrisk og positiv bestemt, kan vi løse ved først at beregne Cholesky -nedbrydningen , derefter løse for y ved fremadrettet substitution og til sidst løse for x ved tilbagesubstitution . ${\ displaystyle \ mathbf {Ax} = \ mathbf {b}}$${\ displaystyle \ mathbf {Ax} = \ mathbf {b}}$${\ displaystyle \ mathbf {A} = \ mathbf {LL} ^{\ mathrm {*}}}$${\ displaystyle \ mathbf {Ly} = \ mathbf {b}}$${\ displaystyle \ mathbf {L^{*} x} = \ mathbf {y}}$

En alternativ måde at eliminere at tage kvadratrødder i nedbrydningen er at beregne Cholesky -nedbrydningen , derefter løse for y og til sidst løse . ${\ displaystyle \ mathbf {LL} ^{\ mathrm {*}}}$${\ displaystyle \ mathbf {A} = \ mathbf {LDL} ^{\ mathrm {*}}}$${\ displaystyle \ mathbf {Ly} = \ mathbf {b}}$${\ displaystyle \ mathbf {DL} ^{\ mathrm {*}} \ mathbf {x} = \ mathbf {y}}$

For lineære systemer, der kan sættes i symmetrisk form, er Cholesky -nedbrydningen (eller dens LDL -variant) den foretrukne metode til overlegen effektivitet og numerisk stabilitet. Sammenlignet med LU -nedbrydningen er den omtrent dobbelt så effektiv.

Lineære mindste firkanter

Systemer af formen Ax = b med A symmetrisk og positiv bestemt opstår ganske ofte i applikationer. For eksempel er de normale ligninger i lineære mindste kvadrater problemer af denne form. Det kan også ske, at matrix A kommer fra en energifunktionel, som skal være positiv ud fra fysiske overvejelser; dette sker ofte i den numeriske løsning af partielle differentialligninger .

Ikke-lineær optimering

Ikke-lineære multivariatfunktioner kan minimeres over deres parametre ved hjælp af varianter af Newtons metode kaldet kvasi-Newton- metoder. Ved iteration k træder søgningen i en retning defineret ved at løse for , hvor er trinretningen, er gradienten og er en tilnærmelse til den hessiske matrix dannet ved at gentage opdateringer af rang 1 ved hver iteration. To kendte opdateringsformler kaldes Davidon – Fletcher – Powell (DFP) og Broyden – Fletcher – Goldfarb – Shanno (BFGS). Tab af den positivt bestemte betingelse ved afrundingsfejl undgås, hvis man i stedet for at opdatere en tilnærmelse til det inverse af hessianerne opdaterer den koleskiske nedbrydning af en tilnærmelse af selve den hessiske matrix. ${\ displaystyle p_ {k}}$${\ displaystyle B_ {k} p_ {k} =-g_ {k}}$${\ displaystyle p_ {k}}$${\ displaystyle p_ {k}}$${\ displaystyle g_ {k}}$${\ displaystyle B_ {k}}$

Monte Carlo -simulering

Cholesky -nedbrydningen bruges almindeligvis i Monte Carlo -metoden til simulering af systemer med flere korrelerede variabler. Den kovariansmatricen dekomponeres til opnåelse nederste trekantede L . Anvendelse af dette på en vektor af ikke -korrelerede prøver u producerer en prøvevektor Lu med kovariansegenskaberne i systemet, der modelleres.

Det følgende forenklede eksempel viser den økonomi, man får fra Cholesky -nedbrydningen: Antag, at målet er at generere to korrelerede normale variabler og med en given korrelationskoefficient . For at opnå dette er det nødvendigt først at generere to ukorrelerede gaussiske tilfældige variabler, og som kan gøres ved hjælp af en Box – Muller -transformation . I betragtning af den nødvendige korrelationskoefficient kan de korrelerede normale variabler opnås via transformationerne og . ${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ displaystyle \ rho}$${\ displaystyle z_ {1}}$${\ displaystyle z_ {2}}$${\ displaystyle \ rho}$${\ displaystyle x_ {1} = z_ {1}}$${\ textstyle x_ {2} = \ rho z_ {1}+{\ sqrt {1- \ rho ^{2}}} z_ {2}}$

Kalman filtre

Uparfumerede Kalman-filtre bruger normalt Cholesky-nedbrydningen til at vælge et sæt såkaldte sigma-punkter. Kalman filter sporer gennemsnitlige tilstand af et system som en vektor x med længden N og kovariansen som en N × N matrix P . Matrixen P er altid positiv semi-bestemt og kan opdeles i LL ^T . Søjlerne L kan tilføjes og trækkes fra middelværdien x for at danne et sæt 2 N vektorer kaldet sigmapunkter . Disse sigma -punkter indfanger fuldstændigt systemtilstandens middelværdi og kovarians.

Matrix inversion

Den eksplicitte omvendt af en hermitisk matrix kan beregnes ved Cholesky -dekomponering på en måde, der ligner løsning af lineære systemer, ved hjælp af operationer ( multiplikationer). Hele inversionen kan endda udføres effektivt på stedet. ${\ displaystyle n^{3}}$${\ displaystyle {\ tfrac {1} {2}} n^{3}}$

En ikke-hermitisk matrix B kan også vendes ved hjælp af følgende identitet, hvor BB * altid vil være hermitisk:

${\ displaystyle \ mathbf {B} ^{-1} = \ mathbf {B} ^{*} (\ mathbf {BB} ^{*}) ^{-1}.}$

Beregning

Der er forskellige metoder til beregning af Cholesky nedbrydning. Beregningskompleksiteten af ​​almindeligt anvendte algoritmer er generelt O ( n ³ ). De nedenfor beskrevne alle algoritmer involvere om (1/3) n ³ flops ( n ³ /6 multiplikationer og det samme antal af tilsætninger) for rigtige varianter og (4/3) n ³ flops for komplekse varianter, hvor n er størrelsen af matricen A . Derfor har de halvdelen af ​​omkostningerne ved LU -nedbrydning , der bruger 2 n ³ /3 FLOP'er (se Trefethen og Bau 1997).

Hvilken af ​​nedenstående algoritmer er hurtigere afhænger af detaljerne i implementeringen. Generelt vil den første algoritme være lidt langsommere, fordi den får adgang til dataene på en mindre regelmæssig måde.

Cholesky -algoritmen

Den Cholesky-algoritmen , anvendes til at beregne nedbrydning matrix L , er en modificeret version af Gauss-eliminering .

Den rekursive algoritme starter med i  : = 1 og

A ⁽¹⁾  : = A .

I trin i har matrixen A ^{( i )} følgende form:

${\ displaystyle \ mathbf {A} ^{(i)} = {\ begin {pmatrix} \ mathbf {I} _ {i-1} & 0 & 0 \\ 0 & a_ {i, i} & \ mathbf {b} _ {i } ^{*} \\ 0 & \ mathbf {b} _ {i} & \ mathbf {B} ^{(i)} \ end {pmatrix}},}$

hvor I _{i −1} betegner identitetsmatricen for dimension i - 1.

Hvis vi nu definerer matrixen L _i ved

${\ displaystyle \ mathbf {L} _ {i}: = {\ begin {pmatrix} \ mathbf {I} _ {i-1} & 0 & 0 \\ 0 & {\ sqrt {a_ {i, i}}} & 0 \\ 0 & {\ frac {1} {\ sqrt {a_ {i, i}}}} \ mathbf {b} _ {i} & \ mathbf {I} _ {ni} \ end {pmatrix}},}$

(bemærk at a _{i, i} > 0 da A ^{( i )} er positiv bestemt), så kan vi skrive A ^{( i )} som

${\ displaystyle \ mathbf {A} ^{(i)} = \ mathbf {L} _ {i} \ mathbf {A} ^{(i+1)} \ mathbf {L} _ {i} ^{*} }$

hvor

${\ displaystyle \ mathbf {A} ^{(i+1)} = {\ begin {pmatrix} \ mathbf {I} _ {i-1} & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & \ mathbf {B} ^{(i )}-{\ frac {1} {a_ {i, i}}} \ mathbf {b} _ {i} \ mathbf {b} _ {i}^{*} \ end {pmatrix}}.}$

Bemærk, at b _i b * _i er et ydre produkt , derfor kaldes denne algoritme for den ydre produktversion i (Golub & Van Loan).

Vi gentager dette for i fra 1 til n . Efter n trin, får vi A ^{( n + 1)} = I . Derfor beregnes den nedre trekantede matrix L, vi leder efter, som

${\ displaystyle \ mathbf {L}: = \ mathbf {L} _ {1} \ mathbf {L} _ {2} \ dots \ mathbf {L} _ {n}.}$

Algoritmerne Cholesky – Banachiewicz og Cholesky – Crout

Adgangsmønster (hvidt) og skrivemønster (gul) til den på plads Cholesky — Banachiewicz-algoritme på en 5 × 5 matrix

Hvis vi skriver ligningen ud

${\ displaystyle {\ begin {align} \ mathbf {A} = \ mathbf {LL} ^{T} & = {\ begin {pmatrix} L_ {11} & 0 & 0 \\ L_ {21} & L_ {22} & 0 \\ L_ {31} & L_ {32} & L_ {33} \\\ slut {pmatrix}} {\ begin {pmatrix} L_ {11} & L_ {21} & L_ {31} \\ 0 & L_ {22} & L_ {32} \\ 0 & 0 & L_ {33} \ end {pmatrix}} \\ [8pt] & = {\ begin {pmatrix} L_ {11}^{2} && ({\ text {symmetric}}) \\ L_ {21} L_ {11 } & L_ {21}^{2}+L_ {22}^{2} & \\ L_ {31} L_ {11} & L_ {31} L_ {21}+L_ {32} L_ {22} & L_ {31} ^{2}+L_ {32}^{2}+L_ {33}^{2} \ end {pmatrix}}, \ end {align}}}$

får vi følgende:

${\ displaystyle {\ begin {align} \ mathbf {L} = {\ begin {pmatrix} {\ sqrt {A_ {11}}} & 0 & 0 \\ A_ {21}/L_ {11} & {\ sqrt {A_ { 22} -L_ {21}^{2}}} & 0 \\ A_ {31}/L_ {11} og \ venstre (A_ {32} -L_ {31} L_ {21} \ højre)/L_ {22} & {\ sqrt {A_ {33} -L_ {31}^{2} -L_ {32}^{2}}} \ end {pmatrix}} \ end {align}}}$

og derfor følgende formler for posterne i L :

${\ displaystyle L_ {j, j} = (\ pm) {\ sqrt {A_ {j, j}-\ sum _ {k = 1}^{j-1} L_ {j, k}^{2}} },}$

${\ displaystyle L_ {i, j} = {\ frac {1} {L_ {j, j}}} \ venstre (A_ {i, j}-\ sum _ {k = 1}^{j-1} L_ {i, k} L_ {j, k} \ right) \ quad {\ text {for}} i> j.}$

For komplekse og reelle matricer er inkonsekventielle vilkårlige tegnændringer af diagonale og tilhørende off-diagonalelementer tilladt. Udtrykket under kvadratroden er altid positivt, hvis A er reelt og positivt bestemt.

For kompleks hermitisk matrix gælder følgende formel:

${\ displaystyle L_ {j, j} = {\ sqrt {A_ {j, j}-\ sum _ {k = 1}^{j-1} L_ {j, k} L_ {j, k}^{* }}},}$

${\ displaystyle L_ {i, j} = {\ frac {1} {L_ {j, j}}} \ venstre (A_ {i, j}-\ sum _ {k = 1}^{j-1} L_ {i, k} L_ {j, k}^{*} \ right) \ quad {\ text {for}} i> j.}$

Så vi kan beregne ( i , j ) posten, hvis vi kender posterne til venstre og ovenfor. Beregningen er normalt arrangeret i en af ​​følgende ordrer:

• Den Cholesky-Banachiewicz algoritme starter fra det øverste venstre hjørne af matricen L og provenuet til at beregne matricen række for række.

  for (i = 0; i < dimensionSize; i++) {
      for (j = 0; j <= i; j++) {
          float sum = 0;
          for (k = 0; k < j; k++)
              sum += L[i][k] * L[j][k];
  
          if (i == j)
              L[i][j] = sqrt(A[i][i] - sum);
          else
              L[i][j] = (1.0 / L[j][j] * (A[i][j] - sum));
      }
  }
  

• Den Cholesky-Crout algoritme starter fra den øverste venstre hjørne af matricen L og fortsætter at beregne matrix søjle for søjle.

  for (j = 0; j < dimensionSize; j++) {
      float sum = 0;
      for (k = 0; k < j; k++) {
          sum += L[j][k] * L[j][k];
      }
      L[j][j] = sqrt(A[j][j] - sum);
  
      for (i = j + 1; i < dimensionSize; i++) {
          sum = 0;
          for (k = 0; k < j; k++) {
              sum += L[i][k] * L[j][k];
          }
          L[i][j] = (1.0 / L[j][j] * (A[i][j] - sum));
      }
  }
  

Begge adgangsmønstre tillader, at hele beregningen udføres på stedet, hvis det ønskes.

Beregningens stabilitet

Antag, at vi vil løse et velkonditioneret system af lineære ligninger. Hvis LU -nedbrydningen bruges, er algoritmen ustabil, medmindre vi bruger en slags drejestrategi. I sidstnævnte tilfælde afhænger fejlen af ​​matrixens såkaldte vækstfaktor, som normalt (men ikke altid) er lille.

Antag nu, at den Cholesky nedbrydning er gældende. Som nævnt ovenfor vil algoritmen være dobbelt så hurtig. Desuden er det ikke nødvendigt at dreje , og fejlen vil altid være lille. Specifikt, hvis vi vil løse Ax = b , og y betegner den beregnede løsning, løser y det forstyrrede system ( A + E ) y = b , hvor

${\ displaystyle \ | \ mathbf {E} \ | _ {2} \ leq c_ {n} \ varepsilon \ | \ mathbf {A} \ | _ {2}.}$

Her || · || ₂ er matricen 2-normen , c _n er en lille konstant afhængig af n , og ε betegner enheden afrunde .

En bekymring ved den Cholesky nedbrydning, man skal være opmærksom på, er brugen af ​​kvadratrødder. Hvis matrixen, der faktoriseres, er positiv bestemt efter behov, er tallene under kvadratrødderne altid positive i nøjagtig aritmetik . Desværre kan tallene blive negative på grund af afrundingsfejl , i hvilket tilfælde algoritmen ikke kan fortsætte. Dette kan dog kun ske, hvis matricen er meget dårligt betinget. En måde at løse dette på er ved at tilføje en diagonal korrektionsmatrix til matricen, der nedbrydes i et forsøg på at fremme den positive beslutsomhed. Selvom dette kan reducere nedbrydningens nøjagtighed, kan det være meget gunstigt af andre årsager; for eksempel, når du udfører Newtons metode til optimering , kan tilføjelse af en diagonal matrix forbedre stabiliteten, når den er langt fra det optimale.

LDL -nedbrydning

En alternativ form, der eliminerer behovet for at tage kvadratrødder, når A er symmetrisk, er den symmetriske ubestemt faktorisering

${\ displaystyle {\ begin {align} \ mathbf {A} = \ mathbf {LDL} ^{\ mathrm {T}} & = {\ begin {pmatrix} 1 & 0 & 0 \\ L_ {21} & 1 & 0 \\ L_ {31} & L_ {32} & 1 \\\ ende {pmatrix}} {\ begin {pmatrix} D_ {1} & 0 & 0 \\ 0 & D_ {2} & 0 \\ 0 & 0 & D_ {3} \\\ slut {pmatrix}} {\ begin {pmatrix } 1 & L_ {21} & L_ {31} \\ 0 & 1 & L_ {32} \\ 0 & 0 & 1 \\\ slut {pmatrix}} \\ [8pt] & = {\ begin {pmatrix} D_ {1} && (\ mathrm {symmetric} ) \\ L_ {21} D_ {1} & L_ {21}^{2} D_ {1}+D_ {2} & \\ L_ {31} D_ {1} & L_ {31} L_ {21} D_ {1 }+L_ {32} D_ {2} & L_ {31}^{2} D_ {1}+L_ {32}^{2} D_ {2}+D_ {3}. \ End {pmatrix}}. \ End {align}}}$

Følgende rekursive relationer gælder for posterne i D og L :

${\ displaystyle D_ {j} = A_ {jj}-\ sum _ {k = 1}^{j-1} L_ {jk}^{2} D_ {k},}$

${\ displaystyle L_ {ij} = {\ frac {1} {D_ {j}}} \ venstre (A_ {ij}-\ sum _ {k = 1}^{j-1} L_ {ik} L_ {jk } D_ {k} \ right) \ quad {\ text {for}} i> j.}$

Dette fungerer, så længe de genererede diagonale elementer i D forbliver ikke-nul. Nedbrydningen er derefter unik. D og L er reelle, hvis A er ægte.

For kompleks hermitisk matrix A gælder følgende formel:

${\ displaystyle D_ {j} = A_ {jj}-\ sum _ {k = 1}^{j-1} L_ {jk} L_ {jk}^{*} D_ {k},}$

${\ displaystyle L_ {ij} = {\ frac {1} {D_ {j}}} \ venstre (A_ {ij}-\ sum _ {k = 1}^{j-1} L_ {ik} L_ {jk }^{*} D_ {k} \ right) \ quad {\ text {for}} i> j.}$

Igen tillader adgangsmønsteret, at hele beregningen kan udføres på stedet, hvis det ønskes.

Blok variant

Når den bruges på ubestemt matricer, er LDL * -faktoriseringen kendt for at være ustabil uden omhyggelig drejning; specifikt kan elementerne i faktoriseringen vokse vilkårligt. En mulig forbedring er at udføre faktoriseringen på blokundermatricer, normalt 2 × 2:

${\ displaystyle {\ begin {align} \ mathbf {A} = \ mathbf {LDL} ^{\ mathrm {T}} & = {\ begin {pmatrix} \ mathbf {I} & 0 & 0 \\\ mathbf {L} _ {21} & \ mathbf {I} & 0 \\\ mathbf {L} _ {31} & \ mathbf {L} _ {32} & \ mathbf {I} \\\ end {pmatrix}} {\ begin {pmatrix } \ mathbf {D} _ {1} & 0 & 0 \\ 0 & \ mathbf {D} _ {2} & 0 \\ 0 & 0 & \ mathbf {D} _ {3} \\\ end {pmatrix}} {\ begin {pmatrix} \ mathbf {I} & \ mathbf {L} _ {21}^{\ mathrm {T}} & \ mathbf {L} _ {31}^{\ mathrm {T}} \\ 0 & \ mathbf {I} & \ mathbf {L} _ {32}^{\ mathrm {T}} \\ 0 & 0 & \ mathbf {I} \\\ end {pmatrix}} \\ [8pt] & = {\ begin {pmatrix} \ mathbf {D } _ {1} && (\ mathrm {symmetrisk)) \\\ mathbf {L} _ {21} \ mathbf {D} _ {1} & \ mathbf {L} _ {21} \ mathbf {D} _ { 1} \ mathbf {L} _ {21}^{\ mathrm {T}}+\ mathbf {D} _ {2} & \\\ mathbf {L} _ {31} \ mathbf {D} _ {1} & \ mathbf {L} _ {31} \ mathbf {D} _ {1} \ mathbf {L} _ {21}^{\ mathrm {T}}+\ mathbf {L} _ {32} \ mathbf {D } _ {2} & \ mathbf {L} _ {31} \ mathbf {D} _ {1} \ mathbf {L} _ {31}^{\ mathrm {T}}+\ mathbf {L} _ {32 } \ mathbf {D} _ {2} \ mathbf {L} _ {32}^{\ mathrm {T}}+\ mathbf {D} _ {3} \ end {pmatrix}}, \ end {align}} }$

hvor hvert element i matricerne ovenfor er en firkantet submatrix. Heraf følger disse analoge rekursive relationer:

${\ displaystyle \ mathbf {D} _ {j} = \ mathbf {A} _ {jj}-\ sum _ {k = 1}^{j-1} \ mathbf {L} _ {jk} \ mathbf {D } _ {k} \ mathbf {L} _ {jk}^{\ mathrm {T}},}$

${\ displaystyle \ mathbf {L} _ {ij} = \ left (\ mathbf {A} _ {ij}-\ sum _ {k = 1}^{j-1} \ mathbf {L} _ {ik} \ mathbf {D} _ {k} \ mathbf {L} _ {jk}^{\ mathrm {T}} \ right) \ mathbf {D} _ {j}^{-1}.}$

Dette indebærer matrixprodukter og eksplicit inversion, hvilket begrænser den praktiske blokstørrelse.

Opdatering af nedbrydning

En opgave, der ofte opstår i praksis, er, at man skal opdatere en Cholesky -nedbrydning. I flere detaljer, har man allerede beregnet Cholesky nedbrydning af nogle matrix , så man ændrer matricen på en eller anden måde i en anden matrix, sige , og man ønsker at beregne Cholesky nedbrydning af den opdaterede matrix: . Spørgsmålet er nu, om man kan bruge Cholesky -nedbrydningen af ​​det, der blev beregnet før til at beregne Cholesky -nedbrydningen af . ${\ displaystyle \ mathbf {A} = \ mathbf {L} \ mathbf {L} ^{*}}$${\ displaystyle \ mathbf {A}}$${\ displaystyle \ mathbf {A}}$${\ displaystyle {\ tilde {\ mathbf {A}}}}$${\ displaystyle {\ tilde {\ mathbf {A}}} = {\ tilde {\ mathbf {L}}} {\ tilde {\ mathbf {L}}}^{*}}$${\ displaystyle \ mathbf {A}}$${\ displaystyle {\ tilde {\ mathbf {A}}}}$

Opdatering af nummer ét

Det specifikke tilfælde, hvor den opdaterede matrix er relateret til matrixen ved , er kendt som en rang-en-opdatering . ${\ displaystyle {\ tilde {\ mathbf {A}}}}$${\ displaystyle \ mathbf {A}}$${\ displaystyle {\ tilde {\ mathbf {A}}} = \ mathbf {A} +\ mathbf {x} \ mathbf {x} ^{*}}$

Her er en funktion skrevet i Matlab- syntaks, der realiserer en rank-one-opdatering:

function [L] = cholupdate(L, x)
    n = length(x);
    for k = 1:n
        r = sqrt(L(k, k)^2 + x(k)^2);
        c = r / L(k, k);
        s = x(k) / L(k, k);
        L(k, k) = r;
        if k < n
            L((k+1):n, k) = (L((k+1):n, k) + s * x((k+1):n)) / c;
            x((k+1):n) = c * x((k+1):n) - s * L((k+1):n, k);
        end
    end
end

Rang-en nedjustering

En rang-on downdate ligner en rang-on opdatering, bortset fra at tilsætningen erstattes af subtraktion: . Dette virker kun, hvis den nye matrix stadig er positiv bestemt. ${\ displaystyle {\ tilde {\ mathbf {A}}} = \ mathbf {A} -\ mathbf {x} \ mathbf {x} ^{*}}$${\ displaystyle {\ tilde {\ mathbf {A}}}}$

Koden til rang-en-opdateringen vist ovenfor kan let tilpasses til at foretage en rang-en-nedgang: man skal blot erstatte de to tilføjelser i opgaven til rog L((k+1):n, k)med subtraktioner.

Tilføjelse og fjernelse af rækker og kolonner

Hvis vi har en symmetrisk og positiv bestemt matrix repræsenteret i blokform som ${\ displaystyle \ mathbf {A}}$

${\ displaystyle \ mathbf {A} = {\ begin {pmatrix} \ mathbf {A} _ {11} & \ mathbf {A} _ {13} \\\ mathbf {A} _ {13}^{\ mathrm { T}} & \ mathbf {A} _ {33} \\\ end {pmatrix}}}$

og dens øvre Cholesky -faktor

${\ displaystyle \ mathbf {L} = {\ begin {pmatrix} \ mathbf {L} _ {11} & \ mathbf {L} _ {13} \\ 0 & \ mathbf {L} _ {33} \\\ end {pmatrix}},}$

derefter for en ny matrix , som er den samme som, men med indsættelse af nye rækker og kolonner, ${\ displaystyle {\ tilde {\ mathbf {A}}}}$${\ displaystyle \ mathbf {A}}$

${\ displaystyle {\ begin {align} {\ tilde {\ mathbf {A}}} & = {\ begin {pmatrix} \ mathbf {A} _ {11} & \ mathbf {A} _ {12} & \ mathbf {A} _ {13} \\\ mathbf {A} _ {12}^{\ mathrm {T}} & \ mathbf {A} _ {22} & \ mathbf {A} _ {23} \\\ mathbf {A} _ {13}^{\ mathrm {T}} & \ mathbf {A} _ {23}^{\ mathrm {T}} & \ mathbf {A} _ {33} \\\ end {pmatrix} } \ end {align}}}$

vi er interesserede i at finde den Cholesky -faktorisering af , som vi kalder , uden direkte at beregne hele nedbrydningen. ${\ displaystyle {\ tilde {\ mathbf {A}}}}$${\ displaystyle {\ tilde {\ mathbf {S}}}}$

${\ displaystyle {\ begin {align} {\ tilde {\ mathbf {S}}} & = {\ begin {pmatrix} \ mathbf {S} _ {11} & \ mathbf {S} _ {12} & \ mathbf {S} _ {13} \\ 0 & \ mathbf {S} _ {22} & \ mathbf {S} _ {23} \\ 0 & 0 & \ mathbf {S} _ {33} \\\ slut {pmatrix}}. \ end {align}}}$

At skrive til løsningen af , som let kan findes til trekantede matricer, og til den koleskiske nedbrydning af , kan følgende relationer findes: ${\ displaystyle \ mathbf {A} \ setminus \ mathbf {b}}$${\ displaystyle \ mathbf {A} \ mathbf {x} = \ mathbf {b}}$${\ displaystyle {\ text {chol}} (\ mathbf {M})}$${\ displaystyle \ mathbf {M}}$

${\ displaystyle {\ begin {align} \ mathbf {S} _ {11} & = \ mathbf {L} _ {11}, \\\ mathbf {S} _ {12} & = \ mathbf {L} _ { 11}^{\ mathrm {T}} \ setminus \ mathbf {A} _ {12}, \\\ mathbf {S} _ {13} & = \ mathbf {L} _ {13}, \\\ mathbf { S} _ {22} & = \ mathrm {chol} \ left (\ mathbf {A} _ {22}-\ mathbf {S} _ {12}^{\ mathrm {T}} \ mathbf {S} _ { 12} \ højre), \\\ mathbf {S} _ {23} & = \ mathbf {S} _ {22}^{\ mathrm {T}} \ setminus \ left (\ mathbf {A} _ {23} -\ mathbf {S} _ {12}^{\ mathrm {T}} \ mathbf {S} _ {13} \ right), \\\ mathbf {S} _ {33} & = \ mathrm {chol} \ venstre (\ mathbf {L} _ {33}^{\ mathrm {T}} \ mathbf {L} _ {33}-\ mathbf {S} _ {23}^{\ mathrm {T}} \ mathbf {S } _ {23} \ right). \ End {align}}}$

Disse formler kan bruges til at bestemme Cholesky -faktoren efter indsættelse af rækker eller kolonner i en hvilken som helst position, hvis vi indstiller række- og kolonnedimensionerne korrekt (inklusive til nul). Det omvendte problem, når vi har

${\ displaystyle {\ begin {align} {\ tilde {\ mathbf {A}}} & = {\ begin {pmatrix} \ mathbf {A} _ {11} & \ mathbf {A} _ {12} & \ mathbf {A} _ {13} \\\ mathbf {A} _ {12}^{\ mathrm {T}} & \ mathbf {A} _ {22} & \ mathbf {A} _ {23} \\\ mathbf {A} _ {13}^{\ mathrm {T}} & \ mathbf {A} _ {23}^{\ mathrm {T}} & \ mathbf {A} _ {33} \\\ end {pmatrix} } \ end {align}}}$

med kendt Cholesky nedbrydning

${\ displaystyle {\ begin {align} {\ tilde {\ mathbf {S}}} & = {\ begin {pmatrix} \ mathbf {S} _ {11} & \ mathbf {S} _ {12} & \ mathbf {S} _ {13} \\ 0 & \ mathbf {S} _ {22} & \ mathbf {S} _ {23} \\ 0 & 0 & \ mathbf {S} _ {33} \\\ slut {pmatrix}} \ slut {align}}}$

og ønsker at bestemme Cholesky -faktoren

${\ displaystyle {\ begin {align} \ mathbf {L} & = {\ begin {pmatrix} \ mathbf {L} _ {11} & \ mathbf {L} _ {13} \\ 0 & \ mathbf {L} _ {33} \\\ end {pmatrix}} \ end {align}}}$

af matricen med rækker og kolonner fjernet, ${\ displaystyle \ mathbf {A}}$

${\ displaystyle {\ begin {align} \ mathbf {A} & = {\ begin {pmatrix} \ mathbf {A} _ {11} & \ mathbf {A} _ {13} \\\ mathbf {A} _ { 13}^{\ mathrm {T}} & \ mathbf {A} _ {33} \\\ end {pmatrix}}, \ end {align}}}$

giver følgende regler:

${\ displaystyle {\ begin {align} \ mathbf {L} _ {11} & = \ mathbf {S} _ {11}, \\\ mathbf {L} _ {13} & = \ mathbf {S} _ { 13}, \\\ mathbf {L} _ {33} & = \ mathrm {chol} \ left (\ mathbf {S} _ {33}^{\ mathrm {T}} \ mathbf {S} _ {33} +\ mathbf {S} _ {23}^{\ mathrm {T}} \ mathbf {S} _ {23} \ right). \ end {align}}}$

Bemærk, at ligningerne ovenfor, der involverer at finde Cholesky -nedbrydningen af ​​en ny matrix, alle er af formen , som gør det muligt at beregne dem effektivt ved hjælp af opdaterings- og nedjusteringsprocedurerne beskrevet i det foregående afsnit. ${\ displaystyle {\ tilde {\ mathbf {A}}} = \ mathbf {A} \ pm \ mathbf {x} \ mathbf {x} ^{*}}$

Bevis for positive semi-bestemte matricer

Bevis ved at begrænse argument

Ovenstående algoritmer viser, at hver positiv bestemt matrix har en Cholesky -dekomponering. Dette resultat kan udvides til at omfatte den positive semi-bestemte sag ved et begrænsende argument. Argumentet er ikke fuldstændigt konstruktivt, dvs. det giver ingen eksplicitte numeriske algoritmer til beregning af Cholesky -faktorer. ${\ displaystyle \ mathbf {A}}$

Hvis er en positiv semi-bestemt matrix , består sekvensen af positive bestemte matricer . (Dette er en umiddelbar konsekvens af f.eks. Den spektrale kortlægningssætning for den polynomiske funktionelle beregning.) Også, ${\ displaystyle \ mathbf {A}}$${\ displaystyle n \ gange n}$ ${\ textstyle \ left (\ mathbf {A} _ {k} \ right) _ {k}: = \ left (\ mathbf {A} +{\ frac {1} {k}} \ mathbf {I} _ { n} \ højre) _ {k}}$

${\ displaystyle \ mathbf {A} _ {k} \ rightarrow \ mathbf {A} \ quad {\ text {for}} \ quad k \ rightarrow \ infty}$

i operatørnorm . Fra det positive bestemte tilfælde har hver Cholesky nedbrydning . Efter operatørnormens ejendom, ${\ displaystyle \ mathbf {A} _ {k}}$${\ displaystyle \ mathbf {A} _ {k} = \ mathbf {L} _ {k} \ mathbf {L} _ {k}^{*}}$

${\ displaystyle \ | \ mathbf {L} _ {k} \ |^{2} \ leq \ | \ mathbf {L} _ {k} \ mathbf {L} _ {k}^{*} \ | = \ | \ mathbf {A} _ {k} \ | \ ,.}$

Den holder fordi udstyret med operatøren normen er en C * algebra. Således er et afgrænset sæt i Banach-rummet for operatører, derfor relativt kompakt (fordi det underliggende vektorrum er endeligt-dimensionelt). Følgelig har den en konvergent undersekvens, også betegnet med , med grænse . Det kan let kontrolleres, at denne har de ønskede egenskaber, dvs. , og er lavere trekantede med ikke-negative diagonale poster: for alle og , ${\ displaystyle \ leq}$${\ displaystyle M_ {n} (\ mathbb {C})}$${\ displaystyle \ venstre (\ mathbf {L} _ {k} \ højre) _ {k}}$${\ displaystyle \ venstre (\ mathbf {L} _ {k} \ højre) _ {k}}$${\ displaystyle \ mathbf {L}}$${\ displaystyle \ mathbf {L}}$${\ displaystyle \ mathbf {A} = \ mathbf {L} \ mathbf {L} ^{*}}$${\ displaystyle \ mathbf {L}}$${\ displaystyle x}$${\ displaystyle y}$

${\ displaystyle \ langle \ mathbf {A} x, y \ rangle = \ left \ langle \ lim \ mathbf {A} _ {k} x, y \ right \ rangle = \ langle \ lim \ mathbf {L} _ { k} \ mathbf {L} _ {k} ^{*} x, y \ rangle = \ langle \ mathbf {L} \ mathbf {L} ^{*} x, y \ rangle \ ,.}$

Derfor . Fordi det underliggende vektorrum er endeligt-dimensionelt, er alle topologier i operatørernes rum ækvivalente. Så har tendens til i norm betyder tendens til entrywise. Dette indebærer igen, at eftersom hver er lavere trekantet med ikke-negative diagonale poster, også. ${\ displaystyle \ mathbf {A} = \ mathbf {L} \ mathbf {L} ^{*}}$${\ displaystyle \ venstre (\ mathbf {L} _ {k} \ højre) _ {k}}$${\ displaystyle \ mathbf {L}}$${\ displaystyle \ venstre (\ mathbf {L} _ {k} \ højre) _ {k}}$${\ displaystyle \ mathbf {L}}$${\ displaystyle \ mathbf {L} _ {k}}$${\ displaystyle \ mathbf {L}}$

Bevis ved QR -nedbrydning

Lad være en positiv semi-bestemt hermitisk matrix. Så det kan skrives som et produkt af sin kvadratroden matrix , . Nu kan QR -nedbrydning påføres , hvilket resulterer i , hvor er enhed og øvre trekantet. Indsættelse af nedbrydning i de oprindelige ligestillingsudbytter . Indstillingen fuldender beviset. ${\ displaystyle \ mathbf {A}}$${\ displaystyle \ mathbf {A} = \ mathbf {B} \ mathbf {B} ^{*}}$${\ displaystyle \ mathbf {B} ^{*}}$${\ displaystyle \ mathbf {B} ^{*} = \ mathbf {Q} \ mathbf {R}}$${\ displaystyle \ mathbf {Q}}$${\ displaystyle \ mathbf {R}}$${\ displaystyle A = \ mathbf {B} \ mathbf {B} ^{*} = (\ mathbf {QR}) ^{*} \ mathbf {QR} = \ mathbf {R} ^{*} \ mathbf {Q } ^{*} \ mathbf {QR} = \ mathbf {R} ^{*} \ mathbf {R}}$${\ displaystyle \ mathbf {L} = \ mathbf {R} ^{*}}$

Generalisering

Cholesky -faktoriseringen kan generaliseres til (ikke nødvendigvis begrænsede) matricer med operatorposter. Lad være en sekvens af Hilbert -mellemrum . Overvej operatormatricen ${\ displaystyle \ {{\ mathcal {H}} _ {n} \}}$

${\ displaystyle \ mathbf {A} = {\ begin {bmatrix} \ mathbf {A} _ {11} & \ mathbf {A} _ {12} & \ mathbf {A} _ {13} & \; \\\ mathbf {A} _ {12}^{*} & \ mathbf {A} _ {22} & \ mathbf {A} _ {23} & \; \\\ mathbf {A} _ {13}^{*} & \ mathbf {A} _ {23}^{*} & \ mathbf {A} _ {33} & \; \\\; & \; & \; & \ ddots \ end {bmatrix}}}$

handler på det direkte beløb

${\ displaystyle {\ mathcal {H}} = \ bigoplus _ {n} {\ mathcal {H}} _ {n},}$

hvor hver

${\ displaystyle \ mathbf {A} _ {ij}: {\ mathcal {H}} _ {j} \ rightarrow {\ mathcal {H}} _ {i}}$

er en afgrænset operatør . Hvis A er positiv (semidefinit) i den forstand, at for alle begrænsede k og for evt

${\ displaystyle h \ in \ bigoplus _ {n = 1}^{k} {\ mathcal {H}} _ {k},}$

vi har , så eksisterer der en lavere trekantet operatormatrix L, således at A = LL *. Man kan også tage de diagonale poster i L for at være positiv. ${\ displaystyle \ langle h, \ mathbf {A} h \ rangle \ geq 0}$

Implementeringer i programmeringsbiblioteker

• C programmeringssprog : GNU Scientific Library giver flere implementeringer af Cholesky nedbrydning.
• Maxima computer algebra system: funktion cholesky beregner Cholesky nedbrydning.
• GNU Octave numeriske beregningssystem giver flere funktioner til at beregne, opdatere og anvende en Cholesky -dekomponering.
• Den LAPACK Biblioteket giver en høj gennemførelse af Cholesky dekomposition, der kan tilgås fra Fortran, C og de fleste sprog ydeevne.
• I Python udfører funktionen "cholesky" fra numpy.linalg -modulet Cholesky nedbrydning.
• I Matlab og R giver "chol" -funktionen Cholesky nedbrydning.
• I Julia giver "cholesky" -funktionen fra LinearAlgebra standardbibliotek Cholesky nedbrydning.
• I Mathematica kan funktionen "CholeskyDecomposition" anvendes på en matrix.
• I C ++ udfører kommandoen "chol" fra bæltedyrsbiblioteket Cholesky nedbrydning. De Eigen bibliotek leverer Cholesky factorizations for både sparsomme og tætte matricer.
• I ROOT -pakken er TDecompChol -klassen tilgængelig.
• I Analytica giver funktionen Decompose Cholesky nedbrydning.
• Den Apache Commons Math bibliotek har en implementering , som kan bruges i Java, Scala og enhver anden JVM sprog.

Se også

• Cyklusrang
• Ufuldstændig koleskisk faktorisering
• Matrixnedbrydning
• Minimum grad algoritme
• Kvadratroden af ​​en matrix
• Sylvesters inertilov
• Symbolsk Cholesky nedbrydning

Noter

Referencer

• Dereniowski, Dariusz; Kubale, Marek (2004). "Cholesky faktorisering af matricer i parallel og rangering af grafer". 5. internationale konference om parallel behandling og anvendt matematik (PDF) . Foredragsnotater om datalogi. 3019 . Springer-Verlag. s. 985–992. doi : 10.1007/978-3-540-24669-5_127 . ISBN 978-3-540-21946-0. Arkiveret fra originalen (PDF) den 2011-07-16.
• Golub, Gene H .; Van Loan, Charles F. (1996). Matrix Computations (3. udgave). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
• Horn, Roger A .; Johnson, Charles R. (1985). Matrix analyse . Cambridge University Press. ISBN 0-521-38632-2.
• SJ Julier og JK Uhlmann. " En generel metode til tilnærmelse af ikke -lineære transformationer af sandsynlighedsfordelinger ".
• SJ Julier og JK Uhlmann, " En ny udvidelse af Kalman -filteret til ikke -lineære systemer ", i Proc. AeroSense: 11. Int. Symp. Aerospace/Defense Sensing, Simulation and Controls, 1997, s. 182–193.
• Trefethen, Lloyd N .; Bau, David (1997). Numerisk lineær algebra . Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-361-9.
• Osborne, Michael (2010). Bayesiske gaussiske processer til sekventiel forudsigelse, optimering og kvadratur (PDF) (speciale). University of Oxford.
• Ruschel, João Paulo Tarasconi, bachelorgrad " Parallel Implementations of the Cholesky Decomposition on CPUs and GPUs " Universidade Federal Do Rio Grande Do Sul, Instituto De Informatica, 2016, s. 29-30.

eksterne links

Videnskabshistorie

• Sur la résolution numérique des systèmes d'équations linéaires , Choleskys manuskript fra 1910, online og analyseret på BibNum (på fransk og engelsk) [for engelsk, klik på 'En download']

Information

• "Cholesky factorization" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Cholesky dekomponering , dataanalysen kortbog
• Cholesky dekomponering på www.math-linux.com
• Cholesky nedbrydning gjort enkel på videnskab meanderthal

Computerkode

• LAPACK er en samling af FORTRAN -underrutiner til løsning af tætte lineære algebra -problemer (DPOTRF, DPOTRF2, detaljer ydeevne )
• ALGLIB inkluderer en delvis port af LAPACK til C ++, C#, Delphi, Visual Basic osv. (Spdmatrixcholesky, hpdmatrixcholesky)
• libflame er et C -bibliotek med LAPACK -funktionalitet.
• Noter og video om højtydende implementering af Cholesky-faktorisering ved University of Texas i Austin.
• Cholesky: TBB + Threads + SSE er en bog, der forklarer implementeringen af ​​CF med TBB, tråde og SSE (på spansk).
• bibliotek "Ceres Solver" af Google.
• LDL -nedbrydningsrutiner i Matlab.
• Armadillo er en C ++ lineær algebra -pakke
• Rosetta Code er et programmeringssted for chrestomati. på sidens emne .
• AlgoWiki er et åbent encyklopædi over algoritmers egenskaber og funktioner i deres implementeringer på sideemne
• Intel® oneAPI Math Kernel Bibliotek Intel-Optimeret Math Bibliotek for Numerisk Computing ? Potrf , ? Potrs

Brug af matrixen i simulering

• Generering af korrelerede tilfældige variabler og stokastiske processer , Martin Haugh, Columbia University

Online regnemaskiner

• Online Matrix -lommeregner udfører koldskåret nedbrydning af matricer online.