Date post: | 19-Oct-2015 |
Category: |
Documents |
Upload: | gabriel-enasoaie |
View: | 58 times |
Download: | 1 times |
of 22
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 .