A new preconditioner for solving linear systems with ill-conditioned Z-matrices

Abstract

The class of Z-matrices is the set of matrices whose off-diagonal entries are non positive. Solving a linear system of the form Ax = b is possible if the coefficient matrix A has certain characteristics such as being of full rank. Linear systems in which the coefficient matrix A is a Z-matrix can be found in many processes used in different applied fields from engineering to economics. For instance, they can be found when approximating the solution of a partial differential equation (PDE) by finite difference methods. Usually, the resulting linear systems are very large and using direct methods is impractical. Then it is necessary to use iterative methods. The success of iterative methods depends on the condition number of the system. The condition number is the maximum ratio of the relative error in x divided by the relative error in b. This is a measurement that relates the behavior of the system given small changes on its right ii hand side (RHS). If the condition number in a linear system is small then it is said that the system is well-conditioned, otherwise it is ill-conditioned. In many cases, large linear systems with Z-matrices as coefficient matrices have large condition numbers, which can cause iterative methods to fail. To alleviate this problem, a technique known as preconditioning is used. Basically, preconditioning is any form of modification of an original linear system that produces an equivalent system that is faster to solve than the original system. The Gauss-Seidel is one of the most reliable and oldest iterative methods for solving linear systems, but it tends to converge slowly for ill-conditioned systems. In 2002, Hisashi Kotakemori [9] proposed a preconditioner for the Gauss-Seidel of the form P = I + Smax for the particular case where the coefficient matrix is a diagonally dominant Z-matrix, with unit diagonal elements. Then, the problem Ax = b is changed to an equivalent one, which is P Ax = P b. This thesis will investigate the properties of the preconditioner P = I + Smax. As it will be shown, using this preconditioner preserves the convergence characteristics of the problem and keeps P A as a Z-matrix. Then, based on these properties, a new preconditioner will be proposed based on P, which can be used for diagonally dominant Z-matrices with positive diagonal elements, not only for unit diagonal elements. In addition, this new preconditioner can be used iteratively to improve the convergence characteristics of the problem.

La clase de las matrices Z es el conjunto de matrices que sus entradas fuera de la diagonal no son positivas. Resolver un sistema lineal de la forma Ax = b es posible si la matriz de coeficientes tiene ciertas características como ser de rango completo. Sistemas lineales en los que la matriz de coeficientes A es una matriz Z se puede encontrar en muchos de los procesos utilizados en diferentes campos aplicados de la ingeniería y la economía. Por ejemplo, se puede encontrar cuando se aproxima la solución de una ecuación diferencial parcial (PDE) por métodos de diferencias finitas. Por lo general, los sistemas lineales resultantes son de gran tamaño lo cual hace que el uso de métodos directos sea impráctico. Entonces es necesario el uso de métodos iterativos. El éxito de los métodos iterativos depende del número de condición del sistema. El número de condición es la relación máxima del error relativo de x dividido por el error relativo iv en b. Esta es una medida que relaciona el comportamiento del sistema ante cambios pequeños en su lado derecho (RHS). Si el número de condición en un sistema lineal es pequeño, entonces se dice que el sistema está bien acondicionado, de lo contrario es mal condicionado. En muchos casos los sistemas lineales grandes con matrices Z como matrices de coeficientes tienen un gran número condición, esto puede causar que los métodos iterativos fallen. Para aliviar este problema, se utiliza una técnica conocida como precondicionamiento. Básicamente, precondicionamiento es cualquier forma de modificación de un sistema lineal en uno equivalente que es más rápido para resolver que el sistema original. El Gauss-Seidel es uno de los métodos iterativos más antiguos y confiables para resolver sistemas lineales, pero tiende a converger lentamente. En 2002, Hisashi Kotakemori en [9] propuso un precondicionador de Gauss-Seidel de la forma P = I +Smax, para el caso particular en que la matriz de coeficientes es una matriz Z diagonalmente dominante, con una diagonal principal unitaria. Entonces, el problema Ax = b se cambia por un equivalente, que es P Ax = P b. En esta tesis se investigarán las propiedades del precondicionador P = I + Smax. Como se verá, el uso de este precondicionador preserva las características de convergencia del problema y mantiene P A como una matriz Z. Luego, basado en estas propiedades, se propone un nuevo precondicionador fundamentado en P, el cual se puede utilizar para matrices Z diagonalmente dominantes con diagonal positiva, no sólo para las de diagonal unitaria. Además, este nuevo precondicionador puede ser utilizado de manera iterativa para mejorar las características de convergencia del problema.