Engeln-Müllges / Niederdrenk / Wodicka Numerik-Algorithmen

Verfahren, Beispiele, Anwendungen
9. Auflage 2005
ISBN: 978-3-540-26353-1
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 677 Seiten

Reihe: Xpert.press

Das Buch ist eine praxisnahe Einführung in die Numerische Mathematik zu grundlegenden Aufgabengebieten wie lineare und nichtlineare Gleichungen und Systeme, Eigenwerte von Matrizen, Approximation, Interpolation, Splines, Quadratur und Kubatur. Die Autoren beschreiben die mathematischen und numerischen Prinzipien wichtiger Verfahren und stellen leistungsfähige Algorithmen für deren Durchführung dar. Zahlreiche Beispiele und erläuternde Skizzen erleichtern das Verständnis. Für jeden Problemkreis werden Entscheidungshilfen für die Auswahl der geeigneten Methode angegeben. Zu allen Verfahren wurden Programme in C entwickelt, die auf einer CD-ROM beigefügt sind. Eine zweite CD-ROM enthält Spline-Funktionen als Demo-Version aus der interaktiven Lernumgebung NUMAS.

Autoren/Hrsg.

Engeln-Müllges, Gisela

Niederdrenk, Klaus

Wodicka, Reinhard

Inhaltsverzeichnis

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

Leseproben

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.