Algoritmos

algoritmos de búsquedas con raíces

método de bisección es un algoritmo de búsqueda de raíces que trabaja dividiendo el intervalo a la mitad y seleccionando el subintervalo que tiene la raíz.

Unas cuantas iteraciones del método de bisección aplicadas en un intervalo [a₁;b₁]. El punto rojo es la raíz de la función.

Introducción

Este es uno de los métodos más sencillos y de fácil intuición para resolver ecuaciones en una variable, también conocido como Método de Intervalo Medio.¹ Se basa en el teorema del valor intermedio (TVI), el cual establece que toda función continua f en un intervalo cerrado [a,b] toma todos los valores que se hallan entre f(a) y f(b). Esto es que todo valor entre f(a) y f(b) es la imagen de al menos un valor en el intervalo [a,b]. En caso de que f(a) y f(b) tengan signos opuestos, el valor cero sería un valor intermedio entre f(j) y f(e), por lo que con certeza existe un p en [a,b] que cumple f(p)=0. De esta forma, se asegura la existencia de al menos una solución de la ecuación f(a)=0.

El método consiste en lo siguiente:

• Debe existir seguridad sobre la continuidad de la función f(x) en el intervalo [a,b]
• A continuación se verifica que ${\displaystyle \scriptstyle f(a)\cdot f(b)<0 annotation="">$
• Se calcula el punto medio m del intervalo [a,b] y se evalúa f(m) si ese valor es igual a cero, ya hemos encontrado la raíz buscada
• En caso de que no lo sea, verificamos si f(m) tiene signo opuesto con f(a) o con f(b)
• Se redefine el intervalo [a, b] como [a, m] ó [m, b] según se haya determinado en cuál de estos intervalos ocurre un cambio de signo
• Con este nuevo intervalo se continúa sucesivamente encerrando la solución en un intervalo cada vez más pequeño, hasta alcanzar la precisión deseada

En la siguiente figura se ilustra el procedimiento descrito.

El método de bisección es menos eficiente que el método de Newton, pero es mucho más seguro para garantizar la convergencia. Si f es una función continua en el intervalo [a, b] y f(a)f(b) < 0, entonces este método converge a la raíz de f. De hecho, una cota del error absoluto es:

${\displaystyle {\frac {\left|b-a\right|}{2^{n}}}}$

en la n-ésima iteración. La bisección converge linealmente, por lo cual es un poco lento. Sin embargo, se garantiza la convergencia si f(a) y f(b) tienen distinto signo.

Si existieran más de una raíz en el intervalo entonces el método sigue siendo convergente pero no resulta tan fácil caracterizar hacia qué raíz converge el método.

Algoritmo

Para aplicar el método consideremos tres sucesiones ${\displaystyle a_{n}\leq p_{n}\leq b_{n}\,}$ definidas por las siguientes relaciones:

${\displaystyle p_{n}={\frac {a_{n}+b_{n}}{2}},\quad a_{n+1}={\begin{cases}a_{n}&{\mbox{si }}f(a_{n})\cdot f(p_{n})<0 a_="" amp="" cdot="" f="" mbox="" n="" p_="" si="">0\end{cases}},\quad b_{n+1}={\begin{cases}b_{n}&{\mbox{si }}f(b_{n})\cdot f(p_{n})<0 amp="" b_="" cdot="" f="" mbox="" n="" p_="" si="">0\end{cases}}}$

Donde los valores iniciales vienen dados por:

${\displaystyle a_{0}:=a,\quad b_{0}:=b}$

Se puede probar que las tres sucesiones convergen al valor de la única raíz del intervalo:

${\displaystyle \lim _{n\to \infty }a_{n}=\lim _{n\to \infty }p_{n}=\lim _{n\to \infty }b_{n}}$

MÉTODO DE BISECCIÓN

Ver Animación...

Si f es una función continua sobre el intervalo [a,b] y si f(a) f(b)<0 class="Estilo1" entonces="" nbsp="" span="" style="font-family: "Times New Roman"; font-size: 14px; font-style: italic;">f

 debe tener un cero en (a,b). Dado que f(a)f(b)<0 cambia="" class="Estilo1" de="" el="" en="" funci="" intervalo="" la="" n="" signo="" span="" style="font-family: "Times New Roman"; font-size: 14px; font-style: italic;">a,b] y por lo tanto tiene por lo menos un cero en el intervalo. (Véase la figura 5.1)

Esta es una consecuencia del teorema del valor intermedio para funciones continuas, que establece que si f es continua en [a,b] y si k es un número entre f(a) y f(b) , entonces existe por lo menos un c  (a,b) tal que f(c)=k.
(para el caso en que f(a)f(b)<0 class="Estilo1" escoge="" nbsp="" se="" span="" style="font-family: "Times New Roman"; font-size: 14px; font-style: italic;">k

=0, luego f(c)=0, c  (a,b)).

El método de bisección consiste en dividir el intervalo en 2 subintervalos de igual magnitud, reteniendo el subintervalo en donde f cambia de signo, para conservar al menos una raíz o cero, y repetir el proceso varias veces.

Por ejemplo, suponga que f tiene un cero en el intervalo [a,b].

Primero se calcula el punto medio del intervalo ; después se averigua sí f(a)f(c)<0 .="" a="" c="" cero="" en="" entonces="" es="" f="" lo="" p="" si="" tiene="" un="">

A continuación se renombra a c como b y se comienza una vez más con el nuevo intervalo [a,b], cuya longitud es igual a la mitad del intervalo original.

Si f(a)f(c)>0 , entonces f(c)f(b)<0 a="" caso="" class="Estilo1" en="" este="" nbsp="" renombra="" se="" strong="" style="font-family: "Times New Roman"; font-size: 14px; font-style: italic;" y="">c

 como a.

En ambos casos se ha generado un nuevo intervalo que contiene un cero de f, y el proceso puede repetirse.

Ejemplo.

La función f(x) = xsenx – 1 tiene un cero en el intervalo [0,2], porque f(0) = -1 y f(2)=0.818595.

Si se denota con entonces c₁ = 1. Ahora f(c₁) = f(1) = -0.158529, luego la función tiene un cero en el intervalo [c₁, b₁] = [1,2] ; se renombra a₂=c₁ y b₂=b₁ .

El nuevo punto medio es  y f(c₂) = f(1.5) = 0.496242, el cero esta en el intervalo [a₂, c₂] y se renombra como [a₃,b₃].

En la tabla de abajo se muestran las primeras nueve iteraciones del método de bisección para f(x)= xsenx –1 con a=0 b=2.

n	Extremo izquierdo an	Extremo derecho bn	Punto medio cn	Valor de la función f(cn)	Error Relativo
1	0	2	1	-0.158529
2	1	2	1.5	0.496242	0.333333
3	1	1.5	1.25	0.186231	0.2
4	1	1.25	1.125	0.015051	0.111111
5	1	1.125	1.0625	-0.071827	0.0588235
6	1.0625	1.125	1.09375	-0.028362	0.0285714
7	1.09375	1.125	1.109375	-0.006643	0.0140845
8	1.1093750	1.125	1.1171875	0.004208	0.0069930
9	1.1093750	1.1171875	1.11328125	-0.001216	0.0035087

(c = 1.114157141 es el cero de f(x) = xsenx - 1)

Para detener el método de bisección y dar una aproximación del cero de una función se pueden usar varios criterios (llamados criterios de parada).
Uno de los criterios de parada consiste en examinar si |f(c_n)| < , donde  es una tolerancia previamente establecida (por ejemplo  = 10^-3). Otro criterio que puede utilizarse es examinar sí 
También se puede usar como criterio de parada el error relativo entre dos aproximaciones del cero de f , 
En el ejemplo anterior si  =0.005, el procedimiento se pararía en la octava iteración con el criterio |f(c_n)|<  , ya que:
         |f(c₈)| = |f(1.1171875)| = 0.004208 <  = 0.005,
pero si se usa el criterio  , el procedimiento se detendría en la novena iteración porque:

Cuando se generan aproximaciones por medio de una computadora, se recomienda fijar un número máximo de iteraciones N que debería realizar la máquina. Esto con el fin de contar con un resguardo para evitar la posibilidad de que el proceso de cálculo caiga en un ciclo infinito cuando la sucesión diverge (o cuando el programa no esta codificado correctamente). Un algoritmo para el método de bisección es:

Teorema. (Error en el método de bisección).
Si f es continua en [a, b] y f(a) f(b) < 0, el método de bisección genera una sucesión  que aproxima un cero c de f con la propiedad que:  , n 1 (Prueba)

Ejemplo.

Para determinar el número de iteraciones necesarias para aproximar el cero de f(x) = xsen x - 1 con una exactitud de 10^-2en el intervalo [0,2], se debe hallar un número n tal que:

 < 10^-2, es decir , n > 7.643...

se necesitan aproximadamente unas 8 iteraciones.

Observe en la tabla de aproximaciones que el cero de f(x) = xsen x - 1 es c=1.114157141 y c₈=1.1171875.
El error real es  = 0.003030359  3x10^-3.
El error real es menor que el error dado por el teorema; en la mayoría de casos la cota de error dada por el teorema es mayor que el número de iteraciones que realmente se necesitan. Para este ejemplo, = 0.004782141<10 sup="">-2

 = 0.01

Notas:

• El método de bisección tiene la desventaja que es lento en cuanto a convergencia (es decir que se necesita un n grande para que  sea pequeño). Otros métodos requieren menos iteraciones para alcanzar la misma exactitud, pero entonces no siempre se conoce una cota para la precisión.
  
• El método de bisección suele recomendarse para encontrar un valor aproximado del cero de una función, y luego este valor se refina por medio de métodos más eficaces. La razón es porque la mayoría de los otros métodos para encontrar ceros de funciones requieren un valor inicial cerca de un cero; al carecer de dicho valor, pueden fallar por completo.
  
• Resolver una ecuación en una variable como por ejemplo: xe^x=1 es equivalente a resolver la ecuación xe^x-1=0 , o a encontrar el cero de la función f(x) = xe^x-1. Para aproximar el cero de f o la raíz de la ecuación se puede hacer la gráfica de f en una calculadora o usar matlab para determinar un intervalo donde f tenga un cero. También se pueden ensayar números a y b de tal manera que f(a)f(b)<0 .="" caso="" class="Estilo1" de="" el="" nbsp="" para="" span="" style="font-family: "Times New Roman"; font-size: 14px; font-style: italic;">f

(x) = xe^x-1 por ejemplo f(0) = -1, f(1) = e-1 1.71828 entonces f tiene un cero en el intervalo [0,1].

Cuando hay raíces múltiples, el método de bisección quizá no sea válido, ya que la función podría no cambiar de signo en puntos situados a cualquier lado de sus raíces. Una gráfica es fundamental para aclarar la situación. En este caso sería posible hallar los ceros o raíces trabajando con la derivada f’(x), que es cero en una raíz múltiple.

El método de Graeffe se utiliza cuando es necesario calcular todas las raíces de una ecuación, sean reales o imaginarias (también es llamado método del cuadrado de las raíces). Es el único método práctico para calcular raíces imaginarias.

Las primeras ideas de este método se encuentran en los escritos de Waring en el siglo XVIII. Más tarde fue propuesto independientemente por Dandelin (1826) y Lobatchevsky (1834) ¹ un método para el cálculo de raíces basado en la misma idea, pero solo Eduard Heinrich Graeffe (1837) lo desarrollo en todos sus detalles.

Análisis

Sea ${\displaystyle f(x)=p_{0}+p_{1}x+p_{2}x^{2}+...+p_{n}x^{n}=0}$

La ecuación propuesta, con raíces ${\displaystyle a_{1},a_{2},...,a_{n}.}$.La primera parte del método, es un algoritmo para la formación de la ecuación con raíces ${\displaystyle a_{1}^{2},a_{2}^{2},...,a_{n}^{2}}$.

Sea ${\displaystyle f(x)=p_{n}(x-a_{1})(x-a_{2})...(x-a_{n}),}$

${\displaystyle (-1)^{n}f(-x)=p_{n}(x+a_{1})(x+a_{2})...(x+a_{n})}$

Multiplicando estas ecuaciones, miembro a miembro, tenemos:

${\displaystyle (-1)^{n}f(x)f(-x)=p_{n}^{2}(x^{2}-a_{1}^{2})(x^{2}-a_{2}^{2})...(x^{2}+a_{n}^{2})}$

Reemplazando ${\displaystyle x}$ por ${\displaystyle {\sqrt {x}}}$ , la ecuación pedida, de raíces ${\displaystyle a_{1}^{2},a_{2}^{2},...,a_{n}^{2}}$, se puede escribir de la siguiente manera.

${\displaystyle F(x)=f({\sqrt {x}})f(-{\sqrt {x}})}$

Entonces:

${\displaystyle f({\sqrt {x}})=p_{0}+p_{2}x+p_{4}x^{2}+...+{\sqrt {x}}(p_{1}+p_{3}x+p_{5}x^{2}+...),}$

${\displaystyle f(-{\sqrt {x}})=p_{0}+p_{2}x+p_{4}x^{2}+...-{\sqrt {x}}(p_{1}+p_{3}x+p_{5}x^{2}+...),}$

Y luego:

${\displaystyle F(x)=(p_{0}+p_{2}x+p_{4}x^{2}+...)^{2}-x(p_{1}+p_{3}x+p_{5}x^{2}+...)^{2}}$

Si ${\displaystyle x^{i}}$ en coeficiente de ${\displaystyle F(x)}$

${\displaystyle (-1)^{i}[p_{2}^{2}-2p_{i-1}p_{i+1}+2p_{i-2}p_{i+2}-...]}$

Escribiendo la ecuación original

${\displaystyle a_{0}x^{n}+a_{1}x^{n-1}+...+a_{n}=0}$

El coeficiente de ${\displaystyle x^{n-1}}$ esta en la ecuación tranformada, cuyas raíces son ${\displaystyle -a_{1}^{2};-a_{2}^{2};...;-a_{n}^{2}}$ y esta expresado por la suma ${\displaystyle a_{i}^{2}-2a_{i-1}a_{i+1}+2a_{i-2}a_{i+2}-...}$ que se continua mientras los índices no se hacen negativos o mayores a ${\displaystyle n}$ .

Raíces de un polinomio. Método de Graeffe

En esta página, se describe un procedimiento matemático ingenioso para hallar las raíces de un polinomio con gran exactitud. El método de Graeffe se presta especialmente a ser programado en el ordenador, constituyendo de por sí un ejercicio relevante, en lo que concierne a los aspectos generales del lenguaje Java: sentencias condicionales e iterativas, arrays unidimensionales y bidimensionales, descomposición de un problema en tareas que se codifican en forma de funciones, y finalmente, la encapsulación de los datos y las funciones para formar una clase.

En muchos campos de las matemáticas es necesario hallar las raíces de un polinomio, por ejemplo, para calcular la integral de una función racional, para calcular las raíces del polinomio característico que son los valores propios de una matriz, etc. Solamente existen fórmulas si el polinomio tiene un grado igual o inferior a cuatro. Excepto para los polinomios de primer y segundo grado, las fórmulas son complicadas, por lo que se emplean procesos de aproximación numérica. Entre los numerosos métodos que existen, el más conocido es quizá el método de Newton. Sin embargo, describiremos un método, realmente ingenioso, que nos proporciona gran exactitud en las raíces de un polinomio.

Sea el polinomio

a0xn+a1xn−1+a2xn−2+a3xn−3+ ... an−1x+an=0  (1)${\displaystyle a_0{x}^n+a_1{x}^{n-1}+a_2{x}^{n-2}+a_3{x}^{n-3}+\mathrm{...}{a}_{n-1}x+a_n=0(1)}$

Hacemos el polinomio más simple dividiendo todos los coeficientes por el primer término de modo que a₀ es siempre 1. Supongamos que sus raíces reales y distintas son

-r₁, -r₂, -r₃, ...-r_n

Al elevar al cuadrado el polinomio y agrupar los términos se obtiene un polinomio de grado 2n

a20(xn)2−(a21−2a2a0)(xn−1)2+(a22−2a1a3+2a4a0)(xn−2)2−(a23−2a2a4+2a1a5−2a6a0)(xn−3)2+ ...=0} (2)${\displaystyle \begin{array}{l}{a}_0^2{\left(x^n\right)}^2-(a_1^2-2a_2{a}_0){\left(x^{n-1}\right)}^2+(a_2^2-2a_1{a}_3+2a_4{a}_0){\left(x^{n-2}\right)}^2\\ -(a_3^2-2a_2{a}_4+2a_1{a}_5-2a_6{a}_0){\left(x^{n-3}\right)}^2+\mathrm{...}\text{=0}\end{array}\}(2)}$

Cuyas raíces serán

−r21,−r22,−r23 ... −r2n${\displaystyle -r_1^2,-r_2^2,-r_3^2\mathrm{...}-r_n^2}$

Hemos construido así una nueva ecuación cuyas raíces son numéricamente iguales a los cuadrados de las raíces de la ecuación original. Repitiendo el proceso, se pueden obtener ecuaciones cuyas raíces sean numéricamente iguales a las potencias cuarta, octava, decimosexta, etc. de las raíces de la ecuación original. El efecto de este proceso de elevar al cuadrado es el de producir ecuaciones cuyas raíces están cada vez más separadas. Por ejemplo, si dos raíces de la ecuación original están entre sí como 5 : 4 sus potencias 128 están en la razón 5¹²⁸ : 4¹²⁸, o sea, 2.54 10¹²: 1, lo que es muy deseable ya que las ecuaciones cuyas raíces están muy separadas se pueden resolver rápidamente con exactitud considerable. Supóngase ahora, que reiterando el proceso de elevación al cuadrado se llega a un polinomio

α0(xn)2m+α1(xn−1)2m+α2(xn−2)2m+α3(xn−3)2m+ ...=0  (3)${\displaystyle {\alpha }_0{\left(x^n\right)}^{2^m}+{\alpha }_1{\left(x^{n-1}\right)}^{2^m}+{\alpha }_2{\left(x^{n-2}\right)}^{2^m}+{\alpha }_3{\left(x^{n-3}\right)}^{2^m}+\mathrm{...}\text{=0}\text{(3)}}$

donde m es el número de veces que se repite el proceso de elevación al cuadrado. Así, si se repite siete veces el proceso de elevación al cuadrado, 2^m =2⁷ =128 sería el exponente al que estarían elevados las sucesivas potencias xⁿ, x^n-1, x^n-2, ... del polinomio. Sus raíces serán las del polinomio original elevadas al exponente 2^m.

−r2m1,−r2m2,−r2m3, ... −r2mn${\displaystyle -r_1^{2^m},-r_2^{2^m},-r_3^{2^m},\mathrm{...}-r_n^{2^m}}$

Por las relaciones conocidas entre raíces y coeficientes del polinomio, se tiene que

α0=1α1=-(suma de las raíces)=r2m1+r2m2+ ... +r2mnα2=(suma de las raíces tomando dos cada vez)=r2m1r2m2+r2m1r2m3+ ... +r2m2r2m3+ ... +r2mn−1r2mnα3=−(suma de las raíces tomando tres cada vez)=r2m1r2m2r2m3+r2m1r2m2r2m4+ ... +r2m2r2m3r2m4+ ... +r2mn−2r2mn−1r2mnαn=(−1)n(producto de todas las raíces)=r2m1r2m2r2m3 ... r2mn${\displaystyle \begin{array}{l}{\alpha }_0=1\\ {\alpha }_1=\text{-(suma de las raíces)}=r_1^{2^m}+r_2^{2^m}+\mathrm{...}+r_n^{2^m}\\ {\alpha }_2=\text{(suma de las raíces tomando dos cada vez)}=\\ r_1^{2^m}{r}_2^{2^m}+r_1^{2^m}{r}_3^{2^m}+\mathrm{...}+r_2^{2^m}{r}_3^{2^m}+\mathrm{...}+r_{n-1}^{2^m}{r}_n^{2^m}\\ {\alpha }_3=-\text{(suma de las raíces tomando tres cada vez)}=\\ r_1^{2^m}{r}_2^{2^m}{r}_3^{2^m}+r_1^{2^m}{r}_2^{2^m}{r}_4^{2^m}+\mathrm{...}+r_2^{2^m}{r}_3^{2^m}{r}_4^{2^m}+\mathrm{...}+r_{n-2}^{2^m}{r}_{n-1}^{2^m}{r}_n^{2^m}\\ {\alpha }_n={\left(-1\right)}^n\text{(producto de todas las raíces)}=r_1^{2^m}{r}_2^{2^m}{r}_3^{2^m}\mathrm{...}{r}_n^{2^m}\end{array}}$

En la suposición de que

|r1|>|r2|>|r3|> ... |rn|${\displaystyle \left|r_1\right|>\left|r_2\right|>\left|r_3\right|>\mathrm{...}\left|r_n\right|}$

y de que 2^m es grande por ejemplo 128 ó 256, se cumplirá que

|r1|2m>>>|r2|2m>>>|r3|2m>>> ... |rn|2m${\displaystyle {\left|r_1\right|}^{2^m}>>>{\left|r_2\right|}^{2^m}>>>{\left|r_3\right|}^{2^m}>>>\mathrm{...}{\left|r_n\right|}^{2^m}}$

donde el símbolo >>> indica mucho mayor que. Las relaciones entre coeficientes y raíces quedarán simplificadas con gran aproximación a las expresiones.

α0=1α1=r2m1α2=r2m1r2m2α3=r2m1r2m2r2m3αn=r2m1r2m2r2m3 ... r2mn${\displaystyle \begin{array}{l}{\alpha }_0=1\\ {\alpha }_1=r_1^{2^m}\\ {\alpha }_2=r_1^{2^m}{r}_2^{2^m}\\ {\alpha }_3=r_1^{2^m}{r}_2^{2^m}{r}_3^{2^m}\\ {\alpha }_n=r_1^{2^m}{r}_2^{2^m}{r}_3^{2^m}\mathrm{...}{r}_n^{2^m}\end{array}}$

Así, el módulo de r₁ se puede hallar extrayendo la raíz 2^m-ésima de α₁ . De la segunda ecuación se obtiene r₂, y así sucesivamente. La fórmula para obtener el módulo de la raíz r_i es

|ri|=αiαi−1−−−−√2m${\displaystyle \left|r_i\right|=\sqrt[2^m]{\frac{{\alpha }_i}{{\alpha }_{i-1}}}}$

En la práctica, hallamos el logaritmo de r_i, y luego, calculamos el antilogaritmo del resultado obtenido, de este modo se obtiene el valor absoluto de la raíz r_i.

log |ri|=log αi−log αi−12m(4)${\displaystyle \log \left|r_i\right|=\frac{\log {\alpha }_i-\log {\alpha }_{i-1}}{2^m}(4)}$

Para determinar el signo, se halla el valor del polinomio original para los valores r_i, y -r_i, uno de los dos hará que dicho valor sea próximo a cero y por tanto, será la raíz buscada.