P.

PREFA

Lucrarea pune la dispoziia studenilor de la Facultatea de tiina i Tehnologia Informaiei -profil Informatic- din Universitatea Titu MAIORESCU un material complet i unitar pentru aprofundarea noiunilor de calcul numeric (analiz numeric) conform planului de nvmnt pentru anul nti de studiu. Fa de chestiunile teoretice absolut necesare, n lucrare se insist pe latura aplicativ a celor prezentate, cu un accent suplimentar asupra implementrii algoritmilor n programe numerice performante realizate sub mediul MATLAB.

UTM-STI

Modul de prezentare i soluionare a problematicii specifice are n vedere faptul c acest material este destinat n, principal, studenilor ce se pregtesc n informatic; n egal msur el este util i specialitilor din domeniul informatic -crora li se pune la dispoziie un material omogen, complet i coerent- ce sunt interesai de analiza implicaiilor pe care le are un calculul aproximativ asupra acurateei rezultatelor obinute. Structura lucrrii este conform cu programa analitic a disciplinei Analiz numeric; n acest sens ea conine: Capitolul 1 prezint elemente fundamentale de calcul matriceal, menite s reaminteasc noiunile de baz referitoare la vector, matrice, operaii cu vectori i matrice, produs scalar, norm, etc. El ofer i modalitatea simplist (dar util atunci cnd tot calculul se face analitic) de determinare a unei baze pentru subspaiul imagine, ortogonal, respectiv pentru nucleu, toate realizate cu ajutorul operaiilor gaussiene. Capitolul 2 abordeaz problematica calculului numeric cu specificitile datorate reprezentrii aproximative a tuturor operanzilor; n acest sens se prezint formatul n virgul mobil FVM ca modalitatea cea mai adecvat de reprezentare a numerelor ntr-un calculator numeric precum i cile de analiz a erorilor, inclusiv sub aspectul limitrii lor.

iv

S. erban, M. Tilca

ANALIZ NUMERIC

Soluionarea sistemelor algebrice liniare, pentru cazul matricilor A de form ptrat (i, n mod expres, nesingulare), folosind transformri elementare pentru asigurarea structurilor triunghiulare este abordat n capitolul 3. n final, se prezint problematica acurateei soluiei obinute, precum i factorii care o condiioneaz. n capitolul 4 este prezentat metoda celor mai mici ptrate CMMP, ce este esenial pentru rezolvarea sistemelor algebrice liniare la care matricea A este dreptunghiular. Drept metode se folosesc factorizarea QR sau LQ dup cum sistemul este supra sau subdeterminat. Capitolul 5 abordeaz problema descompunerii valorilor singulare DVS, ca fiind cea mai eficient procedur de determinare a rangului unei matrice. Aceasta metod permite rezolvarea numeric stabil i a altor probleme specifice cum ar fi: calculul normelor matriceale, evaluarea numrului de condiionare, calculul pseudoinversei, etc. n sfrit, n capitolul 6 sunt prezentate elementele fundamentale legate de utilizarea programului MATLAB pentru rezolvarea ntregii problematici numerice prezentat n capitolele anterioare. Pentru fiecare capitol, cititorul are la dispoziie rezultatele teoretice strict necesare, probleme tipice rezolvate, precum i o serie de exerciii propuse spre soluionare cititorului. Se atrage atenia c, din condiii ce in de compactizarea spaiului tipografic, apar situaii n care pe acelai rnd, se regsesc mai multe relaii, care nu pun ns probleme de interpretare la apelarea acestora.

UTM-STI

Ne exprimm convingerea c, prezenta lucrare, va aduce un plus de nelegere a problematicii numerice de calcul, dovedindu-se de o real utilitate pentru cititor. Demersul fcut n aceast lucrare va fi continuat de autori pentru o permanent perfecionare a coninutului i a modului de expunere, folosind inclusiv reacia cititorului.

Februarie 2007 Prof. univ. dr. ing. Sever ERBAN Asist. univ. drd. Magnolia TILCA

C.

CUPRINS

NOTAII ABREVIERI 1 ELEMENTE FUNDAMENTALE DE CALCUL MATRICEAL 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10 1.11 1.12 1.13 2 Introducere, 1 Vectori. Spaiul vectorial n, 1 Produs scalar. Norme vectoriale, 5 Matrice, 7 nmulirea matricelor, 10 Norme matriceale, 13 Matrice structurate, 14 Matrice bloc, 15 Matrice normale, 16 Valori i vectori proprii, 19

viii xii 1

Utilizarea algoritmului de ealon redus pe linii (AERL) pentru calculul elementelor structurale ale transformrilor liniare, 20 Rutine MATLAB, 29 Probleme propuse, 30 33

ELEMENTE FUNDAMENTALE DE CALCUL NUMERIC

S. erban, M. Tilca2.1 2.2 2.3 2.4 2.5 2.6 2.7 3 Introducere, 33 Reprezentarea numerelor n virgul mobil, 33 Operaii cu numere reprezentate n FVM, 41 Condiionarea problemelor de calcul, 43 Specificitile algoritmilor de calcul, 45 Structuri de calculatoare n corelaie cu organizarea algoritmilor, 46 Probleme propuse, 48 49

vi

SOLUIONAREA SISTEMELOR ALGEBRICE LINIARE 3.1 3.2 3.3 3.4 3.5 3.6 3.7 Introducere, 49 Transformri elementare, 49 Triangularizarea matricelor ptrate prin eliminare gaussian, 52 Tehnici de pivotare, 56 3.4.1 Pivotare complet, 56 Factorizri LU, 58 3.5.1 Factorizarea Crout compact, 60 Soluionarea sistemelor liniare, 62 Calculul inversei i al determinantului unei matrice, 64 3.7.1 Calculul inversei unei matrice, 64 3.7.2 Calculul determinantului, 68 Condiionarea sistemelor algebrice liniare, 69 Estimarea numrului de condiionare, 71

3.8 3.9 3.10

Stabilitatea numeric a algoritmilor gaussieni, 74 3.10.1. Analiza erorilor generate de algoritmii de eliminare gaussian, 74 3.10.2. Scalarea sistemelor liniare, 75 3.10.3 Creterea preciziei soluiei prin apelarea la iteraii, 76 Sisteme de tip band, 77 Sisteme simetrice, 81 Sisteme simetrice pozitiv definite, 83

3.11 3.12 3.13

Notaii i abrevieri3.14 3.15 4 Rutine MATLAB, 87 Probleme propuse, 88 91

vii

PROBLEMA CELOR MAI MICI PTRATE (CMMP) 4.1 4.2 Introducere, 91 Transformri ortogonale, 92 4.2.1 Reflectori, 92 4.2.2. Rotaii, 96 Transformri unitare, 99 4.3.1. Reflectori compleci, 99 4.3.2. Rotaii complecse, 101

4.3

4.4 4.5 4.6 4.7

Realizarea formei triunghiulare folosind transformri ortogonale, 102 Factorizarea QR, 104 Rezolvarea problemei CMMP, 105 4.6.1. Calculul pseudosoluiei, 107 Sisteme liniare subdeterminate, 109 4.7.1. Triangularizare ortogonal la dreapta, 109 4.7.2. Factorizarea LQ, 110 4.7.3. Rezolvarea sistemelor subdeterminate, 111 Rutine MATLAB, 113 Probleme propuse, 114 115

4.8 4.9 5

CALCULUL VALORILOR I VECTORILOR PROPRII 5.1 5.2 5.3 5.4 5.5 5.6 Introducere 115 Formularea problemei 115 Forma Schur 121 Metode de calcul al vectorilor proprii 126 Algoritmul QR 130 Rutine MATLAB 148

6

PROGRAMUL MATLAB -un mediu ideal de calcul i simulare

151

S. erban, M. Tilca6.1 6.2 6.3 6.4 6.5 Introducere, 151 Funcii de control general, 153 Elemente fundamentale de programare n MATLAB, 155 Instruciuni i funcii de control, 157 Funcii matematice uzuale, 159

viii

Indexul funciilor MATLAB, 161

UTM-STINOTAII i ABREVIERIn prezenta lucrare s-a ncercat respectarea cu strictee a notaiilor specifice teoriei sistemelor aa cum se prezint ele n momentul de fa, n urma unui lung proces de rafinare i uniformizare. Ca reguli generale menionm: # scalarii sunt notai cu litere de rnd; # vectorii sunt notai cu litere mici grase (bold); # liniile se reprezint prin vectori transpui; # matricile se noteaz cu litere mari grase (bold); # spaiile i subspaiile sunt desemnate de litere ronde (fonturi romneti).

Notaiile generale sunt:

Notaii i abrevieri x x 0 n u u 0 m y y 0 p v v 0 r z z 0 q t k mrimea de stare a unui sistem (starea); idem cu specificarea dimensiunii i naturii vectorului; mrimea de intrare a sistemului, uzual reprezentnd mrimea de comand (comanda); idem cu specificarea dimensiunii i naturii vectorului; mrimea de ieire a sistemului, obinuit desemnnd mrimea msurat din sistem (msura); idem cu specificarea dimensiunii i naturii vectorului; mrimea de perturbaie (perturbaia); idem, cu specificarea dimensiunii i naturii vectorului;

ix

UTM-STI

mrimea de calitate din sistem (calitate); idem cu specificarea dimensiunii i naturii vectorului; variabila independent timp; idem n cazul discret sau discretizat, cnd t ar genera confuzie; notaie unificatoare pentru cazul neted i discret;

[ ] -1 [ ] Z[ ] Z-1 [ ] s p z (A, B, C)

operatorul tranformrii Laplace; operatorul tranformrii Laplace inverse; operatorul tranformrii Z; operatorul tranformrii Z inverse; variabila complex din transformata Laplace; idem n cazul n care prin utilizarea literei s s-ar genera confuzii; variabila complex din transformata Z; variabil unificatoare pentru transformatele Laplace i Z; triplet ce specific un sistem liniar;

(A, B, C, D, E) T () T () 0 p x m () H () H () 0 () T (t), h (t) T c (t), h c (t) Im A = A (Im A) z = A Ker A A-1 Vz

UTM-STI

elementele definitorii ale unui sistem dinamic complet n forma primar; matricea de transfer a sistemului liniar; idem, cu specificarea structurii i naturii elementelor; funcia de transfer a sistemului liniar; idem, cu specificarea naturii sale; matricea, respectiv funcia pondere, la momentul t; matricea, respectiv funcia de rspuns cauzal la impuls, specificat la momentul t; imaginea transformrii liniare reprezentat de matricea A; subspaiul ortogonal pentru transformarea liniar reprezentat prin matricea A; nucleul transformrii liniare reprezentat de matricea A; imaginea invers a subspaiului V prin matricea (ptrat) A, nu neaprat nesingular; mulimea valorilor proprii ale matricii A (spectrul matricii A); mulimea valorilor singulare ale matricii A; cea mai mare valoare singular (a matricii A); cea mai mic valoare singular (a matricii A); semiplanul drept al variabilei complexe s, inclusiv frontiera (axa imaginar); semiplanul stng al variabilei complexe s, exclusiv frontiera; idem, mpreun cu frontiera; discul de raz unu, centrat n origine, fr frontiera sa; idem, mpreun cu frontiera;

(A) = ={ * det ( I - A ) = 0} (A)& & max (A) = (A) =

min (A) = (A) = + = {s * Re s $ 0 } - = {s * Re s < 0 }& - = {s * Re s # 0 } U 1 (0) = {z * * z * < 1} & U 1 (0) = {z * * z * # 1}

,,,

mulimea numerelor reale, complexe, ntregi, respectiv naturale;

Notaii i abrevieri # det (A) sau * A * rang (A) AT A* A-1 AH xH & & 2 A 2 2 = (A) = 2A2 numrul de . . . determinantul matricii (ptrate) A; rangul matricii A (nu neaprat ptrat); transpusa matricii A; adjuncta matricii A; inversa matricii A (ptrat i nesingular); transpusa conjungatei complexe a matricii A; vectorul x transpus i conjugat complex; norma doi sau norma spectral a matricii A; norma matricii A care, n cazul general, trebuie neleas ca norma Frobenius a matricii A, nu neaprat ptrat;

xi

UTM-STI

norma euclidian a vectorului x de dimensiune n;

urma matricii ptrate A;

A# AqB

pseudo-inversa matricii A (inversa Moore-Penrose); produsul Kronecker al matricilor A i B;

S. erban, M. Tilca ArB In J diag{ J i j } O R d n Rz d n N d n N z d n [ T () ] [ H () ] [ p () ] [(A, B, D)] u(.) F

xii

UTM-STI

suma Kronecker a matricilor A i B; matricea unitate de dimensiune n; forma Jordan a unei matrici; matricea cu structur bloc diagonal de elemente J i j , celelalte blocuri fiind nule; matricea nul (de dimensiuni specificate sau subnelese); subspaiul strilor controlabile; subspaiul strilor necontrolabile; subspaiul strilor neobservabile; subspaiul strilor observabile; mulimea polilor matricii de transfer; mulimea polilor funciei de transfer; zerourile polinomului (ecuaiei); zerourile (de transmisie ale) sistemului specificat n paranteze; funcia u (vectorul funcie); legea de reacie dup stare; elementele definitorii ale unui compensator dinamic;

( A c ,B c ,F c ,G c ) xc , 1, d, c,

starea compensatorului dinamic; cuantificatorii de oricare, respectiv exist; cuantificatorii de intersecie, incluziune, reuniune, respectiv reuniune disjunct (cu repetarea tuturor elementelor); sfrit al unui enun sau rezultat, atunci cnd textul nu face aceast distincie.

n problematica reglrii apar urmtoarele notaii specifice: x1 x2 zr yr z y xc2 xc1 S starea sistemului condus; starea sistemului exogen (generatorul semnalelor externe); mrimea de referin (programul de conducere) pentru mrimea de calitate; idem pentru mrimea msurat; mrimea de calitate cu sensul de eroare pe mrimea de calitate; mrimea msurat avnd semnificaia de eroare pe mrimea msurat; starea modelului intern; starea compensatorului stabilizator; matricea de deductibilitate.

Notaii i abrevieri (A 1 ,B 1 ,A 3 ,C 1 ,D 1 ,A 2 ,C 2 ,D 2 ) elementele definitorii ale sistemului condus (parte fixat) i ale aciunii semnalelor exogene;

xiii

n teoria estimatorilor (de stare) se practic notaiile nestandard: z w

(J, K, H, M, N, P)

UTM-STIAERC C CDA CSS E EL EM ERC EU I. LC MI P

mrimea de stare a estimatorului; mrimea de ieire din estimator;

elementele definitorii ale unui estimator.

ABREVIERI A. AERL CD CDS D. EF ELR ER ERL Ind. L. LR O. anex; algoritm de ealon redus pe linii; compensator dinamic; compensator stabilizator; definiie; estimator de funcional; estimator de lege de reacie; ecuaiile reglrii; ealon redus pe linii; indicaie; lem; lege de reacie; observaie; dinamic algoritm de ealon redus pe coloane; compensator; compensator dinamic alocator; compensator structural stabil; estimator; ecuaiile Luenberger; estimator minimal; ealon redus pe coloane; estimator unitar; ipotez; lege de comand; model intern; (numr de) poli;

S. erban, M. Tilca P. PCA P.R. PRIS PS (R) RM S SD SL D S Nl TDC TKS THO ZT propoziie; problem alocare; complet de PA P.P. PR intern PRSS R. problema alocrii; problem propus; problema reglrii;

xiv

problem rezolvat; problema stabile; reglrii

problema reglrii structural stabile; rspuns (rezolvare); realizarea (standard) controlabil;

problema stabilizrii;

proprietate de reglare; realizarea minimal; sistem; sistem dinamic; sistem liniar discret; sistem neliniar;

UTM-STIR(S)C R(S)O (S) SE SL N T. TDO THC Z teorem;

realizarea (standard) observabil; proprietatea de stabilitate; sistem extins; sistem liniar neted;

teorema de descompunere controlabil; teorema Kalman de structur; teorema Hautus observabilitate; zerouri de transmisie. de

teorema de descompunere observabil; teorema Hautus de controlabilitate; (numr de) zerouri;

1.

ELEMENTE FUNDAMENTALE DE CALCUL MATRICEAL

1.1. Introducere

Scopul acestui capitol este introducerea noiunilor fundamentale cu care se opereaz n calculul numeric orientat spre utilizarea calculatoarelor numerice profesionale, de ultim generaie. n egal msur sunt vizate acele programe software care utilizeaz exclusiv calculul modern cu matrici, avnd proprieti remarcabile de stabilitate numeric, timp de calcul i acuratee. Ca modalitate de prezentare, de fiecare dat sunt date, pe scurt, elementele teoretice fundamentale, dup care sunt evideniate aspectele algoritmice implicate. Se menioneaz c noiunile fundamentale aparin algebrei liniare dar, pentru completitudinea expunerii, acestea vor fi reamintite de fiecare dat.

UTM-STI

1.2. Vectori. Spaiul vectorial nDin considerente ce in de aplicabilitatea practic concret, toate entitile utilizate n continuare (scalari, vectori, matrici) sunt construite cu numere reale ; cnd este cazul, se va face extensia de rigoare la nivelul numerelor complexe , menionnd eventualele diferenieri. Vom numi scalar orice numr real, notndu-l uzual cu litere greceti mici ( 0 , 0 , 0 , etc.). a) Vectori. Un vector real, n dimensional, notat uzual cu caractere latine mici, este o colecie de n numere reale, reprezentate sub forma unei coloane ordonate ca n relaia (1.1-1); numerele reale xi i=1:n reprezint componentele vectorului (sau coordonatele sale). n cadrul textului (pentru economie de spaiu), un vector se va nota ca o linie transpus aa cum se vede n (1.1-2).

2

S. erban, M. Tilca

ANALIZ NUMERIC

(1.1)

Mulimea vectorilor n dimensionali reprezint spaiul real n - dimensional notat prin n; n cadrul lui, un vector x este reprezentat de un segment orientat cu baza n originea spaiului i vrful n punctul geometric de coordonate (x1, x2, . . . ,xn), aa cum se prezint1 n figura 1.1a. Vectorul cu toate componentele nule (originea axelor de coordonate) se numete vectorul nul i se noteaz simplu prin 0. Vectorii cu un singur element egal cu 1, toate celelalte fiind nule, se numesc vectori unitate i reprezint versorii axelor de coordonate din n (vezi figura 1.1b) i se noteaz cu

indicele artnd poziia unitii.

UTM-STIFig. 1.1. a) Un vector n 3 i coordonatele sale; b) vectorii unitate n3

(1.2)

Doi vectori cu aceeai dimensiune x, y 0 n sunt egali (x = y) dac i numai dac au toate componentele egale xi = yi , i = 1:n. Suma a doi vectori cu aceeai dimensiune x, y 0 n este vectorul z 0 n, notat z =x+y, definit prin zi = xi +yi , i = 1:n. Geometric, suma a doi vectori se face dup regula paralelogramului, aa cum se prezint n figura 1.2a. Spaiul n cu operaia de adunare definit anterior, se organizeaz ca grup comutativ, pentru c are proprietile < asociativitate: x + (y +z) = (x + y) + z;

1

Pentru claritatea reprezentrii, se folosesc spaiile 3 sau 2.

Calcul matriceal < < 0, x 0 n , x 0 (pozitivitate); < 2 x 2 = * * 2 x 2, x 0 n , 0 (omogenitate); < 2 x + y 2 # 2 x 2 + 2 y 2, x, y 0 n (inegalitatea triunghiului). (1.15) Este uor de demonstrat c 2 0 2 = 0 i c 2 - x 2 = 2 x 2, x 0 n.

UTM-STI

Se pot defini diverse norme; cea mai general este norma p cu p $ 1 (denumit i norma Hlder) (1.16) din care, prin particularizarea lui p, se obin normele cu care se opereaz n mod curent. Acestea sunt: (1.17)

(1.18) care se mai numete i norma euclidian, respectiv (1.19) Dou norme pe n (particularizate prin p i q) se numesc echivalente dac

6

S. erban, M. Tilca

ANALIZ NUMERIC (1.20)

Toate normele de tip p sunt echivalente, cele mai utilizate relaii de echivalen fiind (1.21) (1.22) (1.23) c) Ortogonalitate. Unghiul dintre doi vectori nenuli x, y 0 n se definete prin (1.24) i semnific exact unghiul geometric dintre cei doi vectori. Doi vectori nenuli x, y0n se numesc ortogonali dac unghiul dintre ei este = 90 [grade unghi], adic produsul lor scalar este nul, yT x = 0; se practic i notaia x z y. Generaliznd, vectorii x1, x2, . . . ,xm se zic ortogonali dac oricare doi sunt ortogonali adic (1.25) Vectorii dai anterior se numesc ortonormali dac sunt ortogonali i, n plus, sunt de lungimi unitare adic normele lor euclidiene sunt egale cu unu: 2 xi 22 = 1, i=1:m. Orice subspaiu de dimensiune mai mare ca unu are o infinitate de baze ortonormale, fiind de acum arhicunoscut algoritmul Gram- Schmidt de construcie a unei astfel de baze plecnd de la o baz oarecare. Teorema lui Pitagora se generalizeaz imediat n n ; astfel vectorii x, y 0 n sunt ortogonali (vrfurile lor determin un triunghi dreptunghic) dac i numai dac (1.26) Noiunea de ortogonalitate se poate extinde la subspaii liniare; astfel, spunem c vectorul x 0 n este ortogonal pe subspaiul S d n dac este ortogonal pe oricare vector din S , practicndu-se notaia x z S . Dou subspaii S , T d n se numesc ortogonale dac oricare vector s 0 S este ortogonal pe oricare vector t 0 T i se noteaz S z T . Un subspaiu T d n se numete complementul ortogonal al subspaiului liniar S d n dac cele dou subspaii sunt ortogonale i complementare; n acest caz practicm notaia S = T z sau T = S z .

UTM-STI

Calcul matriceal d) Spaiul euclidian n. Produsul scalar este o funcie f : n x n urmtoarele proprieti: 1. 2. 3. (comutativitate); f (x, y + z) = f (x, y) + f (x, z) (distributivitate); ; 6

7 cu

4. f (x, x) $0, x 0 n i f (x, x) = 0 ] x = 0 (pozitivitate). (1.27) unde suprabararea desemneaz aici conjugarea complecs. Forma clasic de definire a produsului scalar este (1.28) Doi vectori x, y 0 n sunt ortogonali dac au produsul scalar nul, y H x = 0. Spaiul n mpreun cu un produs scalar se numete spaiu euclidian. Norma unui vector x este o funcie g : n 6 + notat uzual prin g (x) = 2 x 2 i are aceleai proprieti ca n cazul real. Norma euclidian se definete prin (1.29) unde * xi * desemneaz modulul numrului complecs.

UTM-STI

1.4. Matricea) Matrice. O matrice real A cu m linii i n coloane este un un tablou bidimensional de numere reale, cu elemente notate a i j , avnd indici care desemneaz linia ( i ) i coloana ( j ). Explicit ea se reprezint astfel

(1.30)

Matricea se numete complecs dac elementele sale sunt numere din aceast clas, caz n care se noteaz A 0 m x n . Dac m = n, matricea se numete ptrat. Elementele cu indici egali desemneaz diagonala principal a matricei ptrate; suma acestor elemente se numete urma (trace) matricei, cu notaia

8

S. erban, M. Tilca

ANALIZ NUMERIC

(1.31) b) Operaii. Suma a dou matrice A, B 0 m x n este o matrice de aceeai form, definit prin (1.32) Produsul unei matrici A 0 m x n cu un scalar 0 , este matricea (1.33) Mulimea matricilor din m x n cu operaia (intern) de adunare i cea (extern) de nmulire cu scalari se organizeaz ca un subspaiu vectorial de dimensiune mn. Baza natural a acestui subspaiu este format din matricile E i j 0 m x n cu i=1:m i j=1:n, avnd toate elementele nule mai puin cel de pe poziia (i, j) care este egal cu unu. Transpusa matricii A 0 m x n este matricea B 0 n x m , notat B = AT, ce se definete prin b i j = a j i cu i=1:m i j=1:n. Sunt imediate urmtoarele egaliti: # (AT)T = A, A 0 m x n; # (A + B)T = AT + BT , A, B 0 m x n; # (A)T = AT , A 0 m x n i 0 . (1.34) Produsul matrice- vector. Pentru matricea A 0 m x n i vectorul x 0 n produsul este un vector y 0 m dat de

UTM-STI

(1.35) unde yi este componenta (i) a vectorului y. Explicit produsul se scrie astfel

(1.36)

Se remarc faptul c matricea A 0 m x n poate fi privit ca o transformare liniar scris astfel f : n 6 m , y = f( x) = A x; ea este liniar pentru c f (u + v) ) = f(u) + f(v), u, v 0 n ; f(u) = f(u), u 0 n i 0 . (1.37)

Calcul matriceal

9

Produsul matrice- vector se poate exprima i astfel: dac se evideniaz coloanele matricei A 0 m x n prin a1, a2, . . . ,an 0 m (vezi (1.38-1)) i componentele xi ale vectorului x 0 n , atunci vectorul y0 m este (1.38) care arat c y este o combinaie liniar a coloanelor matricii A. c) Matrice i subspaii liniare generate. Matricea A 0 m x n poate fi privit ca o transformare liniar ntre spaiile euclidiene n i m , n sensul c ataeaz fiecrui vector x 0 n un vector y 0 m prin dependena y = A x. Cu o astfel de accepiune, se definesc urmtoarele subspaii liniare: Imaginea transformrii A A= Az

Subspaiul ortogonal pe imaginea transformrii A =

UTM-STI

(1.39)

(1.40)

Nucleul transformrii A (1.41)

Dac se scrie ultima relaie n forma (1.42) se deduce c nucleul transformrii A este ortogonalul subspaiului imagine generat de AT. Substituind pur i simplu pe A cu AT avem c (1.43) Facem observaia c subspaiile (Im A) i ( Im A )z sunt ortogonale i complementare n m ; dac se ine cont i de relaia anterioar se obin egalitile (1.44)

10

S. erban, M. Tilca

ANALIZ NUMERIC

Substituind pe A cu AT din relaiile anterioare rezult (1.45) Rangul matricii A este dimensiunea celui mai mare minor diferit de zero (ca determinant), toi minorii de ordin mai mare fiind nuli. Ca urmare rangul matricei A este dat de numrul de coloane liniar independente adic de dimensiunea subspaiului imagine. Cum prin transpunere rangul se conserv, adic rangA = rangAT, el este dat i de numrul de linii liniar independente ale matricii. Conchidem c, pentru matricea A0 m x n , se ndeplinesc relaiile (1.46) Matricea A0 m x n cu coloane liniar independente se numete monic (are rang maximal coloan); n acest caz m $ n, rang A = n i Ker A = {0}. Dac are liniile liniar independente, matricea se zice epic (cu rang maximal linie), rezultnd c m#n, rang A = m i Im A = m. Drept cazuri particulare de matrice se poate meniona: matricea cu o coloan care este un vector i cea cu m=1, care este o linie (se reamintete c o linie se noteaz prin vector transpus). Dac o matrice se scrie cu evidenierea liniilor (aiT este, aici, linia i a matricei A), produsul Ax primete scrierea

UTM-STI

(1.47)

1.5. nmulirea matricelora) Produsul a dou matrice. Pentru matricele A0 m x q i B0 q x n , produsul lor este matricea C = AB 0 m x n definit prin

Calcul matriceal

11

(1.48) Produsul matriceal nu este comutativ. Produsul a dou matrice primete urmtoarele forme echivalente de scriere (prin evidenierea liniilor i/sau coloanelor): (1.49)

UTM-STIdin care rezult c adic fiecare coloan a lui C este o combinaie liniar a coloanelor lui A;

(1.50)

(1.51)

(1.52)

(1.53)

ce arat c (1.54) i deci fiecare linie a matricei C este o combinaie liniar a liniilor lui B. Produsul matriceal are urmtoarele proprieti: ! A(BC) = (AB)C (asociativitate);

12 ! !

S. erban, M. Tilca A(B + C) = AB + AC (distributivitate); (AB)T = BT AT.

ANALIZ NUMERIC

(1.55)

O matrice care are m = n se numete ptrat; mulimea matricelor ptrate, mpreun cu operaiile de adunare i nmulire, primete structur de inel necomutativ, elementul neutru la adunare fiind matricea nul On 0 n x n. Matricea ptrat cu toate elementele nule, mai puin cele de pe diagonala principal care sunt egale cu 1, se numete matricea unitate In 0 n x n , notat uzual cu I (dimensiunea sa este precizat de contextul n care apare); este de acum arhicunoscut c In = [e1 e2 . . . en]. Pentru A 0 n x n, dac exist X 0 n x n astfel nct AX = XA =I, se spune c A este inversabil i c X este inversa sa, notaia standard fiind A -1. Matricea A 0 n x n este inversabil dac are determinantul nenul sau, echivalent, rangA=n adic are coloanele (liniile) liniar independente. Testarea numeric a inversabilitii nu apeleaz, n general, la condiiile anterioare ci la metode mult mai sofisticate dar, n acelai timp, mult mai sigure. Mulimea matricilor ptrate i inversabile, cu operaiile uzuale de adunare i nmulire, primete structur de corp necomutativ, elementul neutru la nmulire fiind matricea unitate. Trebuie de asemenea s se rein c

UTM-STI

(1.56) b) Echivalen. Dou matrice A, B 0 m x n se numesc echivalente la dreapta dac exist T 0 n x n nesingular (inversabil) astfel nct B = A T. Dac exist S0m x m inversabil astfel nct B = S A, cele dou matrici se zic echivalente la stnga. n sfrit, dac exist T 0 n x n i S 0 m x m inversabile astfel nct B = S A T matricele A i B se numesc echivalente (bilateral). P.1.1. Dac A, B 0 m x n sunt echivalente la dreapta atunci Im A = Im B. Demonstraie. Se demonstreaz dubla incluziune Im A d Im B, Im A e Im B care valideaz egalitatea din propoziie. Astfel, dac y 0 ImB Y x a.. y=Bx Y y=ATx Y y=Az Y y 0 ImA i deci ImB d ImA; reciproc, dac y 0 ImA Y x a.. y=Ax Y y=BT -1 x Y y=Bz Y y 0 ImB i deci ImA d ImB, ceeace justific egalitatea. Relaia anterioar se poate scrie i sub forma Ker AT = Ker BT. Dac A, B 0 m x n sunt echivalente la dreapta i au coloane liniar independente, ele reprezint baze pentru ImA = ImB, iar relaia B = AT reprezint o schimbare de baz (din baza A n baza B). Acest lucru se justific imediat pentru c, dac x0ImA = ImB, avem (1.57)

Calcul matriceal

13

cu c = [1 2 . . . n]T respectiv d = [1 2 . . . n]T coordonatele vectorului x n cele dou baze. Cum ns B = AT avem x = Ac = Bd = ATd, rezultnd c = Td sau, reciproc, d= T-1 c, ceeace corespunde transformrii de coordonate ntre cele dou baze. Similar, dac A, B 0 m x n sunt echivalente la stnga atunci Im AT = Im BT, sau echivalent, Ker A = Ker B. Dac, n plus, A i B sunt baze atunci avem aj = S bj , deci S transform vectorii unei baze n cei ai celeilalte baze.

1.6. Norme matricealea) Produsul scalar matriceal este generalizarea produsului scalar vectorial. Astfel pentru matricele A, B 0 m x n , produsul scalar este

b) Normele matriceale se definesc similar cu cele vectoriale. n acest sens, o norm matriceal este o funcie g : m x n 6 + notat uzual prin g (A) = 2 A 2, care are proprietile: < 2 A 2 > 0, A 0 m x n , A O (pozitivitate); < 2 A 2 = * * 2 A 2, A 0 m x n , 0 (omogenitate); < 2 A + B 2 # 2 A 2 + 2 B 2, A, B 0 m x n (inegalitatea triunghiului).(1.59) O norm matriceal este consistent dac 2AB2#2A22B2 (1.60) atunci cnd produsul este definit. Se pot defini diverse norme; cea mai general este norma Frobenius (ce este consistent), care este norma matriceal indus de produsul scalar matriceal dat anterior (1.61) O alt clas de norme matriceale este cea definit pe baza normelor vectoriale (de aceea se numesc norme subordonate) dup relaia (1.62) Cele mai utilizate norme subordonate sunt (1.63)

UTM-STI

(1.58)

14

S. erban, M. Tilca

ANALIZ NUMERIC

(1.64) menionnd c se poate defini i o norm 2 subordonat. Se demonstreaz c norma 2 subordonat a matricii A este rdcina ptrat a celei mai mari valori proprii a matricei A T A

Toate normele subordonate sunt consistente i asigur 2 I 2=1. c) Echivalena normelor. Se poate justifica faptul c, normele matriceale sunt echivalente, cele mai uzitate relaii de legtur fiind

UTM-STI

(1.65)

(1.66)

(1.67) d) Cazul complecs. O norm matriceal peste spaiul complecs m x n este o funcie cu valori reale pozitive ce satisface aceleai condiii ca cele prezentate n cazul real. Toate definiiile i relaiile anterioare rmn valabile, cu meniunea c apar modulele scalarilor compleci; de exemplu, norma Frobenius se definete prin (1.68)

1.7. Matrice structurateSe spune c o matrice este structurat dac va conine mereu elemente nule n anumite zone ale ei. Operaiile cu matrice structurate sunt mult mai simple dect cu matrici generale, de aceea majoritatea algoritmilor au, ca o prim etap, structurarea matricilor participante. Se prezint n continuare, pricipalele tipuri de matrici structurate i proprietile lor. Numai pentru simplitate, toate exprimrile se fac pentru matrici ptrate din n x n dar, o eventual generalizare la tablouri dreptunghiulare, este imediat. # Matricea D 0 n x n se numete diagonal dac toate elemente nediagonale

Calcul matriceal #

15

sunt nule deci d i j = 0, pentru ij; Matricea T 0 n x n este superior triunghiular dac t i j = 0, pentru i>j i inferior triunghiular atunci cnd t i j = 0 cnd ii+1, respectiv superior Hessenberg cnd h i j = 0 la indici satisfcnd condiia i>j+1; # Matricea A 0 n x n se numete tridiagonal dac este simultan inferior i superior Hessenberg; # Matricea B 0 n x n se numete band de lime inferioar p dac b i j = 0 pentru i> j+p, respectiv de lime superioar q atunci cnd b i j = 0 pentru j>i+q. Operaia de adunare a matricilor structurate conserv forma acestora; i operaia de nmulire pstreaz unele forme structurate, cum ar fi: dac D este diagonal, produsul AD i DA are structura lui A; produsul a dou matrice inferior (superior) triunghiulare are aceeai structur cu operanzii; pentru L inferior (superior) triunghiular i H inferior (superior) Hessenberg, produsul LH i HL este n forma inferior (superior) Hessenberg. Operaiile cu matrici structurate se pot simplifica mult dac se apeleaz la algoritmi care in cont efectiv de prezena elementelor nule i exclud operaiile cu aceste elemente. De asemenea memorarea matricilor structurate se poate face vectorial, cu implificarea numai a elementelor nenule, putnd s rezulte economii importante de memorie.

UTM-STI

1.8. Matrice blocMatricile cu dimensiuni mari se pot partiiona cu notarea blocurilor componente. Rezult structuri matriceale ce forma

(1.69)

n care blocurile A i j au dimensiunile i x j , iar B i j sunt de forma i x j ; este clar c, de exemplu, A are ( 1 + 2 + . . . + m) linii i ( 1 + 2 + . . . + n ) coloane. Efectuarea operaiilor cu matrici bloc, presupune ca ele s aib partiionri conforme

16

S. erban, M. Tilca

ANALIZ NUMERIC

pentru ca efectuarea operaiilor s fie posibil. Astfel dac < m=p, i = i , i = 1:m i n=q, i = i , i = 1:m i n=q, j = j , j=1:n, se poate defini suma pe blocuri prin

(1.70)

j, matricea A se numete bloc superior triunghiular, respectiv bloc inferior triunghiular dac A i j = O, i < j, etc.

1.9. Matrice normaleReferindu-ne strict la matricele ptrate din n x n , se introduce urmtoarea terminologie: matrice simetrice dac A = AT adic a i j = a j i , i , j=1:n; matrice antisimetrice dac A = -AT adic a i j = -a j i , i , j=1:n, rezultnd implicit c elementele diagonale sunt nule;

Calcul matriceal matrice normale dac A AT = AT A; matrice ortogonale dac AT A = I.

17

Forma ptratic asociat unei matrice simetrice este funcia f : n 6 , definit prin (1.73) i este un polinom omogen de grad 2 n n variabile. Formele ptratice se asociaz numai matricilor simetrice pentru c, dac A nu este simetric, se opereaz cu matricea B = (A + AT)/2 care, evident, este simetric i asigur egalitatea evident xT B x = (xT A x + xT AT x)/2 = xT A x. O matrice simetric A este pozitiv definit dac forma ptratic constituit cu ea, xT A x> 0, x 0 n , x 0, practicndu-se notaia (formal) A>0. Ea se numete pozitiv semidefinit dac xTAx$0, x 0 n , care se noteaz (formal) cu A$0. Matricea A simetric se numete negativ (semi)definit dac -A este pozitiv (semi)definit. Dac nu se ncadreaz n nici una din clasele anterioare, matricea simetric se zice de semn nedefinit. Pozitivitatea unei matrice simetric, A0n x n , se verific cu testul Sylvester: A>0 dac i numai dac are toi minorii principali (n minori formai din colul stnga-sus al tabloului A) strict pozitivi.

UTM-STI

Dou matrice simetrice A, B 0 n x n se numesc congruente dac exist o matrice nesingularT 0 n x n astfel nct B = T T A T sau, reciproc, A = T -TB T -1. Congruena conserv semnul matricilor simetrice pentru c, dac A>0 este congruent cu B, atunci x TB x = x T T T A T x = (Tx) T A (Tx) >0 pentru c A>0 i Tx 0 pentru x0 deoarece T are coloane liniar independente (fiind nesingular). Matrice ortogonale. Sunt matricele cu utilizare aproape exclusiv n calculele numerice matriceale, pentru c posed o serie de proprieti remarcabile evideniate n continuare. Prin definiie, matricea ptrat Q 0 n x n este ortogonal dac se ndeplinete condiia Q T Q = In . Pentru astfel de matrice se ndeplinesc condiiile: i Q T = Q -1adic se nltur operaia de inversare matriceal care este una din cele mai dificile operaii numerice, pe fondul restriciilor de limitare a erorilor de calcul; i dac se evideniaz coloanele matricei Q, relaia de definiie se exprim prin qi T qj = 0, ij i 2 qi 22 = 1, i=1:n i deci coloanele matricei Q sunt ortonormale; i ca o generalizare, dac matricea Q 0 m x n i Q T Q =I n atunci matricea Q are coloane ortonormale (m>n i Q Q TI m), iar dac Q Q T = I m atunci liniile sunt ortonormale (n>m i Q T Q I n); i dac matricele Q, R 0 n x n sunt ortogonale, cum (Q R) T (Q R) = R TQ TQR= = R T R = I, se vede c produsul a dou matrice ortogonale este ortogonal;

18 i

S. erban, M. Tilca dac Q 0 n x n este ortogonal, cum

ANALIZ NUMERIC

(1.74) se vede c se conserv norma 2 a unui vector la nmulirea cu o matrice ortogonal; dac Q 0 n x n i R 0 m x m sunt ortogonale, iar A 0 m x n este oarecare, avem (1.75) iar din (1.76) deducem c

i

adic produsul cu matrice ortogonale conserv norma 2 a oricrei matrice. Similar, se poate arta ca 2 RAQ 2F = 2 A 2F pentru R, Q ortogonale i A oarecare. Echivalena primete i atributul de ortogonal dac se realizeaz prin intermediul unor astfel de matrici. Proiectori. Fie un subspaiu S d n. Matricea P 0 n x n se numete proiector pe S dac ImP = S i P 2 = P deoarece, pentru orice vector x0 n avem Px0ImP =S (deci Px este proiecia lui x pe S ) i, n plus, P(Px) = P 2 x = Px (vectorii din S nu sunt modificai de proiector). Dac, mai mult, P este simetric atunci se numete proiector ortogonal deoarece a r e p r o p r i1.3.Proiector ortogonal e Fig. e t i l e s p e c i f i c proiectorilor dar, n plus, avem c P(x-Px)=0 adic x-Px 0 KerP = KerP T = (Im P) z; aceasta nseamn c Px i (x-Px) sunt ortogonali (vezi figura 1.3). Cazul matricelor complexe. Toate noiunile prezentate n cazul real se refac pentru cazul complex dac n locul transpusei se introduce conjugata complex a transpusei

UTM-STI

(1.77)

Calcul matriceal

19

(notat cu indice superior H). Astfel matricea A 0 n x n se numete normal dac AA H =A H A; (1.78) hermitic cnd A H =A; unitar dac A H A = I; pozitiv definit atunci cnd este hermitic i x H Ax>0, x 0 n , x0.

1.10. Valori i vectori propriiPentru matricea A 0 n x n numrul 0 se numete valoare proprie dac exist vectorul nenul v 0 n (numit vector propriu) astfel nct (1.79) Vectorii proprii sunt determinai numai ca direcie (nu i ca mrime) pentru c, la acelai , dac v este vector propriu atunci i u=v, 0 este vector propriu. Din ultima form de scriere practicat n relaia anterioar, cum v0, este valoare proprie dac i numai dac matricea ( In - A) este singular; mai mult, sunt totdeauna n valori proprii (numrnd i multiplicitile), generate de polinomul (ecuaia) caracteristic

UTM-STI

(1.80) care este monic (coeficientul gradului este egal cu 1) i de grad n. Mulimea valorilor proprii ale matricei A se numete spectrul acesteia i se noteaz cu (1.81) Este clar c, dac A este o matrice real, polinomul caracteristic este cu coeficieni reali i atunci existena unei valori proprii complecse atrage automat prezena valorii proprii complecs conjugate; aceeai observaie este valabil i pentru vectorii proprii. Dou matrice A, B 0 n x n se numesc asemenea dac exist T 0 n x n (numit matrice de asemnare) nesingular astfel nct (1.82) Dac T este unitar matricele se numesc ortogonal asemenea. Transformrile de asemnare conserv valorile proprii pentru c (1.83) n plus, vectorii proprii sunt asemenea pentru c (1.84)

20

S. erban, M. Tilca

ANALIZ NUMERIC

Matrice simpl este matricea A 0 n x n care are toi vectorii proprii liniar independeni. O matrice simpl are n valori proprii distincte; n plus, se poate diagonaliza printr-o transformare de asemnare deoarece (V=[v1 v2 . . . vn ] este matricea vectorilor proprii care, fiind liniar independeni, este nesingular)

(1.85)

Subspaii invariante. Fie matricea A 0 n x n i un subspaiu S d n ; el se numete A- invariant dac Av 0 S , v 0 S . Este imediat c, dac S are o baz format din vectorii proprii ai matricei A, atunci el este A-invariant.

1.11. Utilizarea algoritmului de ealon redus pe linii (AERL) pentru calculul elementelor structurale ale transformrilor liniarea) Definirea structurii de ealon redus pe linii (ERL) Fie o matrice real cu m linii i n coloane A 0 m x n, care definete o transformare (sau altfel spus o aplicaie) liniar ntre spaiile3 euclidiene n i m , n sensul c, oricare ar fi u 0 n , avem (1.86) ERL este o form particular a matricii A ce se caracterizeaza prin existena numai a dou tipuri de Fig. 1.4. Structura coloane: coloanelor de tip 1. - coloane de tip 1: sunt cele de structura din figura 1.4 adic cu o singur unitate (pe linia 1#i#m), urmtoarea coloan (spre dreapta) de acelai tip avnd unitatea cu o linie mai jos (pe linia (i+1)); - coloane de tip 2: sunt acelea care conin elemente nenule pe liniile cu uniti ale coloanelor de tip 1 aflate n stnga coloanei respective. Structura unui ERL este deci cea din figura 1.5, coloanele de tip 1 fiind marcate cu sgeat, celelalte fiind de tip 2.

UTM-STI

3

Sau subspaii U d n i Y d m

Calcul matriceal

21

Fig. 1.5. Structuri posibile de ERL.

Realizarea concret a unei structuri de ERL pentru o matrice dat se face iterativ, ntrun numr finit de pai, efectund operaii care nu afecteaz rangul matricii, cu liniile sale (pstrnd deci poziia coloanelor). Aceste operaii, denumite de tip gauss (sau gaussiene) sunt: # permutri de linii; # sumri de linii ponderate cu constante diferite de zero; # nmulirea unei linii cu o constant diferit de zero. ntr-o evoluie a algoritmului de la stnga la dreapta i de sus n jos, pasul fundamental k de ciclare se descrie astfel (presupunem c s-a ajuns in linia q coloana fiind evident k): < Se exploreaz coloana k de pe poziia q pn la m i se identific primul element nenul4 care, pentru precizare, s presupunem c se afl pe linia i (q#i#m); < Se permut linia i cu linia q i deci acum pe poziia (q, k) exist un element diferit de zero; < Se mparte noua linie q prin elementul de pe poziia (q, k) efectul fiind c pe aceast poziie apare unitatea; < Cu unitatea de pe poziia (q, k) se anuleaz toate elementele de pe coloana k prin sumri ale liniei q, ponderat corespunzator, cu celelalte linii; < Se trece la coloana urmatoare (k+1) relund algoritmul de pe linia (q+1). n acest fel pe coloana k a aprut o coloan de tip 1 care nu va fi deteriorat de paii urmtori ai algoritmului. n situaia n care de pe poziia q n jos toate elementele sunt nule nseamn c aceast coloan este de tip 2 i se trece n coloana (k+1) la nivelul aceleeai linii q. Cum operaiile gaussiene cu liniile unei matrici se pot efectua prin nmulirea la stnga a acesteia cu o matrice nesingular, rezult c exist matricea (de transformare) T nesingular astfel nct TA = E (1.87) unde cu E s-a notat forma de ERL. Determinarea matricii T se face observnd c4 Ca variant de lucru, se caut elementul de modul maxim, pentru a nu genera numere mari n matrice atunci cnd se efectueaz operaii de mprire.

UTM-STI

22

S. erban, M. Tilca

ANALIZ NUMERIC operaiile de tip gauss se pot realiza nmulind la stnga matricea dat cu o matrice unitate n care s-au efectuat operaiile respective. Astfel dac, dup pasul k, matricea dat a devenit A k (convenim c A0 = A) i este necesar urmtoarea operaie gaussian (general) (1.88) transformarea Tk este cea din figura 1.6. Este uor de verificat c

are efectuat operaia cerut (1.88). n acest fel, cu transformri succesive, se aduce A la forma E, rezultnd c (1.90)

UTM-STI

Fig. 1.6. Transformarea (1.89) elementar T k

Practic, determinarea transformrii T se face aplicnd AERL matricii A, n cadrul tabloului extins (adic lucrnd cu liniile ntregului tablou) (1.91) n locul matricii unitate grupndu-se matricea T. Evident, coloanele de tip 1 sunt liniar independente, iar cele de tip 2 sunt liniar dependente de cele de tip 1 aflate n stnga lor, coeficienii de dependen liniar fiind chiar coeficienii de pe coloana respectiv. b) Calculul rangului unei matrice Rangul matricei A este dat de numrul de coloane liniar independente i deci, din forma de ERL, rezult imediat ca fiind numrul de coloane de tip 1. c) Calculul subspaiului imagine i a complementului su ortogonal Subspaiul imagine A = Im A d m ce corespunde transformrii reprezentat de matricea A este (1.92) A = Im A = { y 0 m * y = A u , u 0 n } Atunci o baza pentru A este dat de coloanele liniar independente deci de cele ce corespund coloanelor de tip 1; cum coloanele nu au fost modificate ca poziie, identificarea coloanelor liniar independente se face uor pe baza formei de ERL.

Calcul matriceal

23

Complementul ortogonal al subspaiului A este A z = { z 0 m * z z y, y 0 A } = {z 0 m * z T y = 0, y 0 A } = = { z 0 m * z T A u = 0, u 0 n } = { z 0 m * z T A = 0 } (1.93) Dac se aplic AERL pentru matricea A n cadrul tabloului extins [ A | Im ] atunci se determin i transformarea T care intervine n (1.87); scriind explicit aceast egalitate pe baza partiiei pe care o induce structura lui E rezult (1.94) ultima relaie artnd c o baz pentru A z este reprezentat de matricea T2 . Desigur c orice combinaie liniar a vectorilor baz reprezint tot o baz; de aceea plecnd de la bazele deduse, se pot obine baze mai simple efectund operaii gaussiene cu coloanele acestora. d) Calculul nucleului unei transformri

Fie o transformare liniar, definit prin matricea A, aa cum se prezint n (1.86). Atunci nucleul acestei transformri este (1.95) Conform cu (1.93) se poate scrie Az sau pur i simplu renotnd (1.97) Aceast ultim relaie arat c nucleul transformrii definit de matricea A se poate calcula ca ortogonalul subspaiului imagine pentru AT i ca urmare el se poate determina cu AERL aplicat tabloului extins [ A T * I n ]. O.1.1. Desigur c se poate concepe i o form de ealon redus pe coloane (ERC), definit de o manier similar cu cea de ERL, operaiile efectundu-se ntre coloanele matricii. Efectund un ERC pentru A n cadrul tabloului extins se realizeaz transferul (1.98) ar rezulta direct Ker A. Pentru a nu complica lucrurile preferm s ramnem numai la AERL, nucleul calculndu-se ca ortogonalul lui AT. (1.96)

UTM-STI

24

S. erban, M. Tilca

ANALIZ NUMERIC

O.1.2. n cazul particular n care A este ptrat (A 0 n x n ) i nesingular, ERL este chiar matricea unitate i deci transformarea T obinut din tabloul extins este matricea invers A-1. Acest caz particular reprezint algoritmul Gauss de inversare a unei matrice.P.R.1.1. Fie matricele

(1.99)

a) S se determine matricea R=[ B AB A2B A3B A4B A5B ] (se atrage atenia c blocurile matricei R se calculeaz succesiv folosind blocul anterior; astfel A2B = A (AB), A3B=A(A2B), etc.); b) S se calculeze folosind AERL: r = rangul lui R, o baz R1 pentru subspaiul R = Im R, o baz S1 pentru R z = (Im R)z , respectiv o baz T = [ R1 S1 ] pentru ntregul spaiu 6 ; c) Utiliznd AERL s se determine T-1 ; d) S se constituie matricea Q n care blocurile C, CA, CA2, CA3, CA4, CA5 sunt plasate pe linii; e) Cu AERL s se determine o baz Q1 pentru Ker Q, respectiv o baz N1 pentru (Ker Q)z rezultnd astfel o alt baz, notat V=[ Q1 N1 ], pentru ntregul spaiu 6 ; f) Determinai matricea de legtur dintre cele dou baze T i V ale spaiului 6 (schimbare de coordonate). R. a) Matricea R se determin uzual (pentru reducerea volumului de calcul, se folosete indicaia dat)

UTM-STI

(1.100)

b) Pentru a determina direct toate elementele pretinse, se aplic procedura de ERL tabloului extins (s-au dat i etapele intermadiare)

Calcul matriceal

25

(1.101)

UTM-STI(1.102) Se vede c: rang R = dim R = 3; primele 3 coloane ale lui R sunt liniar independente i ca urmare pot reprezenta o baz a subspaiului imagine; este evideniat i matricea S1 care reprezint o baz pentru subspaiul ortogonal. Ca urmare se poate se poate scrie c

R

Rz

(1.103)

i atunci o baz pentru ntregul spaiu este

26

S. erban, M. Tilca

ANALIZ NUMERIC

(1.104)

c) Se determin T-1 cu algoritmul de ealon redus pe linii aplicat tabloului extins (se dau toate etapele intermediare)

UTM-STI

(1.105)

din care se deduce matricea invers. d) Matricea Q se calculeaz obinuit, folosind relaiile de recuren CAk+1 = (CAk ) A, rezultnd

Calcul matriceal

27

(1.106)

e) Se aplic AERL tabloului [ QT * I6 ] rezultatul fiind (exerciiu pentru cititor)

UTM-STI

din care se deduce c

(1.108)

i se scrie imediat baza V = [ Q1 N1 ]. f) Pentru a determina transformarea de legtur ntre cele dou baze scriem (1.109) i atunci rezult c schimbarea de coordonate este reprezentat prin matricea S (exerciiu pentru cititor)

(1.107)

28

S. erban, M. Tilca

ANALIZ NUMERIC

(1.110)

P.R.1.2. S se deduc o baz mai simpl (cu mai multe zerouri) pentru 6 plecnd de la baza T dedus anterior, prin combinaii liniare ntre vectorii ce compun aceast baz. R. Combinnd liniar coloanele lui T (identificai coeficienii de dependen liniar) se obin succesiv

UTM-STI

(1.111)

ultima baz fiind mult mai potrivit pentru calculele ulterioare.

Calcul matriceal

29

1.12. Rutine MATLABProgramul MATLAB opereaz cu matrice; acestea se generez astfel: T se introduc elementele liniilor separate prin , (virgul) sau blanc; T pentru a trece la o nou linie se folosete ; (punct i virgul) sau Enter; T dac nu ncap toate elementele pe o linie, simbolul . . . (trei puncte) semnalizeaz programului continuarea pe linia urmtoare; T elementele matricei pot fi numere (reale, complecse), sau expresii; T matricea se delimiteaz prin paranteze drepte [ ].Astfel a=[2.1456,-35.5873,sqrt(2^3-log10(.56*4^(-.2569)));exp(3^2.0156),... -log2(35.2896),-2.3578] sau a=[2.1456 -35.5873 sqrt(2^3-log10(.56*4^(-.2569))) exp(3^2.0156) -log2(35.2896) -2.3578] genereaz aceeai matrice, scris aici cu formatul numeric long e a= 2.1456e+000 -3.5587e+001 2.8994e+000 9.4671e+003 -5.1412e+000 -2.3578e+000

UTM-STI kron magic pascal toeplitz vander wilkinson Tensorul Kronecker; Ptratul magic; Matricea Pascal; Matricea Toeplitz; Matricea Vandermonde; Matricea Wilkinson.

Matricele speciale se pot genera direct prin funcii dedicate:zeros ones eye rand randn compan diag hadamard hankel hilb invhilb Matricea nul de dimensiuni specificate; Matrice cu toate elementele 1, de dimensiuni specificate; Matricea unitate de dimensiune specificat; Matrice cu numere aleatoare de distribuie uniform; Idem cu distribuie normal; Companionul matriceal; Matrice diagonal; Matricea Hadamard; Matricea Hankel; Matricea Hilbert; Matricea Hilbert invers;

Programul MATLAB dispune de urmtoarele funcii de analiz matriceal:det inv rank trace rref norm cond Calculeaz determinantul matricei (ptrate); Calculeaz inversa matricei ptrate (nesingulare); Determin rangul matricei (dreptunghiulare); Calculeaz urma matrice (ptrate); Determin forma de ealon redus pe linii (cu operaii gaussiene); Determin norma unui vector; Estimeaz numrul de condiionare a matricei.

Manipulri de matrice se pot face cu funciile:

30

S. erban, M. Tilca

ANALIZ NUMERIC

diag fliplr flipud reshape rot90 tril triu :

Creaz sau extrage diagonalele matricelor; Rotete matricea n jurul axei verticale (permut coloanele); Rotete matricea n jurul axei orizontale (permut liniile); Schimb dimensiunile unei matrice; Rotete matricea cu un multiplu de 90 grade; Extrage matricea inferior triunghiular dintr-o matrice; Extrage matricea superior triunghiular; Specific indicii, rearanjeaz sau decupeaz o submatrice.

Operaiile uzuale cu matrice se scriu n MATLAB ntr-o form absolut natural:Operaia Simbol algebric Adunare Scdere nmulire mprire la dreapta mprire la stnga Ridicare la putere Transpunere + x : : Scalari Exemplu MATLAB a+b a-b a*b a/b a\b a^n Matrice Exemplu MATLAB a+b a-b a*b a/b a\b a^n a

UTM-STI

1.13. Probleme propuseP.P. 1.1. S se demonstreze c un subspaiu liniar din n este un spaiu vectorial. P.P. 1.2. S se demonstreze inegalitatea * xT y *#2 x 22 2 y 22 , x, y 0 n (inegalitatea Cauchy -Buniakowski -Schwarz). P.P. 1.3. S se determine vectorii liniar independeni x, y 0 n pentru care s se realizeze egalitatea 2 x + y 2p = 2 x 2p + 2 y 2p unde p = 1, 2, 4. P.P. 1.4. (Procedura Gram- Schimdt de ortogonalizare) Fie B ={b1 , b2 , . . . , bq } o baz oarecare pentru subspaiul S d n. Folosii urmtoarea procedur iterativ (1.112) pentru a determina A ={a1 , a2 , . . . , aq } ortogonal. Cum se determin n continuare o baz ortonormal? P.P. 1.5. Fie vectorii x 0 m i y 0 n cu care se calculeaz matricea A=xy T0m x n. S se arate c rangA = 1.

Calcul matricealP.P. 1.6. Dac B este o submatrice oarecare a lui A atunci

31

(1.113) P.P. 1.7.S se demonstreze c (1.114) P.P. 1.8. Demonstrai inegalitile (1.65), (1.66) i (1.67). P.P. 1.9. Cnd inegalitile anterioare devin egaliti? P.P. 1.10. S se justifice

UTM-STIP.P. 1.11. Pentru matricea A 0 n x n nesingular este adevrat egalitatea P.P. 1.13. S se demonstreze c dac A 0 n ortogonal diagonalizabil.x n

(1.115)

(1.116) P.P. 1.12. Pentru orice matrice A 0 n x n strict inferior (superior) triunghiular se ndeplinete relaia A n = O (nilpoten). este o matrice simetric atunci ea este

P.P. 1.14. Fie A 0 n x n o matrice simetric pozitiv definit. S se arate c (1.117) este o norm vectorial. P.P. 1.15. Dac A 0 n x n este o matrice simetric pozitiv definit atunci ea este inversabil i, n plus, A - 1 este pozitiv definit. P.P. 1.16. Dac A 0 n x n este o matrice simetric i triunghiular, ea este diagonal. P.P. 1.17. Cum este A 0 n x n dac este o matrice antisimetric i triunghiular? P.P. 1.18. Dac A 0 n x n este o matrice triunghiular i ortogonal atunci ea este diagonal.

32

S. erban, M. Tilca

ANALIZ NUMERIC

P.P. 1.19. Dac se consider matricea A 0 n x n i x = u + i v 0 n cu u, v 0 n este un vector propriu atunci i (u - i v) este vector propriu. P.P. 1.20. Dac A 0 n x n este o matrice simetric pozitiv definit atunci ea are toate valorile proprii reale i pozitive. P.P. 1.21. S se justifice relaiile (1.21), (1.22) i (1.23). P.P. 1.22. Justificai ultima egalitate din (1.58). P.P. 1.23. Demonstrai c norma Frobenius este consistent.

UTM-STI

2.

ELEMENTE FUNDAMENTALE DE CALCUL NUMERIC

UTM-STI2.1. IntroducereCalculul numeric pe un calculator este permanent tarat de erori de calcul datorit faptului c lungimea registrelor este finit. n acest sens apar ca principale surse de eroare: erorile de reprezentare datorate faptului c toate numerele utilizate au o lungime fix de bii, mai mare sau mai mic, n funcie de tipul calculatorului, dar oricnd prezent; erori de rotunjire sunt datorate faptului c rezultatele tuturor calculelor se reprezint tot sub form finit de bii. Folosind programul MATLAB s-a efectuat acelai calcul echivalent cu numere reale, rezultatele fiind: G .01+.02-.03 = 0 G .01-.03+.02 = 3.469446951953614e-018 G -.03+.02+.01 = 1.734723475976807e-018 (2.1) G (.1+.2-.3)*.1 = 5.551115123125783e-018 Desigur, de fiecare dat, erorile de calcul sunt mici dar ele sunt totui prezente; din acest moment este problema determinrii cauzelor ce le-au determinat i a modului cum se propag acestea la continuarea calculelor, existnd posibilitatea, deocamdat ipotetic ca, dup mii de calcule, rezultatul s fie complet viciat.

2.2. Reprezentarea numerelor n virgul mobilConform cu cele prezentate anterior fie un numr x i fie & o aproximare a sa. x Eroarea de reprezentare se poate exprima prin: < eroarea absolut

34

S. erban, M. Tilca

ANALIZ NUMERIC (2.2)

y reprezentate n FVM cu t ranguri pentru mantis i care au primele k cifre egale, adic sunt

UTM-STI

(2.38) unde s-a dat i reprezentarea lor n FVM cu parametrii (, t, p). Rezultatul scderii n FVM este (2.39) egal cu cel efectuat uzual. La operarea cu valorile exacte se obine ns (2.40) i eroarea relativ este (2.41) i deci, dac k este apropiat de t, rezult erori foarte mari. De aceea scderea numerelor foarte apropiate trebuie evitat eventual printr-o adaptare corespunztoare a algoritmului.

2.4. Condiionarea problemelor de calculCalculele numerice efectuate pe un calculator numeric sunt aferente unei probleme concrete, bine precizat; se subnelege c existena i unicitatea soluiei problemei de calcul reprezint condiii primare i eseniale, fr de care se pierde complet sensul rezolvrii sale numerice. Discutnd la modul general, o problem de calcul revine la evaluarea funciei

Calculul n virgul mobil

43 (2.42)

n punctul x 0 cunoscut, cele n componente ale lui x reprezint datele de intrare, rezultnd y 0 m cu m componente ce corespund datelor de ieire. Trebuie s acceptm din start c rezultatele obinute sunt aproximative, cum de altfel chiar reprezentarea datelor de intrare comport un anume grad de imprecizie. Pentru a caracteriza erorile menionate se folosesc urmtoarele noiuni: # condiionarea problemei de calcul; # stabilitatea algoritmului de calcul. D.2.3. Condiionarea numeric sau sensibilitatea local a problemei (2.42) n punctul x 0 se exprim prin amplificarea erorilor relative, adic prin (2.43) unde s-a presupus c definirea are sens, adic x 0 i f(x) 0. Problema este bine condiionat n punctul x dac (x) este mic (cel mult de ordinul unitii), n caz contrar fiind ru condiionat. O problem se zice bine condiionat dac are aceast calitate n oricare x 0 ; dac exist x 0 n care proprietatea nu are loc se spune c este ru condiionat. Pe de alt parte, pentru a rezolva o problem de calcul, este necesar s se apeleze la un anume algoritm de calcul care specific n fapt secvena operaiilor de calcul necesare soluionrii. Menionm c, pentru aceeai problem de calcul, se pot imagina mai muli algoritmi de calcul, uneori complet diferii ntre ei. Un algoritm ataat problemei f se exprim prin (2.44) unde s-a specificat n mod expres c el opereaz cu date exprimate n FVM. D.2.4. Un algoritm &, destinat rezolvrii problemei f, se numete numeric stabil dac f se ndeplinete una din urmtoarele condiii ! (i) &(x) este aproape de f(x) pentru oricare intrare x, adic soluia determinat f cu ajutorul algoritmului aproximeaz bine soluia exact; ! (ii) pentru orice intrare x exist & 0 , apropiat de x astfel nct f( & ) s fie x x & egal cu f (x), deci soluia calculat cu & folosind date exacte este egal cu f soluia exact pentru date de intrare uor perturbate. n caz contrar algoritmul este numeric instabil. Se remarc faptul c cele dou condiii sunt similare. Ele sugereaz ns cele dou

UTM-STI

44

S. erban, M. Tilca

ANALIZ NUMERIC

modaliti de interpretare a erorilor ce caracterizeaz stabilitatea numeric a & algoritmului i anume: 2 f (x) - f (x) 2 reprezint eroarea nainte deoarece este & asociat cu sensul de calcul al algoritmului, iar 2 x - x 2 se numete eroarea napoi pentru c se asociaz cu revenirea n spaiul datelor dup aplicarea algoritmului (vezi figura 2.2).

UTM-STIFig.2.2. Semnificaia erorilor nainte i napoi

Este important c utilizarea unui algoritm numeric stabil la rezolvarea unei probleme bine condiionate va furniza un rezultat cu o bun precizie. Astfel, pentru un x conform definiiei anterioare, exist & astfel nct se ndeplinete relaia x (2.45) iar din condiionarea numeric a problemei avem (2.46) unde i sunt de ordinul unitii. Ca urmare, folosind egalitatea ultim din (2.45), se obine (2.47) ceeace justific afirmaia fcut. O.2.4. n calculul numeric este o distincie clar ntre termenul precizie -care depinde de numrul de cifre semnificative de reprezentare a numerelor din FVM i acurateece caracterizeaz mrimea erorii dintre rezultatul calculat cu un algoritm i cel exact. P.R.2.8. Calculul sumei a dou numere reale (care se formuleaz prin f(x,y)=x+y) poate fi o

Calculul n virgul mobil

45

problem bine sau prost condiionat n funcie de operanzi. Astfel dac datele exacte x i y sunt perturbate cu acelai ordin de mrime (2.46) eroarea relativ corespunztoare sumei este (2.43) Dac x i y au acelai semn, unic i pentru 1 i 2 , relaia anterioar devine

UTM-STI

(2.43)

adic eroarea este de ordinul erorii operanzilor (buna condiionare). Dac ns x i y au semne diferite, ca de altfel i 1 i 2 , iar (2.43) deci operanzii sunt de valori absolute foarte apropiate, cu definirea (2.43) reprezentnd o margine a erorii, rezult c >> (condiionare rea). Ex. 2.9. Algoritmul uzual de adunare este numeric stabil pentru c (2.46) adic rezultatul este tarat de o eroare de ordinul de mrime a operanzilor.

2.5. Specificitile algoritmilor de calculAlgoritmii de calcul se pot analiza i din punct de vedere al unor atribute proprii ce se evideniaz n continuare. T Numrul de operaii condiioneaz direct timpul de calcul pretins de algoritmul respectiv. Se denumete flop o operaie elementar de adunare, scdere, nmulire sau mprire; ca urmare numrul de operaii este dat de numrul de flopi necesari obinerii rezultatului. Cum, dependent de calculator, execuia unui flop presupune un interval de timp bine precizat, avem i o msur a timpului total de calcul pretins de algoritm. Dei numrul de flopi, notat cu Nop , depinde de complexitatea algoritmului, uzual este o funcie de numrul datelor de intrare n, exprimat ca un polinom cu grad precizat Nop = f(n) = a0 nk + a1 nk-1 + . . . + ak a0 nk unde n ultima

46

S. erban, M. Tilca

ANALIZ NUMERIC

T

T T

aproximare s-a pstrat numai termenul semnificativ; n aprecieri pur calitative se scrie c Nop = O ( nk ). Volumul de memorie necesar reprezint numrul de elemente n FVM necesar pentru rularea algoritmului (date de intrare, de ieire, rezultate intermediare). Reducerea volumului de memorie este un deziderat natural pentru algoritmii complicai, pentru realizarea cruia multe calcule se fac pe loc adic folosind aceleai locaii de memorie. Stabilitatea numeric a algoritmului a fost prezentat pe larg n paragraful anterior. Sigurana n funcionare este capacitatea algoritmului de a furniza rezultate corecte pentru toate combinaiile posibile ale datelor de intrare, precum i capabilitatea sa de a semnala situaiile n care rezultatul este eronat datorit proastei condiionri a problemei.

UTM-STI

2.6. Structuri de calculatoare n corelaie cu organizarea algoritmilorClasica main (calculator) von Neumann are structura din figura 2.3; pentru efectuarea calculelor presupuse de un algoritm operanzii se aduc din memoria M n unitatea central UC, se efectueaz operaia implicat iar rezultatul este depus din nou n M. La o astfel de organizare timpul de calcul depinde de cel necesar efecturii operaiei matematice precum i de timpii de transfer ntre M i UC, adic este proporional cu numrul de flopi. Calculatoarele vectoriale au structura din figura 2.4 i cuprinde memoria M, unitatea central scalar UCS care este de form clasic (efectueaz operaii matematice cu scalari, respectiv unitatea central vectorial UCV astfel organizat nct poate efectua operaii cu vectori (cu secvene de scalari). Aceasta se asigur prin modul de organizare a UCV precum i modului de comunicare a acesteia cu M. dac algoritmul este organizat (dominant) pe operaii cu vectori va rezulta o reducere substanial a timpului de calcul.

Calculul n virgul mobil

47

UTM-STIFig.2.3. Arhitectur de tip von Neumann Fig.2.4. Arhitecur vectorial

Calculatoarele cu memorie ierarhic au structura din figura 2.5, principala inovaie fiind prezena a cel puin dou niveluri de memorie. La limit este prezent o memorie rapid MR cu timp de acces mult mai mic dect al memoriei pricipale MP. n acest caz tranferurile ntre MR i unitatea central UC beneficiaz de timpi mult mai mici dect timpii de calcul; cum timpul de acces spre MP este mult mai mare, un algoritm eficient de calcul trebuie s apeleze la ct mai mai puine astfel de tranferuri, ceeace ce presupune o organizare a calculelor la nivel de bloc de matrice toate depozitate n MR. Calculatoarele paralele propun o alt arhitectur, constituit pe baza Fig.2.5. a mai multe procesoare identice, care pot lucra independent i care Arhitectur cu coopereaz printr-un mediu de comunicaie eficient. memorieierarhic

48

S. erban, M. Tilca

ANALIZ NUMERIC

2.7. Probleme propuseP.P.2.1. Reprezentai n baz 2 numrul (1643.023)10 i verificai corectitudinea reprezentrii. P.P.2.2. Reprezentai numrul binar obinut anterior n FVM asociat simplei precizii (2,24,7). P.P.2.3. Idem n FVM asociat dublei precizii (2,53,10). P.P.2.4. Fie numerele a1 = 0.002, a2 = 2 i a3 = -2 reprezentate n FVM (10,3,1). Care este eroarea relativ la efectuarea calculului x= a1 + a2 + a3 ? P.P.2.5. Fie FVM (,t,p); care este numrul mai mare ca 1 i cel mai apropiat de acesta, reprezentabil exact n formatul dat. P.P.2.6. Care din formulele a2 - b2 sau (a - b) (a + b) se recomand pentru calculul n FVM? P.P.2.7. Folosind FVM (10,3,1), soluionai ecuaia de gradul 2, ax2 +bx+c=0 cu a0, utiliznd relaiile uzuale de calcul (2.47) atunci cnd a=1.22, b=3.34 i c=2.28. Comparai rezultatele obinute cu cele calculate exact. Dai o explicaie apariiei erorilor foarte mari de calcul. P.P.2.8. Pentru problema anterioar utilizai relaiile echivalente de calcul a rdcinilor (2.48) Ce putei spune despre acurateea noilor rezultate? P.P.2.9. Care sunt numerele reale (exprimate n baza 10) ce se reprezint exact n FVM (2,3,1)?

UTM-STI

3.

SOLUIONAREA SISTEMELOR ALGEBRICE LINIARE

UTM-STI3.1. IntroducereSe abordeaz aici problema rezolvrii sistemului algebric liniar n necunoscuta x (3.1) unde se presupune c A este inversabil adic sistemul are o unic soluie. Se practic dou clase de metode numerice cu o bun stabilitate: Metode directe ce apeleaz la o secven de transformri elementare care aduc matricea A la una sau dou forme triunghiulare, aplicabile pentru cazul sistemelor de dimensiuni medii n k+r. Lucrul acesta este vizibil dac urmrim figura 3.3 pentru c: dac pe prima coloan primul pivot este localizat pe linia i101:r+1 i permutarea liniilor 1 i i1 face ca prima linie s aib elemente nenule (cazul cel mai nefavorabil) pe coloanele 1: 1+q+r, rezult c (3.96) i n atribuirea A 7 T1 A, exprimarea explicit fiind (3.97) rezult (3.98) adic elementele specificate nu se modific. Ca urmare se produc modificri numai pentru elementele din blocul A(2: 1+r, 1: 1+q+r). Matricea A rmne, n rest, band inferioar de lime r iar pe prima linie este band superioar de lime q+r i pe liniile 1+r: n band de lime superioar q. Toate aceste consideraii se menin i pentru paii urmtori k= 2, 3, . . . n-1. Pivotarea parial face ca matricea U s rezulte band superioar de lime mai mare dect cea a matricei A; n plus, matricea inferior

80

S. erban, M. Tilca

ANALIZ NUMERIC

triunghiular L nu mai este band cum rezulta n cazul algoritmului fr pivotare.

UTM-STIFig. 3.4. Eliminare gaussian cu pivotare parial pentru cazul unei matrice band (aici, pentru precizare, de lime inferioar 2 i superioar 1). Se accept faptul c pivotarea se face aici cu linia cea mai ndeprtat.

Se obine atunciAlgoritmul 3.16. (GPPb -Eliminare gaussian cu pivotare parial pentru o matrice band) Se d o matrice A0 n x n band nesingular de lime inferioar r i superioar q. Se determin matricea U superior triunghiular, transformrile elementare (ITE) Tk (memorate peste matricea A) i permutrile elementare (PE) Pk (memorate n vectorul p) ce asigur egalitatea U=T n-1 P n-1 T n-2 P n-2 . . . T 1 P 1 A. 1. Pentru k = 1: n-1 1. Pentru r1=min(k+r, n), q1 = min(k+q+r, n) 2. Se determin ik 0k: r1 a. . 3. p (k) 7 ik 4. Pentru j = k: q1 1. 5. Pentru i = k+1: r1 1. 6. Pentru i=k+1: r1 1. Pentru j=k+1: q1 1. aij 7 aij - ik akj

Sisteme algebrice liniare

81

3.12. Sisteme simetricen cazul sistemelor algebrice liniare A x= b, la care matricea A este simetric (adic A=AT), pot s rezulte reduceri importante ale volumului de calcul (a numrului de operaii) dac se ine cont de proprietatea de simetrie. Algoritmul de eliminare gaussian trebuie ns adaptat astfel nct s se conserve structura simetric a matricei pe toat durata algoritmului. Dac analizm primul pas din algoritmul G, constatm c prin alocarea A 7 T1 A (unde T1 = I - t1 e1T ) este distrus simetria dintre prima coloan (care are toate elementele subdiagonale nule) i prima linie (care, n general, nu are aceast particularitate), n timp ce restul matricei pstreaz simetria deoarece

UTM-STI

(3.99)

Ca urmare nu trebuie calculate toate elementele anterioare ci numai jumtate din ele (de exemplu, cele din triunghiul inferior) rezultnd o reducere la jumtate a numrului de calcule. Pentru refacerea simetriei la nivelul primei linii i coloane, se face alocarea urmtoare A 7 T1 A T1T care nu afecteaz dect prima linie, introducnd zerouri pe toate coloanele ei, mai puin pe prima poziie. Mai mult, nmulirea efectiv la dreapta nici nu trebuie efectuat deoarece rezultatul este cel menionat anterior. Procednd similar pentru celelalte coloane se obine factorizarea (3.100) cu D o matrice diagonal. Din relaia anterioar rezult (3.101) i un algoritm care realizeaz aceast factorizare cu L inferior triunghiular unitate, i D diagonal, ambele memorate n A, este dat n continuareAlgoritmul 3.17. (Factorizarea matricelor simetrice) Se d o matrice A0 n x n simetric i nesingular. Se determin matricea L inferior triunghiular unitate i matricea diagonal D (memorate peste matricea A). Se folosete vectorul auxiliar p pentru salvarea elementelor coloanei curente k, egale cu cele ale liniei k n triunghiul superior, pe poziiile crora se memoreaz multiplicatorii.

82

S. erban, M. Tilca

ANALIZ NUMERIC

1. Pentru k = 1: n-1 1. Pentru i = k+1: n 1. p i 7 a i k 2. 2. Pentru j = k+1: n 1. Pentru i = j: n 1. aij 7 aij - aik pj

Procedura menionat anterior nu a presupus c toate submatricele lider principale sunt nenule, de aceea algoritmul anterior poate s eueze. Este deci necesar ca s se introduc pivotri dar acestea altereaz simetria matricei. Nici ideea permutrilor simetrice, adic a alocrilor de forma A 7 P1 A P1T, nu este viabil deoarece face permutri numai de elemente diagonale (care ar putea s fie nule). Soluia problemei este reprezentat de o factorizare cvasi- diagonal, definit n T.3.5. Pentru matricea A0 n x n simetric i nesingular, exist o matrice L inferior triunghiular unitate, o matrice cvasi- diagonal D cu blocuri diagonale de dimensiune q=1 sau q=2 i o matrice de permutare P astfel nct se asigur egalitatea (3.102) care se numete factorizarea cvasi- diagonal (matricea D este inversabil). Demonstraie. Primul pas al procedurii de factorizare se aplic matricei (3.103) unde E este un bloc qxq iar P1 este o matrice de permutare. Dac A este inversabil atunci i E este inversabil pentru c: dac a11 0 se ia q=1 i P1 = I; dac a11 = 0, cum exist sigur un a1j 0 (altfel A ar fi singular) i atunci se ia s=2 i P1 se ia s permute liniile unu cu j i deci det(E) = - a1j2 0. Pentru a determina primele q coloane ale factorizrii LD se utilizeaz relaia (3.104) Pentru q=1 factorizarea anterioar se face dup schema dat de factorizarea LDLT; pentru q=2 determinarea lui E-1 se face, cel mai simplu, dup relaia analitic de calcul adic

UTM-STI

Sisteme algebrice liniare

83

(3.105) iar restul calculului este banal. Se obine astfelAlgoritmul 3.18. (FCD -Factorizare cvasi -diagonal) Se d o matrice A0 n x n simetric i nesingular. Se determin matricea L inferior triunghiular unitate, matricea cvasi -diagonal D, cu blocuri de forma 1x1 sau 2x2 i matricea de permutare P. Matricele L i D se memoreaz peste A dar este necesar un spaiu suplimentar pentru salvarea temporal a coloanei (coloanelor, dac q=2) curente din matricea A care este asigurat aici de matricea notat M0 n x 2. Pentru calculul matricei P, vezi algoritmii anteriori. 1. k 7 1 2. Dac k < n 1. Se determin Pk i q 2. Se efectueaz permutarea A 7 Pk A PkT 3. Dac q=1 atunci 1. Pentru i = k+1: n 1. m i 1 7 a i k 2. Altfel 2. 3. Pentru i = k+2: n 1. mi1 7 aik , mi2 7 ai, k+1 2. aik 7 aik e11 + ai, k+1 e21 3. ai, k+1 7 mi1 e21 + ai, k+1 e22 4. Pentru j=k+q: n 1. Dac q=1 atunci 1. aij 7 aij - ai, k mj1 Altfel 2. ai, j 7 aij - aik mj1 - ai, k+1 mj2 5. k 7 k + q

UTM-STI

3.13. Sisteme simetrice pozitiv definiteS considerm sistemul algebric liniar A x = b n care A0 n x n este simetric i pozitiv definit. Rezolvarea sistemului dat anterior are la baz urmtorul rezultat

84

S. erban, M. Tilca

ANALIZ NUMERIC

T.3.6. Pentru orice matrice A0 n x n simetric i pozitiv definit, exist o unic matrice L inferior triunghiular cu elemente diagonale pozitive, astfel nct (3.106) care se numete factorizarea Cholesky (matricea L este factorul Cholesky al matricei A). Reciproc, dac factorizarea Cholesky exist, atunci matricea A este pozitiv definit. De reinut c factorizarea anterioar se poate scrie i sub forma (3.107) unde R = LT este superior triunghiular, care este tot o factorizare Cholesky.Demonstraie. Deoarece matricea A este pozitiv definit, submatricele lider principale A[k], k=1: n-1, sunt pozitiv definite deci nesingulare. Ca urmare A are o unic factorizare LDU pe care o notm A = L / D U / = L / D (L / )T, ultima relaie fiind o consecin a simetriei. Urmarea echivalenei dintre A i D este i faptul c D este pozitiv definit, adic d i i >0. Se introduce matricea diagonal F0 n x n, denumit matrice radical, definit prin

UTM-STI

(3.108)i L L / F, cu care se obine factorizarea (3.106). Pentru reciproc, cum

(3.109)rezult c A este pozitiv definit.

Pentru a obine un algoritm de factorizare a matricelor simetrice pozitiv definite vom apela la un calcul a factorului Cholesky n ordinea cresctoare a coloanelor; din identitatea A = L LT se obine scrierea explicit (pentru c A este simetric s-a reprezentat numai triunghiul inferior)

(3.110)

din care, pentru prima coloan, avem

(3.111)

Sisteme algebrice liniare

85

n continuare, presupunnd c primele (k-1) coloane au fost calculate, identificnd poziia (k, k) a factorizrii se obine (3.112) unde condiia din parantez este asigurat de faptul c A este pozitiv definit. Continund, se poate scrie

din care, pe sensul de calcul, se scoate necunoscuta

UTM-STI

(3.113)

(3.114)

Trebuie reinut c algoritmul de factorizare Cholesky este i testul cel mai eficient de verificare a pozitivitii unei matrice, acesta fiind reprezentat de relaia dat n parantez n cadrul relaiilor (3.112). Conform cu relaiile de calcul date, se obineAlgoritmul 3.19. (CHOL -Factorizare Cholesky) Se d o matrice A0 n x n simetric. Se determin dac matricea A este pozitiv definit i, n caz afirmativ, se scrie peste triunghiul inferior al lui A matricea L din factorizarea Cholesky A=LLT. 1. Pentru k=1: n 1. 2. Dac # 0 atunci 1. Tiprete A nu este pozitiv definit 2. Stop 3. 4. Pentru i = k+1: n

86

S. erban, M. Tilca

ANALIZ NUMERIC

1.

Algoritmul prezentat necesit NCHOL = n3 /3 flopi i n extrageri de radical i un volum de memorie MCHOL = n2 /2. Trebuie reinut de asemenea c acest algoritm are stabilitate mai bun dect cel de eliminare gaussian cu pivotare complet. Ct privete rezolvarea sistemului algebric liniar Ax=b, la care A este simetric i pozitiv definit, aceasta se face astfel1. Se factorizeaz A=LLT cu algoritmul CHOL 2. Se rezolv sistemul inferior triunghiular Ly=b 3. Se rezolv sistemul superior triunghiular LT x=y

UTM-STI

numrul de operaii fiind de dou ori mai mic dect cel presupus de algoritmul de eliminare gaussian. O.3.4. Dac matricea A este cu numere complecse A 0 n x n, factorizarea Cholesky este A = L LH unde L 0 n x n este inferior triunghiular, cu elementele diagonale reale i pozitive. Corespunztor relaiile de calcul date n cazul real se modific astfel

(3.115)

Sisteme algebrice liniare

87

3.14. Rutine MATLABPractic toate programele prezentate n acest capitol se regsesc i n cadrul mediului de programare MATLAB. Apelarea lor este deosebit de facil atunci cnd se cunoate denumirea rutinei respective. De aceea n continuare se prezint principalele subprograme ntlnite n acest program. V recomandm de asemenea s apelai la funcia help pentru a obine informaii despre aceste subprograme, modul de apelare, date de intrare i de ieire precum i subprogramele cu care se nrudesc. Programul MATLAB dispune de urmtoarele funcii de analiz matriceal:det(A) inv(A) rank(A) trace(A) rref(A) norm(x) cond(A) Calculeaz determinantul matricei (ptrate) A; Calculeaz inversa matricei ptrate (nesingulare) A; Determin rangul matricei (dreptunghiulare) A; Calculeaz urma matrice (ptrate) A; Determin forma de ealon redus pe linii (cu operaii gaussiene) pentru A; Determin norma unui vector x (sau a unei matrice A); Estimeaz numrul de condiionare al matricei A.

UTM-STI

Pentru principalele prelucrri matriceale n MATLAB sunt prezente urmtoarele subprograme:chol(A) lu(A) qr(A) qz(A) eig(A) svd(A) Calculeaz factorizarea Cholesky a matricei A; Calculeaz descompunerea LU (lower -upper) a matricei A; Determin descompunerea ortogonal -triunghiular a matricei A; Calculeaz descompunerea QZ a matricei A; Determin volorile i vectorii proprii ai matricei A; Determin valorile singulare ale unei matrice.

n MATLAB un sistem algebric liniar cu n ecuaii i n necunoscute se exprim matriceal n urmtoarele dou moduri (3.116) unde evident (3.117) i unde x este necunoscuta sub forma unui vector n dimensional (y este o linie cu n coloane), A este matricea coeficienilor i are n linii i n coloane (idem pentru C) i b este termenul liber(membrul drept) sub forma unui vector n dimensional (d este o linie cu n coloane).

88

S. erban, M. Tilca

ANALIZ NUMERIC

Presupunnd (aa cum s-a fcut permanent n acest capitol) c A (C) este nesingular, rezolvarea se poate face astfel: # mprire la stnga: x=A\b; # calculul inversei: x=inv(A)*b; # mprire la dreapta: y=d/C; # calculul inversei: z=d*inv(C).

3.15. Probleme propuseP.P.3.1. Scriei n MATLAB un subprogram de tip function pentru implementarea algoritmului G. Rutina primete din exterior matricea A (notat a), verific dac este ptrat i returneaz matricea U n forma superior triunghiular. Verificai acest program pe matricea (care se v-a fi utilizat pentru toate exemplele ulterioare)

UTM-STI

(3.118)

P.P.3.2. Idem pentru algoritmul GPC. P.P.3.3. Idem pentru CROUT i CROUTP. P.P.3.4. Implementai algoritmii UTRIS i S_GPC n programe scrise n MATLAB. P.P.3.5. Idem pentru algoritmul GPP. P.P.3.6. Determinai relaiile analitice de calcul a inversei matricei nesingulare A care este n forma superior triunghiular la dreapta (la stnga). P.P.3.7. Idem atunci cnd A este sub forma inferior triunghiular la stnga (la dreapta). P.P.3.8. Scriei relaiile analitice pentru rezolvarea sistemului algebric liniar Ax=b, atunci cnd A0nxn este nesingular i superior triunghiular, iar b 0 n. P.P.3.9. Idem, dar pentru A inferior triunghiular la stnga. P.P.3.10. Scriei n MATLAB un program de inversare a unei matrice A (vezi algoritmul UINV) dup ce a fost adus la forma superior triunghiular. P.P.3.11. Scriei un program n MATLAB pentru rezolvarea sistemului algebric liniar Ax=b, cu A nesingular, prin aducerea lui A la forma superior triunghiular; verificai acest program pe datele din (3.118). P.P.3.12. Dai un algoritm de rezolvare a sistemului algebric Ak x = b, k$1 i A nesingular,

Sisteme algebrice liniare

89

-fr a efectua ridicarea la putere a matricei A- prin aducerea lui A la forma superior triunghiular; implementai acest algoritm ntr-un program MATLAB. P.P.3.13. Realizai un algoritm (respectiv un program MATLAB) pentru rezolvarea sistemului algebric general AX=B cu A 0 n x n nesingular i B 0 n x m, prin aducerea lui A (o singur dat!) la forma superior triunghiular la dreapta. P.P.3.14. Idem pentru sistemul XA=B cu A 0 n x n nesingular i B 0 m x n. P.P:3.15. Pentru A, B 0 n x n nesingulare scriei un algoritm eficient de rezolvare a sistemului algebric liniar (AB)k x = b cu b 0 n (nu efectuai ridicarea la putere!). P.P.3.16. Determinai un algoritm i un program MATLAB pentru rezolvarea sistemului algebric liniar Ax=b cu A 0 n x n nesingular i b 0 n, folosind exclusiv matematica real. P.P.3.17. Demonstrai c sistemul algebric liniar complecs Cz = w cu C=A+jB 0 n x n nesingular, z=x+jy 0 n i w=u+jv 0 n este echivalent cu sistemul real (decomplecsificare) (3.119) i scriei un un algoritm i un program MATLAB pentru rezolvarea sistemului complecs folosind aceast idee. P.P.3.18. Scriei un algoritm i un program MATLAB pentru factorizarea LU a unei matrice A 0 n x n nesingulare i validai acest program pe exemplul (3.118). P.P.3.19. Determinai relaiile analitice de calcul a soluiei sistemului algebric liniar Ax=b atunci cnd A 0 n x n este nesingular i factorizat LU. P.P.3.20. Se consider matricele A 0 n x n nesingular, D 0 m x m nesingular, B 0 n x m i C 0 m x n . Dac se noteaz (actualizarea de rang m a matricei A) A+ = A + B D -1 C, demonstrai c: a) Are loc egalitatea (formula Sherman-Morrison-Woodbury) (3.120) b) Pentru matricea H definit mai jos, inversa este cea menionat

UTM-STI

(3.121)

nesingular P.P.3.21. Pentru A 0 n x m i B 0 m x n , plecnd de la identitatea A+ABA = A+ABA,

90

S. erban, M. Tilca

ANALIZ NUMERIC

demonstrai c det(In + AB) = det(Im + BA). Folosii acest rezultat pentru a determina determinantul matricei A = In + u vT unde u, v 0 n.

UTM-STI

4.

PROBLEMA CELOR MAI MICI PTRATE (CMMP)

UTM-STI4.1. Introduceren acest capitol se trateaz cazul general al rezolvrii sistemului algebric liniar n necunoscuta x (4.1) unde (cazul interesant aici) mn adic numrul de ecuaii este diferit de cel al necunoscutelor. n funcie de relaia dintre m i n apar urmtoarele situaii: Dac m>n (sistem supradeterminat) soluionarea sistemului (4.1) presupune & & determinarea unei soluii aproximative & 0 n care face ca reziduul r = b - A x x & s fie ct mai mic; altfel spus, x trebuie s minimizeze funcia (4.2) (@) este o norm adecvat peste m . Dimpotriv, n situaia m 1 atunci 1. = 2 x 2 2. 0 atunci 1. Dac x 1 0 atunci 7 sgn (x 1 ) 2. 3. 7 u 1 = 1 + x 1 4. x 1 7 -

4.2.2. Rotaii Se pleac de la clasica rotaie n plan (n 2) ce se descrie prin (4.22) i care, pentru m $ 2, se generalizeaz prin

Problema celor mai mici ptrate D.4.2. Dac se fixeaz ntregii ik 0 1: m, matricea P ki 0 m x m dat de

97

(4.23)

se numete o rotaie de ordinul m n planul (k, i), sau nc transformarea Givens. Transformarea menionat este o matrice ortogonal. Folosirea rotaiilor este dedicat introducerii de zerouri la nivelul unui vector i, prin utilizare repetat, la nivelul coloanelor unei matrice. Pentru aceasta fie T.4.2. Dac se fixeaz ntregii ik 0 1: m i se consider vectorul x 0 m sub restriciaFig.4.2. Efectul unei rotaii asupra unui vector (aici n 2 ).

UTM-STI(4.24)

definete o rotaie Pki de structura (4.23) care asigur (4.25) adic anuleaz componenta xi . Demonstraie. Rezult imediat c (4.26) Semnificaia geometric a unei rotaii, n cazul m=2, este dat n figura 4.2. Se obine atunciAlgoritmul 4.4. Se consider numerele ik 0 1: m i vectorul x 0 m pentru care se

98

S. erban, M. Tilca

ANALIZ NUMERIC

determin o rotaie Pki care asigur forma din (4.25). 1.

2. 3. xk = r; xi = 0; % vectorul transformat

Ct privete implementarea numeric a algoritmului dat anterior se fac urmtoarele observaii: G Este de preferat ca, de la nceput, s se fac o scalare a vectorului x, de exemplu, prin M = * xk * + * xi *; G Dac M = 0 (sau, echivalent, r = 0) se pune Pki = Im prin alegerea c=1 i s=0; G Semnul lui r se alege acelai cu al componentei maximale (n modul) dintre xk i xi . Acceptarea ultimei observaii date anterior, conduce la posibilitatea refacerii numeric stabile a parametrilor c i s pe baza unui singur numr z. Este de asemenea evident c o rotaie produce un singur zerou la nivelul vectorului x; realizarea unui efect similar cu al reflectorului Hauseholder se face prin aplicarea succesiv de rotaii, ntreaga transformare fiind (4.27) Cum rotaiile sunt transformri plane, se poate raiona pe cazul bidimensional, caz n care notm transformarea prin P12 . Cu precizrile date avem, ca form finalAlgoritmul 4.5. (ROTG- Rotaie general) Se determin i se aplic transformarea de tip rotaie care efectueaz operaia (4.26). Se obine i numrul z (memorat pe poziia x2 a vectorului care a devenit nul) pe baza cruia se pot reface numeric stabil parametrii de rotaie c i s. 1. r = 2 x 2 2. Dac r = 0 atunci 1. c = 1, s = 0; altfel 2. Dac * x2 * $ * x1 * atunci 1. r 7 sgn( x2 ) r altfel 2. r 7 sgn (x 1 ) r 3. 4. x 1 = r

UTM-STI

Problema celor mai mici ptrate% calculul lui z 5. Dac c = 0 atunci 1. z = 1 altfel dac * x2 * $ * x1 * atunci 2. altfel 3. z = s 6. x 2 = z % reconstrucia perechii (c, s) 7. Dac z = 1 atunci 1. c = 0, s = 1 altfel dac * z * > 1 atunci 2. altfel 3.

99

UTM-STI

4.3. Transformri unitaren cazul matricelor cu elemente complecse transformrile recomandate pentru obinerea unor anume structurri sunt cele unitare. Vom prezenta pe scurt i acest caz, absolut similar celui real, cu observaia c, de fiecare dat, n locul transpunerii va apare operaia de transpunere i conjugare complecs. 4.3.1. Reflectori compleci Matricea Q 0 m x m se numete unitar dac Q H Q = Im . De asemenea se reamintete c, pentru cazul complecs, produsul scalar i norma euclidian sunt cele definite mai jos (4.28) Fie u 0 m un vector Householder, u 0. Se consider matricele complecse (4.29) pentru care

100

S. erban, M. Tilca

ANALIZ NUMERIC (4.30)

i deci transformarea este unitar dac i numai dac (4.31) Pe de alt parte, Q1 este hermitic dac i numai dac 0 ; ca urmare, pe fondul acestor dou cerine, se opteaz pentru: dac = 0 avem Q1 = Im , iar pentru cazul contrar

caz n care se obin reflectori hermitici ce reprezint generalizarea noiunii de reflectori (reali). n continuare se determin reflectorul Q1 astfel nct (4.33) condiia de norm fiind datorat faptului c matricea Q1 este unitar. Pe considerente numerice, se poate face alegerea (4.34) Similar cazului real se scrie (4.35) i pentru ndeplinirea relaiei (4.33) avem (4.36) n plus (se ine cont i de relaia (4.33-2)) (4.37) rmnnd s se determine numai factorul de scalare . Aceast alegere se poate face: i = 1 i dedus din (4.34-1) sau (4.34-2) conduc la un algoritm similar celui din cazul real;

UTM-STI

(4.32)

Problema celor mai mici ptrate i opiunea = face ca

101

(4.38)

i

n sfrit cu = x1 + avem

UTM-STIAlgoritmul rezultat este2.

(4.39)

Algoritmul 4.6. (CRFG- Reflector general n cazul complecs) Se determin i se aplic transformarea de tip reflector Q1 ce implementeaz relaia (4.33-1). 1. = 0 2. Dac m > 1 atunci 1. = 2 x 2 2. Dac 0 atunci 1. Dac Re ( x1 ) 0 atunci 7 sgn ( Re x1 )

3. 4. x 1 7 -

4.3.2. Rotaii complecse Conform cu cele prezentate n cazul real, este suficient s considerm spaiul bidimensional, aici 2. O rotaie complecs este o matrice de forma (4.40) care este unitar pentru c PH P = I2 . Efectul acestei transformri este

102

S. erban, M. Tilca

ANALIZ NUMERIC

(4.41) i se pot face urmtoarele opiuni: (4.42)

Algoritmul de calcul este n acest caz

UTM-STI

(4.43)

Algoritmul 4.7. (CROTG- Rotaie general n cazul complecs) Se determin i se aplic transformarea de tip rotaie asociat cazului complecs care efectueaz operaia (4.41). 1. Dac * x1 * = 0 atunci 1. c = 0, s = 1 2. x1 7 r = x2 , x 2 = 0 altfel 3.

4. 5. x 1 7 , x2 = 0

4.4. Realizarea formei triunghiulare folosind transformri ortogonaleSe consider n continuare cazul matricelor complecse A 0 m x n care, prin transformri unitare aplicate la stnga, se vor aduce la forma superior triunghiular (la dreapta); se vor face permanent precizri privind particularitile ce apar n cazul matricelor reale A 0 m x n , pentru care transformrile aplicate sunt cele ortogonale. n acest sens fie T.4.3. Pentru orice matrice A 0 m x n exist matricea unitar U QH 0 m x n care pentru pentru R din relaia (4.44) i asigur forma superior triunghiular; pentru cazul A 0 m x n

transformarea

Problema celor mai mici ptrate

103

implicat este U = QT este real i ortogonal. Ca urmare orice matrice A se poate scrie sub forma A = Q R unde Q este unitar (ortogonal), iar R este superior triunghiular (factorizarea QR). Demonstraie. Se procedeaz pur i simplu constructiv, folosind reflectori sau rotaii. n cele ce urmeaz se face apel la cazul real; pentru cazul complecs raionamentele sunt absolut identice. Etapa 1. Dac elementele primei coloane din A nu sunt toate nule (n caz contrar, se ia U1 = Im i algoritmul debuteaz de la coloana urmtoare) se aplic reflectorul Hauseholder care anuleaz toate elementele acestei coloane, mai puin primul element; rezult (A1 A)

UTM-STI

(4.45)

Etapa k, k = 2: n. Dup primii (k-1) pai s-a obinut matricea

(4.46)

Dac toate elementele din coloana k, de la linia k n jos, sunt nule se pune Uk matricea unitate i se trece n coloana urmtoare; n caz contrar, se determin reflectorul care produce anularea tuturor elementelor acestei coloane de la linia (k+1) n jos. Se continu n acelai mod pn la coloana n; dac m > n, dup n pai rezultatul este

104

S. erban, M. Tilca

ANALIZ NUMERIC

(4.47) cu R1 0 n x n superior triunghiular. n cazul m # n, dup m - 1 pai, se obine matricea superior trapezoidal, care se partiioneaz ca mai jos (4.48) n care R1 0 m x m este superior triunghiular. Se obine

Algoritmul 4.8. (QR- Triangularizare ortogonal pentru cazul real) Se determin transformarea, respectiv factorii Q i R. 1. Pentru k = 1: min (m-1, n) % Se determin transformarea Uk 1. 2. u kk = a kk + ; u i k = a i k , pentru i = k+1: m 3. k = u k k % Se aplic transformarea U k 4. Pentru j = k+1: n 1. 2. a i j 7 a i j - u i k % Coloana k 5. a kk = - ; a i k = 0, pentru i = k+1: m

UTM-STI

4.5. Factorizarea QRCele prezentate anterior permit realizarea unei factorizri de tip QR pentru orice matrice A 0 m x n. Astfel, dac m $ n, se obine T.4.4. Pentru orice matrice de tipul anterior exist o descompunere de forma (4.49) n care Q1 are coloane ortogonale (Q1H Q1 = In ), iar R1 este superior triunghiular. Scrierea (4.49) se numete factorizarea QR a matricei A. Matricea R1 este nesingular dac i numai dac A este monic. n acest ultim caz factorizarea este i

Problema celor mai mici ptrate

105

unic dac, n plus, se impune condiia ca R1 s aib elementele diagonale reale i pozitive. Demonstraie. Conform cu cele prezentate anterior, este adevrat relaia (4.50) i, partiionnd pe Q conform cu dimensiunile de structurare ale lui R avem

ceea ce justific imediat forma (4.49). Pentru partea a doua a teoremei, plecm de la faptul c a este monic dac i numai dac oricare x 0 n, x 0 avem Ax 0 adic dac i numai dac xH AH A x = 2 A x 2 > 0 oricare x 0 n, x 0. Ca urmare matricea hermit