Numerische Methoden – Annähern statt exakt lösen

Einführung

Die meisten interessanten mathematischen Probleme der realen Welt haben keine schöne, geschlossene Lösung. Die Gleichung $x^3 - 2x + 0{,}5 = 0$ lässt sich nicht elegant nach $x$ umformen. Das Integral $\int_0^1 e^{-x^2} dx$ hat keine elementare Stammfunktion. Und dennoch brauchen Ingenieure, Physiker und Ökonomen genaue Antworten. Die Lösung: numerische Methoden – systematische Verfahren, die sich schrittweise an die exakte Antwort annähern, bis die Genauigkeit ausreicht.

Grundidee

Statt einer exakten Lösung berechnet man eine Näherungslösung mit kontrolliertem Fehler. Die Kernidee ist Iteration: Man startet mit einer Schätzung und verbessert sie Schritt für Schritt, bis das Ergebnis „gut genug” ist. Wie gut genug? Das hängt vom Problem ab – für GPS reichen ein paar Zentimeter, für Atomsimulationen müssen Fehler kleiner als $10^{-12}$ sein.

Erklärung

Warum numerische Methoden?

Drei Gründe, warum exakte Lösungen oft unmöglich oder unpraktisch sind:

1. Keine geschlossene Form: Polynome ab Grad 5, transzendente Gleichungen ($e^x = x$), die meisten Differentialgleichungen.
2. Rechenzeitaufwand: Exakte symbolische Berechnung ist oft exponentiell teurer als eine Näherung.
3. Datenunsicherheit: Wenn die Eingabedaten selbst fehlerbehaftet sind (Messungen!), ist übertriebene Exaktheit sinnlos.

Newton-Verfahren (Newton-Raphson)

Das Newton-Verfahren findet Nullstellen einer differenzierbaren Funktion $f$:

Idee: An der aktuellen Schätzung $x_n$ legt man die Tangente an die Funktion. Wo schneidet diese Tangente die x-Achse? Das ist die verbesserte Schätzung $x_{n+1}$.

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

Beispiel: Nullstelle von $f(x) = x^2 - 2$ (also $\sqrt{2}$), Startwert $x_0 = 1$:

$n$	$x_n$	$f(x_n)$
0	1.0000	-1.0000
1	1.5000	0.2500
2	1.4167	0.0069
3	1.4142	0.000006

Das Newton-Verfahren konvergiert quadratisch: Die Anzahl korrekter Dezimalstellen verdoppelt sich etwa bei jedem Schritt.

Wann versagt es? Wenn $f'(x_n) \approx 0$ (Division durch fast Null), bei mehreren Nullstellen (falscher Zweig), oder bei schlechtem Startwert.

Intervallhalbierung (Bisektionsverfahren)

Robustere Alternative zum Newton-Verfahren:

Idee: Wenn $f(a) < 0$ und $f(b) > 0$ (oder umgekehrt), muss nach dem Zwischenwertsatz eine Nullstelle in $[a, b]$ liegen. Berechne den Mittelpunkt $m = \frac{a+b}{2}$. Je nach Vorzeichen von $f(m)$ liegt die Nullstelle in $[a, m]$ oder $[m, b]$. Halbiere das Intervall und wiederhole.

$m = \frac{a+b}{2}, \quad \text{neues Intervall: } \begin{cases} [a, m] & \text{falls } f(a)\cdot f(m) < 0 \\ [m, b] & \text{falls } f(m) \cdot f(b) < 0 \end{cases}$

Konvergenz: linear – nach $n$ Schritten ist der Fehler kleiner als $\frac{b-a}{2^n}$. Langsamer als Newton, aber immer konvergent (solange eine Nullstelle im Intervall liegt).

Numerische Integration

Viele Integrale haben keine elementare Stammfunktion. Statt exakt zu integrieren, approximiert man die Fläche unter der Kurve.

Trapezregel: Teile $[a, b]$ in $n$ gleiche Teilintervalle der Breite $h = \frac{b-a}{n}$ auf. Ersetze die Kurve auf jedem Teilintervall durch eine Gerade (Trapez):

$\int_a^b f(x)\,dx \approx h \left[\frac{f(x_0)}{2} + f(x_1) + f(x_2) + \cdots + f(x_{n-1}) + \frac{f(x_n)}{2}\right]$

Simpson-Regel: Nutze statt Geraden quadratische Parabeln – genauere Approximation:

$\int_a^b f(x)\,dx \approx \frac{h}{3}\left[f(x_0) + 4f(x_1) + 2f(x_2) + 4f(x_3) + \cdots + f(x_n)\right]$

(mit $n$ gerade)

Vergleich der Fehler: Trapezregel $\sim O(h^2)$, Simpson $\sim O(h^4)$ – Simpson ist deutlich genauer bei gleichem Rechenaufwand.

Fehleranalyse

Zwei grundlegende Fehlertypen:

Abbruchfehler (Diskretisierungsfehler): Entsteht durch das Abbrechen einer unendlichen Reihe oder durch die Diskretisierung eines kontinuierlichen Problems. Kleiner $h$ → kleinerer Abbruchfehler.

Rundungsfehler: Computer rechnen mit endlicher Stellenzahl (64-Bit-Gleitkomma: ca. 15–16 Dezimalstellen). Jede Operation erzeugt minimale Ungenauigkeiten. Bei vielen Operationen können sich Rundungsfehler aufschaukeln (Fehlerfortpflanzung).

Das Dilemma: Kleineres $h$ reduziert Abbruchfehler, aber erhöht die Anzahl der Operationen und damit den kumulativen Rundungsfehler. Es gibt ein optimales $h$.

Konvergenz und Fixpunktsätze

Ein iteratives Verfahren konvergiert, wenn die Folge $x_0, x_1, x_2, \ldots$ gegen einen Grenzwert strebt.

Fixpunkt: Ein Punkt $x^*$ mit $g(x^*) = x^*$ heißt Fixpunkt der Funktion $g$. Wenn man das Newton-Verfahren als $g(x) = x - \frac{f(x)}{f'(x)}$ schreibt, ist die Nullstelle von $f$ ein Fixpunkt von $g$.

Der Banach’sche Fixpunktsatz garantiert Konvergenz, wenn $g$ eine Kontraktion ist (benachbarte Punkte werden näher zusammengebracht).

Beispiel aus dem Alltag

GPS: Die Position des Empfängers wird durch ein nichtlineares Gleichungssystem aus Satellitendistanzen bestimmt. Die exakte Lösung ist analytisch kompliziert – stattdessen verwendet der GPS-Chip iterative Verfahren, die in Millisekunden konvergieren.

Wettervorhersage: Die Navier-Stokes-Gleichungen der Atmosphärendynamik sind partiell und nichtlinear – keine exakte Lösung möglich. Numerische Methoden (Finite-Differenzen, Spektralmethoden) diskretisieren die Atmosphäre in Millionen von Gitterpunkten.

Finite-Elemente-Methode (FEM): Beim Entwurf eines Autobauteils berechnet FEM, wie das Material unter Belastung verformt wird. Das kontinuierliche Problem wird in Tausende kleine Elemente zerlegt – ein riesiges lineares Gleichungssystem, das numerisch gelöst wird.

Anwendung

Aufgabe: Berechne mit der Trapezregel und $n = 4$ Teilintervallen: $\int_0^1 x^2 \, dx$.

Lösung: $h = 0{,}25$, Stützstellen: $x_0 = 0,\ x_1 = 0{,}25,\ x_2 = 0{,}5,\ x_3 = 0{,}75,\ x_4 = 1$.

Funktionswerte: $f(0) = 0$, $f(0{,}25) = 0{,}0625$, $f(0{,}5) = 0{,}25$, $f(0{,}75) = 0{,}5625$, $f(1) = 1$.

$T_4 = 0{,}25 \cdot \left[\frac{0}{2} + 0{,}0625 + 0{,}25 + 0{,}5625 + \frac{1}{2}\right] = 0{,}25 \cdot 1{,}375 = 0{,}34375$

Exakter Wert: $\frac{1}{3} \approx 0{,}33333$. Fehler: $\approx 0{,}010$. Mit $n = 8$ halbiert sich der Fehler auf $\approx 0{,}003$.

Typische Fehler

Newton-Verfahren ohne Startwertstrategie: Ein schlechter Startwert kann dazu führen, dass das Verfahren divergiert oder zur falschen Nullstelle konvergiert. Immer erst grafisch prüfen, wo die Nullstelle ungefähr liegt.

Trapezregel bei stark gekrümmten Funktionen: Die Trapezregel approximiert Kurven durch Geraden – bei stark gekrümmten Funktionen ist der Fehler groß. Hier liefert die Simpson-Regel oder eine adaptive Schrittweitensteuerung deutlich bessere Ergebnisse.

Fehler ignorieren: Numerische Ergebnisse ohne Fehlerabschätzung sind wertlos. Ein Ergebnis ohne Angabe der Genauigkeit ist wie ein Messwert ohne Einheit.

Zusammenfassung

Merke dir:

• Numerische Methoden nähern sich an exakte Lösungen an, wenn diese nicht analytisch bestimmbar sind
• Newton-Verfahren: quadratische Konvergenz, braucht guten Startwert und $f' \neq 0$
• Intervallhalbierung: lineare Konvergenz, aber robust – immer konvergent bei vorzeichenwechselnden Intervallen
• Trapezregel: $O(h^2)$; Simpson: $O(h^4)$ – Simpson deutlich effizienter
• Abbruchfehler durch Diskretisierung, Rundungsfehler durch endliche Computerarithmetik
• Praxisbeispiele: GPS, Wettervorhersage, FEM in der Ingenieurwissenschaft

Quiz

Frage 1: Führe einen Newton-Schritt aus für $f(x) = x^3 - x - 1$ mit Startwert $x_0 = 1{,}5$.

Antwort anzeigen

$f(1{,}5) = 3{,}375 - 1{,}5 - 1 = 0{,}875$. $f'(x) = 3x^2 - 1$, also $f'(1{,}5) = 6{,}75 - 1 = 5{,}75$. $x_1 = 1{,}5 - \frac{0{,}875}{5{,}75} \approx 1{,}5 - 0{,}152 = 1{,}348$. Die tatsächliche Nullstelle liegt bei $x^* \approx 1{,}3247$.

Frage 2: Bei der Intervallhalbierung: Du hast $f(1) = -2$ und $f(3) = 5$. Was ist der nächste Mittelpunkt, und wie schränkt sich das Intervall ein, wenn $f(2) = 1$?

Antwort anzeigen

Mittelpunkt: $m = \frac{1+3}{2} = 2$. Da $f(1) = -2 < 0$ und $f(2) = 1 > 0$, liegt die Nullstelle im Intervall $[1, 2]$. Das neue Suchintervall ist $[1, 2]$ (halbiert).

Frage 3: Warum ist die Simpson-Regel genauer als die Trapezregel bei gleichem $n$?

Antwort anzeigen

Die Trapezregel approximiert die Funktion auf jedem Teilintervall durch eine Gerade (Polynom 1. Grades). Die Simpson-Regel verwendet Parabeln (Polynome 2. Grades) – sie passt sich der Krümmung der Funktion besser an. Damit integriert die Simpson-Regel Polynome bis Grad 3 exakt, die Trapezregel nur bis Grad 1. Der Fehler der Trapezregel ist $O(h^2)$, der der Simpson-Regel $O(h^4)$.

Frage 4: Was passiert numerisch, wenn man beim Newton-Verfahren den Ableitungswert $f'(x_n) \approx 0$ erhält?

Antwort anzeigen

Der Korrekturterm $\frac{f(x_n)}{f'(x_n)}$ wird sehr groß (Division durch eine sehr kleine Zahl). Das Verfahren springt weit von der aktuellen Schätzung weg und kann divergieren oder in eine andere Region der Funktion springen. Das passiert z. B. bei Sattelpunkten oder wenn man mit einer Schätzung nahe einem lokalen Extremum startet.