Alte factorizări LU#

Dacă sunteți în continuare curioși să învățați despre factorizările LU, putem extinde acum conceptele anterioare, încercând să factorizăm în mai multe matrice.

Vom prezenta pe scurt factorizările LDU și PLU.

Factorizarea LDU#

Fie \(A\in\mathbb{R}^{n\times n}\) o matrice pătratică cu \(n\) linii și \(n\) coloane, \(n\in\mathbb{N}^*\). Această tehnică de factorizare își propune să scrie matricea \(A\) sub forma unui produs de alte trei matrice, \(L,D,U\in\mathbb{R}^{n\times n}\) alese astfel încât \(L\) să fie inferior unitriunghiulară, \(D\) să fie diagonală și \(U\) să fie superior unitriunghiulară. Cu alte cuvinte:

\[\boxed{A=LDU}\]

Desfășurând partea dreaptă a ecuației, obținem:

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

Înainte de a continua

Înainte să citiți mai departe, încercați să vedeți dacă puteți ajunge singuri la formulele pentru această factorizare.

Hint: Nu reinventați roata, utilizați conceptele deja studiate!

Calcularea matricelor componente#

Așa cum probabil ați realizat deja, grupând matricea \(D\) fie cu \(L\), fie cu \(U\), ne întoarcem la o factorizare Crout sau Doolittle.

Să considerăm \(A=LU'\) factorizarea Doolittle a matricei \(A\in\mathbb{R}^{n\times n}\), \(n\in\mathbb{N}^*\). Ne propunem să spargem acum matricea \(U'\) în produsul matricelor \(DU\):

\[ \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}=\begin{bmatrix} d_{11} & 0 & \dots & 0 \\ 0 & d_{22} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \dots & d_{nn} \end{bmatrix} \begin{bmatrix} 1 & u_{12} & \dots & u_{1n} \\ 0 & 1 & \dots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \dots & 1 \end{bmatrix} \]

Să executăm produsul în sine:

\[ \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}=\begin{bmatrix} d_{11} & d_{11}u_{12} & \dots & d_{11}u_{1n} \\ 0 & d_{22} & \dots & d_{22}u_{2n} \\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \dots & d_{nn} \end{bmatrix} \]

Devin așadar evidente relațiile pentru calculul elementelor matricelor \(D\) și \(U\):

\[ \begin{cases} d_{ii}=u'_{ii},&\forall i\in\overline{1,n}\\ u_{ij}=\frac{u'_{ij}}{d_{ii}},&\forall i\in\overline{1,n-1},\,j\in\overline{i+1,n} \end{cases} \]

Factorizarea Crout

Încercați acum să obțineți un rezultat similar folosind factorizarea Crout în locul factorizării Doolittle.

Cod ilustrativ#

Pentru a implementa algoritmul LDU (funcția Doolittle_LDU), vom presupune că avem implementată a funcție ce realizează factorizarea Doolittle a unei matrice primite drept parametru (funcția Doolittle).

Funcția returnează tripletul [L, D, U], unde fiecare element este:

L - o matrice inferior unitriunghiulară;
D - o matrice diagonală;
U - o matrice superior unitriunghiulară.

Evident, aceste matrice au proprietatea că \(A=LDU\).

function [L, D, U] = Doolittle_LDU(A)
    [L, U] = Doolittle(A);
    for i = [1 : n]
        D(i,i) = U(i,i);
        U(i,:) /= D(i,i);
    end
end

Factorizarea PLU#

Fie \(A\in\mathbb{R}^{n\times n}\) o matrice pătratică cu \(n\) linii și \(n\) coloane, \(n\in\mathbb{N}^*\). Să considerăm factorizarea \(A=PLU\), unde \(P,L,U\in\mathbb{R}^{n\times n}\) sunt alese astfel încât matricea \(P\) să reprezinte o matrice de permutare, iar \(L\) și \(U\) să fie matrice inferior, respectiv superior triunghiulare. Această factorizare se numește factorizare LU cu pivotare.

De ce ne pasă?#

Motivul pentru care este necesară o astfel de factorizare este simplu - există situații în care algoritmul LU pur și simplu se defectează.

Spre exemplu, să considerăm factorizarea LU a unei matrice nesingulare (inversabile) \(A\in\mathbb{R}^{n\times n}\), unde \(n\in\mathbb{N}^*\), ce va conține în colțul din stânga sus valoarea \(a_{11}=0\).

Licență#

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