ANALIZA NUMERICAExercitii si teme de laboratorEditie completata si revizuita

Iuliana PARASCHIV-MUNTEANU

Daniel STANICA

Bucuresti, 2008

Cuprins

Introducere 9

Prefata la editia a doua 11

Notatii 13

1 Sisteme liniare 151.1 Elemente de analiza matriciala . . . . . . . . . . . . . . . . . . . . . 15

1.1.1 Norme de vectori si norme de matrice . . . . . . . . . . . . . 151.1.2 Conditionarea unui sistem de ecuatii liniare . . . . . . . . . . 23

1.2 Metode directe pentru rezolvareasistemelor de ecuatii liniare . . . . . . . . . . . . . . . . . . . . . . . 281.2.1 Rezolvarea unui sistem triunghiular . . . . . . . . . . . . . . 281.2.2 Metoda lui Gauss (cu pivotare partiala) . . . . . . . . . . . . 291.2.3 Metoda lui Gauss (cu pivotare totala) . . . . . . . . . . . . . 321.2.4 Descompunerea LU . . . . . . . . . . . . . . . . . . . . . . . . 341.2.5 Descompunerea LU recursiva si descompunerea LUP . . . . . 371.2.6 Descompunerea Choleski . . . . . . . . . . . . . . . . . . . . . 421.2.7 Descompunerea QR . . . . . . . . . . . . . . . . . . . . . . . 44

1.3 Metode iterative pentru aproximarea solutiilorsistemelor liniare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461.3.1 Metoda lui Jacobi . . . . . . . . . . . . . . . . . . . . . . . . 461.3.2 Metoda lui Jacobi pentru matrice diagonal dominante . . . . 491.3.3 Metoda Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . 511.3.4 Metoda relaxarii simultane . . . . . . . . . . . . . . . . . . . 541.3.5 Metoda relaxarii succesive . . . . . . . . . . . . . . . . . . . . 571.3.6 Metoda gradientilor conjugati . . . . . . . . . . . . . . . . . . 59

1.4 Inversa (pseudoinversa) unei matrice . . . . . . . . . . . . . . . . . . 621.4.1 Inversa unei matrice triunghiulare . . . . . . . . . . . . . . . 621.4.2 Metoda Gauss-Jordan . . . . . . . . . . . . . . . . . . . . . . 621.4.3 Metoda lui Ritz . . . . . . . . . . . . . . . . . . . . . . . . . . 641.4.4 Pseudoinversa unei matrice . . . . . . . . . . . . . . . . . . . 651.4.5 Algoritm pentru determinarea rangului unei matrice . . . . . 71

5

6 CUPRINS

2 Ecuatii neliniare 732.1 Ecuatii neliniare pe R . . . . . . . . . . . . . . . . . . . . . . . . . . 73

2.1.1 Metoda bisectiei . . . . . . . . . . . . . . . . . . . . . . . . . 732.1.2 Regula ”falsi” . . . . . . . . . . . . . . . . . . . . . . . . . . . 752.1.3 Metoda contractiei . . . . . . . . . . . . . . . . . . . . . . . . 762.1.4 Metoda coardei . . . . . . . . . . . . . . . . . . . . . . . . . . 782.1.5 Metoda secantei . . . . . . . . . . . . . . . . . . . . . . . . . 802.1.6 Metoda lui Newton . . . . . . . . . . . . . . . . . . . . . . . . 81

2.2 Metode numerice pentru determinarea extremelor functiilor reale . . 822.2.1 Metoda sectiunii de aur . . . . . . . . . . . . . . . . . . . . . 832.2.2 Metoda Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . 83

2.3 Ecuatii neliniare ın Rm . . . . . . . . . . . . . . . . . . . . . . . . . 852.3.1 Principiul contractiei . . . . . . . . . . . . . . . . . . . . . . . 852.3.2 Metoda Gauss-Seidel neliniara . . . . . . . . . . . . . . . . . 862.3.3 Metoda lui Newton . . . . . . . . . . . . . . . . . . . . . . . . 882.3.4 Metoda lui Newton-Kantorovici . . . . . . . . . . . . . . . . . 902.3.5 Metoda lui Newton simplificata . . . . . . . . . . . . . . . . . 91

3 Vectori si valori proprii 943.1 Metode folosind polinomul caracteristic . . . . . . . . . . . . . . . . 94

3.1.1 Metoda Danilevsky . . . . . . . . . . . . . . . . . . . . . . . . 953.1.2 Metoda Krylov . . . . . . . . . . . . . . . . . . . . . . . . . . 983.1.3 Metoda Leverrier . . . . . . . . . . . . . . . . . . . . . . . . . 1003.1.4 Metoda coeficientilor nedeterminati . . . . . . . . . . . . . . 104

3.2 Metoda rotatiilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1053.3 Metoda puterii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1103.4 Algoritmul LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1113.5 Algoritmul QR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1123.6 Metoda bisectiei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

4 Interpolare 1194.1 Formula lui Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . 1194.2 Algoritmul lui Aitken . . . . . . . . . . . . . . . . . . . . . . . . . . . 1204.3 Algoritmul lui Neville . . . . . . . . . . . . . . . . . . . . . . . . . . 1224.4 Formula lui Newton de reprezentare a polinomului de interpolare . . 1244.5 Formula lui Newton de interpolare ascendenta . . . . . . . . . . . . . 1304.6 Formula lui Newton de interpolare descendenta . . . . . . . . . . . . 1324.7 Formula de interpolare Gauss ınainte . . . . . . . . . . . . . . . . . . 1344.8 Formula de interpolare Gauss ınapoi . . . . . . . . . . . . . . . . . . 1354.9 Formula de interpolare Stirling . . . . . . . . . . . . . . . . . . . . . 1364.10 Interpolare cu functii spline de ordinul ıntai . . . . . . . . . . . . . . 1394.11 Interpolare cu functii spline cubice . . . . . . . . . . . . . . . . . . . 1434.12 Derivare numerica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1464.13 Constructia curbelor de regresie . . . . . . . . . . . . . . . . . . . . . 151

CUPRINS 7

5 Cuadraturi si cubaturi numerice 1535.1 Formula de cuadratura a dreptunghiului . . . . . . . . . . . . . . . . 1535.2 Formula de cuadratura a trapezului . . . . . . . . . . . . . . . . . . . 1565.3 Formula de cuadratura Simpson . . . . . . . . . . . . . . . . . . . . . 1585.4 Formula de cuadratura Hermite . . . . . . . . . . . . . . . . . . . . . 1615.5 Formula de cuadratura Newton . . . . . . . . . . . . . . . . . . . . . 1635.6 Formula de cuadratura Newton-Cotes . . . . . . . . . . . . . . . . . 1655.7 Formule de cuadratura Gauss . . . . . . . . . . . . . . . . . . . . . . 1715.8 Formula de cuadratura Euler-Maclaurin . . . . . . . . . . . . . . . . 1755.9 Formula de extrapolare Romberg . . . . . . . . . . . . . . . . . . . . 1765.10 Formule de cubatura . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

6 Metode numerice pentru ecuatii diferentiale 1836.1 Preliminarii teoretice . . . . . . . . . . . . . . . . . . . . . . . . . . . 1856.2 Metoda aproximatiilor succesive (Picard) . . . . . . . . . . . . . . . 1866.3 Metode ıntr-un pas (directe) . . . . . . . . . . . . . . . . . . . . . . . 188

6.3.1 Metoda Taylor . . . . . . . . . . . . . . . . . . . . . . . . . . 1906.3.2 Metoda Euler explicita (progresiva) . . . . . . . . . . . . . . 1926.3.3 Metode Runge-Kutta . . . . . . . . . . . . . . . . . . . . . . 195

6.4 Metode ın mai multi pasi (indirecte) . . . . . . . . . . . . . . . . . . 2096.4.1 Metoda Adams-Bashforth . . . . . . . . . . . . . . . . . . . . 2116.4.2 Metoda Adams-Moulton . . . . . . . . . . . . . . . . . . . . . 2166.4.3 Metoda predictor-corector . . . . . . . . . . . . . . . . . . . . 221

7 Metode numerice pentru ecuatii cu derivate partiale 2247.1 Ecuatii cu derivate partiale de ordinul ıntai . . . . . . . . . . . . . . 224

7.1.1 Scheme explicite pentru metoda cu diferente finite . . . . . . 2267.1.2 Scheme implicite pentru metoda cu diferente finite . . . . . . 234

7.2 Ecuatii cu derivate partiale de ordinul doi . . . . . . . . . . . . . . . 2377.2.1 Ecuatii cu derivate partiale de tip parabolic . . . . . . . . . . 2387.2.2 Ecuatii cu derivate partiale de tip eliptic . . . . . . . . . . . . 2477.2.3 Ecuatii cu derivate partiale de tip hiperbolic . . . . . . . . . 253

Bibliografie 262

8 CUPRINS

Introducere

Aceasta lucrare este o culegere de lucrari de laborator si exercitii de seminar carese adreseaza studentilor din Facultatea de Matematica si Informatica a UniversitatiiBucuresti ce urmeaza cursul general de analiza numerica.

Analiza numerica reprezinta un capitol important al analizei matematicie careare ca obiect rezolvarea sau aproximarea solutiilor ecuatiilor, sistemelor de ecuatii,ecuatiilor diferentiale, aproximarea functiilor si a derivatelor lor, integralelor definiteetc. In ultimele decenii metodele numerice s-au dezvoltat foarte mult, ın specialdatorita progresului tehnicii de calcul, care - daca luam doar un exemplu - a permisrezolvarea unui numar impresionant de ecuatii ıntr-un timp foarte scurt si cu oprecizie foarte buna. Aproximarea numerica este una dintre cele mai folosite metodede rezolvare a unei probleme complexe si a preocupat dea lungul timpului marimatematicieni care si-au legat numele de o serie de metode consacrate folosite si ınprezent ın obtinerea algoritmilor de calculator.

Cele sase capitole prezentate ın lucrare permit abordarea unor probleme vari-ate de analiza numerica cum ar fi: metode exacte si aproximative de rezolvare asistemelor de ecuatii liniare si neliniare, metodele de determinare a valorilor si vec-torilor proprii ai unei matrice, interpolarea polinomiala si cu functii spline, derivareasi integrarea numerica, trasarea curbelor de regresie, metode de rezolvare a ecuatiilordiferentiale ordinare.

Prima parte a fiecarui paragraf cuprinde aprofundarea unor notiuni teoretice sideducerea unui algoritm pentru problema prezentata, iar a doua parte se refera lacalcule numerice pe baza algoritmului si la testarea sa pe exemple numerice concrete,care sa fie folosite ın verificarea programelor. Sunt prezentate exercitii rezolvate, caredemonstreaza fie rezultate teoretice, fie reprezinta aplicatii ale algoritmilor de calculnumeric.

Prezenta lucrare este rezultatul activitatii desfasurate de autori cu studentii ıncadrul seminarelor si laboratoarelor de analiza numerica, pe parcursul a mai multiani. Am ıncercat ca observatiile si cerintele studentilor sa se regaseasca ın aceastalucrare.

Aducem multumiri referentilor lucrarii pentru lectura atenta si avizata a lucrariisi pentru observatiile constructive asupra continutului lucrarii.

9

10 introducere

Prefata la editia a doua

Ca urmare a solicitarilor aparute din partea studentilor dupa publicarea primei editiia acestei lucrari ne-am gandit ca este bine ca ıntr-o a doua editie sa facem eventualeretusuri si completari necesare. Fata de prima editie a lucrarii fost adaugate:− exercitii la paragrafele privind conditionarea unei matrice, descompunerea LU ,

pseudoinversa unei matrice, metoda contractiilor, metoda Newton;− algoritmi: algoritmul Gramm-Schimdt pentru pseudoinversa unei matrice,

metode numerice pentru puncte de extrem, algoritm pentru formula de reprezentareNewton, formulele de cuadratura Euler-Maclaurin si Romberg, metode numericepentru integrale multiple (cubaturi numerice);− capitolul 7 care contine metode numerice pentru ecuatii cu derivate partiale,

si anume, scheme explicite si implicite cu diferente finite pentru pentru ecuatiicvasiliniare cu derivate partiale de ordinul ıntai si pentru ecuatii cu derivate partialede ordinul al doilea de tip parabolic, eliptic si hiperbolic cu conditii initiale si la limita(schema Crank-Nicolson, metoda directiilor alternante, metode iterative punctuale,metode iterative ın bloc). Pentru fiecare metoda au fost prezentate exemple nu-merice si grafice corespunzatoare.

20 Aprilie 2008

Autorii

11