Algoritmos

algoritmos de búsquedas de raíces

calcular la raíz cuadrada de un número real positivo, siendo el más conocido el método de resolución.

Método de resolución

Partes de la raíz cuadrada.

En la imagen podemos ver cinco partes esenciales de la raíz cuadrada en el método de resolución:

• 1- Radical, no es más que el símbolo que indica que es una raíz cuadrada.
• 2- Radicando, es el número al que se le obtendrá la raíz cuadrada.
• 3- Renglón de la raíz cuadrada, ahí se distinguirá el resultado.
• 4- Renglones auxiliares, nos ayudarán a resolver la raíz cuadrada.
• 5- Residuo, es el resto que queda luego de resolver la raíz cuadrada.

Los pasos a seguir son estos:

Paso 1.

• Paso 1: Se separa el número del radicado (en el ejemplo, 5836.3690) en grupos de dos cifras. La separación se hace desde el signo de decimal (si lo hubiera) hacia la derecha y hacia la izquierda. Si del lado de los decimales (a la derecha del punto, es decir 369) no hay un número par de cifras, es evidente que quedaría una suelta: en ese caso, se le añadiría un cero. Si del lado de los enteros (a la izquierda del punto, es decir, 5836) quedara un número suelto, se quedaría así. En la imagen de la derecha podemos ver el número 5836.369 dividido en grupos de dos cifras; después del número 9 se ha agregado un cero (en azul) pues en el lado decimal no puede haber un grupo de una cifra (en el ejemplo, esta separación quedaría así: 58/36.36/90)

Paso 2.

• Paso 2: Se busca un número que multiplicando por sí mismo (es decir, elevado al cuadrado) dé como resultado el número que coincida o que más se aproxime por debajo al primer grupo de números de la izquierda (en el ejemplo, 58). El resultado no puede ser mayor que 58. Una vez encontrado el número se agrega a la parte de la raíz. En este caso el número sería el 7, porque 7 x 7 es 49. Otra posibilidad sería 6 x 6, pero daría 36 (lo que quedaría más alejado de 58) y 8 x 8, pero daría 64 (lo que excedería a 58).

Paso 3.

• Paso 3: El número obtenido (7) es el primer resultado de la raíz cuadrada. En el paso anterior lo escribíamos en el cajetín de la derecha. Ahora lo multiplicamos por sí mismo. El resultado (49) se escribe debajo del primer grupo de cifras de la izquierda (58), y se procede a restarlo. El resultado de la resta (58-49) es 9. Una vez obtenido el resultado de la resta, se baja el siguiente grupo de dos cifras (36), con lo que la siguiente cifra de la raíz es ahora la unión del resultado de la resta anterior con las nuevas cifras bajadas (es decir, 936).Para continuar la extracción de la raíz cuadrada multiplicamos por 2 el primer resultado (7) y lo escribimos justo debajo de éste, en el siguiente renglón auxiliar (en la imagen, el 14 está escrito justo debajo del 7, ya que 7 x 2 es 14).

Paso 4.

• Paso 4: En este paso hay que encontrar un número n que, añadido a 14, y multiplicado por ese mismo n, de como resultado un número igual o inferior a 936. Es decir, podría ser 141 x 1, 142 x 2, 143 x 3... y así hasta 149 x 9. Muchas veces se utiliza el procedimiento de tanteo para hallar ese número, si bien se puede emplear el método de dividir las primeras dos cifras del residuo (93) entre el número del renglón auxiliar (14). La primera cifra del resultado que no sea cero, aunque sea un decimal, es, generalmente, la que buscamos. El resultado se agrega al número de la raíz y al del renglón auxiliar. En este caso 93 dividido entre 14 es 6. De manera que la operación buscada es 146 x 6 = 876 (operación que añadimos en el renglón auxiliar). El siguiente resultado de la raíz cuadrada es 6. También procedemos a anotarlo en el radicando.

Paso 5.

• Paso 5: El procedimiento es el mismo que anteriormente. El resultado de la operación anterior (876) se coloca debajo del número procedente de la resta anterior (936) y se restan. Al resultado de la resta (60) se le añade el siguiente grupo de cifras del radical (en este caso, 36). Si el siguiente grupo está después del punto decimal se agrega un punto decimal al número de la raíz. El nuevo número obtenido es 6036.

Paso 6.

• Paso 6: Se retoma el procedimiento del paso 3. La cifra de la raíz (76) se multiplica por dos (resultando 152). Buscamos un número que añadido a 152 y multiplicado por ese mismo número nos dé una cantidad aproximada a 6036. Sería, por tanto, 1521 x 1, 1522 x 2, 1523 x 3, etc. Se puede hacer por tanteo, o por el procedimiento de dividir en este caso, las tres primeras cifras de la raíz por las tres primeras cifras de la línea auxiliar (nótese que antes eran las dos primeras cifras), es decir, 603/152 (el número buscado es 3, ya que el resultado es 3.9 y se ha dicho que la cifra que se debe tomar es la primera). La operación a realizar es, por tanto, 1523 x 3. El resultado (4569) se coloca bajo el último resto y se procede a hallar la diferencia, que es 1467. Una vez realizada la resta se baja el siguiente grupo de cifras y se continúa el proceso. Obsérvese que el número a dividir entre renglón auxiliar y residuo va aumentado.

Paso 7.

• Paso 7: Se continúa el mismo proceso, la raíz se vuelve a multiplicar por dos (ignorando el punto de los decimales)(763 x 2 = 1526). El resultado de la multiplicación se agrega al tercer renglón auxiliar, se vuelven a dividir los primeros cuatro números del residuo (1467) entre el resultado de la multiplicación (1526),(nótese que son las primeras cuatro cifras, cuando antes eran las tres primeras), lo que nos da un resultado de 0.9 (como decíamos antes, se toma el primer número que no sea cero aunque sea decimal, por lo tanto, la cifra buscada es 9). El nueve se agrega en el renglón de la raíz y el tercer renglón auxiliar, y se multiplica 9 por 15269, lo que da un resultado de 137421, esta cifra se le resta a 146790 y nos da un resultado de 9369.

La raíz cuadrada de 5836.369 es 76.39, con un residuo de 0.9369. Recordemos que el cero es sólo un auxiliar. Es también que la operación anterior utilizada como ejemplo no está completa. Si la continuáramos daría como resultado 76.396132101 (con nueve decimales).

Los pasos se pueden resumir en ciclos de cuatro después de separar en grupos de dos cifras y teniendo en cuenta cuando se coloca el punto decimal en la raíz:

• 1) Hallar una nueva raíz.
• 2) Realizar la resta correspondiente.
• 3) Bajar un nuevo par del radicando.
• 4) Multiplicar raíz actual por dos.

Identidad exponencial

Las calculadoras de bolsillo típicamente implementan buenas rutinas para calcular la función exponencial y el logaritmo natural, entonces calculan la raíz cuadrada de ${\displaystyle x}$ utilizando la identidad

${\displaystyle {\sqrt {x}}=e^{{\frac {1}{2}}\ln x}}$ o ${\displaystyle {\sqrt {x}}=10^{{\frac {1}{2}}\log x}}$

La misma identidad es usada cuando se calculan las raíces cuadradas con tablas de logaritmos o reglas de cálculo.

Estimación imprecisa

Muchos de los métodos de cálculo para raíces cuadradas requieren un valor inicial. Si el valor inicial está muy lejos de la raíz cuadrada real, el cálculo será muy lento. Por lo tanto es útil tener un cálculo aproximado, que puede ser muy inexacto pero fácil de calcular. Una forma de obtener tal estimación para ${\displaystyle {\sqrt {x}}}$ está calculando ${\displaystyle 3^{D}}$, donde ${\displaystyle D}$ es el número de dígitos (a la izquierda del punto decimal) de ${\displaystyle x}$. Si ${\displaystyle x<1 annotation="">$, ${\displaystyle D}$ es el negativo del número de ceros a la derecha inmediata del punto decimal.

Un mejor método de estimación es éste:

• Si ${\displaystyle D}$ es impar (${\displaystyle D=2n+1}$), ${\displaystyle {\sqrt {x}}\approx 2\cdot 10^{n}}$
• Si ${\displaystyle D}$ es par (${\displaystyle D=2n+2}$), ${\displaystyle {\sqrt {x}}\approx 6\cdot 10^{n}}$

Al trabajar en el sistema de numeración binario (como lo hacen las computadoras internamente), un método alternativo es utilizar ${\displaystyle 2^{\left\lfloor D/2\right\rfloor }}$ (aquí D es el número de dígitos binarios).

Algoritmo babilónico

El algoritmo babilónico aproxima un rectángulo a cuadrado.

El algoritmo babilónico¹ se centra en el hecho de que cada lado de un cuadrado es la raíz cuadrada del área. Fue usado durante muchos años para calcular raíces cuadradas a mano debido a su gran eficacia y rapidez. Para calcular una raíz, dibuje un rectángulo cuya área sea el número al que se le busca raíz y luego aproxime la base y la altura del rectángulo hasta formar o por lo menos aproximar un cuadrado.

El algoritmo se puede enunciar sin el uso de dibujos como sigue:

Raíz(x):

1. Escoja dos números ${\displaystyle b}$ y ${\displaystyle h}$ tales que ${\displaystyle bh=x}$
2. Si ${\displaystyle h\approx b}$ vaya al paso 6, si no, vaya al paso 3
3. Asigne ${\displaystyle b\leftarrow {\frac {h+b}{2}}}$
4. Asigne ${\displaystyle h\leftarrow {\frac {x}{b}}}$
5. Vaya al paso 2
6. Escriba "${\displaystyle {\sqrt {x}}\approx b}$"

Diagrama de flujo del algoritmo babilónico.

Este algoritmo aproxima la raíz cuadrada de cualquier número real tanto como se desee. Es claro que no se necesita conocer el valor de ${\displaystyle h}$, puesto que depende directamente de ${\displaystyle x}$ y que el área del rectángulo siempre se aproxima a la raíz cuadrada de ${\displaystyle x}$ sin importar el valor de ${\displaystyle b}$ siempre y cuando ${\displaystyle b>0}$. De esta manera surge la función recursiva

${\displaystyle f_{0}(x)=x\,}$

${\displaystyle f_{n}(x)={\frac {1}{2}}\left({\frac {x}{f_{n-1}(x)}}+f_{n-1}(x)\right)}$

de manera tal que ${\displaystyle n}$ es la ${\displaystyle n}$-ésima aproximación a ${\displaystyle {\sqrt {x}}}$. Esto implica que

${\displaystyle f_{\infty }(x)={\sqrt {x}}}$

Puesto que algunas raíces son números irracionales es necesario definir qué tanto es "aproximadamente". Afortunadamente nadie es capaz de escribir un número con una infinita cantidad de dígitos, por lo que el umbral de aproximación se limita a la cantidad de dígitos que se es capaz de escribir. Entonces podemos definir que el algoritmo termine en el momento que la última aproximación es la misma que la anterior (es decir, ya no se puede aproximar más).

Descripción formal

De manera formal, se expresa el algoritmo babilónico usando pseudocódigo de la siguiente manera:

función ${\displaystyle \mathrm {raiz} (x)\,}$ ${\displaystyle r\leftarrow x}$ ${\displaystyle t\leftarrow 0}$ mientras ${\displaystyle t\neq r}$ ${\displaystyle t\leftarrow r}$ ${\displaystyle r\leftarrow {\frac {1}{2}}\left({\frac {x}{r}}+r\right)}$ devolver ${\displaystyle r\,}$

donde ${\displaystyle x\leftarrow y}$ significa "sustituya el valor de ${\displaystyle x}$ por del de ${\displaystyle y}$", y devolver expresa el resultado del algoritmo y su terminación.

Fracciones continuas periódicas

Los irracionales cuadráticos (números de la forma ${\displaystyle {\frac {a+{\sqrt {b}}}{c}}}$, donde a, b y c son enteros), y en particular, las raíces cuadradas de números enteros, tienen fracciones continuas periódicas. Podemos estar interesados a veces no en encontrar el valor numérico de una raíz cuadrada, sino por algo en su expansión como fracción continua. El algoritmo iterativo siguiente se puede utilizar para este propósito (S es cualquier número natural que no sea un cuadrado perfecto):

${\displaystyle m_{0}=0\,\!}$

${\displaystyle d_{0}=1\,\!}$

${\displaystyle a_{0}=\left\lfloor {\sqrt {S}}\right\rfloor \,\!}$

${\displaystyle m_{n+1}=d_{n}a_{n}-m_{n}\,\!}$

${\displaystyle d_{n+1}={\frac {S-m_{n+1}^{2}}{d_{n}}}\,\!}$

${\displaystyle a_{n+1}=\left\lfloor {\frac {{\sqrt {S}}+m_{n+1}}{d_{n+1}}}\right\rfloor =\left\lfloor {\frac {a_{0}+m_{n+1}}{d_{n+1}}}\right\rfloor \!.}$

Hay que notar que m_n, d_n, y a_n son siempre enteros. El algoritmo termina cuando en este trío el resultado nuevo que obtenemos ya empieza a ser igual al anterior. La expansión se repetirá entonces. La secuencia [a₀; a₁, a₂, a₃, …] es la expansión fracción continua:

${\displaystyle {\sqrt {S}}=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+\,\cdots }}}}}}}$

Ejemplo, raíz cuadrada de 114 como una fracción continua

Comenzamos con m₀=0; d

Ahora de enlaza de nuevo con la segunda ecuación de arriba.

Por lo tanto, la fracción continua para la raíz cuadrada de 114 es: ${\displaystyle {\sqrt {114}}=[10;1,2,10,2,1,20,1,2,10,2,1,20,1,2,10,2,1,20,...].}$

Aproximación de Bakhshali

Este método para encontrar una aproximación a la raíz cuadrada fue descrito en un manuscrito antiguo llamado manuscrito de Bakhshali. Equivale a dos iteraciones del método babilónico comenzando con el número ${\displaystyle n}$ tal que ${\displaystyle n^{2}}$ es el cuadrado más cercano a ${\displaystyle x}$.

${\displaystyle {\sqrt {x}}\approx {\frac {n^{4}+6n^{2}x+x^{2}}{4n^{3}+4nx}}}$

Ejemplo con la raíz cuadrada de 10.5

Si queremos calcular ${\displaystyle {\sqrt {10.5}}}$ con este método lo primero que hacemos es asignarle el número cuadrado perfecto cuyo cuadrado se acerque más a 10.5, ese número va a ser 3, ya que al dar ${\displaystyle 3^{2}\,\!}$ como resultado 9 se acerca más a 10.5 que ${\displaystyle 4^{2}\,\!}$ que da 16, con lo que ahora en la igualdad sustituimos:

${\displaystyle {\sqrt {10.5}}\approx {\frac {3^{4}+6\times 3^{2}\times 10.5+10.5^{2}}{4\times 3^{3}+4\times 3\times 10.5}}}$

${\displaystyle {\sqrt {10.5}}\approx {\frac {81+567+110.25}{108+126}}}$

${\displaystyle {\sqrt {10.5}}\approx {\frac {758.25}{234}}\approx 3.240384615}$

Siendo las cifras 384615 periódicas.

Este método da un valor bastante aproximado de la raíz cuadrada del número, se puede observar también que este método al dar el resultado mediante una fracción da un número racional, mientras que la raíz cuadrada real de un número es irracional siempre que este no sea un cuadrado perfecto (o el cociente de dos cuadrados perfectos).

Series de Taylor

Si N es una aproximación a ${\displaystyle {\sqrt {S}}}$, una aproximación mejor puede ser encontrada usando la serie de Taylor de la función de la raíz cuadrada:

${\displaystyle {\sqrt {N^{2}+d}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}(2n)!d^{n}}{(1-2n)n!^{2}4^{n}N^{2n-1}}}=N+{\frac {d}{2N}}-{\frac {d^{2}}{8N^{3}}}+{\frac {d^{3}}{16N^{5}}}-{\frac {5d^{4}}{128N^{7}}}+\cdots }$

Como método iterativo, el orden de convergencia es igual al número de los términos usados. Con 2 términos, es idéntica al método babilónico; con 3 términos, cada iteración toma casi tantas operaciones como la aproximación de Bakhshali, pero converge más lentamente. Por lo tanto, esta no es una manera particularmente eficiente de la operación.

método de la regula falsi (regla del falso) o falsa posición es un método iterativo de resolución numérica de ecuaciones no lineales. El método combina el método de bisección y el método de la secante.

El método

Las primeras dos iteraciones de regula falsi. La curva roja muestra la función f; las líneas azules, las secantes.

Como en el método de bisección, se parte de un intervalo inicial [a₀,b₀] con f(a₀) y f(b₀) de signos opuestos, lo que garantiza que en su interior hay al menos una raíz (véase Teorema de Bolzano). El algoritmo va obteniendo sucesivamente en cada paso un intervalo más pequeño [a_k, b_k] que sigue incluyendo una raíz de la función f.

A partir de un intervalo [a_k, b_k] se calcula un punto interior c_k:

${\displaystyle c_{k}={\frac {f(b_{k})a_{k}-f(a_{k})b_{k}}{f(b_{k})-f(a_{k})}}}$

Dicho punto es la intersección de la recta que pasa por (a,f(a_k)) y (b,f(b_k)) con el eje de abscisas (igual a como se hace en el método de la secante).

Se evalúa entonces f(c_k). Si es suficientemente pequeño, c_k es la raíz buscada. Si no, el próximo intervalo [a_k+1, b_k+1] será:

• [a_k, c_k] si f(a_k) y f(c_k) tienen signos opuestos;
• [c_k, b_k] en caso contrario.

Análisis del método

Se puede demostrar que bajo ciertas condiciones el método de la falsa posición tiene orden de convergencia lineal, por lo que suele converger más lentamente a la solución de la ecuación que el método de la secante, aunque el método de la falsa posición siempre converge a una solución de la ecuación.

El algoritmo tiene el inconveniente de que si la función es convexa o cóncava cerca de la solución, el extremo del intervalo más alejado de la solución queda fijo variando únicamente el más cercano, convergiendo muy lentamente.

Un ejemplo de este fenómeno se da en la función:

${\displaystyle f(x)=2x^{3}-4x^{2}+3x\,}$

comenzando con [−1,1]. El extremo izquierdo del intervalo, −1, nunca cambia; el extremo derecho se aproxima a 0 linealmente.

La situación en que el método falla es fácil de detectar (el mismo extremo del intervalo se elige dos veces seguidas) y fácil de corregir eligiendo un c_k diferente, como:

${\displaystyle c_{k}={\frac {{\frac {1}{2}}f(b_{k})a_{k}-f(a_{k})b_{k}}{{\frac {1}{2}}f(b_{k})-f(a_{k})}}}$

o

${\displaystyle c_{k}={\frac {f(b_{k})a_{k}-{\frac {1}{2}}f(a_{k})b_{k}}{f(b_{k})-{\frac {1}{2}}f(a_{k})}}}$

restándole peso a uno de los extremos del intervalo para obligar a que el próximo c_k ocurra de ese lado de la función.

El factor 2 usado arriba, garantiza una convergencia superlineal (asintóticamente, el algoritmo ejecuta dos pasos normales por cada paso modificado). Hay otras formas que dan incluso mejores tasas de convergencia. El ajuste mencionado arriba, y otras modificaciones similares se conocen como Algoritmo Illinois. Ford¹ resume y analiza las variantes superlineales del método regula falsi modificado. A juzgar por la bibliografía, estos métodos eran bien conocidos en los años 1970 pero han sido olvidados en los textos actuales.