1

Subiectul I.

1. Rotunjirea uniforma:

rotunjirea uniform (metoda cifrei pare)

n acest caz, fl(x) are urmtoarea expresie:

parafcifraultima,2

,0|g|,f

imparafcifraultima,2

,0|g|,f

2,0|g|,f

2,0|g|,f

)x(fl

e

tee

tee

e

.

n aceast expresie de definiie, semnul + se consider pentru 0f i semnul - se consider pentru

0f .Este cea implementata in prezent.

2. Triangularizarea directe-principiu+cand esueaza

Acest algoritm parcurge )1n( etape, la fiecare etap zerorizndu-se elementele de sub diagonala

principal i pstrnd nealterate transformrile care s-au efectuat n coloanele anterioare ale matricei A.

Principiu:

Matricele ]a[ 11 , , 1nj11ni1ij ]a[ se numesc submatrice principale ale lui A sau minori principali

directori.

Teorem:

Dac matricea nnA are toate submatricele principale inversabile (nesingulare), atunci exist

matricele nnU,D,L astfel nct:

UDLA (Error! No text of specified style in document..1)

unde L este o matrice inferior triunghiular, D este o matrice diagonal i U este o matrice superior

triunghiular..

La triangularizarea simpl, unde elementele matricei A se modific corespunztor relaiei:

n,...,kj;n,...,1ki,aaa ]k[kjik]k[

ij]1k[

ij

,

multiplicatorii ik pot avea, n principiu, orice valoare. Dac aceste valori sunt mari sau foarte mari,

atunci pot apare fenomenele de omitere catastrofal i/sau de neutralizare a termenilor. Mai mult, dac

aceti multiplicatori au valori supraunitare n modul, atunci ei amplific erorile prezente n termenii ]k[kja ,

n felul acesta triangularizarea simpl fiind instabil numeric, n general. Altfel spus, nu exist nici un

control asupra stabilitii numerice a algoritmului triangularizrii simple.

2

3. De ce se alege norma euclidiana pt functia de minimizat Deoarece norma euclidiana este singura care satisface cele doua conditii de diferentiabilitate.

Norma euclidiana:

m

1i

2i

T22

22 r

2

1rr

2

1||r||

2

1||xAb||

2

1)x(V .

Impunand cele 2 conditii de minimizat pt:

n

*

x 0)}x(V{ rezulta bAxAATT (sistem determinant de n ecuatii cu n necunoscute si se

numeste sistem de ecuatii normale atasat sistemului supradeterminat)

0)}x(V{*

x rezulta AAT (pozitiv-definita)

Se prefera urmatorul mod de lucru:

Se transforma sistemul 1n1mnm x,b,A,bxA . Cu ajutorul unor matrici ortogonale

(pentru ca pastreaza norma euclidiana) a.i. sistemul transformat obtinut sa aiba matricea in forma

superior triunghiulara.In acest caz pseudosolutia in sensul celor mai mici patrate va fi data de solutia

sistemului supradeterminat obtinut din primele n ecuatii ale sistemului transformat(acesta solutie se

determina prin substitutie inversa)

4. Principiul algoritmului QR

Algoritmul QR pentru calculul valorilor i vectorilor proprii construiete un ir de matrice

ortogonal asemenea ,...A,...,A,AA k10 convergent ctre forma canonic Schur:

SAk

k

.

irul de matrice AA,}A{ 00kk , definit prin relaiile Error! Reference source not found.

nkkkk

kknkk

IQRA

RQIA

1

, se numete ir QR ataat matricei A, iar relaiile se numesc pas QR cu deplasare explicit.

Algoritmul original QR, descris de relaii, este n general consumator de timp. De aceea se folosete o

form optimizat a algoritmului QR cu deplasare explicit, pentru calculul valorilor i vectorilor proprii.

Algoritmul optimizat cuprinde dou faze:

Faza I-a este o etap pregtitoare, de obinere a formei superior Hessenberg a matricei A, printr-un

ir de transformri ortogonale de asemnare. Se noteaz cu H forma superior Hessenberg a matricei A.

Matricele A i H sunt ortogonal asemenea

Aadar, matricea H are elementele n,...,2ji,2n,...,1j,0h ij . Faza I-a implic o procedur

direct ce se desfoar n 2n iteraii.

Faza a II-a implic o procedur iterativ cu un numr finit, dar necunoscut de pai. Plecnd de la

forma superior Hessenberg a matricei A, se construiete un ir de matrice ortogonal asemenea, convergent

ctre forma canonic Schur S. Astfel, se urmrete zerorizarea unor elemente aflate pe sub-diagonala

principal a matricei H atfel nct, n final, s se obin forma canonic Schur.

Aplicnd n aceast faz algoritmul QR cu deplasare explicit, plecnd de la matricea superior

Hessenberg, se poate demonstra c se obine un ir de matrice aflate tot n forma superior Hessenberg.

Altfel spus, forma superior Hessenberg este invariant la algoritmul QR.

Observaie:

3

Dac se aplic direct algoritmul QR asupra matricei iniiale A, atunci fiecare iteraie necesit un numr

de operaii n virgul mobil de ordinul lui 3n . Dac, ns, algoritmul QR se aplic formei superior

Hessenberg, atunci la fiecare pas QR numrul de operaii n virgul mobil este de ordinul lui 2n .

5. Baza ortogonala a subspatiului nul al lui A

ultimele rn coloane ale matricei V~

formeaz o baz ortogonal pentru subspaiul nul al matricei A:

}x,0xA/x{)A(N 1nm ,

]U~

U~

[]V~

V~

[AU~

V~

A 2121 .

)rn(m2111 V~

A,U~

V~

A 0

Din relaiile scrise mai sus i formele pe care le poate lua matricea , rezult c ultimele rn

coloane ale matricei V~

pot constitui o baz pentru )A(N . Subspaiul nul astfel determinat conine

doar vectorul n0 numai dac matricea A este de rang complet i nm .

6. Metoda Bairstow-descriere pe scurt

Principiul este de a pune n eviden divizori de grad nti sau doi ai polinomului )x(Pn . Divizorii

sunt separai succesiv, n urma unui proces iterativ.

Una din metodele cele mai rspndite este algoritmul Bairstow care const n separarea divizorilor de

grad doi. Dac gradul n al polinomului este impar, atunci ultimul divizor separat este un polinom de grad

nti. Prin gsirea rdcinilor divizorilor separai se obin soluiile ecuaiei polinomiale iniiale.

Ideea esenial care st la baza acestei metode este aplicarea metodei Newton pentru rezolvarea

sistemelor de ecuaii neliniare de ordinul doi care rezult din condiia ca restul mpririi unui polinom

de grad oarecare la un polinom de grad doi s fie zero.

n concluzie, aplicarea metodei implic parcurgerea unui algoritm care trebuie s combine rezolvarea

sistemului de ecuaii neliniare de ordinul doi (Error! No text of specified style in document..5) n

necunoscutele p i q, pe de o parte, cu determinarea coeficienilor polinomului ct, )x(Q 2n , pe de alt

parte.

Caracteristica acestei metode este faptul c ea favorizeaz acumularea i propagarea erorilor de

rotunjire. Astfel, odat ce este separat un divizor, procedeul se continu asupra polinomului ct, )x(Q 2n ,

i aa mai departe. Drept urmare, coeficienii ultimilor divizori pot fi afectai de erori de rotunjire ntr-o

msur inacceptabil.

7. Ce semnificatie are cuadratura si regula simpla+compusa

Pentru aproximarea numeric a integralei definite se folosete termenul de cuadratur numeric,

realiznd astfel o distincie fa de estimarea numeric a soluiilor ecuaiilor difereniale numit integrare

numeric (a ecuaiilor difereniale).

Spre deosebire de operaia de derivare numeric, cuadratura tinde s netezeasc sau s diminueze

erorile ce afecteaz datele.

Se numete regul (elementar) de cuadratur, o formul simpl care aproximeaz valorile

integralelor elementare )f(Ii .

4

Se numete regul compus de cuadratur, o formul care aproximeaz valoarea integralei definite

)f(I , ca o sum a regulilor (elementare) de cuadratur.

8. Principiul integrarii ecuatiilor diferentiale de ordin 1.

Se consider ecuaia diferenial de ordinul nti de forma:

)t(y,t(fdt

)t(dy ,(Error! No text of specified style in document..2)

Iy],b,a[t),t(yy 0000 (Error! No text of specified style in document..3)

unde 0y reprezint condiia iniial cunoscut sau precizat. Fr a restrnge generalitatea, se poate

considera at0 .

Problema de calcul este determinarea soluiei (aproximative), y(t), a ecuaiei difereniale (Error! No

text of specified style in document..2), cu condiia iniial (Error! No text of specified style in document..3), pentru orice valoare a argumentului ]b,a[t . Problema astfel definit se numete

problema Cauchy. Pentru rezolvarea acesteia, se enun urmtorul rezultat.

Teorem:

Fie ecuaia (Error! No text of specified style in document..2) i condiia iniial (Error! No text of

specified style in document..3). Dac sunt ndeplinite condiiile:

(i) funcia f este continu n raport cu argumentul ]b,a[t ;

(ii) funcia f este lipschitzian n raport cu argumentul Iy , anume 0L astfel nct este

ndeplinit relaia:

|yy|L|)y,t(f)y,t(f|,Iy,y],b,a[t 212121 ,

atunci exist i este unic o soluie a problemei Cauchy.

Subiectul II.

1. Multimea nr in virgula mobile:

O mulime de numere n virgul mobil este definit prin urmtorii parametri: (a) - baza mainii de calcul;

(b) t - numrul de cifre n baza utilizate pentru a reprezenta partea fracionar (precizia mainii de

calcul);

(c) L - cel mai mic exponent (limita de depire inferioar);

(d) U - cel mai mare exponent (limita de depire superioar).

Exponentul e este cuprins ntre valorile: UeL .

Definiie:

Mulimea F de numere n virgul mobil este:

5

}0{}fx/x{F e , unde:

UeL

t,,1i,1d0,ddd

f itt

i

i1

unde f este mantisa (fracia), e este exponentul, este baza mainii, t este numrul de cifre n baza i

id sunt cifrele bazei.

2. Principiul metodei iterative la sist. de ec. alg. liniare

Fie sistemul de ecuaii algebrice liniare:

1nnn b,A,bxA ,(Error! No text of specified style in

document..4)

n care A este o matrice nesingular.

Metodele iterative se bazeaz pe construcia unui ir de aproximaii ale soluiei, ,...1,0k,x]k[

,

convergent la soluia adevrat:

]0[]k[

kx,xxlim

.

Pentru construcia acestui ir, se consider rescrierea sau descompunerea matricei A a sistemului sub

forma: PNA , n care N este o matrice nesingular. De regul, se alege matricea N cu o form

simpl. Ecuaia (Error! No text of specified style in document..4) devine:

bxPxNbx)PN( .(Error! No text of specified style in

document..5)

irul de aproximaii se construiete cu ajutorul relaiei:

,...1,0k,bxPxN]k[]1k[

(Error! No text of specified style in

document..6)

n care estimaia iniial ]0[

x este dat (cunoscut). n particular, n]0[

0x .

Din relaia (Error! No text of specified style in document..6) rezult:

,...1,0k,bNxPNx 1]k[1]1k[

3. Ce transformari se aplica la mat A din alg QR

Pentru determinarea reflectorilor kU la fiecare iteraie k, se va considera drept vector , coloana

numrul k a matricei kA transformate. Astfel, se vor zeroriza, coloan cu coloan, elementele de sub

pseudo-diagonala principal a matricei A. n urma calculului matricei 1kA , primele 1k coloane din

matricea kA se pstreaz, iar coloanele de la 1k la n se modific n liniile de la k la m.

6

Algoritmul eueaz dac matricea A este deficient de rang. n acest caz, la calculul reflectorului kU ,

mrimea k ar fi nul, ceea ce va conduce la 0k n aritmetica real ( impusk || n virgul mobil).

Ca o consecin a acestui fapt, elementul k,kr de pe diagonala principal a matricei 1R va rezulta nul,

dac algoritmul eueaz la iteraia k. Pentru continuarea procesului de triangularizare (condiia de

executarea a unei iteraii), testul uzual care ine cont de erorile n virgul mobil este: impusk || .

n urma aplicrii acestui algoritm se obine:

RAUUU 11nn .

4. Algoritmul SVD

Algoritmul SVD (SVD este abrevierea consacrat din limba englez de la Singular Value

Decomposition; n traducere: descompunerea valorilor singulare) const n construirea unui ir de

matrice ortogonal echivalente bilateral, ir convergent ctre forma canonic pseudo-diagonal a unei

matrice.

Principiul de calcul este de a aplica mascat, anume direct asupra matricei A, algoritmul QR pentru

obinerea formei canonice Schur a matricei AAB T . Altfel spus, se aplic matricei iniiale A,

transformrile corespunztoare celor care s-ar aplica matricei B n cadrul algoritmului QR de aducere la

forma canonic Schur. Masca este dat de corespondena:

nnTT B,BB,AABA .

5. Conditia suficienta de convergenta la sisteme de ecuatii algebrice neliniare

Spunem ca este convergenta pe o vecinatate V2 daca exista 2 vectori Vy,x , un scalar x

7

Pentru funcia f cunoscut prin intermediul unui ir de valori corespunztor unei divizri a

intervalului de definiie al funciei, [a,b], se dorete determinarea unui polinom de grad mai mic sau egal

cu n: n

n10n xcxcc)x(P ,

astfel nct:

n,,0i),x(f)x(P iin .

3. Cand pseudosolutia in sensul CMMP are solutie unica ?

Pentru orice matrice nm,A nm , urmtoarele afirmaii sunt echivalente:

i.) A este o matrice monic; ii.) n)A(rang ;

iii.) }0{)A(N n ;

iv.) matricea AAT este pozitiv definit, deci inversabil (nesingular).

Concluzia care se desprinde este aceea c problema (Error! No text of specified style in document..2) va

avea o soluie unic dac vectorul m0b aparine subspaiului imagine al matricei A, )AIm(b , sau,

altfel spus, vectorul b este o combinaie liniar a coloanelor matricei A, acesta n ipoteza c n)A(rang .

Este posibil, ns, ca vectorul b s fie (uor) perturbat, deci s nu mai aparin subspaiului imagine al

matricei A. i n astfel de cazuri se dorete determinarea unei soluii pentru problema de calcul (Error! No

text of specified style in document..2).

4. Integrare (sau ceva de genu) a ec dif si conditii initiale

Fie ecuaia )t(y,t(fdt

)t(dy , i condiia iniial Iy],b,a[t),t(yy 0000 . Dac sunt

ndeplinite condiiile:

(i) funcia f este continu n raport cu argumentul ]b,a[t ;

(ii) funcia f este lipschitzian n raport cu argumentul Iy , anume 0L astfel nct este

ndeplinit relaia:

|yy|L|)y,t(f)y,t(f|,Iy,y],b,a[t 212121 ,

atunci exist i este unic o soluie a problemei Cauchy.

Se spune c se realizeaz integrarea numeric a ecuaiei )t(y,t(fdt

)t(dy , cu condiia iniial

Iy],b,a[t),t(yy 0000 prin aplicarea unei metode de integrare numeric.

Valorile 1N,...,1,0i,tt:h i1ii se numesc pai de integrare. Intervalul ]t,t[ N0 se numete

interval de observare. Lungimea intervalelor corespunztoare valorilor calculate care, mai departe, sunt

folosite drept valori extrase din soluia numeric, se numesc pai de observare.

Subiectul III.

8

1. Fenomene de eroare de la adunare/scadere

(a) omiterea catastrofal: apare atunci cnd se adun doi termeni i valoarea absolut a unui termen

este mai mic dect precizia de reprezentare a celuilalt termen; n acest caz, rezultatul este dat de

termenul cu valoare absolut mai mare

(b) neutralizarea termenilor: apare atunci cnd se adun numere cu semne diferite i cu valori

absolute apropiate; n acest caz, n mod eronat, rezultatul este nul

2. Problema matlab, cu plot-ul unei functii

;FunctieMN.m

function y=FunctieMN(x)

y=x*3;(sau tot carnatul ala)

end;

;program.m

X=5:1:5;(saucateintervalul)

y=FunctieMN(x);

plot(x,y,'-b');

end;

3. Problema matlab, ceva cu svd si rank

4. Tipul de matrice necesara pentru metoda cu cele mai mici patrate (din cap3)

Pentru orice matrice nm,A nm , urmtoarele afirmaii sunt echivalente:

v.) A este o matrice monic; vi.) n)A(rang ;

vii.) }0{)A(N n ;

viii.) matricea AAT este pozitiv definit, deci inversabil (nesingular).

pseudosoluia *

x este unic determinat dac matricea acestui sistem, AAT , este inversabil.

Aceast condiie este ndeplinit dac matricea AAT este pozitiv definit.

n practic, ns, nu se recomand rezolvarea sistemului de ecuaii normale Error! Reference source not

found. deoarece matricea AAT , dei teoretic este pozitiv definit, prin calcul, datorit erorilor de

rotunjire, ea poate deveni pozitiv semidefinit, deci neinversabil. Astfel, n general, matricea AAT

este prost condiionat deoarece calculul su este afectat de erori de rotunjire deseori cu caracter

catastrofal.

5. Metodele indirecte de la cap2

Metodele iterative au la baz construirea unui ir de aproximaii pentru soluia sistemului,

,1,0k,x ]k[ care s fie convergent pentru k la soluia adevrat, x :

9

0||xx||lim]k[

k

.

Practic, calculele se opresc la un index de iterare [s], atunci cnd este ndeplinit o condiie de

forma:

impus

]1s[]s[||xx||

,

sau, altfel spus, ]s[

x constituie o aproximare satisfctoare a soluiei calculate.

Avnd n vedere faptul c pentru o singur iteraie numrul de operaii n virgul mobil este de

ordinul lui 2n , asemenea metode se folosesc pentru sisteme de ordin mare i anume 42 1010 .

6. Pasul QR cu deplasare explicita

irul de matrice AA,}A{ 00kk , definit prin relaiile

nkkk1kkknkk IQRA,RQIA , se numete ir QR ataat matricei A, iar relaiile

Error! Reference source not found. se numesc pas QR cu deplasare explicit.

7. Ce sunt valorile singular

Numerele p1 ,, ( ( V

~AU

~ T sau TV~

U~

A ), i

0},,,{diag p21p1 ) se numesc valori singulare ale matricei A.

8. Problema matlab, de implementat metoda secantei pt o functie

citete 21 x,x

atribuie 10 xx

atribuie 21 xx

atribuie )}xx/()]x(f)x(f/{[)x(fxx 0101112

scrie soluia = , 2x

5. Cuadratura numerica cu metoda simpson

Principiul este de a aproxima fct f pe (xi,xi+1) printr-un polinom de grad 2 constrans sa treaca prin

punctele { xi+1,f(xi+1)}

10

)}x(f,x{},2

xxf,

2

xx{)},x(f,x{ 1i1i

1ii1iiii

.

)(2

4)(6

1)( 1

1i

iiiii xf

xxfxfhfS

1. Dac numrul de intervale, egal cu n, este par, atunci se obine:

S(f) ).42424(3

123210 nnnn fffffffh

- se numete regula 1/3

Simpson.

2. Dac numrul de intervale n este impar, atunci folosind un polinom de interpolare de gradul trei se

obine:

).33233233(8

3)( 123543210 nnnn ffffffffff

hfS

Aceast formul se numete regula 3/8 Simpson

6. Integrarea cu metoda taylor de ordin 2 Principiul acestei metode este ca pentru fiecare punct de integrare ii1i1i htt,1N,...,1,0i,t , s se

opreasc primii 1p termeni din dezvoltarea n serie Taylor a funciei y(t) n jurul punctului it .

.y)t(y;1N,...,1,0i

),y,t(f!p

h)y,t(f

!2

h)y,t(fhyy

00

ii)1p(

pi

ii)1(

2i

iiii1i

reprezint formula de integrare Taylor de ordinul p, pentru rezolvarea acuaiilor difereniale ordinare

de ordinul nti.

Subiectul IV

1. Ce se intelege prin calcul in virgula mobila. Prin aritmetica virgulei mobile se neleg urmtoarele:

(a) un model matematic de reprezentare a numerelor (definirea mulimii F);

(b) o modalitate de reprezentare a numerelor din mulimea G n calculatorul numeric, altfel spus o

modalitate de implementare n calculator a modelului (definirea operatorului de rotunjire, notat cu

fl);

(c) operaiile elementare: adunarea, scderea, nmulirea i mprirea definite cu numerele mulimii F.

Corespunztor ultimei forme scrise, se denumesc i se noteaz urmtoarele elemente:

mantis (fracie), notat cu f, reprezentnd numrul fracionar;

exponent, notat cu e, reprezentnd exponentul la care este ridicat baza de numeraie folosit;

11

baza de numeraie, notat cu , n cazul de fa egal cu 10;

numrul cifrelor mantisei, notat cu litera t. Rezult, aadar, c poziia virgulei poate fi modificat, cu adaptarea corespunztoare a exponentului.

2. Reprezentarea grafica a unei ecuatii in Matlab ATRIBUIE u zeros(m,n) ATRIBUIE beta zeros(n,1) _ PENTRU k = 1,n EXECUT | ATRIBUIE sum sqrt( (a(k:m,k))'*a(k:m,k) ) | _ DAC ( a(k,k) >= 0 ) ATUNCI | | ATRIBUIE semn 1 | |ALTFEL

| |_ ATRIBUIE semn -1 | ATRIBUIE sigma semn*sum | ATRIBUIE u(k,k) a(k,k) + sigma | ATRIBUIE u(k+1:m,k) a(k+1:m,k) | ATRIBUIE beta(k) sigma*u(k,k) | _ DAC ( abs(beta(k)) < EPS ) ATUNCI | |_ SCRIE 'algoritmul va esua: beta < EPS'

| ATRIBUIE a(k,k) - sigma | ATRIBUIE a(k+1:m,k) zeros(m-k,1) | _ PENTRU j = k+1,n EXECUT | | ATRIBUIE sum u(k:m,k)'*a(k:m,j) | | ATRIBUIE tau sum/beta(k) | |_ ATRIBUIE a(k:m,j) a(k:m,j) - tau*u(k:m,k) | SCRIE 'k = ',k

|_ SCRIE 'a = ',a

. 3. Triangularizarea simpla a unei matrici patratice.

Dac matricea nnA are toate submatricele principale inversabile (nesingulare), atunci exist

matricele nnU,D,L astfel nct:

UDLA (Error! No text of specified style in document..7)

unde L este o matrice inferior triunghiular, D este o matrice diagonal i U este o matrice superior

triunghiular.

Se pot face, n cele ce urmeaz, urmtoarele observaii:

1.1 relaia (Error! No text of specified style in document..1) se numete factorizare L-D-U a matricei

A;

1.2 uzuale sunt factorizrile: ULA ;

1.3 demonstraia teoremei enunate este constructiv, constituind nsui algoritmul de descompunere L-U

a matricei A;

1.4 algoritmul de descompunere este n fond procedeul de eliminare gaussian, prin care matricea A este

adus la forma superior triunghiular n urma unui ir de transformri de asemnare. Transformrile

efectuate asupra matricei A se acumuleaz ntr-o matrice inferior triunghiular, cu elementele de pe

diagonala principal egale cu 1. Acest tip de descompunere se numete descompunere Doolittle.

12

1.5 considernd descompunerea L-U a matricei sistemului A, ULA , atunci rezolvarea sistemului

implic dou subetape:

1.6 rezolvarea sistemului byL , etap numit i substituie nainte, obinnd soluia intermediar

y . Determinarea componentelor vectorului ni1i ]y[y are loc din aproape n aproape: se ncepe

cu 1y (prima ecuaie), se nlocuiete n a doua ecuaie determinnd pe 2y i aa mai departe.

1.7 rezolvarea sistemului yxU , n care necunoscuta este x , etap numit i substituie invers.

n acest caz, determinarea componentelor vectorului x are loc pornind de la ultima ecuaie.

Aceast manier de descompunere i de rezolvare se ncadreaz n aa-numita rezolvare a sistemelor

determinate de ecuaii algebrice liniare prin triangularizare simpl (direct).

4. Faza II al algoritmului QR.

Faza a II-a implic o procedur iterativ cu un numr finit, dar necunoscut de pai. Plecnd de la forma superior Hessenberg a matricei A, se construiete un ir de matrice ortogonal asemenea, convergent ctre forma canonic Schur S. Astfel, se urmrete zerorizarea unor elemente aflate pe sub-diagonala principal a matricei H atfel nct, n final, s se obin forma canonic Schur.

5. Compresie de date. (SVD - proprietatea P3) P3. descompunerea valorilor singulare are urmtoarea interpretare geometric: valorile

singulare ale unei matrice A sunt exact semiaxele unui hiperelipsoid definit de:

}1||x||,xA{E 2 .

6. Cum se calculeaza un sistem supradeterminat al unei ecuatii liniare. Se consider sistemul supradeterminat de ecuaii algebrice liniare

1n1mnm x,b,A,bxA , unde matricea sistemului este de rang complet pe coloane: nmA , n)A(rang , nm . Se multiplic la stnga ecuaia cu secvena de reflectori Householder

care realizeaz triangularizarea ortogonal a matricei sistemului i acumulate n matricea U. Se obine:

bUxAU .

7. Sa se schiteze un algoritm pentru rezolvarea unei ecuatii. (era o

egalitate intre 2 ecuatii) 8. Metoda Frubenius. 9. Sa se schiteze un algoritm pentru metoda trapezului ... (pauza!) 10. Metoda Taylor.

Principiul acestei metode este ca pentru fiecare punct de integrare ii1i1i htt,1N,...,1,0i,t , s se

opreasc primii 1p termeni din dezvoltarea n serie Taylor a funciei y(t) n jurul punctului it .

.y)t(y;1N,...,1,0i

),y,t(f!p

h)y,t(f

!2

h)y,t(fhyy

00

ii)1p(

pi

ii)1(

2i

iiii1i

reprezint formula de integrare Taylor de ordinul p, pentru rezolvarea acuaiilor difereniale ordinare

de ordinul nti.

13

Subiectul V

1. Ce erori apar la adunarea/scaderea numerelor in virgula mobila.

a. omiterea catastrofal: apare atunci cnd se adun doi termeni i valoarea absolut a unui

termen este mai mic dect precizia de reprezentare a celuilalt termen; n acest caz,

rezultatul este dat de termenul cu valoare absolut mai mare

b. neutralizarea termenilor: apare atunci cnd se adun numere cu semne diferite i cu

valori absolute apropiate; n acest caz, n mod eronat, rezultatul este nul

2. functie simpluta, de facut plot

;FunctieMN.m

function y=FunctieMN(x)

y=x*3;(sau tot carnatul ala)

end;

;program.m

X=5:1:5;(saucateintervalul)

y=FunctieMN(x);

plot(x,y,'-b');

end;

3. Pasul QR irul de matrice AA,}A{ 00kk , definit prin relaiile

nkkk1kkknkk IQRA,RQIA , se numete ir QR ataat matricei A, iar relaiile se

numesc pas QR cu deplasare explicit.

4. Ce sunt metodele indirect Metodele iterative au la baz construirea unui ir de aproximaii pentru soluia sistemului,

,1,0k,x ]k[ care s fie convergent pentru k la soluia adevrat, x :

0||xx||lim]k[

k

.

Practic, calculele se opresc la un index de iterare [s], atunci cnd este ndeplinit o condiie

de forma:

impus

]1s[]s[||xx||

,

sau, altfel spus, ]s[

x constituie o aproximare satisfctoare a soluiei calculate.

Avnd n vedere faptul c pentru o singur iteraie numrul de operaii n virgul mobil

este de ordinul lui 2n , asemenea metode se folosesc pentru sisteme de ordin mare i anume 42 1010 .

14

5. Metoda Simpson Principiul este de a aproxima fct f pe (xi,xi+1) printr-un polinom de grad 2 constrans sa treaca prin

punctele { xi+1,f(xi+1)}

)}x(f,x{},2

xxf,

2

xx{)},x(f,x{ 1i1i

1ii1iiii

.

)(2

4)(6

1)( 1

1i

iiiii xf

xxfxfhfS

3. Dac numrul de intervale, egal cu n, este par, atunci se obine:

S(f) ).42424(3

123210 nnnn fffffffh

- se numete regula 1/3

Simpson.

4. Dac numrul de intervale n este impar, atunci folosind un polinom de interpolare de gradul trei se

obine:

).33233233(8

3)( 123543210 nnnn ffffffffff

hfS

Aceast formul se numete regula 3/8 Simpson

6. Metoda Taylor Principiul acestei metode este ca pentru fiecare punct de integrare

ii1i1i htt,1N,...,1,0i,t , s se opreasc primii 1p termeni din dezvoltarea n

serie Taylor a funciei y(t) n jurul punctului it .

.y)t(y;1N,...,1,0i

),y,t(f!p

h)y,t(f

!2

h)y,t(fhyy

00

ii)1p(

pi

ii)1(

2i

iiii1i

reprezint formula de integrare Taylor de ordinul p, pentru rezolvarea acuaiilor

difereniale ordinare de ordinul nti.

7. problema cu SVD si rank 8. problema cu implementarea metodei secantei

citete 21 x,x

atribuie 10 xx

atribuie 21 xx

atribuie )}xx/()]x(f)x(f/{[)x(fxx 0101112

scrie soluia = , 2x

15

9. Ce sunt valorile singulare ale unei matrici Numerele

p1 ,, ( ( V~

AU~ T sau TV

~U~

A ), i

0},,,{diag p21p1 ) se numesc valori singulare ale matricei A.

Subiectul VI

1. Cum se realizeaza inmultirea/impartirea in virgula mobile ? Oricare ar fi x i y, dou numere din mulimea G, pentru care exist fl(x) i, respectiv, fl(y) aparinnd

multimii F, numrului yx i se asociaz numrul )yx(fl , care se determin cu algoritmul urmtor:

Pas 1: se reprezint intern numerele x i y prin fl(x) i, respectiv, fl(y).

Pas 2: se nmulesc fraciile i se adun exponenii.

Pas 3: din fracia rezultat se opresc t cifre.

Pas 4: dac este necesar, se normalizeaz rezultatul.

Observaii:

1. nmulirea nu este asociativ. 2. mprirea se realizeaz n aceeai manier ca i nmulirea, cu deosebirea c la pasul 2 mantisele se

mpart, iar exponenii se scad.

2. Care sunt etapele parcurse in rezolvarea unui sistem determinat de

ecuatii algebrice liniare prin descompunerea L_U a matricii sistem? considernd descompunerea L-U a matricei sistemului A, ULA , atunci rezolvarea sistemului

(Error! No text of specified style in document..2) implic dou subetape:

a. rezolvarea sistemului byL , etap numit i substituie nainte, obinnd soluia

intermediar y . Determinarea componentelor vectorului ni1i ]y[y are loc din aproape n

aproape: se ncepe cu 1y (prima ecuaie), se nlocuiete n a doua ecuaie determinnd pe 2y

i aa mai departe.

rezolvarea sistemului yxU , n care necunoscuta este x , etap numit i substituie invers. n

acest caz, determinarea componentelor vectorului x are loc pornind de la ultima ecuaie

3. De ce nu se recomanda rezolvarea sistemului de ec. normale pt.

obtinerea pseudosolutiei in sensul celor mai mici patrate a unui sistem supradeterminat de ec. algebrice liniare?

Conform celor prezentate n capitolul 2, pentru sistemul determinat de ecuaii normale Error!

Reference source not found., pseudosoluia *

x este unic determinat dac matricea acestui sistem,

AAT , este inversabil. Aceast condiie este ndeplinit dac matricea AAT este pozitiv definit.

n practic, ns, nu se recomand rezolvarea sistemului de ecuaii normale Error! Reference source

not found. deoarece matricea AAT , dei teoretic este pozitiv definit, prin calcul, datorit erorilor

de rotunjire, ea poate deveni pozitiv semidefinit, deci neinversabil. Astfel, n general, matricea

16

AAT este prost condiionat deoarece calculul su este afectat de erori de rotunjire deseori cu

caracter catastrofal.

4. In forma implementabila de ce nu se aplica direct matricii A algoritmul

QR (original) de aducere la forma canonica Schur? Algoritmul original QR, descris de relaiile Error! Reference source not found., este n general

consumator de timp. De aceea se folosete o form optimizat a algoritmului QR cu deplasare

explicit, pentru calculul valorilor i vectorilor proprii. Algoritmul optimizat cuprinde dou faze,

decsrise principial n continuare, iar n detaliu n subcapitolul urmtor.

5. Cum se determina o baza ortogonala a subspatiului nul al unei matrici

A (apartine R la nxn) folosind descompunerea valorilor singulare al matricei?

ultimele rn coloane ale matricei V~

formeaz o baz ortogonal pentru subspaiul nul al matricei

A:

}x,0xA/x{)A(N 1nm

,

]U~

U~

[]V~

V~

[AU~

V~

A 2121 .

)rn(m2111 V~

A,U~

V~

A 0 Din relaiile scrise mai sus i formele pe care le poate lua matricea , rezult c ultimele rn

coloane ale matricei V~

pot constitui o baz pentru )A(N . Subspaiul nul astfel determinat conine

doar vectorul n0 numai dac matricea A este de rang complet i nm .

6. Care este principiul metodei Newton de rezolvare a unei ec. neliniare?

Dac funcia f, care apare n membrul stng al ecuaiei neliniare, ndeplinete anumite condiii, atunci metoda Newton, denumit i metoda tangentei, se dovedete a fi cea mai rapid din clasa metodelor iterative.

7. Care este principiul regulei trapezului de cuadratura numerica?

Regula trapezului: aproximarea integrandului printr-un polinom de gradul unu

.2

)x(f)x(fh)f(T)f(T)f(I

1n

0i

1iii

1n

0ii

8. Care este principiul metodelor de integrare numerica a unei ec.

diferentiale ordinare de ordin I cu conditie initiala? Se consider ecuaia diferenial de ordinul nti de forma:

)t(y,t(fdt

)t(dy ,(Error! No text of specified style in document..8)

17

Iy],b,a[t),t(yy 0000 (Error! No text of specified style in document..9)

unde 0y reprezint condiia iniial cunoscut sau precizat. Fr a restrnge

generalitatea, se poate considera at0 .

Subiectul VII

1. ce intelegeti prin aritmetica virgulei mobile Prin aritmetica virgulei mobile se neleg urmtoarele:

(d) un model matematic de reprezentare a numerelor (definirea mulimii F);

(e) o modalitate de reprezentare a numerelor din mulimea G n calculatorul numeric, altfel spus o

modalitate de implementare n calculator a modelului (definirea operatorului de rotunjire, notat cu

fl);

(f) operaiile elementare: adunarea, scderea, nmulirea i mprirea definite cu numerele mulimii F.

2. care este principiul metodelor directe la sist de ec liniare Acest algoritm parcurge )1n( etape, la fiecare etap zerorizndu-se elementele de sub diagonala

principal i pstrnd nealterate transformrile care s-au efectuat n coloanele anterioare ale matricei

A.

3. ce intelegeti prin pseudosolutia sist de ec supradeterminat Triangularizarea bazat pe transformri ortogonale prezerv norma euclidian matricial. Aadar,

se pstreaz condiionarea numeric a matricei sistemului n raport cu norma euclidian, fiind

singura metod adecvat pentru calculul pseudosoluiei n sensul celor mai mici ptrate.

4. principiul alg QR

Pentru determinarea reflectorilor kU la fiecare iteraie k, se va considera drept vector , coloana

numrul k a matricei kA transformate. Astfel, se vor zeroriza, coloan cu coloan, elementele de sub

pseudo-diagonala principal a matricei A. n urma calculului matricei 1kA , primele 1k coloane din

matricea kA se pstreaz, iar coloanele de la 1k la n se modific n liniile de la k la m.

Algoritmul eueaz dac matricea A este deficient de rang. n acest caz, la calculul reflectorului kU ,

mrimea k ar fi nul, ceea ce va conduce la 0k n aritmetica real ( impusk || n virgul mobil).

Ca o consecin a acestui fapt, elementul k,kr de pe diagonala principal a matricei 1R va rezulta nul,

dac algoritmul eueaz la iteraia k. Pentru continuarea procesului de triangularizare (condiia de

executarea a unei iteraii), testul uzual care ine cont de erorile n virgul mobil este: impusk || .

n urma aplicrii acestui algoritm se obine:

RAUUU 11nn .

18

5. ce sunt valorile singulare Numerele

p1 ,, ( ( V~

AU~ T sau TV

~U~

A ), i

0},,,{diag p21p1 ) se numesc valori singulare ale matricei A.

6. care sunt conditiile de convergenta la metodele de rezolvare a

sist de ec neliniare

Spunem ca este convergenta pe o vecinatate V2 daca exista 2 vectori Vy,x , un scalar x

19

mantisa attea poziii cte sunt necesare pentru a crete exponentul la valoarea exponentului celuilalt

termen.

Pas 3: se adun mantisele i din rezultat se pstreaz t cifre.

Pas 4: dac este necesar, se normalizeaz rezultatul.

Observaii:

1. Deplasarea mantisei spre dreapta determin creterea exponentului, iar deplasarea spre stnga a mantisei determin scderea exponentului.

2. Scderea se realizeaz la fel ca adunarea, cu deosebirea c mantisele se scad. n fapt, scderea reprezint o adunare n care scztorul are semn schimbat.

2. triangularizare cu pivotare partiala n cazul triangularizrii cu pivotare parial (Figura 2.1), la pasul k se caut pivotul k printre

elementele din coloana k, pornind de la elementul de pe diagonala principal n jos, alegndu-se

elementul care are cea mai mare valoare n modul:

k

k

kinik

k

ki aa k |}{|max|| ][,

][

, .

3. de ce se alege norma euclediana pentru rezolvarea ecuatiilor in sensul c.m.m.p

Se intampla in sistemele practice ca vectorul b sa fie usor perturbat sis a nu apartina Im(A) dar si

intr-o astfel de situatie se doreste rezolvarea sistemului A* x = b . Ca urmare problema de calcul se

modifica si in loc sa caut x care sa satisfaca relatia, voi cauta *

x a.i. || *

xAb ||

4. ce metoda se foloseste pentru aflarea vectorilor propii

n general, calculul valorilor i vectorilorproprii intervine ca etap esenial n analiza i sinteza

sistemelor dinamice liniare (continue de timp), n probleme legate de:

studiul stabilitii (interne);

studiul rspunsului sistemelor.

Astfel, n ceea ce privete analiza stabilitii sistemelor automate, tehnicile matriceale bazate pe

localizarea valorilor proprii au o deosebit importan. n funcie de natura problemei, uneori este

suficient a determina plasarea valorilor proprii ale unei matrice n planul complex, alteori este absolut

necesar determinarea cu precizie a valorilor proprii. Pentru a rspunde acestor cerine diferite, au fost

abordate metode ce necesit un efort de calcul adecvat i a cror aplicare eficient presupune utilizarea

tehnicii de calcul:

- localizarea valorilor proprii prin metoda inegalitilor lui Ghergorin - calculul valorilor i vectorilor proprii bazat pe algoritmul QR i forma canonic Schur

5. valori singulare

20

Numerele p1 ,, ( ( V

~AU

~ T sau TV~

U~

A ), i

0},,,{diag p21p1 ) se numesc valori singulare ale matricei A.

6. metoda dreptunghiului

Regula dreptunchiului: aproximarea integrandului printr-un polinom de gradul zero

Funcia )x(f este aproximat pe intervalul ]x,x[ 1ii printr-un polinom de gradul zero, deci printr-o

constant: )2/)xx((f)x(f 1ii . Ca urmare, se obine:

1n,,0i,xxh,2

xxfh)f(D)f(I i1ii

1iiiii

.

Subiectul IX

1. Ce se intelege prin algoritm stabil numeric? Un algoritm G se numete stabil numeric, dac datele exacte i datele perturbate ale problemei de

calcul G fiind apropiate ntr-un anumit sens, atunci i soluia exact matematic corespunztoare setului de

date perturbate G(D*) este apropiat, ntr-un anumit sens, de soluia algoritmului corespunztoare setului

de date exacte G*(D). Altfel, algoritmul se spune c este instabil din punct de vedere numeric.

2. Cum se realizeaza triangularizarea cu pivotare totala a unei matrici A

apartinand lui R la n*n? n cazul triangularizrii cu pivotare total (Figura 2.2), la pasul [k] al triangularizrii se alege drept pivot

elementul maxim n modul din submatricea format din liniile de la k la n, coloanele de la k la n:

|}a{|max|a| ]k[ j,injknik

]k[

j,i kk

.

3. De ce se folosesc matrici ortogonale de transformare pt.

triangularizarea matricii sistemului in cazul rezolvarii numerice in sensul celor mai mici patrate a unui sistem supradeterminat de ecuatii algebrice liniare? ceea ce intereseaz este determinarea unui vector

*x care minimizeaz norma euclidian a reziduului:

xAbr .

Multiplicnd la stnga relaia cu matricea ortogonal U, se obine :

2

11

d

xRd

xRdxAUbUrU .

Matricea U fiind ortogonal, aceasta pstreaz norma vectorial euclidian

21

4. Ce structura are forma canonica Schur a unei matrici A apartinand lui

R la n*n? O matrice nnT se spune c este n form bloc superior triunghiular, dac are urmtoarea

structur:

ii ppii

mm

m222

m11211

T,

T

TT

TTT

T

00

0

,

unde m,...,1i,Tii sunt submatrice ptratice. Dac, n plus, blocurile diagonale sunt matrice de ordin

maxim 2, atunci se spune c matricea este n form cvasi-superior triunghiular.

5. Cum se determina rangul unei matrici?

Se consider o matrice nmA i fie }n,mmin{p . Se noteaz cu r rangul matricei A. Acesta

satisface la relaia: pr . Dac pr , se spune c matricea este deficient de rang, iar dac pr ,

atunci se spune c matricea este de rang complet.

rangul matricei A este egal cu rangul matricei nm , care este egal cu r. Altfel spus, rangul

acestor matrice este egal cu numrul valorilor singulare nenule.

6. Care este principiul metodei Gauss-Seidel de rezolvare a unui sistem

de ecuatii algebrice neliniare? Ca urmare, rezolvarea sistemului neliniar se transform n rezolvarea a n probleme, fiecare problem

nsemnnd rezolvarea unei ecuaii neliniare Se aplic acelai principiu de la metoda Jacobi. De aceast dat, n afar de aproximaia de la iteraia

[k], anterioar, se folosesc succesiv, cnd este posibil, i componentele determinate ale estimaiei de la iteraia curent, ]1k[

7. Care sunt conditiile pe baza carora se determina functia spline cubica

natural ce aproximeaza o functie? se numete funcie spline de ordinul m pe reeaua , notat )x(s , o funcie care ndeplinete

urmtoarele condiii:

(i) restricia la intervalul 1n,,0i],x,x[ 1ii , ]x,x[ 1ii)x(s

, aparine mulimii polinoamelor

algebrice de grad maxim m;

(ii) funcia )x(s este continu, cu derivate continue pn la ordinul 1m pe intervalul ]b,a[ :

1m]b,a[C)x(s

.

Dac 1m , atunci funciile spline se numesc liniare, dac 2m , atunci ele se numesc funcii spline

cuadrice, iar dac 3m , atunci funciile spline se numesc cubice.

Pentru a calcula aceti parametri, se utilizeaz condiiile din definiia funciilor spline:

(C1) condiii de interpolare:

n.,0i,y)x(s ii

22

ceea ce nseamn )1n( condiii;

(C2) continuitatea funciei )x(s :

1n,,1i),x(slim)x(s)x(s)x(slim

i

i

i

ixxxx

not

ii

not

xxxx

,

ceea ce nseamn )1n( condiii;

(C3) continuitatea primei derivate, )x(s :

1n,,1i),x(slim)x(s)x(s)x(slim

i

i

i

ixxxx

not

ii

not

xxxx

,

ceea ce nseamn )1n( condiii;

(C4) continuitatea derivatei a doua, )x(s :

1n,,1i),x(slim)x(s)x(s)x(slim

i

i

i

ixxxx

not

ii

not

xxxx

,

ceea ce nseamn )1n( condiii.

8. Care este principiul metodei Euler de integrare numerica a unei

ecuatii diferentiale? Principiul acestor tipuri de metode este ca pentru fiecare punct de integrare

ii1i1i htt,1N,...,1,0i,t , s se opreasc primii doi termeni din dezvoltarea n serie Taylor a

funciei y(t) n jurul punctului it .