Einführung in die Methoden der Numerischen Mathematik: für Mathematiker, Informatiker und Interessenten der naturwissenschaftlichen Fächer

Dieses Buch wendet sich an Studenten der Mathematik bis zum Vordiplom, an Informatiker und an Interessenten aus anderen naturwissenschaftlichen Fächern. Vorausgesetzt werden nur Grundkenntnisse der Analysis und der linearen Algebra. Das Buch entstand aus einer einsemestrigen, dreistündigen Vorlesung, die der erst­ genannte Verfasser wiederholt an der TU Braunschweig hielt. Es bringt eine elemen­ tare Einführung in die Methoden der numerischen Mathematik. Hauptanliegen ist es, die Grundideen der algorithmischen Lösung verschiedenster mathematischer Aufgaben möglichst klar werden zu lassen, um den Studenten in die Lage zu ver­ setzen, verwandte Fragestellungen selbständig zu bearbeiten sowie die erlernten Prinzipien auf neue Probleme anzuwenden. Um bei den Studenten die Freude an der Praxis zu wecken, sollte der Stoff mög­ lichst lebendig dargestellt werden, ohne die Grundgedanken der Verfahren mit bezeichnungs-und beweistechnischen Schwierigkeiten zu überdecken. Um praxisnah zu sein, sind die Algorithmen stets in einer Algol 60 ähnlichen Schreibweise angegeben, die unmittelbar programmierbar ist. An einfachen Bei­ spielen wird der Ablauf der Verfahren demonstriert. Besonderen Dank verdient Frl. Dr. Ingrid Brückner, die die erste Vorlesungsmit­ schrift anfertigte und am Entstehen des Buches wesentlich beteiligt war. Für ihre Mithilfe beim Lesen der Korrekturen danken wir Frl. Dr. Brückner, Herrn Prof. Dr. Homuth und Herrn cand. math. Jürgen Rüger. Wolfenbüttel und Stuttgart Wolfgang Böhm und Günther Gose im Frühjahr 1977 IV Inhaltsverzeichnis Vorwort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . III . . . . . . . . . . . I. Grundbegriffe 1. Algorithmen und Fehlerfortpflanzung . . . . . . . . . . . . . . . . . . . ... . 1 . . . . 1.1. Algorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 1 . . . . . . . . 1.2. Realisierung von Algorithmen .................................. 2 1.3. Die Beurteilung von Algorithmen ................................ 2 1.4. Aufgaben und Ergänzungen. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 3 . . . . . .

I. Grundbegriffe.- 1. Algorithmen und Fehlerfortpflanzung.- 1.1. Algorithmen.- 1.2. Realisierung von Algorithmen.- 1.3. Die Beurteilung von Algorithmen.- 1.4. Aufgaben und Ergänzungen.- 2. Matrizen.- 2.1. Bezeichnungen.- 2.2. Matrizenprodukte.- 2.3. Das Schema von Falk.- 2.4. Rang und Determinante.- 2.5. Norm und Konvergenz.- 2.6. Aufgaben und Ergänzungen.- II. Lineare Gleichungen und Ungleichungen.- 3. Der Algorithmus von Gauß.- 3.1. Rückwärtseinsetzen.- 3.2. Der Algorithmus von Gauß.- 3.3. Pivotsuche.- 3.4. Aufgaben und Ergänzungen.- 4. Die LR-Zerlegung.- 4.1. Die LR-Zerlegung von A.- 4.2. LR-Zerlegung mit Pivotsuche.- 4.3. Lineare Gleichungssysteme.- 4.4. Aufgaben und Ergänzungen.- 5. Das Austauschverfahren.- 5.1. Variablentausch.- 5.2. Schema und Algorithmus.- 5.3. Inversion.- 5.4. Lineare Gleichungen.- 5.5. Aufgabenp und Ergänzungen.- 6. Die Cholesky-Zerlegung.- 6.1 Symmetrische Zerlegung.- 6.2 Existenz und Eindeutigkeit.- 6.3 Symmetrische lineare Gleichungssysteme.- 6.4 Nachiteration.- 6.5. Aufgaben und Ergänzungen.- 7. Die QR-Zerlegung.- 7.1. Die Householdertransformation.- 7.2. Der Algorithmus von Householder.- 7.3. Lineare Gleichungssysteme.- 7.4. Aufgaben und Ergänzungen.- 8. Relaxation.- 8.1. Koordinatenrelaxation.- 8.2. Konvergenz bei diagonaldominanten Matrizen.- 8.3. Das Minimumproblem.- 8.4. Konvergenz bei symmetrischen, positiv definiten Matrizen.- 8.5. Geometrische Deutung.- 8.6. Aufgaben und Ergänzungen.- 9. Lineares Ausgleichen.- 9.1. Überbestimmte lineare Gleichungssysteme.- 9.2. Die Verwendung der QR-Zerlegung.- 9.3. Anwendung.- 9.4. Unterbestimmte lineare Gleichungssysteme.- 9.5.Anwendung.- 9.6. Geometrische Deutung und Dualität.- 9.7. Aufgaben und Ergänzungen.- 10. Lineare Optimierung.- 10.1. Lineare Ungleichungen und lineares Programm.- 10.2. Eckentausch und Simplexverfahren.- 10.3. Elimination.- 10.4. Ausgleichen nach Tschebyscheff.- 10.5. Aufgaben und Ergänzungen.- III. Iteration.- 11. Vektoriteration.- 11.1. Das Eigenwertproblem für Matrizen.- 11.2. Die Modalmatrix.- 11.3. Vektoriteration nach von Mises.- 11.4. Inverse Iteration.- 11.5. Verbesserung einer Näherung.- 11.6. Aufgaben und Ergänzungen.- 12. Der LR-Algorithmus.- 12.1. Der Algorithmus von Rutishauser.- 12.2. Der Konvergenzbeweis.- 12.3. Betragsgleiche Eigenwertpaare.- 12.4. Aufgaben und Ergänzungen.- 13. Eindimensionale Iteration.- 13.1. Kontrahierende Abbildungen.- 13.2. Fehlerabschätzungen.- 13.3. Konvergenzgeschwindigkeit.- 13.4. Das ?2-Verfahren von Aitken.- 13.5. Geometrische Konvergenzbeschleunigung.- 13.6. Nullstellen.- 13.7. Aufgaben und Ergänzungen.- 14. Mehrdimensionalelteration.- 14.1. Kontrahierende Abbildungen.- 14.2. Konvergenzgeschwindigkeit.- 14.3. Konvergenzbeschleunigung.- 14.4. Nullstellen von Systemen.- 14.5. Aufgaben und Ergänzungen.- 15. Nullstellen von Polynomen.- 15.1. Das Horner-Schema.- 15.2. Das erweiterte Horner-Schema.- 15.3. Einfache Nullstellen.- 15.4. Das Verfahren von Bairstow.- 15.5. Das erweiterte Horner-Schema für quadratische Faktoren.- 15.6. Aufgaben und Ergänzungen.- 16. Das Verfahren von Bernoulli.- 16.1. Lineare Differenzengleichungen.- 16.2. Matrixschreibweise.- 16.3. Das Verfahren von Bernoulli.- 16.4. Inverse Iteration.- 16.5. Aufgaben und Ergänzungen.- 17. Das QD-Schema.- 17.1. Der LR-Algorithmus für tridiagonale Matrizen.- 17.2. Das QD-Schema für Polynome.- 17.3. Betragsgleiche Wurzelpaare.- 17.4. Aufgaben und Ergänzungen.- IV. Interpolation und diskrete Approximation.- 18. Interpolation.- 18.1. Interpolationspolynome.- 18.2. Lagrange-Polynome.- 18.3. Lagrange-Interpolation.- 18.4. Newton-Interpolation.- 18.5. Mehrdimensionale Interpolation.- 18.6. Das Lemma von Aitken.- 18.7. Das Schema von Neville.- 18.8. Aufgaben und Ergänzungen.- 19. Diskrete Approximation.- 19.1. Die Taylorentwicklung.- 19.2. Das Stützpolynom.- 19.3. Tschebyscheff-Approximation.- 19.4. Tschebyscheff-Polynome.- 19.5. Die Minimumeigenschaft.- 19.6. Entwicklung nach Tschebyscheff-Polynomen.- 19.7. Das Ökonomisieren eines Polynoms.- 19.8. Die Methode der kleinsten Quadrate.- 19.9. Die Orthogonalität der Tschebyscheff-Polynome.- 19.10. Aufgaben und Ergänzungen.- 20. Bézierpolynome.- 20.1. Bernsteinpolynome.- 20.2. Bézier-Polynome.- 20.3. Die Konstruktion von Punkt und Tangente.- 20.4. Bézier-Flächen.- 20.5. Aufgaben und Ergänzungen.- 21. Splines und Subsplines.- 21.1. Bézier-Kurven.- 21.2. Differenzierbarkeitsbedingungen.- 21.3. Kubische Splines und Subsplines.- 21.4. Die Minimaleigenschaft.- 21.5. Aufgaben und Ergänzungen.- V. Numerische Differentiation und Integration.- 22. Numerische Differentiation und Integration.- 22.1.Differentiation des Stützpolynoms.- 22.2.Fehlerabschätzung für die numerische Differentiation.- 22.3.Integration des Stützpolynoms.- 22.4.Summation.- 22.5.Fehlerabschätzung für die numerische Integration.- 22.6.Aufgaben und Ergänzungen.- 23. Extrapolation.- 23.1. Näherungsfolgen.- 23.2. Richardson-Extrapolation.- 23.3. Wiederholte Richardson-Extrapolation.- 23.4. Romberg-Integration.- 23.5. Aufgaben und Ergänzungen.- 24. Einschrittverfahren für Differentialgleichungen.- 24.1. Diskretisierung.- 24.2. Der Diskretisierungsfehler.- 24.3. Die Verfahren von Runge-Kutta.- 24.4. Paare von Runge-Kutta-Verfahren.- 24.5. Schrittweitensteuerung.- 24.6. Aufgaben und Ergänzungen.- 25. Lineare Mehrschrittverfahren für Differentialgleichungen.- 25.1. Diskretisierung.- 25.2. Die Konvergenz eines Mehrschrittverfahrens.- 25.3. Die Wurzelbedingung.- 25.4. Hinreichende Konvergenzbedingung.- 25.5. Die Anlaufrechnung.- 25.6. Prediktor-Korrektor Verfahren.- 25.7. Die Schrittweitensteuerung.- 25.8. Vergleich von Einschritt-und Mehrschrittverfahren.- 25.9. Aufgaben und Ergänzungen.