El método de bisección es un método numérico para encontrar la raíz de un polinomio. En el método de bisección, llegamos iterativamente a la solución reduciéndola después de adivinar dos valores que encierran la solución real.
El método de bisección es lo mismo que adivinar el juego de números que podrías haber jugado en tu escuela, donde el jugador adivina el número y luego recibe una pista sobre si el número real es mayor o menor que la suposición. El jugador realiza un seguimiento de las pistas e intenta llegar al número real en un número mínimo de conjeturas. Aquí hay un juego de muestra (la solución es 4)
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|
Gameplay1: conjeturas aleatorias
- Adivina: 8 (pista: el número real es más bajo)
- Adivina: 2 (pista: el número real es mayor)
- Adivina: 7 (pista: el número real es más bajo)
- Adivina: 5 (pista: el número real es más bajo)
- Adivina: 4 (correcto)
Jugabilidad 2: Cortar en mitades
- Adivina: 5 (pista: el número real es más bajo)
- Adivina: 2 (pista: el número real es mayor)
- Adivina: 4 (correcto)
En los dos juegos anteriores, está claro que es mejor cortar la región delimitada por la mitad que hacer conjeturas a ciegas. El método de bisección usa la misma técnica para resolver una ecuación y se aproxima a la solución dividiendo la posible región de solución a la mitad y luego decidiendo qué lado contendrá la solución. Sugerencia: el lado donde la función se encuentra con el eje x es el lado a seguir. Los valores para los cuales la función da valores con signos opuestos encierra el punto donde la función se encuentra con el eje x.
Pasos
- Adivina primero los límites superior e inferior iniciales. (que debe incluir la solución real)
- Compruebe si los límites superior e inferior iniciales son correctos. Si la función da valores con signos opuestos para ambos valores, entonces los límites son correctos.
- iterativamente:
- Calcular el punto medio de los límites superior e inferior
- Calcule el valor de la función para los tres valores: límite inferior, límite superior y el punto medio
- Decide de qué lado ir. (El lado que contiene la solución/donde la función cambia de signo)
Reemplace el límite inferior o superior con el punto medio para dividir la región por la mitad. En otras palabras, elija lowerBound, midpoint o midpoint, upperBound como el nuevo lowerBound y upperBound - Repita hasta que el valor del punto medio alcance los lugares decimales deseados o la diferencia entre el límite superior e inferior sea menor que el error tolerable.
- Midpoint es su solución deseada.
Ejemplo
f(x) = x2 – 3
Sea a: límite inferior, b: límite superior y m: punto medio por brevedad.
Límites iniciales: a = 1 & b=2
un | b | fa) | pensión completa) | m = (a+b)/2 | f(m) | Elegir el lado | Error = ba |
---|---|---|---|---|---|---|---|
1.0 | 2.0 | -2.0 | 1.0 | 1.5 | -0.75 | un = metro | 0.5 |
1.5 | 2.0 | -0.75 | 1.0 | 1.75 | 0.062 | segundo = metro | 0.25 |
1.5 | 1.75 | -0.75 | 0.0625 | 1.625 | -0.359 | un = metro | 0.125 |
1.625 | 1.75 | -0.3594 | 0.0625 | 1.6875 | -0.1523 | un = metro | 0.0625 |
1.6875 | 1.75 | -0.1523 | 0.0625 | 1.7188 | -0.0457 | un = metro | 0.0313 |
1.7188 | 1.75 | -0.0457 | 0.0625 | 1.7344 | 0.0081 | segundo = metro | 0.0156 |
1.71988 | 1.7344 | -0.0457 | 0.0081 | 1.7266 | -0.0189 | un = metro | 0.0078 |
Ahora el error es tolerable, por lo que nuestra solución deseada es 1.7266
Este ejemplo fue simple, pero en la vida real se necesita una gran cantidad de iteraciones para llegar a la raíz deseada, por lo que usamos la computadora para ayudarnos.
0 # Convert into bool function
begin, end = test(x), test(x + step)
assert begin is not end # func(x) and func(x+step) must be on opposite sides
while abs(step) > prec:
step *= 0.5
if test(x + step) is not end: x += step
return xpy
—>
<!– Commmmmmmmmmment
def solve(func, x = 0.0, step = 1e3, prec = 1e-10): test = lambda x: func(x) > 0 # Convert into bool function begin, end = test(x), test(x + step) assert begin is not end # func(x) and func(x+step) must be on opposite sides while abs(step) > prec: step *= 0.5 if test(x + step) is not end: x += step return xpy
Created using ToHtml.com on 2019-02-08 20:05:41 UTC –>