Slutlig skillnadsmetod - Finite difference method

Differentialekvationer
Navier – Stokes differentialekvationer som används för att simulera luftflöde runt ett hinder
Omfattning Naturvetenskap Teknik Astronomi Fysik Kemi Biologi Geologi Tillämpad matematik Kontinuummekanik Kaosteori Dynamiska system Samhällsvetenskap Ekonomi Befolkningsdynamik
Klassificering
Typer Vanlig Partiell Differential-algebraisk Integro-differential Fraktionerad Linjär Icke-linjärt Efter variabel typ Beroende och oberoende variabler Autonom Komplex Kopplad / frånkopplad Exakt Homogen  / nonhomogen Funktioner Ordning Operatör Notation
Relation till processer Skillnad (diskret analog) Stokastisk Stokastisk partiell Dröjsmål
Lösning
Existens och unikhet Picard – Lindelöf sats Peano existens sats Carathéodorys existenssats Cauchy – Kowalevski sats
Allmänna ämnen Wronskian Fasporträtt Fasutrymme Lyapunov  / asymptotisk  / exponentiell stabilitet Konvergenshastighet Serie  / integrerade lösningar Numerisk integration Dirac delta -funktion
Lösningsmetoder Inspektion Metod för egenskaper Euler Exponentiell svarsformel Ändlig skillnad  ( Crank – Nicolson ) Slutligt element Oändligt element Ändlig volym Galerkin Petrov – Galerkin Integrerande faktor Integrerade transformationer Störningsteori Runge – Kutta Separation av variabler Obestämda koefficienter Variation av parametrar
människor 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
v t e

I numerisk analys är finite-difference-metoder ( FDM ) en klass av numeriska tekniker för att lösa differentialekvationer genom att approximera derivat med ändliga skillnader . Både den rumsliga domänen och tidsintervallet (om tillämpligt) diskretiseras eller bryts upp i ett begränsat antal steg, och värdet på lösningen vid dessa diskreta punkter approximeras genom att lösa algebraiska ekvationer som innehåller ändliga skillnader och värden från närliggande punkter.

Slutliga skillnadsmetoder omvandlar vanliga differentialekvationer (ODE) eller partiella differentialekvationer (PDE), som kan vara olinjära , till ett system av linjära ekvationer som kan lösas med matrisalgebra -tekniker. Moderna datorer kan effektivt utföra dessa linjära algebraberäkningar, vilket tillsammans med deras relativa enkelhet har lett till en utbredd användning av FDM i modern numerisk analys. Idag är FDM en av de vanligaste metoderna för numerisk lösning av PDE, tillsammans med ändliga elementmetoder .

Ursprung från Taylors polynom

Först och främst, förutsatt att funktionen vars derivat ska approximeras är korrekt uppförd, genom Taylors sats , kan vi skapa en Taylor-serie expansion

${\ 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),}$

var n ! betecknar factorial för n , och R _n ( x ) är en återstående term, som betecknar skillnaden mellan Taylor -polynomet för grad n och den ursprungliga funktionen. Vi kommer att härleda en approximation för det första derivatet av funktionen "f" genom att först stympa Taylor -polynomet:

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

Inställning, x ₀ = a vi har,

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

Att dela med h ger:

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

Lösning för f '(a):

${\ displaystyle f '(a) = {f (a+h) -f (a) \ över h}-{R_ {1} (x) \ över h}}$

Om vi ​​antar att det är tillräckligt litet är approximationen av det första derivatet av "f": ${\ displaystyle R_ {1} (x)}$

${\ displaystyle f '(a) \ approx {f (a+h) -f (a) \ over h}.}$

Detta är inte av en slump liknande definitionen av derivat, som ges som:

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

förutom gränsen mot noll (metoden är uppkallad efter detta).

Noggrannhet och ordning

Felet i en metodlösning definieras som skillnaden mellan approximationen och den exakta analytiska lösningen. De två felkällorna i begränsade skillnadsmetoder är avrundningsfel , förlust av precision på grund av datoravrundning av decimalmängder och avstämningsfel eller diskretiseringsfel , skillnaden mellan den exakta lösningen av den ursprungliga differentialekvationen och den exakta kvantiteten förutsatt perfekt aritmetik (det vill säga förutsatt ingen avrundning).

För att använda en begränsad skillnadsmetod för att approximera lösningen på ett problem måste man först diskretisera problemets domän. Detta görs vanligtvis genom att dela upp domänen i ett enhetligt rutnät (se bilden till höger). Detta innebär att metoder med begränsad skillnad producerar uppsättningar av diskreta numeriska approximationer till derivatet, ofta på ett "tidsstegande" sätt.

Ett uttryck för allmänt intresse är det lokala trunkeringsfelet i en metod. Typiskt uttryckt med Big-O-notering , lokal trunkeringsfel avser felet från en enda applikation av en metod. Det vill säga det är kvantiteten om refererar till det exakta värdet och till den numeriska approximationen. Resten av ett Taylor -polynom är bekvämt för att analysera det lokala avkortningsfelet. Använda Lagrange -formen av resten från Taylor -polynomet för , vilket är ${\ 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}}$, var , ${\ displaystyle x_ {0} <\ xi <x_ {0}+h}$

den dominerande termen för det lokala trunkeringsfelet kan upptäckas. Till exempel, igen med hjälp av framåtskillnadsformeln för det första derivatet, med vetskap om att , ${\ 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},}$

och med viss algebraisk manipulation leder detta till

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

och noterar vidare att kvantiteten till vänster är approximationen från metoden med begränsad skillnad och att kvantiteten till höger är den exakta räntemängden plus en återstod, klart att resten är det lokala avkortningsfelet. Ett sista uttryck för detta exempel och dess ordning är:

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

Detta innebär att det lokala trunkeringsfelet i detta fall är proportionellt mot stegstorleken. Kvaliteten och varaktigheten av den simulerade FDM -lösningen beror på valet av diskretiseringsekvation och stegstorlekarna (tid och rymdsteg). Datakvaliteten och simuleringstiden ökar betydligt med mindre stegstorlek. Därför är en rimlig balans mellan datakvalitet och simuleringstid nödvändig för praktisk användning. Stora tidssteg är användbara för att öka simuleringshastigheten i praktiken. Tidssteg som är för stora kan dock skapa instabilitet och påverka datakvaliteten.

De von Neumann och Courant-Friedrichs-Lewy kriterier är ofta utvärderas för att bestämma den numeriska modellen stabilitet.

Exempel: vanlig differentialekvation

Tänk till exempel på den vanliga differentialekvationen

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

Den Eulers metod för att lösa denna ekvation använder finita skillnaden kvoten

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

att approximera differentialekvationen genom att först ersätta den med u '(x) och sedan applicera lite algebra (multiplicera båda sidor med h och sedan lägga till u (x) på båda sidor) för att få

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

Den sista ekvationen är en ekvitet med begränsad skillnad, och att lösa denna ekvation ger en ungefärlig lösning på differentialekvationen.

Exempel: Värmeekvationen

Betrakta den normaliserade värmeekvationen i en dimension, med homogena Dirichlet -gränsförhållanden

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

${\ displaystyle U (0, t) = U (1, t) = 0 \,}$ (randvillkor)

${\ displaystyle U (x, 0) = U_ {0} (x) \,}$ (initialtillstånd)

Ett sätt att numeriskt lösa denna ekvation är att approximera alla derivat med begränsade skillnader. Vi delar upp domänen i rymden med hjälp av ett nät och i tid med ett nät . Vi antar en enhetlig uppdelning både i rymden och i tid, så skillnaden mellan två på varandra följande blankstegspunkter kommer att vara h och mellan två på varandra följande tidpunkter kommer att vara k . Poängen ${\ displaystyle x_ {0}, ..., x_ {J}}$${\ displaystyle t_ {0}, ...., t_ {N}}$

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

kommer att representera den numeriska approximationen av ${\ displaystyle u (x_ {j}, t_ {n}).}$

Explicit metod

Med hjälp av en framåtskillnad i tid${\ displaystyle t_ {n}}$ och en andra ordningens centrala skillnad för rymdderivatet vid position ( FTCS ) får vi återkommande ekvation: ${\ 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}}}. \,}$

Detta är en tydlig metod för att lösa den endimensionella värmeekvationen .

Vi kan få från de andra värdena på detta sätt: ${\ displaystyle u_ {j}^{n+1}}$

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

var ${\ displaystyle r = k/h^{2}.}$

Så, med denna återkommande relation, och genom att känna till värdena vid tidpunkten n , kan man få motsvarande värden vid tidpunkten n +1. och måste ersättas med gränsvillkoren, i detta exempel är de båda 0. ${\ displaystyle u_ {0}^{n}}$${\ displaystyle u_ {J}^{n}}$

Denna tydliga metod är känd för att vara numeriskt stabil och konvergent när som helst . De numeriska felen är proportionella mot tidsteget och kvadraten i rymdsteget: ${\ displaystyle r \ leq 1/2}$

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

Implicit metod

Om vi ​​använder bakåtskillnaden vid tidpunkten${\ displaystyle t_ {n+1}}$ och en andra ordningens centrala skillnad för rymdderivatet vid position (The Backward Time, Centered Space Method "BTCS") får vi återkommande ekvation: ${\ 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}}}. \,}$

Detta är en implicit metod för att lösa den endimensionella värmeekvationen .

Vi kan få genom att lösa ett system med linjära ekvationer: ${\ 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}}$

Schemat är alltid numeriskt stabilt och konvergerande men vanligtvis mer numeriskt intensivt än den uttryckliga metoden eftersom det kräver att man löser ett system med numeriska ekvationer vid varje tidsteg. Felen är linjära över tidssteget och kvadratiska över rymdsteget:

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

Vev – Nicolson -metod

Slutligen, om vi använder den centrala skillnaden vid tidpunkten och en andra ordningens centrala skillnad för rymdderivatet vid position ("CTCS") får vi återkommande ekvation: ${\ displaystyle t_ {n+1/2}}$${\ displaystyle x_ {j}}$

${\ displaystyle {\ frac {u_ {j}^{n+1} -u_ {j}^{n}} {k}} = {\ frac {1} {2}} \ vänster ({\ 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}}} \ höger). \,}$

Denna formel är känd som Crank – Nicolson -metoden .

Vi kan få genom att lösa ett system med linjära ekvationer: ${\ 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}}$

Schemat är alltid numeriskt stabilt och konvergerande men vanligtvis mer numeriskt intensivt eftersom det kräver att man löser ett system med numeriska ekvationer vid varje tidsteg. Felen är kvadratiska över både tidssteg och rymdsteg:

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

Jämförelse

För att sammanfatta är vanligtvis Crank – Nicolson -schemat det mest exakta schemat för små tidssteg. För större tidssteg fungerar det implicita systemet bättre eftersom det är mindre beräkningskrävande. Det uttryckliga schemat är det minst exakta och kan vara instabilt, men är också det enklaste att implementera och det minst numeriskt intensiva.

Här är ett exempel. Figurerna nedan visar de lösningar som ges av metoderna ovan för att approximera värmeekvationen

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

med gränsvillkoret

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

Den exakta lösningen är

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

Exempel: Laplace -operatören

Den (kontinuerliga) Laplace -operatören i -dimensioner ges av . Den diskreta Laplace -operatören beror på dimensionen . ${\ displaystyle n}$${\ displaystyle \ Delta u (x) = \ sum _ {i = 1}^{n} \ partiell _ {i}^{2} u (x)}$${\ displaystyle \ Delta _ {h} u}$${\ displaystyle n}$

I 1D approximeras Laplace -operatören som

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

Denna approximation uttrycks vanligtvis via följande stencil

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

och som representerar en symmetrisk, tridiagonal matris. För ett lika långt rutnät får man en Toeplitz -matris .

2D -fallet visar alla egenskaper hos det mer generella nD -fallet. Varje andra partiella derivat måste approximeras ungefär som 1D -fallet

${\ displaystyle {\ begin {align} \ Delta u (x, y) & = u_ {xx} (x, y)+u_ {yy} (x, y) \\ & \ approx {\ 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 {align}}}$

som vanligtvis ges av följande stencil

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

Konsistens

Konsistensen av den ovannämnda approximationen kan visas för höggradigt regelbundna funktioner, såsom . Uttalandet är ${\ displaystyle u \ i C^{4} (\ Omega)}$

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

För att bevisa detta måste man ersätta Taylor Series -utökningar upp till order 3 i den diskreta Laplace -operatören.

Egenskaper

Subharmonisk

På samma sätt som kontinuerliga subharmoniska funktioner kan man definiera subharmoniska funktioner för approximationer med begränsad skillnad${\ displaystyle u_ {h}}$

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

Medelvärde

Man kan definiera en allmän stencil av positiv typ 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} \ ,.}$

Om är (diskret) underton då följande medelvärdet egendom innehar ${\ 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 \ i \ {N, E, S, W \}} \ alfa _ {i}}} \ ,,}$

där approximationen utvärderas på punkter i rutnätet och schablonen antas vara av positiv typ.

En liknande medelvärdesegenskap gäller också för det kontinuerliga fallet.

Maximal princip

För en (diskret) subharmonisk funktion gäller följande ${\ displaystyle u_ {h}}$

${\ displaystyle \ max _ {\ Omega _ {h}} u_ {h} \ leq \ max _ {\ partiell \ Omega _ {h}} u_ {h} \ ,,}$

var finns diskretiseringar av den kontinuerliga domänen respektive gränsen . ${\ displaystyle \ Omega _ {h}, \ partiell \ Omega _ {h}}$${\ displaystyle \ Omega}$${\ displaystyle \ partial \ Omega}$

En liknande maxprincip gäller också för det kontinuerliga fodralet.

SBP-SAT-metoden

SBP-SAT-metoden är en stabil och noggrann teknik för att diskretisera och införa gränsvillkor för en välpositionerad partiell differentialekvation med hjälp av begränsade skillnader i hög ordning. Metoden är baserad på ändliga skillnader där differentieringsoperatörerna uppvisar summa-för-delar-egenskaper. Vanligtvis består dessa operatörer av differentieringsmatriser med centrala skillnadstenciler i interiören med noggrant utvalda ensidiga gränsstenciler utformade för att efterlikna integration-för-delar i den diskreta inställningen. Med hjälp av SAT -tekniken införs gränsvillkoren för PDE svagt, där gränsvärdena "dras" mot de önskade villkoren snarare än exakt uppfylls. Om avstämningsparametrarna (tillhörande SAT-tekniken) väljs korrekt, kommer det resulterande systemet för ODE att uppvisa liknande energibeteende som den kontinuerliga PDE, dvs systemet har ingen icke-fysisk energitillväxt. Detta garanterar stabilitet om ett integrationsschema med ett stabilitetsområde som inkluderar delar av den imaginära axeln, till exempel Runge-Kutta-metoden av fjärde ordningen, används. Detta gör SAT -tekniken till en attraktiv metod för att införa gränsvillkor för högre ordnade begränsade skillnadsmetoder, till skillnad från till exempel injektionsmetoden, som vanligtvis inte kommer att vara stabil om differentieringsoperatörer med hög ordning används.

Se även

Referenser

Vidare läsning

• KW Morton och DF Mayers, numerisk lösning av partiella differentialekvationer, en introduktion . Cambridge University Press, 2005.
• Autar Kaw och E. Eric Kalu, Numerical Methods with Applications , (2008) [1] . Innehåller en kort, teknikorienterad introduktion till FDM (för ODE) i kapitel 08.07 .
• John Strikwerda (2004). Slutliga skillnadsscheman och partiella differentialekvationer (andra upplagan). SIAM. ISBN 978-0-89871-639-9.
• Smith, GD (1985), Numerical Solution of Partial Differential Equations: Finite Difference Methods, 3: e upplagan. , Oxford University Press
• Peter Olver (2013). Introduktion till partiella differentialekvationer . Springer. Kapitel 5: Slutliga skillnader. ISBN 978-3-319-02099-0..
• Randall J. LeVeque , Finite Difference Methods for Ordinary and Partial Differential Equations , SIAM, 2007.
• Sergey Lemeshevsky, Piotr Matus, Dmitriy Poliakov (Eds): "Exact Finite-Difference Schemes", De Gruyter (2016). DOI: https://doi.org/10.1515/9783110491326 .