Numerische Mathematik kompakt

Vorwort
Inhaltsverzeichnis
1 Polynominterpolation
1.1 Allgemeine Vorbetrachtungen
1.2 Landausche Symbole
1.2.1 Einführung
1.2.2 Anwendung landauscher Symbole
1.2.3 Rechnen mit landauschen Symbolen
1.3 Existenz und Eindeutigkeit bei der Polynominterpolation
1.3.1 Die lagrangesche Interpolationsformel
1.3.2 Eine erste Vorgehensweise zur Berechnung des interpolierenden
Polynoms
1.4 Neville-Schema
1.5 Die newtonsche Interpolationsformel, dividierte
Differenzen
1.6 Fehlerdarstellungen zur Polynominterpolation
1.7 Tschebyscheff-Polynome
Weitere Themen und Literaturhinweise
Übungsaufgaben
2 Splinefunktionen
2.1 Einführende Bemerkungen
2.2 Interpolierende lineare Splinefunktionen
2.2.1 Die Berechnung interpolierender linearer Splinefunktionen
2.3 Minimaleigenschaften kubischer Splinefunktionen
2.4 Die Berechnung interpolierender kubischer Splinefunktionen
2.4.1 Vorüberlegungen
2.4.2 Natürliche Randbedingungen
2.4.3 Vollständige Randbedingungen
2.4.4 Periodische Randbedingungen
2.4.5 Existenz und Eindeutigkeit der betrachteten interpolierenden kubischen
Splines
2.5 Fehlerabschätzungen für interpolierende kubische
Splines
Weitere Themen und Literaturhinweise
Übungsaufgaben
3 Diskrete Fouriertransformation und Anwendungen
3.1 Diskrete Fouriertransformation
3.2 Anwendungen der diskreten Fouriertransformation
3.2.1 Fourierreihen
3.2.2 Zusammenhang zwischen komplexen Fourierkoeffizienten und der
diskreten Fouriertransformation
3.2.3 Trigonometrische Interpolation, Teil 1
3.2.4 Trigonometrische Interpolation, Teil 2
3.2.5 Trigonometrische Interpolation, Teil 3
3.2.6 Interpolierende reelle trigonometrische Polynome
3.3 Schnelle Fouriertransformation (FFT)
3.3.1 Einführende Bemerkungen
3.3.2 Der grundlegende Zusammenhang
3.3.3 Bit-Umkehr
3.3.4 Der FFT-Algorithmus in der Situation N = 2q
3.3.5 Aufwandsbetrachtungen für den FFT-Algorithmus
3.3.6 Pseudocode für den FFT-Algorithmus in der Situation N = 2q
Weitere Themen und Literaturhinweise
Übungsaufgaben
4 Lösung linearer Gleichungssysteme
4.1 Gestaffelte lineare Gleichungssysteme
4.1.1 Obere gestaffelte Gleichungssysteme
4.1.2 Untere gestaffelte Gleichungssysteme
4.2 Der Gauß-Algorithmus
4.2.1 Einführende Bemerkungen
4.2.2 Gauß-Algorithmus mit Pivotsuche
4.3 Die Faktorisierung PA = LR
4.3.1 Permutationsmatrix
4.3.2 Eliminationsmatrizen
4.3.3 Die Faktorisierung PA = LR
4.4 LR-Faktorisierung
4.5 Cholesky-Faktorisierung symmetrischer, positiv
definiter Matrizen
4.5.1 Grundbegriffe
4.5.2 Die Berechnung einer Faktorisierung A = LLT für positiv definite Matrizen A ∈ RNxN
4.5.3 Eine Klasse positiv definiter Matrizen
4.6 Bandmatrizen
4.7 Normen und Fehlerabschätzungen
4.7.1 Normen
4.7.2 Spezielle Matrixnormen
4.7.3 Die Konditionszahl einer Matrix
4.7.4 Störungsresultate für Matrizen
4.7.5 Fehlerabschätzungen für fehlerbehaftete Gleichungssysteme
4.8 Orthogonalisierungsverfahren
4.8.1 Elementare Eigenschaften orthogonaler Matrizen
4.8.2 Die Faktorisierung A = QR mittels Gram-Schmidt-Orthogonalisierung
4.8.3 Die Faktorisierung A = QS mittels Householder-Transformationen
4.8.4 Anwendung 1: Stabile Lösung schlecht konditionierter GleichungssystemeAx = b
4.8.5 Anwendung 2: Lineare Ausgleichsrechnung
Weitere Themen und Literaturhinweise
Übungsaufgaben
5 Iterative Lösung nichtlinearer Gleichungssysteme
5.1 Vorbemerkungen
5.2 Der eindimensionale Fall
5.2.1 Ein allgemeines Resultat
5.2.2 Das Newton-Verfahren im eindimensionalen Fall
5.3 Der banachsche Fixpunktsatz
5.4 Das Newton-Verfahren im mehrdimensionalen Fall
5.4.1 Einige Begriffe aus der Analysis
5.4.2 Das Newton-Verfahren und seine Konvergenz
5.4.3 Nullstellenbestimmung bei Polynomen
Weitere Themen und Literaturhinweise
Übungsaufgaben
6 Numerische Integration von Funktionen
6.1 Interpolatorische Quadraturformeln
6.2 Spezielle interpolatorische Quadraturformeln
6.2.1 Abgeschlossene Newton-Cotes-Formeln
6.2.2 Andere interpolatorische Quadraturformeln
6.3 Der Fehler bei der interpolatorischen Quadratur
6.4 Der Genauigkeitsgrad abgeschlossener Newton-Cotes-Formeln In für gerade Zahlen n
6.4.1 Der Beweis von Lemma 6.16
6.5 Summierte Quadraturformeln
6.5.1 Summierte Rechteckregeln
6.5.2 Summierte Trapezregel
6.5.3 Summierte Simpson-Regel
6.6 Asymptotik der summierten Trapezregel
6.6.1 Die Asymptotik
6.7 Extrapolationsverfahren
6.7.1 Grundidee
6.7.2 Neville-Schema
6.7.3 Verfahrensfehler bei der Extrapolation
6.8 Gaußsche Quadraturformeln
6.8.1 Einleitende Bemerkungen
6.8.2 Orthogonale Polynome
6.8.3 Optimale Wahl der Stützstellen und Gewichte
6.8.4 Nullstellen von orthogonalen Polynomen als Eigenwerte
6.9 Nachtrag: Beweis der Asymptotik für die summierte Trapezregel
6.9.1 Bernoulli-Polynome
6.9.2 Der Beweis von Theorem 6.24
Weitere Themen und Literaturhinweise
Übungsaufgaben
7 Explizite Einschrittverfahren für Anfangswertprobleme bei gewöhnlichen Differenzialgleichungen
7.1 Ein Existenz- und Eindeutigkeitssatz
7.2 Theorie der Einschrittverfahren
7.2.1 Ein elementares Resultat zur Fehlerakkumulation
7.3 Spezielle Einschrittverfahren
7.3.1 Einschrittverfahren der Konsistenzordnung p = 1
7.3.2 Einschrittverfahren der Konsistenzordnung p = 2
7.3.3 Einschrittverfahren der Konsistenzordnung p = 4
7.4 Rundungsfehleranalyse
7.5 Asymptotische Entwicklung der Approximationen
7.5.1 Einführende Bemerkungen
7.5.2 Herleitung der asymptotischen Entwicklung des globalen Verfahrensfehlers,
1. Teil
7.5.3 Herleitung der asymptotischen Entwicklung des globalen Verfahrensfehlers,
2. Teil
7.5.4 Asymptotische Entwicklungen des lokalen Verfahrensfehlers
7.6 Extrapolationsmethoden für Einschrittverfahren
7.7 Schrittweitensteuerung
7.7.1 Verfahrensvorschrift
7.7.2 Problemstellung
7.7.3 Vorgehensweise bei gegebener Testschrittweite h(k)
7.7.4 Bestimmung einer neuen Testschrittweite h(k+1) im Fall δ(k) > ε
7.7.5 Pseudocode zur Schrittweitensteuerung
Weitere Themen und Literaturhinweise
Übungsaufgaben
8 Mehrschrittverfahren für Anfangswertprobleme
bei gewöhnlichen Differenzialgleichungen
8.1 Grundlegende Begriffe
8.1.1 Mehrschrittverfahren
8.1.2 Konvergenz- und Konsistenzordnung
8.1.3 Nullstabilität, Lipschitzbedingung
8.1.4 Übersicht
8.2 Der globale Verfahrensfehler bei Mehrschrittverfahren
8.2.1 Das Konvergenztheorem
8.2.2 Hilfsresultat 1: Das Lemma von Gronwall
8.2.3 Beschränktheit der Matrixfolge A, A2, A3,...
8.2.4 Die Konsistenzordnung linearer Mehrschrittverfahren
8.3 Spezielle lineare Mehrschrittverfahren – Vorbereitungen
8.4 Adams-Verfahren
8.4.1 Der Ansatz
8.4.2 Adams-Bashfort-Verfahren
8.4.3 Adams-Moulton-Verfahren
8.5 Nyström- und Milne-Simpson-Verfahren
8.5.1 Der Ansatz
8.5.2 Nyström-Verfahren
8.5.3 Milne-Simpson-Verfahren
8.6 BDF-Verfahren
8.6.1 Der Ansatz
8.6.2 Tabellarische Übersicht über spezielle Mehrschrittverfahren
8.7 Prädiktor-Korrektor-Verfahren
8.7.1 Linearer Prädiktor/Linearer Korrektor
8.8 Lineare homogene Differenzengleichungen
8.8.1 Die Testgleichung
8.8.2 Existenz und Eindeutigkeit bei linearen homogenen Differenzengleichungen
8.8.3 Die komplexwertige allgemeine Lösung der homogenen Differenzengleichung Lu = 0
8.8.4 Die reellwertige allgemeine Lösung der homogenen Differenzengleichung Lu = 0
8.8.5 Eine spezielle Differenzengleichung
8.9 Steife Differenzialgleichungen
8.9.1 Einführende Bemerkungen
8.9.2 Existenz und Eindeutigkeit der Lösung bei Anfangswertproblemen
für Differenzialgleichungen mit oberer Lipschitzeigenschaft
8.9.3 Das implizite Euler-Verfahren für steife Differenzialgleichungen
8.9.4 Steife Differenzialgleichungen in den Anwendungen
Weitere Themen und Literaturhinweise
Übungsaufgaben
9 Randwertprobleme bei gewöhnlichen Differenzialgleichungen
9.1 Problemstellung, Existenz, Eindeutigkeit
9.1.1 Problemstellung
9.1.2 Existenz und Eindeutigkeit der Lösung
9.2 Differenzenverfahren
9.2.1 Numerische Differenziation
9.2.2 Der Ansatz für Differenzenverfahren
9.2.3 Das Konvergenzresultat für Differenzenverfahren
9.2.4 Vorbereitungen für den Beweis von Teil a) des Theorems 9.11
9.2.5 Nachweis der Aussage in Teil a) von Theorem 9.11
9.3 Galerkin-Verfahren
9.3.1 Einführende Bemerkungen
9.3.2 Eigenschaften des Differenzialoperators Lu = u" + ru
9.3.3 Galerkin-Verfahren – ein allgemeiner Ansatz
9.3.4 Systemmatrix
9.3.5 Finite-Elemente-Methode
9.3.6 Anwendungen
9.3.7 Das Energiefunktional
9.4 Einfachschießverfahren
9.4.1 Numerische Realisierung des Einfachschießverfahrens mit dem
Newton-Verfahren
9.4.2 Numerische Realisierung des Einfachschießverfahrens mit einer
Fixpunktiteration
Weitere Themen und Literaturhinweise
Übungsaufgaben
10 Gesamtschritt-, Einzelschritt- und Relaxationsverfahren zur Lösung linearer Gleichungssysteme
10.1 Iterationsverfahren zur Lösung linearer Gleichungssysteme
10.1.1 Hintergrund zum Einsatz iterativer Verfahren bei linearen Gleichungssystemen
10.2 Lineare Fixpunktiteration
10.2.1 Ein Modellbeispiel
10.3 Einige spezielle Klassen von Matrizen und ihre Eigenschaften
10.3.1 Irreduzible Matrizen
10.4 Das Gesamtschrittverfahren
10.5 Das Einzelschrittverfahren
10.5.1 Der Betrag einer Matrix
10.5.2 Konvergenzergebnisse für das Einzelschrittverfahren
10.6 Das Relaxationsverfahren und erste Konvergenzresultate
10.6.1 M-Matrizen
10.7 Das Relaxationsverfahren für konsistent geordnete Matrizen
Weitere Themen und Literaturhinweise
Übungsaufgaben
11 Verfahren der konjugierten Gradienten und
GMRES-Verfahren
11.1 Vorbetrachtungen
11.1.1 Ausblick
11.2 Der Ansatz des orthogonalen Residuums für positiv definite
Matrizen
11.2.1 Existenz, Eindeutigkeit und Minimaleigenschaft
11.2.2 Der Ansatz des orthogonalen Residuums (11.2) für gegebene A-konjugierte Basen
11.3 Das CG-Verfahren für positiv definite Matrizen
11.3.1 Einleitende Bemerkungen
11.3.2 Die Berechnung A-konjugierter Suchrichtungen in Kn(A, b)
11.3.3 Der Algorithmus zum CG-Verfahren
11.4 Die Konvergenzgeschwindigkeit des CG-Verfahrens
11.5 Das CG-Verfahren für die Normalgleichungen
11.6 Arnoldi-Prozess
11.6.1 Vorbetrachtungen zum GMRES-Verfahren
11.6.2 Arnoldi-Prozess
11.7 Realisierung von GMRES auf der Basis des
Arnoldi-Prozesses
11.7.1 Einführende Bemerkungen
11.7.2 Allgemeine Vorgehensweise zur Lösung des
Minimierungsproblems (11.32)
11.7.3 Detaillierte Beschreibung der Vorgehensweise zur Lösung des Minimierungsproblems
(11.32)
11.7.4 Matlab-Programm für GMRES
11.8 Konvergenzgeschwindigkeit des GMRES-Verfahrens
11.9 Nachtrag 1: Krylovräume
11.10 Nachtrag 2: Interaktive Programmsysteme mit Multifunktionalität
Weitere Themen und Literaturhinweise
Übungsaufgaben
12 Eigenwertprobleme
12.1 Einleitung
12.2 Störungstheorie für Eigenwertprobleme
12.2.1 Diagonalisierbare Matrizen
12.2.2 Der allgemeine Fall
12.3 Lokalisierung von Eigenwerten
12.4 Variationsformulierung für Eigenwerte von symmetrischen
Matrizen
12.5 Störungsresultate für Eigenwerte symmetrischer Matrizen
12.6 Nachtrag: Faktorisierungen von Matrizen
12.6.1 Symmetrische Matrizen
12.6.2 Diagonalisierbare Matrizen
12.6.3 Schur-Faktorisierung
Weitere Themen und Literaturhinweise
Übungsaufgaben
13 Numerische Verfahren für Eigenwertprobleme
13.1 Einführende Bemerkungen
13.1.1 Ähnlichkeitstransformationen
13.1.2 Vektoriteration
13.2 Transformation auf Hessenbergform
13.2.1 Householder-Ähnlichkeitstransformationen zur Gewinnung von
Hessenbergmatrizen
13.2.2 Der symmetrische Fall
13.3 Newton-Verfahren zur Berechnung der Eigenwerte von
Hessenbergmatrizen
13.3.1 Der nichtsymmetrische Fall. Die Methode von Hyman
13.3.2 Das Newton-Verfahren zur Berechnung der Eigenwerte tridiagonaler
Matrizen
13.4 Jacobi-Verfahren zur Nichtdiagonaleinträge-Reduktion
bei symmetrischen Matrizen
13.4.1 Approximation der Eigenwerte durch Diagonaleinträge
13.4.2 Givensrotationen zur Reduktion der Nichtdiagonaleinträge
13.4.3 Zwei spezielle Jacobi-Verfahren
13.5 Das QR-Verfahren
13.5.1 Eindeutigkeit und Stetigkeit der QR-Faktorisierung einer Matrix
13.5.2 Definition des QR-Verfahrens
13.5.3 Konvergenz des QR-Verfahrens für betragsmäßig einfache Eigenwerte
13.5.4 Praktische Durchführung des QR-Verfahrens für Hessenbergmatrizen
13.6 Das LR-Verfahren
13.7 Die Vektoriteration
13.7.1 Definition und Eigenschaften der Vektoriteration
13.7.2 Spezielle Vektoriterationen
Weitere Themen und Literaturhinweise
Übungsaufgaben
14 Restglieddarstellung nach Peano
14.1 Einführende Bemerkungen
14.2 Peano-Kerne
14.3 Anwendungen
14.3.1 Interpolation
14.3.2 Numerische Integration
Weitere Themen und Literaturhinweise
Übungsaufgaben
15 Approximationstheorie
15.1 Einführende Bemerkungen
15.2 Existenz eines Proximums
15.3 Eindeutigkeit eines Proximums
15.3.1 Einige Notationen; streng konvexe Mengen
15.3.2 Strikt normierte Räume
15.4 Approximationstheorie in Räumen mit Skalarprodukt
15.4.1 Einige Grundlagen
15.4.2 Proxima in linearen Unterräumen
15.5 Gleichmäßige Approximation stetiger Funktionen durch Polynome vom Höchstgrad n - 1
15.6 Anwendungen des Alternantensatzes
15.6.1 Ein Beispiel
15.6.3 Eine zweite Anwendung des Alternantensatzes
15.7 Haarsche Räume, Tschebyscheff-Systeme
15.7.1 Alternantensatz für haarsche Räume
15.7.2 Eindeutigkeit des Proximums
15.7.3 Untere Schranken für den Minimalabstand
Weitere Themen und Literaturhinweise
Übungsaufgaben
16 Rechnerarithmetik
16.1 Zahlendarstellungen
16.2 Allgemeine Gleitpunkt-Zahlensysteme
16.2.1 Grundlegende Begriffe
16.2.2 Struktur des normalisierten Gleitpunkt-Zahlensystems F
16.2.3 Struktur des denormalisierten Gleitpunkt-Zahlensystems F
16.3 Gleitpunkt-Zahlensysteme in der Praxis
16.3.1 Die Gleitpunktzahlen des Standards IEEE 754
16.3.2 Weitere Gleitpunkt-Zahlensysteme in der Praxis
16.4 Runden, Abschneiden
16.4.1 Runden
16.4.2 Abschneiden
16.5 Arithmetik in Gleitpunkt-Zahlensystemen
16.5.1 Arithmetische Grundoperationen in Gleitpunkt-Zahlensystemen
16.5.2 Fehlerakkumulation bei der Hintereinanderausführung von Multiplikationen
und Divisionen in Gleitpunkt-Zahlensystemen
16.5.3 Fehlerverstärkung bei der Hintereinanderausführung von Additionen
in einem gegebenen Gleitpunkt-Zahlensystem F
Weitere Themen und Literaturhinweise
Literaturverzeichnis
Index