Factorizarea Gram-Schmidt modificată#

Pentru o bună înțelegere a acestui algoritm este necesară aprofundarea algoritmului Gram-Schmidt nemodificat - noțiunile de bază și notațiile nu vor fi modificate, așadar sunteți încurajați să mai treceți încă o dată prin materialul dedicat.

Îmbunătățirea adusă#

Pornim de la notațiile explicate anterior.

Ne interesează să descoperim două formule pe care să le întrețesem:

  1. Cunoaștem deja faptul că \(r_{ij}=\langle \bm{a_j},\bm{q_j}\rangle\), \(\forall i\lt j\).

  2. Folosindu-ne de proprietatea de ortogonalitate \(\bm{q_k}\perp\bm{q_i}\), mai știm și că \(\langle\bm{q_k},\bm{q_i}\rangle=0\), \(\forall i\neq k\).

    Evident, prin înmulțirea cu un scalar, tot nul va fi produsul scalar: \(r_{kj}\langle\bm{q_k},\bm{q_i}\rangle=0\)

Putem face acum următoarea prelucrare aparent inutilă (pentru \(\forall i\lt j\)):

\[\begin{split} r_{ij}&=\langle \bm{a_j},\bm{q_i}\rangle\\ &=\langle \bm{a_j},\bm{q_i}\rangle-\sum_{k=1}^{i-1}r_{kj}\langle\bm{q_k},\bm{q_i}\rangle\\ &=\left\langle \bm{a_j}-\sum_{k=1}^{i-1}r_{kj}\bm{q_k}, \bm{q_i}\right\rangle \end{split}\]

Teoretic, nu am realizat decât o scădere repetată cu 0, adică valoarea finală nu ar trebui să se modifice. Dacă ne folosim de înlocuirea \(\bm{v_j}=\bm{a_j}-\sum_{k=1}^{i-1}r_{kj}\bm{q_k}\), ajungem la formula:

\[ \boxed{r_{ij}=\langle \bm{v_j},\bm{q_i}\rangle}\,,\,\,\forall i\lt j \]
Îmbunătățirea adusă

Din punct de vedere matematic, nu am realizat absolut nimic.

Cu toate acestea, numeric, adică din punct de vedere al erorii numerice, aceasta a fost mult micșorată! Altfel spus, în practică, acest algoritm se va comporta mult mai bine decât varianta nemodificată a algoritmului Gram-Schmidt!

Explicația algoritmică#

Descompunerea QR se face folosind Gram-Schmidt clasic, cu excepția valorilor ce compun matricea \(R\). Pentru aceasta, se va folosi următoarea formulă îmbunătățită:

\[ \boxed{r_{ij}=\langle \bm{a_j},\bm{q_i}\rangle=\left\langle \bm{a_j}-\sum_{k=1}^{i-1}r_{kj}\bm{q_k}, \bm{q_i}\right\rangle}\,,\,\,\forall i\lt j \]

Cod ilustrativ#

Vom implementa acum varianta modificată a algoritmului Gram-Schmidt sub forma funcției gsm - notăm cu A matricea pe care încercăm să o factorizăm.

Funcția returnează perechea [Q, R], unde am notat:

  • Q - matricea ortogonală din factorizarea QR;

  • R - matricea superior triunghiulară a factorizării QR.

Evident, se respectă egalitatea \(A=QR\). 

function [Q, R] = gsm(A)
    [m, n] = size(A);
    for i = [1 : n]
        R(i, i) = norm(A(1:m, i));
        Q(1:m, i) = A(1:m, i) / R(i, i);
        for j = [i+1 : n]
            R(i, j) = Q(1:m, i)' * A(1:m, j);
            A(1:m, j) = A(1:m, j) - Q(1:m, i) * R(i, j);
        end
    end
end

Concluzii#

Din punct de vedere matematic, acest algoritm este identic cu varianta nemodificată. Cu toate acestea, din punct de vedere numeric, această metodă este mult mai stabilă.

Din nefericire însă, îmbunătățirea aceasta nu este suficientă pentru ca algoritmul să poată fi considerat stabil numeric. În subcapitolele următoare, vom explica alternative mult mai utile în descompunerile QR.

Licență#

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

Results will appear as you type