Numerische Mathematik kompakt

Description

Dieses Lehrbuch behandelt in kompakter und übersichtlicher Form die grundlegenden Themen der numerischen Mathematik. Es vermittelt ein solides Basiswissen der wichtigen Algorithmen und dazugehörigen Fehler- und Aufwandsbetrachtungen, das zur Lösung von zahlreichen in der Praxis auftretenden mathematischen Problemstellungen benötigt wird. Die vorgestellten Resultate werden mit elementaren Methoden hergeleitet. Für die meisten der vorgestellten Verfahren werden Pseudo-Codes angegeben, die sich unmittelbar in Computerprogramme umsetzen lassen. Mit rund 200 Übungsaufgaben und weiterführenden Literaturhinweisen ist das Buch für das Selbststudium geeignet. Zahlreiche Abbildungen und übersichtliche Schemata erleichtern dabei das Lernen. Das Lehrbuch ist ohne weitere Themenauswahl als Vorlage für zwei jeweils vierstündige einführende Vorlesungen über Numerik verwendbar.In der vorliegenden fünften Auflage sind Aktualisierungen, Korrekturen und stilistische Änderungen vorgenommen worden. Außerdem sind zahlreiche weitere Übungsaufgaben und Beispiele aufgenommen worden, und landausche Symbole werden nun umfassender eingeführt. 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