Analiza numerica

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Notă despre dezambiguizare.svg Dezambiguizare - "Aproximare numerică" se referă aici. Dacă sunteți în căutarea altor semnificații, consultați Aproximarea .

« Matematica ne învață să calculăm 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. "

( Giuseppe Peano , Prefață la volumul Tabelelor numerice )

Analiza numerică (numită și calcul numeric sau calcul științific ) este o ramură a matematicii aplicate care rezolvă modelele produse prin analiză matematică la descompunerile finite practicabile în mod normal, implicând conceptul de aproximare . Instrumentele sale, numite algoritmi , pot fi caracterizate pe baza vitezei de convergență , a stabilității numerice și a calculabilității .

Descriere

Majoritatea metodelor de soluție oferite de analiza numerică se bazează pe algebră liniară sau pe construcția de secvențe convergente de numere sau funcții la care se adaugă contribuțiile combinatoriei și geometriei și conexiunile cu metode probabilistice și fizico-matematice .

Unele probleme ale matematicii continue pot fi rezolvate cu algoritmi care rezolvă problema într-un număr finit, și posibil cunoscut a priori, de pași; aceste metode se numesc metode directe . Un exemplu tipic este dat de metoda de eliminare gaussiană 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 de la o încercare și găsește aproximări succesive care, sperăm, converg spre soluție.

De obicei, scriem problema formei x = F (x) și aplicăm teorema punctului fix . Un exemplu clasic de algoritm iterativ este metoda lui Newton pentru calcularea zerourilor 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 pentru toți: algoritmul FFT (Fast Fourier Transformation), care este unul dintre succesele analizei numerice, stă la baza algoritmilor reconstructivi de tomografie computerizată și imagini de rezonanță magnetică și rezolvarea problemelor multimedia , cum ar fi, printre cele mai important, compresia JPEG a imaginilor, compresia MP3 a muzicii, compresia mpeg a filmelor, eșantionarea și filtrarea 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, prognoza meteo , analiza moleculelor ( chimie de calcul ). Algoritmii de analiză numerică sunt, de asemenea, baza programelor CAE și aproape toate supercomputerele sunt ocupate în mod constant cu 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 empirice ale calculelor 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 s-au dedicat 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 publicația NIST editată de Abramowitz și Stegun , o carte de peste 1000 de pagini care conține un număr imens de formule și funcții utilizate în mod obișnuit și valorile lor în multe locuri. 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 calculatoare 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 simplă: algoritmul lui Horner este adesea mai eficient decât metoda banală. În general, atenția principală în rezolvarea acestor probleme vizează estimarea și controlul 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 anumite 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ă prin interpolare polinomială uneori mai precisă, dar care suferă de fenomenul Runge . Alte metode de interpolare utilizează funcții regulate în bucăți, cum ar fi 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 date sunt inexacte. Cea mai utilizată tehnică pentru regresie este metoda celor mai puțin 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. De exemplu, metoda de eliminare Gaussian și factorizarea LU aparțin acestei categorii. Metodele directe construiesc soluția exactă, până la erori de rotunjire, într-un număr finit de pași. Practic, ei folosesc 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 acționează pe matrice de coeficienți densi , dar pe sisteme mari și / sau cu matrice de coeficienți rare, acestea tind să fie prea scumpe î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. De exemplu, metoda Jacobi , metoda Gauss-Seidel și metoda gradientului conjugat aparțin metodelor iterative. 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, se folosesc algoritmi 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ă. Linearizarea este o altă tehnică pentru rezolvarea ecuațiilor neliniare.

Optimizare

Problemele de optimizare necesită găsirea punctului în care o anumită funcție își asumă valoarea maximă sau minimă. De multe ori punctul trebuie să satisfacă și unele 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 de constrângeri. De exemplu, programarea liniară tratează cazul în care atât funcția obiectivă, cât și constrângerile sunt liniare. Cel mai faimos algoritm de programare liniară este metoda simplex .

Metoda multiplicatorului Lagrange poate fi utilizată pentru a reduce problemele de optimizare constrânse la probleme de optimizare fără restricții.

Algoritmii de optimizare sunt în general testați folosind funcții de testare specifice, concepute pentru a le testa în probleme care prezintă dificultăți de calcul particulare.

Evaluarea integralelor

Pictogramă lupă mgx2.svg Același subiect în detaliu: Integrarea numerică .

Integrarea numerică, cunoscută și sub numele de cvadratură numerică, estimează valoarea unei integrale definite. Metodele populare folosesc unele formule Newton-Cotes , de exemplu regula punctului mediu sau regula trapezoidală sau cvadratura Gaussiană . Cu toate acestea, dacă dimensiunea domeniului de integrare devine mare, aceste metode devin costisitoare. În această situație, poate fi utilizată o metodă Monte Carlo , o metodă cvasi-Monte Carlo sau, pentru dimensiuni moderat mari, metoda grilajului rar .

Ecuațiile diferențiale

Analiza numerică este, de asemenea, interesată de calculul aproximativ al soluției ecuațiilor diferențiale , atât diferențiale ordinare, cât și parțiale . Ecuațiile diferențiale sunt rezolvate mai întâi prin discretizarea ecuației, adică aducând-o într-un sub-spațiu dimensional finit. Acest lucru se poate face cu o metodă cu element finit , o metodă cudiferență finită sau o metodă cu volum finit , utilizată în special în inginerie. Justificarea teoretică a acestor metode implică adesea teoreme de analiză funcțională . 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:

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 de aproximare nu trebuie să crească necontrolat pe măsură ce mărimea 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:

O eroare, odată ce a fost generată, se propagă în general prin calcul. Acest lucru duce la conceptul de stabilitate numerică : se spune că un algoritm este 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. Se spune că o problemă care nu este condiționată prost este 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

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:

Notă

  1. ^ Valeriano Comincioli, Metode numerice și statistice pentru științele aplicate , CEA Casa Editrice Ambrosiana, 1992, ISBN 88-408-0757-8
  2. ^ Giovanni Monegato, Elements of Numerical Computing , Ed. Levrotto & Bella, Torino 1995, ISBN 978-88-8218-017-1 , pp. III-2, III-3

Bibliografie

Lucrări introductive

  • R. Bevilacqua, D. Bini, M. Capovani , O. Menchi (1987): Introduction to Computational Mathematics , Zanichelli, 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 ; nouă ediție a cărții electronice APOGEO, Feltrinelli Milano, 2005 http://www.apogeonline.com/libri/88-503-1031-5/scheda
  • Giovanni Monegato (1990): Fundamente de calcul 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

(este disponibilă și o versiune mai mare în limba engleză) ISBN 88-470-0077-7

  • G. Naldi, L. Pareschi, G. Russo (2001, 2004 II ed.): Introducere în calculul științific , McGraw-Hill, ISBN 88-386-0885-7
  • ( EN ) Endre Süli și David Mayers, An Introduction to Numerical Analysis , Cambridge, Cambridge University Press, 2003, ISBN 978-0-521-00794-8 .

Lucrări de referință

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 , O. Menchi (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

Elemente conexe

Alte proiecte

linkuri externe

Controlul autorității Tezaur BNCF 1143 · LCCN (EN) sh85093237 · GND (DE) 4042805-9 · BNF (FR) cb11930888x (data)
Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică