Metode de Rezolvare a Sistemelor Liniare Bazate pe Factorizare Ortogonală

Sistemul supradeterminat de ecuaţii liniare

Ax=b, A∈Rmxn, b ∈Rm, m>n

nu admite în general soluţie.

Soluţia în sensul celor mai mici pătrate (sau pseudosoluţia) se defineşte ca vectorul x* din Rn care asigură minimizarea normei euclidiene a vectorului reziduu:

() r()2RxRx2**xAbminxrminxAbx

Pseudosoluţia este soluţie exactă pentru sistemul normal

ATAx=ATb

Sistemul normal este rău condiţionat astfel încât metodele obişnuite de rezolvare (Gauss, Cholesky, etc) nu dau rezultate satisfăcătoare, fiind necesare metode mai stabile din punct de vedere numeric, bazate pe triunghiularizare ortogonală.

Pseudosoluţia este unică dacă matricea A are coloanele liniar independente, caz în care se exprimă ca:

x*=(ATA)-1ATb=A#b

în care se defineşte

A#=(ATA)-1AT∈Rnxm

ca inversă generalizată sau pseudoinversă Penrose - Moore a matricei dreptunghiulare A∈Rmxn.

Doi vectori x, y ∈ Rn sunt ortogonali în raport cu produsul euclidian dacă xTy=0.

Complementul ortogonal S⊥ a subspaţiului S ∈ Rn se defineşte ca:

S⊥ = {y∈Rn │ xTy=0, x∈S}

Vectorii q1, q2,...,qn∈Rm sunt ortonormaţi, dacă qiTqj=δij

Matricea Q = [q1 q2 ... qn] ∈ Rmxn este ortogonală şi QT.Q=In

Considerăm o matrice ortogonală pătrată Q ∈ Rnxn. Matricele ortogonale au următoarele proprietăţi:

10. Q-1 = QT

20. det(Q) = ±1

det(QT.Q)=det(Q.Q)=det2(Q)=det(In)=1

În Cn vectorii sunt ortogonali dacă xHy=0, unde xH=xT (transpus conjugat) Matricea Q este unitară dacă QH.Q=In.

30. ║Hx║2=║x║2 -transformarea ortogonală conservă norma euclidiană a unui vector

║Hx║22=(Hx,Hx)=(Hx)T(Hx)=xTHTHx=xT(HTH)x=xTx=║x║22

1

40. ║H║2=1 -norma matricială euclidiană subordonată este 1:

50. cond2(A) = 1 1xxHsupH220x2=⋅=≠

60. ║H.A║2=║A║2 -transformarea ortogonală conservă norma euclidiană a unei matrice:

R=H.A ⇒ ║R║2=║H.A║2≤║H║2.║A║2=║A║2

A=HT.R ⇒ ║A║2=║HT.R║2≤║H║2.║R║2=║R║2

║H.A║2=║A║2

O matrice P se numeşte matrice idempotentă sau matrice proiector, dacă P2=P.

În raport cu un proiector P, un vector v∈Rn poate fi descompus unic în:

v = P.v + (I-P).v = v1 + v2

P.v2 = P.(I-P).v = (P-P2).v = 0.v = 0

v1=P.v ∈ S – proiecţia lui v în spaţiul imagine a lui P

v2=(I-P )v ∈ S⊥ – proiecţia lui v în spaţiul nul a lui P

Dacă P este simetric (P=PT), atunci:

v1Tv2 =(P.v)T.(I-P).v=vT.P.(I-P)= vT.(P-P2)v=0 ⇒ v2 ⊥ S ⇒ v2∈S⊥

P este proiectorul ortogonal în S

I-P este proiectorul ortogonal în S⊥

O metodă ortogonală transformă sistemul Ax=b într-un sistem echivalent cu matrice superior triunghiulară HAx=Hb în care matricea de transformare H∈Rmxn este ortogonală. Matricea sistemului echivalent (în sensul că are aceeaşi pseudosoluţie cu sistemul iniţial), are acelaşi număr de condiţionare în normă 2. Intr-adevăr, transformările ortogonale conservă norma euclidiană

Metoda Householder

O matrice ortogonală elementară se obţine modificând matricea unitate, cu o matrice de rang 1. Reflectorul Householder este o asemenea matrice ortogonală:

H = I - βuuT, β = 2 / (uTu)

H este simetrică:

HT=(I - βuuT)T = I - β(uuT)T = I - β(uT)TuT = I - βuuT = H

H este ortogonală:

HTH = H2 = I-2βuuT+β2u(uTu)uT = I-2βuuT+β2u(2/β)uT = I

u se numeşte vector Householder.

Hu = (I-βuuT)u = u - βu(uTu) = u - βu(2/β) = u – 2u = -u ceea ce justifică numele de reflector