métodos numéricos. grado en ingeniería informática. …lalvarez/teaching/mn/2010... ·...

ULPGCLogo

Métodos Numéricos.Grado en Ingeniería Informática.

Tema 2. Cálculo de ceros de una función

Luis Alvarez León

Univ. de Las Palmas de G.C.

Luis Alvarez León () Métodos Numéricos Univ. de Las Palmas de G.C. 1 / 69

ULPGCLogo

Contenido

1 Introducción

2 El método de la bisección

3 El método de la Regula-Falsi

4 El método de Newton-Raphson

5 El método de la secante

6 El método de Muller

7 Práctica 2. Implementación del método de Newton-Raphson

8 Cálculo de los ceros de un polinomio

9 El algoritmo de Horner para evaluar un polinomio y su derivada

10 Separación en intervalos de los ceros de un polinomio


ULPGCLogo

Contenido

1 Introducción











ULPGCLogo

Cálculo de los ceros de una función. Ejemplo

Una persona aporta a un plan de pensiones durante 30 años una cuotaanual de 600 euros que se va incrementado en un 10 % cada año. Alfinal de los 30 años le dan 156.263 euros. ¿Que interés i nos estádando el banco por el dinero depositado?

año aportación anual valor a los 30 añosaño 1 600 600× (1 + i)30

año 2 600× 1,1 600× 1,1× (1 + i)29

año 3 600× 1,12 600× 1,12 × (1 + i)28

año . .......... .............año 30 600× 1,129 600× 1,129 × (1 + i)TOTAL .......... 156263

La ecuación que debemos resolver para obtener el interés i es

29∑n=0

(600) (1,1)n (1.+ i)30−n = 156263

29∑n=0

(600) (1,1)n (1.+ i)30−n − 156263 = 0


ULPGCLogo

Contenido

1 Introducción











ULPGCLogo

Cálculo de los ceros de una funciónMétodo de la bisección. Objetivo: Confinar en un intervalo cada vez más pequeño uncero de la función


ULPGCLogo



ULPGCLogo


Descripción del algoritmo del método de la bisección

Se parte de una función f (x) y de un intervalo [a,b] donde lafunción cambia de signo

Se calcula el punto medio x = a+b2

Si f (a)f (x) < 0 hacemos b = x , en caso contrario hacemos a = x

Hacemos iteraciones de este procedimiento hasta que f (x) = 0 o∣b − a∣ ≤ (∣b∣+ �)TOL

¿Puede el algoritmo entrar en un bucle infinito de iteraciones?

No


ULPGCLogo

Contenido

1 Introducción











ULPGCLogo

Cálculo de los ceros de una funciónMétodo de la Regula Falsi


ULPGCLogo



ULPGCLogo


En el método de la Regula Falsi el punto x para dividir el intervalo [a,b]es el punto donde se anula la recta que pasa por los puntos (a,f(a)) y(b,f(b)). La ecuación de dicha recta viene dada por la expresión :

y − f (a)f (b)− f (a)

=x − ab − a

Por tanto, el punto x que se utiliza para dividir el intervalo es :

x = a− b − af (b)− f (a)

f (a)


ULPGCLogo

Contenido

1 Introducción











ULPGCLogo

Cálculo de los ceros de una funciónMétodo de Newton-Raphson


ULPGCLogo



ULPGCLogo


En el método de Newton-Raphson, a partir de una aproximación inicialx0 del cero de la función, se va actualizando dicho punto a través delcero de la recta tangente en x0. Para calcular la recta tangente utilizare-mos el desarrollo de Taylor de una función que es :

f (x) = f (x0) + f ′(x0)(x − x0) +f ′′(x0)

2! (x − x0)2 + ..+ f n)(x0)

n! (x − x0)n + .

La ecuación anterior es la recta tangente en x0, si la igualamos a ceroy despejamos obtenemos :

x1 = x0 − f (x0)f ′(x0)

En general, partir de x0 obtenemos una secuencia xn de valores quevan aproximando la raíz, definidos porxn+1 = xn − f (xn)

f ′(xn)


ULPGCLogo

Cálculo de los ceros de una funciónMétodo de Newton-Raphson. Criterios de convergencia

En el método de Newton-Raphson el criterio de convergencia habituales :

∣xn+1 − xn∣ ≤ (∣xn+1∣+ �)TOL

Hay que poner un número máximo de iteraciones porque el métodopuede no converger.

Además, el algoritmo se puede bloquear cuando f ′(xn) = 0


ULPGCLogo

Cálculo de los ceros de una función. Pseudocódigopara calcular la raiz cuadrada de un número.

Algoritmo Raiz_Cuadradavariables reales A,TOLvariable entera Nmaxvariables reales X0, X1leer(A,TOL)leer(Nmax)si A<0 entonces

escribir(’El numero A no es positivo’)devolver CODIGO DE ERROR

finsiX0←(1+A)/2.para K←1 hasta Nmax hacer

X1←X0-(X0*X0-A)/(2.*X0)si X0=X1 mod TOL entonces

escribir (’LA RAIZ DE A ES’,X0)devolver X1

sinoX0←X1

finsifinparaescribir(’No máximo de iterac. excedido’)devolver CODIGO DE ERROR


ULPGCLogo

Contenido

1 Introducción











ULPGCLogo

Cálculo de los ceros de una funciónEl método de la Secante

El método de la Secante es una variante del método de Newton parael caso en que no sea posible calcular la derivada de f (x) de unaforma analítica. En este caso, se sustituye el valor f ′(xn) en elalgoritmo, por el valor

f (xn)− f (xn−1)

xn − xn−1

que corresponde a una aproximación de f ′(xn). Para iniciar elalgoritmo, son necesarias dos aproximaciones iniciales, x0 y x1.


ULPGCLogo

Cálculo de los ceros de una funciónMétodo de la Secante


ULPGCLogo



ULPGCLogo

Contenido

1 Introducción











ULPGCLogo

Cálculo de los ceros de una funciónMétodo de Muller

En el método de Muller, hacemos una aproximación parabólica de unafunción. A partir de una aproximación inicial x0 del cero de la función,se calcula la parábola tangente a x0 :

f (x) ≂ f (x0) + f ′(x0)(x − x0) +f ′′(x0)

2! (x − x0)2

Se calculan las 2 raices de la parábola y se actualiza el valor de x0tomando la raiz más cercana.

Vamos a tener una secuencia xn de valores que van aproximando laraíz.

En cada etapa, para pasar de xn−1 a xn, calculamos f ′(xn), f ′′(xn) uti-lizando los valores xn−1, xn−2, xn−3 de la siguiente forma :


ULPGCLogo


f (x) ≈ f (xn−1) + f ′(xn−1)(x − xn−1) +f ′′(xn−1)

2(x − xn−1)

2

xn = xn−1 +−f ′(xn−1)±

√(f ′(xn−1))

2 − 2f (xn−1)f ′′(xn−1)

f ′′(xn−1)

f ′′(xn−1) ≈ 2f (xn−2)−f (xn−3)

xn−2−xn−3− f (xn−1)−f (xn−2)

xn−1−xn−2

xn−3 − xn−1

f ′(xn−1) ≈f (xn−1)− f (xn−2)

xn−1 − xn−2+

f ′′(xn−1)

2(xn−1 − xn−2)


ULPGCLogo



ULPGCLogo

Contenido

1 Introducción











ULPGCLogo


ULPGCLogo

Funciones matemáticas en C

#include <math.h>

raiz cuadrada√

xsqrt(double x)sqrtf(float x)sqrtl(long double x)

exponencial ex

exp(double x)expf(float x)expl(long double x)

Como usar las funciones matematicas con realsqrtl( (long double) real x)expl( (long double) real x)


ULPGCLogo

Contenido

1 Introducción











ULPGCLogo

Cálculo de los ceros de una funciónCaso especial de un polinomio

Algoritmo de Horner para evaluar un polinomio en un punto

P(x) = 4x3 − 3x2 − 2x + 1 = ((4x − 3)x − 2)x + 1

P(2) = ((4(2)− 3)2− 2)2 + 1 = ((5)2− 2)2 + 1 = (8)2 + 1 = 17

Ejemplos:

P(x) = x4 − 2x3 + 3x + 4 = (((x − 2)x + 0)x + 3)x + 4

P(x) = x4 − x3 + x2 − x + 1 = (((x − 1)x + 1)x − 1)x + 1


ULPGCLogo

Contenido

1 Introducción











ULPGCLogo


Algoritmo de Horner para evaluar la derivada de un polinomio en unpunto. Se evalua simultáneamente el polinomio y su derivada

P(x) = 4x3 − 3x2 − 2x + 1 = ((4x − 3)x − 2)x + 1

P(2) = ((4(2)− 3)2− 2)2 + 1 = ((5)2− 2)2 + 1 = (8)2 + 1 = 17

P ′(2) = 4(2)2 + 5(2) + 8


ULPGCLogo


Algoritmo de Horner para evaluar la derivada de un polinomio en unpunto. Se evalua simultáneamente el polinomio y su derivada

P(x) = x4 − x3 + x2 − x + 1 = (((1x − 1)x + 1)x − 1)x + 1

P(3) = 1272061

P ′(3) = 1(3)3 + 2(3)2 + 7(3)1 + 20


ULPGCLogo

Contenido

1 Introducción











ULPGCLogo

Cálculo de los ceros de una funciónAislar todos los ceros de un polinomio en un sólo intervalo

TeoremaSea un polinomio P(x) = anxn + an−1xn−1 + ......+ a0 con an ∕= 0,entonces las raíces reales de P(x) están en el intervalo[

−1−maxk=0,..,n−1 ∣ ak ∣

∣ an ∣,1 +

maxk=0,..,n−1 ∣ ak ∣∣ an ∣

]

Ejemplo

El polinomio P(x) = 4x3 − 8x2 + x − 3 tiene todas sus raíces en elintervalo

[−3,3]


ULPGCLogo

Cálculo de los ceros de un polinomioAislar cada raíz en un intervalo diferente


ULPGCLogo



ULPGCLogo


Procedimiento para aislar las raíces de un polinomio P(x) de grado n.

Calculamos el intervalo [−a,a] donde se encuentran todas lasraíces

Derivamos n − 1 veces el polinomio, obteniendo el polinomioPn−1)(x) de grado 1

Calculamos la raiz xn−10 de Pn−1)(x)

Calculamos las raíces xn−20 , xn−2

1 del polinomio Pn−2)(x) en los

intervalos[−a, xn−1

0

]y[xn−1

0 ,a]

Calculamos las raíces xn−30 , xn−3

1 , xn−32 del polinomio Pn−3)(x) en

los intervalos[−a, xn−2

0

],[−xn−2

0 , xn−21

], y[xn−2

1 ,a]

Continuamos de esta manera hasta llegar a las raíces de P(x)


métodos numéricos. grado en ingeniería informática. …lalvarez/teaching/mn/2010... ·...

Documents