Computer-Numerik 2

Thema des Werkes ist das computerunterstützte numerische Lösen mathematisch orientierter Problemstellungen mit besonderer Betonung der Auswahl und gegebenenfalls eigenen Entwicklung effizienter Numerik-Software. Anhand von ca. 500 Beispielen, 250 Abbildungen, 120 Tabellen sowie 150 Algorithmen und Programmstücken wird erläutert, wie man nach praktisch brauchbaren Lösungen sucht, welche Schwierigkeiten bei der Entwicklung und beim Einsatz von Numerik-Software unter Umständen auftreten können und wie man diese überwindet. An die 100 sachgebietsorientierte Software-Hinweise liefern dem Leser sowohl Information über die kommerziell angebotenen Software-Bibliotheken (IMSL, NAG etc.) als auch über frei verfügbare, qualitativ hochstehende Numerik-Software, auf die man über das Internet zugreift.

10 Optimale Approximation.- 10.1 Mathematische Grundlagen.- 10.2 Bestapproximation im Quadratmittel ― L2-Approximation.- 10.2.1 Grundlagen der L2-Approximation.- 10.2.2 Optimale Approximation durch Orthogonalität.- 10.2.3 Normalgleichungen.- 10.2.4 Approximationsfehler.- 10.2.5 Orthogonale Polynome.- 10.3 Diskrete l2―Approximation ― Methode der kleinsten Quadrate.- 10.3.1 Lineare l2-Approximation..- 10.3.2 Nichtlineare l2-Approximation.- 10.4 Gleichmäßige Bestapproximation ― L>?-Approximation.- 10.4.1 Polynome als L?-Approximationsfunktionen.- 10.5 Approximationsalgorithmen.- 10.6 Approximationssoftware für spezielle Funktionen..- 10.6.1 Standardfunktionen.- 10.6.2 FUNPACK.- 10.6.3 IMSL.- 10.6.4 NAG.- 11 Fourier-Transformation.- 11.1 Mathematische Grundlagen.- 11.1.1 Trigonometrische Approximation.- 11.1.2 Das Spektrum.- 11.2 Trigonometrische Interpolation.- 11.3 Faltung.- 11.4 Manipulationen am Signalspektrum.- 11.5 DFT-Algorithmen.- 11.5.1 Schnelle Fourier-Transformation (FFT).- 11.5.2 FFT von reellen Funktionen.- 11.5.3 FFT in zwei und mehr Dimensionen.- 11.6 FFT-Softwarepakete.- 11.6.1 FFTPACK.- 11.6.2 VFFTPK.- 11.7 FFT in Softwarebibliotheken.- 11.7.1 IMSL-Softwarebibliotheken.- 11.7.2 NAG-Softwarebibliotheken.- 11.8 Sonstige FFT-Programme.- 11.8.1 TOMS-Sammlung.- 11.8.2 Diverse NETLIB-Software.- 12 Numerische Integration.- 12.1 Grundprinzipien der Numerischen Integration.- 12.1.1 Integrationsbereiche.- 12.1.2 Gewichtsfunktionen.- 12.1.3 Integrationsmethoden.- 12.1.4 Kondition des Integrationsproblems.- 12.1.5 Inhärente Unsicherheit numerischer Integration.- 12.2 Vorverarbeitung von Integrationsproblemen.- 12.2.1 Transformation von Integralen.- 12.2.2 Zerlegung von Integrationsbereichen.- 12.2.3 Iteration von Integralen.- 12.3 Univariate Integrationsformeln.- 12.3.1 Konstruktion von Integrationsformeln.- 12.3.2 Einfache interpolatorische Quadraturformeln.- 12.3.3 Zusammengesetzte Quadraturformeln.- 12.3.4 Romberg-Formeln.- 12.3.5 Nichtlineare Extrapolation.- 12.3.6 Spezielle Methoden.- 12.4 Multivariate Integrationsformeln.- 12.4.1 Allgemeine Konstruktionsprinzipien.- 12.4.2 Polynomiale Integrationsformeln.- 12.4.3 Zahlentheoretische Integrationsformeln.- 12.4.4 Monte-Carlo-Integrationsverfahren.- 12.4.5 Gitterpunkt-Integrationsformeln.- 12.4.6 Spezielle Methoden.- 12.5 Integrationsalgorithmen.- 12.5.1 Fehlerschätzung.- 12.5.2 Diskretisierungs-Strategie.- 12.5.3 Adaptive Integrations-Algorithmen und -Programme.- 12.5.4 Software für univariate Probleme: Global adaptive Integrationsprogramme.- 12.5.5 Software für multivariate Probleme: Global adaptive Integrationsprogramme.- 12.5.6 Erhöhung der Zuverlässigkeit.- 12.5.7 Mehrfache Integranden.- IV Algebraische Modelle.- 13 Lineare Gleichungssysteme.- 13.1 Planungsphase.- 13.1.1 Problemtyp.- 13.1.2 Strukturmerkmale der Systemmatrix.- 13.1.3 Art der Lösung.- 13.1.4 Forderungen an Algorithmen und Software.- 13.2 Realisierungsphase.- 13.3 Überprüfungsphase.- 13.4 Mathematische Grundlagen.- 13.4.1 Lineare Räume.- 13.4.2 Vektornormen.- 13.4.3 Orthogonalität.- 13.4.4 Lineare Funktionen.- 13.4.5 Matrizen.- 13.4.6 Inverse einer Matrix.- 13.4.7 Eigenwerte einer Matrix.- 13.4.8 Matrixnormen.- 13.4.9 Determinante einer Matrix.- 13.5 Spezielle Matrixeigenschaften.- 13.5.1 Symmetrische und Hermitesche Matrizen.- 13.5.2 Orthogonale und unitäre Matrizen.- 13.5.3 Positiv definite Matrizen.- 13.6 Speziell besetzte Matrizen.- 13.6.1 Diagonalmatrizen.- 13.6.2 Dreiecksmatrizen.- 13.6.3 Blockmatrizen.- 13.6.4 Hessenberg-Matrizen.- 13.6.5 Tridiagonale Matrizen.- 13.6.6 Bandmatrizen.- 13.6.7 Permutationsmatrizen.- 13.7 Singulärwertzerlegung.- 13.7.1 Geometrie linearer Abbildungen.- 13.7.2 Struktur linearer Abbildungen.- 13.7.3 Verallgemeinerte Umkehrabbildungen.- 13.7.4 Allgemeine Lösung linearer Gleichungssysteme.- 13.7.5 Lösung homogener Gleichungssysteme.- 13.7.6 Lineare Ausgleichsprobleme.- 13.8 Kondition linearer Gleichungssysteme.- 13.8.1 Kondition regulärer Systeme.- 13.8.2 Auswirkungen einer gestörten rechten Seite.- 13.8.3 Auswirkungen einer gestörten Matrix.- 13.9 Kondition linearer Ausgleichsprobleme.- 13.10 Konditionsanalyse mittels Singulärwertzerlegung.- 13.11 Direkte Verfahren.- 13.11.1 Das Eliminationsprinzip.- 13.11.2 LU-Faktorisierung.- 13.11.3 Pivot-Strategien.- 13.12 Gleichungssysteme besonderer Struktur.- 13.12.1 Symmetrische, positiv definite Matrizen.- 13.12.2 Bandmatrizen.- 13.13 Beurteilung der erzielten Genauigkeit.- 13.13.1 Konditionsschätzungen.- 13.13.2 Rückwärtsfehleranalyse.- 13.13.3 Nachiteration.- 13.13.4 Experimentelle Konditionsuntersuchung.- 13.14 Verfahren für Ausgleichsprobleme.- 13.14.1 Normalgleichungen.- 13.14.2 QR-Verfahren.- 13.15 LAPACK ― Das fundamentale Softwarepaket für die Lineare Algebra.- 13.15.1 Die Vorgeschichte.- 13.15.2 LAPACK und die BLAS.- 13.15.3 Blockalgorithmen.- 13.15.4 Inhaltliche Gliederung des LAPACK.- 13.16 LAPACK-Black-box-Programme.- 13.16.1 Lineare Gleichungssysteme.- 13.16.2 Lineare Ausgleichsprobleme.- 13.17 LAPACK-Rechenprogramme.- 13.17.1 Fehlerschranken.- 13.17.2 Orthogonale Faktorisierungen.- 13.17.3 Singulärwertzerlegung (SVD).- 13.18 LAPACK-Dokumentation.- 13.18.1 Parameter.- 13.18.2 Fehlerbehandlung.- 13.19 LAPACK-Speicherorganisation.- 13.19.1 Konventionelle Speicherung.- 13.19.2 Gepackte Speicherung.- 13.19.3 Speicherung von Bandmatrizen.- 13.19.4 Tridiagonal- und Bidiagonalmatrizen.- 13.19.5 Orthogonale oder unitäre Matrizen.- 13.20 Blockgröße für Blockalgorithmen.- 13.21 LAPACK-Varianten und Erweiterungen.- 14 Nichtlineare Gleichungen.- 14.1 Iterationsverfahren.- 14.1.1 Fixpunkt-Iteration.- 14.1.2 Konvergenz von Iterationsverfahren.- 14.1.3 Konvergenzgeschwindigkeit.- 14.1.4 Startwertbestimmung.- 14.1.5 Abbruch einer Iteration.- 14.2 Skalare nichtlineare Gleichungen.- 14.2.1 Vielfachheit einer Nullstelle.- 14.2.2 Kondition des Nullstellenproblems.- 14.2.3 Bisektions-Verfahren.- 14.2.4 Newton-Verfahren.- 14.2.5 Sekanten-Verfahren.- 14.2.6 Müller-Verfahren.- 14.2.7 Effizienzvergleich.- 14.2.8 Konvergenzbeschleunigung.- 14.2.9 Polyalgorithmen.- 14.2.10 Polynom-Nullstellen.- 14.3 Systeme nichtlinearer Gleichungen.- 14.3.1 Verallgemeinerte lineare Verfahren.- 14.3.2 Newton-Verfahren.- 14.3.3 Sekanten-Verfahren.- 14.3.4 Modifikationsverfahren.- 14.3.5 Große nichtlineare Systeme.- 14.4 Nichtlinearer Ausgleich.- 14.4.1 Minimierungsverfahren.- 14.4.2 Levenberg-Marquardt-Verfahren.- 14.4.3 Powell-Verfahren.- 14.4.4 Spezielle Funktionen.- 15 Eigenwerte und Eigenvektoren.- 15.1 Mathematische Grundlagen.- 15.1.1 Das charakteristische Polynom.- 15.1.2 Ähnlichkeit.- 15.1.3 Eigenvektoren.- 15.1.4 Unitär-Ähnlichkeit.- 15.1.5 Ähnlichkeit zu (Quasi-) Diagonalmatrizen.- 15.1.6 Eigenwert-Abschätzungen.- 15.2 Kondition des Eigenwertproblems.- 15.3 Vektoriteration.- 15.3.1 Inverse Iteration.- 15.3.2 Inverse Iteration mit Spektral Verschiebungen.- 15.4 QR-Algorithmus.- 15.4.1 QR-Algorithmus mit Spektralverschiebungen.- 15.4.2 Aufwandsreduktion bei QR-Algorithmen.- 15.5 Transformation auf Diagonalform.- 15.6 Transformation auf Hessenberg-Form.- 15.6.1 Givens-Verfahren.- 15.6.2 Householder-Verfahren.- 15.7 LAPACK-Programme.- 15.7.1 Symmetrische Eigenprobleme.- 15.7.2 Nichtsymmetrische Eigenprobleme.- 15.7.3 Singulärwertzerlegung (SVD).- 15.7.4 Allgemeine symmetrische Eigenprobleme.- 15.7.5 Allgemeine nichtsymmetrische Eigenprobleme.- 16 Große schwach besetzte Systeme.- 16.1 Speicherung für iterative Verfahren.- 16.1.1 COO-Format: Koordinatenformat.- 16.1.2 CRS-Format: Komprimierte Zeilenspeicherung.- 16.1.3 MRS-Format: Modifiziertes CRS-Format.- 16.1.4 CCS-Format: Komprimierte Spaltenspeicherung.- 16.1.5 BCRS-Format: Blockweises CRS-Format.- 16.1.6 CDS-Format: Komprimiertes Diagonalenformat.- 16.1.7 BND- bzw. LAPACK-Format für Bandmatrizen.- 16.1.8 JDS-Format: Verschobenes Diagonalenformat.- 16.1.9 SKS-Format: Skyline-Speicherung.- 16.2 Speicherung symmetrischer Matrizen.- 16.3 Speicherung für direkte Verfahren.- 16.3.1 Bandformat.- 16.3.2 Allgemeine Speicherformate.- 16.4 Vergleich der Speicherformate.- 16.5 Direkte Verfahren.- 16.5.1 Gauß-Elimination für schwach besetzte Systeme.- 16.5.2 Bandmatrizen.- 16.5.3 Poisson-Matrizen.- 16.5.4 Matrizen mit allgemeiner Struktur.- 16.6 Iterative Verfahren.- 16.7 Minimierungsverfahren.- 16.7.1 Einzelschritt- (Gauß-Seidel-) Verfahren.- 16.7.2 Gradientenverfahren.- 16.7.3 Gesamtschritt- (Jacobi-) Verfahren.- 16.7.4 Verfahren der konjugierten Gradienten.- 16.7.5 Krylov-Verfahren.- 16.8 Stationäre iterative Verfahren.- 16.8.1 Jacobi-Verfahren.- 16.8.2 Gauß-Seidel-Verfahren.- 16.8.3 Überrelaxationsverfahren (SOR-Verfahren).- 16.8.4 Symmetrisches SOR-Verfahren (SSOR-Verfahren).- 16.9 Nichtstationäre iterative Verfahren.- 16.9.1 Verfahren der konjugierten Gradienten (CG-Verfahren).- 16.9.2 CG-Verfahren für Normalgleichungen.- 16.9.3 Residuenminimierung (MINRES-Verfahren) und symmetrisches LQ-Verfahren.- 16.9.4 Verallgemeinerte Minimierung des Residuums (GMRES- Verfahren).- 16.9.5 Bikonjugiertes Gradientenverfahren (BiCG-Verfahren).- 16.9.6 Quasi-Residuenminimierung (QMR-Verfahren).- 16.9.7 Quadriertes CG-Verfahren (CGS-Verfahren).- 16.9.8 Bikonjugiertes stabilisiertes Gradientenverfahren (BiCGSTAB-Verfahren).- 16.9.9 Tschebyscheff-Iteration.- 16.10 Vorkonditionierung.- 16.10.1 Jacobi-Vorkonditionierung.- 16.10.2 SSOR-Vorkonditionierung.- 16.10.3 Unvollständige Faktorisierung.- 16.10.4 Unvollständige Blockfaktorisierung.- 16.10.5 Unvollständige LQ-Faktorisierung.- 16.10.6 Polynomial Vorkonditionierung.- 16.11 Matrix-Vektor-Produkte.- 16.11.1 Matrix-Vektor-Produkt im CRS-Format.- 16.11.2 Matrix-Vektor-Produkt im CDS-Format.- 16.12 Parallelisierung.- 16.13 Auswahl eines iterativen Verfahrens.- 16.13.1 Eigenschaften iterativer Verfahren.- 16.13.2 Fallstudie: Vergleich iterativer Verfahren.- 16.14 Software für schwach besetzte Systeme.- 16.15 Elementare Software.- 16.15.1 Harwell-Boeing-Collection.- 16.15.2 SPARSE-BLAS.- 16.15.3 SPARSKIT.- 16.16 Softwarepakete für Gleichungssysteme.- 16.16.1 ITPACK.- 16.16.2 TEMPLATES.- 16.16.3 SLAP.- 16.16.4 Y12M.- 16.16.5 UMFPACK.- 16.16.6 PIM.- 16.17 Programme aus Softwarebibliotheken.- 16.17.1 IMSL-Softwarebibliotheken.- 16.17.2 NAG-Softwarebibliotheken.- 16.17.3 Harwell-Bibliothek.- V Stochastische Modelle.- 17 Zufallszahlen.- 17.1 Zufallszahlengeneratoren.- 17.2 Erzeugung gleichverteilter Zufallszahlen.- 17.2.1 Lineare Kongruenzgeneratoren.- 17.2.2 Fibonacci-Generatoren.- 17.2.3 Subtraktionsgeneratoren mit Übertrag.- 17.2.4 Mehrdimensionale gleichverteilte Zufallsvektoren.- 17.2.5 Verbesserung von Zufallszahlengeneratoren.- 17.3 Erzeugung nicht-gleichverteilter Zufallszahlen.- 17.3.1 Inversionsmethode für univariate Verteilungen.- 17.3.2 Ablehnungsmethode.- 17.3.3 Zusammensetzungsmethode.- 17.4 Testen von Zufallszahlen.- 17.5 Software für die Zufallszahlenerzeugung.- 17.5.1 Programmiersprachen.- 17.5.2 IMSL.- 17.5.3 NAG.- Symbolverzeichnis.- Literatur.- Autoren.