Metoda konečných rozdílů - Finite difference method

Diferenciální rovnice
Diferenciální rovnice Navier – Stokes používané k simulaci proudění vzduchu kolem překážky
Rozsah Přírodní vědy Inženýrství Astronomie Fyzika Chemie Biologie Geologie Aplikovaná matematika Mechanika kontinua Teorie chaosu Dynamické systémy Společenské vědy Ekonomika Populační dynamika
Klasifikace
Typy Obyčejný Částečný Diferenciálně-algebraické Integro-diferenciál Frakční Lineární Nelineární Podle typu proměnné Závislé a nezávislé proměnné Autonomní Komplex Spojeno / odpojeno Přesný Homogenní  / nehomogenní Funkce Objednat Operátor Zápis
Vztah k procesům Rozdíl (diskrétní analog) Stochastický Stochastické částečné Zpoždění
Řešení
Existence a jedinečnost Picardova – Lindelöfova věta Peano věta o existenci Carathéodoryho věta o existenci Cauchyho – Kowalevského věta
Obecná témata Wronský Fázový portrét Fázový prostor Lyapunov  / Asymptotická  / Exponenciální stabilita Míra konvergence Série  / Integrovaná řešení Numerická integrace Funkce Dirac delta
Metody řešení Inspekce Metoda charakteristik Euler Exponenciální vzorec odezvy Konečný rozdíl  ( Crank – Nicolson ) Konečný element Nekonečný prvek Konečný objem Galerkin Petrov – Galerkin Integrační faktor Integrální transformace Poruchová teorie Runge – Kutta Oddělení proměnných Neurčené koeficienty Variace parametrů
Lidé Isaac Newton Gottfried Leibniz Leonhard Euler Émile Picard Józef Maria Hoene-Wroński Ernst Lindelöf Rudolf Lipschitz Augustin-Louis Cauchy John Crank Phyllis Nicolson Carl David Tolmé Runge Martin Kutta
proti t E

V numerické analýze jsou metody konečných rozdílů ( FDM ) třídou numerických technik pro řešení diferenciálních rovnic aproximací derivací s konečnými rozdíly . Prostorová doména i časový interval (je -li k dispozici) jsou diskretizovány nebo rozděleny do konečného počtu kroků a hodnota řešení v těchto diskrétních bodech je aproximována řešením algebraických rovnic obsahujících konečné rozdíly a hodnoty z blízkých bodů.

Metody konečných diferencií převádějí obyčejné diferenciální rovnice (ODE) nebo parciální diferenciální rovnice (PDE), které mohou být nelineární , na systém lineárních rovnic, které lze vyřešit technikami maticové algebry. Moderní počítače mohou tyto lineární výpočty algebry provádět efektivně, což spolu s jejich relativně snadnou implementací vedlo k rozšířenému používání FDM v moderní numerické analýze. Dnes jsou FDM spolu s metodami konečných prvků jedním z nejběžnějších přístupů k numerickému řešení PDE .

Odvození z Taylorova polynomu

Za prvé, za předpokladu, že funkce, jejíž deriváty mají být aproximovány, se chová správně, podle Taylorovy věty můžeme vytvořit rozšíření Taylorovy řady

${\ Displaystyle f (x_ {0}+h) = f (x_ {0})+{\ frac {f '(x_ {0})} {1!}} h+{\ frac {f^{(2) } (x_ {0})} {2!}} h^{2} +\ cdots +{\ frac {f^{(n)} (x_ {0})} {n!}} h^{n} +R_ {n} (x),}$

kde n ! označuje faktoriál z n , a R _n ( x ) je zbytek termín, označující rozdíl mezi Taylorova polynomu stupně n a původní funkci. Pro první derivaci funkce „f“ odvodíme aproximaci tak, že nejprve zkrátíme Taylorův polynom:

${\ Displaystyle f (x_ {0}+h) = f (x_ {0})+f '(x_ {0}) h+R_ {1} (x),}$

Nastavení, x ₀ = a máme,

${\ Displaystyle f (a+h) = f (a)+f '(a) h+R_ {1} (x),}$

Dělením na h získáte :

${\ Displaystyle {f (a+h) \ over h} = {f (a) \ over h}+f '(a)+{R_ {1} (x) \ over h}}$

Řešení pro f '(a):

${\ Displaystyle f '(a) = {f (a+h) -f (a) \ over h}-{R_ {1} (x) \ over h}}$

Za předpokladu, že je dostatečně malý, aproximace první derivace „f“ je: ${\ displaystyle R_ {1} (x)}$

${\ Displaystyle f '(a) \ zhruba {f (a+h) -f (a) \ přes h}.}$

Toto je, ne náhodou, podobné definici derivátu, která je dána jako:

${\ Displaystyle f '(a) = \ lim _ {h \ to 0} {\ frac {f (a+h) -f (a)} {h}}.}$

kromě limitu směrem k nule (metoda je pojmenována po tomto).

Přesnost a pořádek

Chyba v řešení metody je definována jako rozdíl mezi aproximací a přesným analytickým řešením. Dva zdroje chyb v metodách konečných rozdílů jsou chyby zaokrouhlení, ztráta přesnosti v důsledku počítačového zaokrouhlování desetinných veličin a chyba zkrácení nebo chyba diskretizace , rozdíl mezi přesným řešením původní diferenciální rovnice a přesnou kvantitou za předpokladu dokonalá aritmetika (tj. za předpokladu, že není zaokrouhleno).

Aby bylo možné použít metodu konečných rozdílů k aproximaci řešení problému, je třeba nejprve diskretizovat doménu problému. To se obvykle provádí rozdělením domény do jednotné mřížky (viz obrázek vpravo). To znamená, že metody konečných rozdílů vytvářejí sady diskrétních numerických aproximací derivátu, často způsobem „časově krokovým“.

Výrazem obecného zájmu je chyba místního zkrácení metody. Typicky vyjádřená pomocí notace Big-O , chyba místního zkrácení odkazuje na chybu z jedné aplikace metody. To znamená, že jde o množství , které odkazuje na přesnou hodnotu a numerickou aproximaci. Zbývající člen Taylorova polynomu je vhodný pro analýzu chyby místního zkrácení. Pomocí Lagrangeovy formy zbytku z Taylorova polynomu pro , což je ${\ Displaystyle f '(x_ {i})-f' _ {i}}$${\ displaystyle f '(x_ {i})}$${\ displaystyle f '_ {i}}$${\ displaystyle f (x_ {0}+h)}$

${\ Displaystyle R_ {n} (x_ {0}+h) = {\ frac {f^{(n+1)} (\ xi)} {(n+1)!}} (h)^{n+ 1}}$, kde , ${\ Displaystyle x_ {0} <\ xi <x_ {0}+h}$

lze zjistit dominantní člen chyby místního zkrácení. Například opět pomocí vzorce pro dopředný rozdíl pro první derivaci s vědomím, že , ${\ Displaystyle f (x_ {i}) = f (x_ {0}+ih)}$

${\ Displaystyle f (x_ {0}+ih) = f (x_ {0})+f '(x_ {0}) ih+{\ frac {f' '(\ xi)} {2!}} (ih) ^{2},}$

as určitou algebraickou manipulací to vede k

${\ Displaystyle {\ frac {f (x_ {0}+ih) -f (x_ {0})} {ih}} = f '(x_ {0})+{\ frac {f' '(\ xi) } {2!}} Ih,}$

a dále s tím, že množství vlevo je aproximací z metody konečných rozdílů a že množství vpravo je přesné množství zájmu plus zbytek, jasně, že zbytek je chyba místního zkrácení. Konečný výraz tohoto příkladu a jeho pořadí je:

${\ Displaystyle {\ frac {f (x_ {0}+ih) -f (x_ {0})} {ih}} = f '(x_ {0})+O (h).}$

To znamená, že v tomto případě je chyba místního zkrácení úměrná velikostem kroků. Kvalita a trvání simulovaného řešení FDM závisí na výběru rovnice diskretizace a velikosti kroků (časové a prostorové kroky). S menší velikostí kroku se výrazně zvyšuje kvalita dat a doba simulace. Pro praktické využití je proto nutná rozumná rovnováha mezi kvalitou dat a délkou simulace. Velké časové kroky jsou užitečné pro zvýšení rychlosti simulace v praxi. Příliš velké časové kroky však mohou způsobit nestability a ovlivnit kvalitu dat.

K určení stability numerického modelu jsou často vyhodnocována kritéria von Neumanna a Courant-Friedrichse-Lewyho .

Příklad: obyčejná diferenciální rovnice

Zvažte například obyčejnou diferenciální rovnici

${\ Displaystyle u '(x) = 3u (x) +2. \,}$

Eulerova metoda pro řešení této rovnice používá konečný rozdíl kvocient

${\ displaystyle {\ frac {u (x+h) -u (x)} {h}} \ cca u '(x)}$

aproximovat diferenciální rovnici tak, že ji nejprve nahradíme u '(x), poté použijeme malou algebru (vynásobíme obě strany h a poté přidáme u (x) na obě strany), abychom získali

${\ Displaystyle u (x+h) = u (x)+h (3u (x) +2). \,}$

Poslední rovnice je rovnice konečných rozdílů a vyřešením této rovnice získáte přibližné řešení diferenciální rovnice.

Příklad: Tepelná rovnice

Zvažte normalizovanou tepelnou rovnici v jedné dimenzi s homogenními Dirichletovými okrajovými podmínkami

${\ displaystyle U_ {t} = U_ {xx} \,}$

${\ Displaystyle U (0, t) = U (1, t) = 0 \,}$ (okrajová podmínka)

${\ Displaystyle U (x, 0) = U_ {0} (x) \,}$ (počáteční podmínka)

Jedním ze způsobů, jak numericky vyřešit tuto rovnici, je aproximovat všechny derivace konečnými rozdíly. Rozdělujeme doménu v prostoru pomocí sítě a v čase pomocí sítě . Předpokládáme rovnoměrné rozdělení jak v prostoru, tak v čase, takže rozdíl mezi dvěma po sobě následujícími mezerami bude h a mezi dvěma po sobě jdoucími časovými body bude k . Body ${\ displaystyle x_ {0}, ..., x_ {J}}$${\ displaystyle t_ {0}, ...., t_ {N}}$

${\ Displaystyle u (x_ {j}, t_ {n}) = u_ {j}^{n}}$

bude představovat numerickou aproximaci ${\ Displaystyle u (x_ {j}, t_ {n}).}$

Explicitní metoda

Pomocí dopředného rozdílu v čase${\ displaystyle t_ {n}}$ a centrálního rozdílu druhého řádu pro prostorovou derivaci v poloze ( FTCS ) dostaneme rovnici opakování: ${\ displaystyle x_ {j}}$

${\ Displaystyle {\ frac {u_ {j}^{n+1} -u_ {j}^{n}} {k}} = {\ frac {u_ {j+1}^{n} -2u_ {j }^{n}+u_ {j-1}^{n}} {h^{2}}}. \,}$

Toto je explicitní metoda pro řešení jednorozměrné tepelné rovnice .

Z ostatních hodnot můžeme získat tímto způsobem: ${\ displaystyle u_ {j}^{n+1}}$

${\ Displaystyle u_ {j}^{n+1} = (1-2r) u_ {j}^{n}+ru_ {j-1}^{n}+ru_ {j+1}^{n}}$

kde ${\ Displaystyle r = k/h^{2}.}$

S touto relací opakování a znalostí hodnot v čase n lze získat odpovídající hodnoty v čase n +1. a musí být nahrazeny okrajovými podmínkami, v tomto případě jsou obě 0. ${\ displaystyle u_ {0}^{n}}$${\ displaystyle u_ {J}^{n}}$

Tato explicitní metoda je známá jako numericky stabilní a konvergentní kdykoli . Číselné chyby jsou úměrné časovému kroku a druhé mocnině mezerového kroku: ${\ Displaystyle r \ leq 1/2}$

${\ Displaystyle \ Delta u = O (k)+O (h^{2}) \,}$

Implicitní metoda

Použijeme -li zpětný rozdíl v čase${\ displaystyle t_ {n+1}}$ a centrální rozdíl druhého řádu pro prostorovou derivaci v poloze (Zpětný čas, metoda středového prostoru „BTCS“), dostaneme rovnici opakování: ${\ displaystyle x_ {j}}$

${\ Displaystyle {\ frac {u_ {j}^{n+1} -u_ {j}^{n}} {k}} = {\ frac {u_ {j+1}^{n+1} -2u_ {j}^{n+1}+u_ {j-1}^{n+1}} {h^{2}}}. \,}$

Toto je implicitní metoda pro řešení jednorozměrné tepelné rovnice .

Z řešení soustavy lineárních rovnic můžeme získat : ${\ displaystyle u_ {j}^{n+1}}$

${\ Displaystyle (1+2r) u_ {j}^{n+1} -ru_ {j-1}^{n+1} -ru_ {j+1}^{n+1} = u_ {j}^ {n}}$

Schéma je vždy numericky stabilní a konvergentní, ale obvykle je numericky intenzivnější než explicitní metoda, protože vyžaduje řešení systému numerických rovnic v každém časovém kroku. Chyby jsou lineární v časovém kroku a kvadratické ve vesmírném kroku:

${\ Displaystyle \ Delta u = O (k)+O (h^{2}). \,}$

Crank -Nicolsonova metoda

Nakonec pokud použijeme centrální rozdíl v čase a centrální rozdíl druhého řádu pro prostorovou derivaci v poloze („CTCS“), dostaneme rovnici opakování: ${\ displaystyle t_ {n+1/2}}$${\ displaystyle x_ {j}}$

${\ Displaystyle {\ frac {u_ {j}^{n+1} -u_ {j}^{n}} {k}} = {\ frac {1} {2}} \ left ({\ frac {u_ {j+1}^{n+1} -2u_ {j}^{n+1}+u_ {j-1}^{n+1}} {h^{2}}}+{\ frac {u_ {j+1}^{n} -2u_ {j}^{n}+u_ {j-1}^{n}} {h^{2}}} \ right). \,}$

Tento vzorec je známý jako Crank -Nicolsonova metoda .

Z řešení soustavy lineárních rovnic můžeme získat : ${\ displaystyle u_ {j}^{n+1}}$

${\ Displaystyle (2+2r) u_ {j}^{n+1} -ru_ {j-1}^{n+1} -ru_ {j+1}^{n+1} = (2-2r) u_ {j}^{n}+ru_ {j-1}^{n}+ru_ {j+1}^{n}}$

Schéma je vždy numericky stabilní a konvergentní, ale obvykle je numericky intenzivnější, protože vyžaduje řešení systému numerických rovnic v každém časovém kroku. Chyby jsou kvadratické v časovém i vesmírném kroku:

${\ Displaystyle \ Delta u = O (k^{2})+O (h^{2}). \,}$

Srovnání

Abychom to shrnuli, obvykle je schéma Crank -Nicolson nejpřesnějším schématem pro malé časové kroky. Pro větší časové kroky funguje implicitní schéma lépe, protože je méně výpočetně náročné. Explicitní schéma je nejméně přesné a může být nestabilní, ale je také nejsnadněji implementovatelné a nejméně numericky náročné.

Zde je příklad. Níže uvedené obrázky představují řešení daná výše uvedenými metodami pro aproximaci tepelné rovnice

${\ Displaystyle U_ {t} = \ alpha U_ {xx}, \ quad \ alpha = {\ frac {1} {\ pi ^{2}}},}$

s okrajovou podmínkou

${\ Displaystyle U (0, t) = U (1, t) = 0.}$

Přesné řešení je

${\ Displaystyle U (x, t) = {\ frac {1} {\ pi ^{2}}} e ^{-t} \ sin (\ pi x).}$

Příklad: Laplaceův operátor

(Spojitý) Laplaceův operátor v dimenzích je dán vztahem . Diskrétní Laplaceův operátor závisí na rozměru . ${\ displaystyle n}$${\ Displaystyle \ Delta u (x) = \ sum _ {i = 1}^{n} \ částečné _ {i}^{2} u (x)}$${\ displaystyle \ Delta _ {h} u}$${\ displaystyle n}$

V 1D je Laplaceův operátor aproximován jako

${\ Displaystyle \ Delta u (x) = u '' (x) \ cca {\ frac {u (xh) -2u (x)+u (x+h)} {h^{2}}} =: \ Delta _ {h} u (x) \ ,.}$

Tato aproximace je obvykle vyjádřena pomocí následující šablony

${\ displaystyle \ Delta _ {h} = {\ frac {1} {h^{2}}} {\ begin {bmatrix} 1 & -2 & 1 \ end {bmatrix}}}$

a který představuje symetrickou, tridiagonální matici. Pro ekvidistantní mřížku se získá Toeplitzova matice .

2D případ ukazuje všechny charakteristiky obecnějšího případu nD. Každou druhou parciální derivaci je třeba aproximovat podobně jako v případě 1D

${\ Displaystyle {\ begin {aligned} \ Delta u (x, y) & = u_ {xx} (x, y)+u_ {yy} (x, y) \\ & \ zhruba {\ frac {u (xh , y) -2u (x, y)+u (x+h, y)} {h^{2}}}+{\ frac {u (x, yh) -2u (x, y)+u (x , y+h)} {h^{2}}} \\ & = {\ frac {u (xh, y)+u (x+h, y) -4u (x, y)+u (x, yh )+u (x, y+h)} {h^{2}}} \\ & =: \ Delta _ {h} u (x, y) \ ,, \ end {zarovnáno}}}$

což je obvykle dáno následující šablonou

${\ Displaystyle \ Delta _ {h} = {\ frac {1} {h^{2}}} {\ begin {bmatrix} & 1 \\ 1 & -4 & 1 \\ & 1 \ end {bmatrix}} \ ,.}$

Konzistence

Konzistenci výše uvedené aproximace lze ukázat u vysoce pravidelných funkcí, jako je např . Prohlášení je ${\ displaystyle u \ in C^{4} (\ Omega)}$

${\ Displaystyle \ Delta u- \ Delta _ {h} u = {\ mathcal {O}} (h^{2}) \ ,.}$

Abychom to dokázali, je třeba nahradit rozšíření Taylor Series do objednávky 3 do diskrétního Laplaceova operátoru.

Vlastnosti

Subharmonie

Podobně jako u spojitých subharmonických funkcí lze definovat subharmonické funkce pro aproximace s konečným rozdílem${\ displaystyle u_ {h}}$

${\ Displaystyle -\ Delta _ {h} u_ {h} \ leq 0 \ ,.}$

Střední hodnota

Jeden může definovat obecný šablony z pozitivního typu via

${\ Displaystyle {\ begin {bmatrix} & \ alpha _ {N} \\\ alpha _ {W} &-\ alpha _ {C} & \ alpha _ {E} \\ & \ alpha _ {S} \ end {bmatrix}} \ ,, \ quad \ alpha _ {i}> 0 \ ,, \ quad \ alpha _ {C} = \ sum _ {i \ in \ {N, E, S, W \}} \ alpha _ {i} \ ,.}$

Pokud je (diskrétní) subharmonický pak následující vlastnost průměrná hodnota je držitelem ${\ displaystyle u_ {h}}$

${\ Displaystyle u_ {h} (x_ {C}) \ leq {\ frac {\ sum _ {i \ in \ {N, E, S, W \}} \ alpha _ {i} u_ {h} (x_ {i})} {\ sum _ {i \ in \ {N, E, S, W \}} \ alpha _ {i}}} \ ,,}$

kde je aproximace vyhodnocena v bodech mřížky a vzorník je považován za kladný typ.

Podobná vlastnost střední hodnoty platí také pro spojitý případ.

Maximální princip

Pro (diskrétní) subharmonickou funkci platí následující ${\ displaystyle u_ {h}}$

${\ Displaystyle \ max _ {\ Omega _ {h}} u_ {h} \ leq \ max _ {\ částečné \ Omega _ {h}} u_ {h} \ ,,}$

kde jsou diskretizace spojité domény , respektive hranice . ${\ Displaystyle \ Omega _ {h}, \ částečné \ Omega _ {h}}$${\ displaystyle \ Omega}$${\ Displaystyle \ partial \ Omega}$

Podobný maximální princip platí také pro spojitý případ.

Metoda SBP-SAT

Metoda SBP-SAT je stabilní a přesnou technikou pro diskretizaci a uložení okrajových podmínek dobře navržené parciální diferenciální rovnice pomocí konečných rozdílů vysokého řádu. Metoda je založena na konečných rozdílech, kde operátoři diferenciace vykazují vlastnosti součtu po částech. Obvykle se tyto operátory skládají z diferenciačních matic s centrálními rozdílovými šablonami v interiéru s pečlivě vybranými jednostrannými hraničními šablonami navrženými tak, aby napodobovaly integraci jednotlivých částí v diskrétním nastavení. Pomocí techniky SAT jsou okrajové podmínky PDE uloženy slabě, kde jsou hraniční hodnoty „přitahovány“ směrem k požadovaným podmínkám, než aby byly přesně splněny. Pokud jsou správně vybrány parametry ladění (vlastní technice SAT), výsledný systém ODE bude vykazovat podobné energetické chování jako kontinuální PDE, tj. Systém nemá žádný nefyzický růst energie. To zaručuje stabilitu, pokud je použito integrační schéma s oblastí stability, která zahrnuje části imaginární osy, jako je metoda Runge-Kutta čtvrtého řádu. Díky tomu je technika SAT atraktivní metodou ukládání okrajových podmínek pro metody konečných rozdílů vyššího řádu, na rozdíl například od metody vstřikování, která obvykle nebude stabilní, pokud jsou použity operátory diferenciace vysokého řádu.

Viz také

Reference

Další čtení

• KW Morton a DF Mayers, numerické řešení parciálních diferenciálních rovnic, úvod . Cambridge University Press, 2005.
• Autar Kaw a E. Eric Kalu, Numerical Methods with Applications , (2008) [1] . Obsahuje stručný, inženýrsky orientovaný úvod do FDM (pro ODE) v kapitole 08.07 .
• John Strikwerda (2004). Schémata konečných rozdílů a parciální diferenciální rovnice (2. vyd.). SIAM. ISBN 978-0-89871-639-9.
• Smith, GD (1985), Numerical Solution of Partial Differential Equations: Finite Difference Methods, 3rd ed. , Oxford University Press
• Peter Olver (2013). Úvod do parciálních diferenciálních rovnic . Springer. Kapitola 5: Konečné rozdíly. ISBN 978-3-319-02099-0..
• Randall J. LeVeque , Metody konečných rozdílů pro obyčejné a parciální diferenciální rovnice , SIAM, 2007.
• Sergey Lemeshevsky, Piotr Matus, Dmitriy Poliakov (Eds): „Exact Finite-Difference Schemes“, De Gruyter (2016). DOI: https://doi.org/10.1515/9783110491326 .