Numerische Mathematik

Gleichgewichtslage eines Feder-Masse-Systems:

Masse m sei zwischen zwei Federn eingespannt, die durch das Gewicht symmetrisch nach unten auslenkt werden
bei waagerechter Position seien beide Federn entspannt (keine Vorspannung)
Kräftebilanz zur Bestimmung der Gleichgewichtsposition x liefert nicht-lineare Gleichung

Existenz und Eindeutigkeit von Lösungen:

keine allgemeinen Aussagen möglich
vgl. Beispiel
- cos(x) = a (x - 2)²
leicht in eine Grundform überführbar, z.B.
- f(x) = 0 (Nullstellenform)
- f(x) = x (Fixpunktform)
auch mehrdimensional (x, f Vektoren), aber noch viel schwerer
häufige Ausgangssituation
- stetige Funktion f
- Startintervall [x₁ x₂] mit f(x₁) f(x₂) < 0 (d.h. verschiedene Vorzeichen)
Mittelwertsatz → es gibt (mindestens!) eine Lösung
schwieriger: Nullstellen ohne Vorzeichenwechsel (wie bei x² = 0)

Standardbeispiele im Folgenden:

Beispiel 1 ("normal")
- Startintervall [4.8, 5.5]
- f(4.8) = -7.861819
- f(5.5) = 2.292519
Beispiel 2 ("bösartig")
- Startintervall [1 3]
- f(1) = -1
- f(3) = 1

Bisektionsverfahren:

stetiges f wechsle Vorzeichen auf [a b]

einfaches Verfahren mit ständiger Intervallhalbierung

wiederhole bis Intervallbreite < delta
   bestimme Mittelpunkt xm = (a + b)/2
   berechne Vorzeichen von f(xm)
   wenn f(b) f(xm) < 0
      neues Intervall [xm b]
   sonst
      neues Intervall [a xm]

funktioniert immer (bei exakter Arithmetik)

beim Standardbeispiel (nachrechnen mit kap04.m)

        a                    b                  xm           f(xm)
---------------------------------------------------------------------
 4.800000000000000   5.500000000000000   5.150000000000000  +1.28e+00
 4.800000000000000   5.150000000000000   4.975000000000000  -2.47e-01
 4.975000000000000   5.150000000000000   5.062500000000000  +7.08e-01
 4.975000000000000   5.062500000000000   5.018750000000000  +2.99e-01
 4.975000000000000   5.018750000000000   4.996874999999999  +4.69e-02
 4.975000000000000   4.996874999999999   4.985937499999999  -9.40e-02
 4.985937499999999   4.996874999999999   4.991406249999999  -2.21e-02
 4.991406249999999   4.996874999999999   4.994140624999999  +1.27e-02
 4.991406249999999   4.994140624999999   4.992773437499999  -4.63e-03
 4.992773437499999   4.994140624999999   4.993457031249999  +4.07e-03
 4.992773437499999   4.993457031249999   4.993115234374999  -2.75e-04
 4.993115234374999   4.993457031249999   4.993286132812499  +1.90e-03
 4.993115234374999   4.993286132812499   4.993200683593749  +8.12e-04
 4.993115234374999   4.993200683593749   4.993157958984374  +2.69e-04
 4.993115234374999   4.993157958984374   4.993136596679687  -2.80e-06
 4.993136596679687   4.993157958984374   4.993147277832030  +1.33e-04
 4.993136596679687   4.993147277832030   4.993141937255858  +6.51e-05
 4.993136596679687   4.993141937255858   4.993139266967773  +3.12e-05
 4.993136596679687   4.993139266967773   4.993137931823730  +1.42e-05
 4.993136596679687   4.993137931823730   4.993137264251708  +5.69e-06
 4.993136596679687   4.993137264251708   4.993136930465697  +1.45e-06
 4.993136596679687   4.993136930465697   4.993136763572692  -6.76e-07
 4.993136763572692   4.993136930465697   4.993136847019194  +3.86e-07
 4.993136763572692   4.993136847019194   4.993136805295944  -1.45e-07
 4.993136805295944   4.993136847019194   4.993136826157569  +1.20e-07
 4.993136805295944   4.993136826157569   4.993136815726756  -1.23e-08
 4.993136815726756   4.993136826157569   4.993136820942162  +5.40e-08
 4.993136815726756   4.993136820942162   4.993136818334460  +2.08e-08
 4.993136815726756   4.993136818334460   4.993136817030608  +4.26e-09
 4.993136815726756   4.993136817030608   4.993136816378682  -4.03e-09
 4.993136816378682   4.993136817030608   4.993136816704645  +1.13e-10
 4.993136816378682   4.993136816704645   4.993136816541663  -1.96e-09
 4.993136816541663   4.993136816704645   4.993136816623155  -9.24e-10
 4.993136816623155   4.993136816704645   4.993136816663900  -4.06e-10
 4.993136816663900   4.993136816704645   4.993136816684272  -1.46e-10
 4.993136816684272   4.993136816704645   4.993136816694459  -1.69e-11
 4.993136816694459   4.993136816704645   4.993136816699552  +4.79e-11
 4.993136816694459   4.993136816699552   4.993136816697005  +1.55e-11
 4.993136816694459   4.993136816697005   4.993136816695731  -6.79e-13
 4.993136816695731   4.993136816697005   4.993136816696368  +7.42e-12
 4.993136816695731   4.993136816696368   4.993136816696049  +3.37e-12
 4.993136816695731   4.993136816696049   4.993136816695890  +1.34e-12
 4.993136816695731   4.993136816695890   4.993136816695811  +3.38e-13
 4.993136816695731   4.993136816695811   4.993136816695771  -1.70e-13
 4.993136816695771   4.993136816695811   4.993136816695792  +8.93e-14
 4.993136816695771   4.993136816695792   4.993136816695781  -4.66e-14
 4.993136816695781   4.993136816695792   4.993136816695786  +2.13e-14
 4.993136816695781   4.993136816695786   4.993136816695784  -1.24e-14
 4.993136816695784   4.993136816695786   4.993136816695785  -8.88e-16
 4.993136816695785   4.993136816695786   4.993136816695785  +1.02e-14

Problem mit Rechnerarithmetik
- Wie klein darf Abbruchbreite δ (= Genauigkeit des Ergebnisses) sein?
- sinnvoller Minimalwert: δ = ε*abs(a)
- bei "problematischen" Funktionen viel früher
- vgl. Funktion B im Polynom-Plot

Newton-Verfahren:

Idee: nähere Funktion durch Tangente
Tangente durch x_n
x_n+1 = Nullstelle der Tangente →

Standardbeispiel 1

4.800000000000000
4.860313493747295
4.930340369122104
4.979104035027125
4.992436030128772
4.993135068876532
4.993136816684912
4.993136816695785
4.993136816695785

konvergiert hier sehr viel schneller als Bisektionsverfahren
Standardbeispiel 2
- ```
 3.5
 0.5
 3.5
 0.5
 ...
```
Probleme
- konvergiert nur in der Nähe der Lösung ("lokal")
- Ableitung von f wird benötigt

Konvergenz-Geschwindigkeit:

Sei x die exakte Lösung, ε_i := |x_i - x| der Fehler im i-ten Schritt. Gibt es ein p ≥ 1 und ein c mit 0 ≤ c < 1, so dass gilt
dann heißt p die Konvergenzordnung der Folge x_i.
etwas laxer ausgedrückt: Der Fehler sinkt etwa wie
Beispiel Bisektionsverfahren
- Fehler wird in jedem Schritt halbiert
- also p = 1, c = 1/2
bei Newton ist p = 2 (falls f'(x) ≠ 0) (Beweis: [3])

Sekanten-Verfahren:

Idee: nähere die Tangente bei Newton durch die Sekante durch die letzten zwei Punkte
konkret

Standardbeispiel 1

 5.500000000000000
 4.800000000000000
 5.341962754641359
 5.233078480512697
 4.692715063982089
 5.249938048452647
 5.267980603914145
 4.740153341717683
 5.240757795434711
 5.216227584826059
 4.795417173225895
 5.150185032751038
 5.103681829226098
 4.931222941473443
 5.017500486888689
 4.998505040389419
 4.992671292678041
 4.993145710865901
 4.993136831431582
 4.993136816695318
 4.993136816695785
 4.993136816695785

Konvergenzordnung p = 1.618 (vgl. [2])
Probleme
- konvergiert nur in der Nähe der Lösung ("lokal")
- Sekantensteigung wird ungenau (Subtraktion ähnlicher Zahlen)

Inverse quadratische Interpolation (IQI):

Idee: statt einer Geraden durch die letzten zwei Punkte bestimme eine Parabel durch die letzten drei Punkte
Problem: Parabel hat evtl. keine Nullstelle
Lösung: wähle "inverse Parabel"
konkret
- ggb. letzte drei Werte x₁, x₂, x₃ und Funktionswerte y_i = f(x_i)
- Einsetzen der Punkte in Parabelgleichung liefert lineares System für (a b c)
- nächster Punkt = Schnittpunkt von Parabel und x-Achse = c
- x₄ = c

Standardbeispiel 1

 4.800000000000000
 5.500000000000000
 5.150000000000000
 4.796299397999127
 4.792545722045462
 5.071630116446963
 5.032407352330408
 4.985297936065732
 4.992830056897817
 4.993138014176794
 4.993136816732284
 4.993136816695785
 4.993136816695785

Konvergenzordnung p = 1.839 (vgl. [2])
Probleme
- konvergiert nur in der Nähe der Lösung ("lokal")
- Probleme, wenn zwei der drei Funktionswerte f(x_i) fast gleich sind

Aufgaben:

Grundlegende Methoden bei einer Unbekannten