Artículos

Una Solución al Método de Newton-Raphson de Orden Cuadrático para Acelerar la Convergencia de Algoritmos Iterativos de Varias Variables

A Solution to the Newton-Raphson Method of Quadratic Order to Accelerate the Convergence of Iterative Algorithms of Several Variables

Echeverría Briones, Pedro

Pedro Echeverría Briones

pecheverria@dmgs.ecotec.edu.ec

Universidad Ecotec Ecuador

Revista Tecnológica ESPOL - RTE

Escuela Superior Politécnica del Litoral, Ecuador

ISSN: 0257-1749

ISSN-e: 1390-3659

Periodicidad: Semestral

vol. 32, núm. 2, 2020

rte@espol.edu.ec

Recepción: 29 septiembre 2020

Aprobación: 04 noviembre 2020

URL: https://portal.amelica.org/ameli/journal/844/84452068445206010/

DOI: https://doi.org/10.37815/rte.v32n2.777

License Creative Commons
Esta obra está bajo una Licencia Creative Commons Atribución-NoComercial 4.0 Internacional.

Modelo de publicación sin fines de lucro para conservar la naturaleza académica y abierta de la comunicación científica

ePub generado a partir de XML JATS4R

Resumen: Actualmente se busca reducir los tiempos de ejecución de los algoritmos iterativos que son usados en las optimizaciones que ayudan a la sociedad a encontrar raíces, máximos y mínimos en soluciones a modelos de tipos prescriptivos. Estos algoritmos nacen como respuestas de las matemáticas aplicadas para que puedan ser ejecutadas en cualquier tipo de ordenadores y en lo que hoy en día predomina que son los ordenadores móviles, que por sus recursos limitados nos vemos obligados a disminuir el tiempo usado en el procesador, buscando la convergencia en problemas de funciones de muchas variables. Algunos algoritmos solo llegan a explotar los polinomios de grado 1, dejando por fuera algunas soluciones no lineales, que pueden acelerar la convergencia al aproximar la búsqueda la raíz de una función polinómica de grado 2. En este trabajo se van a demostrar cuáles serían las condiciones para que este tipo de modelos puedan converger, en modelos de 1 variable y de 2 variables, pudiendo determinar una generalidad sobre este tipo de expresiones. Finalmente, se procederá a experimentar con una herramienta sencilla de programación como una hoja de cálculo, para mostrar que existe rapidez en la convergencia hacia la raíz de la función.

Palabras clave: Iteración, cuadrática, convergencia, raíces, máximos, mínimos.

Abstract: Currently, it is sought to reduce the execution times of the iterative algorithms that are used in the optimizations that help society to find roots, maximums and minimums in solutions to prescriptive models. These algorithms are born as the responses of applied mathematics to be executed in any type of computer, predominantly mobile computers, which due to their limited resources, we are forced to reduce the time spent in the processor to seek convergence in function problems of several variables. Some algorithms only manage to exploit polynomials of degree 1, leaving out some non-linear solutions, which can accelerate convergence by approaching the search for the root of a polynomial function of degree 2. This work aims to demonstrate the conditions for this type of models to converge in 1-variable and 2-variable models, being able to determine a generality about this type of expressions. Finally, it proceeds to experiment with a simple programming tool such as a spreadsheet, to demonstrate that there is speed in the convergence towards the root of the function.

Keywords: Iteration, quadratic, convergence, roots, maximum, minimum.

I. INTRODUCCIÓN

En el mundo de los algoritmos iterativos quedan interrogantes poco exploradas como ¿Es posible que el método de Newton-Raphson pueda ser extendido a un polinomio de grado 2? ¿Puede una secuencia de parábolas aproximar en un intervalo a una función? ¿Cuáles son los argumentos que se deben de realizar para seleccionar una de las dos raíces dentro del algoritmo? ¿Es de fácil implementación este tipo de algoritmos con polinomios de grados 2 en un programa informático? ¿Por qué se debe de invertir en la búsqueda de estos algoritmos?

El objetivo es llegar a encontrar un algoritmo que utilizando la aproximación de un polinomio de grado 2, pueda hacer que una de sus raíces converja hacia la raíz de la función. Para lograrlo se utilizará principalmente el Teorema de Taylor debido a que por los supuestos se obtiene el método de Newton-Raphson. Siendo estos supuestos los que se van a utilizar para expandir el polinomio de Taylor de grado 2, encontrando los criterios de convergencia en la selección de sus raíces. Esto se lo va a repetir en funciones de dos variables, para encontrar la generalidad en funciones de varias variables.

Se agregarán algunos elementos de experimentación con respecto a la convergencia del método de orden cuadrático para mostrar los resultados obtenidos.

A. Teorema de Taylor

Sea f una función n veces diferenciable en un intervalo abierto, que contenga a . Entonces para todo x en el intervalo abierto, se puede aproximar a la función f por el polinomio de Taylor [1]:

De la ecuación (1) se obtiene la expresión del método de Newton-Raphson, para polinomios de grado uno [2] [3]:

Usando una extensión del método anterior, obtenemos el polinomio de Taylor de grado dos que se convertirá en la base, para demostrar la convergencia del método por medio de los criterios para determinar la raíz del polinomio que se aproxime a la raíz de la función.

B. Polinomio de Taylor para dos variables de orden cuadrático

Sea una función la cual puede ser n veces diferenciable en algún subconjunto abierto de su dominio, su polinomio de Taylor de grados 2 [4] [5]:

C. Análisis Matemático

1. Definición de la solución cuadrática + b z + c=0. La fórmula para obtener las raíces de una ecuación cuadrática [2], es:

2. La función debe de ser diferenciable hasta el segundo orden, consiguiendo una aproximación de un polinomio cuadrático de la función.

3. Al ser una raíz la función tendrá el valor de cero.

4. La función en su segunda derivada debe de ser distinta de cero.

II. DESARROLLO

D. Convergencia del método cuadrático para el método de Newton-Raphson de funciones de una variable

Por los supuestos realizados en la sección previa podemos deducir de la ecuación (3) cuando que

Utilizando la ecuación (5) con los valores a, b y c de la ecuación (6):

Despejando en la ecuación (8):

donde

Encontrando un problema de convergencia dado que podría tomar dos valores diferentes debido a los signos de la raíz cuadrada. Para seleccionar el signo, hacemos uso de dos supuestos:

1. Cuando entonces

2. Cuando entonces =0

Reduciendo la ecuación (9) en:

Despejando el divisor de la ecuación (10):

Remplazando , en la ecuación (11):

Al despejar de la ecuación (12):

Esta igualdad solo se puede producir si se usa la función signo de por de la ecuación (13). Siendo este el principal elemento de convergencia que reduce de dos posibles soluciones a una solución.

Al sustituir la función signo de de la ecuación (14) por el de la ecuación (9) obtenemos:

Por los supuestos realizados en la sección previa es convergente en los valores de iniciales que sean válidos.

E. Convergencia del método cuadrático para el método de Newton-Raphson de funciones de dos variables

Continuando con la ecuación (4), cuando entonces , por tanto:

Por lo que se repite la forma de las ecuaciones cuadráticas, para cada una de las variables. Para , se encuentran los siguientes factores cuadráticos:

Al remplazar las ecuaciones (18), (19) y (20) en la ecuación (5):

Utilizando la función que produce la convergencia usando la ecuación (15), nos daría:

Produciendo un efecto circular entre los valores de debido a que está en función de y viceversa. Por lo que se plantean dos casos que puedan ocurrir (1) ; (2) , cuando .

Al analizar solo el caso (2) se tendría dos supuestos y . Pero ambos supuestos no se darán en la misma iteración.

Lo primero en el caso (2) sería analizar qué pasaría si primero . Siendo importante que no aparezca como argumento de la función de . Quedando b1 y c1:

Simplificando la ecuación (23) usando la equivalente ecuación (16), nos quedaría una ecuación que utiliza derivadas parciales de

Lo segundo en el caso (2) sería analizar qué pasaría si , entonces se podría obtener

Repitiéndose el modelo de la ecuación (6) para: . Obteniendo la solución al remplazar en la ecuación (15):

Repitiendo el patrón del modelo de la ecuación (26) en la ecuación (28).

Al analizar el caso (1) y repitiendo el proceso anterior que obtuvo las ecuaciones (26) y (28), se puede demostrar que se llega a las mismas ecuaciones solo que en otro orden.

F. Generalización

Se utilizará la expresión generalizada de la expresión de la serie de Taylor para k número de variables, donde l sería un numero entre 1 y k. Se producirá la siguiente expresión:

G. Algoritmo iterativo

Se evaluará variable por variable, dejando fijas a las otras variables en ese procedimiento. Manteniendo los valores obtenidos de las variables evaluadas en n+1.

Para Dos Variables el algoritmo sería:

Etapa Cero

Etapa n

Donde

III. EXPERIMENTACIÓN

Se propone la siguiente función para analizar la convergencia. En la TABLA I se muestran los resultados obtenidos usando Ms Excel para verificar con facilidad.

TABLA I

CONVERGENCIA PARA DETERMINAR x1 Y x2

n |  |  |  |  | Error Absoluto
1 | -2 | 9 | -2 | 9,76782688 | 0,58955811
-2 | 9,76782688 | -2,1378836 | 9,76782688 | 0,01901188
2 | -2,1378836 | 9,76782688 | -2,1378836 | 9,76879997 | 9,4691E-07
-2,1378836 | 9,76879997 | -2,1378838 | 9,76879997 | 4,2633E-14
3 | -2,1378838 | 9,76879997 | -2,1378838 | 9,76879997 | 1,4211E-14
-2,1378838 | 9,76879997 | -2,1378838 | 9,76879997 | 0
4 | -2,1378838 | 9,76879997 | -2,1378838 | 9,76879997 | 0
-2,1378838 | 9,76879997 | -2,1378838 | 9,76879997 | 0
5 | -2,1378838 | 9,76879997 | -2,1378838 | 9,76879997 | 0
-2,1378838 | 9,76879997 | -2,1378838 | 9,76879997 | 0
6 | -2,1378838 | 9,76879997 | -2,1378838 | 9,76879997 | 0
-2,1378838 | 9,76879997 | -2,1378838 | 9,76879997 | 0

Se propone la siguiente función para analizar la convergencia. En la TABLA II se muestran los resultados obtenidos usando Ms Excel para verificar con facilidad.

TABLA II

CONVERGENCIA PARA DETERMINAR x1 Y x2

n |  |  |  |  | Error Absoluto
1 | 3 | 3 | 3 | 1,8361786 | 629
3 | 1,8361786 | 2,55407298 | 1,8361786 | 67,1508266
2 | 2,55407298 | 1,8361786 | 2,55407298 | 1,81739292 | 3,14416724
2,55407298 | 1,81739292 | 2,55398202 | 1,81739292 | 0,01068569
3 | 2,55398202 | 1,81739292 | 2,55398202 | 1,81739292 | 1,2686E-07
2,55398202 | 1,81739292 | 2,55398202 | 1,81739292 | 0
4 | 2,55398202 | 1,81739292 | 2,55398202 | 1,81739292 | 0
2,55398202 | 1,81739292 | 2,55398202 | 1,81739292 | 0
5 | 2,55398202 | 1,81739292 | 2,55398202 | 1,81739292 | 0
2,55398202 | 1,81739292 | 2,55398202 | 1,81739292 | 0
6 | 2,55398202 | 1,81739292 | 2,55398202 | 1,81739292 | 0
2,55398202 | 1,81739292 | 2,55398202 | 1,81739292 | 0

IV. CONCLUSIONES

1. Al usar el signo para determinar el siguiente punto, estamos consiguiendo un algoritmo que es simple de programar.

2. El algoritmo plantea una restricción en el punto de inicio, que debe de cumplir el valor de la raíz cuadrada sea un número real, lo cual nos evita tener iteraciones que sean divergentes.

3. Haciendo un paralelismo con otros algoritmos iterativos, como Gradiente Descendiente, que tiene la particularidad de tener un λ que multiplica el gradiente de la función, debería tender a disminuir. Lo cual es demostrable y calculable por este procedimiento. Pudiéndose determinar tablas que ayudan a indicar el valor sugerido de reducción porcentual del λ.

REFERENCIAS

[1] M. Laczkovich y V. T.Sós, Real Analysis Series, Functions of Several Variables, and Applications, New York: Springer, 2017.

[2] L. Leithold, El Cálculo, México: Oxford University Press, 1998.

[3] J. T. A. Marsden, Cálculo Vectorial, México DF: Addison-Wesley Iberoamericana, 1991.

[4] J. Artega y M. Malakhaltsev, Cálculo vectorial, México: Cengage Learning Editores S.A., 2013.

[5] R. Burden, D. Faires y A. Burden, Análisis Numérico, México: Cengage Learning, 2017.

[6] S. Weintraub, Differential forms, a complement to vector calculus, New York: Academic Press, 1996.

[7] S. Colley, Vector Calculus, New York: Pearson, 2012.

[8] G. M. Phillips y P. J. Taylor, Academic Press, New York: Academic Press, 1996.

[9] S. D. Conte, Elementary numerical analysis: algorithmic approach, New York: McGraw-Hill, 1980.

[10] A. E., M. R. Taylor, Advanced Calculus, New York: Wiley, 1983.