Zusammenfassung Wissenschaftliches Rechnen

Aus VISki
Wechseln zu: Navigation, Suche

Ziel dieser Zusammenfassung: All denjenigen welche die Vorlesung besucht (oder Slides studiert) haben, helfen, sich an alle Details und Zusammenhänge zu erinnern

  • Die behandelten Konzepte kurz und präzise erläutern und übersichtlich darstellen
  • Die wichtigsten Eigenschaften von Konzepten auflisten
  • Die Begriffe (Buzz-Words) wichtiger Konzepte auflisten und kurz beschreiben, damit man sich an die Begriffe erinnern kann
  • Überblick vermitteln (Wo gehört was hin? Wie hängt was zusammen? Worin unterscheiden sich die Konzepte?)


Nicht Ziel dieser Zusammenfassung: Jemandem der keine Ahnung vom Stoff der Vorlesung hat diesen verständlich machen

  • Die Konzepte ins Detail erklären (Dies ist Aufgabe der Vorlesung/Slides)
  • Viele Beispiele auflisten
  • Prüfungsfragen als Beispiele (Besser das getestete Wissen in die Zusammenfassung integrieren)
  • Nicht vorlesungsbezogenes Wissen vermitteln (Dies ist eine Zusammenfassung der Vorlesung. Eine Auswahl von all dem was es zu wissen gibt. Wer mehr will darf jeder Zeit Wikipedia verlinken)
  • Wikipedia kopieren


Fernziel

  • Zu einem Skript erweitern? (Bitte in einem neuen Artikel daran arbeiten)


Inhaltsverzeichnis

Mathematische Grundlagen

Dieser Abschnitt enthält Mathematische Grundlagen, welche nicht in anderen Vorlesungen behandelt wurden oder für die eine andere Betrachtung notwendig ist. Für Mathematische Grundlagen, welche behandelt wurden, siehe Zusammenfassungen der entsprechenden Vorlesungen. (Bitte keine mathematischen Grundlagen erklären, die anderswo schon erklärt sind... keine Redundanzen!)

Insbesondere:

Orthogonale Polynome

Zwei Polynome p(x) und q(x) mit sind orthogonal, wenn sie zu einem gegebenen Skalarprodukt 0 ergeben (Orthogonalitätsbedingung). Manchmal fordert man zusätzlich noch, dass das Skalarpodukt mit sich selbst normiert ist (Normalisierungsbdingung)

Das Skalarprodukt hat gewöhnlich die Form wobei eine zu definierende Gewichtsfunktion ist

Orthogonalitätsbedingung
Normalisierungsbedingung


Beispiel für eine Orthogonalitätsbedingung für das Skalarprodukt (Für die Gewichtsfunktion gilt also w(x) = 1)

Legendre Polynome

Legendre-Polynome sind im Intervall [-1,1] gegenseitig orthogonal bezüglich dem Skalarprodukt . (Man beachte dass dies nur im Intervall [-1,1] gilt.)


Für zwei Legendre-Polynome und im Intervall [-1,1] gilt:


Die ersten Legendre-Polynome


Eigenschaften

  • hat genau n einfach Nullstellen im Intervall ]-1,1[
  • Jedes Polynom vom Grad n kann als Linearkombination von Legendre Polynomen dargestellt werden

Bestimmen von orthogonalen Polynomen zu einem gegebenen Skalarprodukt

  1. Definiere allgemeine Polynome
  2. Stelle ein Gleichungssystem mit den Orthogonalitätsbedingungen auf (und falls nötig den Normalisierungsbedingungen)
    • (Orthogonalitätsbedingung)
    • (Orthogonalitätsbedingung)
    • (Orthogonalitätsbedingung)
    • (Normalisierungsbedingung falls gewünscht)
    • (Normalisierungsbedingung falls gewünscht)
    • (Normalisierungsbedingung falls gewünscht)
  3. Löse das Gleichungssystem nach den Koeffizienten auf

Verallgemeinerte Kettenregel

Gegeben

Gemäss verallgemeinerten Kettenregel ist dann die Ableitung wobei die Ableitung von f nach g ist, und sowie die Ableitung nach x ist


Beispiel

ToDo:
z.B. Ricatti-Gleichung
Alle momentan zu editierenden Einträge werden hier gesammelt.

Kurzrepetition

Kurze Repetition der benötigten Mathematischen Grundlagen

Numerische Integration

(=Numerische Quadratur)

Die Numerische Integration folgt generell dem Ansatz, das Integral mittels einer Approximation durch gewichtete Summen zu bestimmen:


Bemerkung zu den Gewichten wi

  • Die Gewichte summieren sich stets zur Länge des Intervalls, über welches integriert wird

Definitionen

Definition: Fehlerordnung

Die Fehlerordnung einer Integrationsregel entspricht der Potenz mit welcher der Fehler von der Intervallbreite abhängt


Definition: Präzision (Genauigkeitsgrad)

Die Präzision einer Integrationsregel entspricht dem höchsten Polynomgrad, für den exakte Integration mit dieser Integrationsregel möchlich ist

Newton-Cotes-Verfahren

  • Es handelt sich hierbei um eine ganze Familie von Verfahren, welche alle von gegebenen äquidistanten Stützstellen xi ausgehen und zu diesen die optimalen Gewichte wi bestimmen
  • Die zu integrierende Funktion wird durch ein Polynom vom Grad n approximiert, welches durch Interpolation erhalten wird.
  • Der Grad n des Interpolationspolynoms ist charakteristisch für die einzelnen Verfahren.


Eigenschaften

  • Mit zunehmendem n wird die Präzision und die Fehlerordnung besser, jedoch sind die Newton-Cotes-Regeln nur für kleine Werte von n stabil.
  • Ein Verfahren mit höherer Fehlerordnung liefert im allgemeinen nicht exaktere Resultate als ein Verfahren kleinerer Fehlerordnung


Mittelpunktregel (n=0)

  • Interpolation einer gegebenen Funktion durch ein Polynom 0-ter Ordnung im Intervall [a,b]
  • Stützstellen: 1 in der Mitte des Intervalls
  • Fehlerordnung: 3 (kubisch)
  • Präzision: 1
für ein bestimmtes


Trapezregel (n=1)

  • Interpolation einer gegebenen Funktion durch ein Polynom 1-ter Ordnung im Intervall [a,b]
  • Stützstellen: 2. Jeweils eine am Intvervall-Anfang und Ende
  • Fehlerordnung: 3 (kubisch)
  • Präzision: 1
für ein bestimmtes

Bemerkung

  • Gut geeignet für periodische Funktionen

Simpsonregel (n=2)

  • Interpolation einer gegebenen Funktion durch ein Polynom 2-ter Ordnung im Intervall [a,b]
  • Stützstellen: 3. 1 in der Mitte des Intervalls und je eine am Intervall Anfang und Ende
  • Fehlerordnung: 5 (quintisch)
  • Präzision: 3
für ein bestimmtes

3/8-Regel (n=3)

  • Interpolation einer gegebenen Funktion durch ein Polynom 3-ter Ordnung im Intervall [a,b]
  • Stützstellen: 4
ToDo:
Formel besorgen. Achtung: Bitte gleiche Variblenkonvention benutzen (insbesondere für h!)
Alle momentan zu editierenden Einträge werden hier gesammelt.
  • Fehlerordnung: 5
  • Präzision: 3

Milneregel (n=4)

  • Interpolation einer gegebenen Funktion durch ein Polynom 4-ter Ordnung im Intervall [a,b]
  • Stützstellen: Teilintervallbreite , Stützstelllen , Funktionswerte
  • Fehlerordnung: 7
  • Präzision: 5
ToDo:
Formel stimmt evt nicht. + Fehler ergänzen
Alle momentan zu editierenden Einträge werden hier gesammelt.

Konstruktion von Newton-Cotes-Formeln via Lagrange-Interpolation

Gesucht: wi so dass

Idee: Die Funktion f(x) wird durch ein Polynom vom Grad n angenähert:


1. Bestimmen von mittels Lagrange-Interpolation durch die gegebenen äquidistanten Stütstellen xi:

2. Einsetzen ergibt:

3. Dies lässt sich weiter vereinfachen

wobei

Konstruktion von Newton-Cotes-Formeln via Newton-Interpolation

am Beispiel der Simpson-Regel


Gesucht: wi so dass


Gegeben: Äquidistante Stützstellen


  • Idee ist die gegebene Funktion f(x) durch ein Polynom zu approximieren, und dann dieses zu integrieren. Es wird ein Polynom zweiten Grades verwendet, da 3 Stützstellen gegeben sind. Das approximierende Polynom erhält man z.B durch Newton-Interpolation


Fehlerabschätzung

Für ein Interpolationspolynom n-ten Grades welches die Funktion f(x) mittels den Stützstellen interpoliert gilt die Formel des Interpolationsfehlers:

für


Für den Integrationsfehler folgt:


Durch Anwendung des erweiterten Mittelwertsatzes und anschliessender Integration erhält man den Fehler

Newton-Cotes-Composite-Verfahren

Idee: Unterteilung des zu integrierenden Intervalls in Subintervalle und dann Integration der Subintervalle mit den Newton-Cotes-Verfahren


Eigenschaften

  • Die Fehlerordnung der Newton-Cotes-Composite-Verfahren ist jeweils um eine Potenz kleiner als die Fehlerordnung des entsprechenden Newton-Cotes-Verfahren


Composite Mittelpunktregel

Unterteilung des Intervalls [a,b] in m/2 Teilintervalle mit m/2 Stützstellen und darauf Anwendung der Mittelpunktregel

  • m ist die doppelte Anzahl gewünschter Teilintervalle
  • m gerade
  • Fehlerordnung: 2 (quadratisch)
für ein bestimmtes und und

Composite Trapezregel

Unterteilung des Intervalls [a,b] in m Teilintervalle m + 1 Stützstellen und darauf Anwendung der Trapezregel

  • m ist die Anzahl Teilintervalle
  • m gerade oder ungerade
  • Fehlerordnung: 2 (quadratisch)
für ein bestimmtes und und

Composite Simpsonregel

Unterteilung des Intervalls [a,b] in m/2 Teilintervalle mit m/2 + 1 Stützstellen und darauf Anwendung der Trapezregel

  • m ist die doppelte Anzahl gewünschter Teilintervalle
  • m gerade
  • Fehlerordnung: 4 (quartisch)
für ein bestimmtes und und

Romberg-Integration

Die Romberg Integration nutzt die Fehlerentwicklung der Trapezregel zur Genaugikeitssteigerung. Der Fehler der Traperegel lässt sich in eine Potenzreihe in h² entwickeln.

Idee:

  • Mittels einem Newton-Cotes-Composite Verfahren N (normalerweise Composite-Trapezregel) das Integral eines Intervalles mit verschiedenen Schrittweiten h () approximieren
  • Extrapolation von h=0 mittels den erhaltenen Grössen . Extrapolation mittels Aitken-Neville


Algorithmus (Als N wird die Composite-Trapezregel verwendet)

n ist die Anzahl Intervalle, hi die grösse des Teilintervalls.

  1. Berechne die Werte für
    • N ist die Composite Trapezregel mit und
  2. Interpolation
    • Verwende die berechneten grössen als Initialisierungswerte für das Aitken Neville Schema:
    • Verwende als Rekursionformel (-Formel mit Indexverschiebung)


Eigenschaften

  • Konvergenz: quartisch



Algorithmus (Optimiert für rekursive Berechnung)

Diese Art der Berechnung ist absolut identisch zur oberen. (Beim Einsetzen auf das richtige h achten!)


n ist die Anzahl Intervalle, hi die grösse des Teilintervalls.

  1. Berechne wobei:
    • für wobei
  2. Interpolation
    • Verwende die berechneten grössen als Initialisierungswerte für das Aitken Neville Schema:
    • Verwende als Rekursionformel (-Formel mit Indexverschiebung)


Eigenschaften

  • Konvergenz: quartisch
  • Aufwand: Verdopplung bei jedem Halbierungsschritt

Satz über die Existenz und Genauigkeit von interpolatorischen Integrationsformeln

Satz: Genauigkeitsgrad von Integrationsformeln

Der Genauigkeitsgrad einer Integrationsformel mit m Stützstellen ist höchstens 2m - 1

ToDo:
Stimmt das hier unten dran?
Alle momentan zu editierenden Einträge werden hier gesammelt.
  • Aus dem Satz folgt, dass die Newton-Cotes-Formeln nicht optimal sind bezüglich Präzision

Gauss-Integration

  • Die Gauss-Integration wählt die optimalen Stützstellen und Gewichte.
  • Präzision: 2n-1 (n ist die Anzahl Stützstellen)


Bemerkung

  • Man beachte, dass man die zwei folgenden möglichen Verfahren auch kombiniert werden können!


Vorgehen via Gleichungssystem

  • Gesucht: Integrationsformel für eine Funktion f(x) im Intervall [a, b] mit n Stützstellen und Genauigkeitsgrad 2n - 1


Idee:

  • Approximation der Funktion f(x) mit einem Polynom von Grad 2n-1
  • Die Stützstellen und Gewichte sollen so gewählt werden, dass die Monome kleiner gleich dem Grad 2n-1 exakt integriert werden


Algorithmus

  1. Löse das nichtlineare Gleichungssystem auf nach wj und xj
    mit
  2. Normiere das Integral:


Bemerkung

  • Das Gleichungssystem aus Punkt 1 kann man vereinfachen, wenn man die xi via Legendre Polynome berechnet!
  • Lösen von nichtlinearen Gleichungssystemen ist potentiell instabil

Vorgehen via Legendre-Polynome

  • Gesucht: Integrationsformel für eine Funktion f(x) im Intervall [a, b] mit n Stützstellen und Genauigkeitsgrad 2n - 1
  • Die n Stützstellen sind die Nullstellen des orthogonalen Polynom vom Grad n


Algorithmus

  1. Bestimme Nullstellen von wobei das orthogonale Polynom vom Grade n zu einem gegebenen Skalarprodukt ist
  2. Bestimme die Gewichte wobei
  3. Normiere das Integral:

Adaptive Quadratur

  • Zur Verbesserung des Resultates ist es effizienter, nur Intervallbereiche mit grossem Fehler weiter zu halbieren, anstelle stets überall die Intervalle zu halbieren.
  • Mittels einem Abbruchkriterium wird entschieden, ob sich eine weitere Halbierung lohnt.
  • Das adaptive Qudadratur Verfahren kann auf beliebige Integrationsformeln angewendet werden. Es ist somit kein Integrationsverfahren für sich alleine, sondern eine Verbesserungsmöglichkeit bestehender.


Beispiel mit Simpson und Trapez:

ToDo:
Beispiel genauer erarbeiten
Alle momentan zu editierenden Einträge werden hier gesammelt.
ToDo:
Algorithmus pseudocode mässig hinschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Abbruchskriterien


wobei
wobei

Übersicht über die Integrationsverfahren

Verfahren Stützstellen, Gewichte Ziel zu beachten
Newton-Cotes-Formeln Nicht optimale äquidistante Stützstellen, optimale Gewichte zu diesen Stützstellen Nur für kleine Ordnung stabil
Newton-Cotes-Composite-Formeln Nicht optimale äquidistante Stützstellen, optimale Gewichte zu diesen Stützstellen Verbesserung des Resultates durch Anwendung der Newton-Cotes-Formeln auf Teilintervalle anstatt auf das ganze Intervall
Romberg-Integration Nicht optimale äquidistante Stützstellen, optimale Gewichte zu diesen Stützstellen Verbesserung der Konvergenz der Newton-Cotes-Formeln durch Extrapolation
Adaptive-Integration Minimierung des Rechenaufwandes bei gleichzeitigem Verbessern des Ergebnisses
Gauss-Integration Optimale Wahl der Stützstellen, optimale Gewichte zu diesen Stützstellen

Numerisches Lösen von Differentialgleichungen

Differentialgleichungen werden wie folgt unterschieden

  • ODE: Ordinary Differential Equation (Gewöhnliche Differentialgleichungen) Bsp:
    • ODE mit Anfangsbedingungen
    • ODE mit Randbedingung (Randwertprobleme)
  • PDE: Partial Differnetial Equation (Partielle Differentialgleichungen) Bsp:

Definitionen

Diskretisierungsfehler

Definition: Lokale Diskretisierungsfehler

Der lokale Diskretisierungsfehler ist die Differenz des angenäherten Wertes y1 und des richtigen Funktionswertes y(x1)


Definition: Globale Diskretisierungsfehler

Der globale Diskretisierungsfehler ist die Differenz des angenäherten Wertes yn und des richtigen Funktionswertes y(xn) an diesem Punkt (xn = x0 + nh)


Inhärente Stabilität

Man spricht von inhärenter Instabilität, wenn die Instabilität einer Berechnung nicht von der gewählten Berechnungsmethode abhängt, sondern die Instabilität durch die DGL selbst gegeben ist.


Inhärente stabilität abhängig von

  • DGL


Eigenschaften inhärenter Instabilität

  • Näherungswerte für Lösungen entfernen sich üblicherweise exponentiell vom exakten Wert
  • Verlangt nach möglichst hoher Fehlerordnung und Rechengenauigkeit

Steife Differentialgleichung

Die Steifheit S charakterisiert die Anfälligkeit eines Differnentialgleichungssystems auf inhärente Instabilitäten


Definition: Steifheit S

Die Steifheit S eines linearen Differentialgleichungssystems erster Ordnung der Form ist wobei der i-te Eigenwert der Systemmatrix A ist


Definition: Steifheit S

Die Steifheit S eines nichtlinearen Differentialgleichungssystems erster Ordnung mit Gleichungen der Form ist wobei der i-te Eigenwert der (lokalen) Jacobi-Matrix des linearisierten Systems ist


Definition: Steifes DGL-System

Von einem steifen (linearen) DGL-System spricht man, wenn S > 10^3 ist


Eigenschaften steifer Systeme

  • Kann nur integriert werden, wenn
    • sehr kleine Schrittweite h gewählt wird
    • oder man ein Integrationsverfahren verwendet, dessen Gebiet der absoluten Stabilität die ganze linke Halbebene von enthält (-> implizite Verfahren, da kein explizites Verfahren dieses Kriterium erfüllt)

Absolute Stabilität

Man spricht von absoluter Stabilität, wenn für exponentiell abfallenden Lösungen auch die Näherungswerte exponentiell abfallen

ToDo:
Bessere Beschreibung für absolute Stabilität!
Alle momentan zu editierenden Einträge werden hier gesammelt.


Definition: Gebiet absoluter Stabilität

Für ein Einschrittverfahren, welches für die Testaufgabe mit auf eine Vorschrift der Form führt, heisst die Menge Gebiet der absoluten Stabilität


Definition: Absolut stabil

Für ein Einschrittverfahren, welches für die Testaufgabe mit auf eine Vorschrift der Form führt, heisst absolut stabil, wenn das Gebiet der absoluten Stabilität die gesamte linke Halbebene von umfasst


Satz: Stabil

Ein Einschrittverfahren, welches für die Testaufgabe die Form hat, ist stabil, wenn im Gebiet absoluter Stabilität liegt (und ) ist


Absolute Stabilität abhängig von

  • DGL
  • Berechnungsverfahren


Bemerkung

  • Kein explizites Verfahren ist absolut stabil für die linke Halbebene von
ToDo:
Stimmt das mit den expliziten Verfahren?
Alle momentan zu editierenden Einträge werden hier gesammelt.

Stationäre Punkte

ToDo:
Wie gliedern sich stationäre Punkte in das ganze Zeugs von Stabilität und Steifheit ein?
Alle momentan zu editierenden Einträge werden hier gesammelt.
Definition: Stationärer Punkt

Stationäre Punkte p sind Punkte, in denen die Differenzialgleichungen zeitunabhängig sind (=Gleichgewichtszustände). In stationären Punkten gilt also


Definition: Stationärer Punkt lokal stabil

Gegeben ein System vom Differentialgleichungen erster Ordnung mit Gleichungen der Form
Ein stationärer Punkt ist lokal stabil, genau dann wenn alle Eigenwerte der Jacobi-Matrix von f im Punkt p negative Realteile besitzt. Also für die Eigenwerte von gilt

Numerisches Lösen von gewöhnlichen Differentialgleichungen mit Anfangsbedingungen

(=ODE)

Gewöhnliche Differntialgleichungen enthalten nur Ableitungen nach einer einzigen unabhängigen Variablen, z.B x:

ODE werden unterteilt in

  • ODE mit Anfangsbedingungen
    • Bsp: ODE der Form mit Bedingungen und
  • ODE mit Randbedingung (Randwertprobleme)
    • Bsp: ODE der Form mit Bedingungen und


Gewöhnliche Differentialgleichungen höherer Ordnung

Alle expliziten gewöhnlichen Differentialgleichungen n-ter Ordnung lassen sich in ein äquivalentes System mit n Differentialgleichungen 1. Ordnung umformen

Die ODE n-ter Ordnung ist somit äquivalent zum Gleichungssystem

wobei , , ...


Lösen mit globaler Taylorreihen

Idee: Man entwickelt die unbekannte Lösungsfunktion y(x) in x0 in eine Taylorreihe

  • Die dabei benötigten höheren Ableitungen von y(x) ergeben sich aus der verallgemeinerten Kettenregel
ToDo:
Genauer Algorithmus hinschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Eigenschaften

  • Mit höheren Ableitungen werden die Terme zunehmend komplizierter
  • Es werden viele Terme für eine genaue Lösung benötigt

Lösen mit lokaler Taylorreihen

Idee: Anstatt nur für den Anfangspunkt die Taylorreihe zu entwickeln. Entwickelt man an mehreren Stellen

ToDo:
Algorithmus hinschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Euler-Verfahren (explizites)

Idee: Ausgehend von einer Anfangsbedingung (=Anfangspunkt) folgt man dem Richtungsfeld

  1. Das Verfahren wird mit einer Anfangsbedingung initialisiert
  2. Das explizite Euler-Verfahren bestimmt die Steigung im Punkt (xk, yk), geht dann einen Schritt h in Richtung der Tangente (Steigung) und gelangt so an den Punkt (xk+1, yk+1) wobei xk+1 = xk + h
  3. Nun wiederholt sich das Verfahren ab Punkt 2


Algorithmus

  1. Verwende die Anfangsbedingung als Initialisierung: Bsp: Für die Anfangsbedingung y(0) = 1 ist x0 = 0, y0 = 1
  2. Berechne die Näherungen mit der Iterationsvorschrift: wobei


Eigenschaften

  • Fehlerordnung: 1
  • Relativer Fehler:

Heun-Verfahren

Idee: Ausgehend von einer Anfangsbedingung (=Anfangspunkt) folgt man dem Richtungsfeld. Dabei wird jedoch nicht wie beim Euler-Verfahren bloss die Steigung im Anfangspunkt genommen, sondern die gemittelte Steigung aus zwei Punkten

  1. Das Verfahren wird mit einer Anfangsbedingung initialisert
  2. Das Heun-Verfahren bestimmt die Steigung im Punkt (xk, yk) und geht dann einen provisorischen Schritt h in Richtung der Tangente (Steigung ist )
  3. Auf dem so erreichten provisorischen Punkt () wird erneut die Steigung bestimmt (Steigung ist )
  4. Vom Punkt (xk, yk) aus wird nun der endgültige Schritt h in Richtung der gemittelten Steigung gemacht und man gelangt zum Punkt () wobei xk+1 = xk + h
  5. Nun wiederholt sich das Verfahren ab Punkt 2


Algorithmus

  • Es gilt:
  1. Initialisierung: Steigung im Punkt ():
  2. Steigung im Punkt ():
  3. Berechne die Näherungen mit der Iterationsvorschrift:


Eigenschaften

  • Fehlerordnung: 2
  • Relativer Fehler:

Runge-Kutta-Verfahren

  • Verallgemeinerung des Prädiktor-Korrektor-Verahrens, welches dem Euler und Heun-Verfahren zugrunde liegt


Die Runge-Kutta-Verfahren werden unterteilt in Einschrittverfahren und Mehrschrittverfahren:

Einschrittverfahren
Diese verwenden nur die Informationen an einer Stelle xk zur Verechnung der Lösung bei xk+1
Mehrschrittverfahren
Diese verwenden Informationen an mehreren Stellen xk, xk + 1, etc
s-stufiges Runge-Kutta-Verfahren
Ein Verfahren, welches s allgemeine Zwischenschritte macht um den nächsten Schritt zu bestimmen
Question.png

Dem Autor des Lösungsvorschlags stellt sich eine Unklarheit betreffend der Prüfungsfrage oder deren Lösung:
Was ist der Unterschied zwischen "Stufen" und "Schritten"?
Hilf mit, die Qualität dieser Seite zu verbessern, indem du eine eindeutige Lösung einfügst oder auf der Diskussionsseite dieses Themas deine Meinung äusserst.

s-stufiges Runge-Kutta-Verfahren

  • Einschrittverfahren


Definition: s-stufiges Runge-Kutta-Verfahren

Ein s-stufiges Runge-Kutta-Verfahren zeichnet sich durch folgende Punkte aus:

  • Für die spezielle DGL mit Anfangsbedingung sind die s - 1 Zwischenwerte ki sowie der Endwert exakt, also und . Dies führt auf folgende Bedingungen
    • mit
  • Die (lokale) Fehlerordnung ist maximal. D.h. für ein Verfahren der Ordnung p stimmt die Entwicklungen der Näherung in h mit der Entwicklung von y(x + h) in h bis zu den Gliedern der Ordnung p (also h^p) überein.


  • Zur einfachen Schreibweise wird ein Runge-Kutta-Verfahren durch die Butcher-Matrix angegeben
  • Die Koeffizienten a, b und c müssen notwendigerweise die folgenden zwei Bedingungen erfüllen und zusätzlich die Fehlerordnung maximieren
    • mit


Algorithmus

  1. Wähle die Koeffizienten a, b und c so, dass die Bedingungen erfüllt sind und die Fehlerordnung maximiert ist
  2. Schätzung der Steigungungen: mit
  3. Eulerschritt mit gewichteter, gemittelter Steigung:

Butcher-Matrix

Die Butcher-Matrix beschreibt wie die Stützstellen gewählt und die Steigungen gewichtet werden

  • c: Stützstellen
  • a: Gewichte für die Schätzungen
  • b: Gewichte bei der Mittelung
c1 = 0
c2 a2,1
c3 a3,1 a3,2
cs as,1 as,2 as,2 as,s-1
b1 b2 b3 bs-1 bs


Für die Butcher Matrix eines s-stufigen Runge-Kutta-Verfahrens gilt (Siehe s-stufiges-Runge-Kutta-Verfahren)

  • Die Einträge in der ersten Spalte sind gleich den Zeilensummen: mit
  • Die Einträge in der letzten Zeile summieren sich zu eins:


Beispiel Butcher-Matrix für das Heun-Verfahren (s=2)

0
1 1
1

Klassisches Runge-Kutta-Verfahren 4. Ordnung

Ein Beispiel eines Ruge-Kutta-Verfahrens 4. Ordnung ist das folgende:

0
1/2
1/2 0
1 0 0 1
1

Eigenschaften

  • Fehlerordnung: 4

Zusammenhang zwischen Runge-Kutta-Verfahren und Integrationsregeln

Beispiel

  • Wendet man das Heun-Verfahren auf die spezielle Differenzialgleichung an, so erhält man die Trapezregel
  • Wendet man das klassische Runge-Kutta-Verfahren 4. Ordnung auf die spezielle Differenzialgleichung an, so erhält man die einfache Simpsonregel

Schrittweitensteuerung

Ziel: Die Schrittweite dynamisch so wählen, dass der lokale Fehler gleich einer vorgegebenen Toleranz ist


  • Sei die Näherung eines Verfahrens der Ordnung p
  • Sei die Näherung eines Verfahrens der Ordnung q = p + 1


Die Schrittweite lässt sich dann abschätzen als:

Runge-Kutta-Fehlberg-Verfahren

Da bei den Runge-Kutta-Verfahren noch freie Parameter vorhanden sind, ist es möglich, Verfahren kleinerer Ordnung zu erstellen, welche die selben Steigungen wie Verfahren höherer Ordnung verwenden. Das Verfahren kleiner Ordnung wird somit in das Verfahren grösserer Ordnung 'eingebettet'. Man bezeichnet solche Einbettungen als Runge-Kutta-Fehlberg-Verfahren mit Ordnung p und q, was mit RKFp(q) abgekürzt wird.


Dieses Verfahren wird insbesondere bei der Schrittweitensteuerung eingesetzt.

Implizite Lösungsverfahren

Implizite haben gegenüber den expliziten Verfahren den Vorteil, dass sie ein besseres Verhalten bezüglich Stabilität haben. Der Preis dafür ist, dass eine Gleichung gelöst werden muss, was nicht immer gelingen muss.

Implizites Euler-Verfahren

Idee: Ausgehend von einer Anfangsbedingung (=Anfangspunkt) folgt man dem Richtungsfeld

  1. Das Verfahren wird mit einer Anfangsbedingung initialisiert
  2. Das implizite Euler-Verfahren bestimmt die Steigung im Punkt (xk+1, yk+1), geht dann einen Schritt h von (xk,yk) aus in Richtung der Tangente (Steigung) und gelangt so an den Punkt (xk+1, yk+1) wobei xk+1 = xk + h
    • Vergleiche: Das explizite Euler-Verfahren verwendet die Steigung im Punkt (xk+1, yk)
  3. Nun wiederholt sich das Verfahren ab Punkt 2


Bemerkung

  • Zur Berechnung von yk+1 wird die Steigung im Punkt (xk+1, yk+1) benötigt. Folglich lässt sich dieses Verfahren nur anwenden, wenn nach yk+1 aufgelöst werden kann


Algorithmus

  1. wobei nach auflösen
  2. Verwende die Anfangsbedingung als Initialisierung: Bsp: Für die Anfangsbedingung y(0) = 1 ist x0 = 0, y0 = 1
  3. Berechne die Näherungen yk + 1 mit der in 1. gefundenen Iterationsvorschrift


ToDo:
Fragezeichen beantworten
Alle momentan zu editierenden Einträge werden hier gesammelt.

Eigenschaften

  • Fehlerordnung: 1 (????? Gleich wie explizites)
  • Relativer Fehler: (????? Gleich wie explizites?)

Numerisches Lösen von gewöhnlichen Differentialgleichungen mit Randbedingungen

Lösungsmethoden

  • Analytische Methoden für lineare Randwertprobleme
  • Shooting-Methode (Schiessverfahren)
  • Finite-Differenzen-Methode


Eigenschaften

  • Weder die Existenz noch die Eindeutigkeit einer Lösung ist garantiert


Shooting-Methode

ToDo:
Shooting Methode erklären
Alle momentan zu editierenden Einträge werden hier gesammelt.


Finite-Differenzen in einer Variable

ToDo:
Finite-Differenzen erklären
Alle momentan zu editierenden Einträge werden hier gesammelt.


Differenzenquotienten

  • Zentraler Differenzenquotient:


Bemerkung:

  • Vorwärts Differenzenquotient:
    • Schlechtere Näherung als der zentrale Differenzenquotient in Bezug auf Auslöschung
    • Entspricht explizitem Euler-Verfahren


Herleitung

  • Die Finiten-Differenzen können via Taylorreihe hergeleitet werden

Finite-Differenzen Methode (FDM)

Idee: Unterteilung des des Intervalls [a,b] in Teilintervalle und Ersetzen der Ableitungswerte durch finite Differenzen

  1. Diskretisierung der gesuchten Lösungsfunktion
  2. Diskrete Approximation der Differentialgleichung durch finite Differenzen
  3. Berücksichtigung der Randbedingungen
  4. Aufstellen eines (linearen) Gleichungssystems

Numerisches Lösen von partielle Differentialgleichungen

(=PDE)

Partielle Differntialgleichungen enthalten Ableitungen nach verschiedenen unabhängigen Variablen, z.B x und t: was äquivalent zur Schreibweise ist


Lösungsmethoden

  • finite Differenzen (FDM)
  • finite Elemente (FEM) (nicht behandelt in dieser Zusammenfassung)
  • finite Volumina (FVM) (nicht behandelt in dieser Zusammenfassung)
  • Randelement-Methode (REM / engl BEM) (nicht behandelt in dieser Zusammenfassung)


Klassifizierung linearer PDE's 2ter Ordnung

Eine lineare PDF 2. Ordnung der Form mit stückweise stetigen Funktionen A, B, ... H in (x,y) und einer Löungsfunktion heisst:

  • elliptisch, falls
    • Laplace-Gleichung:
    • Poisson-Gleichung
  • hyperbolisch, falls
    • einfache, eindimensionale Wellengleichung:
  • parabolisch, falls
    • einfach, eindimensionale Diffusionsgleichung:

Randbedingungen

Zur eindeutigen Bestimmung der Lösungsfunktion einer elliptischen PDE wird eine Randbedingung benötigt. Man unterscheidet:

  • Dirichlet-Bedingung: (Gegeben ist ein Wert für u(x,y) an der Stelle (x,y))
  • Neumann-Bedingung: (Gegeben ist ein Wert für die Ableitung von u(x,y) an der Stelle (x,y))
  • Cauchy-Bedingung: (Glaub Pauly hat mal gesagt, dies sei eine Kombination von Dirichlet und Neumann??????)

Finite-Differenzen in mehreren Variablen

ToDo:
Beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.


Finite-Differenzen Methode (FDM)

  1. Diskretisierung der gesuchten Lösungsfunktion
    • z.B durch das Einheitsquadrat
  2. Diskrete Approximation der Differentialgleichung durch finite Differenzen
  3. Berücksichtigung der Randbedingungen
  4. Aufstellen eines (linearen) Gleichungssystems

Variationsrechnung

ToDo:
Genauer ausarbeiten
Alle momentan zu editierenden Einträge werden hier gesammelt.


Satz: Euler-Lagrange Gleichung

Eine Funktion y(x), die ein Extremum des Funktionals beschreibt, muss die DGL 2. Ordnung erfüllen

Links

Programming in Maple: The Basics

Maple Tutorial