Solución Aproximada de Ecuaciones de una Variable
Uno de los problemas más básicos de la aproximación numérica, el cálculo de raíces. Esto supone la determinación de una raíz, o solución, de una ecuación de la forma f (x) = 0. Las raíces de esta ecuación también se llaman ceros de la función f . Aunque éste es uno de los problemas de aproximación más antiguos, se trata de un área en la que continúa investigándose abundantemente.
El problema de hallar una aproximación a la raíz de una ecuación puede remontarse por lo menos hasta una época tan lejana como el año 1700 a. C. Una tablilla cuneiforme de la Yale Babylonian Collection, que data de ese período, da un número sexagesimal (en base 60) que es equivalente a 1.414222 como aproximación de √2, un resultado que tiene una precisión de 10−5. Esta aproximación puede calcularse aplicando la técnica.
El Método de Bisección
La primera, y más elemental, técnica que consideramos es el método de Bisección, o de Búsqueda Binaria. El método de Bisección se emplea para determinar, con toda la precisión que el ordenador permita, una solución de f (x) = 0 en un intervalo [a, b], supuesto que f es continua en dicho intervalo y que f (a) y f (b) tienen signos distintos.
Aunque el método funciona en el caso en que hay más de una raíz en el intervalo [a, b], supondremos para facilitar nuestra argumentación que la raíz en dicho intervalo es única.
Para empezar el método de Bisección, pongamos a1 = a y b1 = b, y sea p1 el punto medio del intervalo [a, b]:
2
.
Si f (p1) = 0, entonces la raíz p viene dada por p = p1; si f (p1) 6= 0, entonces f (p1) tiene el mismo signo que f (a1) o que f (b1). Si f (p1) y f (a1) tienen el mismo signo, entonces p está en el intervalo (p1, b1) y
Tomamos si, por el contrario, f (p1) y f (a1) tienen distinto signo, entonces p está en el intervalo (a1, p1) y tomamos
a2 = a1 y b2 = p1.
Aplicamos el mismo proceso en el intervalo [a2, b2] y continuamos formando [a3, b3], [a4, b4]. Cada nuevo intervalo sigue conteniendo la raíz p y su longitud es la mitad de la longitud del intervalo precedente.
Hay tres criterios de parada que se suelen incorporar al método de Bisección. El primero es detener el método si uno de los puntos medios coincide con la raíz. El segundo es detener el método cuando la longitud del intervalo es menor que una tolerancia prescrita que llamaremos TOL. Finalmente, el método también se detendrá si el número de iteraciones excede una cota máxima N0 dada de antemano.
Para que podamos aplicar el método de Bisección, necesitamos encontrar un intervalo [a, b] en el que f (a) · f (b) < 0. En cada paso, la longitud del intervalo en el que sabemos que hay un cero de f se reduce a la mitad. Puesto que el punto medio p1 debe distar de la raíz p menos de (b − a)/2 y en cada iteración subsiguiente se divide el intervalo en cuestión por la mitad, tenemos
En consecuencia, es fácil determinar una cota del número de iteraciones necesario para garantizar una tolerancia dada. Si se requiere que la raíz sea calculada con una precisión TOL, debemos determinar el número de iteraciones n de manera que
Puesto que el número de iteraciones que se requieren para garantizar un precisión dada depende de la longitud del intervalo inicial [a, b], es deseable elegir este intervalo lo más pequeño posible.
Por ejemplo, para f (x) = 2x3 − x2 + x − 1 tenemos tanto f (−4) · f (4) < 0 como f (0) · f (1) < 0, así que el método de Bisección podría usarse tanto en [−4, 4] como en [0, 1]. Sin embargo, empezar el método en [0, 1] en vez de en [−4, 4] disminuye en 3 el número de iteraciones requerido para alcanzar el grado de precisión preestablecido.
Compiladores:
- Mayra Ávila
- Fernando Castillo
- Gabriela Narváez
