Tridiagonal-Toeplitz-Matrix

Eine Tridiagonal-Toeplitz-Matrix ist in der linearen Algebra eine Tridiagonalmatrix mit konstanten Hauptdiagonal- und Nebendiagonalelementen. Tridiagonal-Toeplitz-Matrizen treten in der numerischen Mathematik recht häufig auf, beispielsweise bei der Berechnung kubischer Splines oder bei der Diskretisierung partieller Differentialgleichungen zweiter Ordnung in einer Raumdimension nach der Finite-Differenzen-Methode bei Verwendung äquidistanter Stützstellen.

Definition

Eine Tridiagonal-Toeplitz-Matrix $T\in \mathbb {R} ^{n\times n}$ oder $T\in \mathbb {C} ^{n\times n}$ ist eine quadratische Matrix der Form

T={\begin{pmatrix}a&b&&&&&\\c&a&b&&&&\\&c&a&b&&&\\&&\ddots &\ddots &\ddots &&\\&&&c&a&b&\\&&&&c&a&b\\&&&&&c&a\\\end{pmatrix}}.

wobei die leeren Plätze mit Nullen besetzt sind. $a$ , $b$ und $c$ sind reelle oder komplexe Zahlen. Eine Tridiagonal-Toeplitz-Matrix ist damit sowohl eine spezielle Tridiagonalmatrix, bei der die Haupt- und Nebendiagonalelemente konstant sind, als auch eine spezielle Toeplitz-Matrix, bei der die Elemente außerhalb der Haupt- und Nebendiagonalen gleich null sind.

Eigenschaften

Lineare Gleichungssysteme der Form $Tx=d$ können effizient mit Hilfe des Thomas-Algorithmus, einer vereinfachten Variante der Gauß-Elimination, mit einem Aufwand der Ordnung $O(n)$ gelöst werden.

Die Eigenwerte und Eigenvektoren einer reellen Tridiagonal-Toeplitz-Matrix $T$ lassen sich aus Formeln berechnen. Das sind die Lösungen der Eigenwertgleichung

T\cdot {\vec {v}}=\lambda \,{\vec {v}}.

Es gibt im allgemeinen Fall $n$ Lösungen für die Eigenwerte und $n$ zugehörige Eigenvektoren, wobei $n$ die Anzahl der Zeilen resp. Anzahl der Spalten ist. $\lambda _{i}$ symbolisiere einen speziellen Eigenwert mit der Nummer $i$ , ${\vec {v}}_{i}$ den zugehörigen Eigenvektor.

Sind die Nebendiagonalelemente $b$ und $c$ ungleich null, dann sind die Eigenwerte von $T$ alle verschieden und durch

\lambda _{i}=a-2{\sqrt {b\;c}}\;\cos \left({\frac {\pi \;i}{n+1}}\right)=a-2{\sqrt {b\;c}}\,\cos \varphi _{i}

^[1]

und den Winkeln

\varphi _{i}={\frac {\pi \;i}{n+1}}

mit jeweils $i=1,\ldots ,n$ gegeben.^[2]

Die ersten fünf Eigenvektoren einer großen Tridiagonal-Toeplitz-Matrix mit Markierungspunkten für den Spezialfall einer Matrix der Größe 5×5

Die Komponenten $j$ des Eigenvektors ${\vec {v}}_{i}$ zum Eigenwert $\lambda _{i}$ kann man im Fall $b=c$ aus der Formel

v_{ij}=const\cdot \sin \left({\frac {\pi \;i\;j}{n+1}}\right)

mit $j=1,\ldots ,n$ berechnen.^[3] Es ist $const$ eine beliebige Konstante, die als Normierungskonstante bezeichnet wird, für die man auch den Wert $const=1$ wählen kann. Die Komponenten aller Eigenvektoren bilden eine quadratische Matrix $V$ , die symmetrisch ist, wie aus der Formel sofort ersichtlich. Von den Werten $a$ und $b$ auf den Nebendiagonalen hängen die Eigenvektoren nicht ab.

Trägt man die Komponenten $v_{ij}$ für festes $i$ über der fortlaufenden Nummer $j$ auf, so liegen diese auf einer Sinuskurve, die für die (nicht mehr dazugehörigen) Werte $j=0$ und $j=n+1$ durch Null geht und zwischen diesen Werten $i/2$ Perioden enthält.

Die Grafik zeigt die Sinuskurven $\sin(i\cdot \varphi )$ für $i=1,\ldots ,5$ in unterschiedlichen Farben, auf denen die Komponenten der Eigenvektoren liegen. Die rote Sinuskurve, die zum ersten Eigenvektor resp. zum ersten Eigenwert gehört, enthält eine halbe Periode, die grüne zum zweiten Eigenvektor eine (vollständige) Periode, die blaue $3/2$ Perioden usw. Die farbigen Punkte markieren die Werte der Vektorkomponenten für den Spezialfall $n=5$ . Die durchgezogenen Sinuskurven sind die Eigenvektoren für den Fall von sehr großem $n$ und damit die Eigenfunktionen des entsprechenden kontinuierlichen Eigenwertproblems.

Ist $b\;c=0$ , so hat $T$ den einzigen Eigenwert $a$ . Die zugehörigen Eigenvektoren sind dann die Einheitsvektoren $e_{1}$ , falls $c\neq 0$ ist, $e_{n}$ , falls $b\neq 0$ ist, und $e_{1},\ldots ,e_{n}$ , falls $b=c=0$ sind. Die Eigenwerte von $T$ sind damit genau dann reell, wenn $b\;c\geq 0$ gilt. Die Eigenwerte einer Triadiagonal-Toeplitz-Matrix werden beispielsweise bei der numerischen Stabilitätsanalyse des Crank-Nicolson-Verfahrens benötigt.

Quadrat einer Tridiagonal-Toeplitz-Matrix

Da Tridiagonal-Toeplitz-Matrizen zu den Matrizen gehören, für die Eigenwerte und Eigenvektoren formelmäßig berechnet werden können, sind sie besonders geeignet als Testmatrizen für diejenigen Anwender, die entsprechenden Quelltext zu programmieren und ihren Code zu testen haben. Aber auch für die, die übernommene Computerprogramme testen wollen oder die sich in solche einarbeiten müssen.

Eine weitere solche Testmatrix ist auch das Quadrat einer Tridiagonal-Toeplitz-Matrix. Multiplizieren wir die Eigenwertgleichung

T\cdot {\vec {v}}=\lambda \,{\vec {v}}.

von links mit der Matrix $T,$ so erhalten wir

T^{2}\cdot {\vec {v}}=\lambda \;T\cdot {\vec {v}}=\lambda ^{2}\,{\vec {v}}.

Die Eigenwerte des Quadrats $T^{2}$ einer Tridiagonal-Toeplitz-Matrix $T$ sind folglich gleich den Quadraten der Eigenwerte $\lambda _{i}$ der Matrix $T$ . Die Eigenvektoren beider Matrizen sind gleich. Analoges gilt auch für höhere Potenzen der Matrix $T$ .

Durch Multiplikation der Matrix $T$ mit sich selbst ergibt die Matrix

T^{2}={\begin{pmatrix}{\boldsymbol {a^{2}+bc}}&2ab&b^{2}&&&&\\2ac&a^{2}+2bc&2ab&b^{2}&&&&\\c^{2}&2ac&a^{2}+2bc&2ab&b^{2}&&&\\&\ddots &\ddots &\ddots &\ddots &\ddots &&\\&&c^{2}&2ac&a^{2}+2bc&2ab&b^{2}&\\&&&c^{2}&2ac&a^{2}+2bc&2ab&\\&&&&c^{2}&2ac&{\boldsymbol {a^{2}+bc}}\\\end{pmatrix}}.

Die Matrix $T^{2}$ ist eine Bandmatrix mit fünf Bändern. Sie ist jedoch keine Toeplitz-Matrix. Das erkennt man an den beiden hervorgehobenen Elementen $t_{11}$ und $t_{nn}$ , die sich von den sonstigen Diagonalelementen unterscheiden.

Siehe auch

Literatur

Albrecht Böttcher, Sergei M. Grudsky: Spectral Properties of Banded Toeplitz Matrices. SIAM, Philadelphia PA 2005, ISBN 0-89871-599-7, Kapitel 2.2.
Silvia Noschese, Lionello Pasquini, Lothar Reichel: Tridiagonal Toeplitz matrices. Properties and novel applications. In: Numerical Linear Algebra with Applications. Band 20, Nr. 2: Special Issue: Inverse Problems Dedicated to Biswa Datta, 2013, ISSN 1070-5325, S. 302–326, doi:10.1002/nla.1811.

Einzelnachweise und Anmerkung

↑ Da $\cos(x)=\cos(-x)$ ist, ändern sich bei Wechsel des Vorzeichens des zweiten Summanden nur die Reihenfolge der Eigenwerte. Wählt man das Minuszeichen, so ist der erste Eigenwert der kleinste, wählt man das Pluszeichen, so ist der erste Eigenwert der größte.
↑ Richard Bellman: Introduction to matrix algebra. McGraw, New York 1960, S. 215 f. (328 S.). Der Name Tridiagonal-Toeplitz-Matrix für diesen Matrixtyp wird von Bellman nicht verwendet.
↑ Rudolf Zurmühl: Matrizen und ihre technischen Anwendungen. Vierte neubearbeite Auflage. Springer, Berlin, Göttingen, Heidelberg 1964, S. 229 f. (XII, 452, eingeschränkte Vorschau in der Google-Buchsuche). Der Name Tridiagonal-Toeplitz-Matrix für diesen Matrixtyp wird von Zurmühl nicht verwendet.

[1] Da $\cos(x)=\cos(-x)$ ist, ändern sich bei Wechsel des Vorzeichens des zweiten Summanden nur die Reihenfolge der Eigenwerte. Wählt man das Minuszeichen, so ist der erste Eigenwert der kleinste, wählt man das Pluszeichen, so ist der erste Eigenwert der größte.

[Bellman_1960-2] Richard Bellman: Introduction to matrix algebra. McGraw, New York 1960, S. 215 f. (328 S.). Der Name Tridiagonal-Toeplitz-Matrix für diesen Matrixtyp wird von Bellman nicht verwendet.

[Zurmuehl_1964-3] Rudolf Zurmühl: Matrizen und ihre technischen Anwendungen. Vierte neubearbeite Auflage. Springer, Berlin, Göttingen, Heidelberg 1964, S. 229 f. (XII, 452, eingeschränkte Vorschau in der Google-Buchsuche). Der Name Tridiagonal-Toeplitz-Matrix für diesen Matrixtyp wird von Zurmühl nicht verwendet.

[1]

[2]

[3]