Metoda Leimkuhlera-Matthewsa

Metoda Leimkuhlera-Matthewsa (lub metoda LM w oryginalnym artykule) jest algorytmem do znajdowania zdyskretyzowanych rozwiązań dynamiki Browna

${\ Displaystyle \ operatorname {d} X_ {t} = - \ nabla V (X_ {t}) \, \ operatorname {d} t + \sigma \,\mathrm {d} W_{t},}$

gdzie ${\ Displaystyle \ sigma > 0}$ jest stałą i można $ją$ traktować jako funkcję energii potencjalnej, powszechnie spotykaną molekularnej z ${R} ^ {N}}$${ \ displaystyle X_ {t}$$mathbb$$wektor$ stanu wraz z wymiarowym procesem Wienera oznaczony jako ${\ Displaystyle W_ {t}}$ . Biorąc pod uwagę krok czasowy , schemat aktualizacji Leimkuhlera-Matthewsa jest zwięźle zapisany jako ${\ displaystyle \ Delta t> 0}$

${\ Displaystyle Y_ {t + \ Delta t} = Y_ {t} - \ nabla V (Y_ {t}) \ Delta t + \ sigma {\ Frac {\ sqrt {\ Delta t}} {2}} \, (R_ {t} + R_ {t + \ Delta t}),}$

z warunkiem początkowym ${\ Displaystyle Y_ {0}: = X_ {0}}$$i$ gdzie jest niezależnych normalnych liczb losowych przerysowywanych na każdym kroku, więc ${\ Displaystyle {\ tekst {E}} [R_ {t} \ cdot R_ {s}] = N \ delta _ {ts}} (gdzie mi$ [ $Displaystyle {\text{E}}[\punktor]}$ oznacza oczekiwanie ). Pomimo tego, $dotyczące$ ma taki sam koszt jak pod względem liczby ocen funkcji na aktualizację), biorąc pod uwagę pewne założenia ${\ Displaystyle \ Delta t, \, V (X)}$ Wykazano, że rozwiązania mają właściwość superzbieżności i ${\ Displaystyle f (X)}$

${\ Displaystyle {\ tekst {E}} [| f (Y_ {t}) -f (X_ {t}) |] \ równoważnik C_ {1 }e^{-\lambda t}\Delta t+C_{2}\Delta t^{2}}$

dla stałych $\ Displaystyle C_ {k} \ geq 0 \, \ lambda > 0}$ nie zależy od ${\ displaystyle t}$ . Oznacza to, że gdy $efektywne$$uzyskujemy$ drugie zamówienie z błędem w obliczonych Dla małego kroku czasowego może to dać znaczną poprawę w stosunku do Eulera-Maruyamy ${\ displaystyle \ Delta t}$ schemat, bez dodatkowych kosztów.

Dyskusja

Porównanie z innymi schematami

Oczywistą metodą porównania jest schemat Eulera-Maruyamy $,$ ponieważ ma ten sam koszt i krok Jego aktualizacja ma postać

${\ Displaystyle {\ kapelusz {Y}} _ {t + \ Delta t} = {\ kapelusz {Y }}_ {t}-\nabla V({\kapelusz {Y}}_{t})\Delta t+\sigma {\sqrt {\Delta t}}\,R_{t},}$

z błędem (biorąc pod uwagę pewne założenia) jako $C \ Delta t}$ równoważnik ${\ Displaystyle C> 0}$ niezależny od ${\ displaystyle t}$ . W porównaniu z powyższą definicją, jedyną różnicą między schematami jest jednoetapowość uśredniony termin szumu, dzięki czemu jest łatwy do wdrożenia.

Dla wystarczająco małego kroku czasowego $Maruyama$ dużego czasu $.$ jasne, że schemat LM daje mniejszy błąd niż Euler- Chociaż istnieje wiele algorytmów, które mogą dawać mniejszy błąd w porównaniu ze schematem Eulera (patrz np. metoda Milsteina , Runge-Kutty lub Heuna ), prawie zawsze wiążą się one z kosztem wydajności, wymagając więcej obliczeń w zamian za zmniejszenie błędu. Jednak schemat Leimkuhlera-Matthewsa może znacznie zmniejszyć błąd przy minimalnych zmianach w stosunku do standardowego schematu Eulera. Kompromis wynika z (stosunkowo) ograniczonego zakresu stochastyczne równanie różniczkowe , które rozwiązuje: $musi$ być stałą skalarną, a funkcja dryfu musi mieć postać ${\ Displaystyle \ nabla V (X)$ . Schemat LM również nie jest markowski , ponieważ aktualizacje wymagają czegoś więcej niż tylko stanu $czasie$ . Możemy jednak przekształcić ten schemat w proces Markowa, rozszerzając przestrzeń.

Forma Markowa

Możemy przepisać algorytm w postaci Markowa, rozszerzając przestrzeń stanów o $pędu$ że to ${\ Displaystyle (X_ {t}, P_ {t})}$ w czasie ${\ displaystyle t}$ . Inicjując pęd jako wektor $normalnych$ liczb losowych, mamy

${\ Displaystyle X'_ {t + \ Delta t} = X_ {t} - \ nabla V (X_ { t}) \ Delta t + \ sigma {\ Frac {\ sqrt {\ Delta t}} {2}} \, P_ {t},} P t + Δ t ∼$

$+ \Delta t}\sim {\text{Normalny}}(0,I),}$

${\ Displaystyle X_ {t + \ Delta t} = X'_ {t + \ Delta t} + \ sigma {\ Frac { \sqrt {\Delta t}}{2}}\,P_{t+\Delta t},}$

gdzie środkowy krok całkowicie przerysowuje pęd, tak że każdy składnik jest niezależną normalną liczbą losową. Ten schemat jest markowski i ma takie same właściwości jak oryginalny schemat LM.

Aplikacje

Algorytm ma zastosowanie wszędzie tam, gdzie wymagane są słabe (tj. przeciętne) właściwości rozwiązań dynamiki Browna . Dotyczy to każdego problemu symulacji molekularnej (takiego jak klasyczna dynamika molekularna ), ale może również odnosić się do problemów z próbkowaniem statystycznym ze względu na właściwości rozwiązań w dużych czasach. W granicach ${\ Displaystyle t \ do \ infty}$ rozwiązania zostaną rozdzielone zgodnie z rozkładem prawdopodobieństwa ${\ Displaystyle \ pi (X) \ propto \ exp (-V (X))}$ . W ten sposób możemy wygenerować niezależne próbki zgodnie z wymaganym rozkładem, używając ${\ Displaystyle V (X) = - \ log (\ pi (X))}$ algorytm aż do dużego ${\ displaystyle t}$ . Takie strategie mogą być skuteczne (na przykład) w wnioskowania bayesowskiego .

Zobacz też

• Euler-Maruyama
• metoda Milsteina
• Metoda Runge-Kutty (SDE)
• Metoda Heuna