AMIGOS PARA SIEMPRE: Algoritmos

Algoritmos de búsqueda de raíces

método de la secante es un método para encontrar los ceros de una función de forma iterativa.

Es una variación del método de Newton-Raphson donde en vez de calcular la derivada de la función en el punto de estudio, teniendo en mente la definición de derivada, se aproxima la pendiente a la recta que une la función evaluada en el punto de estudio y en el punto de la iteración anterior. Este método es de especial interés cuando el coste computacional de derivar la función de estudio y evaluarla es demasiado elevado, por lo que el método de Newton no resulta atractivo.

En otras palabras, el método de la secante es un algoritmo de la raíz de investigación que utiliza una serie de raíces de las líneas secantes para aproximar mejor la raíz de una función f. El método de la secante se puede considerar como una aproximación en diferencias finitas del método de Newton-Raphson. Sin embargo, este método fue desarrollado independientemente de este último.

Dos primeras iteraciones del método de la secante.

El método

El método se define por la relación de recurrencia:

x_{n+1} = x_n - \frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})} f(x_n).

Como se puede ver, este método necesitará dos aproximaciones iniciales de la raíz para poder inducir una pendiente inicial.

Derivación del método

El método se basa en obtener la ecuación de la recta que pasa por los puntos (x_n−1, f(x_n−1)) y (x_n, f(x_n)). A dicha recta se le llama secante por cortar la gráfica de la función. En la imagen de arriba a la derecha se toman los puntos iniciales x₀ y x₁, se construye una línea por los puntos (x₀, f(x₀)) y (x₁, f(x₁)). En forma punto-pendiente, esta línea tiene la ecuación mostrada anteriormente. Posteriormente se escoge como siguiente elemento de la relación de recurrencia, x_n+1, la intersección de la recta secante con el eje de abscisas obteniendo la fórmula, y un nuevo valor. Seguimos este proceso, hasta llegar a un nivel suficientemente alto de precisión (una diferencia lo suficientemente pequeñas entre x_n y x_n-1).

Convergencia

El orden de convergencia de este método, en un punto cercano a la solución, es

\varphi

donde

\varphi = \frac{1+\sqrt{5}}{2} \approx 1,618

es el número áureo, por lo que se trata de una convergencia superlineal inferior a la del método de Newton-Raphson. En caso de que la aproximación inicial sea demasiado lejana o la raíz no sea simple, este método no asegura la convergencia y tiene un comportamiento similar al de Newton-Raphson.

Comparación con otros métodos de búsqueda de raíces

El método de bisección necesita de muchas iteraciones comparado con el método de la secante, ya que el proceso que éste sigue es mucho más preciso que el de bisección, el cual solo divide por mitades sucesivamente hasta dar con un valor aproximado al real y por consecuente conlleva un número significativamente mayor de iteraciones.

El método de la regla falsa utiliza la misma fórmula que el método de la secante. Sin embargo, no se aplica la fórmula en x_n−1 y x_n, como el método de la secante, pero en x_n y en la última iteración x_k tal que f(x_k) y f(x_n) tiene un signo diferente. Esto significa que el método de regla falsa siempre converge.

La fórmula de recurrencia del método de la secante se puede derivar de la fórmula para el método de Newton-Raphson:

x_n = x_n - \frac{f(x_{n-1})}{f'(x_{n-1})} .

utilizando la aproximación de diferencias finitas:

f'(x_{n-1}) \approx \frac{f(x_{n-1})-f(x_{n-2})}{x_{n-1}-x_{n-2}}.

Si comparamos el método de Newton-Raphson con el método de la secante, vemos que el método de Newton-Raphson converge más rápido (para 2 en contra α ≈ 1,6). Sin embargo, el método de Newton-Raphson requiere la evaluación de ambos f y su derivada en cada paso, mientras que el método de la secante sólo requiere la evaluación de f. Por lo tanto, el método de la secante puede muy bien ser más rápido en la práctica.

Ejercicio de ejemplo

Utilice el método de la secante para encontrar una raíz real de la ecuación polinomial: F(x)=x³+2x²+10x-20=0.

Utilizando la ecuación:

x_{n+1} = x_n - \frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})} f(x_n).

Obtenemos:

x_{n+1} = x_n - \frac{(x_n-x_{n-1})(x_{n}^3+2x_{n}^2+10x_{n}-20)}{(x_{n}^3+2x_{n}^2+10x_{n}-20)-((x_{n-1}^3+2x_{n-1}^2+10x_{n-1}-20))}

Y mediante x₀=0 y x₁=1 se calcula x₂

x_{2} = 1 - \frac{(1-0)(1^3+2(1)^2+10(1)-20)}{(1^3+2(1)^2+10(1)-20)-(0^3+2(0)^2+10(0)-20)}=1.53846

Los valores posteriores son los siguientes:

Ahí tenemos el resultado, cuando

|x_{n+1} - x_n|

≤

\epsilon =10^{-3}

Comprobando el resultado graficando la función utilizando software obtenemos:

Si bien no se converge a la raíz tan rápido como resolviéndolo utilizando el método Newton-Raphson, la velocidad de convergencia no es tan lenta como resolviéndolo por el método de punto fijo; entonces se tiene para este ejemplo una velocidad de convergencia intermedia.

Método de la secante

El principal inconveniente del método de Newton estriba en que requiere conocer el valor de la primera derivada de la función en el punto. Sin embargo, la forma funcional de f(x) dificulta en ocasiones el cálculo de la derivada. En estos casos es más útil emplear el método de la secante.

El método de la secante parte de dos puntos (y no sólo uno como el método de Newton) y estima la tangente (es decir, la pendiente de la recta) por una aproximación de acuerdo con la expresión:

$\begin{displaymath}f'(x_{0}) = \frac{f(x_{1})-f(x_{0})}{x_{1}-x_{0}}\end{displaymath}$

(34)

Sustituyendo esta expresión en la ecuación (29) del método de Newton, obtenemos la expresión del método de la secante que nos proporciona el siguiente punto de iteración:

$\begin{displaymath}x_{2} = x_{0} - \frac{x_{1}-x_{0}}{f(x_{1})-f(x_{0})}f(x_{0})\end{displaymath}$

(35)

**Figure:** Representación geométrica del método de la secante.
[scale=0.9]eps/secante

En la siguiente iteración, emplearemos los puntos x₁ y x₂para estimar un nuevo punto más próximo a la raíz de acuerdo con la ecuación (35). En la figura (8) se representa geométricamente este método.

En general, el método de la secante presenta las mismas ventajas y limitaciones que el método de Newton-Raphson explicado anteriormente.

método de Steffensen (por Johan Frederik Steffensen) es un algoritmo para obtener los ceros de una función. El método de Steffensen se puede considerar como una combinación del método de punto fijo y del método de Aitken. Como el método de Aitken esencialmente acelera la convergencia de otro método, se puede definir este método como el método de punto fijo acelerado.

Ventajas

El método de Steffensen presenta una convergencia rápida y no requiere, como en el caso del método de Newton, la evaluación de derivada alguna. Presenta además, la ventaja adicional de que el proceso de iteración sólo necesita un punto inicial.

Otra ventaja del método de Steffensen es que -al igual que el de Newton- tiene convergencia cuadrática. Es decir, ambos métodos permiten encontrar las raíces de una función f "rápidamente" - en este caso rápidamente significa que en cada iteración, el número de dígitos correctos en la respuesta se duplica. Pero la fórmula para el método de Newton requiere la evaluación de la derivada de la función, el método de Steffensen no, por lo que este último puede ser programado para una función genérica, mientras que la función cumpla la restricción mencionada anteriormente.

El precio de la convergencia rápida es una doble evaluación de la función: tanto

f(x_n)

como

f(x_n + h)

deben ser calculadas, lo que podría llevar un tiempo considerable dependiendo de la función f. Por comparación, el método de la secante sólo necesita una evaluación de la función por cada paso, así que con dos evaluaciones de la función del método de la secante se pueden hacer dos pasos, y esos dos pasos aumentan el número de dígitos correctos en un factor de 1,6. En un solo paso de tiempo el método de Steffensen (o de Newton) aumenta los dígitos correctos en un factor de 2, lo que es sólo un poco mejor.

Al igual que el método de Newton y otros métodos cuadráticamente convergentes, la debilidad fundamental en el método de Steffensen es la elección del valor inicial

x_0

. Si el valor de

x_0

no está "lo suficientemente cerca" de la solución, el método puede fallar y la secuencia de valores

x_0, x_1, x_2, x_3,\dots

o bien puede oscilar entre dos valores, o bien diverger hacia infinito (ambas alternativas pueden suceder).

Se calcula el siguiente punto de iteración a partir de la expresión:

x_{n+1} = x_n - {[f(x_n)]^2 \over {f(x_n + f(x_n)) - f(x_n)} }

Algoritmo

Para una sucesión {x_n}, obtenida por el método del punto fijo x_n+1 = f(x_n), partimos de tres puntos:^{[cita requerida]}

y₀= f(x₀)

z₀= f(y₀)

donde x₀ es el punto inicial. Obteniendo así:

x₁ = x₀ – (y₀ –x₀)^1/2

z₀ – 2*y₀ – x₀

En forma general:

X_n+1 = x_n – (y_n – x_n)^1/2

z_n – 2* y_n – x_n

Donde si |x_n+1 – x_n| = error < Tol entonces se satisface la tolerancia.

teorema de la raíz racional o la prueba de la raíz racional indica una restricción en las soluciones racionales (o raíces) de la ecuación polinómica con coeficientes enteros:

a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0 = 0\,\!

Si a₀ y a_n son diferentes de cero, entonces cada solución racional x, cuando está escrita como fracción irreducible x = p/q, satisface

p es un factor del término constante a₀, y
q es un factor del coeficiente del término a_n.
p y q son coprimos:

Así, una lista de las posibles raíces racionales de la ecuación se puede derivar usando la fórmula

x = \pm \frac{p}{q}

El teorema de la raíz racional es un caso especial (para un solo factor lineal) del lema de Gauss en la factorización de polinomios. El teorema de la raíz entera es un caso especial del teorema de la raíz racional si el coeficiente principal a_n = 1.

Demostración

Sea

P(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0

para algún

a_0, ..., a_n \in \mathbb{Z}

, y suponga

P(\tfrac{p}{q}) = 0

para algún coprimo

p, q \in \mathbb{Z}

P(\tfrac{p}{q}) = a_n(\tfrac{p}{q})^n + a_{n-1}(\tfrac{p}{q})^{n-1} + ... + a_1(\tfrac{p}{q}) + a_0 = 0.

Cambiando el término constante y multiplicando por

q^n

p(a_np^{n-1} + a_{n-1}qp^{n-2} + ... + a_1q^{n-1}) = -a_0q^n, \qquad q(a_{n-1}p^{n-1} + a_{n-2}qp^{n-2} + ... + a_0q^{n-1}) = -a_np^n.

Todos los términos en estas ecuaciones son enteros, lo que implica

p \mid a_0q^n

q \mid a_np^n

. Pero

p, q^n

q, p^n

son coprimos. Por lo tanto, por el Lema de Euclides,

p \mid a_0

q\mid a_n

.¹

Ejemplo

Por ejemplo, cada solución racional de la ecuación

3x^3 - 5x^2 + 5x - 2 = 0\,\!

debe estar entre los números indicados simbólicamente por

\tfrac{1,2}{1,3}\,,

Lo que da la lista de posibles respuestas:

1, -1, 2, -2, \frac{1}{3}, -\frac{1}{3}, \frac{2}{3}, -\frac{2}{3}\,.

Estos candidatos de raíces pueden ser probados usando la regla de Horner (por ejemplo). En este caso particular hay exactamente una raíz racional. Si un candidato a raíz no satisface la ecuación, puede ser usado para acortar la lista de los candidatos restantes. Por ejemplo, x = 1 no satisface la ecuación puesto que el lado izquierdo es igual a 1. Esto significa que substituyendo x = 1 + t produce un polinomio en t con el término constante 1, mientras que el coeficiente de t³ permanece igual que el coeficiente de x³. Aplicando el teorema de la raíz racional produce así las siguientes posibles raíces para t:

t=\pm\tfrac{1}{1,3}

Por lo tanto,

x = 1+t = 2, 0, \frac{4}{3}, \frac{2}{3}

Los candidatos de raíces que no ocurren en ambas listas son eliminados. La lista de candidatos racionales se ha encogido así a apenas x = 2 y x = 2/3.

Si es encontrada una raíz r₁, la regla de Horner también proporcionará un polinomio de grado n − 1 cuyas raíces, junto con r₁, son exactamente las raíces del polinomio original. Puede también ser el caso que ningunos de los candidatos sea una solución; pero en este caso, la ecuación tiene como solución racional x = 2/3. Si la ecuación carece de un término constante a₀, entonces 0 es una de las raíces racionales de la ecuación.

El teorema racional de las raíces da raíces racionales posibles de un solo polinomio variable con coeficientes del número entero. Las raíces racionales son una raíz de un polinomio que sea un número racional. Dado un polinomio

cualquier raíz racional del polinomio tiene un factor de a0 como numerador y un factor de como denominador. El teorema racional de las raíces también se llama el teorema racional de los ceros.

Comience con el polinómico 2x3 + 5x2 - 4x - 3. Desde a0 = -3, el numerador de cualquier raíz racional debe ser uno de ±1, ±3. Desde a3 = 2, el denominador de cualquier raíz racional debe ser uno de ±1, ±2.

Para ver porqué, comience con los dos factores

La determinación de cada factor a 0 da las raíces del polinomio:

Las raíces del polinomio (3x+2)(5x-7) son x = 2/3 y x = -7/5.

Ahora multiplique los dos factores del polinomio.

(3x-2) (5x+7)=3x*5x+3x*7+ (- 2) *5x+ (- 2) *7=15x^2+21x-10x-14=15x^2+11x-14

Según el teorema racional de las raíces, cualquier raíz racional del polinomio será un factor de -14 dividido por un factor de 15. Los factores de -14 son±1, ±2, ±7, ±14. Los factores de 15 son ±1, ±3, ±5, ±15.

Ejemplos

Paso	Ecuación	Descripción
1		Éste es el polinomio cuyo encontrar raíces.
2		Encuentre todos los factores de `a0`.
3		Encuentre todos los factores de `a3`.
4		Calcule todas las raíces racionales posibles dividiendo los factores de -3 por los factores de 2.
5		Simplifique cualquier fracción que pueda ser simplificada.
6		Pruebe la raíz `x=1` substituye `1` por `x`.
7		Simplifique los exponentes.
8		Simplifique la multiplicación.
9		Simplifique la suma. Puesto que `0=0` es una declaración verdadera, `1` es una raíz de `P(x)`.
10		Utilice la división sintética para encontrar el factor restante.
11		Aquí están los factores del polinomio. Utilice la ecuación cuadrático para encontrar cualquier raíz cuadrático del`2x2+7x+3`.
Ejemplo 1

Paso	Ecuación	Descripción
1		Éste es el polinomio cuyo encontrar raíces.
2		Encuentre todos los factores de.
3		Encuentre todos los factores de `a0`.
4		Calcule todas las raíces racionales posibles dividiendo los factores de `-3` por los factores de `2`.
5		Simplifique cualquier fracción que pueda ser simplificada.
6		Pruebe la raíz `x=3` por `3` que substituyen adentro para el `X.`
7		Simplifique los exponentes.
8		Simplifique la multiplicación.
9		Simplifique la suma y la resta. Desde `84≠0`, `3` no es una raíz de `P(x)`.