Zeros de funcions (2009)

Apunte Español
Universidad Universidad Autónoma de Barcelona (UAB)
Grado Ciencias Ambientales - 1º curso
Asignatura Mates
Año del apunte 2009
Páginas 5
Fecha de subida 25/05/2014
Descargas 1

Vista previa del texto

1 Zeros de Funcions Un problema al que anem a parar tot sovint ´es el del c`alcul de les arrels (zeros o solucions) d’una funci´o f (x). Suposarem en tot el que segueix que f (x) ´es una funci´o real: en general no lineal, d’una variable. Exemples de funcions no lineals s´on f (x) = sin x − x + 2, f (x)x3 − 2x2 + x − 1, f (x) = ex + log x + x − 5.
Volem trobar les solucions de l’equaci´o f (x) = 0. En la majoria dels casos aquesta equaci´o no es pot resoldre expl´ıcitament. El problema que plantegem aqu´ı ´es l’obtenci´o, amb una aproximaci´o arbitraria, de les seves arrels.
Els m`etodes que descriurem per resoldre aquest tipus de problemes no determinen les seves solucions de manera directa (en la major part dels casos aix`o no ´es possible). El que trobarem ser`a una successi´o de valors {xx }n∈N convergent a un valor o soluci´o de l’equaci´o plantejada.
´ a dir Es lim = α, f (α) = 0.
n→∞ Aleshores, prendrem com soluci´o del problema un dels termes xk de la successi´o que verifiqui |f (xk )| < Toler`ancia1 o b´e |xk−1 − xk | < Toler`ancia2 ´ clar que no totes les on els valors de les toler`ancies caldr`a que estiguin fixades d’entrada. Es equacions tenen un u ´nic zero en un cert domini. Per exemple, la funci´o f (x) = x6 sin x t´e un nombre infinit d’arrels en tot interval que contingui l’origen. Per tant, en qualsevol proc´es de c`alcul d’arrels d’una equaci´o no lineal haurem de distingir tres fases 1. Localitzaci´ o: Hem de con`eixer la zona on es troben les arrels. En general, aquesta informaci´o es pot obtenir a partir d’un estudi anal´ıtic de la funci´o o tamb´e a partir d’una representaci´o gr`afica aproximada. En molts casos, les equacions provenen d’un problema t`ecnic o cient´ıfic, el coneixement del qual tamb´e pot ajudar a la localitzaci´o de les arrels.
2. Separaci´ o: Alguns cops tenim que dues arrels diferents d’una equaci´o estan molt pr`oximes.
En aquests casos convindr`a separar les arrels, ´es a dir, determinar dominis que continguin una u ´nica arrel de l’equaci´o.
3. Aproximaci´ o Num` erica: l’objectiu que ens plantegem ´es l’obtenci´o d’una successi´o de valors que convergeixi cap a l’arrel buscada. Aquesta successi´o es construir`a normalment, de manera iterativa a partir d’uns certs valors inicials que suposarem suficientment pr`oxims a l’arrel cercada. A partir de x0 , x1 , . . . , xm , obtindrem xm = G(x0 , . . . , xm ) de manera que lim xk , = α amb f (α) = 0.
k→∞ 1 1.1 Alguns m` etodes d’aproximaci´ o de solucions M` etode de bisecci´ o La fonamentaci´o te`orica d’aquest m`etode ´es: Teorema de Bolzano Sigui f : [a, b] → R cont´ınua en l’interval [a, b] i tal que f (a)f (b) < 0, llavors existeix α ∈ (a, b) tal que f (α) = 0.
En general podr´ıem tenir m´es d’una arrel en l’interval [a, b] per`o suposarem que, si cal, hem aplicat pr`eviament un proc´es de localitzaci´o i separaci´o per tal que aix`o no sigui aix´ı. El m`etode de bisecci´o consisteix en construir una successi´o d’intervals encaixats, (a, b) = (a0 , b0 ) ⊃ (a1 , b1 ) ⊃ (a2 , b2 ) ⊃ . . . ⊃ (ak , bk ) ⊃ . . .
de manera que sempre continguin l’arrel i que l’amplitud de cada interval sigui la meitat de l’anterior, ´es a dir, bk − ak = 2(bk+1 − ak+1 ). Quan l’amplitud de l’interval sigui prou petita podrem considerar com una bona aproximaci´o d’aquesta qualsevol punt de l’´ ultim interval calculat, en particular el punt mitj`a. La successi´o d’intervals es construeix aix´ı: a) Partim de l’interval (a0 , b0 ) tal que f (a0 )f (b0 ) < 0, calculem el punt c1 = (a0 + b0 )/2.
b) Si f (c1 ) = 0, c1 ´es l’arrel buscada.
c) Altrament es considerar`a com interval (a1 , b1 ) l’interval (a0 , c1 ) o el (c1 , b0 ) segons que f (a0 )f (c1 ) < 0 o f (c1 )f (b0 ) < 0, respectivament.
d) El proc´es es continua de manera iterativa, per`o a partir ara de l’interval (a1 , b1 ).
Comentari: El m`etode de bisecci´o t´e l’avantatge de ser sempre convergent per`o la seva velocitat de converg`encia ´es lenta. Per aquest m`etode es pot donar una estimaci´o del nombre d’iteracions necessaries per obtenir una arrel a de l’equaci´o f (x) = 0 amb una precisi´o prefixada. Es comen¸ca el proc´es en l’interval (a0 , b0 ) i despr´es de n passos obtenim l’interval (an , bn ) que cont´e cn+1 , punt mitj`a de l’interval i l’arrel a cercada. Com la longitud de l’interval es redueix a la meitat en cada pas, tenim que |cn+1 − α| ≤ b 0 − a0 .
2n+1 Suposem que volem cercar l’arrel a amb una precisi´o menor que una certa quantitat petita ε, ´es a dir, volem que es compleixi |cn+1 − α| ≤ ε.
Aquesta condici´o es verificara si b 0 − a0 b 0 − a0 ≤ ε , o equivalentmet 2n+1 ≥ n+1 2 ε i prenent logaritmes, veiem que el nombre n, d’iteracions necessaries ha de verificar log n≥ b0 −a0 ε log 2 − 1.
Aix´ı, si volem obtenir l’arrel d’una funci´o amb una precisi´o menor que ε = 10−6 partim d’un interval (a0 , b0 ) de longitud 1, obtindrem la soluci´o cercada al determinar c19 .
2 Exemple: Volem cercar l’´ unica arrel de la funci´o f (z) = x−e−x que esta en l’interval (0.5, 0.6).
Aplicant el m`etode de bisecci´o obtenim la seg¨ uent taula: i (ai , bi ) f (ai ) f (bi ) ci+1 = (bi + ai ) /2 f (ci+1 ) 0 (0.5, 0.6) −0.1065 0.0512 0.55 −0.0270 1 (0.55, 0.6) −0.0270 0.0512 0.575 0.0123 2 (0.55, 0.575) −0.0270 0.0123 0.5625 −0.0073 En aquest exemple tenim que |c3 − α| ≤ 10−1 ∗ 2−3 = 0.0125 i f (c3 ) = 7.3 ∗ 10−3 .
M` etode de Newton-Raphson Suposem ara que la funci´o f ´es dues vegades derivable en un interval (a, b). Sigui xn , una aproximaci´o de l’arrel α de l’equaci´o f (x) = 0 tal que f (xn ) = 0 i h = α − xn , ´es *petit*.
Considerem el desenvolupament de Taylor de la funci´o f al voltant del punt xn , f (x) = f (xn ) + f (xn )(x − xn ) + f (ξ(xn ) (x − xn )2 , 2 on ξ(xn ) ∈< x, xn > . Avaluant el desenvolupament en el punt α = xn + h obtenim 0 = f (α) = f (xn + h) = f (xn ) + f (xn )h + f (ξ(xn ) 2 h.
2 Suposem que, com h ´es petit, el terme que cont´e h2 ´es menyspreable i per tant 0 f (xn ) + f (xn )h.
Isolant h d’aquesta equaci´o obtenim h hn = − f (xn ) .
f (xn ) Aquesta f´ormula ens d´ona una correcci´o, hn , per la nostra aproximaci´o xn , de l’arrel α que anomenem xn+1 = xn + hn . El m`etode de Newton consisteix en donada una aproximaci´o inicial x0 generar una successi´o de valors {xn }, definida per xn+1 = xn − f (xn ) n = 0, 1, . . .
f (xn ) Aquest proc´es s’haur`a d’aturar quan |xn+1 − xn | < ε o b´e |f (xn+1 )| < δ on toler`ancies que estem disposats a acceptar.
i δ s´on les Comentari: El m`etode de Newton no ´es sempre convergent per qualsevol valor de x0 i sempre ´es convenient escollir l’aproximaci´o inicial x0 tan propera com sigui possible a l’arrel buscada.
Ara b´e, quan tenim converg`encia, aquesta sol ser r`apida.
Volem cercar l’´ unica arrel de la funci´o f (z) = x − e−x que esta en I’interval (0.5, 0.6). Aplicant el m`etode de Newton-Raphson obtenim la seg¨ uent taula: n 0 1 2 xn f (xn ) f (xn ) 0.55 −0.026950 0.567090 −0.000084 0.567143 −5.4 ∗ 10−8 3 f (xn ) f (xn ) 1.576950 −0.017090 1.567174 −0.000053 Notem que x1 t´e tres xifres iguals que l’arrel αa i x2 en t´e sis.
Definici´ o: Direm que α ´es una arrel amb multiplicitat m de l’equaci´o f (z) = 0 si es compleix que f (a) = f (a) = . . . = f (m−1) (a) = 0, per`o f (m) (a) = 0.
Nota: El m`etode de Newton presenta problemes quan l’arrel a de la funci´o f t´e multiplicitat mes gran que 1. En aquest cas podem escriure el seg¨ uent m`etode iteratiu que sera usat per cercar arrels de multiplicitat m xn+1 = xn − m f (xn ) n = 0, 1, . . .
f (xn ) El proc´es iteratiu s’aturar`a d’igual forma que s’ha exposat en el m`etode de Newton.
1.2 Teoria general de la iteraci´ o simple L’equaci´o f (x) = 0 es pot escriure en la forma x = g(x) usant operacions elementals i, rec´ıprocament, x = g(x) es pot posar com f (x) = 0. Llavors, si α ´es una arrel de l’equaci´o f (x) = 0, tenim que α = g(α), on α s’anomena punt fix de la funci´o x → g(x). Un m`etode iteratiu de la forma xn+1 = g(xn ) s’anomena proc´es d’iteraci´o simple. Un exemple d’un m`etode n) d’iteraci´o simple ´es el m`etode de Newton xn+1 = xn − ff (x n = 0, 1, . . . que podem escriure (xn ) com xn+1 = g(xn ) amb g(x) = x − f (x) .
f (x) Exemple: Volem cercar l’´ unica arrel de la funci´o f (x) = x − e−x amb x0 = 0.55. Aplicant m`etodes d’iteraci´o simple. L’equaci´o anterior es pot escriure de diferents formes, per exemple podem posar x = e−x o b´e prenent logaritmes x = − log x. Aquestes expressions donen lloc a dos m`etodes iteratius, xn+1 = e−xn i xn+1 = − log xn . Aplicant aquest m`etodes iteratius obtenim la seg¨ uent taula: xn+1 = e−xn n xn 0 0.55 1 0.57695 2 0.561609 3 0.570291 4 0.565361 · · · · · · · · · · 16 0.567141 17 0.567144 18 0.567143 n 0 1 2 3 4 5 6 7 8 xn+1 = − log xn xn 0.55 0.597837 0.514437 0.664682 0.408447 0.895394 0.110492 2.202816 −0.789737 Es veu que el primer dels m`etodes convergeix lentament cap a la soluci´o, despr´es de 18 iterats, mentre que el segon d’ells divergeix. Per tant haur´ıem de tenir algun criteri perqu`e la funci´o g ens don´es una successi´o convergent.
4 Teorema (exist` encia i unicitat d’un punt fix) Sigui g : [a, b] → R, una funci´o cont´ınua tal que g(x) ∈ [a, b] per a tot x ∈ [a, b]. A m´es, suposem que existeix g en l’interval (a, b) amb |g (x)| ≤ k < 1 per a tot x ∈ (a, b).
Si p0 ´es qualsevol nombre de l’interval [a, b], llavors la successi´o definida per pn = g(pn−1 ), n ≥ 1 convergeix a l’´ unic punt fix p que t´e g en l’interval [a, b].
Es pot veure que l’error despr´es de n passos ve donat per |pn − p| ≤ kn |p1 − p0 |.
1−k En l’´ ultim exemple que hem vist ten´ıem els dos m`etodes iteratius xn+1 = e−xn i xn+1 = − log xn .
En el primer cas. tenim g(x) = e−x , g (x) = −e−x , i per tant g (x) = 0.567 < 1 , per x α.
Mentre en el segon cas, tenim g(x) = − log x, g (x) = −1/x, i per tant g (α) = 1/0.567 > 1, per x α.
5 ...