Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Matrix splitting
Résumé
In the mathematical discipline of numerical linear algebra, a matrix splitting is an expression which represents a given matrix as a sum or difference of matrices. Many iterative methods (for example, for systems of differential equations) depend upon the direct solution of matrix equations involving matrices more general than tridiagonal matrices. These matrix equations can often be solved directly and efficiently when written as a matrix splitting. The technique was devised by Richard S. Varga in 1960.
We seek to solve the matrix equation
where A is a given n × n non-singular matrix, and k is a given column vector with n components. We split the matrix A into
where B and C are n × n matrices. If, for an arbitrary n × n matrix M, M has nonnegative entries, we write M ≥ 0. If M has only positive entries, we write M > 0. Similarly, if the matrix M1 − M2 has nonnegative entries, we write M1 ≥ M2.
Definition: A = B − C is a regular splitting of A if B−1 ≥ 0 and C ≥ 0.
We assume that matrix equations of the form
where g is a given column vector, can be solved directly for the vector x. If () represents a regular splitting of A, then the iterative method
where x(0) is an arbitrary vector, can be carried out. Equivalently, we write () in the form
The matrix D = B−1C has nonnegative entries if () represents a regular splitting of A.
It can be shown that if A−1 > 0, then < 1, where represents the spectral radius of D, and thus D is a convergent matrix. As a consequence, the iterative method () is necessarily convergent.
If, in addition, the splitting () is chosen so that the matrix B is a diagonal matrix (with the diagonal entries all non-zero, since B must be invertible), then B can be inverted in linear time (see Time complexity).
Many iterative methods can be described as a matrix splitting. If the diagonal entries of the matrix A are all nonzero, and we express the matrix A as the matrix sum
where D is the diagonal part of A, and U and L are respectively strictly upper and lower triangular n × n matrices, then we have the following.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique