Numerik

Voraussetzung: $f$ stetig auf $[a, b],$ $f(a) \cdot f(b) < 0$

$a, b$

linke und rechte Grenze des aktuellen Intervalls

$m$

Mittelpunkt des Intervalls, neue Näherung

$f$

stetige Funktion, deren Nullstelle gesucht ist

Das Bisektionsverfahren halbiert ein Intervall mit Vorzeichenwechsel so lange, bis die Nullstelle genau genug eingeschlossen ist.

Voraussetzung: $y'(t) = f(t, y(t)),$ $y(t_0) = y_0,$ $h > 0$

$y_k$

Näherung für die Lösung y(t_k)

$t_k$

k-ter Zeitpunkt, t_k = t_0 + k · h

$h$

Schrittweite

$f(t, y)$

rechte Seite der Differentialgleichung y′ = f(t, y)

$y_0$

Anfangswert zur Zeit t_0

Das explizite Euler-Verfahren löst y′ = f(t, y) näherungsweise, indem es in jedem Schritt der aktuellen Steigung folgt.

Voraussetzung: $f$ zweimal stetig differenzierbar auf $[a, b],$ $h = \frac{b - a}{n}$

$T_n$

Näherung der summierten Trapezregel mit n Teilintervallen

$a, b$

Integrationsgrenzen

$h$

Schrittweite, Breite eines Teilintervalls

$n$

Anzahl der Teilintervalle

$f''$

zweite Ableitung des Integranden

Der Fehler der summierten Trapezregel ist höchstens (b − a) · h² / 12 mal das Maximum von |f″|; er sinkt quadratisch mit h.

Voraussetzung: $\varphi([a, b]) \subseteq [a, b],$ $|\varphi(x) - \varphi(y)| \leq L \, |x - y|$ auf $[a, b],$ $0 \leq L < 1,$ $x_0 \in [a, b]$

$\varphi$

Iterationsfunktion, deren Fixpunkt gesucht ist

$x_n$

n-te Näherung

$x_0$

Startwert

$x^*$

Fixpunkt, also Lösung von x = φ(x)

$L$

Kontraktionskonstante (Lipschitz-Konstante kleiner als 1)

$n$

Anzahl der Iterationsschritte

Bei der Fixpunktiteration setzt man jede Näherung wieder in φ ein; ist φ eine Kontraktion, konvergiert das gegen den Fixpunkt.

Voraussetzung: $A x = b,$ $a_{ii} \neq 0,$ $i = 1, \ldots, n$

$x_i^{(k)}$

i-te Komponente der Näherung nach k Schritten

$a_{ij}$

Einträge der Koeffizientenmatrix A

$a_{ii}$

Diagonaleinträge von A

$b_i$

Komponenten der rechten Seite b

$n$

Anzahl der Gleichungen und Unbekannten

Das Gauß-Seidel-Verfahren arbeitet wie das Jacobi-Verfahren, verwendet neu berechnete Komponenten aber sofort weiter.

Voraussetzung: $y' = f(t, y),$ $y(t_0) = y_0,$ $h > 0$ (Schrittgleichung eindeutig lösbar, z.B. bei $hL < 1$ mit Lipschitz-Konstante $L$)

$y_n$

Näherung für die Lösung y(t_n)

$t_n$

n-ter Zeitpunkt, t_n = t_0 + n · h

$h$

Schrittweite

$f(t, y)$

rechte Seite der Differentialgleichung y′ = f(t, y)

Das implizite Euler-Verfahren nimmt die Steigung am neuen Punkt; dafür muss man in jedem Schritt eine Gleichung lösen.

Voraussetzung: $A x = b,$ $a_{ii} \neq 0,$ $i = 1, \ldots, n$

$x_i^{(k)}$

i-te Komponente der Näherung nach k Schritten

$a_{ij}$

Einträge der Koeffizientenmatrix A

$a_{ii}$

Diagonaleinträge von A

$b_i$

Komponenten der rechten Seite b

$n$

Anzahl der Gleichungen und Unbekannten

Das Jacobi-Verfahren löst jede Gleichung nach ihrer Diagonalvariablen auf und setzt die alte Näherung für alle anderen ein.

Voraussetzung: $y' = f(t, y),$ $y(t_0) = y_0,$ $f$ hinreichend glatt$,$ $h > 0,$ $t_{n+1} = t_n + h$

$y_n$

Näherung für die Lösung y(t_n)

$h$

Schrittweite

$k_1$

Steigung am Anfang, k₁ = f(t_n, y_n)

$k_2$

Steigung in der Mitte, k₂ = f(t_n + h/2, y_n + h/2 · k₁)

$k_3$

verbesserte Steigung in der Mitte, k₃ = f(t_n + h/2, y_n + h/2 · k₂)

$k_4$

Steigung am Ende, k₄ = f(t_n + h, y_n + h · k₃)

Das klassische Runge-Kutta-Verfahren mittelt vier Steigungen pro Schritt und erreicht so die Konvergenzordnung 4.

Voraussetzung: $A$ invertierbar$,$ $A x = b,$ $A(x + \Delta x) = b + \Delta b,$ $b \neq 0$

$\kappa(A)$

Konditionszahl der Matrix A bezüglich der gewählten Norm

$\|A\|$

Matrixnorm von A, passend zur verwendeten Vektornorm

$A^{-1}$

inverse Matrix

$x, \Delta x$

exakte Lösung und ihre Änderung

$b, \Delta b$

rechte Seite und ihre Störung (z.B. Mess- oder Rundungsfehler)

Die Konditionszahl gibt an, wie stark sich relative Fehler in der rechten Seite höchstens auf die Lösung auswirken.

Voraussetzung: $p \geq 1,$ $C > 0,$ $C < 1$ falls $p = 1,$ $k \geq k_0$

$x_k$

Näherung nach k Iterationsschritten

$x^*$

gesuchter Grenzwert, z.B. eine Nullstelle

$p$

Konvergenzordnung

$C$

Konstante; bei p = 1 die Konvergenzrate

$k_0$

Index, ab dem die Ungleichung gilt

Die Konvergenzordnung p gibt an, wie schnell der Fehler eines Iterationsverfahrens von Schritt zu Schritt schrumpft.

Voraussetzung: $x_0, \ldots, x_n$ paarweise verschieden

$p(x)$

Interpolationspolynom vom Grad höchstens n

$x_i, y_i$

Stützstellen und zugehörige Stützwerte

$L_i(x)$

Lagrange-Basispolynom, 1 bei x_i und 0 bei allen anderen Stützstellen

$n$

Anzahl der Stützstellen minus 1

Die Lagrange-Formel liefert das eindeutige Polynom vom Grad höchstens n durch n + 1 Punkte mit verschiedenen x-Werten.

Voraussetzung: $A \in \mathbb{R}^{n \times n},$ Gauß-Elimination ohne Zeilentausch durchführbar

$A$

quadratische Koeffizientenmatrix

$L$

untere Dreiecksmatrix mit Einsen auf der Diagonalen; enthält die Eliminationsfaktoren

$U$

obere Dreiecksmatrix, das Ergebnis der Gauß-Elimination

Die LU-Zerlegung schreibt eine Matrix als Produkt einer unteren und einer oberen Dreiecksmatrix, wie sie die Gauß-Elimination liefert.

Voraussetzung: $h = \frac{b - a}{n},$ $n \in \mathbb{N},$ $n \geq 1$

$a, b$

untere und obere Integrationsgrenze

$f$

Funktion, die integriert wird

$n$

Anzahl der Teilintervalle (Rechtecke)

$h$

Schrittweite, Breite eines Rechtecks

$k$

Nummer des Teilintervalls

Die Mittelpunktregel nähert ein Integral durch Rechtecke an, deren Höhe der Funktionswert in der Mitte jedes Teilintervalls ist.

Voraussetzung: $x_0, \ldots, x_n$ paarweise verschieden

$p(x)$

Interpolationspolynom vom Grad höchstens n mit p(x_i) = f(x_i)

$x_0, \ldots, x_n$

Stützstellen

$f[x_0, \ldots, x_k]$

dividierte Differenz der Ordnung k

$n$

Anzahl der Stützstellen minus 1

Die Newton-Form baut das Interpolationspolynom aus dividierten Differenzen auf; eine neue Stützstelle fügt nur ein Glied hinzu.

Voraussetzung: $f$ differenzierbar$,$ $f'(x_n) \neq 0$

$x_n$

aktuelle Näherung für die Nullstelle

$x_{n+1}$

nächste, meist bessere Näherung

$f(x_n)$

Funktionswert an der Stelle xₙ

$f'(x_n)$

Ableitung (Tangentensteigung) an der Stelle xₙ

Das Newton-Verfahren nähert eine Nullstelle an, indem es immer zur Nullstelle der Tangente im aktuellen Punkt springt.

Voraussetzung: $F: \mathbb{R}^n \to \mathbb{R}^n$ stetig differenzierbar$,$ $J_F(x^{(k)})$ invertierbar

$F$

Funktion, deren Nullstelle F(x) = 0 gesucht ist

$x^{(k)}$

Näherungsvektor nach k Schritten

$J_F$

Jacobi-Matrix von F, Matrix der partiellen Ableitungen ∂F_i/∂x_j

$\Delta x^{(k)}$

Korrekturvektor im k-ten Schritt

Das Newton-Verfahren für Systeme ersetzt F durch seine Linearisierung und löst in jedem Schritt ein lineares Gleichungssystem.

Voraussetzung: $f$ stetig auf $[a, b],$ $f(a) \cdot f(b) < 0$

$a, b$

Grenzen des aktuellen Intervalls mit Vorzeichenwechsel

$c$

Nullstelle der Sekante, neue Näherung

$f$

stetige Funktion, deren Nullstelle gesucht ist

Die Regula falsi schneidet die Sekante durch die Intervallenden mit der x-Achse und behält stets ein Intervall mit Vorzeichenwechsel.

Voraussetzung: $f(x_n) \neq f(x_{n-1})$

$x_n, x_{n-1}$

die beiden letzten Näherungen

$x_{n+1}$

neue Näherung, Nullstelle der Sekante

$f$

Funktion, deren Nullstelle gesucht ist

Das Sekantenverfahren ersetzt beim Newton-Verfahren die Tangente durch die Sekante durch die letzten beiden Näherungen.

Voraussetzung: $f$ auf $[a, b]$ integrierbar und an den Stützstellen definiert

$a, b$

untere und obere Integrationsgrenze

$f$

Funktion, die integriert wird

$\frac{a + b}{2}$

Intervallmitte

Die Simpsonregel ersetzt die Funktion durch eine Parabel durch Anfang, Mitte und Ende und integriert diese exakt.

Voraussetzung: $h = \frac{b - a}{n},$ $x_k = a + k h,$ $n \in \mathbb{N},$ $n \geq 1$

$a, b$

untere und obere Integrationsgrenze

$f$

Funktion, die integriert wird

$n$

Anzahl der Teilintervalle

$h$

Schrittweite, Breite eines Teilintervalls

$x_k$

Stützstellen, x₀ = a bis xₙ = b

Die Trapezregel nähert ein Integral durch Trapeze unter den Sehnen zwischen benachbarten Stützstellen an.