De Doolittle-decompositie is een algoritme voor de LU-decompositie van een vierkante niet-singuliere matrix in een benedendriehoeksmatrix ${\displaystyle L}$ en een bovendriehoeksmatrix ${\displaystyle U}$. In de matrix ${\displaystyle 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]

Zij ${\displaystyle A}$ een ${\displaystyle n\times n}$-matrix met elementen a_i,j. De Doolittle-decompositie is formeel gezien een Gauss-eliminatie. Het algoritme begint dan met als ${\displaystyle L}$ de ${\displaystyle n\times n}$-eenheidsmatrix en ${\displaystyle U}$ gelijk aan ${\displaystyle A}$. In ${\displaystyle n-1}$ stappen wordt ${\displaystyle U}$ herleid tot een bovendriehoeksmatrix en ${\displaystyle L}$ tot een benedendriehoeksmatrix, zodanig dat het matrixproduct ${\displaystyle LU}$ steeds gelijk blijft aan ${\displaystyle A}$.

In de ${\displaystyle k}$-de stap worden de elementen onder de hoofddiagonaal in de ${\displaystyle k}$-de kolom van ${\displaystyle U}$ op nul gebracht. Dit gebeurt door rij ${\displaystyle k}$ met de juiste factor te vermenigvuldigen en dan af te trekken van rij ${\displaystyle j}$, wat een nieuwe rij ${\displaystyle j}$ geeft ${\displaystyle (j>k)}$. De factoren zijn de verhoudingen van de elementen in de rijen ${\displaystyle j}$ en ${\displaystyle k}$ in kolom ${\displaystyle k}$. Die factoren, ${\displaystyle u_{j,k}/u_{k,k}}$, kopiëren we in de corresponderende kolom van ${\displaystyle L}$.

Indien ${\displaystyle U}$ een element ${\displaystyle u_{k,k}}$ op de hoofddiagonaal heeft dat nul is, gaat dit natuurlijk niet op. In dat geval moet de rij ${\displaystyle k}$ verwisseld worden met een onderliggende rij ${\displaystyle j}$ waarin ${\displaystyle u_{j,k}}$ niet nul is. De verwisseling gebeurt ook in ${\displaystyle L}$. De verwisselingen kunnen bijgehouden worden in een permutatiematrix ${\displaystyle P}$. In het begin is ${\displaystyle P}$ de eenheidsmatrix. Wanneer twee rijen in ${\displaystyle U}$ en ${\displaystyle L}$ verwisseld worden, worden dezelfde rijen in ${\displaystyle P}$ verwisseld. De decompositie is dan niet langer ${\displaystyle A=LU}$ maar ${\displaystyle P^{-1}A=LU}$.

Indien men rekening houdt met de specifieke structuur van ${\displaystyle L}$ en ${\displaystyle U}$, kan men de coëfficiënten ervan een voor een berekenen. Immers als men het matrixproduct ${\displaystyle A=LU}$ uitschrijft, verkrijgt men een stelsel van ${\displaystyle n\times n}$ lineaire vergelijkingen in de ${\displaystyle n\times n}$ onbekende coëfficiënten van ${\displaystyle L}$ en ${\displaystyle U}$. Maar deze vergelijkingen kan men zo rangschikken dat elke volgende vergelijking een nieuwe coëfficiënt geeft; bijvoorbeeld:

${\displaystyle a_{1,1}=u_{1,1}}$

${\displaystyle a_{2,1}=l_{2,1}u_{1,1}}$ of ${\displaystyle l_{2,1}={\frac {a_{2,1}}{a_{1,1}}}}$

${\displaystyle a_{3,1}=l_{3,1}u_{1,1}}$ of ${\displaystyle l_{3,1}={\frac {a_{3,1}}{a_{1,1}}}}$ enz.;

${\displaystyle a_{1,2}=u_{1,2}}$

${\displaystyle a_{2,2}=u_{2,2}+l_{2,1}u_{1,2}}$ of ${\displaystyle u_{2,2}=a_{2,2}-l_{2,1}a_{1,2}}$

${\displaystyle a_{3,2}=l_{3,1}u_{1,2}+l_{3,2}u_{2,2}}$ of ${\displaystyle l_{3,2}=(a_{3,2}-l_{3,1}a_{1,2})/u_{2,2}}$ enz.;

${\displaystyle a_{1,3}=u_{1,3}}$

${\displaystyle a_{2,3}=l_{2,1}u_{1,3}+u_{2,3}}$ of ${\displaystyle u_{2,3}=a_{2,3}-l_{2,1}a_{1,3}}$

${\displaystyle a_{3,3}=l_{3,1}u_{1,3}+l_{3,2}u_{2,3}+u_{3,3}}$ of ${\displaystyle 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 ${\displaystyle L}$ en ${\displaystyle U}$, een voor een, rechtstreeks berekenen. Dit is de "compacte" vorm van de Doolittle-decompositie.

Gegeven:

${\displaystyle 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 ${\displaystyle L}$ de eenheidsmatrix en ${\displaystyle U}$ gelijk aan ${\displaystyle A}$:

${\displaystyle 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}}}$

In de eerste stap zijn de factoren om de elementen onder de diagonaal in de eerste kolom van ${\displaystyle U}$ op nul te krijgen, respectievelijk −1, 2 en −3. Die komen onder de diagonaal in de eerste kolom van ${\displaystyle L}$. In ${\displaystyle 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:

${\displaystyle 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 ${\displaystyle A}$ is.

Om de elementen onder de diagonaal in de tweede kolom van ${\displaystyle U}$ op nul te krijgen moeten we van de derde rij van ${\displaystyle U}$ de tweede rij van ${\displaystyle U}$ vermenigvuldigd met −5 aftrekken, en van de vierde rij van ${\displaystyle U}$ de tweede rij vermenigvuldigd met 8. Dit geeft:

${\displaystyle 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}}}$

In de laatste stap staat het enige overgebleven element onder de hoofddiagonaal van ${\displaystyle U}$ in de derde kolom. Door de derde rij van ${\displaystyle U}$ te vermenigvuldigen met 3 en af te trekken van de vierde rij wordt dit nul:

${\displaystyle 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 ${\displaystyle A}$ in ${\displaystyle LU}$ beëindigd. In dit geval was er geen verwisseling van rijen nodig.

Om een stelsel van lineaire vergelijkingen ${\displaystyle Ax=B}$ op te lossen gaat men als volgt te werk:

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

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

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

en:

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

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

• Cholesky, Doolittle and Crout Factorization