Überhuber Computer-Numerik 2

1995
ISBN: 978-3-642-57794-9
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 520 Seiten, eBook

Zielgruppe

Graduate

Autoren/Hrsg.

Überhuber, Christoph

Inhaltsverzeichnis

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.