1. Método de la Bisección ¿Qué es?
Referencia: Burden 2.1 p36, Chapra 5.2 p124, Rodríguez 3.1 p36
El método más simple para buscar raíces de una ecuación, se basa en el teorema del valor intermedio, búsqueda binaria, partición de intervalos o de Bolzano.
En el intervalo donde existe un cruce por cero de la función f(x), el algoritmo busca la raíz al reducir el intervalo en la mitad (bisección), seleccionando el sub- intervalo donde se mantenga el cambio de signo de la función f(x).
Los pasos a seguir son los siguientes:
- el intervalo
[a,b]se divide siempre en la mitadc. - Si la función f(x) cambia de signo sobre un intervalo, se evalúa el valor de la función en el punto medio
f(c). - La posición de la raíz se determina en el punto medio del sub-intervalo, izquierdo o derecho, dentro del cual ocurre un "cambio de signo".
- el proceso se repite hasta obtener una mejor aproximación
La gráfica muestra una animación del proceso, observe la forma en que progresivamente se acercan los puntos [a,b], donde se mantienen valores con signo diferente entre f(a) y f(b).
Para describir mejor el método, observamos la gráfica en una sola iteración.
Para la primera iteración se tiene que la función tiene un cambio de signo dentro del intervalo [a,b].
El intervalo se divide en la mitad, representado por el punto c, obteniendo el sub-intervalo izquierdo [a,c] o sub-intervalo derecho [c,b].
El sub-intervalo que contiene la función con un cambio de signo, se convierte en el nuevo intervalo por analizar en la siguiente iteración.
1.2 Cota de Error
Referencia: Burden Teorema 2.1 p39.
El error del método de la bisección se estima como el ancho o tamaño del intervalo [a,b] de la última iteración realizada. Si el error es menor que la tolerancia del ejercicio, el algoritmo se detiene y se considera encontrada la raíz.
Suponga que f ∈ C[a,b] y f(a)*f(b)<0, f es una función en el intervalo [a,b] y que presenta un cambio de signo.
|p_n - p| \leq \frac{b-a}{2^n}donde n ≥ 1
la desigualdad implica que pn converge a p con una razón de convergencia de orden:
O \Big(\frac{1}{2^n}\Big)es decir:
p_n =p+O \Big( \frac{1}{2^n} \Big)Con lo que se puede determinar el número de iteraciones necesarias para encontrar la raíz, tal como se muestra en el siguiente ejercicio.
1.3 Cantidad de iteraciones - Ejercicio
Referencia: Burden ejemplo 2 p40
Determine la cantidad de iteraciones necesarias para resolver
f(x) = x^3 + 4x^2 -10 =0con exactitud de 10-3 en el intervalo [1,2].
Desarrollo: Se busca encontrar un entero n que satisface la ecuación:
|p_n -p| \leq \frac{b-a}{2^{n}} 2^{-n}< 10^{-3}usando logaritmos:
-n \log _{10}( 2) < -3 n > \frac{3}{\log _{10}( 2)} = 9.96En consecuencia se requieren unas diez iteraciones para lograr la aproximación de 10-3. Verifique los resultados con los valores calculados.
2. Ejercicio
Referencia: Burden 2.1 ejemplo 1 p38
La ecuación mostrada tiene una raíz en [1,2], ya que f(1)=-5 y f(2)=14 y existe cambio de signo. Muestre los resultados parciales del algoritmo de la bisección con una tolerancia de 0.0001
f(x) = x^3 + 4x^2 -10 =03. Desarrollo Analítico - ejemplo paso a paso
El desarrollo del ejercicio tradicionalmente realizado con lápiz, papel y calculadora, muestra el orden y detalle de las operaciones que se pueden traducir a un algoritmo en Python. El objetivo además de desarrollar la comprensión del método, permite en una evaluación observar si el estudiante conoce el método y usa apropiadamente los valores en cada iteración.
iteración 1
cambio de signo a la izquierda
a = 1, b= c = 1.5 tramo = |1.5-1| =0.5iteración 2
cambio de signo a la derecha
a = c = 1.25, b=1.5 tramo = |1.5-1.25| = 0.25iteración 3
continuar como tarea ...
La tabla resume los valores de las iteraciones.
La misma tabla se puede realizar con un algoritmo para tener los resultados más rápido y observar el comportamiento del método.
| i | a | c | b | f(a) | f(c) | f(b) | tramo |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1.5 | 2 | -5 | 2.37 | 14 | 0.5 |
| 2 | 1 | 1.25 | 1.5 | -5 | -1.79 | 2.37 | 0.25 |
| 3 | 1.25 | ... | 1.5 |
Observe los resultados de f(c), principalmente en la iteración i=9 con tramo=0.00097 que representa el error de estimación del valor vs tolerancia.
método de Bisección
i ['a', 'c', 'b'] ['f(a)', 'f(c)', 'f(b)']
tramo
0 [1. 1.5 2. ] [-5. 2.375 14. ]
0.5
1 [1. 1.25 1.5 ] [-5. -1.7969 2.375 ]
0.25
2 [1.25 1.375 1.5 ] [-1.7969 0.1621 2.375 ]
0.125
3 [1.25 1.3125 1.375 ] [-1.7969 -0.8484 0.1621]
0.0625
4 [1.3125 1.3438 1.375 ] [-0.8484 -0.351 0.1621]
0.03125
5 [1.3438 1.3594 1.375 ] [-0.351 -0.0964 0.1621]
0.015625
6 [1.3594 1.3672 1.375 ] [-0.0964 0.0324 0.1621]
0.0078125
7 [1.3594 1.3633 1.3672] [-0.0964 -0.0321 0.0324]
0.00390625
8 [1.3633 1.3652 1.3672] [-3.2150e-02 7.2025e-05 3.2356e-02]
0.001953125
9 [1.3633 1.3643 1.3652] [-3.2150e-02 -1.6047e-02 7.2025e-05]
0.0009765625
Método de la Bisección
iteraciones: 10
raíz en: 1.3642578125
errado: 0.0009765625
>>> Se realiza la gráfica con los puntos [c,f(c)] de la tabla para observar el resultado, resaltando que los puntos al final se aglomeran alrededor de la solución o raíz de la ecuación.
4. Algoritmo en Python para el método de la Bisección
El video presenta el desarrollo básico conceptual del algoritmo en Python para una comprensión del proceso paso a paso.
# Método de la Bisección
# [a,b] se seleccionan de la gráfica de f(x)
import numpy as np
# INGRESO
fx = lambda x: x**3 + 4*x**2 - 10
a = 1
b = 2
tolera = 0.001
# PROCEDIMIENTO
tramo = b-a
while not(tramo<tolera):
c = (a+b)/2
fa = fx(a)
fb = fx(b)
fc = fx(c)
cambia = np.sign(fa)*np.sign(fc)
if cambia < 0: # cambio de signo izquierda
a = a
b = c
if cambia > 0: # cambio de signo derecha
a = c
b = b
tramo = b-a
# SALIDA
print('Bisección raiz en: ', c)
print('errado: ', tramo)
Instrucciones en Python del Algoritmo básico del video
Se obtiene el siguiente resultado:
Bisección raíz en: 1.3642578125
errado: 0.0009765625
>>>5. Algoritmo en Python como función
El algoritmo presentado en el video se puede mejorar, por ejemplo simplificando los dos condicionales en uno.
if (cambia<0): # cambio de signo izquierda
b = c
fb = fc
else: # cambio de signo derecha
a = c
fa = fc
Considere que en cada iteración, se evalúa la función en tres puntos, fa y fb se calculan en la iteración anterior. Se puede optimizar sustituyendo los valores de los extremos y solo evaluando el centro fc.
fa = fx(a)
fb = fx(b)
tramo = np.abs(b-a)
itera = 0
...
while (tramo>=tolera and itera<=iteramax):
c = (a+b)/2
fc = fx(c)
cambia = np.sign(fa)*np.sign(fc)
Para el desarrollo con lápiz y papel sería necesario observar los valores calculados en cada iteración, por lo que se añade una variable "vertabla" para activar las instrucciones que muestran los cálculos en cada iteración.
if vertabla==True:
print('método de Bisección')
print('i', ['a','c','b'],
[ 'f(a)', 'f(c)','f(b)'])
print(' ','tramo')
np.set_printoptions(precision)
Se incluye validar que el intervalo disponga de fa y fb con signos opuestos, antes de intentar usar el algoritmo
if cambia<0: # existe cambio de signo f(a) vs f(b)
Finalmente se puede convertir el procedimiento en una función de Python.
Algoritmo en Python como función
# Algoritmo de Bisección, con tabla
# Los valores de [a,b] son aceptables
# y seleccionados desde la gráfica de la función
# error = tolera
import numpy as np
def biseccion(fx,a,b,tolera,iteramax = 50,
vertabla=False, precision=6):
'''Algoritmo de Bisección
Los valores de [a,b] son seleccionados
desde la gráfica de la función
error = tolera
'''
fa = fx(a)
fb = fx(b)
tramo = np.abs(b-a)
itera = 0
cambia = np.sign(fa)*np.sign(fb)
tabla=[]
if cambia<0: # existe cambio de signo f(a) vs f(b)
if vertabla==True:
print('método de la Bisección')
print('i', ['a','c','b'],[ 'f(a)', 'f(c)','f(b)'])
print(' ','tramo')
np.set_printoptions(precision)
while (tramo>=tolera and itera<=iteramax):
c = (a+b)/2
fc = fx(c)
cambia = np.sign(fa)*np.sign(fc)
unafila = np.array([a,c,b,fa,fc,fb])
if (cambia<0):
b = c
fb = fc
else:
a = c
fa = fc
tramo = np.abs(b-a)
unafila = np.concatenate([unafila,[tramo]],axis=0)
tabla.append(unafila)
if vertabla==True:
print(itera,unafila[0:3],unafila[3:6])
print(' ',tramo)
itera = itera + 1
respuesta = c
# Valida respuesta
if (itera>=iteramax):
respuesta = np.nan
else:
print(' No existe cambio de signo entre f(a) y f(b)')
print(' f(a) =',fa,', f(b) =',fb)
respuesta=np.nan
tabla = np.array(tabla,dtype=float)
return(respuesta,tabla)
# PROGRAMA ----------------------
# INGRESO
fx = lambda x: x**3 + 4*x**2 - 10
a = 1
b = 2
tolera = 0.001
verdigitos = 4 # ver digitos en tabla
# PROCEDIMIENTO
c,tabla = biseccion(fx,a,b,tolera,
vertabla=True,
precision=verdigitos)
n = len(tabla)
errado = tabla[n-1,6]
# SALIDA
print('Método de la Bisección')
print('iteraciones:',n)
print('raíz en: ',c)
print('errado:',errado)
6. Gráfica en Python
La sección para la gráfica, contiene las variantes:
Las muestras para la gráfica de f(x), con la marca de un punto de la raíz.
Para el caso de realizar la gráfica de una iteración particular, usar la variable itera_graf. Por ejemplo para las gráficas presentadas en cada iteración en la sección de desarrollo analítico.
Las instrucciones que se añaden al algoritmo como función son:
# GRAFICA ---------------------
import matplotlib.pyplot as plt
muestras = 21 # en intervalo [a,b]
itera_graf = n-1 # iteración en gráfica
titulo = 'Bisección'
xk = np.linspace(a,b,muestras)
fk = fx(xk)
[ai,ci,bi] = tabla[itera_graf,0:3]
[fai,fci,fbi] = tabla[itera_graf,3:6]
plt.plot(xk,fk, label='f(x)')
if itera_graf==(n-1): # iteración final
plt.plot(c,0,'D',color='orange',label='c')
if itera_graf<(n-1): # una iteración en gráfica
titulo = titulo + ', itera='+str(itera_graf)
plt.plot(ai,fai,'o',color='red',label='a')
plt.plot(bi,fbi,'o',color='green',label='b')
plt.plot(ci,fci,'o',color='orange',label='c')
plt.plot([ai,ai],[fai,0],'--',color='red')
plt.plot([bi,bi],[fbi,0],'--',color='green')
plt.plot([ci,ci],[fci,0],'--',color='orange')
plt.axhline(0,color='gray')
plt.xlabel('x')
plt.ylabel('f(x)')
plt.title(titulo)
plt.grid()
plt.legend()
plt.tight_layout()
plt.show()
7. Función en librería Scipy.optimize.bisect
El método de la bisección se encuentra también implementado en las librería Scipy, que también puede ser usado de la forma:
>>> import scipy as sp
>>> fx = lambda x: x**3 + 4*x**2 - 10
>>> sp.optimize.bisect(fx,1,2,xtol=0.001)
1.3642578125que es el resultado de la raíz para la última iteración del ejercicio. Lo que muestra que el algoritmo realizado tiene un valor más aproximado.
Sin embargo por didáctica y mejor comprensión de los métodos y su implementación en algoritmos que es parte del objetivo de aprendizaje, se continuará desarrollando la forma básica y detallada con Python.
Referencia: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.bisect.html