Adaptacyjny rozmiar kroku

W matematyce i analizie numerycznej adaptacyjny rozmiar kroku jest stosowany w niektórych metodach numerycznego rozwiązywania równań różniczkowych zwyczajnych (w tym w szczególnym przypadku całkowania numerycznego ) w celu kontrolowania błędów metody i zapewnienia stabilności właściwości, takich jak A- stabilność . Zastosowanie adaptacyjnej wielkości kroku ma szczególne znaczenie, gdy występuje duża zmienność wielkości pochodnej. Na przykład podczas modelowania ruchu satelity wokół Ziemi jako standardowej orbity Keplera wystarczająca może być metoda stałych kroków czasowych, taka jak metoda Eulera . Jednak sytuacja jest trudniejsza, jeśli chce się modelować ruch statku kosmicznego, biorąc pod uwagę zarówno Ziemię, jak i Księżyc, jak w problemie trzech ciał . Tam pojawiają się scenariusze, w których można wykonać duże kroki czasowe, gdy statek kosmiczny jest daleko od Ziemi i Księżyca, ale jeśli statek kosmiczny zbliży się do zderzenia z jednym z ciał planetarnych, potrzebne są małe kroki czasowe. Metoda Romberga i Runge – Kutta – Fehlberg to przykłady metod całkowania numerycznego, które wykorzystują adaptacyjny rozmiar kroku.

Przykład

Dla uproszczenia w poniższym przykładzie zastosowano najprostszą metodę całkowania, metodę Eulera ; w praktyce preferowane są metody wyższego rzędu, takie jak metody Runge-Kutty, ze względu na ich doskonałe właściwości zbieżności i stabilności.

Rozważ problem wartości początkowej

${\ Displaystyle y' (t) = f (t, y (t)), \ qquad y (a) = y_ {A}}$

gdzie y i f mogą oznaczać wektory (w takim przypadku to równanie reprezentuje system sprzężonych ODE w kilku zmiennych).

Mamy daną funkcję f ( t , y ) i warunki początkowe ( a , y _a ) i jesteśmy zainteresowani znalezieniem rozwiązania w t = b . Niech y ( b ) oznacza dokładne rozwiązanie w b i niech y _b oznacza rozwiązanie, które obliczamy. Piszemy $= y (b)}$$varepsilon$ , gdzie jest w rozwiązaniu numerycznym.

Dla ciągu ( t _n ) wartości t , przy czym t _n = a + nh , metoda Eulera daje przybliżenia odpowiednich wartości y ( t _n ) jako

${\ Displaystyle y_ {n + 1} ^ {(0)} = y_ {n} + hf (t_ {n}, y_ {n })}$

Lokalny błąd obcięcia tego przybliżenia jest określony przez

${\ Displaystyle \ tau _ {n + 1} ^ {(0)} = y (t_ {n + 1}) -y_ {n+1}^{(0)}}$

a na podstawie twierdzenia Taylora można wykazać, że (pod warunkiem, że f jest wystarczająco gładkie) lokalny błąd obcięcia jest proporcjonalny do kwadratu wielkości kroku:

${\ Displaystyle \ tau _ {n + 1} ^ {(0)} = ch ^ {2}}$

gdzie c jest pewną stałą proporcjonalności.

Oznaczyliśmy to rozwiązanie i jego błąd za ${\ displaystyle (0)}$ .

Wartość c nie jest nam znana. Zastosujmy teraz ponownie metodę Eulera z inną wielkością kroku, aby wygenerować drugie przybliżenie do y ( t _{n +1} ). Otrzymujemy drugie rozwiązanie, które oznaczamy za ${\ Displaystyle (1)}$ . Przyjmij nowy rozmiar kroku równy połowie pierwotnego rozmiaru kroku i zastosuj dwa kroki metody Eulera. To drugie rozwiązanie jest przypuszczalnie dokładniejsze. Ponieważ musimy dwukrotnie zastosować metodę Eulera, błąd lokalny jest (w najgorszym przypadku) dwukrotnie większy od błędu pierwotnego.

${\ Displaystyle y_ {n + {\ Frac {1} {2}}} = y_ {n} + {\ Frac {h} {2 }} f (t_ {n}, y_ {n})}$

${\ Displaystyle y_ { n+1}^{(1)}=y_{n+{\frac {1}{2}}}+{\frac {h}{2}}f(t_{n+{\frac {1}{2} }},y_{n+{\frac {1}{2}}})}$

${\ Displaystyle \ tau _ {n + 1} ^ {(1)} = c \ lewo ({\ Frac {h} {2}} \ prawo) ^ { 2}+c\left({\frac {h}{2}}\right)^{2}=2c\left({\frac {h}{2}}\right)^{2}={\frac {1}{2}}ch^{2}={\frac {1}{2}}\tau _{n+1}^{(0)}}$

${\ Displaystyle y_ {n + 1} ^ {(1)} + \ tau _ {n + 1} ^ {(1)} = y (t + h)}$

$_$ zakładamy $współczynnik$ całym przedziale W rzeczywistości jego tempo zmian jest proporcjonalne do ${\ Displaystyle y ^ {(3)} (t)}$ . Odejmując rozwiązania daje oszacowanie błędu:

${\ Displaystyle y_ {n + 1} ^ {(1)} -y_ {n + 1} ^ {(0)} =\tau _{n+1}^{(1)}}$

To oszacowanie błędu lokalnego jest dokładne trzeciego rzędu.

Oszacowanie błędu lokalnego można wykorzystać do podjęcia decyzji, w jaki sposób należy zmodyfikować rozmiar kroku, $aby$ pożądaną dokładność. Na przykład, jeśli dozwolona jest lokalna tolerancja , moglibyśmy pozwolić h ewoluować jak: ${\ displaystyle {\ text {tol}}}$

${\ Displaystyle h \ strzałka w prawo 0,9 \ razy h \ razy \ min \ lewo (\ max \left(\left({\frac {\text{tol}}{2\left|\tau _{n+1}^{(1)}\right|}}\right)^{1/2} ,0.3\prawo),2\prawo)}$

0,9 ${\ displaystyle 0,9}$ jest współczynnikiem bezpieczeństwa zapewniającym sukces przy następnej próbie Minimalne i maksymalne mają zapobiegać ekstremalnym zmianom w stosunku do poprzedniego kroku. Powinno to w zasadzie dać błąd około ${\ displaystyle 0,9 \ razy {\ text {tol}}}$ przy następnej próbie. Jeśli ${\ displaystyle |\ tau _ {n+1} ^ {(1)}|<{\ text {tol}}}$ uważamy krok za udany, a oszacowanie błędu służy do ulepszenia rozwiązania:

${\ Displaystyle y_ {n + 1} ^ {(2)} = y_ {n + 1} ^ {(1) }+\tau _{n+1}^{(1)}}$

To rozwiązanie jest w rzeczywistości dokładne trzeciego rzędu w zakresie lokalnym (drugie zamówienie w zakresie globalnym), ale ponieważ nie ma dla niego oszacowania błędu, nie pomaga to w zmniejszeniu liczby kroków. Ta technika nazywa się ekstrapolacją Richardsona .

Zaczynając od początkowego rozmiaru kroku $.$ ta ułatwia naszą kontrolowaną integrację ODE od punktu ${$$displaystyle b}$ \ optymalnej liczby kroków biorąc pod uwagę lokalną tolerancję błędów. Wadą jest to, że rozmiar kroku może stać się zbyt mały, zwłaszcza przy użyciu metody Eulera niskiego rzędu .

Podobne metody można opracować dla metod wyższego rzędu, takich jak metoda Runge-Kutty czwartego rzędu. Globalną tolerancję błędów można również osiągnąć, skalując błąd lokalny do zasięgu globalnego.

Osadzone oszacowania błędów

Adaptacyjne metody wielkości stopni, które wykorzystują tak zwane „osadzone” oszacowanie błędu, obejmują metody Bogackiego – Shampine , Runge – Kutta – Fehlberg , Cash – Karp i Dormand – Prince . Metody te są uważane za bardziej wydajne obliczeniowo, ale mają niższą dokładność oszacowań błędów.

Aby zilustrować idee metody osadzonej, rozważmy następujący schemat, który aktualizuje: ${\ displaystyle y_ {n}}$ :

${\ Displaystyle y_ {n + 1} = y_ {n} + h_ {n} \ psi (t_ {n}, y_ { n}, h_ {n}}}$

${\ Displaystyle t_ {n + 1} = t_ {n} + h_ {n}}$

$1$$\ Displaystyle h_ {n} = g (t_$ sol - .

${\ tylda {\ psi}}}$ RK obliczenie obejmuje metodę RK niższego rzędu $Displaystyle$ . Błąd można wtedy po prostu zapisać jako

${\ Displaystyle {\ textrm {err}}_ {n}(h)={\tylda {y}}_{n+1}-y_{n+1}=h({\tylda {\psi}}(t_{n},y_ {n},h_{n})-\psi (t_{n},y_{n},h_{n}))}$

${\ displaystyle {\ textrm {err}} _ {n}}$ to nieznormalizowany błąd. Aby ją znormalizować, porównujemy ją z tolerancją zdefiniowaną przez użytkownika, która składa się z tolerancji bezwzględnej i tolerancji względnej:

${\ Displaystyle {\ textrm {tol}} _ {n} = {\ textrm {Atol}} + {\ textrm {Rtol} } \ cdot \ max (| y_ {n} |, | y_ {n-1} |)}$

${\ Displaystyle E_ {n} = {\ textrm {norma}} ( {\textrm {błąd}}_ {n}/{\textrm {tol}}_ {n})}$

Następnie porównujemy znormalizowany błąd $}$ 1, aby uzyskać przewidywany : mi $h_ {n}$ :

${\ Displaystyle h_ {n} = h_ {n-1} (1 / E_ {n}) ^ {1 / (q + 1 )}}$

Parametr q to kolejność odpowiadająca metodzie RK $.$ ma niższy rząd Powyższa formuła przewidywania jest wiarygodna w tym sensie, że zwiększa krok, jeśli oszacowany błąd lokalny jest mniejszy niż tolerancja, aw przeciwnym razie zmniejsza krok.

Powyższy opis jest uproszczoną procedurą stosowaną w sterowaniu stopniem dla solwerów typu explicit RK. Bardziej szczegółowe leczenie można znaleźć w podręczniku Hairera. Solver ODE w wielu językach programowania wykorzystuje tę procedurę jako domyślną strategię adaptacyjnego sterowania krokowego, która dodaje inne parametry techniczne, aby system był bardziej stabilny.

Zobacz też

• Adaptacyjna kwadratura
• Adaptacyjne różniczkowanie numeryczne

Dalsza lektura

•   William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, Przepisy numeryczne w C , wydanie drugie, CAMBRIDGE UNIVERSITY PRESS, 1992. ISBN 0-521-43108-5
•   Kendall E. Atkinson, Analiza numeryczna , wydanie drugie, John Wiley & Sons, 1989. ISBN 0-471-62489-6