Raices 2014
Programación y Métodos Numéricos
Universidad Nacional de General Sarmiento
1◦ Semestre 2014
Programación y Métodos Numéricos
Búsqueda de raíces de funciones
Un problema clásico de la matemática es la búsqueda de raíces de
funciones. Es decir, dada una función f encontrar un valor x tal que
f (x ) = 0
La cuestión ahora es que no existe una fórmula, tal comola
resolvente para la ecuación cuadrática, para cada una de las
funciones. Por lo que fue necesario desarrollar algoritmos para
poder, al menos, aproximar los valores de las raíces.
Programación y Métodos Numéricos
Para comenzar...
Para poder aproximar las raíces es necesario definir ciertos
parámetros:
1
Precisión o Tolerancia : este valor nos indica hasta donde
permitimos el error delalgoritmo. Es decir, dado > 0,
diremos que la raíz de f es aproximadamente c si
|f (c) | <
2
Condición de parada: Puede suceder que por algún motivo no
se verifique que |f (c) | < , ya sea porque el algoritmo falló o
porque f no tiene raíces. Por lo que es necesario incluir una
variable que permita detener el programa luego de n
repeticiones/iteraciones.
Programación y Métodos Numéricos
Paracomenzar...
Para poder aproximar las raíces es necesario definir ciertos
parámetros:
1
Precisión o Tolerancia : este valor nos indica hasta donde
permitimos el error del algoritmo. Es decir, dado > 0,
diremos que la raíz de f es aproximadamente c si
|f (c) | <
2
Condición de parada: Puede suceder que por algún motivo no
se verifique que |f (c) | < , ya sea porque el algoritmo falló o
porque f notiene raíces. Por lo que es necesario incluir una
variable que permita detener el programa luego de n
repeticiones/iteraciones.
Programación y Métodos Numéricos
Recordemos algo de Matemática I...
Para empezar cualquier algoritmo es necesario determinar un
intervalo donde nos aseguremos que haya al menos una raíz para
que el programa no colapse. Para eso recordamos a nuestro
querido amigoBolzano...
Teorema de Bolzano: Sea f : [a, b] → R una función continua en
[a, b] y tal que f (a) · f (b) < 0, es decir que hay un cambio de
signo entre f (a) y f (b). Entonces existe c ∈ (a, b) tal que
f (c) = 0.
Programación y Métodos Numéricos
Recordemos algo de Matemática I...
Para empezar cualquier algoritmo es necesario determinar un
intervalo donde nos aseguremos que haya al menos una raízpara
que el programa no colapse. Para eso recordamos a nuestro
querido amigo Bolzano...
Teorema de Bolzano: Sea f : [a, b] → R una función continua en
[a, b] y tal que f (a) · f (b) < 0, es decir que hay un cambio de
signo entre f (a) y f (b). Entonces existe c ∈ (a, b) tal que
f (c) = 0.
Programación y Métodos Numéricos
Algoritmo de Bisección
Para este algoritmo se parte de una función fcontinua en el
intervalo [a, b] y de la tolerancia > 0. Si f (a) · f (b) < 0, por
Bolzano que f tiene al menos una raíz por lo que no hace falta la
condición de parada. Este método toma el punto medio de [a, b],
es decir,
c=
Programación y Métodos Numéricos
a+b
2
Algoritmo de Bisección
Pueden suceder 3 cosas:
• Si |f (c) | < , el proceso se termina y se devuelve el valor c
como raíz aproximada.Programación y Métodos Numéricos
Algoritmo de Bisección
• Si f (a) · f (c) < 0, en cuyo caso se sustituye b por c y se
repite el proceso.
Programación y Métodos Numéricos
Algoritmo de Bisección
• Si f (c) · f (b) < 0, en cuyo caso se sustituye a por c y se
repite el proceso.
Programación y Métodos Numéricos
Algoritmo de Bisección
Convergencia
Luego de n iteraciones, si x es la raíz def y c es su aproximación
se puede decir que :
|x − c| ≤
b−a
2n
Esto indica que converge globalmente de manera lineal de razón 21 .
Programación y Métodos Numéricos
Algoritmo de Bisección
Pseudo-código
Entrada: la función f , los extremos del intervalo a y b y la
tolerancia
c = a+b
2
while abs(f (c)) ≥ do
if f (a) · f (c) < 0 then
b=c
else
a=c
end if
c = a+b
2
end while
Salida: el valor c....
Regístrate para leer el documento completo.