Eulerova metoda - Euler method

v matematika a výpočetní věda, Eulerova metoda (také zvaný vpřed Eulerova metoda) je prvního řádu numerické postup řešení obyčejné diferenciální rovnice (ODR) s daným počáteční hodnota. Je to nejzákladnější explicitní metoda pro numerická integrace obyčejných diferenciálních rovnic a je nejjednodušší Metoda Runge – Kutta. Metoda Euler je pojmenována po Leonhard Euler, který o tom zacházel ve své knize Institutionum calculi integralis (zveřejněno 1768–1870).[1]
Metoda Euler je metoda prvního řádu, což znamená, že lokální chyba (chyba na krok) je úměrná druhé mocnině velikosti kroku a globální chyba (chyba v daném čase) je úměrná velikosti kroku. Eulerova metoda často slouží jako základ pro konstrukci složitějších metod, např. metoda prediktor-korektor.
Neformální geometrický popis
Zvažte problém výpočtu tvaru neznámé křivky, která začíná v daném bodě a splňuje danou diferenciální rovnici. Zde lze diferenciální rovnici považovat za vzorec, kterým sklon z tečna na křivku lze vypočítat v kterémkoli bodě křivky, jakmile byla vypočítána poloha tohoto bodu.
Myšlenka je, že zatímco křivka je zpočátku neznámá, její počáteční bod, který označujeme je známo (viz obrázek vpravo nahoře). Potom z diferenciální rovnice sklon ke křivce v lze vypočítat, a tak tečnu.
Udělejte malý krok podél této tečné čáry až k bodu Podél tohoto malého kroku se sklon příliš nemění, takže bude blízko křivky. Pokud to předstíráme je stále na křivce, stejné uvažování jako u bodu lze použít výše. Po několika krocích, a polygonální křivka je vypočítán. Obecně se tato křivka neodchyluje příliš daleko od původní neznámé křivky a chybu mezi těmito dvěma křivkami lze zmenšit, pokud je velikost kroku dostatečně malá a interval výpočtu je konečný:[2]
Vyberte hodnotu pro velikost každého kroku a nastavení . Nyní, jeden krok Eulerovy metody od na je:[3]
Hodnota je přiblížení řešení k ODR v čase : . Eulerova metoda je explicitní, tj. řešení je explicitní funkcí pro .
Zatímco Eulerova metoda integruje ODR prvního řádu, libovolnou ODR řádu N lze reprezentovat jako systém ODR prvního řádu: zacházet s rovnicí
- ,
zavedeme pomocné proměnné a získejte ekvivalentní rovnici:
Toto je systém prvního řádu v proměnné a lze s nimi manipulovat Eulerovou metodou nebo ve skutečnosti jakýmkoli jiným schématem pro systémy prvního řádu.[4]
Příklad
Vzhledem k problému počáteční hodnoty
chtěli bychom použít Eulerovu metodu k aproximaci .[5]
Použitím velikosti kroku rovné 1 (h = 1)

Eulerova metoda je
nejprve musíme spočítat . V této jednoduché diferenciální rovnici funkce je definováno . My máme
Provedením výše uvedeného kroku jsme našli sklon přímky, která je tečná ke křivce řešení v bodě . Připomeňme, že sklon je definován jako změna v děleno změnou v nebo .
Dalším krokem je vynásobení výše uvedené hodnoty velikostí kroku , které zde považujeme za rovné jedné:
Vzhledem k tomu, že velikost kroku je změna v , když vynásobíme velikost kroku a sklon tečny, dostaneme změnu v hodnota. Tato hodnota se poté přidá k počátečnímu hodnota k získání další hodnoty, která má být použita pro výpočty.
Výše uvedené kroky je třeba opakovat, abyste našli , a .
Kvůli opakující se povaze tohoto algoritmu může být užitečné uspořádat výpočty ve formě grafu, jak je vidět níže, aby nedocházelo k chybám.
0 1 0 1 1 1 2 1 2 1 2 1 2 4 2 4 2 4 1 4 8 3 8 3 8 1 8 16
Závěr tohoto výpočtu je takový . Přesné řešení diferenciální rovnice je , tak . Ačkoli aproximace Eulerovy metody nebyla v tomto konkrétním případě příliš přesná, zejména kvůli velké velikosti hodnotového kroku , jeho chování je kvalitativně správné, jak ukazuje obrázek.
Příklad kódu MATLAB
Průhledná; clc; zavřít('Všechno');y0 = 1;t0 = 0;h = 1; % try: h = 0,01tn = 4; % se rovná: t0 + h * n, s n počet kroků[t, y] = Euler(t0, y0, h, tn);spiknutí(t, y, 'b');% přesné řešení (y = e ^ t):tt = (t0:0.001:tn);yy = exp(tt);držet('na');spiknutí(tt, yy, 'r');držet('vypnuto');legenda('Euler', 'Přesný');funkce [t, y] = Euler (t0, y0, h, tn) fprintf('% 10s% 10s% 10s% 15s n', 'já', 'yi', 'ti', 'f (yi, ti)'); fprintf('% 10d% + 10,2f% + 10,2f% + 15,2f n', 0, y0, t0, F(y0, t0)); t = (t0:h:tn)'; y = nuly(velikost(t)); y(1) = y0; pro i = 1: 1: délka (t) - 1 y(i + 1) = y(i) + h * F(y(i), t(i)); fprintf('% 10d% + 10,2f% + 10,2f% + 15,2f n', i, y(i + 1), t(i + 1), F(y(i + 1), t(i + 1))); koneckonec% v tomto případě, f (y, t) = f (y)funkcedydt =F(y, t)dydt = y;konec% VÝSTUP:% i yi ti f (yi, ti)% 0 +1.00 +0.00 +1.00% 1 +2.00 +1.00 +2.00% 2 +4.00 +2.00 +4.00% 3 +8.00 +3.00 +8.00% 4 +16.00 +4.00 +16.00% POZNÁMKA: Kód také vygeneruje srovnávací graf
Příklad kódu R.

Níže je uveden kód příkladu v souboru Programovací jazyk R..
# ============# ŘEŠENÍ# y '= y, kde y' = f (t, y)# pak:F <- funkce(ti,y) y# POČÁTEČNÍ HODNOTY:t0 <- 0y0 <- 1h <- 1tn <- 4# Eulerova metoda: definice funkceEuler <- funkce(t0, y0, h, tn, dy.dt) { # dy.dt: derivační funkce # t sekvence: tt <- násl(t0, tn, podle=h) # tabulka s tolika řádky jako tt prvky: tbl <- data.frame(ti=tt) tbl$yi <- y0 # Inicializuje yi s y0 tbl$Dy.dt [1] <- dy.dt(tbl$ti [1],y0) # derivát pro (i v 2:nrow(tbl)) { tbl$yi [i] <- tbl$yi [i-1] + h*tbl$Dy.dt [i-1] # Pro další iteraci: tbl$Dy.dt [i] <- dy.dt(tbl$ti [i],tbl$yi [i]) } vrátit se(tbl)}# Eulerova metoda: funkční aplikacer <- Euler(t0, y0, h, tn, F)názvy řádků(r) <- 0:(nrow(r)-1) # se shoduje s indexem n# Přesné řešení pro tento případ: y = exp (t)# přidáno jako další sloupec do rr$y <- exp(r$ti)# TABULKA s výsledky:tisk(r)spiknutí(r$ti, r$y, typ="já", plk="Červené", ok=2)řádky(r$ti, r$yi, plk="modrý", ok=2)mřížka(plk="Černá")legenda("horní", legenda = C("Přesný", "Euler"), ok=2, plk = C("Červené", "modrý"))# VÝSTUP:## ti yi Dy.dt y# 0 0 1 1 1.000000# 1 1 2 2 2.718282# 2 2 4 4 7.389056# 3 3 8 8 20.085537# 4 4 16 16 54.598150# POZNÁMKA: Kód také vygeneruje srovnávací graf
Použití dalších velikostí kroků

Jak je navrženo v úvodu, metoda Euler je přesnější, pokud je velikost kroku je menší. Tabulka níže ukazuje výsledek s různými velikostmi kroků. Horní řada odpovídá příkladu v předchozí části a druhá řada je znázorněna na obrázku.
velikost kroku výsledek Eulerovy metody chyba 1 16.00 38.60 0.25 35.53 19.07 0.1 45.26 9.34 0.05 49.56 5.04 0.025 51.98 2.62 0.0125 53.26 1.34
Chyba zaznamenaná v posledním sloupci tabulky je rozdíl mezi přesným řešením v a Eulerova aproximace. Ve spodní části tabulky je velikost kroku poloviční oproti kroku v předchozím řádku a chyba je také přibližně poloviční oproti chybě v předchozím řádku. To naznačuje, že chyba je zhruba úměrná velikosti kroku, alespoň u poměrně malých hodnot velikosti kroku. To platí obecně, také pro jiné rovnice; viz část Chyba globálního zkrácení Více podrobností.
Jiné metody, například metoda středního bodu také ilustrované na obrázcích, chovají se příznivěji: globální chyba metody středního bodu je zhruba úměrná hodnotě náměstí velikosti kroku. Z tohoto důvodu se o Eulerově metodě říká, že jde o metodu prvního řádu, zatímco metoda středního bodu je druhá.
Z výše uvedené tabulky můžeme extrapolovat, že velikost kroku potřebná k získání správné odpovědi na tři desetinná místa je přibližně 0,00001, což znamená, že potřebujeme 400 000 kroků. Tento velký počet kroků znamená vysoké výpočetní náklady. Z tohoto důvodu lidé obvykle používají alternativní metody vyššího řádu, jako jsou Metody Runge – Kutta nebo lineární vícestupňové metody, zvláště je-li požadována vysoká přesnost.[6]
Derivace
Metodu Euler lze odvodit mnoha způsoby. Nejprve je zde geometrický popis výše.
Další možností je zvážit Taylorova expanze funkce kolem :
Diferenciální rovnice to říká . Pokud je toto nahrazeno v Taylorově expanzi a jsou kvadratické a vyšší řády ignorovány, vzniká Eulerova metoda.[7] Níže je použita Taylorova expanze k analýze chyby způsobené Eulerovou metodou a lze ji rozšířit na produkci Metody Runge – Kutta.
Úzce související derivace je nahradit dopředu konečný rozdíl vzorec pro derivát,
v diferenciální rovnici . Tím se opět získá Eulerova metoda.[8] Podobný výpočet vede k metoda středního bodu a zpětně Eulerova metoda.
Nakonec lze integrovat diferenciální rovnici z na a použít základní věta o počtu dostat:
Nyní aproximujte integrál levou rukou obdélníková metoda (pouze s jedním obdélníkem):
Kombinací obou rovnic najdeme opět Eulerovu metodu.[9] V této myšlenkové linii lze i nadále dospět k různým lineární vícestupňové metody.
Chyba místního zkrácení
The chyba místního zkrácení Eulerovy metody je chyba v jediném kroku. Je to rozdíl mezi numerickým řešením po jednom kroku, a přesné řešení v čase . Numerické řešení je dáno vztahem
Pro přesné řešení používáme Taylorovo rozšíření zmíněné v části Derivace výše:
Místní chyba zkrácení (LTE) zavedená Eulerovou metodou je dána rozdílem mezi těmito rovnicemi:
Tento výsledek je platný, pokud má omezenou třetí derivaci.[10]
To ukazuje, že pro malé , místní chyba zkrácení je přibližně úměrná . Díky tomu je Eulerova metoda méně přesná (pro malé ) než jiné techniky vyššího řádu, jako např Metody Runge-Kutta a lineární vícestupňové metody, pro které je místní chyba zkrácení úměrná vyššímu výkonu velikosti kroku.
Trochu odlišnou formulaci chyby místního zkrácení lze získat použitím Lagrangeova formuláře pro zbytek termínu v Taylorova věta. Li má spojitou druhou derivaci, pak existuje a takhle
Ve výše uvedených výrazech pro chybu druhá derivace neznámého přesného řešení lze nahradit výrazem zahrnujícím pravou stranu diferenciální rovnice. Ve skutečnosti to vyplývá z rovnice že
Chyba globálního zkrácení
The chyba globálního zkrácení je chyba ve stanoveném čase , ale po mnoha krocích je třeba provést metody, aby bylo dosaženo tohoto času od počátečního času. Globální chyba zkrácení je kumulativní účinek místních chyb zkrácení spáchaných v každém kroku.[13] Počet kroků lze snadno určit , což je úměrné a chyba spáchaná v každém kroku je úměrná (viz předchozí část). Lze tedy očekávat, že chyba globálního zkrácení bude úměrná .[14]
Toto intuitivní uvažování lze zpřesnit. Pokud řešení má omezenou druhou derivaci a je Lipschitz kontinuální ve svém druhém argumentu je pak globální chyba zkrácení (GTE) omezena
kde je horní mez na druhé derivaci v daném intervalu a je Lipschitzova konstanta .[15]
Přesná forma této vazby má malý praktický význam, protože ve většině případů vazba výrazně nadhodnocuje skutečnou chybu spáchanou Eulerovou metodou.[16] Důležité je, že ukazuje, že chyba globální zkrácení je (přibližně) úměrná . Z tohoto důvodu se o Eulerově metodě říká, že je prvního řádu.[17]
Numerická stabilita

Eulerova metoda může být také numerická nestabilní, zejména pro tuhé rovnice, což znamená, že numerické řešení roste velmi velké pro rovnice, kde přesné řešení není. To lze ilustrovat pomocí lineární rovnice
Přesné řešení je , která se rozpadá na nulu jako . Pokud je však na tuto rovnici s velikostí kroku použita Eulerova metoda , pak je numerické řešení kvalitativně špatné: osciluje a roste (viz obrázek). To znamená být nestabilní. Pokud se například použije menší velikost kroku , pak se numerické řešení rozpadne na nulu.

Pokud je na lineární rovnici použita Eulerova metoda , pak je numerické řešení nestabilní, pokud je produkt je mimo region
znázorněno vpravo. Tato oblast se nazývá (lineární) oblast stability.[18] V příkladu je -2,3, takže pokud pak který je mimo oblast stability, a tak je numerické řešení nestabilní.
Toto omezení - spolu s jeho pomalou konvergencí chyby s h- znamená, že Eulerova metoda se často nepoužívá, kromě jednoduchého příkladu numerické integrace.
Chyby zaokrouhlování
Dosavadní diskuse ignorovala důsledky chyba zaokrouhlování. V kroku n Eulerovy metody má chyba zaokrouhlování zhruba velikost εyn kde ε je stroj epsilon. Za předpokladu, že chyby zaokrouhlování mají přibližně stejnou velikost, je kombinovaná chyba zaokrouhlování dovnitř N kroky je zhruba Nεy0 pokud všechny chyby ukazují stejným směrem. Protože počet kroků je nepřímo úměrný velikosti kroku h, celková chyba zaokrouhlování je úměrná ε / h. Ve skutečnosti je však extrémně nepravděpodobné, že by všechny chyby zaokrouhlování směřovaly stejným směrem. Pokud se místo toho předpokládá, že chyby zaokrouhlování jsou nezávislé náhodné proměnné, pak je očekávaná celková chyba zaokrouhlování úměrná .[19]
U extrémně malých hodnot velikosti kroku bude tedy chyba zkrácení malá, ale účinek chyby zaokrouhlování může být velký. Většině účinků chyby zaokrouhlování lze snadno zabránit, pokud kompenzovaný součet se používá ve vzorci pro Eulerovu metodu.[20]
Úpravy a rozšíření
Jednoduchá modifikace Eulerovy metody, která eliminuje problémy se stabilitou uvedené v předchozí části, je zpětně Eulerova metoda:
To se liší od (standardní nebo dopředné) Eulerovy metody v tom, že funkce se vyhodnotí v koncovém bodě kroku, místo v počátečním bodě. Zpětná Eulerova metoda je implicitní metoda, což znamená, že vzorec pro zpětnou Eulerovu metodu má na obou stranách, takže při použití zpětné Eulerovy metody musíme vyřešit rovnici. Díky tomu je implementace nákladnější.
Další úpravy Eulerovy metody, které pomáhají se stabilitou, poskytují exponenciální Eulerova metoda nebo částečně implicitní Eulerova metoda.
Složitější metody mohou dosáhnout vyššího řádu (a vyšší přesnosti). Jednou z možností je použít více vyhodnocení funkcí. To dokládá metoda středního bodu který je již zmíněn v tomto článku:
- .
To vede k rodině Metody Runge – Kutta.
Druhou možností je použít více minulých hodnot, jak dokládá dvoustupňová metoda Adams – Bashforth:
To vede k rodině lineární vícestupňové metody. Existují další úpravy, které využívají techniky kompresního snímání k minimalizaci využití paměti[21]
V populární kultuře
Ve filmu Skryté postavy, Katherine Goble se při výpočtu opětovného vstupu astronauta uchyluje k Eulerově metodě John Glenn z oběžné dráhy Země.[22]
Viz také
- Metoda Crank – Nicolson
- Přechodový sestup podobně používá konečné kroky, zde k nalezení minima funkcí
- Seznam metod Runge-Kutta
- Lineární vícestupňová metoda
- Numerická integrace (pro výpočet určitých integrálů)
- Numerické metody pro obyčejné diferenciální rovnice
Poznámky
- ^ Řezník 2003, str. 45; Hairer, Nørsett & Wanner 1993, str. 35
- ^ Atkinson 1989, str. 342; Řezník 2003, str. 60
- ^ Řezník 2003, str. 45; Hairer, Nørsett & Wanner 1993, str. 36
- ^ Řezník 2003, str. 3; Hairer, Nørsett & Wanner 1993, str. 2
- ^ Viz také Atkinson 1989, str. 344
- ^ Hairer, Nørsett & Wanner 1993, str. 40
- ^ Atkinson 1989, str. 342; Hairer, Nørsett & Wanner 1993, str. 36
- ^ Atkinson 1989, str. 342
- ^ Atkinson 1989, str. 343
- ^ Řezník 2003, str. 60
- ^ Atkinson 1989, str. 342
- ^ Stoer & Bulirsch 2002, str. 474
- ^ Atkinson 1989, str. 344
- ^ Řezník 2003, str. 49
- ^ Atkinson 1989, str. 346; Lakoba 2012, rovnice (1,16)
- ^ Iserles 1996, str. 7
- ^ Řezník 2003, str. 63
- ^ Řezník 2003, str. 70; Iserles 1996, str. 57
- ^ Řezník 2003, str. 74–75
- ^ Řezník 2003, str. 75–78
- ^ Unni, M. P .; Chandra, M. G .; Kumar, A. A. (březen 2017). "Redukce paměti pro numerické řešení diferenciálních rovnic pomocí kompresního snímání". 2017 IEEE 13. mezinárodní kolokvium o zpracování signálu jeho aplikacemi (CSPA): 79–84. doi:10.1109 / CSPA.2017.8064928. ISBN 978-1-5090-1184-1. S2CID 13082456.
- ^ Khan, Amina. „Seznamte se s matematikem„ Skrytých postav “, který pomohl vyslat Američany do vesmíru“. Los Angeles Times. Citováno 12. února 2017.
Reference
- Atkinson, Kendall A. (1989). Úvod do numerické analýzy (2. vyd.). New York: John Wiley & Sons. ISBN 978-0-471-50023-0.
- Ascher, Uri M .; Petzold, Linda R. (1998). Počítačové metody pro běžné diferenciální rovnice a diferenciálně-algebraické rovnice. Philadelphie: Společnost pro průmyslovou a aplikovanou matematiku. ISBN 978-0-89871-412-8.
- Řezník, John C. (2003). Numerické metody pro obyčejné diferenciální rovnice. New York: John Wiley & Sons. ISBN 978-0-471-96758-3.
- Hairer, Ernst; Nørsett, Syvert Paul; Wanner, Gerhard (1993). Řešení obyčejných diferenciálních rovnic I: Nonstiffovy problémy. Berlín, New York: Springer-Verlag. ISBN 978-3-540-56670-0.
- Iserles, Arieh (1996). První kurz numerické analýzy diferenciálních rovnic. Cambridge University Press. ISBN 978-0-521-55655-2.
- Stoer, Josef; Bulirsch, Roland (2002). Úvod do numerické analýzy (3. vyd.). Berlín, New York: Springer-Verlag. ISBN 978-0-387-95452-3.
- Lakoba, Taras I. (2012), Jednoduchá Eulerova metoda a její úpravy (PDF) (Poznámky k přednášce pro MATH334), University of Vermont, vyvoláno 29. února 2012
- Unni, M P. (2017). "Redukce paměti pro numerické řešení diferenciálních rovnic pomocí kompresního snímání". 2017 IEEE 13. mezinárodní kolokvium o zpracování signálu a jeho aplikacích (CSPA). IEEE CSPA. str. 79–84. doi:10.1109 / CSPA.2017.8064928. ISBN 978-1-5090-1184-1. S2CID 13082456.
externí odkazy
Média související s Eulerova metoda na Wikimedia Commons
- Implementace Eulerovy metody v různých jazycích podle Rosettský kód
- „Eulerova metoda“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]