Rekursionsformeln zur Berechnung der charakteristischen Polynome von symmetrischen Bandmatrizen
FacultiesFakultät für Mathematik und Wirtschaftswissenschaften
LicenseStandard (Fassung vom 03.05.2003)
In this thesis we treat the algebraic eigenvalue problem for symmetric banded matrices with N rows and columns, say. For symmetric tridiagonal matrices, there is a well-known two-term recursion to evaluate the characteristic polynomials of its principal submatrices. This recursion requires O(N) numerical operations containing no divisions and is very stable. By the Poincare separation theorem, the sequence of these polynomials constitutes a Sturmian chain and therefore every eigenvalue can be computed via bisection. The basis of this thesis is a recursion for the characteristic polynomials of symmetric banded matrices and of its principal submatrices. This result is established by considering certain Hamiltonian difference systems and can be seen as a generalization of the two-term recursion for symmetric tridiagonal matrices. Unfortunately the recursion is quite unstable and does not have the good numerical properties of the two-term recursion. To stabilize the recursion we consider a suitable Riccati matrix difference equation which is derived from the Hamiltonian system. This leads to a new recursion and a corresponding algorithm containing divisions. It requires only O(N) operations, the O-constant depending on the bandwidth. For penta- and heptadiagonal matrices we carry out these divisions and derive new division-free algorithms with O(N) operations. In the general case the explicit form of the division-free recursion is too complicated and therefore we illustrate a recursive scheme to derive it algorithmically. The main result of this thesis is a corresponding algorithm with a division-free recursion for arbitrary symmetric banded matrices. We prove that the general algorithm requires O(N) operations and give results for the forward error of the tri- and pentadiagonal algorithm. Finally we present an implementation of the new algorithms in C++ and give some examples to underline their performance.
Subject HeadingsBandmatrix [GND]
Hamiltonsches System [GND]