estudi dels algorismes que utilitzen aproximació numèrica per resoldre problemes d'anàlisi matemàtica From Wikipedia, the free encyclopedia
L'anàlisi numèrica o càlcul numèric és la branca de les matemàtiques que s'encarrega de l'estudi i disseny d'algorismes per obtenir solucions numèriques aproximades als problemes de matemàtica contínua.
A diferència de la matemàtica discreta els problemes de matemàtica contínua, en general, no admeten una solució numèrica exacta. Per exemple, per expressar numèricament la longitud de la diagonal d'un quadrat que tingui una aresta de llargada unitat requeriria infinits nombres decimals. Per tant, en moltes aplicacions pràctiques, cal treballar amb una aproximació prou exacta.
Forma part de l'anàlisi numèrica l'estudi de l'eficiència dels algorismes que obtenen aquestes solucions aproximades i de la magnitud dels errors que es comenten. Tracta de determinar els mètodes per garantir que els errors estaran fitats dins de magnituds conegudes i acceptables per les aplicacions que els fan servir.
L'anàlisi numèrica precedeix la invenció dels ordinadors moderns en molts segles. La Interpolació lineal es feia servir fa més de 2000 anys. Molts grans matemàtics del passat es varen preocupar per l'anàlisi numèrica, com és obvi dels noms d'algorismes importants com mètode de Newton, interpolació polinòmica de Lagrange, mètode de reducció de Gauss, o mètode d'Euler.
Per facilitar els càlculs a mà, es produïen voluminosos llibres amb fórmules i taules de dades emprats com punts d'interpolació i coeficients de funcions. Utilitzant aquestes taules, sovint compilades per a 16 posicions decimals o més en algunes funcions, es podrien buscar valors per introduir a les fórmules donades i aconseguir molt bones estimacions numèriques d'algunes funcions. El treball clàssic en aquest camp és la publicació NIST editada per Abramowitz and Stegun, un llibre de més de 1000 pàgines amb un nombre molt gran de fórmules i funcions emprades habitualment i els seus valors a molts punts. Els valors de funció ja no són gaire útils quan es té un ordinador disponible, però la gran llista de fórmules encara pot ser molt pràctica.
La calculadora mecànica també es va desenvolupar com a eina per facilitar el càlcul manual. Aquestes calculadores evolucionaren a ordinadors electrònics durant els anys 1940, i es trobava llavors que aquests ordinadors eren també útils per a propòsits administratius. Però la invenció de l'ordinador també influïa al camp d'anàlisi numèrica, donat que ara es podrien fer càlculs més llargs i més complicats.
Mètodes directes vs mètodes iteratius Considereu el problema de resoldre
per a la quantitat desconeguda x.
Per al mètode iteratiu, aplicar el mètode de bisecció a f (x) = 3 x 3 - 24. Els valors inicials són a = 0, b = 3, f (a) = -24, f (b) = 57.
Es conclou a partir d'aquesta taula que la solució és entre 1.875 i 2.0625. L'algorisme podria tornar qualsevol nombre en aquest interval amb un error de menys de 0.2. Integració de Discretització i numèrica
Una discretització seria dir que la velocitat del cotxe era constant des de 0:00 a 0:40, llavors des de les 0:40 fins a 1:20 i finalment de 1:20 a 2:00. Per exemple, la distància total viatjada en els primers 40 minuts és aproximadament (2/3 h × 140 km/h)=93.3 km. Això permetria calcular la distància total viatjada com 93.3 km + 100 km + 120 km = 313.3 km, que és un exemple de integració numèrica (vegeu més avall) es fa servir un sumatori de Riemann, perquè el desplaçament és la integral de la velocitat. Problema mal condicionat: S'agafa la funció f (x) = 1/(x − 1). S'observa que f(1.1) = 10 i f(1.001) = 1000: un canvi en x de menys de 0.1 vegades porta a un canvi en f(x) de gairebé 1000. Avaluar f(x) prop de x = 1 és un problema mal condicionat. Problema ben condicionat: En canvi la funció és contínua i per tan avaluar-la és ben condicionat, com a mínim si x no està a la vora de zero. |
Els algorismes directes calculen la solució a un problema en un nombre finit de passos. Aquests mètodes donarien la resposta precisa si es realitzaven en aritmètica de precisió infinita. Exemples inclouen el mètode de reducció de Gauss, l'algorisme QR de factorització per resoldre sistemes d'equacions lineals, i el mètode símplex en programació lineal. A la pràctica, es fa servir precisió finita i el resultat és una aproximació de la veritable solució (suposant estabilitat numèrica).
Per per contrast als algorismes directes, els algorismes iteratius no pretenen acabar en un cert nombre de passos. Començant amb un valor inicial aproximat de la solució, els mètodes iteratius formen successives aproximacions que convergeixen a la solució exacta només en el límit. S'especifica un test de convergència per decidir quan s'ha trobat una solució suficientment acurada. Fins i tot fent servir aritmètica de precisió infinita, aquests mètodes (en general) no arribarien mai a la solució exacta en un nombre finit de passos. Els exemples inclouen el mètode de Newton, el mètode de bipartició i la iteració de Jacobi. En l'àlgebra de càlcul de matrius, en general els mètodes iteratius es necessiten per a problemes grans.
Els algorismes iteratius són més comuns que els directes en l'anàlisi numèrica. Alguns algorismes són directes en principi però s'utilitzen normalment com si no ho fossin, p. ex. GMRES i el mètode del gradient Conjugat. Per a aquests algorismes el nombre de passos necessitats per obtenir la solució exacta és tan gran que s'accepta una aproximació de la mateixa manera com es fa pels mètodes iteratius.
Els problemes continus s'han de substituir de vegades per un problema discret la solució del qual se sap que aproxima la del problema continu; aquest procés s'anomena discretització. Per exemple, la solució d'una equació diferencial és una funció. Aquesta funció s'ha de representar per una quantitat finita de dades, per exemple pel seu valor en un nombre finit de punts al seu domini, encara que aquest domini sigui continu en tingui infinits de punts.
Els errors d'arrodoniment sorgeixen perquè és impossible representar tots els nombres reals exactament en una màquina amb memòria finita (que és el que són tots els ordinador digitals pràctics).
Els errors de truncament es cometen quan s'acaba un mètode iteratiu o s'aproxima un procediment matemàtic, i la solució aproximada difereix de la solució exacta. De manera similar, la discretizació provoca un error de discretització perquè la solució del problema discret no coincideix amb la solució del problema continu. Per exemple, en la iteració de l'algorisme del costat per calcular la solució de , després de 10 iteracions aproximadament, es conclou que l'arrel és aproximadament 1,99 (per exemple). Per això es té un error de truncament de 0,01.
Finalment, un altre concepte paral·lel a l'anàlisi numèrica és el de la representació, tant dels nombres com d'altres conceptes matemàtics com els vectors, polinomis, etc. Per exemple, per a la representació en ordinadors de nombres reals, s'utilitza el concepte de coma flotant que dista molt de l'emprat per la matemàtica convencional.
El fet de representar els nombres reals emprant nombres de coma flotant s'ha de tenir en compte en el mateix disseny dels algorismes perquè en nombres de coma flotant no es compleixen les lleis clàssiques de l'aritmètica com per exemple la propietat associativa. Així, en general, (a + b) + c ≠ a + (b +c) perquè l'error d'arrodoniment depèn de la magnitud dels nombres que s'estan sumant. Per exemple si es fan servir nombres amb una única xifra de mantissa i una única xifra decimal:
(5,2 * 10² + 4 * 10-1) + 4 * 10-1 = (5,2 * 10²) + 4 * 10-1 = 5,2 * 10²
Perquè en fer cada suma dona 52 + 0,4 = 52,4 però en arrodonir queda 52.
Mentre que si es fa:
5,2 * 10² + (4 * 10-1 + 4 * 10-1) = 5,2 * 10² + (8 * 10-1) = 5,3 * 10²
Perquè en sumar 0,4 + 0,4 dona 0,8 i llavors en fer 52 + 0,8 dona 52,8 que s'arrodoneix a 53. En el primer cas l'error és de 0,8 mentre que en el segon és de 0,2 (quatre vegades més petit).
Una vegada que es genera un error, es propagarà generalment durant el càlcul. Per exemple en multiplicar un nombre per un factor l'error s'amplificarà o en restar dos nombres pot resultar que només quedi l'error. Per exemple si a representa la magnitud exacta i ε i δ representen errors:
k*(a + ε) = k*a + k*ε
(a + ε) - (a + δ) = ε - δ
En el cas que es restin dos nombres diferents el resultat no és que quedi només la diferència d'errors però el mòdul de la diferència dels verdaders valors pot fer-se molt petit mentre que els errors poden ser de signes contraris i augmentar. Llavors el pes relatiu de l'error augmenta. Aquest fenomen es coneix amb el nom de cancel·lació catastròfica.
A partir d'aquí, apareix un concepte addicional, el d'error. Definit l'error, juntament amb l'error admissible, es passa al concepte d'estabilitat dels algorismes. Moltes de les operacions matemàtiques es poden efectuar a través de la generació d'una sèrie de nombres que al seu torn alimenten de nou l'algorisme (feedback). Això proporciona una potència de càlcul i refinament molt important que a mesura que va completant un cicle va arribant a la solució. El problema passa a ser determinar fins quan haurà de continuar amb el cicle, o si fins i tot l'algorisme s'està allunyant de la solució del problema.
L'estabilitat numèrica és una idea important en l'anàlisi numèrica. Un algorisme s'anomena numèricament estable si un error, sigui quina sigui la seva causa, no creix gaire més durant el càlcul. Això passa si el problema és ben condicionat, el que significa que la solució canvia només en una quantitat petita si les dades de problema es canvien en una quantitat petita. En canvi, si un problema és mal condicionat, llavors qualsevol error petit en les dades acabarà per ser un error gran.
Tant el problema original com l'algorisme que es fa servir per resoldre aquell problema poden ser ben condicionats i/o mal condicionats, i qualsevol combinació és possible.
Així un algorisme que resol un problema ben condicionat pot ser o numèricament estable o numèricament inestable. Un art d'anàlisi numèrica és trobar un algorisme estable per resoldre un problema matemàtic ben condicionat. Per exemple, calcular l'arrel quadrada de 2 (que és aproximadament 1.41421) és un problema ben condicionat. Molts algorismes resolen aquest problema començant amb una aproximació inicial x1 a , per exemple x1=1.4, i llavors calculen aproximacions millorades x₂, x₃, etc. Un mètode d'aquest tipus és el famós mètode babilònic, que ve donat per xk+1 = xk/2 + 1/xk. Un altre mètode iteratiu, s'anomenarà mètode X, ve donat per xk + 1 = (xk²−2)² + xk.[3] S'han calculat unes quantes iteracions de cada mètode en forma de taula a davall, amb valors inicicials x1 = 1.4 i x1 = 1.42.
Mètode babilonic | Mètode babilonic | Mètode X | Mètode X |
---|---|---|---|
x1 = 1,4 | x1 = 1,42 | x1 = 1,4 | x1 = 1,42 |
x₂ = 1,4142857... | x₂ = 1,41422535... | x₂ = 1,4016 | x₂ = 1,42026896 |
x₃ = 1,414213564... | x₃ = 1,41421356242... | x₃ = 1,4028614... | x₃ = 1,42056... |
... | ... | ||
x1000000 = 1,41421... | x28 = 7280,2284... |
Observeu que el mètode babilònic convergeix de pressa independentment del valor de partida, mentre que el mètode X convergeix extremadament lent amb el valor de partida 1,4 i divergeix per al valor de partida 1,42. Per això, el mètode babilònic és numèricament estable, mentre que mètode X és numèricament inestable.
En general, aquests mètodes s'apliquen quan es necessita un valor numèric com a solució a un problema matemàtic, i els procediments "exactes" o "analítics" (manipulacions algebraiques, teoria d'equacions diferencials, mètodes d'integració, etc.) Són incapaços de donar una resposta. A causa d'això, són procediments d'ús freqüent per físics i enginyers, i el desenvolupament s'ha vist afavorit per la necessitat d'aquests d'obtenir solucions, encara que la precisió no sigui completa. Cal recordar que la física experimental, per exemple, mai dona valors exactes sinó intervals que engloben la gran majoria de resultats experimentals obtinguts, ja que no és habitual que dues mesures del mateix fenomen donin valors exactament iguals.
Un altre motiu que ha propiciat l'auge de l'anàlisi numèrica ha estat el desenvolupament dels ordinadors. L'augment extraordinari de la potència de càlcul ha convertit en possibles i en eficients algorismes que no seria factible realitzar a mà.
Els problemes d'aquesta disciplina es poden dividir en dos grups fonamentals:
Problemes de dimensió finita: aquells que la resposta són un conjunt finit de nombres, com les equacions algebraiques, els determinants, els problemes de valors propis, etc.
Problemes de dimensió infinita: problemes en els quals la solució o plantejament intervenen elements descrits per una quantitat infinita de nombres, com integració i derivació numèriques, càlcul d'equacions diferencials, interpolació, etc.
Així mateix, hi ha una subclassificació d'aquests dos grans apartats en tres categories de problemes, atesa la seva naturalesa o motivació per a emprar el càlcul numèric:
Interpolació: S'ha observat que la temperatura ha variat de 20º Celsius a la 1:00 fins a 14 graus a les 3:00. Una interpolació lineal d'aquestes dades conclouria que era de 17 graus a les 2:00 i 18.5 graus a la 1:30. Extrapolació: Si el producte interior brut d'un país ha estat creixent una mitjana d'un 5% per any i era de 100.000 milions d'euros el darrer any, es podria extrapolar que serà de 105.000 milions d'euros aquest any. Regressió: En la regressió lineal, donats n punts, es calcula una recta que passa tan a prop com sigui possible als n punts. Optimització: Suposant que es ven llimonada en una parada de llimonada, i s'observa que a 1 €, es pot vendre 197 gots de llimonada per dia, i que per a cada augment de 0,01 €, es vendrà un got menys de llimonada per dia. Si es pogués cobrar 1,485 €, es maximitzaria el benefici, però a causa de la restricció d'haver de cobrar un cèntim sencer, el preu de 1,49 € per got produirà els màxims ingressos de $220,52 per dia. Equació diferencial: Si s'engeguen 100 ventiladors bufant aire des d'un extrem de l'habitació cap a l'altre i llavors es deixa caure una ploma al vent, el que passa? La ploma seguirà els corrents d'aire, que poden ser molt complexos. Una aproximació és mesurar la velocitat a la que bufa el vent a prop de la ploma cada segon, i avançar la ploma simulada com si s'estigués movent en línia recta a aquella mateixa velocitat durant un segon, abans de mesurar la velocitat del vent una altra vegada. Això s'anomena el mètode d'Euler per resoldre una equació diferencial ordinària. |
L'anàlisi numèrica es divideix en diferents disciplines d'acord amb el problema a resoldre.
Un dels problemes més senzills és l'avaluació d'una funció en un punt donat. Per polinomis, un dels mètodes més utilitzats és l'algorisme de Horner, ja que redueix el nombre d'operacions a realitzar. En general, és important estimar i controlar els errors d'arrodoniment que es produeixen per l'ús de l'aritmètica de coma flotant.
La interpolació resol el problema següent: donat el valor d'una funció desconeguda en un nombre de punts, quin és el valor de la funció en un punt entre els punts donats? El mètode més senzill és la interpolació lineal, que assumeix que la funció desconeguda és lineal entre qualsevol parell de punts successius. Aquest mètode pot generalitzar-se a la interpolació polinòmica, que sol ser més precisa però que pateix l'anomenat fenomen de Runge. Altres mètodes d'interpolació fan servir un altre tipus de funcions interpoladors donant lloc a la interpolació mitjançant splines i a la interpolació trigonomètrica. Altres mètodes d'interpolació utilitzant derivades successives de la funció són mitjançant els polinomis de Taylor i l'aproximació de Padé.
L'extrapolació és molt similar a la interpolació, excepte que ara volem trobar el valor de la funció desconeguda en un punt que no està comprès entre els punts donats.
La regressió és també similar, però té en compte que les dades són imprecises. Donats alguns punts, i una mesura del valor de la funció en els mateixos (amb un error a causa de la mesura), volem determinar la funció desconeguda. El mètode dels mínims quadrats és una forma popular d'aconseguir-ho.
Un altre problema fonamental és calcular la solució d'una equació o sistema d'equacions donat. Es distingeixen dos casos depenent de si l'equació o sistema d'equacions és o no lineal. Per exemple, l'equació 2x + 5 = 3 és lineal mentre que l'equació 2x² + 5 = 3 no ho és.
Molt esforç s'ha posat en el desenvolupament de mètodes per a la resolució de sistemes d'equacions lineals. Mètodes directes, ie, mètodes que utilitzen alguna factorització de la matriu són el mètode d'eliminació de Gauss, la descomposició LU, la descomposició de Cholesky per matrius simètriques (o ermites) definides positives, i la descomposició QR. Mètodes iteratius com el mètode de Jacobi, el mètode de Gauss-Seidel, el mètode de les aproximacions successives i el mètode del gradient conjugat s'utilitzen freqüentment per a grans sistemes.
En la resolució numèrica d'equacions no lineals alguns dels mètodes més coneguts són els mètodes de bisecció, de la secant i el de regula falsi. Si la funció és a més derivable i la derivada es coneix, el mètode de Newton és molt utilitzat. Aquest mètode és un mètode d'iteració de punt fix. La linealització és una altra tècnica per a resoldre equacions no lineals.
Les equacions algebraiques polinomials posseeixen una gran quantitat de mètodes numèrics per enumerar:
Bastants problemes importants poden ser expressats en termes de descomposició espectral (el càlcul dels vectors i valors propis d'una matriu) o de descomposició en valors singulars. Per exemple, l'anàlisi de components principals utilitza la descomposició en vectors i valors propis.
Els problemes d'optimització busquen el punt per al qual una funció donada assoleix el seu màxim o mínim. Sovint, el punt també satisfà certa restricció. Exemples de problemes d'optimització són la programació lineal en què tant la funció objectiu com les restriccions són lineals. Un mètode famós de programació lineal és el mètode símplex. El mètode dels multiplicadors de Lagrange es pot utilitzar per reduir els problemes d'optimització amb restriccions a problemes sense restriccions.
La integració numèrica, també coneguda com a quadratura numèrica, busca calcular el valor d'una integral definida. Mètodes populars utilitzen alguna de les fórmules de Newton-Cotes (com la regla del rectangle o la regla de Simpson) o de quadratura gaussiana. Aquests mètodes es basen en una estratègia de "divideix i venceràs", dividint l'interval d'integració en subintervals i calculant la integral com la suma de les integrals en cada subinterval, i es podrà millorar posteriorment el valor de la integral obtingut mitjançant el mètode de Romberg. Per al càlcul d'integrals múltiples aquests mètodes requereixen massa esforç computacional, sent útil el mètode de Monte Carlo.
L'anàlisi numèric també pot calcular solucions aproximades d'equacions diferencials, bé equacions diferencials ordinàries, bé equacions en derivades parcials. Els mètodes utilitzats solen basar-se en discretitzar l'equació corresponent. És útil veure la derivació numèrica.
Per a la resolució d'equacions diferencials ordinàries els mètodes més utilitzats són el mètode d'Euler i els mètodes de Runge-Kutta.
Les equacions en derivades parcials es resolen primer discretitzar l'equació, portant-la a un subespai de dimensió finita. Això es pot fer mitjançant un mètode dels elements finits.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.