Anàlisis numèric

Archiu:Ybc7289-bw.jpg

Tablilla d'argila babilònica YBC 7289 (c. 1800-1600 aC) en anotacions. L'aproximació de la raïl quadrada de 2 són quatre sifres sexagesimals, que són aproximadament sis sifres decimals: 1 + 24/60 + 51/60² + 10/60³ = 1.41421296...

El anàlisis numèric o càlcul numèric és la branca de les matemàtiques encarregada de dissenyar algoritmes per a simular aproximacions de solució a problemes en anàlisis matemàtic. Es distinguix del còmput simbòlic en que no manipula expressions algebraiques, sino números.

L'anàlisis numèric cobra especial importància en l'arribada dels ordenadors. Els ordenadorés són útils per a càlculs matemàtics extremadament complexos, pero en última instància operen en número binario i operacions matemàtiques simples.

Des d'este punt de vista, l'anàlisis numèric proporcionarà tot el andamiaje necessari per a portar a terme tots aquells procediments matemàtics susceptibles d'expressar-se algorítmicament, basant-se en algoritmes que permeten la seua simulació o càlcul en processos més senzills amprant números.

Definit l'error, junt en l'error admissible, passem al concepte d'estabilitat dels algoritmes. Moltes de les operacions matemàtiques poden dur-se alvance a través de la generació d'una série de números que a la seua volta alimenten de nou l'algoritme (feedback). Açò proporciona un poder de càlcul i refinament importantíssim a la màquina que a mida que va completant un cicle va aplegant a la solució. El problema ocorre en determinar fins a quàn deurà continuar en el cicle, o si nos estem alluntant de la solució del problema.

Finalment, un atre concepte paralel a l'anàlisis numèric és el de la representació, tant dels números com d'atres conceptes matemàtics com els vectorés, polinomis, etc. Per eixemple, per a la representació en ordenadors de número real, s'ampra el concepte de menge flotant que dista molt de l'empleat per la matemàtica convencional.

En general, estos métodos 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étodos d'integració, etc.) són incapaces de donar una resposta. Debido a ello, són procediments d'us freqüent per físics i ingeniers, i el desenroll dels quals s'ha vist favorit per la necessitat d'estos d'obtindre solucions, encara que la precisió no siga completa. Deu recordar-se que la física experimental, per eixemple, mai tira valors exactes sino intervals que engloben la gran majoria de resultats experimentals obtinguts, ya que no és habitual que dos mides del mateix fenomen tiren valors exactament iguals.

Per eixemple, les equacions diferencials ordinàries apareixen en la mecànica celest per a la predicció dels moviments de planetes, estreles i galàxies; l'àlgebra llineal numèrica és important per al anàlisis de senyes; Les equacions diferencials estocàstiques i les cadenes de Markovs són essencials en la simulació de cèlules vives per a la medicina i la biologia.

Abans de l'arribada dels ordenadors moderns, els métodos numèrics depenien a sovint de fòrmules d'interpolació manuals aplicades a les senyes de grans taules impreses. Des de mediats de el XX, els ordenadors calculen les funcions necessàries en el seu lloc, pero moltes de les mateixes fòrmules seguixen utilisant-se, no obstant, com a part dels algoritmes del software.

El punt de vista numèric es remonta als primers escrits matemàtics. Una tablilla de la Colecció Babilònica de Yale (YBC 7289), dona una aproximació numèrica sexagesimal de la raïl quadrada de 2, la llongitut de la diagonal en un quadrat unitari.

L'anàlisis numèric continua esta llarga tradició: en lloc de respostes simbòliques exactes, que solament poden aplicar-se a les medicions del món real per mig de la traducció a dígits, dona solucions aproximades dins de llímits d'error especificats.

Introducció general

L'objectiu general del camp de l'anàlisis numèric és el disseny i anàlisis de tècniques per a donar solucions aproximades pero precises a problemes difícils, la varietat dels quals se sugerix en lo següent:

• Els métodos numèrics alvançats són essencials per a fer viable la predicció numèrica del temps.
• El càlcul de la trayectòria d'una nau espacial requerix la solució numèrica precisa d'un sistema d'equacions diferencials ordinàries.
• Les empreses automovilístiques poden millorar la seguritat dels seus vehículs per mig de simulacions per ordenador d'accidents de tràfic. Estes simulacions consistixen essencialment en la resolució numèrica d'equacions diferencials parcials.
• Els fondos de cobertura (fondos d'inversió privats) utilisen ferramentes de tots els camps de l'anàlisis numèric per a intentar calcular el valor de les accions i els derivats en major precisió que atres participants en el mercat.
• Les aerollínies utilisen sofisticats algoritmes d'optimisació per a decidir el preu dels billets, l'assignació d'avions i tripulacions i les necessitats de combustible. Històricament, estos algoritmes s'han desenrollat en el camp de l'investigació operativa.
• Les companyies de segurs utilisen programes numèrics per a l'anàlisis actuarial.

El restant d'esta secció esbossa varis temes importants de l'anàlisis numèric.

Història

El camp de l'anàlisis numèric és anterior a l'invenció dels ordenadors moderns en molts sigles. l'interpolació llineal ya s'utilisava fa més de 2000 anys. Molts grans matemàtics del passat es varen preocupar per l'anàlisis numèric, com es desprén dels noms d'importants algoritmes com el método de Newton, el polinomi d'interpolació de Lagrange, l'eliminació gaussiana o el método de Euler.

Per a facilitar els càlculs a mà, es varen produir grans llibres en fòrmules i taules de senyes com els punts d'interpolació i els coeficients de les funcions. En estes taules, a sovint calculades en 16 decimals o més per a algunes funcions, es podien buscar valors per a introduir-los en les fòrmules donades i conseguir molt bones estimacions numèriques d'algunes funcions. El treball canònic en este camp és la publicació del NIST editada per Abramowitz i Stegun, un llibre de més de 1000 pàgines en un gran número de fòrmules i funcions d'us comú i els seus valors en molts punts. Els valors de les funcions ya no són molt útils quan es dispon d'un ordenador, pero el gran llistat de fòrmules pot seguir sent molt útil.

La calculadora mecànica també es va desenrollar com a ferramenta de càlcul manual. Estes calculadores varen evolucionar fins a convertir-se en ordenadors electrònics en la década de 1940, i llavors es va descobrir que estos ordenadors també eren útils per a fins administratius. Pero l'invenció de l'ordenador també va influir en el camp de l'anàlisis numèric, ya que ara es podien fer càlculs més llarcs i complicats.

Métodos directes i iterativos

Considerem el problema de resoldre

3x³ + 4 = 28

per a la cantitat desconeguda x.

Método directe

	3x3 + 4 = 28.
Restar 4	3x3 = 24.
Dividir per 3	x3 =  8.
Fer la raïl cúbica	x =  2.

Per al método iterativo, apliquem el método de bisecció a f(x) = 3x³ − 24. Els valors inicials són: a = 0, b = 3, f(a) = −24, f(b) = 57.

Método iterativo

a	b	mid	f(mid)
0	3	1.5	−13.875
1.5	3	2.25	10.17...
1.5	2.25	1.875	−4.22...
1.875	2.25	2.0625	2.32...

D'esta taula es pot concloure que la solució està entre 1,875 i 2,0625. L'algoritme podria tornar qualsevol número en eixe ranc en un error inferior a 0,2.

Discretización i integració numèrica

Archiu:Schumacher (Ferrari) in practice at caps block 19 2005.jpg

En una carrera de dos hores, la velocitat del coche es medix en tres instants i es registra en la següent taula:

Temps	0:20	1:00	1:40
km/h	140	150	180

Una discretización seria dir que la velocitat del coche va ser constant de 0:00 a 0:40, després de 0:40 a 1:20 i finalment d'1:20 a 2:00. Per eixemple, la distància total recorreguda en els primers 40 minuts és aproximadament (2/3 h × 140 km / h) = 93,3 quilómetros. Açò nos permetria estimar la distància total recorreguda com 93,3 quilómetros +100 km +120 km =313,3 km, que és un eixemple de integració numèrica (vore més alvance) utilisant una sumixca de Riemann, perque el desplaçament és l'integral de la velocitat.

Problema mal condicionat: Prenga's la funció f(x) = 1/(x − 1). Tinga's en conte que un canvi en x de menys de 0.1 es convertix en un canvi en f(1.1) = 10 i f(1.001) = 1000, de casi 1000. Evaluar f (x) prop de x = 1 és un problema mal condicionat.

Problema ben condicionat: pel contrari, evaluar la mateixa funció f(x) = 1/(x − 1) prop de x = 10 és un problema ben condicionat. Per eixemple, f(10) = 1/9 ≈ 0.111 i f(11) = 0.1, per lo que un canvi modest en x conduïx a un canvi modest en f (x).

Els métodos directes calculen la solució d'un problema en un número finito de passos. Estos métodos donarien la resposta precisa si es realisaren en aritmètica de precisió infinita. Alguns eixemples són l'eliminació gaussiana, el método de factorización QR per a resoldre sistemes d'equacions llineals, i el método simplex de programació llineal. En la pràctica, s'utilisa precisió finita i el resultat és una aproximació de la solució verdadera (assumint estabilitat).

A diferència dels métodos directes, no s'espera que els métodos iterativos terminen en un número finito de passos. Partint d'una conjectura inicial, els métodos iterativos formen aproximacions successives que convergixen a la solució exacta solament en el llímit. S'especifica una prova de convergència, que a sovint implica el residu, per a decidir quàn s'ha trobat (en sòrt) una solució suficientment exacta. Inclús utilisant aritmètica de precisió infinita, estos métodos no alcançarien, en general, la solució en un número finito de passos. Alguns eixemples són el método de Newton, el método de bisecció i el método de Jacobi. En l'àlgebra matricial computacional, els métodos iterativos són generalment necessaris per a problemes grans.

Els métodos iterativos són més comuns que els métodos directes en l'anàlisis numèric. Alguns métodos són directes en principi, pero solen utilisar-se com si no ho anaren, per eixemple, el GMRES i el método del gradient conjugat. Per a estos métodos el número de passos necessaris per a obtindre la solució exacta és tan gran que s'accepta una aproximació de la mateixa manera que per a un método iterativo.

Problemes

Els problemes d'esta disciplina es poden dividir en dos grups fonamentals:

• Problemes de dimensió finita: aquells la resposta dels quals són un conjunt finito de números, com les equacions algebraiques, els determinants, els problemes de valors propis, etc.

• Problemes de dimensió infinita: problemes en la solució dels quals o plantejament intervenen elements descrits per una cantitat infinita de números, com a integració i derivació numèriques, càlcul d'equacions diferencials, interpolació, etc.

Classificació atenent a la seua naturalea o motivació

Aixina mateix, existix una subclasificación d'estos dos grans apartats en tres categories de problemes, atenent a la seua naturalea o motivació per a l'ocupació del càlcul numèric:

• Problemes de tal complexitat que no posseïxen solució analítica.
• Problemes en els quals existix una solució analítica, pero esta, per complexitat o atres motius, no pot explotar-se de forma senzilla en la pràctica.
• Problemes per als quals existixen métodos senzills pero que, per a elements que s'ampren en la pràctica, requerixen una cantitat de càlculs excessiva; major que la necessària per a un método numèric.

Àrees d'estudi

L'anàlisis numèric es dividix en diferents disciplines d'acort en el problema que resoldre.

Càlcul dels valors d'una funció

Un dels problemes més senzills és l'evaluació d'una funció en un punt donat. Per a polinomis, un dels métodos més utilisats és l'algoritme de Horner, ya que reduïx el número d'operacions a realisar. En general, és important estimar i controlar els errors de grosseig que es produïxen per l'us de l'aritmètica de punt flotant.

l'extrapolació és molt similar a l'interpolació, excepto 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, pero té en conte que les senyes són imprecises. Donats alguns punts, i una mida del valor de la funció en els mateixos (en un error per la medició), volem determinar la funció desconeguda. El método dels mínims quadrats és una forma popular de conseguir-ho.

Resolució d'equacions i sistemes d'equacions

Un atre problema fonamental és calcular la solució d'una equació o sistema d'equacions donat. Es distinguixen dos casos depenent de si l'equació o sistema d'equacions és o no llineal. Per eixemple, l'equació $2x+5=3$ és llineal mentres que l'equació de segon grau $2x^2+5=3$ no ho és.

Molt esforç s'ha posat en el desenroll de métodos per a la resolució de sistemes d'equacions llineals. Métodos directes, i.i., métodos que utilisen alguna factorización de la matriu són el método d'eliminació de Gauss, la descomposició LU, la descomposició de Cholesky per a matrius simètriques (o hermíticas) definides positives, i la descomposició QR. Métodos iterativos com el método de Jacobi, el método de Gauss-Seidel, el método de les aproximacions successives i el método del gradient conjugat s'utilisen freqüentment per a grans sistemes.

En la resolució numèrica d'equacions no llineals alguns dels métodos més coneguts són els métodos de bisecció, de la secante i de la falsa posició. Si la funció és ademés derivable i la derivada es coneix, el método de Newton és molt utilisat. Este método és un método de iteración de punt fix. La linealización és una atra tècnica per a resoldre equacions no llineals.

Les equacions algebraiques polinomiales posseïxen una gran cantitat de métodos numèrics per a enumerar :

• Método de Gräeffe (o método de Lobachevsky o de Lobachevsky-Dandelin-Gräeffe o del quadrat de les raïls)

• Método de Laguerre

• Método de Bairstow (o método de Lin-Bairstow)

• Método de Bernoulli

• Método de Horner

• Método de Householder

• Método de Newton-Raphson especialisat per a polinomis

• Método de Richmond especialisat per a polinomis

• Método modificat de Richmond

• Método de Newton-Horner

• Método de Richmond-Horner

• Método de Birge-Biète

• Método de Jenkins-Traub

Descomposició espectral i en valors singulars

Prou problemes importants poden ser expressats en térmens de descomposició espectral (el càlcul dels vectores i valors propis d'una matriu) o de descomposició en valors singulars. Per eixemple, l'anàlisis de components principals utilisa la descomposició en vectores i valors propis.

Optimisació

Artícul principal → Optimisació (matemàtica).

Els problemes d'optimisació busquen el punt per al qual una funció donada alcança el seu màxim o mínim. A sovint, el punt també satisfà certa restricció.

Eixemples de, problemes d'optimisació són la programació llineal en que tant la funció objectiu com les restriccions són llineals. Un método famós de programació llineal és el método simplex.

El método dels multiplicadors de Lagrange pot usar-se per a reduir els problemes d'optimisació en restriccions a problemes sense restriccions.

Evaluació d'integrals

Artícul principal → Integració numèrica.

l'integració numèrica, també coneguda com a quadratura numèrica, busca calcular el valor d'una integral definida. Métodos populars utilisen alguna de les fòrmules de Newton-Cotes (com la regla del rectàngul o la regla de Simpson) o de quadratura gaussiana. Estos métodos es basen en una estratègia de «dividix i venceràs», dividint l'interval d'integració en subintervalos i calculant l'integral com la suma de les integrals en cada subintervalo, podent-se millorar posteriorment el valor de l'integral obtingut per mig del método de Romberg. Per al càlcul d'integrals múltiples estos métodos requerixen massa esforç computacional, sent útil el método de Mont Carlo.

Equacions diferencials

L'anàlisis numèric també pot calcular solucions aproximades d'equacions diferencials, ben equacions diferencials ordinàries, ben equacions en derivades parcials. Els métodos utilisats solen basar-se en discretizar l'equació corresponent. És útil vore la derivació numèrica.

Per a la resolució d'equacions diferencials ordinàries els métodos més utilisats són el método de Euler i els métodos de Runge-Kutta.

Les equacions en derivades parcials es resolen primer discretizando l'equació, duent-la a un subespacio de dimensió finita. Açò pot fer-se per mig d'un método dels elements finitos.

Fonts d'error i el seu impacte

Els algoritmes dels métodos numèrics solen implementar-se per mig de computadores. Estes posseïxen algunes propietats que causen falles en amprar-les per a trobar la solució numèrica de problemes matemàtics, entre les que es troben les següents:

1. Les computadores són capaces d'almagasenar un número finito de dígits, per lo que no poden almagasenar el conjunt dels número real en la seua totalitat per a realisar operacions numèriques en estos. En canvi, conten en un subconjunt dels número real al com es coneix com a números de punt flotant o números de màquina. A l'error al que comporta esta limitante se li crida error de grosseig.
2. Existixen problemes que involucren molts càlculs per a la seua solució. En ocasions, les solucions són sensibles a la precisió dels càlculs intermijos, en el cas dels quals es diu que les solucions poden haver segut pertorbades per les senyes.
3. A major número d'operacions realisades es tindrà un error de grosseig major. La velocitat que proveïxen les computadores per al processament ha agilitat significativament la rapidea en la que es calculen operacions. No obstant, la propagació d'errors de grosseig pels càlculs realisats per computadores pot derivar en l'inestabilitat dels resultats tirats pels algoritmes programats en elles.

Les falles en els càlculs intermijos realisats per una computadora per a tirar un resultat final són, en freqüència, desconeguts per als programadors i molt difícils de detectar: la suma i el producte de números de punt flotant són operacions conmutativas, pero no són associatives i tampoc distributivas. Al no verificar estes dos propietats dels número real, el maneig de les operacions realisades en números de punt flotant resulta una tasca complicada. Per una atra part, l'orde de les operacions pot incidir en la precisió dels resultats tornats per la màquina, puix dos expressions equivalents en un sentit algebraic poden donar resultats distints en el context dels números de màquina.

Afortunadament, existixen algunes tècniques per a previndre i atacar l'error de grosseig. En es discutixen algunes de les implicacions d'estes estratègies per a les operacions bàsiques de suma, resta, multiplicació i divisió. També en es discutixen alguns estàndarts de punt flotant de la IEEE i les conexions entre el punt flotant i el disseny de sistemes computacionals.

El mejoramiento en la precisió dels números de punt flotant seguix sent motiu d'estudi en els nostres dies. En 2015, investigadors de l'Universitat de Washington varen desenrollar una ferramenta computacional a la que varen cridar Herbie i que «detecta automàticament les transformacions necessàries per a que un programa millore la seua precisió». Herbie evalua l'error d'una expressió de punt flotant i identifica quines operacions contribuïxen de forma més significativa a l'acumulació d'errors, després genera alternatives per a realisar estes operacions i fa un comparatiu per a finalment determinar l'expressió equivalent òptima (aquella que minimisa l'error) per a corregir el programa.

L'interés en assegurar cert nivell de precisió en els resultats numèrics proveïts una computadora es deu a les seues possibles repercussions en la pràctica. Per eixemple, en l'àmbit acadèmic s'han donat casos d'artículs d'investigació en els que l'error de grosseig ha impedit que els resultats siguen reproduibles i, en ocasions, est ha segut inclús motiu de rebuig per a la seua publicació ( i). Este tipo d'error també ha permeado la regulació llegal financera d'alguns països i distorsionat índexs del mercat bossístic.

La limitante en la representació d'número real per mig del punt flotant també té repercussions en les gràfiques generades per mig d'una computadora. Quan un número és menor a lo que es coneix com l'épsilon de màquina, la computadora és incapaç de representar-ho. Açò pot fer que les gràfiques associades a valors numèrics menors al épsilon presenten falsos comportaments i afectar la presa de decisions basades en elles, en conseqüències insospitades, per eixemple, en realisar pronòstics, àrea en la que la precisió juga un paper crucial.

Existixen atres tipos d'error en el context dels métodos numèrics que mereixen igual atenció i conte. Errors de truncació i de conversió, entre uns atres, han donat orige a múltiples catàstrofe: la falla del missil Patriot, l'explosió de l'eixida Ariane 5 inaugural, l'afonament de la plataforma petrolera Sleipner són solament alguns eixemples d'això. D'ahí l'importància de reconéixer estes fonts d'error per a anticipar-se a elles i, en el seu cas, detectar-les i corregir-les.

Atres temes d'anàlisis numèric

• Error d'aproximació, error absolut i error relatiu
• Orde de convergència
• Grosseig
• Sistema de numeració
• Truncació

Bibliografia

• (1986) Matrix Computations, 3rd edició, Johns Hopkins University Press. ISBN 0-8018-5413-X.
• Higham, Nicholas J. (1996). Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics. ISBN 0-89871-355-2.
• Hildebrand, F. B. (1974). Introduction to Numerical Analysis, 2nd edició, McGraw-Hill. ISBN 0-07-028761-9.
• Leader, Jeffery J. (2004). Numerical Analysis and Scientific Computation, Addison Wesley. ISBN 0-201-73499-0.
• Wilkinson, J.H. (1965). The Algebraic Eigenvalue Problem, Clarendon Press.
• (examples of the importance of accurate arithmetic).
• Trefethen, Lloyd N. (2006). "Numerical analysis", 20 pages. In: Timothy Gowers and June Barrow-Green (editors), Princeton Companion of Mathematics, Princeton University Press.

Enllaços externs

Commons

• Wikimedia Commons alberga contingut multimèdia sobre Anàlisis numèric.

En espanyol

• Artícul sobre anàlisis numèric en la Enciclopèdia lliure universal en espanyol
• http://docencia.udea.edu.co/ingenieria/analisis-numerico/
• http://mat21.etsii.upm.es/matesp/index.htm [1] archivat en Wayback Machine.
• Grup de métodos numèrics en ingenieria (ETS Ingeniers de Camins de l'Universitat de La Corunya)

• Notes sobre métodos numèrics bàsics per a ingenieria [2] archivat en Wayback Machine.

En anglés

• wikibooks:Numerical Methods
• Numerical analysis DMOZ category
• Numerical Recipes Homepage - with free, complete downloadable books
• Numerical Analysis Project by John H. Mathews
• Alternatives to Numerical Recipes
• The definition of numerical analysis

Publicacions

• gdz.sub.uni-goettingen, Numerische Mathematik, volumes 1-66, Springer, 1959-1994 (searchable; pages llaure images).
• Numerische Mathematik, volumes 1–112, Springer, 1959–2009
• Journal on Numerical Analysis, volumes 1-47, SIAM, 1964–2009

Texts on-line

• Plantilla:Springer
• Numerical Recipes, William H. Press (free, downloadable previous editions)
• First Steps in Numerical Analysis (archived), R.J.Hosking, S.Joe, D.C.Joyce, and J.C.Turner
• CSEP (Computational Science Education Project), U.S. Department of Energy (archived 2017-08-01)
• Numerical Methods, ch 3. in the Digital Library of Mathematical Functions

Material del cursos on-line

• Numerical Methods [3] archivat en Wayback Machine., Stuart Dalziel University of Cambridge
• Lectures on Numerical Analysis, Dennis Deturck and Herbert S. Wilf University of Pennsylvania
• Numerical methods, John D. Fenton University of Karlsruhe
• Numerical Methods for Physicists, Anthony O’Hare Oxford University
• Lectures in Numerical Analysis (archived), R. Radok Mahidol University
• Introduction to Numerical Analysis for Engineering, Henrik Schmidt Massachusetts Institute of Technology
• Numerical Analysis for Engineering, D. W. Harder University of Waterloo