Universitat Autnoma de Barcelona, Departament de Fsica

Mtodes numrics

Alfredo Hernndez Cavieres2014-2015

cbeaAquesta obra est subjecta a una llicncia de

Reconeixement-NoComercial-CompartirIgual 4.0Internacional de Creative Commons.

ndex 4

ndex

1 Resoluci dequacions no lineals 61.1 Mtode zero . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2 Mtode de NewtonRaphson . . . . . . . . . . . . . . . . . 61.3 Mtode de regula falsi . . . . . . . . . . . . . . . . . . . . 71.4 Resoluci de sistemes dequacions no lineals . . . . . . . . 81.5 Estimaci dels errors . . . . . . . . . . . . . . . . . . . . . 9

2 Derivaci i integraci numrica 122.1 Derivaci numrica . . . . . . . . . . . . . . . . . . . . . . 122.2 Integraci pel mtode del rectangle . . . . . . . . . . . . . 132.3 Integraci pel mtode del trapezi . . . . . . . . . . . . . . 132.4 Integraci pel mtode de Simpson . . . . . . . . . . . . . . 132.5 Integraci pel mtode de Romberg . . . . . . . . . . . . . . 14

3 Resoluci dequacions diferencials ordinries 163.1 Condicions inicials . . . . . . . . . . . . . . . . . . . . . . 163.2 Condicions de contorn . . . . . . . . . . . . . . . . . . . . 16

1 Resoluci dequacions no lineals 6

1 Resoluci dequacions no linealsLobjectiu s trobar {x R | f(x) = 0}, on f : R R. Cal tenir encompte que potser no hi ha soluci o b pot ser que s que nhi hagi perel mtode seguit no sigui vlid per torbar-la.

1.1 Mtode zeroTeorema 1.1. Sigui g(x) R contnua en [a, b]. Si {L < 1 | |g(x) g(y)| L |x y|},x, y [a, b], llavors:i) ! soluci a lequaci x = g(x) en [a, b].ii) La soluci s x = limix{xi}, amb

xi+1 = g(xi) (1.1)

on x0 s qualsevol x [a, b].

Exemple 1.1. Volem resoldre ln x = 1. Analticament sabem que lasoluci s x = e ( 2.718 28).i) Estudiem lequaci g(x) = 1 x ln x = x.ii) Intum que la soluci s 0 < x < 10.iii) g(x) g(y) =

1 + ln(y/x)xy < 1 ! soluci (0, 10).Fent moltes iteracions arribem a x15 = 2.717 346 . . . , s a dir hem obtingut3 xifres significatives. Com es pot veure, aquest mtode t un error quedecau molt lentament. N

1.2 Mtode de NewtonRaphsonSigui f(x) una funci de la qual volem trobar els punts on f(x) = 0. Elmtode consisteix en agafar un punt inicial x0 i trobar la recta tangental punt: y = f (x0)(x x0) + f(x0) i igualant-la a zero. s fcil veureque la segent recurrncia ens porta a la soluci x = limix{xi}:

xi+1 = xi f(xi)f (xi)

(1.2)

Ara b, no sempre s possible trobar una soluci x0 R.

7 Mtodes numrics

Teorema 1.2. Es pot demostrar que ! arrel de f(x) = 0 en [a, b] si escompleixen les segents condicions:1. f(x) C1[a,b].2. f (x) 6= 0, x [a, b].3. f (x) 6= 0, x [a, b].4. f(a)f(b) < 0.

5. max{ f(a)f (a)

, f(b)f (b)} < b a.

Exemple 1.2. Volem trobar

3 ( 1.732 050 807 5). Llavors estudiaremlequaci f(x) = x2 3 = 0. La seva derivada s f (x) = 2x.i) f(x) CR , en particular agafem linterval [1, 4].ii) f (x) no canvia de signe (s sempre positiva).iii) f(1)f(4) = 26 < 0.iv) max

{32 , 168 } < 5.Agafant x0 = 2 arribem a x3 = 1.732 050 8 . . . , s a dir, amb tres iteracionsarribem a un resultat exacte en 8 xifres decimals.1 for(i = 0; i < N; ++i)2 {3 x[i+1] = x[i] - (x[i]**2 - 3)/(2*x[i]));4 if (fabsl(x[i+1]-x[i]) < pow(10, -tolerance))5 {6 N = i+1; // Es redefineix per loops posteriors7 break;8 }9 }

N

1.3 Mtode de regula falsi

c = f(b)a f(a)bf(b) f(a) (1.3)

1 Resoluci dequacions no lineals 8

1 # TODO: implement the code2 for(i = 0; i < N; ++i)3 {4 x[i+1] = x[i] - (x[i]**2 - 3)/(2*x[i]));5 if (fabsl(x[i+1]-x[i]) < pow(10, -tolerance))6 {7 N = i+1; // Es redefineix per loops posteriors8 break;9 }10 }

1.4 Resoluci de sistemes dequacions no linealsSigui ~f(~x) = ~0 un sistema dequacions. El mtode emprat per trobarsolucions s una generalitzaci del mtode de NewtonRaphson:

~xi+1 = ~xi (J~

~

~f~xi

)1~f(~xi) (1.4)

on J~

~

~f~xi

s la matriu jacobiana de ~f(~x) evaluada a ~xi. Anlogament, shade complir la segent condici per lexistncia de la soluci:

i) detJ~

~

~f~xi6= 0

(J~

~

~f~xi

)1.

Exemple 1.3. Siguix

2 + y2 1 = 0x2 y2 + 1/2 = 0 . La construcci de la recur-

rncia seria la segent:

(xi+1yi+1

)=(xiyi

)(

2xi 2yi2xi 2yi

)1 (x2 + y2 1x2 y2 + 1/2

)

=(xiyi

)

2x2i y2i + 1/yi + 1/2

4xi2x2i y2i + 1/yi + 1/2

4yi

= 18

4x2i + 1xi

4y2i + 3yi

Amb x0 = 1, y0 = 1, arribem a x3 =

32816560 0.500 152 439, y3 =

1881721728

0.866 025 405, que s una de les quatre solucions amb 3 xifres exactes a xi 8 xifres significatives a y.

9 Mtodes numrics

1 for(i = 0; i < N; ++i)2 {3 x[i+1] = (4 * x[i]**2 + 1)/(8*x[i]);4 y[i+1] = (4 * y[i]**2 + 3)/(8*y[i]);5 if ((fabsl(x[i+1]-x[i]) < pow(10, -tolerance)) //6 && (fabsl(y[i+1]-y[i]) < pow(10, -tolerance)))7 {8 N = i+1; // Es redefineix per loops posteriors9 break;10 }11 }

N

1.5 Estimaci dels errors

Per a mtodes iteratius es pot fitar lerror e coms entre cada iteraci.Sigui x la soluci exacta de f(x) = 0 i xn valor aproximat de lansima iteraci. Llavors tenim

en+1 = x xn+1 = x xn + f(xn)f (xn)

(NewtonRaphson)

f(x) = f(xn + en) f(xn) + f (xn)en + f ()e2n = 0 (Taylor)

en+1 = |f()|

|2f (xn|e2n ke2n , k R

on (x, xn) o b (xn, x) segons la situaci, i per tant s un valorfitat.

Estimar lerror en un programa

Una de les coses que volem controlar en un programa s el temps declcul. Com ens podem assegurar que passat x temps el nostre programaha trobat la soluci amb lexactitud que volem? Per controlar el clculpodem emprar les segents estratgies:i) Comparar xi amb valors anteriors: lobjectiu s parar de calcular

quan el resultat ha arribat a una tolerncia (i.e., xifres exactes)predeterminada, s a dir, que pari si |xi xi1| < .

1 Resoluci dequacions no lineals 10

ii) Predeterminar un nombre mxim diteracions: lobjectiu s evitarque el programa es quedi calculant infinitament. El nombre mximditeracions no sempre s trivial destablir de manera ptima, permentre major sigui, ms exacte hauria de ser el resultat.

Exemple 1.4. A la lnia 1 establim el nombre mxim diteracions N. Ala lnia 4 establim = 10-tolerance.1 for(i = 0; i < N; ++i)2 {3 [...]4 if (fabsl(x[i+1]-x[i]) < pow(10, -tolerance))5 {6 printf("Sha arribat a la tolerncia desitjada.\n");7 break;8 }9 [...]10 }

N

2 Derivaci i integraci numrica 12

2 Derivaci i integraci numrica

2.1 Derivaci numrica

Si b la derivaci numrica s senzilla, shauria devitar sempre que siguipossible, ja que introdueix molt error numric.

Primera derivada

f (x0) f(x0 + h) f(x0 h)2h =fx (2.1)

on h s la llargada de cada pas de la discretitzaci del domini de la funcif(x).Observem que si savalua la funci als extrems del domini la frmulaanterior falla. No s difcil veure que les frmules equivalents sn lessegents:

Extrem esquerre: f (x0) f(x0) f(x0 + h)h

Extrem dret: f (x0) f(x0 h) f(x0)h

Segona derivada

A travs de lexpansi per Taylor podem arribar fcilment a una expressiper a la segona derivada:

f(x0 + h) = f(x0) + f (x0)h+12f(x0)h2 +O(h3)

f(x0 h) = f(x0) f (x0)h+ 12f(x0)h2 +O(h3)

f (x0) = f(x0 + h) + f(x0 h) 2f(x0)h2

(2.2)

13 Mtodes numrics

2.2 Integraci pel mtode del rectangle

Sigui f(x) una funci de la qual volem saber la seva integral en x [a, b].El mtode consisteix bsicament en fer una suma de Riemann, on la sevadiscretitzaci consisteix en partir el domini en n subintervals de midah = b a

n.

baf(x) dx

ni=0

f

(a+ h

(i+ 12

))h (2.3)

Lerror associat al mtode s de O(h), s a dir, lineal.

2.3 Integraci pel mtode del trapezi

Sigui f(x) una funci de la qual volem saber la seva integral en x [a, b].El mtode consisteix bsicament en fer una suma de Riemann, on la sevadiscretitzaci consisteix en partir el domini en n subintervals de midah = b a

n. La diferncia amb el mtode del rectangle s que en comptes

de calcular rees de rectangles es fa de trapezis.

baf(x) dx

f(a) + f(b) + 2 n1i=1

f(a+ hi) h

2 (2.4)

Lerror associat al mtode s de O(h2), s a dir, quadrtic.

2.4 Integraci pel mtode de Simpson

Sense aprofundir gaire, el mtode consisteix en agafar el punt mitj decada subinterval. Daquesta manera a cada subinterval hi ha definits trespunts, i es pot descriure unvocament una parbola que passi pels tres.La primera aproximaci per la suma de Simpson (per a n = 1) s

baf(x) dx b a6

(f(a) + 4f

(b a

2

)+ f(b)

)(2.5)

Lerror associat al mtode s de O(h3).

2 Derivaci i integraci numrica 14

2.5 Integraci pel mtode de Romberg

El mtode es deriva del mtode del trapezi. Sigui T (h) laproximacide la integral de f(x) a [a, b] pel mtode del trapezi associada al pas h.Aquesta suma la podem expressar (mitjanant lexpansi de MacLaurin)com:

T (h) baf(x) dx+ 1h2 + 2h4 + . . .

T (h/2) baf(x) dx+ 1 (h/2)2 + 2 (h/2)4 + . . .

Manipulant aquests dos valors arribem a una expressi exacta del valorde la integral:

baf(x) dx 4T (h/2) T (h)3 +O(h

4) (2.6)

Observem que el que hem pogut aconseguir s eliminar lerror dordre h2,de manera que aquest mtode s molt ms precs que el del trapezi.

Generalitzaci de Romberg

Si en comptes de treballar amb dos valors de laproximaci pel mtodedel trapezi treballem amb m valors, lexpressi de Romberg esdev

Rm,j =4j1Rm,j1 Rm1,j1

4j1 1 (2.7)

on Rm,1 sn les aproximacions de la integral pel mtode del trapezi, quesegueixen la recurrncia segent:

Rm,1 = T(

h

2m1

)(2.8)

Una manera senzilla dentendre lalgoritme s pensar en una matriude resultats. Per exemple, a partir de quatre aproximacions inicials

15 Mtodes numrics

(mmax = 4), tenim: R1,1 0 0 0R2,1 R2,2 0 0R3,1 R3,2 R3,3 0R4,1 R4,2 R4,3 R4,4

Notem que la precisi del resultat R augmenta amb el creixement de m ide j, de manera que el cal esperar que Rm,m sigui el que saproximi ambms exactitud al resultat veritable.

Exemple 2.1. Volem saber 10ex

2dx. Les tres primeres iteracions pel

mtode del trapezi ens donen els segents resultats:i) T (1) 1.859 140 914.ii) T (1/2) 1.571 583 165.iii) T (1/4) 1.490 678 862.Llavors, mitjanant el mtode de Romberg calculem els segents resultats:iv) R2,2 1.475 730 582.v) R3,2 1.463 710 761.vi) R3,3 1.462 909 439.Comparant amb el valor real de la integral, 10 ex2 dx 1.462 651 745,podem veure que per cada iteraci, el valor calculat convergeix a la solucide la integral.1 # TODO: implement the code2 for(i = 0; i < N; ++i)3 {4 x[i+1] = x[i] - (x[i]**2 - 3)/(2*x[i]));5 if (fabsl(x[i+1]-x[i]) < pow(10, -tolerance))6 {7 N = i+1; // Es redefineix per loops posteriors8 break;9 }10 }

N

3 Resoluci dequacions diferencials ordinries 16

3 Resoluci dequacions diferencialsordinries

3.1 Condicions inicials

3.2 Condicions de contorn

Resoluci d'equacions no linealsMtode zeroMtode de NewtonRaphsonMtode de regula falsiResoluci de sistemes d'equacions no linealsEstimaci dels errors

Derivaci i integraci numricaDerivaci numricaIntegraci pel mtode del rectangleIntegraci pel mtode del trapeziIntegraci pel mtode de SimpsonIntegraci pel mtode de Romberg

Resoluci d'equacions diferencials ordinriesCondicions inicialsCondicions de contorn