8.11.02 Bandmatrizen:

Zu signifikanten Effizienzsteigerungen für Berücksichtigung der Strucktur, wenn A eine Bandmatrix ist, also sehr viele symmetrisch angeordnete Nullen enthält. Der praktisch äußerst wichtige Fall von sehr großen Systemen, bei denen in jeder Gleichung nur wenige Unbekannte vorkommen, also die meisten Koeffizienten Null sind, die Anordnung dieser Nullen aber unregelmäßig ist.

Die Anzahl non-null(A)der nischt als verschwindend anzunehmenden Elemente einer Bandmatrix A ist bei kleinen Werten von kl und ku (Anzahl der unteren und oberen nebendiaginalen)

Für K_u,K₁<< n tritt alsoeine beträchtliche Reduktion der Menge signifikanter Daten ein.

Dies muß sowohl bei der Speicherung der Daten als auch bei der Durchführung des Eliminitationsalgorithmus geeignet berücksichtigt werden.

Bei festem K_u,K₁<< n ist dei Anzahl der für die Gleichungsauflösung notwendigen aritmetischen Operationen der lediglich proportional zu n;

dies gilt natürlich asymptotisch für großes n.

Der extremste Spezialfall, der aber im Rahmen vieler übergeordneter Algorithmen eine große Bedeutung hat, ist der einer Tridiagonalmatrix, bei der außer der Hauptdiagonale nur die beiden Nebendiagonalen besetzt sind:

Auf keinen Fall darf man bei Bandmatrizen das Gleichungssystem Ax=b durch Berechnung von A^-1 und Multiplikation lösen. Die schwache besetztheit der Bandmatrizen überträgt sich nämlich nicht auf deren Inverse.

Beispiel:

[<] [globale Übersicht] [Kapitelübersicht] [Stichwortliste] [>]