Die BDF-Verfahren (englisch Backward Differentiation Formulas) sind lineare Mehrschrittverfahren zur numerischen Lösung von Anfangswertproblemen gewöhnlicher Differentialgleichungen:
.
Dabei wird für
eine Näherungslösung an den Zwischenstellen
berechnet:
.
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 steife Anfangswertprobleme weit verbreitet.
Beschreibung
Im Gegensatz zu Adams-Moulton-Verfahren wird bei BDF-Verfahren nicht die rechte Seite durch ein Interpolationspolynom approximiert, stattdessen konstruiert man ein Polynom
mit (maximalem) Grad
, welches die letzten
Approximationen
an die Lösung sowie den unbekannten Wert
interpoliert:
.
Zusätzlich fordert man, dass das Interpolationspolynom
die gegebene Differentialgleichung im Punkt
löst, also dass gilt
,
und erhält so ein nichtlineares Gleichungssystem für die Bestimmung des implizit gegebenen Wertes
.
Lagrange-Darstellung
Eine Möglichkeit für die Darstellung des Interpolationspolynoms
ist die Lagrange-Darstellung. Dabei sind die Lagrange-Basispolynome mit den
Stützstellen
definiert durch
![{\displaystyle l_{j}(x_{n+i})=\delta _{ji}={\begin{cases}1&{\text{falls }}j=i,\\0&{\text{falls }}j\neq i.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9faa18d8d5671a034a15a87e168a7d4dfe968283)
wobei
das Kronecker-Delta ist. Damit folgt wegen
direkt die Darstellung
.
Mit der Forderung
erhält man nun die lineare Rekursionsformel für die BDF-Verfahren:
,
wobei die Koeffizienten
gegeben sind durch
.
Alternative Lagrange-Darstellung
Alternativ betrachten wir die Lagrange-Basispolynome definiert durch
![{\displaystyle L_{j}(-s)=\delta _{js}={\begin{cases}1&{\text{falls }}j=s,\\0&{\text{falls }}j\neq s.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/caf285360ae16519028d6ed0268c745c9a0aa53d)
Damit folgt die Darstellung
.
Dabei ist
der Abstand der Stützstellen und die konstante Schrittweite des Verfahrens. Mit der Forderung
, wobei hier
![{\displaystyle 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8befc37a99a0a395198bbe21d8d2ecb77fdb484c)
gilt, erhält man nun für die Berechnung der Koeffizienten
![{\displaystyle \alpha _{j}=L_{k-j}'(0),\quad j=0,\dots ,k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/968dc9e9dba9dd040973af2bb1e5d3fa3c1c4d76)
und damit die Rekursionsformel
![{\displaystyle \sum _{j=0}^{k}L_{k-j}'(0)y_{n+j}=hf(x_{n+k},y_{n+k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46d020313c9cb758ecfffb546c4cdcb9ad816605)
Newton-Darstellung
Die Newton-Darstellung des Interpolationspolynoms
verwendet Rückwärtsdifferenzen, welche rekursiv definiert sind durch
![{\displaystyle \nabla ^{0}y_{i}=y_{i},\quad \nabla ^{j+1}y_{i}=\nabla ^{j}y_{i}-\nabla ^{j}y_{i-1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/77a92f413524e5e8ceca2ee785753fb340f1e89e)
Damit lässt sich
schreiben als
.
Diese Formel führt wegen
für
auf die Darstellung
![{\displaystyle \sum \limits _{j=1}^{k}{\frac {1}{j}}\nabla ^{j}y_{n+k}=hf(x_{n+k},y_{n+k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61833937acbac248fbd4e0c21382177daafd9586)
der BDF-Verfahren.
Alle oben betrachteten Darstellungen der Berechnungsformeln sind äquivalent, da sie nur verschiedene Arten der Darstellung des eindeutigen Interpolationspolynoms
verwendet haben. Für
lauten die impliziten Berechnungsformeln der BDF(k)-Verfahren:
- BDF(1) – implizites Euler-Verfahren:
![{\displaystyle y_{n+1}-y_{n}=hf(x_{n+1},y_{n+1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9e2136b1a66f4bddbc4bd8b128522f8a2fb89c7)
![{\displaystyle 3y_{n+2}-4y_{n+1}+y_{n}=2hf(x_{n+2},y_{n+2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5ae4648a3322d653b3248848e8d59a174f4e807)
![{\displaystyle 11y_{n+3}-18y_{n+2}+9y_{n+1}-2y_{n}=6hf(x_{n+3},y_{n+3})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e304adb88bc3ee2d652df196b3169c6de39adc71)
![{\displaystyle 25y_{n+4}-48y_{n+3}+36y_{n+2}-16y_{n+1}+3y_{n}=12hf(x_{n+4},y_{n+4})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96c680a168e8669c185be5f4d2b7b00f8a6c1974)
![{\displaystyle 137y_{n+5}-300y_{n+4}+300y_{n+3}-200y_{n+2}+75y_{n+1}-12y_{n}=60hf(x_{n+5},y_{n+5})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c79a3e7501260705e4248a37a527f879a42a51b1)
![{\displaystyle 147y_{n+6}-360y_{n+5}+450y_{n+4}-400y_{n+3}+225y_{n+2}-72y_{n+1}+10y_{n}=60hf(x_{n+6},y_{n+6})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f82b3515386c8e3b17b5d65a66f1cd8f229009d)
Eigenschaften
Die BDF-Verfahren sind alle implizit, da der unbekannte Wert
in die Gleichung eingeht. BDF(k) besitzt genau die Konsistenzordnung k. Das Verfahren BDF(1) ist das implizite Euler-Verfahren. Dieses und BDF(2) sind A-stabil, die Verfahren höherer Ordnung A(
)-stabil, wobei der Öffnungswinkel
sich mit höherer Ordnung verkleinert. Insbesondere BDF(2) ist aufgrund seiner optimalen Eigenschaften bezüglich der 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.
- Stabilitätsgebiete der BDF-Verfahren
-
BDF1
-
BDF2
-
BDF3
-
BDF4
-
BDF5
-
BDF6
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
- Gear, Backward Differentiation Formulas, Scholarpedia