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

Pedro
Echeverría Briones

Universidad Ecotec

Guayaquil, Ecuador

[email-masked]

Orcid: 0000-0002-4921-1111

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.

Enviado: 29/09/2020                                     Aceptado:
04/11/2020                                   Publicado:
30/12/2020

Sumario: I Introducción, II Desarrollo, III Experimentación, IV
Conclusiones.

Como
citar: Echeverría, Pedro. (2020). Una Solución
al Método de Newton-Raphson de Orden Cuadrático para Acelerar la
Convergencia de Algoritmos Iterativos de Varias Variables. Revista
Tecnológica - Espol, 32(2). Recuperado a partir de
http://www.rte.espol.edu.ec/index.php/tecnologica/article/view/777

http://www.rte.espol.edu.ec/index.php/tecnologica/rte/article/view/777

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

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]:

(1)

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

(2)

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.

.

(3)

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]:

.

(4)

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:

.

(5)

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

[3]:

.

(6)

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

.

(7)

(8)

Despejando en la ecuación (8):

(9)

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:

.

(10)

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

.

(11)

Remplazando

, en la ecuación (11):

.

(12)

Al
despejar de la ecuación (12):

.

(13)

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.

.

(14)

Al
sustituir la función signo de

de la ecuación (14) por el

de la ecuación (9) obtenemos:

.

(15)

(16)

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:

.

(17)

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:

(18)

(19)

(20)

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

.

(21)

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

(22)

(23)

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:

(24)

.

(25)

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

(26)

Lo
segundo en el caso (2) sería analizar qué pasaría si

, entonces se podría obtener:

.

(27)

Repitiéndose
el modelo de la ecuación (6) para:

. Obteniendo la solución al
remplazar en la ecuación (15):

(28)

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:

(29)

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

Lo
que asegura las convergencias haciendo que las iteraciones se conviertan en un
procedimiento serial.

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.