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\times n$ -matrix met elementen a_i,j. De Doolittle-decompositie is formeel gezien een Gauss-eliminatie. Het algoritme begint dan met als $L$ de $n\times 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 de rijen $j$ en $k$ in kolom $k$ . Die factoren, $u_{j,k}/u_{k,k}$ , kopiëren we in de corresponderende kolom van $L$ .

Indien $U$ een element $u_{k,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 $u_{j,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^{-1}A=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\times n$ lineaire vergelijkingen in de $n\times 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:

a_{1,1}=u_{1,1}

a_{2,1}=l_{2,1}u_{1,1}

of

l_{2,1}={\frac {a_{2,1}}{a_{1,1}}}

a_{3,1}=l_{3,1}u_{1,1}

of

l_{3,1}={\frac {a_{3,1}}{a_{1,1}}}

enz.;

a_{1,2}=u_{1,2}

a_{2,2}=u_{2,2}+l_{2,1}u_{1,2}

of

u_{2,2}=a_{2,2}-l_{2,1}a_{1,2}

a_{3,2}=l_{3,1}u_{1,2}+l_{3,2}u_{2,2}

of

l_{3,2}=(a_{3,2}-l_{3,1}a_{1,2})/u_{2,2}

enz.;

a_{1,3}=u_{1,3}

a_{2,3}=l_{2,1}u_{1,3}+u_{2,3}

of

u_{2,3}=a_{2,3}-l_{2,1}a_{1,3}

a_{3,3}=l_{3,1}u_{1,3}+l_{3,2}u_{2,3}+u_{3,3}

of

u_{3,3}=a_{3,3}-l_{3,1}a_{1,3}-l_{3,2}u_{2,3}

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.

Voorbeeld

Gegeven:

A={\begin{pmatrix}3&-7&-2&2\\-3&5&1&0\\6&-4&0&-5\\-9&5&-5&12\\\end{pmatrix}}

We beginnen met als matrix $L$ de eenheidsmatrix en $U$ gelijk aan $A$ :

LU={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}{\begin{pmatrix}3&-7&-2&2\\-3&5&1&0\\6&-4&0&-5\\-9&5&-5&12\\\end{pmatrix}}

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:

LU={\begin{pmatrix}1&0&0&0\\-1&1&0&0\\2&0&1&0\\-3&0&0&1\\\end{pmatrix}}{\begin{pmatrix}3&-7&-2&2\\0&-2&-1&2\\0&10&4&-9\\0&-16&-11&18\\\end{pmatrix}}

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:

LU={\begin{pmatrix}1&0&0&0\\-1&1&0&0\\2&-5&1&0\\-3&8&0&1\\\end{pmatrix}}{\begin{pmatrix}3&-7&-2&2\\0&-2&-1&2\\0&0&-1&1\\0&0&-3&2\\\end{pmatrix}}

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:

LU={\begin{pmatrix}1&0&0&0\\-1&1&0&0\\2&-5&1&0\\-3&8&3&1\\\end{pmatrix}}{\begin{pmatrix}3&-7&-2&2\\0&-2&-1&2\\0&0&-1&1\\0&0&0&-1\\\end{pmatrix}}

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 $Ax=B$ op te lossen gaat men als volgt te werk:

Vorm de matrices $L$ en $U$ : $LUx=B$ . We noemen $y$ het (voorlopig onbekende) product $Ux$ .
Los $Ly=B$ op door voorwaartse substitutie.
Los $Ux=y$ op door achterwaartse substitutie.

Wanneer bijvoorbeeld $B={\begin{pmatrix}-36&20&2&-34\end{pmatrix}}^{T}$ , vinden we achtereenvolgens:

$y_{1}=-36$
$-y_{1}+y_{2}=20$ waaruit $y_{2}=-16$
$2y_{1}-5y_{2}+y_{3}=2$ waaruit $y_{3}=-6$
$-3y_{1}+8y_{2}+3y_{3}+y_{4}=-34$ waaruit $y_{4}=4$

en:

$-x_{4}=y_{4}=4$ of $x_{4}=-4$
$-x_{3}+x_{4}=y_{3}=-6$ waaruit $x_{3}=2$
$-2x_{2}-x_{3}+2x_{4}=y_{2}=-16$ waaruit $x_{2}=3$
$3x_{1}-7x_{2}-2x_{3}+2x_{4}=y_{1}=-36$ waaruit $x_{1}=-1$

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.

Websites

Cholesky, Doolittle and Crout Factorization

Voetnoten

↑ Myrick H. Doolittle. "Method employed in the solution of normal equations and the adjustment of a triangulation", U.S. Coast and Geodetic Survey Report 1878, Appendix 8, Paper No. 3, blz.. 115–120.

[1] Myrick H. Doolittle. "Method employed in the solution of normal equations and the adjustment of a triangulation", U.S. Coast and Geodetic Survey Report 1878, Appendix 8, Paper No. 3, blz.. 115–120.

[1]