Mehrschrittverfahren

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Mehrschrittverfahren sind Verfahren zur numerischen Lösung von gewöhnlichen Differentialgleichungen. Im Gegensatz zu Einschrittverfahren, so wie das Eulersche Polygonzugverfahren oder dem Runge-Kutta-Verfahren, nutzen Mehrschrittverfahren die Information aus den zuvor bereits errechneten Stützpunkten.

Inhaltsverzeichnis

1 Theorie
2 Analyse
- 2.1 Konsistenz
- 2.2 Stabilität
3 Beispiele
- 3.1 Explizite Verfahren
- 3.2 Implizite Verfahren
4 Vorteile gegenüber Einschrittverfahren
5 Praxis
- 5.1 Startwerte
- 5.2 Prädiktor-Korrektor-Methode
  - 5.2.1 PECE

[Bearbeiten] Theorie

Lineare Mehrschrittverfahren (LMV) mit m Schritten mit Abstand h lassen sich allgemein als Verfahren der Form $\sum_{i=0}^{m}a_{i} \, y(x_{k+i}) = h \sum_{i=0}^m b_{i} \, y'(x_{k+i})$ bzw. $\sum_{i=0}^{m}a_{i} \, y(x_{k+i}) = h \sum_{i=0}^m b_{i} \, f(x_{k+i},y(x_{k+i}))$ mit $y'(x k) = f (x k, y (x k))$ darstellen. Man nennt das LMV implizit, falls $b_m \neq 0$ , und explizit, falls $b m = 0$ . Implizite Verfahren haben meist eine um 1 höhere Konsistenzordnung als explizite. Ihr Nachteil besteht jedoch darin, dass bei der Berechnung von $y n + 1$ bereits $y (x n + 1)$ benötigt wird. Dies führt zu nichtlinearen Gleichungssystemen.

[Bearbeiten] Analyse

Man untersucht die LMV auf Konsistenz und Stabilität. Diese beiden Eigenschaften ergeben dann zusammen die Konvergenz des LMVs, d.h. dass wenn die Schrittweite $h \to 0$ die Differenz $|y_k-\bar y_k|=0$ . Hier bezeichnet $\bar y_k$ den durch das jeweilige LMV gewonnenen Näherungswert für $y k : = y (x k)$ .

[Bearbeiten] Konsistenz

Sei : $T_h(x_k)=\frac{1}{h}\sum_{i=0}^{m}a_{i} \, y(x_{k+i}) - \sum_{i=0}^m b_{i} \, y'(x_{k+i})$ . Man definiert dann:

Ein LMV heißt konsistent, falls

$\lim_{h \to 0} \max_{x_k \in U} |T_h(x_k)| = 0$ .

Es heißt konstistent der Ordnung p, falls für $h \to 0$

$\lim_{h \to 0} \max_{x_k \in U} |T_h(x_k)| = O(h^p)$ .

Man berechnet dies oftmals unter Zuhilfenahme der Taylor-Entwicklung. So ist

$y(x_{k+i}) = y(x_k + i h) = y(x_k)+ ih \, y'(x_k)+ \frac{(ih)^2}{2}y''(x_k) + \dots + \frac{(ih)^p}{p!}\,y^{(p)}(x_k) + O(h^p)$

wobei $y (p) (x k)$ die p-te Ableitung an der Stelle x_k bezeichnet. Dies führt man für alle im LMV auftretenden Terme durch und setzt dies in $T h (x k)$ ein.

[Bearbeiten] Stabilität

Man definiert zwei Polynome $ρ,σ$

$\rho (\lambda) = \sum_{i=0}^ma_i \, \lambda^i$

$\sigma(\lambda) = \sum_{i=0}^mb_i \, \lambda^i$

Ein LMV wird durch diese beiden Polynome vollständig charakterisiert, so dass man anstelle von obiger Schreibweise des LMVs auch von einem "LMV ( $ρ,σ$ )" spricht.

Sei $λ 0$ eine Nullstelle von $ρ$ Ein LMV ( $ρ,σ$ ) ist stabil, wenn für alle Nullstellen $λ 0$ gilt:

$|\lambda_0| \le 1$
$|\lambda_0| = 1 \Rightarrow \lambda_0$ ist einfache Nullstelle.

[Bearbeiten] Beispiele

[Bearbeiten] Explizite Verfahren

Ein 'Explizites Verfahren' bedeutet in diesem Zusammenhang, dass zu Berechnung der Näherungswerte nur Werte herangezogen werden, die zeitlich vor dem zu Berechnenden liegen. Das wohl bekannteste explizite LMV ist die s+1 - Schritt Adams-Bashforth-Methode. Diese hat die Form:

$y_{n+1}=y_n + h \sum_{j=0}^s b_{j} \, f(x_{n-j},y_{n-j})$ .

mit

$b_j = {(-1)^j \over j!(s-j)!}\int_0^1 \prod_{i=0, i\ne j}^s (u+i) \,du,\quad j=0,\ldots, s.$

z.B.:

s = 1

$y_{n+1} = y_n + h\left( {3\over 2} f(t_n, y_n) - {1 \over 2} f(t_{n-1}, y_{n-1})\right)$

s = 2

$y_{n+1} = y_n + h\left( {23\over 12} f(t_n, y_n) - {16 \over 12} f(t_{n-1}, y_{n-1}) + {5\over 12}f(t_{n-2}, y_{n-2})\right)$

usw.

[Bearbeiten] Implizite Verfahren

Bei 'Impliziten Verfahren' wird zur Berechnung auch der zu berechnende Wert selbst benutzt. Im Beispiel taucht so auf beiden Seiten der Gleichung $y n + 1$ auf. Das seinerseits bekannteste implizite LMV ist die Adams-Moulton-Methode. Dieses hat die Form:

$y_{n+1} = y_n + h \sum_{j=-1}^{s-1} b_j f(t_{n-j}, y_{n-j}),\quad 0 \le s \le n$

mit

$b_j = {(-1)^{j+1} \over (j+1)!(s-j-1)!}\int_0^1 \prod_{i=-1, i\ne j}^{s-1} (u+i) \,du,\quad j=-1,0,\ldots,s-1$

z.B.:

s = 2

$y_{n+1}=y_n+h\left({1 \over 12}(5f(t_{n+1}, y_{n+1})+8f(t_n,y_n)-f(t_{n-1},y_{n-1}))\right)$

[Bearbeiten] Vorteile gegenüber Einschrittverfahren

Der offensichtliche Vorteil lineare Mehrschrittverfahren gegenüber Einschrittverfahren ist ihr Verhältnis zwischen Kosten und Konsistenzordnung. Dies liegt daran, dass bei einem LMV jeweils nur ein Wert aus bereits vorhandenem Datenmaterial berechnet werden muss.

[Bearbeiten] Praxis

[Bearbeiten] Startwerte

Oftmals hat man es in der Praxis mit Problemen der Art:

$y'(x)=f\left( x,y(x) \right) , \quad y(0)=y_0$

zu tun. Hier fehlt es an Startwerten. Diese werden zunächst durch Einschrittverfahren (z.B. dem klassischen Runge-Kutta-Verfahren) gewonnen.

[Bearbeiten] Prädiktor-Korrektor-Methode

Mit dem Gedanken, die im Vergleich um 1 höhere Konsistenzordnung der impliziten LMVs zu nutzen, umgeht man das Lösen der nichtlinearen Gleichungen durch die sog. Prädiktor-Korrektor-Methode. Es wird der in der impliziten Methode benötigte Wert für $y n + 1$ durch eine explizite Methode berechnet, wonach durch Iteration der Wert für $y n + 1$ zu verbessern versucht wird. Dazu gibt es verschiedene Verfahren, die geläufigsten sind:

[Bearbeiten] PECE

Beim PECE wird der durch das implizite Verfahren gewonnene Wert $y n + 1, a l t$ für $y n + 1$ wieder in das implizite Verfahren eingesetzt, wodurch man einen neuen Wert für $y n + 1$ , nämlich $y n + 1, n e u$ erhält. Dies wird so lange iteriert, bis $| y n + 1, n e u - y n + 1, a l t |$ kleiner als eine festgelegte Fehlertoleranz ist.

Von „http://de.wikipedia.org../../../m/e/h/Mehrschrittverfahren.html“

Kategorien: Gewöhnliche Differentialgleichungen | Numerische Mathematik