Numerik-Algorithmen

4.17 Entscheidungshilfen für die Auswahl des Verfahrens (S. 219-220)

Trotz der Vielzahl numerischer Verfahren, die zur Lösung linearer Gleichungssysteme zur Verfügung stehen, ist die praktische Bestimmung der Lösungen für große Werte von n eine problematische numerische Aufgabe. Die Gründe hierfür sind (1) der Arbeitsaufwand (die Rechenzeit), (2) der Speicherplatzbedarf, (3) die Verfälschung der Ergebnisse durch Rundungsfehler oder mathematische Instabilität des Problems.

Zu (1): Der Arbeitsaufwand lässt sich über die Anzahl erforderlicher Punktoperationen (Multiplikationen, Divisionen) abschätzen. Die folgende Tabelle liefert die Anzahl der Punktoperationen, die erforderlich sind, um ein lineares Gleichungssystem aus n Gleichungen mit n Unbekannten nach den angegebenen Verfahren zu lösen. Die Anzahl erforderlicher Additionen und Subtraktionen bleibt in diesem Vergleich unberücksichtigt.

Zu (2): Vom Computer her gesehen ergeben sich bez¨uglich des Speicherplatzes zwei kritische Größen f¨ur sehr große n: (a) der für die Speicherung der aik verfügbare Platz im Arbeitsspeicher (Hauptspeicher), (b) der dafür verfügbare Platz in den Hintergrundspeichern. Der Speicherplatzbedarf verringert sich, wenn A spezielle Eigenschaften, z. B. Bandstruktur, besitzt, dünn besetzt ist oder symmetrisch ist. Es entsteht praktisch kein Speicherplatzbedarf, wenn sich die aik aufgrund einer im Einzelfall gegebenen Vorschrift jeweils im Computer berechnen lassen ("generated Matrix"), siehe auch die folgende Bemerkung.

Zu (3): Durch geeignete Gestaltung des Ablaufs der Rechnung kann die Akkumulation von Rundungsfehlern unter Kontrolle gehalten werden, sofern die Ursache nicht in mathematischer Instabilit¨a t des Problems liegt. Deshalb sollte grundsätzlich mit skalierter teilweiser Pivotisierung gearbeitet werden, es sei denn, die spezielle Struktur des Systems garantiert numerische Stabilität. Mit relativ geringem Aufwand lassen sich die Ergebnisse jeweils durch Nachiteration verbessern. Im Allgemeinen lassen sich weder die Kondition des Systems noch die Frage, ob die Bedingungen f¨ur die eindeutige Lösbarkeit erfüllt sind, vor Beginn der numerischen Rechnung prüfen. Daher sollten die Programme so gestaltet sein, dass sie den Benutzern im Verlaufe der Rechnung darüber Auskunft geben.

Bemerkungen zu großen Systemen und dünnbesetzten Matrizen:

Bei sehr großen Systemen, bei denen die Elemente von A und a nicht vollst¨a ndig im Arbeitsspeicher unterzubringen sind (selbst nicht in gepackter Form), können sogenannte Blockmethoden angewandt werden, s. dazu Abschnitt 4.15. Solche Systeme treten vorwiegend im Zusammenhang mit der numerischen Lösung partieller Di.erentialgleichungen auf. Sind die Matrizen d¨unn besetzt, wie es häufig bei der Lösung von Randwertproblemen für gewöhnliche und partielle Di.erentialgleichungen durch Differenzenverfahren oder die Finite-Elemente-Methode auftritt, sollten entsprechende Lösungsalgorithmen verwendet werden, siehe dazu z. B. [MAES1985] und [WEIS1990],

1. Die Anwendung des Algorithmus von Cuthill-McKee [CUTH1969] überführt die dünnbesetzte Matrix (z. B. Stei.gkeitsmatrix) in eine Bandmatrix mit fast optimaler Bandbreite, aber eben im Allgemeinen noch nicht mit der möglichen minimalen Bandbreite.

2. Anschließend wird mit den Nummerierungen aus Cuthill-McKee als Startnummerierung der Algorithmus von Rosen angewandt, der im Allgemeinen die Bandbreite weiter verringert. Es gibt aber auch Fälle, wo damit keine weitere Verminderung der Bandbreite erzielt werden kann. Weitere geeignete Verfahren, insbesondere auch Iterationsverfahren, sind in [WEIS1990] zu finden.