Numerik-Algorithmen (eBook)

Vorwort zur 9. Auflage 7
Informationen zur beigefügten Software (CD-1, CD-2) 9
Bezeichnungen 13
Inhaltsverzeichnis 15
Kapitel 1 Darstellung von Zahlen und Fehleranalyse,Kondition und Stabilität 22
1.1 Definition von Fehlergrößen 22
1.2 Zahlensysteme 24
1.3 Rechnung mit endlicher Stellenzahl 32
1.4 Fehlerquellen 38
Kapitel 2 Numerische Verfahren zur Lösung nichtlinearer Gleichungen 48
2.1 Aufgabenstellung und Motivation 48
2.2 Definitionen und Sätze über Nullstellen 50
2.3 Allgemeines Iterationsverfahren 52
2.4 Konvergenzordnung eines Iterationsverfahrens 70
2.5 Newtonsche Verfahren 72
2.6 Das Sekantenverfahren 84
2.7 Einschlussverfahren 87
2.8 Anwendungsbeispiele 106
2.9 Effzienz der Verfahren und Entscheidungshilfen 110
Kapitel 3 Verfahren zur Lösung algebraischer Gleichungen 112
3.1 Vorbemerkungen 112
3.2 Das Horner-Schema 113
3.3 Methoden zur Bestimmung sämtlicher Lösungen algebraischer Gleichungen 122
3.4 Anwendungsbeispiel 133
3.5 Entscheidungshilfen 134
Kapitel 4 Direkte Verfahren zur Lösung linearer Gleichungssysteme 136
4.1 Aufgabenstellung und Motivation 136
4.2 Definitionen und Sätze 141
4.3 Lösbarkeitsbedingungen für ein lineares Gleichungssystem 153
4.4 Prinzip der direkten Methoden zur Lösung linearer Gleichungssysteme 154
4.5 Der Gauß-Algorithmus 157
4.6 Matrizeninversion mit dem Gauß-Algorithmus 172
4.7 Verfahren für Systeme 174
4.8 Das Gauß-Jordan-Verfahren 185
4.9 Gleichungssysteme mit tridiagonaler Matrix 186
4.10 Gleichungssysteme mit zyklisch tridiagonaler Matrix 193
4.11 Gleichungssysteme mit fünfdiagonaler Matrix 198
4.12 Gleichungssysteme mit Bandmatrix 204
4.13 Lösung überbestimmter linearer Gleichungssysteme mit Householdertransformation 215
4.14 Fehler, Kondition und Nachiteration 220
4.15 Gleichungssysteme mit Blockmatrix 231
4.16 Algorithmus von Cuthill-McKee für dünn besetzte, symmetrische Matrizen 236
4.17 Entscheidungshilfen für die Auswahl des Verfahrens 240
Kapitel 5 Iterationsverfahren zur Lösung linearer Gleichungssysteme 244
5.1 Vorbemerkungen 244
5.2 Vektor- und Matrizennormen 244
5.3 Das Iterationsverfahren in Gesamtschritten 246
5.4 Das Gauß-Seidelsche Iterationsverfahren, Iteration in Einzelschritten 255
5.5 Relaxation beim Gesamtschrittverfahren 257
5.6 Relaxation beim Einzelschrittverfahren – SOR-Verfahren 257
Kapitel 6 Systeme nichtlinearer Gleichungen 262
6.1 Aufgabenstellung und Motivation 262
6.2 Allgemeines Iterationsverfahren für Systeme 265
6.3 Spezielle Iterationsverfahren 271
6.4 Entscheidungshilfen für die Auswahl der Methode 279
Kapitel 7 Eigenwerte und Eigenvektoren von Matrizen 280
7.1 Definitionen und Aufgabenstellungen 280
7.2 Diagonalähnliche Matrizen 281
7.3 Das Iterationsverfahren nach v. Mises 283
7.4 Konvergenzverbesserung mit Hilfe des Rayleigh-Quotienten im Falle hermitescher Matrizen 292
7.5 Das Verfahren von Krylov 293
7.6 Bestimmung der Eigenwerte positiv definiter, symmetrischer, tridiagonaler Matrizen mit Hilfe des QD-Algorithmus 296
7.7 Transformationen auf Hessenbergform, LR- und QR-Verfahren 297
7.8 Ermittlung der Eigenwerte und Eigenvektoren einer Matrix nach den Verfahren von Martin, Parlett, Peters, Reinsch und Wilkinson 304
7.9 Entscheidungshilfen 305
7.10 Anwendungsbeispiel 306
Kapitel 8 Lineare und nichtlineare Approximation 312
8.1 Aufgabenstellung und Motivation 312
8.2 Lineare Approximation 315
8.3 Diskrete nichtlineare Approximation 363
8.4 Entscheidungshilfen 369
Kapitel 9 Polynomiale Interpolation sowie Shepard-Interpolation 372
9.1 Aufgabenstellung 372
9.2 Interpolationsformeln von Lagrange 374
9.3 Aitken-Interpolationsschema für beliebige Stützstellen 377
9.4 Inverse Interpolation nach Aitken 381
9.5 Interpolationsformeln von Newton 383
9.6 Abschätzung und Schätzung des Interpolationsfehlers 389
9.7 Zweidimensionale Interpolation 394
9.8 Entscheidungshilfen 406
Kapitel 10 Interpolierende Polynom-Splines zur Konstruktion glatter Kurven 408
10.1 Polynom-Splines dritten Grades 408
10.2 Hermite-Splines fünften Grades 463
10.3 Polynomiale kubische Ausgleichssplines 473
10.4 Entscheidungshilfen für die Auswahl einer geeigneten Splinemethode 486
Kapitel 11 Akima- und Renner-Subsplines 492
11.1 Akima-Subsplines 492
11.2 Renner-Subsplines 499
11.3 Abrundung von Ecken bei Akima- und Renner-Kurven 509
11.4 Berechnung der Länge einer Kurve 513
11.5 Flächeninhalt einer geschlossenen ebenen Kurve 516
11.6 Entscheidungshilfen 519
Kapitel 12 Zweidimensionale Splines, Oberflchensplines, Bezier-Splines, B-Splines 520
12.1 Interpolierende zweidimensionale Polynomsplines dritten Grades zur Konstruktion glatter Flächen 520
12.2 Zweidimensionale interpolierende Oberflächensplines 534
12.3 Bezier-Splines 537
12.4 B-Splines 551
12.5 Anwendungsbeispiel 562
12.6 Entscheidungshilfen 567
Kapitel 13 Numerische Differentiation 570
13.1 Aufgabenstellung und Motivation 570
13.2 Differentiation mit Hilfe eines Interpolationspolynoms 571
13.3 Differentiation mit Hilfe interpolierender kubischer Polynom-Splines 574
13.4 Differentiation mit dem Romberg-Verfahren 576
13.5 Entscheidungshilfen 580
Kapitel 14 Numerische Quadratur 582
14.1 Vorbemerkungen 582
14.2 Konstruktion von Interpolationsquadraturformeln 585
14.3 Newton-Cotes-Formeln 588
14.4 Quadraturformeln von Maclaurin 607
14.5 Die Euler-Maclaurin-Formeln 612
14.6 Tschebysche.sche Quadraturformeln 614
14.7 Quadraturformeln von Gauß 616
14.8 Berechnung von Gewichten und Stützstellen verallgemeinerter Gauß-Quadraturformeln 620
14.9 Quadraturformeln von Clenshaw-Curtis 623
14.10 Das Verfahren von Romberg 624
14.11 Fehlerschätzung und Rechnungsfehler 629
14.12 Adaptive Quadraturverfahren 631
14.13 Konvergenz der Quadraturformeln 633
14.14 Anwendungsbeispiel 634
14.15 Entscheidungshilfen für die Auswahl der geeigneten Methode 635
Kapitel 15 Numerische Kubatur 638
15.1 Problemstellung 638
15.2 Konstruktion von Interpolationskubaturformeln 640
15.3 Newton-Cotes-Formeln für rechteckige Integrationsbereiche 643
15.4 Das Romberg-Kubaturverfahren für Rechteckbereiche 651
15.5 Gauß-Kubaturformeln für Rechteckbereiche 654
15.6 Berechnung des Riemannschen Flächenintegrals mit bikubischen Splines 657
15.7 Vergleich der Verfahren anhand von Beispielen 657
15.8 Kubaturformeln für Dreieckbereiche 662
15.9 Entscheidungshilfen 676
Literaturverzeichnis 678
Sachwortverzeichnis 690

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.