Introducere#

În acest subcapitol, vom începe călătoria în lumea factorizării LU. Acest lucru presupune însușirea câtorva noțiuni teoretice de algebră liniară prin care vom trece rapid, iar apoi ne întoarcem la conținutul real al acestui capitol.

Noțiuni teoretice#

Veți observa, în timp ce parcurgeți cartea, că materia predată în cadrul cursului de Metode Numerice este ancorată foarte mult în universul matematicii. Primele capitole pot părea că demonstrează opusul, însă, pe viitor, se vor acumula rapid foarte multe informații noi.

Din acest motiv, insistăm ca cititorul să capete cunoștințele matematice necesare cât mai devreme cu putință. Bineînțeles, sunteți încurajați să reveniți la conținutul teoretic ori de câte ori simțiți dezvoltarea unei lacune!

Matrice triunghiulare#

Pentru început, să vorbim despre o gamă specială de matrice, anume matricele (pătratice) triunghiulare.

Fie \(U\in\mathbb{R}^{n\times n}\), \(n\in\mathbb{N}^*\), o matrice pătratică ce conține numai elemente nule sub diagonala principală, adică ia forma:

\[ U=\begin{bmatrix} u_{11} & u_{12} & \dots & u_{1n} \\ 0 & u_{22} & \dots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \dots & u_{nn} \end{bmatrix}=(u_{ij})_{1\leq i,j\leq n},\,\,\text{unde}\,\,i\gt j\rightarrow u_{ij}=0 \]

Atunci, \(U\) se consideră superior triunghiulară (en. Upper Triangular Matrix, de aici și notația utilizată). De exemplu, matricea \(U=\begin{bmatrix}-1&4\\0 & 3\end{bmatrix}\).

Analog, fie \(L\in\mathbb{R}^{n\times n}\), \(n\in\mathbb{N}^*\), o matrice pătratică ce conține numai elemente nule deasupra diagonalei principale, adică ia forma:

\[ L=\begin{bmatrix} l_{11} & 0 & \dots & 0 \\ l_{21} & l_{22} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots\\ l_{n1} & l_{n2} & \dots & l_{nn} \end{bmatrix}=(l_{ij})_{1\leq i,j\leq n},\,\,\text{unde}\,\,i\lt j\rightarrow l_{ij}=0 \]

În acest caz, matricea \(L\) se numește inferior triunghiulară (en. Lower Triangular Matrix, de unde apare și notația utilizată). Spre exemplu, \(L=\begin{bmatrix}1 & 0\\-2 & -3\end{bmatrix}\).

Generalizând, o matrice se consideră triunghiulară dacă aceasta fie este superior triunghiulară, fie este inferior triunghiulară.

Trivial, se poate demonstra că, prin transpunere, o matrice inferior triunghiulară devine superior triunghiulară și invers.

Determinantul matricelor triunghiulare#

Calculul determinantului acestui tip de matrice se dovedește a fi mult mai ușor comparativ cu matricele oarecare.

Astfel, fără a demonstra, determinantul unei matrice triunghiulare \(T\in\mathbb{R}^{n\times n}\), \(n\in\mathbb{N}^*\), se poate calcula realizând produsul elementelor aflate pe diagonala principală, adică:

\[ \boxed{\det T = \prod_{i=1}^nt_{ii}} \]

Demonstrație

Întrucât, prin transpunere, o matrice inferior triunghiulară devine superior triunghiulară și invers, respectiv \(\det A=\det A^T\), \(\forall A\in\mathbb{R}^{n\times n}\), \(n\in\mathbb{N}^*\), rezultă că este suficient să demonstrăm formula pentru un singur tip de matrice triunghiulară, de exemplu cea inferior triunghiulară.

Vom schița o demonstrație pe baza dimensiunii matricei:

Pasul 1. \(L\in\mathbb{R}^{1\times1}\)

Este evident că determinantul acestei matrice este egal cu singurul element al său. Totodată, acesta se regăsește pe diagonala principală a matricei.

Pasul k. \(L\in\mathbb{R}^{k\times k}\rightarrow L'=\begin{bmatrix}L&\bm{0}\\\bm{l'}&l'_{k+1,k+1}\end{bmatrix}\) (unde \(\bm{0}, \bm{l'}^T\in\mathbb{R}^k\))

Folosindu-ne de proprietățile determinanților, putem folosi ultima coloană pentru a elimina toate valorile nenule de pe ultima linie. Cu alte cuvinte, executăm \(\bm{{L'}_i}\rightarrow\bm{{L'}_i}-\frac{l'_{k+1,i}}{l'_{k+1,k+1}}\bm{{L'}_{k+1}}\), \(\forall i\in\overline{1,k}\). Obținem:
\[\det L'=\begin{vmatrix}L&\bm{0}\\\bm{l'}&l'_{k+1,k+1}\end{vmatrix}=\begin{vmatrix}L&\bm{0}\\\bm{0}&l'_{k+1,k+1}\end{vmatrix}\]
Conform proprietăților determinanților, concluzionăm că \(\det L'=(-1)^{(k+1)(k+1)}\cdot l'_{k+1,k+1}\cdot \det L\).

Excepția de la acest caz apare pentru \(l'_{k+1,k+1}=0\), caz în care se formează implicit \(\bm{L'}_{k+1}=\bm{0}^{k+1}\), și deci \(\det L'=0=0\cdot\det L\).

Matrice unitriunghiulare#

Putem specializa conceptul de matrice triunghiulară dacă forțăm constrângeri suplimentare asupra acesteia.

De exemplu, fie \(A\in\mathbb{R}^{n\times n}\) o matrice triunghiulară. Dacă elementele aflate pe diagonala principală au valoarea \(a_{ii}=1\), \(\forall i\in\overline{1,n}\), atunci matricea se numește unitriunghiulară.

De exemplu, matricea \(A=\begin{bmatrix}1 & 3 & -2\\0 & 1 & 5 \\ 0 & 0 & 1\end{bmatrix}\) este o matrice unitriunghiulară.

Determinantul matricelor unitriunghiulare#

Ca o consecință asupra faptului că elementele de pe diagonala principală sunt unitare, este evident că determinantul unei matrice unitriunghiulare va fi egal cu \(1\).

Matrice diagonale#

O altă direcție în care ne putem duce este aceea de a particulariza atât elementele aflate sub, cât și cele aflate deasupra diagonalei principale ale unei matrice oarecare.

Fie \(D\in\mathbb{R}^{n\times n}\) o matrice care conține numai valori nule sub și deasupra diagonalei principale, adică ia forma:

\[ D=\begin{bmatrix} d_{11} & 0 & \dots & 0 \\ 0 & d_{22} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \dots & d_{nn} \end{bmatrix}=(d_{ij})_{1\leq i,j\leq n},\,\,\text{unde}\,\,i\neq j\rightarrow d_{ij}=0 \]

Atunci \(D\) se numește matrice diagonală. Un exemplu de matrice diagonală ar putea fi \(D=\begin{bmatrix}-8 & 0 & 0\\0 & 11 & 0\\0 & 0 & 7\end{bmatrix}\).

Determinantul matricelor diagonale#

Cum matricea diagonală este, în esență, o particularizare a matricei triunghiulare, ecuația determinantului rămâne valabilă și pentru aceasta.

Să o reamintim, întrucât este foarte importantă:

\[ \boxed{\det D = \prod_{i=1}^nd_{ii}} \]

Pentru exemplul anterior, am obține \(\det D = -8\cdot11\cdot7=-616\).

Factorizarea LU#

Să considerăm o matrice pătratică \(A\in\mathbb{R}^{n\times n}\) cu \(n\) linii și \(n\) coloane, \(n\in\mathbb{N}\). Factorizarea LU a matricei \(A\) presupune calcularea a două matrice pătratice, \(L,U\in\mathbb{R}^{n\times n}\), unde \(L\) este o matrice inferior triunghiulară, iar \(U\) este o matrice superior triunghiulară, cu proprietatea că produsul lor revine la matricea \(A\), adică:

\[ \boxed{A=LU} \]

Scrisă desfășurat, ecuația anterioară ia forma:

\[ \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix} = \begin{bmatrix} l_{11} & 0 & \cdots & 0 \\ l_{21} & l_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots\\ l_{n1} & l_{n2} & \cdots & l_{nn} \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & u_{nn} \end{bmatrix} \]

Vom vedea pe parcursul acestui capitol că, fără a impune restricții suplimentare, este imposibil să calculăm această factorizare.

Mai precis, cele 3 factorizări dezbătute impun:

Factorizarea Doolittle - \(L\) să fie unitriunghiulară;
Factorizarea Crout - \(U\) să fie unitriunghiulară;
Factorizarea Cholesky - \(A\) să fie simetrică și pozitiv definită.

Nu vom intra aici în detalii, ci vom prefera să tratăm fiecare caz într-un subcapitol dedicat.

Termenul general#

Oricărui element \(a_{ij}\) al matricei \(A=LU\) îi corespunde combinația liniară unică:

\[ \boxed{ a_{ij}=\sum_{k=1}^{\min{\{i,j\}}}l_{ik}u_{kj} }\,,\,\,1\leq i,j\leq n \]

Acest rezultat se poate obține ușor prin calcul brut. Voi lăsa demonstrația drept exercițiu pentru cititor.

Licență#

The book "Metode Numerice", written by Valentin-Ioan Vintilă, is licensed under CC BY-NC-SA 4.0