ESTUDIO DEL ERROR PROGRESIVO EN LA ELIMINACION DE NEVILLE

Rev.R.Acad. Cienc.Exact.Fis.Nat. (Esp) Vol. 92, N.o 1, pp 1-8, 1998 Matemáticas

ESTUDIO DEL ERROR PROGRESIVO EN LA ELIMINACION DE NEVILLE

PEDRO ALONSO *

MARIANO GASCA**

JUAN MANUEL PEÑA**

* Departamento de Matemáticas. Universidad de Oviedo. Proyecto DGICYT PB93-0310 ** Departamento de Matemáticas Aplicadas, Universidad de Zaragoza. CI Pedro Cerbuna, 12. Edificio Matemáticas, planta La. 50009 Zaragoza. Proyecto DGICYT PB93-0310

Presentado por el Académico Correspondiente Mariano Gasea, 18 de enero de 1997.

RESUMEN

Se realiza un análisis del error progresivo del método de eliminación de Neville para la resolución de un sistema lineal de ecuaciones. Se comparan los resultados obtenidos con otros análogos para la eliminación de Gauss y se obtienen expresiones de los números de condición asociados a las acotaciones del error de la eliminación de Neville.

ABSTRACT

A forward error analysls of Nevilleelimination for solving linear systems of equations is presented. The results are compared with the corresponding ones for Gaussian elimination and some expressions of the condition numbers of the error bounds for Neville elimination are obtai" ned. 1.

INTRODUCCIÓN

La eliminación de Neville es un método de eliminación para resolver sist.emas de ecuaciones lineales distinto al método de Gauss. La diferencia esencial consiste en que en la eliminación de Neville, para hacer un cero en una fila se usa la fila inmediatamente anterior. En general la eliminación de Neville no presenta grandes ventajas ni inconvenientes respecto a la Gaussiana, por lo que dada la universalidad del uso de ésta no la presentamos como una alternativa global que compita con ella. Sin embargo en algunos problemas particulares que vamos a comentar si resulta ventajosa la eliminación de Neville. Este tipo de eliminación se había usado esporádicamente en algunas cuestiones de Teoría de Aproximación y de otros campos (ver [8], [14]), pero no había sido analizada en profundidad hasta una serie de artículos recientes ([6], [9], [11], [12], [13], [18]). En ellos se comprobó que la eliminación

de Neville presenta ventajas sobre la Gaussiana cuando se trabaja con ciertas clases de matrices, en particular las totalmente positivas (éstas son matrices con todos los menores no negativos). Las matrices totalmente positivas aparecen con frecuencia en problemas de Estadística. Teoría de Aproximación y Diseño Geométrico Asistido por Ordenador, entre otros campos (ver [4J, [7], [16]). Las ventajas a las que hemos hecho referencia corresponden a que la eliminación de Neville proporciona caracterizaciones algorítmicas muy sencillas de estas matrices y sus subclases. Respecto del coste computacional, en general es el mismo para la eliminación de Neville que para la Gaussiana, siendo éste

o(~ n 3 }

Sin embargo, en [12] se

comprobó que el coste computacional de la eliminación de Neville puede ser considerablemente inferior al de la eliminación Gaussiana para ciertas matrices especiales, como por ejemplo matrices totalmente positivas que son inversas de una matriz banda. Finalmente mencionemos que en computación en paralelo también se han mostrado útiles esquemas de eliminación próximos a la eliminación de Neville (ver [5], [22]). Un aspecto computacional fundamental para cualquier algoritmo numérico es el del correspondiente análisis de error. En el caso de la eliminación Gaussiana (con aritmética de precisión finita), su análisis de error ha sido materia de estudio desde hace 50 años, y aún continúan esclareciéndose actualmente nuevos aspectos del mismo tal como reflejan las todavía abundantes publicaciones sobre esta materia (ver [15], [23] y [24]). Tres son las cuestiones esenciales a considerar en el análisis de error de un método de eliminación, para la resolución directa de un sistema de ecuaciones lineales Ax = b que se transforma por dicho método en el sistema triangular Ux = e (U es una matriz triangular superior): las estrategias de pivotaje para controlar los errores de redondeo, el análisis de error regresivo y el análisis de error progresivo.

2

Matemáticas: Pedro Alonso et al.

Rev.R.Acad.Cienc.Exact.Fis.Nat. (Esp), 1998; 92

En el caso de la eliminación de NevilIe las estrategias de pivotaje (incluso escalado) fueron consideradas en {lO]. En [3] abordarnos el análisis de error regresivo de la eliminación de NevilIe, especialmente en el caso de matrices totalmente positivas, para las que se comprobó que el comportamiento de la eliminación de NevilIe era similar al de Gauss.

=b y,

La transformación de la matriz de coeficientes A en una matriz triangular superior U, mediante un método de eliminación, equivale matricialmente a la factorización triangular de A: expresar A corno A = LU, con L y U matrices triangular inferior y superior respectivamente. Al utilizar aritmética de precisión finita, aparecen las matrices i, Oen vez de L y U. Si iO = A + E, el análisis de error regresivo consiste en hallar cotas (por normas y por componentes) de la matriz E. Mucho más complejo resulta el análisis de error progresivo. Si es la solución computada por eliminación con precisión finita y x es la solución exacta del sistema, el error progresivo trata de hallar cotas En el caso de (por normas y por componentes) para la eliminación Gaussiana se han llevado a cabo estudios de su error progresivo en los trabajos de Olver y Wilkinson [17] y de Stummel ([20] y [21]).

Consideremos el sistema de ecuaciones lineales Ax = = (aij) ¡Sl.j:$n, .. b = (b¡ )1