viernes, 30 de octubre de 2015

Algoritmos

Algoritmos de búsqueda de raíces

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 [a0,b0] con f(a0) y f(b0) 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 [ak, bk] que sigue incluyendo una raíz de la función f.
A partir de un intervalo [ak, bk] se calcula un punto interior ck:
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(ak)) y (b,f(bk)) con el eje de abscisas (igual a como se hace en el método de la secante).
Se evalúa entonces f(ck). Si es suficientemente pequeño, ck es la raíz buscada. Si no, el próximo intervalo [ak+1, bk+1] será:
  • [ak, ck] si f(ak) y f(ck) tienen signos opuestos;
  • [ck, bk] 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 a diferencia de en el método de la secante 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:
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 ck diferente, como:
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
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 ck 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. Ford1 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.

MÉTODO REGLA FALSA

OBJETIVO MÉTODO
  
Encontrar la intersección de una recta conformada por los puntos a y b con el eje x, y obtener nuevos intervalos mas pequeños, lo la cual  permite una  aproximación a una raíz.

GENERALIDADES
Este método conserva todas las características y condiciones que posee el método de bisección, excepto por la forma de calcular el punto  intermedio del intervalo
Para aplicar el método se debe tener en cuenta:
  •  Si se tiene dos puntos (a, f(a)) y(b, f(b)) y se traza la recta que une a estos dos puntos, se puede observar que un punto esta por debajo del eje x y otro por encima de este, y un punto intermedio (Xm,0), con este punto intermedio se puede comparar los limites y obtener un nuevo intervalo

  • Si  f(A) y f(B)<0 font="" nbsp="">entonces la raíz se encuentra al lado izquierdo del intervalo.
  • Si  f(A) y f(B)>0, entonces la raíz se encuentra al lado derecho del intervalo.
  • Para hallar la intersección de la recta con el eje X usamos la siguiente fórmula:
Xm= a - ((f(a)*(b - a))/(f(b) - f(a)))
El método de Regla Falsa converge más rápidamente que el de bisección porque al permanecer uno de sus valores iniciales fijo el número de cálculos se reduce mientras que el otro valor inicial converge hacia la raíz.  















Método para la división de cualquier polinomio entre un binomio de la forma (x-r)\ , obteniendo el cociente y elr esto. Descrita por Paolo Ruffini en 1809, es un caso especial de «división sintética» (una división de polinomios en donde el divisor es un «factor lineal»).1 El Algoritmo de Horner para la división de polinomios utiliza la regla de Ruffini. La regla de Ruffini permite asimismo localizar las raíces de un polinomio y factorizarlo en binomios de la forma (x-r)\  (siendo r un número entero) si es coherente.

Algoritmo

La regla de Ruffini establece un método para la división del polinomio:
P(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0
entre el binomio:
Q(x)=x-r\,\!
para obtener el cociente:
R(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\cdots+b_1x+b_0
y el resto:
s. \!
  • 1. Se trazan dos líneas a manera de ejes y se escriben los coeficientes de P(x), ordenados y sin omitir términos nulos. Se escribe la raíz r del lado izquierdo y el primer coeficiente en el renglón inferior (an):
\begin{array}{c|ccccc} {} & a_n & a_{n-1} & \dots & a_1 & a_0 \\ r & {} & {} & {} & {} & {} \\ \hline {} & a_n & {} & {} & {} & {} \\ {} & =b_{n-1} & {} & {} & {} & {} \\ \end{array}
  • 2. Se multiplica (an) por r y se escribe debajo de an-1:
\begin{array}{c|ccccc} {} & a_n & a_{n-1} & \dots & a_1 & a_0 \\ r & {} & b_{n-1}\,r & {} & {} & {} \\ \hline {} & a_n & {} & {} & {} & {} \\ {} & =b_{n-1} & {} & {} & {} & {} \\ \end{array}
  • 3. Se suman los dos valores obtenidos en la misma columna:
\begin{array}{c|ccccc} {} & a_n & a_{n-1} & \dots & a_1 & a_0 \\ r & {} & b_{n-1}\,r & {} & {} & {} \\ \hline {} & a_n & a_{n-1} + b_{n-1}\,r & {} & {} & {} \\ {} & =b_{n-1} & =b_{n-2} & {} & {} & {} \\ \end{array}
  • 4. El proceso se repite:
\begin{array}{c|ccccc} {} & a_n & a_{n-1} & \dots & a_1 & a_0 \\ r & {} & b_{n-1}\,r & \dots & b_1\,r & b_0\,r \\ \hline {} & a_n & a_{n-1} + b_{n-1}\,r & \dots & a_1 + b_1\,r & a_0 + b_0\,r \\ {} & =b_{n-1} & =b_{n-2} & \dots & =b_0 & =s \\ \end{array}
Los valores b son los coeficientes del polinomio resultante R(x) \! de grado uno menos que el grado de P(x) \!. El residuo es s. \!

Ejemplo 1

División de
P(x)=2x^3+3x^2-4\,\!
entre
Q(x)=x+1.\,\!
utilizando la regla de Ruffini.
1. Se escribe Q(x)=x+1=x-(-1)\,\! y el primer coeficiente (2) en el primer renglón:
\begin{array}{c|cccc} {} & 2 & 3 & 0 & -4 \\ -1 & {} & {} & {} & {} \\ \hline {} & 2 & {} & {} & {} \\ \end{array}
2. Multiplicando por la raíz r=(-1):
\begin{array}{c|rrrr} {} & 2 & 3 & 0 & -4 \\ -1 & {} & {-2} & {} & {} \\ \hline {} & 2 & {} & {} & {} \\ \end{array}
3. Sumando la columna:
\begin{array}{c|rrrr} {} & 2 & 3 & 0 & -4 \\ -1 & {} & {-2} & {} & {} \\ \hline {} & 2 & {1} & {} & {} \\ \end{array}
4. El procedimiento se repite hasta obtener el residuo:
\begin{array}{c|rrrr} {} & 2 & 3 & 0 & -4 \\ -1 & {} & {-2} & {-1} & {1} \\ \hline {} & 2 & {1} & {-1} & {-3} \\ {} & \mathrm{Coef.} & {} & {} & \mathrm{Resto} \end{array}

Si el polinomio original = divisor×cociente+resto, entonces
P(x)=Q(x)R(x)+s\,\!, donde
R(x) = 2x^2+x-1\,\! y s=-3.\,\!

Ejemplo 2

Cuando el resto es igual a 0; permite factorizar, como en el siguiente ejemplo:
F(x)=x^3+x^2-x-1
Tomamos
G(x)=x+1
Usamos el método, y nos queda así:
\begin{array}{c|rrrr} {} & 1 & 1 & -1 & -1 \\ -1 & {} & {-1} & {0} & {1} \\ \hline {} & 1 & {0} & {-1} & {0} \\ {} & \mathrm{Coef.} & {} & {} & \mathrm{Resto} \end{array}
Entonces F(x) se factoriza (x^2-1)(x+1)

REGLA DE RUFFINI


La regla de Ruffini es un algoritmo que permite obtener fácilmente el cociente y el resto de la división de un polinomio por un binomio de la forma x-a. Veamos el algoritmo con un ejemplo, consideremos P(x)=2x3 + x2 - 3x + 5 y Q(x)=x-1. La división se realiza como sigue:
1.Se ordena el polinomio P(x) de mayor a menor grado y se colocan los coeficientes de cada término . Si no apareciese algún término entre el de mayor grado y el de menor se coloca un 0. A la izquierda se pone el número que se resta a x en Q(x), en nuestro caso 1 y se baja el coeficiente del término de mayor grado, este paso se corresponde con la figura 1.

2. Se multiplica el coeficiente que se ha bajado (2) por el que se ha colocado a la izquierda (1). El resultado del producto se coloca debajo del coeficiente del término siguiente y se suman. Figura 2

3. El resultado de la suma se vuelve a multiplicar por el número situado a la izquierda y se repite el proceso. Figuras 3 y 4.

4. El último número (recuadro rojo en Fig. 4) se corresponde con el resto de la división mientras que el resto de números de la fila inferior son los coeficientes del cociente.
Resto = 5 y C(x)=2x2 + 3x por tanto 2x3 + x2 - 3x + 5 =(x-1) (2x2 + 3x) +5
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)