Integraci?? num??rica

De Viquip??dia

En c??lcul, l'integraci?? num??rica consisteix en una fam??lia d'algorismes per a calcular el valor num??ric d'una integral definida, per extensi??, el terme de vegades es fa servir tamb?? per a descriure la soluci?? num??rica d'equacions diferencials ordin??ries. Aquest article se centra en el c??lcul d'integrals definides. El terme quadratura num??rica (sovint abreviat a quadratura) ??s m??s o menys sin??nim d'integraci?? num??rica, especialment si s'aplica a integrals d'una dimensi?? tot i que pel cas de dues o m??s dimensions (integral m??ltiple) tamb?? es fa servir.

El problema b??sic al que s'adre??a la integraci?? num??rica ??s del de calcular una soluci?? aproximada a una integral definida.

$\int_a^b\! f(x)\, dx.$

Si f(x) ??s una funci?? cont??nuament derivable sobre un nombre petit de dimensions i els l??mits d'integraci?? s??n afitats, llavors hi ha molts m??todes excel??lents per a aproximar l'integral amb una precisi?? arbitr??ria.

Integraci?? num??rica emprant el m??tode de Monte Carlo: Els nodes es distribueixen emprant una distribuci?? de probabilitat uniforme. Als nodes nou s??n blau mar??, els vell blau cel. El valor de la integral tendeix cap a 3,32

Taula de continguts

1 Motius per a la integraci?? num??rica
2 M??todes per a integrals d'una dimensi??
3 Integrals m??ltiples
- 3.1 Montecarlo
- 3.2 Graelles disperses
4 Conexi?? amb les equacions diferencials
5 Software per a integraci?? num??rica
6 Refer??ncies
7 Enlla??os externs

[edita] Motius per a la integraci?? num??rica

Hi ha molts motius per a emprar la integraci?? num??rica. Pot ser que l'integrand f(x) nom??s sigui conegut a determinats punts, per exemple obtinguts per mostreig. Alguns sistemes integrats i altres aplicacions inform??tiques pot ser que necessitin integraci?? num??rica per aquest motiu.

Pot ser que es conegui la f??rmula de l'integrand, per?? pot ser que sigui dif??cil o impossible de trobar una primitiva que sigui una funci?? elemental. Un exemple d'aix?? ??s f(x) = exp(???x²), la primitiva de la qual no es pot escriure de forma elemental.

De vegades ??s possible trobar la primitiva simb??licament, per?? pot ser m??s f??cil de calcular la integral num??ricament que calcular els valors de la primitiva. Aquest pot ser el cas per exemple si la primitiva ve donada per una s??rie o un producte infinits, o si la seva avaluaci?? requereix una funci?? especial l'algorisme per avaluar la qual no es t?? disponible.

[edita] M??todes per a integrals d'una dimensi??

Els m??todes d'integraci?? num??rica troben un valor aproximat de la integral definida. Amb un error que ??s la difer??ncia entre el valor que donen i el valor exacte.

Les difer??ncies entre els diferents m??todes es basen principalment en la forma de trobar la aproximaci?? de la integral i en alguns cassos la forma d'anar afinant el c??lcul per a redu??r l'error estimat.

Una part important de l'an??lisi de la integraci?? num??rica ??s l'estudi del comportament de la aproximaci?? de l'error com a funci?? del nombre d'avaluacions de la funci?? integrand.

Val a dir que el problema nom??s t?? inter??s si no ??s possible con??ixer amb exactitud el valor de l'error. L'error per definici?? ??s la difer??ncia entre el valor aproximat i el valor exacte. En els cassos on es pot con??ixer l'error, n'hi ha prou amb afegir-lo al valor aproximat per a obtenir el valor exacte. Per?? en aquests cassos no cal una integraci?? num??rica. Per tant els m??todes treballen o b?? amb fites superiors de l'error o b?? amb valors estimats de l'error.

Entre dos m??todes que tenen el mateix error, es considera superior el que necessita un nombre inferior d'avaluacions de la funci??.

El fet de reduir el nombre d'avaluacions de la funci?? integrand redueix el nombre d'operacions aritm??tiques implicades. Aix?? redueix el temps de c??lcul. En els cassos en que els c??lculs es fan amb operacions de coma flotant (que s??n la majoria) el fet de reduir el nombre d'operacions tamb?? redueix l'error d'arrodoniment total.

La integraci?? num??rica per la 'for??a bruta' es pot fer, si la funci?? integrand t?? un comportament raonablement bo (per exemple ??s cont??nua), a base d'avaluar l'integrand amb increments molt petits.

[edita] M??todes basats en funcions d'interpolaci??

Hi ha una extensa fam??lia de m??todes que es basen en aproximar la funci?? a integrar $f (x)$ per un altre funci?? $g (x)$ de la qual es coneix l'integral exacta. La funci?? que substitueix l'original es troba de forma que, en un cert nombre de punts tingui el mateix valor que l'original. Com que els punts extrems formen part sempre d'aquest conjunt de punts, de la nova funci?? se'n diu una interpolaci?? de la funci?? original. (quant els punts extrems no es fan servir per trobar la funci?? que substitueix la original llavors se'n diu extrapolaci??). T??picament aquestes funcions s??n polinomis.

Il??lustraci?? del m??tode rectangular.

El m??tode m??s senzill d'aquesta classe ??s el de fer que la funci?? d'interpolaci?? sigui una funci?? constant (un polinomi de grau zero) que passa pel punt ((a+b)/2, f((a+b)/2)). D'aquest m??tode se'n diu el m??tode del punt mig o el m??tode rectangular.

$\begin{align} & g(x)=f\left( \frac{a+b}{2} \right) \\ & \int_{a}^{b}{f\left( x \right)dx\approx }\int_{a}^{b}{g\left( x \right)dx=\left( b-a \right)}f\left( \frac{a+b}{2} \right) \\ \end{align}$

Il??lustraci?? del m??tode trapezial.

La funci?? d'interpolaci?? pot ser tamb?? una funci?? af?? (un polinomi de grau 1) Que passa pels punts extrems (a, f(a)) and (b, f(b)).

D'aquest m??tode se'n diu el m??tode trapezial.

$g(x)=f(a)+\frac{f(b)-f(a)}{b-a}(x-a)$

$\int_a^b f(x)\,dx \approx (b-a) \, \frac{f(a) + f(b)}{2}.$

Il??lustraci?? del m??tode de Simpson.

Per a cada un d'aquests m??todes, es pot aconseguir una aproximaci?? m??s exacta a base de trencar l'interval [a, b] en n subintervals, calculant una aproximaci?? per cada un dels subintervals, i despr??s sumant tos els resultats (si l'amplada del interval ??s constant es pot treure factor com?? de l'amplada de l'interval i multiplicar al final, d'aquesta forma es redueix el nombre d'operacions). D'aix?? se'n diu un m??tode compost, m??tode estes, or m??tode iterat. Per exemple, el m??tode trapezial compost es pot establir com

$\int_a^b f(x)\,dx \approx \frac{b-a}{n} \left( {f(a) + f(b) \over 2} + \sum_{k=1}^{n-1} f \left( a+k \frac{b-a}{n} \right) \right)$

On els subintervals tenen la forma [k h, (k+1) h], amb h = (b???a)/n i k = 0, 1, 2, ..., n???1.

L'interpolaci?? amb polinomis avaluats a punts equidistants en [a, b] porten a les f??rmules de Newton-Cotes, de les quals les regles rectangular i trapezial en s??n exemples. EL m??tode de Simpson, que es basa en polinomis de segon grau ??s tamb?? una f??rmula de Newton-Cotes.

Els m??todes de quadratura que utilitzen punts equidistants tenen la propietat molt convenient de que al subdividir els intervals el nou conjunt de punts cont?? l'anterior, d'aquesta forma els valors de la funci?? integrand es poden reutilitzar (no cal tornar-los a calcular).

Si es permet que els intervals entre punts d'interpolaci?? vari??n, es troba una altre grup de f??rmules de quadratura, com les f??rmules de quadratura de Gauss. Una quadratura de Gauss ??s normalment m??s exacta que una de Newton-Cotes amb la mateixa quantitat d'avaluacions de la funci??, si l'integrand ??s suau (es a dir ??s derivable molts cops). Altres m??todes de quadratura amb intervals variables inclouen la quadratura de Clenshaw-Curtis i els m??todes de quadratura de Fej??r.

Els punts de la quadratura de Gauss no s??n reutilitzables, per?? els de la quadratura de Gauss-Kronrod, que hi esta estretament relacionada, s?? que s??n reutilitzables. Els punts de la quadratura de Clenshaw-Curtis tamb?? s??n reutilitzables.

[edita] Algorismes adaptatius

Article principal: Quadratura adaptativa

Si f(x) no t?? moltes derivades a tots els punts, o si les derivades esdevenen grans (el gr??fic de la funci?? ??s molt proper a una recta vertical), llavors la quadratura de Gauss sovint ??s insuficient. En aquest cas un algorisme com el seg??ent pot donar millors resultats:

   // Aquest algorisme calcula l'integral definida d'una funci??, des de 0 fins a 1,
   // de forma adaptativa, a base de triar passos m??s petits en les zones properes  
   // als punts problem??tics.
   // Assignar a inicial_h la mida inicial del pas.
   x:=0
   h:=inicial_h
   acumulador:=0
   FER MENTRE x<1.0
       SI x+h>1.0 LLAVORS
           h=1.0-x
       FI SI
       SI  l'error de quadratura de  f(x) sobre [x,x+h] ??s massa gran LLAVORS
           Fer h m??s petit
       ALTRAMENT
           acumulador:=acumulador + quadratura de f sobre [x,x+h]
           x:=x+h
           SI l'error de quadratura de f(x) sobre [x,x+h] ??s molt petit LLAVORS
               Fer h m??s gran
           FI SI
       FI SI
   FI FER MENTRE
   RETORNA acumulador

Alguns detalls de l'algorisme requereixen un an??lisi cur??s. En molts cassos, estimar l'error de la quadratura sobre un interval per a una funci?? f(x) no ??s obi. Una soluci?? popular ??s emprar dos m??todes de quadratura diferents i fer servit la difer??ncia com una estimaci?? de l'error. L'altre problema ??s decidir qu?? signifiquen "massa gran" i "molt petit". Un criteri local per a "massa gran" ??s que l'error de quadratura no ha de ser m??s gran que $t\cdot h$ on el nombre real t, ??s la toler??ncia que es desitja establir per a l'error global. Llavors altre cop, si h ja ??s min??scul, pot no valer la pena de fer-lo encara m??s petit encara que l'error de quadratura sigui aparentment gran. Un criteri global ??s que la suma dels errors de tots els intervals ha de ser m??s petit que t. D'aquest tipus d'an??lisi de l'error se'n anomena habitualment "a posteriori" donat que es calcula l'error despr??s d'haver calculat l'aproximaci??.

Les heur??stiques per a la quadratura adaptativa es discuteixen a Forsythe et al. (Secci?? 5.4).

[edita] M??todes d'extrapolaci??

La exactitud d'una quadratura de Newton-Cotes ??s generalment funci?? del nombre de punts d'avaluaci??. EL resultat ??s normalment m??s exacte a mesura que el nombre de punts d'avaluaci?? augmenta, O, el que ??s equivalent, a mesura que la dist??ncia entre punts disminueix. ??s natural de q??estionar quin seria el resultat si es permet??s que el pas s'aprop??s a zero. Aquesta pregunta es pot respondre a base de extrapolar el resultat que s'obt?? a partir de dos o m??s mides de pas petites per?? diferents de zero (vegeu extrapolaci?? de Richardson). La funci?? d'extrapolaci?? pot ser un polinomi o una funci?? racional. Els m??todes d'extrapolaci?? es descriuen amb m??s detall per Stoer i Bulirsch (Secci?? 3.4).

[edita] Estimaci?? conservadora (a priori) de l'error

Sia f una funci?? amb una derivada primera afitada en [a,b]. Llavors el teorema del valor mitj?? per a f, on $x < b$ , diu

$(x - a) f'(y_x) = f(x) - f(a)\,$

Per algun $y x$ de [a,x] depenent de x. Si s'integra en x des de a fins a b als dos cantons i es prenen valors absoluts, s'obt??

$\left| \int_a^b f(x)\,dx - (b - a) f(a) \right| = \left| \int_a^b (x - a) f'(y_x)\, dx \right|$

Encara es pot aproximar m??s l'integral del cant?? dret a base de ficar el valor absolut dins del integrand, i substituinr el terme en f' per una fita superior:

$\left| \int_a^b f(x)\,dx - (b - a) f(a) \right| \leq {(b - a)^2 \over 2} \sup_{a \leq x \leq b} \left| f'(x) \right|$ (**)

(Vegeu suprem.) A partir d'aqu??, si s'aproxima l'integral ???_a^bf(x)dx pel m??tode de quadratura (b???a)f(a) l'error no ??s m??s gran que el cant?? dret de (**). Aix?? es pot convertir en un an??lisi de l'error per al sumatori de Riemann (*), donada una fita superior de

${n^{-1} \over 2} \sup_{0 \leq x \leq 1} \left| f'(x) \right|$

Per al terme d'error d'aquesta particular aproximaci??. (Fixeu-vos que aquest ??s precisament l'error que s'ha calculat pel cas $f (x) = x$ .) Emprant m??s derivades, i a base de anar pessigant la quadratura, es pot fer una an??lisi de l'error similar emprant una s??rie de Taylor (emprant un sumatori parcial amb el terme residual) per f. Aquest an??lisi de l'error dona una fita superior estricta del error, si les derivades de f estan disponibles.

Aquest m??tode d'integraci?? es pot combinar amb l'aritm??tica d'intervals per a produir demostracions computacionals i c??lculs verificats.

[edita] Integrals m??ltiples

Els m??todes de quadratura que s'han comentat fins aqu?? s'han dissenyat tots per a calcular integrals d'una dimensi??.

Per a calcular integrals de v??ries dimensions, un enfocament ??s expressar la integral m??ltiple com a repetici?? d'integrals d'una dimensi?? fent ??s del teorema de Fubini.

Aquest enfocament porta a una quantitat d'avaluacions de la funci?? que creix exponencialment a mesura que creix el nombre de dimensions. Es coneixen dos m??todes per a superar aquesta anomenada maledicci?? de la dimensi??.

[edita] Montecarlo

Article principal: Integraci?? de Montecarlo

Els m??todes de Montecarlo i m??todes de quasi-Montecarlo s??n f??cils d'aplicar a integrals multidimensionals, i poden produir una millor exactitud pel mateix nombre d'avaluacions de la funci?? que en integracions repetides emprant m??todes unidimensionals. Una classe gran de m??todes ??tils de Montecarlo s??n els anomenats algorismes de Cadena de Morkov de Montecarlo, Els quals inclouen l'algorisme de Metropolis-Hastings i el mostreig de Gibbs.

[edita] Graelles disperses

Les graelles disperses varen ser desenvolupades inicialment per Smolyak per a la quadratura de funcions de moltes dimensions. El m??tode es basa sempre en una m??tode de quadratura unidimensional, per?? fa una m??s sofisticada combinaci?? de resultats de cada variable.

[edita] Conexi?? amb les equacions diferencials

El problema d'avaluar l'integral

$\int_a^b f(x)\, dx$

Es pot reduir a un problema de valor inicial per a una equaci?? diferencial ordin??ria. Si l'integral de m??s amunt s'escriu com I(b), llavors la funci?? I satisf??

$I'(x) = f(x), \quad I(a) = 0.$

Els m??todes desenvolpats per a resoldre equacions diferencials ordin??ries, com per exemple els m??todes de Runge???Kutta, es poden aplicar per a resoldre el problema i per tant es poden emprar per avaluar l'integral.

[edita] Software per a integraci?? num??rica

L'integraci?? num??rica ??s un dels problemes m??s intensament estudiats en c??lcul num??ric.

De les moltes implementacions en programari que hi ha aqu?? se'n llisten unes quantes.

QUADPACK (part de SLATEC): descripci?? [1], codi font [2]. QUADPACK ??s una col??lecci?? d'algorismes, en Fortran, per a integraci?? num??rica basats en la quadratura de Gauss.
GSL: La llibreria cient??fica GNU (GSL) ??s una llibreria cient??fica escrita en C que subministra un ample ventall de rutines matem??tiques, com la integraci?? de Montecarlo.
Tamb?? es troben algorsimes d'integraci?? num??rica a la Guia de programari matem??tic disponible classe H2.
ALGLIB ??s una col??lecci?? d'algorismes en C# / C++ / Delphi / Visual Basic / etc., per a integraci?? num??rica.

[edita] Refer??ncies

Philip J. Davis and Philip Rabinowitz, Methods of Numerical Integration.
George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler. Computer Methods for Mathematical Computations. Englewood Cliffs, NJ: Prentice-Hall, 1977. (Vegeu Cap??to 5.)
William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling. Numerical Recipes in C. Cambridge, UK: Cambridge University Press, 1988. (Vegeu Cap??tol 4.)
Josef Stoer and Roland Bulirsch. Introduction to Numerical Analysis. New York: Springer-Verlag, 1980. (Vegeu Cap??tol 3.)
Jon M. Smith Recent Developments in Numerical Integration, J. Dynam. Sys., Measurement and Control 96, Ser. G-1, No. 1, 61-70, Mar. 1974.

[edita] Enlla??os externs

Integration: Background, Simulations, etc. al Holistic Numerical Methods Institute

Integraci??

C??lcul de primitives
$\int_a^b f(x)\,dx$ Integraci?? simb??lica ?? Integral de Gau?? ?? Integral no elemental ?? Constant d???integraci?? ?? Algorisme de Risch ?? Funcions elementals ?? Teorema de Fubini ?? M??tode d'exhausti??
De fraccions racionals ?? Per canvi de variable ?? Per parts ?? Per substituci?? trigonom??trica ?? Per s??ries ?? Integral de la secant al cub
Taules d'integrals
Integrals de funcions racionals ?? Integrals de funcions irracionals ?? Integrals de funcions exponencials ?? Integrals de funcions logar??tmiques ?? Integrals de funcions trigonom??triques ?? Integrals inverses de funcions trigonom??triques ?? Integrals de funcions hiperb??liques ?? Integrals de funcions inverses de les funcions hiperb??liques
Definicions d'integraci??
Integral de Bochner ?? Integral de Darboux ?? Integral de Henstock-Kurzwe ?? Integral de Lebesgue ?? Integral de Lebesgue-Stieltjes ?? Sumatori de Riemann ?? Integral de Riemann ?? Integral de Riemann-Stieltjes
Extensions de la integral
Integral impr??pia ?? Integral m??ltiple ?? Integral multiplicativa ?? Integral de superf??cie ?? Integral curvil??nia ?? Teorema de Fubini
Integraci?? num??rica
M??tode de Simpson ?? M??tode trapezial ?? M??tode rectangular ?? M??tode de Romberg ?? Integraci?? de Montecarlo ?? F??rmules de Newton-Cotes ?? Sumatori de Riemann ?? Quadratura de Gauss ?? Quadratura adaptativa

Categories: Algorismes | Integraci?? num??rica