Finite-Differenzen-Methode

In numerischen Analyse , die Finite - Differenzen - Methode ist eine übliche Technik zum Auffinden ungefähre Lösungen von partiellen Differentialgleichungen , welche einander ausreichend nahe bei der Lösung eines Systems von Beziehungen (Digital - Diagramm) Verknüpfung der Werte der unbekannten Funktionen an bestimmten Punkten besteht. Andere .

Diese Methode scheint am einfachsten zu implementieren zu sein, da sie in zwei Schritten abläuft: einerseits die Diskretisierung der Operatoren der Ableitung / Differenzierung durch endliche Differenzen, andererseits die Konvergenz des so erhaltenen numerischen Diagramms, wenn der Abstand zwischen dem Punkte nimmt ab.

Approximation von Operatoren durch Taylor-Formeln

Eine Diskretisierung der Differentialoperatoren (erste Ableitungen, Sekunden usw., teilweise oder nicht) kann durch Taylors Formeln erhalten werden .

Die Taylor-Young- Formulierung ist in ihrer einfachen Verwendung vorzuziehen, die Taylor-Formulierung mit Laplace-Integralrest ermöglicht die Messung der Fehler (vgl. Unten).

Beispiele für Operatorannäherungen

Zentrierte Annäherungen

An einem Punkt $x$ und für einen Wert $h$ des Diskretisierungsschritts, so dass $u$ über das Intervall $[ x - h , x + h ]$ dreimal differenzierbar ist , führt die Taylor-Young-Formel zu zwei Beziehungen:

{\ displaystyle u (x + h) = u (x) + \ sum _ {n = 1} ^ {3} {{\ frac {h ^ {n}} {n!}} u ^ {(n)} (x)} + h ^ {3} \ varepsilon _ {1} (x, h)}

{\ displaystyle u (xh) = u (x) + \ sum _ {n = 1} ^ {3} {{\ frac {(-h) ^ {n}} {n!}} u ^ {(n) } (x)} + h ^ {3} \ varepsilon _ {2} (x, h)}

wobei die beiden Funktionen $ε i ( x , h )$ mit $h$ gegen 0 konvergieren . Deshalb

{\ displaystyle {\ frac {u (x + h) -u (x)} {h}} = u '(x) + {\ frac {h} {2}} u' '(x) + {\ frac {h ^ {2}} {3!}} u ^ {(3)} (x) + h ^ {2} \ varepsilon _ {1} (x, h)}

{\ displaystyle {\ frac {u (xh) -u (x)} {h}} = - u '(x) + {\ frac {h} {2}} u' '(x) - {\ frac { h ^ {2}} {3!}} u ^ {(3)} (x) + h ^ {2} \ varepsilon _ {2} (x, h)}

entsprechen zwei Annäherungen von $u ( x )$ der 1 st Ordnung $h$ .

Durch Subtrahieren der vorhergehenden Entwicklungen, die sich auf den Durchschnitt der beiden endlichen Differenzen vor und hinter $u ( x )$ belaufen , erhalten wir

{\ displaystyle {\ frac {u (x + h) -u (xh)} {2h}} = u '(x) + {\ frac {h ^ {2}} {6}} u ^ {(3) } (x) + h ^ {2} \ varepsilon _ {3} (x, h)}

Dies ist eine Näherung von $u ( x )$ von 2 e Ordnung $h$ .

Dezentrierte Annäherungen Upstream-Offset

An einem Punkt $x$ und für einen Wert $h$ des Diskretisierungsschritts, so dass $u$ über das Intervall $[ x , x + 2 h ]$ dreimal differenzierbar ist , führt die Taylor-Young-Formel zu der Beziehung:

{\ displaystyle u (x + h) = u (x) + \ sum _ {n = 1} ^ {3} {{\ frac {h ^ {n}} {n!}} u ^ {(n)} (x)} + h ^ {3} \ varepsilon _ {1} (x, h)}

wobei die Funktion mit $h$ gegen 0 konvergiert . Deshalb ${\ displaystyle \ varepsilon _ {i} (x, h)}$

{\ displaystyle {\ frac {u (x + h) -u (x)} {h}} = u '(x) + {\ frac {h} {2}} u' '(x) + {\ frac {h ^ {2}} {3!}} u ^ {(3)} (x) + h ^ {2} \ varepsilon _ {1} (x, h)}

entspricht einer Annäherung der $u ( x )$ der 1 st Ordnung $h$ .

Durch Wiederholen des Vorgangs für einen nachgeschalteten Offset schreiben Sie Folgendes:

{\ displaystyle u '' (x) = {\ frac {{\ frac {u (x + 2h) -u (x + h)} {h}} - {\ frac {u (x + h) -u ( x)} {h}}} {h}} + \ varepsilon _ {2} (x, h)}

wovon

{\ displaystyle {\ frac {u (x + 2h) -2u (x + h) + u (x)} {h ^ {2}}} = u '' (x) + {\ frac {h ^ {2 }} {6}} u ^ {(3)} (x) + h ^ {2} \ varepsilon _ {3} (x, h)}

Dies ist eine Näherung $u '' ( x )$ von 2 e Ordnung $h$ .

Formeln wurden auf aufeinanderfolgende Bestellungen ausgedehnt

Durch Erweitern der Größe der Schablone ist es möglich, endliche Differenzen höherer Ordnungen mit ähnlichen Methoden zu bestimmen (Erhöhen der Ordnung in Taylors Formel und Bestimmen einer geeigneten linearen Kombination , um überflüssige Terme aufzuheben).

Zum Beispiel können wir an einem Punkt $x$ und für einen Wert $h$ des Diskretisierungsschritts, so dass $u$ über das Intervall $[ x - 2 h , x + 2 h ]$ viermal differenzierbar ist , durch Erweiterung der Taylor-Formel mehr als fünf zeigen Punktdiagramme

{\ displaystyle u '(x) = {\ frac {u (x-2h) -8u (xh) + 8u (x + h) -u (x + 2h)} {12h}} + \ varepsilon _ {1} '(x, h)}

{\ displaystyle u '' (x) = {\ frac {-u (x-2h) + 16u (xh) -30u (x) + 16u (x + h) -u (x + 2h)} {12h ^ { 2}}} + \ varepsilon _ {2} '(x, h)}

sind Annäherungen an die erste und zweite Ableitung der Ordnung 4.

Erweiterung auf multivariate Funktionen Upstream-Offset

An einem Punkt $( x , y )$ und für einen Wert $h$ des Diskretisierungsschritts (der gleiche in beiden Dimensionen), so dass $u ( x , y )$ auf dem Rechteck $[0, x + 2 h ] \times [ 0, y + 2 h ]$ können wir schreiben

{\ displaystyle {\ frac {(u (x + 2h, 0) -2u (x + h, 0) + u (x, 0)) + (u (0, y + 2h) -2u (0, y +) h) + u (0, y))} {h ^ {2}}} = \ Delta u (x, y) + {\ frac {h ^ {2}} {12}} (\ teilweise _ {x} ^ {4} u (x, y) + \ partiell _ {y} ^ {4} u (x, y)) + h ^ {2} \ varepsilon _ {5} (x, y, h)}

was eine Annäherung der Laplace - $Δ u ( x , y )$ des 2 e , um $h$ (vgl Gleichung Laplace und Poisson-Gleichung ).

Zentrierte Schablone

An einem Punkt $( x , y )$ und für einen Wert $h$ des Diskretisierungsschritts (der gleiche in beiden Dimensionen), so dass $u ( x , y )$ auf dem Rechteck $[ x - h , x + h ] \times$ viermal differenzierbar ist $[$ $y$ $-$ $h$ $,$ $y$ $+$ $h$ $]$ können wir schreiben

{\ displaystyle {\ frac {u (x + h, y) + u (xh, y) + u (x, y + h) + u (x, yh) -4u (x, y)} {h ^ { 2}}} = \ Delta u (x, y) + {\ frac {h ^ {2}} {12}} (\ partielle _ {x} ^ {4} u (x, y) + \ partielle _ { y} ^ {4} u (x, y)) + h ^ {2} \ varepsilon _ {5} (x, y, h)}

was eine Annäherung der Laplace - $Δ u ( x , y )$ des 2 e , um $h$ (vgl Gleichung Laplace und Poisson-Gleichung ).

Das oben erwähnte Konzept der "Ordnung" entspricht einem Konzept der lokalen Konvergenz des diskretisierten Operators. Die globale Konvergenz der diskreten Lösung ist ein ganz anderes Konzept, obwohl zwischen beiden eine familiäre Beziehung besteht.

Gittergewebe

Bei der Finite-Differenzen-Methode ist ein Netz eine Menge isolierter Punkte ( Knoten genannt ), die sich im Definitionsbereich der Funktionen befinden, die den partiellen Differentialgleichungen unterliegen, wobei auf den einzigen Knoten die Unbekannten definiert sind, die der Näherung entsprechen Werte dieser Funktionen.

Das Netz enthält auch Knoten, die sich am Rand des Feldes befinden (oder zumindest "nahe" an diesem Rand liegen), um die Randbedingungen und / oder die Anfangsbedingung mit ausreichender Genauigkeit auferlegen zu können .

A priori besteht die erste Qualität eines Netzes darin, das Feld, in dem es sich entwickelt, so gut wie möglich abzudecken, um den Abstand zwischen jedem Knoten und seinem nächsten Nachbarn zu begrenzen. Das Netz muss es aber auch ermöglichen, die diskrete Formulierung der Differenzierungsoperatoren auszudrücken: Aus diesem Grund befinden sich die Knoten des Netzes meist auf einem Gitter, dessen Hauptrichtungen die Achsen der Variablen sind.

Man nennt Schritt des Netzes den Abstand zwischen zwei benachbarten Knoten, die sich auf einer Linie parallel zu einer der Achsen befinden. In diesem Sinne ist der Schritt sowohl ein lokaler als auch ein direktionaler Begriff. Wir werden von globaler Tonhöhe sprechen , um die größte lokale Tonhöhe zu bezeichnen , eine Vorstellung, die gerichtet bleibt.

Obwohl eine konstante Tonhöhe meistens beibehalten wird (ohne ein theoretisches Problem für die Auflösung aufzuwerfen), ist es manchmal sinnvoll, eine variable Tonhöhe einzuführen , die in den Bereichen, in denen die genaue Lösung stärker schwankt , feiner gewählt wird: Dieser Trick macht es möglich um die Anzahl der Unbekannten zu verringern, ohne die Genauigkeit der Ergebnisse zu beeinträchtigen. Andererseits ist die Formulierung etwas komplexer, da die Diskretisierung der Differentialoperatoren dies berücksichtigen muss.

Beispiele für Maschen

Für eine Differentialgleichung bezüglich einer Funktion einer Variablen, deren Domäne (in ) das Intervall $[0;$ $In 1]$ ist ein konstantes Teilungsgitter durch $M$ $+ 1$ Knoten $x$ $i$ $=$ $ih$ $, 0 \leq$ $i$ $\leq$ $M$ mit Schritt $h$ $= 1 /$ $M gekennzeichnet$ . Dieses Netz enthält die beiden Randpunkte $x$ $0$ und $x$ $M,$ denen mögliche Randbedingungen auferlegt werden. $\ mathbb {R}$

Betrachten Sie eine partielle Differentialgleichung bezüglich einer Funktion zweier Variablen (Domäne ): ${\ displaystyle \ Omega \ subset \ mathbb {R} ^ {2}}$

Wenn $Ω$ ein Rechteck ist $[0; 1] \times [0; 1]$ (deren Seiten parallel zu den Achsen sind), ein Netz, das sich aus einem Gitter $( x i , y j ) = ( ih , jk )$ ergibt $, 0 \leq$ $i$ $\leq$ $M$ $, 0 \leq$ $j$ $\leq$ $N$ mit den Schritten $h = 1 / M$ und $k = 1 / N$ ist eine einfache Verallgemeinerung des vorherigen Falles.
Wenn Ω eine Scheibe ist, die am Ursprung und mit dem Radius 1 zentriert ist, betrachten wir das Netz, das durch die Knoten eines Gitters gebildet wird, die sich in der Scheibe befinden, dh ( x i , y j ) ∈ Ω wobei ( x i , y j ) = ( ih , jk ) mit dem Abstand h = 1 / M . Um mögliche Randbedingungen aufzuerlegen (zum Beispiel die von Dirichlet, die den Wert der Funktion auf ∂Ω festlegen ), sind die seltenen Knoten, die sich genau an der Grenze befinden, zu wenig repräsentativ. Es ist dann ratsam, die Eigenschaft "an der Grenze sein" auf andere Knoten zu erweitern, die sich in der Nähe befinden, indem beispielsweise alle Knoten des Netzes eingeschlossen werden, die keine vier direkten Nachbarn haben. Die Grenzwerte, die an diesen neuen Grenzknoten festgelegt werden sollen, können auf verschiedene Arten definiert werden:
- Indem man den Wert des exakten Problems nimmt, das dem nächstgelegenen Punkt von $\partialΩ auferlegt wird$ : In diesem Fall $erzeugen$ die geografischen Unregelmäßigkeiten der $Randknoten$ des Netzes (beobachtet, wenn $h$ abnimmt) Störungen der diskreten Lösung, bestenfalls lokale Anomalien unabhängig von der genauen Lösung.
- Indem man berücksichtigt, dass die Werte der neuen Grenzknoten unbekannt sind, aber zusätzliche diskretisierte Differentialbeziehungen hinzufügt, die diese Unbekannten „natürlich“ mit den Werten der benachbarten Knoten und denen bestimmter Punkte von $\partialΩ verbinden$ . Wenn der Ansatz in seiner Implementierung etwas komplexer ist, reduziert er den Fehler des vorherigen erheblich.

Digitales Schema

Ein numerisches Schema kann als algebraische Formulierung eines diskreten Problems definiert werden, das unter Verwendung der Finite-Differenzen-Methode entworfen wurde. Der Prozess umfasst die folgenden Schritte:

Wählen Sie die diskreten Operatoren aus, die Annäherungen an die Differentialoperatoren der exakten Formulierung sind.
Generieren Sie ein Netz der Definitionsdomäne, während Sie auf die Randknoten und die Art und Weise der Übersetzung der Randbedingungen achten.
Indem man sich auf die Ausdrücke stützt, die sich aus den diskreten Operatoren ergeben, um die Beziehungen herzustellen, die die Werte der Funktionen an die Knoten des Netzes binden (die unbekannten Faktoren).
Stellen Sie sicher, dass die Menge der Unbekannten und die Beziehungen, die sie verbinden, ein numerisches Problem darstellen, das nicht über- oder unterbestimmt ist. Diese Überprüfung ist eine Mindestbedingung, um auf eine Lösung zu hoffen, gibt jedoch keine Garantie für die globale Konvergenz.

Sobald das numerische Diagramm erstellt und das diskrete Problem formuliert ist, geht es nicht nur darum, es zu lösen, sondern auch sicherzustellen, dass die diskrete Lösung zur exakten Lösung konvergiert, wenn die Schritte des Netzes gegen 0 tendieren.

Für bestimmte sogenannte explizite Diagramme ist es möglich, die Unbekannten so zu ordnen, dass jedes von ihnen rekursiv aus den vorhergehenden bestimmt werden kann, die bereits berechnet werden sollen ( Dreiecksmatrix ). Bei impliziten Schemata ist es manchmal möglich, die Lösung des gesamten Systems aller Gleichungen zu vermeiden. Dies ist insbesondere bei einem sich entwickelnden System der Fall, dessen durch räumliche Variablen charakterisierter Zustand durch Anfangsbedingungen (t = 0) definiert wird und sich dann im Laufe der Zeit progressiv weiterentwickelt: Das numerische Diagramm bleibt in der Variablen zeitlich explizit und betrifft nur seinen impliziten Charakter die räumlichen Variablen.

In allen Fällen bezieht sich jede Gleichung des numerischen Diagramms nur auf eine kleine Anzahl von Unbekannten. In einer linearen Umgebung führt diese Eigenschaft dazu, das diskrete Problem unter Verwendung spärlicher Matrizen zu formulieren und es zu nutzen, um es mit geeigneten Methoden zu lösen . Dieser Vorteil ist nicht zu leugnen, wenn die Größe des Netzes den Rahmen einer didaktischen Studie überschreitet.

Die Auflösung numerischer Diagramme basiert im Allgemeinen auf klassischen algebraischen Methoden. Andere äquivalente Formulierungen können jedoch Optimierungsmethoden erfordern .

Beispiel eines digitalen Diagramms

Betrachten Sie das folgende Problem:

{\ displaystyle u '(x) - \ tau u (x) = 0 \, \ forall x \ in [0,1], \ u (0) = u_ {0}.}

Dieses Problem bleibt akademisch, sofern die genaue Lösung bekannt ist:

{\ displaystyle u (x) = u_ {0} \, e ^ {\ tau x}.}

Mit dem expliziten Euler-Schema der Ordnung 1, das auf ein reguläres Netz mit der Tonhöhe $h = 1 / M$ angewendet wird , werden die Unbekannten $u n,$ die $u ( nh )$ widerspiegeln, durch die Beziehungen verbunden

{\ displaystyle {\ frac {u_ {n + 1} -u_ {n}} {h}} - \ tau u_ {n} = 0, \; \ forall \, 0 \ leqslant n <M.}

Dieses Diagramm führt zur Wiederholungsrelation

{\ displaystyle u_ {n + 1} = (1 + h \ tau) u_ {n}}

deren explizite Lösung ist

{\ displaystyle u_ {n} = \ left (1 + {\ frac {\ tau} {M}} \ right) ^ {n} u_ {0}.}

Eine andere Formulierung, die unter Verwendung des Diagramms der Ordnung 2 erhalten wird (außer an dem Knoten $n = 1,$ für den man das Diagramm der Ordnung 1 beibehält), ergibt

{\ displaystyle {\ frac {u_ {1} -u_ {0}} {h}} - \ tau u_ {0} = 0,}

{\ displaystyle {\ frac {u_ {n + 1} -u_ {n-1}} {2h}} - \ tau u_ {n} = 0, \; \ forall \, 0 <n <M.}

Wie das erste ist dieses zweite Diagramm explizit .

Es ist sehr einfach, die Lösungen dieser beiden Diagramme numerisch zu bestimmen, um sie mit der genauen Lösung zu vergleichen. Es erscheint legitim, mit dem zweiten Diagramm bessere Ergebnisse zu erwarten, da seine Reihenfolge höher ist als die des ersten (es kann gezeigt werden, dass die beiden digitalen Diagramme einheitlich konvergent sind):

Diese Intuition gilt, wenn $τ > 0 ist$ .
Andererseits stellt sich heraus, dass es fehlerhaft ist, wenn $τ$ ausreichend negativ ist (zum Beispiel $τ <-3$ ). In der Tat erzeugt das Diagramm der Ordnung 1, das auf den ersten Knoten angewendet wird, in diesem Fall eine Anfangsdifferenz $u 1 - u ( h ),$ die Schwingungen auf den an den folgenden Knoten beobachteten Differenzen erzeugt, Schwingungen, die bis zu den letzten Knoten verstärkt werden: Eulers Schema erzeugt zweifellos eine viel bessere Lösung.

Dieser Vergleich zeigt deutlich, dass eine gute Darstellung der Differentialoperatoren keine ausreichende Bedingung ist, um ein gutes numerisches Diagramm zu erhalten.

Konvergenz

Die Konvergenz eines digitalen Diagramms ist eine theoretische Gesamteigenschaft, die sicherstellt, dass der Unterschied (im Sinne eines Standards ) zwischen der Näherungslösung und der exakten Lösung gegen 0 geht, wenn der Diskretisierungsschritt gegen 0 geht (oder wenn jeder der Schritte global zugeordnet ist) mit den verschiedenen Richtungen tendiert gegen 0).

Die ungefähre Lösung eines digitalen Diagramms bleibt nicht sehr glaubwürdig, solange seine Konvergenz nicht gezeigt wurde. Dieser Beweis ist zweifellos der heikelste Punkt der Methode der feinen Unterschiede, auf jeden Fall derjenige, der die Verwendung von Analysewerkzeugen erfordert .

Es reicht nicht aus, anhand konkreter numerischer Beispiele zu überprüfen, ob das Verhalten der diskreten Lösung den Erwartungen zur Gewährleistung der Konvergenz entspricht. Andererseits können solche Beispiele helfen, das Gegenteil zu beweisen.

Konzeptionell manifestieren sich die Unterschiede zwischen der Näherungslösung und der exakten Lösung in einer Kombination zweier Phänomene:

Die Variation, die lokal durch die dem diskretisierten Operator inhärenten Näherungen induziert wird. Es ist der Begriff der Konsistenz oder Robustheit des Diagramms. Zum Beispiel ist eine hohe Näherungsordnung (erhalten durch Taylors Theorem ) nicht von großem Wert, wenn die genaue Lösung nicht die erforderliche Regelmäßigkeit aufweist.
Im Fall eines expliziten Diagramms die Ausbreitung der Variationen, die sich während der Berechnungsphasen mit den vorhergehenden Variationen verbinden und sich progressiv verstärken können. Es ist der Begriff der Stabilität des Diagramms, der auch gedacht wird, wenn er implizit ist.

Diese Konzepte berücksichtigen keine Rundungsfehler, die die Sache weiter komplizieren können, wie in der folgenden Abbildung gezeigt, die anhand eines konkreten Beispiels erhalten wird :

Der Standard, für den die Konvergenz untersucht wird, muss unabhängig von den Diskretisierungsschritten bleiben. Es ist jedoch üblich, Standards zu verwenden, die sich auf diejenigen von L p -Räumen beziehen . Für eine Funktion einer Variablen:

Einfache Konvergenz: Konvergenz an jedem Punkt des Definitionsraums.
Gleichmäßige Konvergenz (in L ∞ ): ${\ displaystyle \ | u_ {h} -u \ | _ {\ infty} = h \ max _ {i} | u_ {i} -u (ih) |.}$
Konvergenz in L 2 : ${\ displaystyle \ | u_ {h} -u \ | _ {2} = h {\ sqrt {\ sum _ {i} | u_ {i} -u (ih) | ^ {2}}}.}$
Konvergenz in L 1 : ${\ displaystyle \ | u_ {h} -u \ | _ {1} = h \ sum _ {i} | u_ {i} -u (ih) |.}$

Im Rahmen eines evolutionären Problem mit Anfangsbedingung , Lax-Theorem rigoros legt die Begriffe der Konsistenz und Stabilität , die zweite eine notwendige und hinreichende Bedingung sein , um sicherzustellen , Konvergenz .

Beispiel für Konvergenz

In dem letzten oben dargestellten Beispiel, für das man gleichzeitig die genaue Lösung und die ungefähre Lösung kennt (Diagramm von Euler) , erfüllt der Bericht ${\ displaystyle \ displaystyle u (x) = u_ {0} e ^ {\ tau x}}$ ${\ displaystyle \ displaystyle u_ {n} = u_ {0} (1+ \ tau h) ^ {n}}$

{\ displaystyle \ ln \ left (\ left | {\ frac {u_ {n}} {u (nh)}} \ right | \ right) = n | \ ln (1+ \ tau h) - \ tau h | = n \, O (h ^ {2}) = O (h)}

was gegen 0 tendiert, wenn gegen 0 tendiert, dies einheitlich für ${\ displaystyle \ displaystyle h}$ ${\ displaystyle n \ leqslant 1 / h.}$

Sie tendiert also gleichmäßig gegen 0, was die Konvergenz dieses Euler-Schemas in der Norm beweist ${\ displaystyle \ displaystyle u (nh) -u_ {n}}$ ${\ displaystyle \ |. \ | _ {\ infty}.}$

Anmerkungen und Referenzen

Man beobachtet hier einen Unterschied zur Finite-Elemente-Methode, bei der die unbekannten Funktionen an jedem Punkt der Elemente des Netzes definiert werden (bestehend aus Dreiecken, Rechtecken usw.). Da es jedoch möglich ist, die durch endliche Differenzen erhaltenen Ergebnisse zu interpolieren , ist diese Unähnlichkeit nicht grundlegend.
Auch wenn die Formulierung des ursprünglichen Problems Integrale umfasst, ist es oft vorteilhaft, zusätzliche Funktionen einzuführen, um sie darzustellen.

Siehe auch

Zum Thema passende Artikel

Externe Links