Analiza numerica
„ Matematica a învățat să calculeze valoarea numerică a necunoscutelor care apar în probleme practice. Acesta este scopul final al tuturor teoriilor, analitice, geometrice și mecanice. Acestea, în școlile noastre, trebuie încoronate prin calcul numeric, pentru a scoate la lumină semnificația și aplicarea lor. " |
( Peano , tabelele de prefață numerice) |
Analiza numerică (cunoscută și sub numele de calcul numeric sau calcul științific) este o ramură a matematicii aplicate care rezolvă modelele produse de la analiza matematică până la descompuneri finalizate în mod normal practicabile, implicând conceptul de aproximare . Instrumentele sale, algoritmii menționați, pot fi caracterizate pe baza vitezei de convergență, a stabilității numerice și a calculabilității .
Descriere
Majoritatea metodelor de soluție numerică oferite de analiză se bazează pe „ algebră liniară sau pe construcția de secvențe convergente de numere sau funcții pe lângă contribuțiile combinatoriale și geometrice și conexiunile cu metode probabiliste și fizico-matematice .
Unele probleme ale constantei matematice pot fi rezolvate cu algoritmi care rezolvă problema într-un număr finit și, eventual, cunoscute în avans, pașii; aceste metode se numesc metode directe. Un exemplu tipic este dat de metoda de eliminare Gauss pentru rezolvarea sistemelor de ecuații liniare . Cu toate acestea, pentru majoritatea problemelor numerice nu există metode directe și în aceste cazuri este adesea posibilă utilizarea unei metode iterative . O metodă iterativă începe printr-o încercare și găsește aproximări succesive care, sperăm, converg spre soluție.
De obicei, scrieți problema formei x = F (x) și aplicați teorema punctului fix . Un exemplu clasic de algoritm iterativ este metoda lui Newton de a calcula zerourile unei funcții. Chiar și atunci când există o metodă directă, este preferabilă uneori o metodă iterativă, deoarece este mai eficientă sau mai stabilă, de exemplu atunci când se rezolvă sisteme de ecuații liniare cu mii de necunoscute.
Aplicații
Impactul asupra lumii reale este decisiv și disipează clișeul că matematica nu are un scop practic. Un exemplu: algoritmul FFT (Fast Fourier Transform), care este unul dintre succesele analizei numerice, stă la baza algoritmilor reconstructivi de tomografie computerizată a imaginii și imagistică prin rezonanță magnetică și rezolvarea problemelor multimedia cum ar fi, printre cele mai importante, compresia Compresie imagine JPEG Compresie muzică MP3 filme mpeg , eșantionare și filtrare a semnalelor.
Algoritmii de analiză numerică sunt aplicați zilnic pentru a rezolva multe alte probleme științifice și tehnice. Exemple sunt proiectarea de structuri precum poduri și avioane, prognozele meteo , analiza moleculelor ( chimie de calcul ). Algoritmii de analiză numerică sunt, de asemenea, baza programelor CAE și aproape toate supercomputerele se străduiesc constant să efectueze algoritmi de analiză numerică.
Eficiența algoritmilor și implementarea lor sunt de o mare importanță. Prin urmare, o metodă euristică eficientă poate fi preferată unei metode cu o bază teoretică solidă, dar ineficientă. Limbajele de programare eficiente Fortran și C , deși datate, sunt cele mai utilizate.
În general, analiza numerică este atât o știință teoretică, cât și o știință experimentală. De fapt, nu numai că folosește axiome , teoreme și dovezi , ca și restul matematicii, dar folosește și rezultatele elaborărilor empirice efectuate pentru a studia cele mai bune metode de rezolvare a problemelor.
fundal
Domeniul analizei numerice datează de secole înainte de inventarea computerelor electronice . De fapt, mulți mari matematicieni din trecut au fost dedicați analizei numerice, după cum reiese din numele unor algoritmi importanți datorate lui Isaac Newton , Joseph-Louis Lagrange , Philipp Ludwig von Seidel , Carl Jacobi , Carl Friedrich Gauss sau Euler .
Pentru a facilita calculele manuale, au fost tipărite cărți mari umplute cu formule și tabele de date, cum ar fi punctele de interpolare și coeficienții funcțiilor. Folosind aceste tabele a fost posibil să se găsească valorile care trebuie inserate în formulele date și să se obțină estimări numerice foarte bune ale unor funcții. Lucrarea canonică în domeniu este publicarea NIST editată de Abramowitz și Stegun , o carte de peste 1.000 de pagini care conține un număr mare de formule și funcții utilizate în mod obișnuit și valorile lor în multe puncte. Valorile funcției nu mai sunt foarte utile atunci când puteți utiliza un computer, dar lista largă de formule poate fi totuși foarte utilă.
Calculatorul mecanic a fost, de asemenea, dezvoltat ca instrument de calcul manual. Aceste calculatoare au evoluat în computere electronice în anii 1940 ; invenția computerului a influențat și domeniul analizei numerice, permițând dezvoltarea unor calcule din ce în ce mai complexe.
Arii de studiu
Domeniul analizei numerice este împărțit în diferite discipline în funcție de problema de rezolvat.
Calculul valorilor funcției
Una dintre cele mai simple probleme este evaluarea unei funcții la un moment dat. Chiar și evaluarea unui polinom nu este imediată: algoritmul lui Horner este adesea mai eficient decât metoda obișnuită. În general, atenția principală în rezolvarea acestor probleme vizează estimarea și menținerea sub control a erorilor de rotunjire datorate aritmeticii în virgulă mobilă . Acest lucru se face acordând atenție ordinii în care sunt efectuate operațiile aritmetice, încercând să minimalizeze numărul acestora și încercând să le evite, atunci când este posibil, pe cele „periculoase”, adică pe cele care duc la pierderea unor cifre semnificative. precum cele care provoacă ștergerea numerică .
Interpolare, extrapolare și regresie
Metodele de interpolare și extrapolare estimează valoarea unei funcții necunoscute, având în vedere valoarea funcției în sine în unele puncte. Cea mai simplă metodă de interpolare este „ interpolare liniară , care presupune că funcția necunoscută este liniară între fiecare pereche de puncte consecutive. Această metodă poate fi generalizată din „ interpolare polinomială care este uneori mai precisă, dar suferă de fenomenul lui Runge . Alte metode de interpolare folosesc funcții regulate uneori ca spline sau wavelets . Extrapolarea, spre deosebire de interpolare, estimează funcția în punctele din afara punctelor pentru care funcția este cunoscută.
Regresia este similară cu problemele de mai sus, dar ia în considerare faptul că valorile datelor sunt inexacte. Tehnica preferată pentru regresie este metoda celor mai mici pătrate .
Soluția de ecuații și sisteme de ecuații
O altă problemă fundamentală este calcularea soluției unei ecuații sau a unui sistem de ecuații. Principala distincție este între ecuații, sau sisteme de ecuații, care sunt liniare și între ecuații, sau sisteme de ecuații, care sunt neliniare. Problemele liniare sunt mai ușor de rezolvat.
Metodele de rezolvare a sistemelor de ecuații liniare pot fi împărțite în două categorii.
Prima categorie este cea a metodelor directe. Această categorie include, de exemplu, metoda de eliminare Gaussian și factorizarea LU . Metodele directe construiesc soluția exactă, până la erori de rotunjire, într-un număr finit de pași. În esență, ei utilizează ideea factorizării matricii coeficienților sistemului în produsul a două matrice mai simple, de obicei triunghiulare sau ortogonale . [1] Acestea sunt, în general, cele mai eficiente metode, mai ales atunci când funcționează pe matrici cu coeficienți densi , dar pe sisteme mai mari și / sau cu coeficienți matricile rare tind să fie prea costisitoare în ceea ce privește consumul de memorie. În aceste situații, metodele aparținând celei de-a doua categorii sunt de obicei preferabile.
A doua categorie este cea a metodelor iterative. Acestea aparțin metodelor iterative, de exemplu metoda Jacobi , Gauss-Seidel și metoda gradientului conjugat . Metodele iterative conduc la soluția sistemului într-un număr teoretic infinit de pași: pornind de la o aproximare inițială a soluției, oferă o serie de aproximări care, în ipoteze adecvate, converg la soluția exactă. Procesul iterativ este oprit imediat ce a fost atinsă precizia dorită. Metoda aplicată este eficientă dacă precizia dorită a fost atinsă într-un număr acceptabil de iterații. [2]
Dacă ecuațiile sunt neliniare, folosim algoritmul pentru a găsi rădăcini . Dacă funcția este diferențiată și derivata ei este cunoscută, atunci metoda Newton este o alegere populară. Liniarizarea este o altă tehnică pentru rezolvarea ecuațiilor neliniare.
„ Optimizarea
Problemele de optimizare necesită găsirea punctului în care o anumită funcție își asumă valoarea maximă sau minimă. Adesea, punctul trebuie să satisfacă anumite constrângeri .
Câmpul optimizării este împărțit în continuare în mai multe subcâmpuri, în funcție de forma funcției obiective și constrângeri. De exemplu, programarea liniară se ocupă de cazul în care atât obiectivul funcționează conform căruia constrângerile sunt liniare. Cel mai faimos algoritm de programare liniară este metoda simplex .
Metoda multiplicatorilor Lagrange poate fi utilizată pentru a reduce problemele de optimizare constrânse în problemele de optimizare constrânse.
Algoritmii de optimizare sunt de obicei testați utilizând funcții speciale de testare , concepute pentru a le testa în probleme care au dificultăți de calcul deosebite.
Evaluarea integralelor
Integrarea numerică, cunoscută și sub numele de cvadratură numerică, estimează valoarea unei integrale definite. Metodele utilizate pe scară largă folosesc unele formule Newton-Cotes , de exemplu, regula punctului de mijloc sau regula trapezoidală , sau cvadratura Gaussiană . Cu toate acestea, dacă dimensiunea domeniului de integrare devine mare, aceste metode devin costisitoare. În această situație, puteți utiliza o metodă Monte Carlo , o metodă cvasi-Monte Carlo sau, pentru moderații mari, metoda rețelelor rare .
Ecuațiile diferențiale
Analiza numerică a fost, de asemenea, interesată de calculul aproximativ al soluției ecuațiilor diferențiale , atât derivate obișnuite până la derivate parțiale . Ecuațiile diferențiale sunt rezolvate mai întâi prin discretizarea ecuației, adică aducerea ei într-un subespai dimensional finit. Acest lucru se poate face cu o metodă cu element finit , ometodă cu diferență finită sau o metodă cu volum finit , utilizată în special în inginerie. Justificarea teoretică a acestor metode implică deseori analiza funcțională a teoremelor dell '. Acest lucru reduce problema la soluția unei ecuații algebrice.
Unele probleme abordate prin analiza numerică
Problemele luate în considerare prin analiza numerică includ:
- Analiza erorii în aritmetica finită
- Reprezentarea de bază și aritmetica finită
- Eroare inerentă, eroare algoritmică, eroare analitică
- Condiționarea unei probleme, eroare de eroare înapoi și înainte
- Calculul valorilor funcției:
- Evaluarea polinoamelor folosind regula Horner
- Estimarea „ erorii de rotunjire ”
- Soluția sistemelor de ecuații liniare :
- Metoda de eliminare a lui Gauss
- Descompunerea LU
- Factorizarea QR
- Descompunerea Cholesky pentru matrici simetrice
- Metode iterative pentru rezolvarea sistemelor de ecuații liniare
- Problema calculului numeric al valorilor proprii
- Metoda puterii
- Algoritm QR
- Rezolvarea problemelor neliniare, folosind adesea tehnici de liniarizare :
- Regresie
- Evaluarea numerică a integralelor utilizând „ integrarea numerică , cunoscută și sub numele de cvadratură
- Soluția numerică a ecuațiilor diferențiale obișnuite
- Metoda lui Euler
- Metode explicite și implicite
- Metode în mai mulți pași: metode Runge Kutta
- Soluția numerică a ecuațiilor diferențiale parțiale
- Teoria interpolării și aproximării
- Extrapolarea
Când sunt posibile soluții diferite la problemele numerice, trei factori se cântăresc în a decide ce metodă să urmeze:
- Stabilitate - erorile din aproximare nu ar trebui să crească necontrolat atunci când dimensiunea calculelor crește
- Precizie - aproximarea numerică trebuie să fie cât mai exactă posibil
- Eficiență - cu cât calculul este mai rapid, cu atât metoda este mai bună. Cu toate acestea, trebuie găsit un compromis între precizie și eficiență
Generarea și propagarea erorilor
Studiul erorilor este o parte importantă a analizei numerice. Există mai multe moduri în care pot fi introduse erori în rezolvarea unei probleme:
- eroare inerentă : are atunci când reprezintă un număr real cu un număr finit de cifre. De exemplu, atunci când reprezintă un număr real cu un număr de mașină într-un computer (de exemplu, anulare digitală ).
- eroare algoritmică : atunci când o utilizați pentru a rezolva problema prin aritmetică, de exemplu, pe computer.
- eroare analitică sau discretizare: se întâmplă atunci când abordează o problemă continuă cu o problemă discretă.
O eroare, odată ce a fost generată, se propagă în general prin calcul. Acest lucru duce la conceptul de stabilitate numerică : un algoritm este declarat numeric stabil dacă o eroare, odată ce a fost generată, nu crește prea mult în timpul calculului. Pentru unele probleme nu există algoritmi stabili, deoarece pentru variații arbitrare mici ale datelor problemei, soluția variază foarte mult. Aceste probleme sunt numite prost condiționate. O problemă este prost condiționată, spune bine condiționată .
Cu toate acestea, un algoritm care rezolvă o problemă bine condiționată poate sau nu să fie stabil din punct de vedere numeric. Scopul principal al analizei numerice este de a găsi algoritmi stabili pentru rezolvarea problemelor bine condiționate. Un alt scop al analizei numerice este de a găsi, pentru fiecare problemă necondiționată, o problemă bine condiționată a cărei soluție se apropie de cea a problemei inițiale.
Software-ul
Atunci când algoritmii de analiză numerică sunt traduși într-un limbaj de programare și adaptați corespunzător la caracteristicile mediului de calcul, de exemplu implementat și executat pe un computer, vorbim despre software numeric. Există cel puțin trei categorii de software numeric:
- Biblioteci pentru programatori ( Netlib , IMSL , NAG, GNU Scientific Library , BLAS , LAPACK , FFTW ).
- Medii interactive pentru rezolvarea problemelor de matematică și științe computaționale ( Mathematica , Matlab , Maple , Scilab , GNU Octave , IDL ) numite Medii de rezolvare a problemelor (PSE).
- Aplicații pentru rezolvarea problemelor specifice aplicațiilor, cum ar fi ingineria (software CAE ).
Notă
- ^ Valeriano Comincioli, Metode numerice și științe statistice aplicate, CEA Casa Editrice Ambrosiana, 1992, ISBN 88-408-0757-8
- ^ John Monegato, Elements of Numerical Analysis, Ed. Levrotto & Bella, Torino 1995 ISBN 978-88-8218-017-1 , pp. III-2, III-3
Bibliografie
Lucrări introductive
- A. Bevilacqua, D. Bini, M. Capuans , Menchi O. (1987): Introduction to Computational Mathematics, Freeman, ISBN 88-08-04356-8
- Samuel D. Conte, Carl de Boor (1981): Analiză numerică elementară. O abordare algoritmică, ediția a 3-a, McGraw-Hill, ISBN 0-07-012447-7
- Valeriano Comincioli (1990): Analiză numerică. Metode, modele, aplicații. McGraw-Hill, ISBN 88-386-0646-3 ; ediție nouă carte electronică APOGEO, Feltrinelli Milano, 2005 http://www.apogeonline.com/libri/88-503-1031-5/scheda
- John Monegato (1990): Fundamentele calculului numeric, Levrotto & Bella, Torino
- (EN) Walter Gautschi (1997): Analiză numerică. O introducere, Birkhäuser ISBN 3-7643-3895-4
- A. Quarteroni , R. Sacco, F. Saleri (2000): Matematică numerică, Springer Italia, Milano
(disponibil și o versiune în limba engleză mai largă) ISBN 88-470-0077-7
- G. Naldi, L. Pareschi, G. Russo (2001, 2004 și II.): Introducere în calculul științific, McGraw-Hill, ISBN 88-386-0885-7
- (EN) Endre Suli și David Mayers, An Introduction to Numerical Analysis, Cambridge, Cambridge University Press, 2003, ISBN 978-0-521-00794-8 .
Lucrări de referință
- Dario A. Bini, Viktor Y. Pan (1994): Calcule polinomiale și matriciale, Birkhäuser, ISBN 0-8176-3786-9
- A. Bevilacqua, D. Bini, M. Capuans , Menchi O. (1992): Metode numerice, Freeman, ISBN 88-08-14510-7
- (EN) Philippe Ciarlet , Jacques-Louis Lions eds. (1990): Manual de analiză numerică Volumul I. Metode de diferență finită (Partea 1). Soluția de ecuații în R n (Partea 1), Olanda de Nord, ISBN 0-444-70366-7
- (EN) Philippe Ciarlet , Jacques-Louis Lions eds. (1991): Manual de analiză numerică Volumul II. Metode cu elemente finite (partea 1), Olanda de Nord, ISBN 0-444-70365-9
Fundamente teoretice
- Kendall Atkinsons, Weimin Han (2001): Analiză teoretică numerică. Un cadru de analiză funcțională, Springer ISBN 0-387-95142-3
Algebră liniară numerică
- D. Bini, M. Capovani , Menchi O. (1988): Metode numerice pentru algebra liniară, Zanichelli, ISBN 88-08-06438-7
- (EN) Gene H. Golub, Charles F. Van Loan (1996): Matrix computations, ed. III, Johns Hopkins University Press, ISBN 0-8018-5414-8
Alte
- HL Rice Teoria și practica interpolației; inclusiv quadratura mecanică și alte probleme importante Preocupate de valorile tabulare ale funcțiilor (TP Nichols, Lynn, Massachusetts, 1899) (interpolare)
- D. Gibb Un curs de interpolare și integrare numerică pentru laboratorul de matematică (Londra: Bell, 1915)
- Horst von Sanden Analiză matematică practică (Methuen, Londra, 1923)
- ET Whittaker și G. Robinson Un curs scurt de interpolare (Londra: Blackie & Sons, 1923) (interpolare)
- ET Whittaker și G. Robinson Calculul observațiilor (Blackie & Sons, Londra, 1924) (interpolare, cuadratură)
- C. Runge și H. Koenig Vorlesungen über numerisches Rechnen (Berlin: Springer, 1924)
- James Blaine Scarborough, Analiză matematică numerică. Baltimore, The Johns Hopkins Press, 1930.
- AS Householder, Principles of Numerical Analysis, (New York, McGraw-Hill 1953) (primul text privind analiza numerelor pentru computere)
- M. Abramowitz și I. Stegun Manual de funcții matematice (Dover, New York, 1972) Capitolul 25
- ME Davis Metode numerice și modelare pentru ingineri chimici (John Wiley & Sons, New York, NY, 1984) ISBN 0-471-88761-7
- GW Collins, II Metode numerice fundamentale și analiza datelor (1990)
- G. și A. Dahlquist Björck, Metode numerice în calculul științific (Prentice-Hall, 1991). Pagina web a lui A. Bjorck cu ediție nouă în format PDF
- David Kincaid, Ward Cheney (2002): Analiză numerică, ediția a III-a, Cap. 6, Brooks / Cole, ISBN 0-534-38905-8
- Michelle Schatzman (2002): Analiza numerică: o introducere matematică, cap.4 și cap.6, Oxford Clarendon Press, ISBN 0-19-850279-6
Elemente conexe
- 65-XX Secțiunea Matematicii Clasificarea subiectului dedicată analizei numerice
- Istoria analizei numerice
- Aritmetica afină
- Fortran
- Calcul paralel
Alte proiecte
-
Wikibooks conține texte sau analize numerice manuale
-
Wikționarul conține intrarea în dicționar „ analiză numerică ”
-
Wikimedia Commons conține imagini sau alte fișiere de analiză numerică
linkuri externe
- (EN) Analiză numerică pe Encyclopedia Britannica , Encyclopædia Britannica, Inc.
- Integratorul - calcul formal al primitivelor (Wolfram Research) , pe integrals.wolfram.com. Adus pe 2 martie 2007 (depus de 'url original 25 martie 2013).
- Server interactiv multifuncțional ( WIMS )
- P. Caressa Note despre analiza numerică
- C. GuerriniAnaliză numerică și planificare (Universitatea din Bologna)
- Baza de date SW calcul matematic pe swmath.org. Adus la 4 mai 2019 ( depus la 4 mai 2019).
Controlul autorității | Tezaur BNCF 1143 · LCCN (EN) sh85093237 · GND (DE) 4042805-9 · BNF (FR) cb11930888x (data) |
---|