Überhuber Computer-Numerik 1

1995
ISBN: 978-3-642-57795-6
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 511 Seiten, eBook

Zielgruppe

Graduate

Autoren/Hrsg.

Überhuber, Christoph

Inhaltsverzeichnis

I Grundlagen.- 1 Modelle.- 1.1 Original und Modell.- 1.2 Modellsubjekt und Modell.- 1.2.1 Verwendungszweck von Modellen.- 1.3 Modellsubjekt und Original.- 1.4 Modellbildung.- 1.4.1 Spezifikation des Problems.- 1.4.2 Aufstellung eines Strukturkonzeptes.- 1.4.3 Auswahl des Modelltyps (Modellentwurf).- 1.4.4 Festlegung der Parameterwerte.- 1.4.5 Testen, Validieren.- 2 Grundbegriffe der Numerik.- 2.1 Vom Anwendungsproblem zur numerischen Lösung.- 2.1.1 Fallstudie: Pendel.- 2.1.2 Quantitative und qualitative Fragestellungen.- 2.2 Numerische Aufgaben.- 2.2.1 Numerische Probleme.- 2.2.2 Kategorien numerischer Probleme.- 2.2.3 Genauigkeit der Ergebnisse.- 2.3 Fehlerbegriffe der Numerik.- 2.3.1 Modellfehler.- 2.3.2 Datenfehler.- 2.3.3 Verfahrensfehler.- 2.3.4 Rundungsfehler (Rechenfehler).- 2.3.5 Fehlerhierarchie.- 2.4 Kondition mathematischer Probleme.- 2.4.1 Ungestörtes und gestörtes Problem.- 2.4.2 Absolute Konditionszahl.- 2.4.3 Relative Konditionszahl.- 2.4.4 Einschränkung der Problemklasse.- 2.4.5 Konditionszahlen durch Differentiation.- 2.4.6 Fallstudie: Quadratische Gleichung.- 2.4.7 Schlecht konditionierte Probleme.- 2.4.8 Inkorrekt gestellte Probleme.- 2.5 Kondition der Anwendungsprobleme.- 2.6 Mathematische Grundlagen der Konditionsabschätzung.- 2.6.1 Kondition direkter mathematischer Probleme.- 2.6.2 Kondition inverser mathematischer Probleme.- 2.7 Validierung numerischer Berechnungen.- 2.7.1 Unsicherheit numerischer Berechnungen.- 2.7.2 Modell-Validierung.- 2.7.3 Sensitivitätsanalyse und Fehlerschätzung.- 2.7.4 Softwarefehler.- II Lösen numerischer Probleme am Computer.- 3 Computer für die Numerische Datenverarbeitung.- 3.1 Prozessoren.- 3.1.1 Pipeline-Prinzip.- 3.1.2 Superpipeline-Architektur.- 3.1.3 Superskalar-Architekturen.- 3.1.4 Vektorprozessoren.- 3.2 Speicher.- 3.2.1 Speicherhierarchie.- 3.2.2 Adressierungsarten.- 3.2.3 Register.- 3.2.4 Cache-Speicher.- 3.2.5 Virtueller Speicher.- 3.2.6 Speicherverschränkung.- 3.3 Quantifizierung der Leistung.- 3.3.1 Der Begriff „Leistung“.- 3.3.2 Leistungsfaktor Zeit.- 3.4 Analytische Leistungsbewertung.- 3.4.1 Maximale Gleitpunktleistung.- 3.4.2 Instruktionenleistung.- 3.4.3 Leistung von Vektorprozessoren.- 3.4.4 Leistungseinfluß des Speichers.- 3.5 Empirische Leistungsbewertung.- 3.5.1 Temporale Leistung.- 3.5.2 Empirische Instruktionenleistung.- 3.5.3 Empirische Gleitpunktleistung.- 3.5.4 Empirische Leistung von Vektorprozessoren.- 4 Numerische Daten und Operationen.- 4.1 Daten der Mathematik.- 4.1.1 Elementare mathematische Daten.- 4.1.2 Algebraische Daten.- 4.1.3 Analytische Daten.- 4.2 Numerische Daten am Computer.- 4.2.1 Elementare numerische Daten.- 4.2.2 Algebraische Daten.- 4.2.3 Analytische Daten.- 4.2.4 Numerische Datentypen.- 4.3 Operationen mit numerischen Daten.- 4.3.1 Arithmetische Operationen.- 4.3.2 Algebraische Operationen.- 4.3.3 Feldverarbeitung in Fortran 90.- 4.3.4 Analytische Operationen.- 4.4 Zahlensysteme am Computer.- 4.4.1 INTEGER-Zahlensysteme.- 4.4.2 Festpunkt-Zahlensysteme.- 4.4.3 Gleitpunkt-Zahlensysteme.- 4.5 Struktur von Gleitpunkt-Zahlensystemen.- 4.5.1 Anzahl der Gleitpunktzahlen.- 4.5.2 Größte und kleinste Gleitpunktzahl.- 4.5.3 Absolute Abstände der Gleitpunktzahlen.- 4.5.4 Relative Abstände der Gleitpunktzahlen.- 4.5.5 Fallstudie: F(10,6, -9,9, true).- 4.6 Normung von Gleitpunkt-Zahlensystemen.- 4.6.1 IEC/IEEE-Norm für Gleitpunktzahlen.- 4.6.2 Implizites erstes Bit.- 4.6.3 Unendlich, NaNs und Null mit Vorzeichen.- 4.6.4 Auswirkungen auf die Programmiersprachen.- 4.7 Arithmetik in Gleitpunkt-Zahlensystemen.- 4.7.1 Rundung.- 4.7.2 Rundungsfehler.- 4.7.3 Rundung und arithmetische Operationen.- 4.7.4 Implementierung einer Gleitpunktarithmetik.- 4.7.5 Multiple-Precision-Software.- 4.8 Abfrage und Manipulation von Zahlen in Fortran 90.- 4.8.1 Parameter der Gleitpunktzahlen.- 4.8.2 Kenngrößen der Gleitpunktzahlen.- 4.8.3 Abstände der Gleitpunktzahlen, Rundung.- 4.8.4 Manipulation von Gleitpunktzahlen.- 4.8.5 Parameter der INTEGER-Zahlen.- 4.8.6 Fallstudie: Produktbildung.- 4.9 Operationen mit algebraischen Daten.- 4.10 Operationen mit Feldern.- 4.10.1 BLAS.- 4.11 Operationen mit analytischen Daten.- 4.11.1 Darstellung von Funktionen.- 4.11.2 Implementierung von Funktionen.- 4.11.3 Operationen mit Funktionen.- 4.11.4 Funktionen als Ergebnisse.- 5 Numerische Algorithmen.- 5.1 Ein intuitiver Algorithmusbegriff.- 5.2 Eigenschaften von Algorithmen.- 5.2.1 Abstraktion.- 5.2.2 Allgemeinheit.- 5.2.3 Finitheit.- 5.2.4 Terminierung.- 5.2.5 Determinismus.- 5.2.6 Determiniertheit.- 5.3 Existenz von Algorithmen.- 5.3.1 Präzisierungen des Algorithmusbegriffs.- 5.3.2 Berechenbare Punktionen.- 5.4 Praktische Lösbarkeit von Problemen.- 5.5 Komplexität von Algorithmen.- 5.5.1 Abstrakte Computermodelle.- 5.5.2 Theoretischer Abarbeitungsaufwand.- 5.5.3 Asymptotische Komplexität von Algorithmen.- 5.5.4 Komplexität von Problemen.- 5.5.5 Fallstudie: Matrizenmultiplikation.- 5.5.6 Praktische Aufwandsermittlung.- 5.6 Darstellung von Algorithmen.- 5.6.1 Fortran90.- 5.6.2 Pseudocode.- 5.7 Rundungsfehlereinfluß auf numerische Algorithmen.- 5.7.1 Arithmetische Algorithmen.- 5.7.2 Implementierung arithmetischer Algorithmen.- 5.7.3 Fehlerfortpflanzung.- 5.7.4 Analyse der Fehlerfortpflanzung.- 5.8 Fallstudie: Gleitpunktzahlen-Summation.- 5.8.1 Paarweise Summation.- 5.8.2 Fehlerkompensierende Summation.- 5.8.3 Vergleich der drei Summationsverfahren.- 5.8.4 Steigende Summation.- 6 Numerische Programme.- 6.1 Qualität numerischer Programme.- 6.1.1 Zuverlässigkeit.- 6.1.2 Portabilität.- 6.1.3 Effizienz.- 6.2 Ursachen geringer Effizienz.- 6.2.1 Fehlender Parallelismus.- 6.2.2 Mangelnde Lokalität von Speicherzugriffen.- 6.2.3 Schlechte Referenzmuster bei Speicherzugriffen.- 6.2.4 Overhead.- 6.3 Messung und Analyse von Leistungsdaten.- 6.3.1 Messung des Leistungsfaktors Arbeit.- 6.3.2 Messung des Leistungsfaktors Zeit.- 6.3.3 Untersuchung der Rechenzeitverteilung (Profiling).- 6.3.4 Ermittlung leistungshemmender Faktoren.- 6.4 Programmtransformationen zur Steigerung der Effizienz.- 6.5 Architektur-unabhängige Transformationen.- 6.6 Schleifen-Transformationen.- 6.6.1 Aufrollen von Schleifen.- 6.6.2 Aufrollen äußerer Schleifen.- 6.6.3 Schleifenverschmelzung.- 6.6.4 Eliminieren von Verzweigungen in Schleifen.- 6.6.5 Assoziative Transformationen.- 6.6.6 Schleifen-Vertauschung.- 6.6.7 Blocken von Speicherzugriffen.- 6.7 Fallstudie: Matrizenmultiplikation.- 6.7.1 Schleifenvertauschungen.- 6.7.2 Schleifenaufrollen.- 6.7.3 Blockung.- 6.7.4 Blockung mit Kopieren.- 6.7.5 Blockung mit Kopieren und Schleifenaufrollen.- 6.7.6 Optimierende System-Software.- 7 Verfügbare Numerische Software.- 7.1 Softwarekosten.- 7.2 Quellen numerischer Software.- 7.2.1 Numerische Anwendungs-Software.- 7.2.2 Einzelprogramme.- 7.2.3 Numerische Softwarebibliotheken.- 7.2.4 Numerische Softwarepakete.- 7.2.5 Softwarehinweise im vorliegenden Buch.- 7.3 Software und globale Computernetze.- 7.3.1 Internet.- 7.3.2 Kommunikation im Internet — E-mail.- 7.3.3 Diskussionsforen im Internet.- 7.3.4 Betriebsmittelverbund im Internet.- 7.3.5 Internet-Suchdienste.- 7.3.6 Netlib.- 7.3.7 eLib.- 7.3.8 GAMS.- 7.4 Interaktive multifunktionale Programmsysteme.- 7.4.1 Systeme für exploratorische Untersuchungen.- 7.4.2 Systeme für numerische Berechnungen.- 7.4.3 Systeme für symbolische Manipulationen.- 7.4.4 Systeme für die Simulation.- 7.5 Problem Solving Environments.- 7.5.1 Verfügbare Problem Solving Environments.- 7.6 Fallstudie: Software für elliptische partielle Differentialgleichungen.- 7.6.1 Klassifikationsmerkmale.- 7.6.2 Softwarepakete für elliptische Probleme.- 7.6.3 Teile numerischer Programmbibliotheken.- 7.6.4 Einzelprogramme der TOMS-Sammlung.- III Analytische Modelle.- 8 Modellbildung durch Approximation.- 8.1 Analytische Modelle.- 8.1.1 Elementare Funktionen als Modelle.- 8.1.2 Algorithmen als Modelle.- 8.2 Information und Daten.- 8.2.1 Algebraische Daten aus diskreter Information.- 8.2.2 Analytische Daten aus kontinuierlicher Information.- 8.2.3 Diskretisierung kontinuierlicher Information.- 8.2.4 Homogenisierung diskreter Daten.- 8.3 Diskrete Approximation.- 8.3.1 Daten der diskreten Approximation.- 8.3.2 Interpolation.- 8.3.3 Fallstudie: Wasserwiderstand von Booten.- 8.4 Funktionsapproximation.- 8.4.1 Nichtadaptive Diskretisierung.- 8.4.2 Adaptive Diskretisierung.- 8.4.3 Algorithmen zur Homogenisierung.- 8.4.4 Zusatzinformation.- 8.5 Wahl der Darstellungsfunktionen.- 8.5.1 Durchgehende und intervallweise Approximation.- 8.5.2 Lineare Approximation.- 8.5.3 Nichtlineare Approximation.- 8.5.4 Globale und lokale Approximation.- 8.5.5 Stetigkeit und Differenzierbarkeit.- 8.5.6 Kondition.- 8.5.7 Invarianz bei Skalierung.- 8.5.8 Nebenbedingungen.- 8.5.9 „Optische Form“.- 8.6 Wahl der Distanzfunktion.- 8.6.1 Mathematische Grundlagen.- 8.6.2 Normen für endlich-dimensionale Räume.- 8.6.3 Normen für unendlich-dimensionale Räume.- 8.6.4 Gewichtete Normen.- 8.6.5 Hamming-Distanz.- 8.6.6 Robuste Abstandsmaße.- 8.6.7 Orthogonale Approximation.- 8.7 Transformation des Problems.- 8.7.1 Ordinatentransformation.- 8.7.2 Kurven.- 9 Interpolation.- 9.1 Interpolationsprobleme.- 9.1.1 Wahl einer Funktionenklasse.- 9.1.2 Bestimmung der Parameter einer Interpolationsfunktion.- 9.1.3 Manipulation der Interpolationsfunktion.- 9.2 Mathematische Grundlagen.- 9.2.1 Das allgemeine Interpolationsprinzip.- 9.2.2 Interpolation bezüglich Wertübereinstimmung.- 9.3 Univariate Polynom-Interpolation.- 9.3.1 Univariate Polynome.- 9.3.2 Darstellungsformen univariater Polynome.- 9.3.3 Koeffizientenberechnung.- 9.3.4 Werteberechnung,.- 9.3.5 Approximations- und Konvergenzeigenschaften.- 9.3.6 Verfahrensfehler der Polynom-Interpolation.- 9.3.7 Konvergenz der Interpolationspolynome.- 9.3.8 Kondition der Polynom-Interpolation.- 9.3.9 Wahl der Interpolationsknoten.- 9.3.10 Hermite-Interpolation.- 9.4 Univariate stückweise Polynom-Interpolation.- 9.4.1 Approximationsgenauigkeit.- 9.4.2 Auswertung.- 9.5 Polynom-Splines.- 9.5.1 Überschwingen und Störungsdämpfung.- 9.5.2 Darstellung von Polynom-Splines.- 9.6 B-Splines.- 9.6.1 Wahl der B-Spline-Teüungspunkte.- 9.6.2 B-Splines in der graphischen Datenverarbeitung.- 9.6.3 Software für B-Splines.- 9.7 Kubische Splinefunktionen.- 9.7.1 Randbedingungen.- 9.7.2 Extremaleigenschaft.- 9.7.3 Approximations- und Konvergenzeigenschaften.- 9.7.4 Koeffizientenberechnung.- 9.7.5 Werteberechnung.- 9.7.6 Kondition.- 9.8 Splines mit geringem „Überschwingen“.- 9.8.1 Exponentialsplines.- 9.8.2 v-Splines.- 9.8.3 Subspline-Interpolation nach Akima.- 9.9 Multivariate Interpolation.- 9.9.1 Tensorprodukt-Interpolation.- 9.9.2 Triangulation.- 9.10 Multivariate Polynom-Interpolation.- 9.11 Multivariate (Sub-) Spline-Interpolation.- 9.11.1 Tensorprodukt-Splinefunktionen.- 9.11.2 Polynomial Interpolation auf Dreiecken.- 9.12 Andere Aufgaben und Methoden.- Symbolverzeichnis.- Literatur.- Autoren.