Introducere#

Înainte să construim factorizările QR pentru matrice oarecare, vom aminti câteva noțiuni matematice ale căror importanță este greu de supraestimat.

Noțiuni teoretice#

Vom considera însușite anterior noțiunile privind matricele (superior) triunghiulare și vom încerca să explicăm conceptul de matrice ortogonală.

Produs scalar#

Fie doi vectori oarecare \(\bm{u},\bm{v}\in\mathbb{R}^n\), \(n\in\mathbb{N}^*\). Alternativ, scriși desfășurat:

\[\bm{u}=\begin{bmatrix}u_1\\\vdots\\u_n\end{bmatrix}\,\,;\,\,\bm{v}=\begin{bmatrix}v_1\\\vdots\\v_n\end{bmatrix}\]

Prin definiție, produsul scalar dintre acești doi vectori este:

\[\boxed{\langle \bm{u},\bm{v}\rangle=\sum_{k=1}^nu_kv_k}\]

Enunțăm și câteva proprietăți utile ale produsului scalar:

• În \(\mathbb{R}^n\), nu contează ordinea vectorilor: \(\langle \bm{u},\bm{v}\rangle = \langle \bm{v},\bm{u}\rangle\);

• Scalarii pot fi extrași în afara produsului: \(\langle\alpha\cdot\bm{u},\bm{v}\rangle=\langle\bm{u},\alpha\cdot\bm{v}\rangle=\alpha\cdot\langle\bm{u},\bm{v}\rangle\).

Normă euclidiană#

Folosindu-ne de produsul scalar, putem defini norma euclidiană a unui vector oarecare \(\bm{u}\in\mathbb{R}^n\), \(n\in\mathbb{N}^*\), drept:

\[\boxed{||\bm{u}||=\sqrt{\langle\bm{u},\bm{u}\rangle}}\]

Vectori ortogonali și ortonormali#

Dar la ce este bun acest produs scalar?

El poate fi o unealtă foarte utilă pentru a determina similitudinea dintre doi vectori - cu cât ne apropiem de \(0\), cu atât aceștia sunt mai "diferiți".

Prin definiție, doi vectori oarecare \(\bm{u},\bm{v}\in\mathbb{R}^n\), \(n\in\mathbb{N}^*\) sunt ortogonali (\(\bm{u}\perp\bm{v}\)) dacă și numai dacă produsul lor scalar este nul, adică:

\[\boxed{\langle \bm{u},\bm{v}\rangle=0}\]

Clădind peste noțiunea anterioară, putem impune suplimentar ca norma euclidiană a acestor doi vectori să fie unitară, adică \(||\bm{u}||=||\bm{v}||=1\) - în acest caz, vectorii se consideră ortonormali.

Matrice ortogonale#

Fie \(Q\in\mathbb{R}^{n\times n}\), \(n\in\mathbb{N}^*\), o matrice nesingulară (inversabilă). Aceasta se consideră ortogonală dacă și numai dacă are proprietatea că:

\[\boxed{Q^{-1}=Q^T}\Leftrightarrow QQ^T=Q^TQ=I_n\]

O definiție alternativă pleacă de la matricea \(Q=\begin{bmatrix}\bm{q_1}&\dots&\bm{q_n}\end{bmatrix}\) ce are în componența sa numai vectori ortonormați - în acest caz, matricea se consideră ortogonală.

Factorizarea QR#

Considerăm \(A\in\mathbb{R}^{n\times n}\) o matrice pătratică cu \(n\) linii și \(n\) coloane, \(n\in\mathbb{N}^*\). Factorizarea QR a matricei \(A\) presupune calcularea a două matrice pătratice, \(Q,R\in\mathbb{R}^{n\times n}\), unde \(Q\) este o matrice ortogonală, iar \(R\) este o matrice superior triunghiulară, astfel încât produsul lor să revină la matricea \(A\), adică:

\[\boxed{A=QR}\]

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

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

Calcularea acestor două matrice nu va mai fi la fel de intuitivă precum în cazul matricelor caracteristice factorizării LU, însă există câțiva algoritmi ce sunt ușor de urmărit:

• Factorizarea Gram-Schmidt - instabilă numeric, dar ușor de înțeles;

• Factorizarea Gram-Schmidt Modificată - mai stabilă din punct de vedere numeric, însă nu suficient, existând alternative mai bune;

• Factorizarea Householder - cea mai stabilă metodă, utilizată în practică pentru orice fel de matrice, rare sau dense;

• Factorizarea Givens - utilizată în mod special pentru matricele rare.

Licență#

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