On iterative methods to solve nonlinear equations
- GRAU GOTES, MARIA ANGELA
- Miquel Grau Sánchez Director
Universidade de defensa: Universitat Politècnica de Catalunya (UPC)
Fecha de defensa: 28 de xaneiro de 2015
- José Manuel Gutiérrez Jiménez Presidente/a
- Sonia Busquier Sáez Secretaria
- Sergio Amat Plata Vogal
Tipo: Tese
Resumo
Many of the problems in experimental sciences and other disciplines can be expressed in the form of nonlinear equations. The solution of these equations is rarely obtained in closed form. With the development of computers, these problems can be addressed by numerical algorithms that approximate the solution. Specifically, fixed point iterative methods are used, which generate a convergent sequence presumably to the solution of the equation or system of equations. Since J.F. Traub (Iterative methods for the solution of equations, Prentice-Hall, N.J. 1964) initiated the qualitative as well the quantitative analysis of iterative methods in the 1960s, iterative methods for nonlinear systems has been a constantly interesting field of study for numerical analysts. Our contribution to this field is the analysis and construction of new iterative methods, by improving the order of convergence and computational efficiency either of these or other known methods. To study the new iterative methods that we have proposed, we reviewed analyzed and improved classic concepts of computational order of convergence, the error equation, and the computational cost of an iterative method for both an equation and a system of nonlinear equations. Specifically, we have worked on the following points: - We computed the local order of convergence for known two-step and new multi-step iterative methods by means of expansions in formal developments in power series of the function F, the Jacobian operator, the inverse Jacobian operator and the divided difference operator and its inverse operator. - We generated some measures that approximate the order of convergence. Four new variants for computing the computational order of convergence (COC) are given: one requires the value of the root, whilst the other three do not. - We constructed families of iterative schemes that are variants of Newton’s method and Chebyshev’s method and improve the order and the efficiency. - We studied several families of the modified Secant method (Secant, Kurchatov and Steffensen), evaluated variants of these methods and chose the most efficient. - We generalized the concepts of efficiency index and computational efficiency for nonlinear equations to systems of nonlinear equations. This has been termed the computational efficiency index (CEI). - We considered that in iterative process using variable precision, the accuracy will increase as the computation proceeds. The final result will be obtained as precisely as possible, depending on the computer and the software. - We expressed the cost of evaluating elementary functions in terms of products. This cost depends on the computer, the software and the arithmetic that we used. The above numerical calculations were performed in the algebraic system called MAPLE. - We presented a new way of comparing elapsed time for different iterative schemes. This consists of estimating the time required to achieve a correct decimal of the solution by the method selected. That is, we measured the relationship between the time to fulfill the stop criterion and the total number of correct decimals obtained by method. The five papers selected for this compendium were published in scientific journals in the area of applied mathematics. The impact factor of these journals is, in all cases, in the first third according to the classification of the Journal of Citation Reports. There are four preceding papers that no are part of this report by its publication date. Gran parte de los problemas en ciencias experimentales y otras disciplinas se pueden expresar en forma de ecuaciones no lineales. La solución de estas ecuaciones rara vez se obtiene en forma cerrada; con el desarrollo de los ordenadores, estos problemas pueden ser abordados por algoritmos numéricos que aproximan la solución. Concretamente, se utilizan métodos iterativos de punto fijo, que generan una secuencia convergente presumiblemente a la solución de la ecuación o sistema de ecuaciones. Desde J.F. Traub, (Iterative methods for the solution of equations, Prentice-Hall, N.J. 1964) inició el estudio cualitativo y el análisis cuantitativo de éstos métodos iterativos en la década de los sesenta, los métodos iterativos para sistemas no lineales ha sido un área de constante estudio para los analistas numéricos. La contribución que presenta este compendio en este campo es el análisis y la construcción de nuevos métodos iterativos mejorando ya sea el orden de convergencia o ya sea la eficiencia computacional de éstos o de otros ya conocidos. Para el estudio de nuevos métodos iterativos, se ha revisado, analizado y en algun caso redefinido los conceptos clásicos de orden de convergencia computacional, de ecuación del error y de coste computacional de un método iterativo, tanto para una ecuación como para un sistema de ecuaciones no linealesEn concreto, se ha trabajado en los siguientes puntos: - El cálculo del orden local de convergencia para métodos conocidos de dos pasos y para nuevos métodos iterativos multipaso se realiza haciendo uso de desarrollos formales en serie de potencias del error. Se ha desarrollado la función F, el operador Jacobiano, el operador Jacobiano inverso, el operador diferencia dividida y su operador inverso. -Se generan algunas medidas que aproximan el orden local de convergencia del método iterativo. Se presentan cuatro nuevas variantes para el cálculo del orden de convergencia computacional (COC, computational order of convergence); un parámetro que necesita el valor de la solución o raíz, y tres parámetros que no requieren de éste valor. - Construcción de familias, los esquemas iterativos de las cuáles son variantes del método de Newton y del método de Chebyshev, mejorando el orden y la eficiencia de éstos. - Estudio de diversas familias, derivadas del método de la Secante (Secante, Kurchatov y Steffensen), variantes de estos métodos y elección de los más eficientes. - Generalización de los conceptos de índice de eficiencia y de eficiencia computacional para ecuaciones a sistemas de ecuaciones no lineales. Se ha denominado índice de eficiencia computacional (CEI, Computational Efficiency Index). - Análisis y construcción de procesos iterativos de precisión variable. La precisión aumenta a medida que la computación avanza, y el resultado final se obtiene con la máxima precisión posible, dependiendo del ordenador y el software disponibles. - Expresión del coste de la evaluación de las funciones elementales en términos de productos. Este coste depende del ordinador, el software y la aritmética que se utiliza. Los cálculos numéricos mencionados se ha realizado con el sistema algebraico MAPLE. - Una nueva forma de comparar el tiempo de ejecución dedicado al cálculo por los diferentes esquemas iterativos. Consiste en calcular el tiempo necesario para conseguir un decimal correcto de la solución por el método escogido. Concretamente, se mide la relación entre el tiempo transcurrido para cumplir el criterio de parada y el número total de decimales correctos obtenidos por el algoritmo. Los cinco trabajos seleccionados para constituir este compendio fueron publicados en revistas científicas del área de matemática aplicada. El factor de impacto de éstas se encuentra en el primer tercio de acuerdo con la clasificación del Journal of Citation Reports. Además, he publicado cuatro artículos previos, que no forman parte de esta memoria por fecha de publicación, válidos para un sexenio el año 2011.