217.92.84.13: /* Lagrange-Darstellung */Indexfehler korrigiert

2022-03-26T13:19:59Z

Lagrange-Darstellung: Indexfehler korrigiert

Neue Seite

Die '''BDF-Verfahren''' ({{enS}} ''Backward Differentiation Formulas'') sind lineare [[Mehrschrittverfahren]] zur [[Numerik|numerischen]] Lösung von [[Anfangswertproblem]]en [[Gewöhnliche Differentialgleichung|gewöhnlicher Differentialgleichungen]]:
:<math>
y'(x) = f(x, y(x)), \quad
y(x_0) = y_0, \quad
y \colon \R \to \R^n
</math>.
Dabei wird für <math>y(x)</math> eine Näherungslösung an den Zwischenstellen <math>x_i</math> berechnet:
:<math>y_i \approx y(x_i) \quad i=1,\dotsc, m</math>.
Die Verfahren wurden 1952 von [[Charles Francis Curtiss]] und [[Joseph Oakland Hirschfelder]] eingeführt und sind seit dem Erscheinen der Arbeiten von [[C. William Gear]] 1971 als Löser für [[Steifes Anfangswertproblem|steife Anfangswertprobleme]] weit verbreitet.

== Beschreibung ==
Im Gegensatz zu [[Adams-Moulton-Verfahren]] wird bei BDF-Verfahren nicht die rechte Seite durch ein [[Polynominterpolation|Interpolationspolynom]] approximiert, stattdessen konstruiert man ein Polynom <math>q_k</math> mit (maximalem) Grad <math>k</math>, welches die letzten <math>k</math> Approximationen <math>y_{n},\dotsc,y_{n+k-1}</math> an die Lösung sowie den unbekannten Wert <math>y_{n+k}</math> interpoliert:

:<math> q_k(x_i)=y_i, \quad \text{für } i=n, \dots, n+k</math>.

Zusätzlich fordert man, dass das Interpolationspolynom <math>q_k</math> die gegebene Differentialgleichung im Punkt <math>x_{n+k}</math> löst, also dass gilt

:<math>q_k'(x_{n+k}) = f(x_{n+k},y_{n+k})</math>,

und erhält so ein nichtlineares Gleichungssystem für die Bestimmung des implizit gegebenen Wertes <math>y_{n+k}</math>.

=== Lagrange-Darstellung ===
Eine Möglichkeit für die Darstellung des Interpolationspolynoms <math>q_k</math> ist die [[Polynominterpolation#Lagrangesche Interpolationsformel|Lagrange-Darstellung]]. Dabei sind die Lagrange-Basispolynome mit den <math>k+1</math> Stützstellen <math>x_{n}, \dots, x_{n+k}</math> definiert durch

:<math>l_{j}(x_{n+i}) = \delta_{ji} = \begin{cases}1 & \text{falls } j=i,\\ 0 & \text{falls } j \neq i. \end{cases} </math>

wobei <math>\delta_{ji}</math> das [[Kronecker-Delta]] ist. Damit folgt wegen <math>q_k(x_{n+i}) = \sum_{j=0}^k l_{j}(x_{n+i}) y_{n+j} = y_{n+i}</math> direkt die Darstellung

:<math> q_k(x) = \sum_{j = 0}^{k} l_{j}(x) y_{n+j}</math>.

Mit der Forderung <math>q_k'(x_{n+k}) = f(x_{n+k},y_{n+k})</math> erhält man nun die lineare [[Rekursion]]sformel für die BDF-Verfahren:

:<math>\sum^{k}_{j=0}\alpha_{j} y_{n+j}= f(x_{n+k}, y_{n+k})</math>,

wobei die Koeffizienten <math>\alpha_j</math> gegeben sind durch

:<math> \alpha_{j} = l_{j}'(x_{n+k}), \quad j=0,\dots,k</math>.

=== Alternative Lagrange-Darstellung ===
Alternativ betrachten wir die Lagrange-Basispolynome definiert durch

:<math>L_{j}(-s) = \delta_{js} = \begin{cases}1 & \text{falls } j=s,\\ 0 & \text{falls } j \neq s.\end{cases}</math>

Damit folgt die Darstellung

:<math> q_k(x_{n+k} + sh) = \sum_{j=0}^k L_{k-j}(s)y_{n+j}</math>.

Dabei ist <math>h=x_{i+1}-x_i</math> der Abstand der Stützstellen und die konstante Schrittweite des Verfahrens. Mit der Forderung <math>q_k'(x_{n+k}) = f(x_{n+k},y_{n+k})</math>, wobei hier

:<math> q_k'(x) = \frac{d}{dx} q_k(x) = \frac{d}{d(sh)}q_k(x_{n+k} + sh) = \frac{1}{h} \frac{d}{ds} q_k(x_{n+k} + sh)</math>

gilt, erhält man nun für die Berechnung der Koeffizienten <math>\alpha_j</math>

:<math> \alpha_{j} = L_{k-j}'(0), \quad j=0,\dots,k</math>

und damit die Rekursionsformel

:<math> \sum_{j=0}^k L_{k-j}'(0) y_{n+j} = hf(x_{n+k},y_{n+k}) </math>

=== Newton-Darstellung ===
Die Newton-Darstellung des Interpolationspolynoms <math>q_k</math> verwendet Rückwärtsdifferenzen, welche rekursiv definiert sind durch

:<math> \nabla^{0} y_{i} = y_{i} ,\quad \nabla^{j+1} y_{i} = \nabla^{j} y_{i} - \nabla^{j} y_{i-1}. </math>

Damit lässt sich <math>q_k</math> schreiben als

:<math>q_k \left(x_{n+k}+sh \right)=\sum_{j=0}^{k}(-1)^{j} \binom{-s}{j} \nabla^{j}y_{n+k}</math>.

Diese Formel führt wegen <math>\left. \frac{d}{ds} (-1)^j \binom{-s}{j} \right|_{s=0} = \frac{1}{j}</math> für <math>j=1,\dots,k</math> auf die Darstellung

:<math> \sum \limits_{j=1}^k \frac{1}{j} \nabla^j y_{n+k} = hf(x_{n+k},y_{n+k}) </math>

der BDF-Verfahren.

== Berechnungsformeln ==
Alle oben betrachteten Darstellungen der Berechnungsformeln sind äquivalent, da sie nur verschiedene Arten der Darstellung des eindeutigen Interpolationspolynoms <math>q_k</math> verwendet haben. Für <math>k \leq 6</math> lauten die impliziten Berechnungsformeln der BDF(k)-Verfahren:

* BDF(1) – implizites Euler-Verfahren:
:<math> y_{n+1} - y_n = h f(x_{n+1}, y_{n+1}) </math>
* BDF(2):
:<math> 3 y_{n+2} - 4 y_{n+1} + y_n = 2 h f(x_{n+2}, y_{n+2}) </math>
* BDF(3):
:<math> 11 y_{n+3} - 18 y_{n+2} + 9 y_{n+1} - 2 y_n = 6 h f(x_{n+3}, y_{n+3}) </math>
* BDF(4):
:<math> 25 y_{n+4} - 48 y_{n+3} + 36 y_{n+2} - 16 y_{n+1} + 3 y_n = 12 h f(x_{n+4},y_{n+4}) </math>
* BDF(5):
:<math> 137 y_{n+5} - 300 y_{n+4} + 300 y_{n+3} - 200 y_{n+2} + 75 y_{n+1} - 12 y_n = 60 h f(x_{n+5},y_{n+5}) </math>
* BDF(6):
:<math> 147 y_{n+6} - 360 y_{n+5} + 450 y_{n+4} - 400 y_{n+3} + 225 y_{n+2} - 72 y_{n+1} + 10 y_n = 60 h f(x_{n+6},y_{n+6}) </math>

== Eigenschaften ==
Die BDF-Verfahren sind alle implizit, da der unbekannte Wert <math>y_{n+k}</math> in die Gleichung eingeht. BDF(k) besitzt genau die [[Konsistenzordnung]] ''k''. Das Verfahren BDF(1) ist das [[implizites Euler-Verfahren|implizite Euler-Verfahren]]. Dieses und BDF(2) sind [[A-Stabilität|A-stabil]], die Verfahren höherer Ordnung A(<math>\alpha</math>)-stabil, wobei der Öffnungswinkel <math>\alpha</math> sich mit höherer Ordnung verkleinert. Insbesondere BDF(2) ist aufgrund seiner optimalen Eigenschaften bezüglich der [[Zweite Dahlquist-Barriere|zweiten Dahlquist-Barriere]] bei der Berechnung steifer Differentialgleichungen sehr beliebt.
Für ''k<6'' sind die Verfahren stabil und konsistent und damit auch konvergent. Der größte Anreiz der BDF-Verfahren sind ihre großen Stabilitätsgebiete, weshalb sie sich für den Einsatz bei der Lösung von steifen Anfangswertproblemen eignen.
Für ''k>6'' sind die Verfahren instabil.

<gallery caption="Stabilitätsgebiete der BDF-Verfahren" widths="220">
Stability region for BDF1.svg|BDF1
Stability region for BDF2.svg|BDF2
Stability region for BDF3.svg|BDF3
Stability region for BDF4.svg|BDF4
Stability region for BDF5.svg|BDF5
Stability region for BDF6.svg|BDF6
</gallery>

== Literatur ==
* E. Hairer, Syvert P. Nørsett, Gerhard Wanner: ''Solving Ordinary Differential Equations I, Nonstiff Problems'', Springer Verlag, ISBN 3-540-56670-8
* E. Hairer, G. Wanner: ''Solving Ordinary Differential Equations II, Stiff problems'', Springer Verlag, ISBN 3-540-60452-9
* H.R. Schwarz, N. Köckler: ''Numerische Mathematik'', Teubner (2004)
*Curtiss, Hirschfelder ''Integration of stiff equations'', Proc. Nat. Acad. Sci. U.S.A., Band 38, 1952, 235–243.

== Weblinks ==
*[http://www.scholarpedia.org/article/Backward_differentiation_formulas Gear, Backward Differentiation Formulas, Scholarpedia]

{{SORTIERUNG:BdfVerfahren}}
[[Kategorie:Numerische Mathematik]]
[[Kategorie:Theorie gewöhnlicher Differentialgleichungen]]

BDF-Verfahren - Versionsgeschichte

217.92.84.13: /* Lagrange-Darstellung */Indexfehler korrigiert