El método de bisección, conocido también como de corte binario, de partición de intervalos o de Bolzano, es un método de búsqueda incremental en el que el intervalo se divide siempre a la mitad.
grafico $$ \begin{equation} x_{raiz} = \frac{x_{inferior} + x_{superior}}{2} \tag{1} \end{equation} $$
Algoritmo
la raiz verdadera está en el intervalo [x_inferior, x_superior]
calcular x_raiz
si f(x_inferior)*f(x_raiz) < 0
la raiz verdadera está en el intervalo [x_inferior, x_raiz]
calcular x_raiz
si f(x_inferior)*f(x_raiz) > 0
la raiz verdadera está en el intervalo [x_raiz, x_superior]
calcular x_raiz
si f(x_inferior)*f(x_raiz) = 0
se encontró la raiz verdadera
Encontrar la raiz de $$ \begin{equation*} y = x^{3} + 4 x^{2} - 10 \end{equation*} $$
la raíz posiblemente se encuentre en \( [x_{l}, x_{u}] = [1,2] \)
Iteración 0
Intervalo actual $$ \begin{equation*} [x_{l_{0}}, x_{u_{0}}] = [1, 2] \end{equation*} $$
Raíz aproximada $$ \begin{equation*} x_{r_{0}} = \frac{x_{l_{0}} + x_{u_{0}}}{2} = \frac{1 + 2}{2} = 1.5 \end{equation*} $$
Siguiente intervalo $$ \begin{equation*} [x_{l_{1}}, x_{u_{1}}] = \left \{ \begin{array}{llcll} si & f(x_{l_{0}}) \cdot f(x_{r_{0}}) = f(1) \cdot f(1.5) < 0 & \longrightarrow & [x_{l_{0}}, x_{r_{0}}] = [1, 1.5] & \checkmark \\ si & f(x_{l_{0}}) \cdot f(x_{r_{0}}) = f(1) \cdot f(1.5) > 0 & \longrightarrow & [x_{r_{0}}, x_{u_{0}}] = [1.5, 2] & \end{array} \right . \end{equation*} $$
Error relativo $$ \begin{equation*} e_{r} = ? \end{equation*} $$
Iteración 1
Intervalo actual $$ \begin{equation*} [x_{l_{1}}, x_{u_{1}}] = [1.5, 2] \end{equation*} $$
Raíz aproximada $$ \begin{equation*} x_{r_{1}} = \frac{x_{l_{1}} + x_{u_{1}}}{2} = \frac{1 + 1.5}{2} = 1.25 \end{equation*} $$
Siguiente intervalo $$ \begin{equation*} [x_{l_{2}}, x_{u_{2}}] = \left \{ \begin{array}{llcll} si & f(x_{l_{1}}) \cdot f(x_{r_{1}}) = f(1) \cdot f(1.25) < 0 & \longrightarrow & [x_{l_{1}}, x_{r_{1}}] = [1, 1.25] & \\ si & f(x_{l_{1}}) \cdot f(x_{r_{1}}) = f(1) \cdot f(1.25) > 0 & \longrightarrow & [x_{r_{1}}, x_{u_{1}}] = [1.25, 1.5] & \checkmark \end{array} \right . \end{equation*} $$
Error relativo $$ \begin{equation*} e_{r} = \bigg|\frac{x_{r_{1}} - x_{r_{0}}}{x_{r_{1}}}\bigg| \times 100\% = \bigg|\frac{1.25 - 1.5}{1.25}\bigg| \times 100\% = 20\% \end{equation*} $$
Iteración 2
Intervalo actual $$ \begin{equation*} [x_{l_{2}}, x_{u_{2}}] = [1.25, 1.5] \end{equation*} $$
Raíz aproximada $$ \begin{equation*} x_{r_{2}} = \frac{x_{l_{2}} + x_{u_{2}}}{2} = \frac{1.25 + 1.5}{2} = 1.375 \end{equation*} $$
Siguiente intervalo $$ \begin{equation*} [x_{l_{3}}, x_{u_{3}}] = \left \{ \begin{array}{llcll} si & f(x_{l_{2}}) \cdot f(x_{r_{2}}) = f(1.25) \cdot f(1.375) < 0 & \longrightarrow & [x_{l_{2}}, x_{r_{2}}] = [1.25, 1.375] & \checkmark \\ si & f(x_{l_{2}}) \cdot f(x_{r_{2}}) = f(1.25) \cdot f(1.375) > 0 & \longrightarrow & [x_{r_{2}}, x_{u_{2}}] = [1.375, 1.5] & \end{array} \right . \end{equation*} $$
Error relativo $$ \begin{equation*} e_{r} = \bigg|\frac{x_{r_{2}} - x_{r_{1}}}{x_{r_{2}}}\bigg| \times 100\% = \bigg|\frac{1.375 - 1.25}{1.375}\bigg| \times 100\% = 9.09\% \end{equation*} $$
Iteración 3
Intervalo actual $$ \begin{equation*} [x_{l_{3}}, x_{u_{3}}] = [1.25, 1.375] \end{equation*} $$
Raíz aproximada $$ \begin{equation*} x_{r_{3}} = \frac{x_{l_{3}} + x_{u_{3}}}{2} = \frac{1.25 + 1.375}{2} = 1.3125 \end{equation*} $$
Siguiente intervalo $$ \begin{equation*} [x_{l_{4}}, x_{u_{4}}] = \left \{ \begin{array}{llcll} si & f(x_{l_{3}}) \cdot f(x_{r_{3}}) = f(1.25) \cdot f(1.3125) < 0 & \longrightarrow & [x_{l_{3}}, x_{r_{3}}] = [1.25, 1.3125] & \\ si & f(x_{l_{3}}) \cdot f(x_{r_{3}}) = f(1.25) \cdot f(1.3125) > 0 & \longrightarrow & [x_{r_{3}}, x_{u_{3}}] = [1.3125, 1.375] & \checkmark \end{array} \right . \end{equation*} $$
Error relativo $$ \begin{equation*} e_{r} = \bigg| \frac{x_{r_{3}} - x_{r_{2}}}{x_{r_{3}}} \bigg| \times 100\% = \bigg|\frac{1.3125 - 1.375}{1.3125}\bigg| \times 100\% = 4.76\% \end{equation*} $$
Seudocódigo para calcular la raíz
function raiz(x_l, x_u)
x_r = (x_l + x_u)/2
return x_r
end function
Seudocódigo para determinar el siguiente intervalo
function intervalo_de_raiz(f(x), x_l, x_u)
x_r = raiz(x_l, x_u)
if f(x_l)*f(x_r) < 0
x_u = x_r
end if
if f(x_l)*f(x_r) > 0
x_l = x_r
end if
return x_l, x_u
end function
def raiz(x_l, x_u):
x_r = (x_l + x_u)/2
return x_r
def intervalo_de_raiz(f, x_l, x_u):
x_r = raiz(x_l, x_u)
if f(x_l)*f(x_r) < 0:
x_u = x_r
if f(x_l)*f(x_r) > 0:
x_l = x_r
return x_l, x_u
Seudocódigo
function biseccion(f(x), x_inferior, x_superior)
x_raiz_actual = raiz(x_inferior, x_superior)
error_permitido = 0.000001
while(True)
x_raiz_anterior = x_raiz_actual
x_inferior, x_superior = intervalo_de_raiz(f(x), x_inferior, x_superior)
x_raiz_actual = raiz(x_inferior, x_superior)
if x_raiz_actual != 0
error_relativo = abs((x_raiz_actual - x_raiz_anterior)/x_raiz_actual)*100
end if
if error_relativo < error_permitido
exit
end if
end while
mostrar x_raiz_actual
end function
O también
function biseccion(f(x), x_inferior, x_superior)
x_raiz_actual = raiz(x_inferior, x_superior)
for 1 to maxima_iteracion do
x_raiz_anterior = x_raiz_actual
x_inferior, x_superior = intervalo_de_raiz(f(x), x_inferior, x_superior)
x_raiz_actual = raiz(x_inferior, x_superior)
end for
mostrar x_raiz_actual
end function
def biseccion(f, x_inferior, x_superior):
print("{0:2s}\t{1:12s}\t{2:12s}\t{3:12s}\t{4:16s}".format(' i', 'x inferior', 'x superior', 'raiz', 'error relativo %'))
x_raiz_actual = raiz(x_inferior, x_superior)
i = 0
print("{0:2d}\t{1:12.10f}\t{2:12.10f}\t{3:12.10f}\t{4:16s}".format(i, x_inferior, x_superior, x_raiz_actual, '????????????????'))
error_permitido = 0.000001
while True:
x_raiz_anterior = x_raiz_actual
x_inferior, x_superior = intervalo_de_raiz(f, x_inferior, x_superior)
x_raiz_actual = raiz(x_inferior, x_superior)
if x_raiz_actual != 0:
error_relativo = abs((x_raiz_actual - x_raiz_anterior)/x_raiz_actual)*100
i = i + 1
print("{0:2d}\t{1:12.10f}\t{2:12.10f}\t{3:12.10f}\t{4:16.13f}".format(i, x_inferior, x_superior, x_raiz_actual, error_relativo))
if (error_relativo < error_permitido) or (i>=20):
break
print('\nx =', x_raiz_actual)
Encontrar la raiz de $$ \begin{equation*} y = x^{3} + 4 x^{2} - 10 \end{equation*} $$
la raíz posiblemente se encuentre en el intervalo \( [1,2] \)
def f(x):
y = x**3 + 4*x**2 - 10
return y
intervalo_de_raiz(f, 1, 2)
(1, 1.5)
intervalo_de_raiz(f, 1, 1.5)
(1.25, 1.5)
intervalo_de_raiz(f, 1.25, 1.5)
(1.25, 1.375)
biseccion(f, 1, 2)
i x inferior x superior raiz error relativo %
0 1.0000000000 2.0000000000 1.5000000000 ????????????????
1 1.0000000000 1.5000000000 1.2500000000 20.0000000000000
2 1.2500000000 1.5000000000 1.3750000000 9.0909090909091
3 1.2500000000 1.3750000000 1.3125000000 4.7619047619048
4 1.3125000000 1.3750000000 1.3437500000 2.3255813953488
5 1.3437500000 1.3750000000 1.3593750000 1.1494252873563
6 1.3593750000 1.3750000000 1.3671875000 0.5714285714286
7 1.3593750000 1.3671875000 1.3632812500 0.2865329512894
8 1.3632812500 1.3671875000 1.3652343750 0.1430615164521
9 1.3632812500 1.3652343750 1.3642578125 0.0715819613457
10 1.3642578125 1.3652343750 1.3647460938 0.0357781753131
11 1.3647460938 1.3652343750 1.3649902344 0.0178858880343
12 1.3649902344 1.3652343750 1.3651123047 0.0089421443262
13 1.3651123047 1.3652343750 1.3651733398 0.0044708722672
14 1.3651733398 1.3652343750 1.3652038574 0.0022353861630
15 1.3652038574 1.3652343750 1.3652191162 0.0011176805892
16 1.3652191162 1.3652343750 1.3652267456 0.0005588371716
17 1.3652267456 1.3652343750 1.3652305603 0.0002794178051
18 1.3652267456 1.3652305603 1.3652286530 0.0001397090977
19 1.3652286530 1.3652305603 1.3652296066 0.0000698545001
20 1.3652296066 1.3652305603 1.3652300835 0.0000349272378
x = 1.3652300834655762
Encontrar la raiz de $$ \begin{equation*} y = \sin{10 x} + \cos{3 x} \end{equation*} $$
la raíz posiblemente se encuentre en el intervalo \( [14,15] \)
from math import sin, cos
def g(x):
y = sin(10*x) + cos(3*x)
return y
intervalo_de_raiz(g, 14, 15)
(14.5, 15)
intervalo_de_raiz(g, 14.5, 15)
(14.75, 15)
intervalo_de_raiz(g, 14.75, 15)
(14.75, 14.875)
biseccion(g, 14, 15)
i x inferior x superior raiz error relativo %
0 14.0000000000 15.0000000000 14.5000000000 ????????????????
1 14.5000000000 15.0000000000 14.7500000000 1.6949152542373
2 14.7500000000 15.0000000000 14.8750000000 0.8403361344538
3 14.7500000000 14.8750000000 14.8125000000 0.4219409282700
4 14.8125000000 14.8750000000 14.8437500000 0.2105263157895
5 14.8437500000 14.8750000000 14.8593750000 0.1051524710831
6 14.8593750000 14.8750000000 14.8671875000 0.0525486074619
7 14.8593750000 14.8671875000 14.8632812500 0.0262812089356
8 14.8593750000 14.8632812500 14.8613281250 0.0131423314496
9 14.8613281250 14.8632812500 14.8623046875 0.0065707339510
10 14.8613281250 14.8623046875 14.8618164062 0.0032854749154
11 14.8618164062 14.8623046875 14.8620605469 0.0016427104723
12 14.8620605469 14.8623046875 14.8621826172 0.0008213484900
13 14.8620605469 14.8621826172 14.8621215820 0.0004106759315
14 14.8621215820 14.8621826172 14.8621520996 0.0002053375441
15 14.8621215820 14.8621520996 14.8621368408 0.0001026688775
16 14.8621368408 14.8621520996 14.8621444702 0.0000513344124
17 14.8621444702 14.8621520996 14.8621482849 0.0000256671996
18 14.8621482849 14.8621520996 14.8621501923 0.0000128335982
19 14.8621482849 14.8621501923 14.8621492386 0.0000064167995
20 14.8621492386 14.8621501923 14.8621497154 0.0000032083996
x = 14.862149715423584
Encontrar la raiz de $$ \begin{equation*} y = \sin{10 x} + \cos{3 x} \end{equation*} $$
la raíz posiblemente se encuentre en el intervalo \( [12,16] \)
biseccion(g, 12, 16)
i x inferior x superior raiz error relativo %
0 12.0000000000 16.0000000000 14.0000000000 ????????????????
1 14.0000000000 16.0000000000 15.0000000000 6.6666666666667
2 14.0000000000 15.0000000000 14.5000000000 3.4482758620690
3 14.5000000000 15.0000000000 14.7500000000 1.6949152542373
4 14.7500000000 15.0000000000 14.8750000000 0.8403361344538
5 14.7500000000 14.8750000000 14.8125000000 0.4219409282700
6 14.8125000000 14.8750000000 14.8437500000 0.2105263157895
7 14.8437500000 14.8750000000 14.8593750000 0.1051524710831
8 14.8593750000 14.8750000000 14.8671875000 0.0525486074619
9 14.8593750000 14.8671875000 14.8632812500 0.0262812089356
10 14.8593750000 14.8632812500 14.8613281250 0.0131423314496
11 14.8613281250 14.8632812500 14.8623046875 0.0065707339510
12 14.8613281250 14.8623046875 14.8618164062 0.0032854749154
13 14.8618164062 14.8623046875 14.8620605469 0.0016427104723
14 14.8620605469 14.8623046875 14.8621826172 0.0008213484900
15 14.8620605469 14.8621826172 14.8621215820 0.0004106759315
16 14.8621215820 14.8621826172 14.8621520996 0.0002053375441
17 14.8621215820 14.8621520996 14.8621368408 0.0001026688775
18 14.8621368408 14.8621520996 14.8621444702 0.0000513344124
19 14.8621444702 14.8621520996 14.8621482849 0.0000256671996
20 14.8621482849 14.8621520996 14.8621501923 0.0000128335982
x = 14.862150192260742