Numerik
Prüfungsvorbereitung
Prüfungsvorbereitung
Was ist eine Kontraktion?
wenn die Lipschitz-Konstante q < 1 ist
Wie groß ist der Aufwand zur Bestimmung der Koeffizienten bei Lagrange-Polynomen?
keiner bzw O(1), da die y-Werte der Stützstellen direkt als Koeffizienten verwendet wwerden können
Wie kann die Extrapolation ohne explizite Berechnung des Interpolationspolynoms durchgeführt werden?
mit dem Neville-Schema
Welche Basispolynome ergeben sich für das Gewicht w(x):
die Tschebyscheff-Polynome
Was ist die summierte Trapenzregel?
Was gilt für die Fehlerabschätzung?
n=3
Trapezregel wird für jedes Intervall angewendet --> kleinerer Fehler
z.B. 4 Stützstellen, 3 Intervalle!
Was ist die maximal erreichbare Ordnung der Gauß-Quadraturformel?
Die Quadraturordnung hängt von der Wahl der Stützstellen ab. Für spezielle Wahl der xi ist bei n+1 Stützstellen die maximal erreichbare Ordnung der Quadraturformel 2n + 2, es geht nicht besser! --> Durch Gauß-Quadratur lassen sich Polynome vom Grad 2n+1 exakt integrieren.
Die xi sind dann gerade die Nullstellen des Orthogonalpolynoms p(x) vom Grad n+1 bzgl des betrachteten Skalarprodukts
Welche Polynome ergeben sich für Gewichtsfunktion w(x) > 0?
- allgemeines w(x) > 0:
Konstruiere Orthogonalpolynom p bzg. (•,•)w durch orthogonalisieren der Monombasis - w(x) = 1 --> Legendre-Polynome
- w(x) = 1/sqrt(1+x2) --> Tschebycheff-Polynome
Wie viele Stützstellen benötigt man um mit Gauß-Quadratur ein Polynom p € P4 exakt integrieren zu können?
Wie viele Nullstellen hat das Orthogonalpolynom?
p € P4 = P2n+1 ----> 4 = 2n + 1 ---> n = 2
benötigte Stützstellen: n+1 = 3
Die Anzahl der Nullstellen von port € P3 = Pn+1 ist gleich der Anzahl der benötigten Stützstellen
Welchen Grad haben die Tschebycheff-Polynome für eine Quadraturformel die Polynome der Ordnung p € P3 exakt bestimmt?
p € P3 = P2n+1 --> 3 = 2n +1 --> n = 1
T = port € Pn+1 --> T ist von Grad 2
Was gilt für quadratische Matrizen?
- m=n
- Ax = b ist für jedes b eindeutig lösbar
- Rang(A) = n
- det(A) =/= 0 --> A ist regulär
- inv(A) ist regulär, transp(A) ist regulär
- alle Eigenwerte von A =/= 0
Was für direkte Verfahren zur Lösung LGS gibt es?
Was für iterative Verfahren zur Lösung LGS gibt es?
direkt (exakt): Cholesky, QR, LR
iterativ: Newton (Approximative Lösung von x)
Was ist a posterori/ a priori Fehlerabschätzung?
- a priori: vor Berechnung, hängt also nicht von berechneten Daten ab
- a posterori: Fehlerabbhängigkeit von Approximation
Was ist der Rechenaufwand für eine LR-Zerlegung?
durch Gauß-Elimination
j = 1, ... , n-1
- Einträge in L: (n-j) Divisionen
- Einträge in R: (n-j)2 Multiplikationen
--> 1/3 n3 + O(n2)
Was ist der Rechenaufwand einer Gauß-Elimination
~ Aufwand LR
1/3 n3 + O(n2)
Was versteht man unter einer LR-Zerlegung?
PA = LR wobei P eine Permutationsmatrix ist.
Falls P = I ist die Zerlegung von A eindeutig bestimmt
Sei A € Rn x n regulär und diagonal-dominant: Dann existiert eine Zerlegung A = LR die mit Gaußscher Elimination ohne Pivotierung bestimmt werden kann.
Wann heißt eine Matrixnorm ||•|| natürlich, wann verträglich mit einer Vektornorm?
- natürlich = induzierte Matrixnorm: A = max ( ||Ax|| / ||x||)
- verträglich wenn: ||Ax|| <= ||A|| ||x||
Wann ist eine (symmetrische) Matrix positiv definit?
Falls alle (reellen) Eigenwerte von A positiv sind
--> alle Diagonalelemente von A positiv
--> das betragsmäßig größte Elemente steht auf der Diagonalen
Wann ist eine Matrix diagonal-dominant?
falls < dann strikt-diagonal-dominant
Was ist eine Cholesky-Zerlegung?
A = LR = L D LT = L' L'T
- L'11 = sqrt( a11)
- L'j1 = aj1 / sqrt( a11) mit j = 2, ... n
Banachscher Fixpunktsatz
Eine Kontraktion eines (nichtleeren) vollständigen metrischen Raumes besitzt genau einen Fixpunkt, also einen Punkt mit .
Was versteht man unter einem direkten, approximativen oder iterativen Verfahren?
- direkt: falls die Lösung bis auf Rundungsfehler exakt berechnet werden kann
- approximativ: falls die Lösung nur angenähert werden kann
- iterativ: falls die Näherung durch mehrfache Ausführung des Verfahrens verbessert werden kann
Was versteht man unter dem Begriff numerischer Aufwand?
Anzahl der notwendigen Operationen
(Eine elementare Operation ist eine Multiplikation und Addition.)
Numerische Aufwand für Horner-Schema
A(n) = 2n
Wie sind die Landau-Symbole definiert?
Sei g eine Funktion mit g --> (inf) für n --> (inf)
- f € O(g) gdw limsup | f(h)/g(h) | < (inf) mit n --> (inf)
f wächst nicht wesentlich schneller als f
- f € o(g) gdw lim | f(h)/g(h) | = 0 mit n --> (inf)
f wächst langsamer als g
Wie werden Gleitkommazahlen in der Regel dargestellt?
- Basis b € N
- Exponent e € N_0
- Mantisse m € R
Diese Darstellung ist nicht eindeutig --> normierte Fließkommazahl-Darstellung mit m1 =/= 0 für x =/= 0
Wie viel Byte werden zur Abspeicherung eines Polynoms p € Pn in doppelter Genauigkeit benötigt?
- Für doppelt genaue Zahlen: (einfache Genauigkeit 32 Bit)
64 bit = 1 Vorzeichen + 11 Exponent + (52+1) Mantisse - Polynome werden durch die Koeffizienten eindeutig festgelegt: 8 • (n +1) Bytes
Was versteht man unter Auslöschung? Wann tritt diese auf?
Verlust an Genauigkeit bei Subtraktion fast gleich großer Gleitkommazahlen
Was versteht man unter absoluten und relativen Fehler?
x: exakter Wert, x* Näherungswert von x
- absoluter Fehler: Dx = |x* - x|
- relativer Fehler: dx = |Dx| / |x|
Was versteht man unter Kondition eines Problems?
Kondition beschreibt man die Abhängigkeit der Lösung eines Problems von der Störung der Eingangsdaten.
Wann ist ein Problem schlecht konditioniert?
- eine kleine Störung der Eingangsdaten hat große (gravierende) Änderungen der Ergebnisse zur Folge
- | k(x) | >> 1
k(x) sind Konditionszahlen, also der Faktor, um den der Eingangsfehler im ungünstigen Fall verstärkt wird:
Multikplikation ist immer gut konditioniert
Wann Fehlerdämpfung?
Wie berechnet man Konditionszahlen?
k = | (f' / f) * x |
Unterschied Stabilität und Kondition
- Kondition ist die Eigenschaft des Problems
- Stabilität ist die Eigenschaft des Algorithmus (durch Implementierung, Fließkommazahldarstellung)
Man sollte lieber den stabileren Algorithmus wählen, auch wenn der Rechenaufwand größer ist...
Was versteht man unter Interpolation?
zu diskreten Daten soll eine stetige Funktion gefunden werden, die diese Daten abbildet.
--> Polynom finden, das die Interpolationsbedinung erfüllt
Unterschied Approximation und Interpolation
- Interpolation: Zuordnung eines Elements g€P zur Funktion F durch Fixieren von Funktionswerten (n+1 Stützstellen)
- Approximation: g€P ist als "beste" Dartellung von f zu bestimmen (Gauß-Approximation)
z.B. max | f(x) - g(x) | soll minimal werden für g (Stützstellen müssen nicht zwingend berührt werden)
Formuliere die Lagrange Interpolationsaufgabe
Lagrange Interpolationsaufgabe besteht darin, zu n + 1 paarweise verschiedenen Stützstellen x0, .. xn €R und gegebenen Knotenwerten y0, .. yn €R ein Polynom p € Pn zu bestimmen mit der Eigenschaft:
p(xi) = yi , i = 0, .... n
Die Lagrange Interpolationsaufgabe ist eindeutig lösbar
Wie viele Stützstellen benötigt man, um die Lagrange-Interpolationsaufgabe eindeutig zu lösen?
Gibt es auch Fälle in denen man mit weniger Sützstellen auskommt?
n + 1
Wenn alle Punkt auf einer Linie liegen, reichen 2 Sützstellen?
Monom-, Lagrange-, Newton-Darstellung eines Polynoms p € P
y[x0, ..., xi] bezeichnen die zu den Punkten (xi, yi) gehörenden dividierten Differenzen
- Monom: O(n) (Horner)
- Newton: O(n) (Horner)
- Lagrange: O(n2)
Was ist das Neville-Schema?
Welchen Vorteil bietet es im Vergleich zu den voher genannten Darstellungen?
Mit dem Neville-Schema kann die Auswertung von P rekursiv erfolgen:
- direkt auswertbar
- erweiterbar, Hinzunahme einer weiteren Stützstelle ist problemlos
- numerisch stabil
Gut geeignet, wenn ein Interpolationspolynom nur an ganz wenigen Stellen ausgewertet werden soll, dabei ist der Algorithmus weniger anfällig gegen Auslöschung.
(Bei Newton Algorithmus für Auswertung an vielen Stellen, aber Gefahr der Auslöschung bei Bestimmung der dividierten Differenzen, wenn die Stützstellen zu nahe beieinander liegen)
Was besagt die Fehlerabschätzung für den Interpolationsfehler?
p € Pn Interpolationspolynom zu f € Cn+1[a,b] in den n+1 paarweise verschiedenen Stützstellen
-
- 1 / 86
-
Flashcards
Was versteht man unter einem direkten, approximativen oder iterativen Verfahren?
- direkt: falls die Lösung bis auf Rundungsfehler exakt berechnet werden kann
- approximativ: falls die Lösung nur angenähert werden kann
- iterativ: falls die Näherung durch mehrfache Ausführung des Verfahrens verbessert werden kann
Was versteht man unter dem Begriff numerischer Aufwand?
Anzahl der notwendigen Operationen
(Eine elementare Operation ist eine Multiplikation und Addition.)
Numerische Aufwand für Horner-Schema
A(n) = 2n
Wie sind die Landau-Symbole definiert?
Sei g eine Funktion mit g --> (inf) für n --> (inf)
- f € O(g) gdw limsup | f(h)/g(h) | < (inf) mit n --> (inf)
f wächst nicht wesentlich schneller als f
- f € o(g) gdw lim | f(h)/g(h) | = 0 mit n --> (inf)
f wächst langsamer als g
Wie werden Gleitkommazahlen in der Regel dargestellt?
- Basis b € N
- Exponent e € N_0
- Mantisse m € R
Diese Darstellung ist nicht eindeutig --> normierte Fließkommazahl-Darstellung mit m1 =/= 0 für x =/= 0
Wie viel Byte werden zur Abspeicherung eines Polynoms p € Pn in doppelter Genauigkeit benötigt?
- Für doppelt genaue Zahlen: (einfache Genauigkeit 32 Bit)
64 bit = 1 Vorzeichen + 11 Exponent + (52+1) Mantisse - Polynome werden durch die Koeffizienten eindeutig festgelegt: 8 • (n +1) Bytes
Was versteht man unter Auslöschung? Wann tritt diese auf?
Verlust an Genauigkeit bei Subtraktion fast gleich großer Gleitkommazahlen
Was versteht man unter absoluten und relativen Fehler?
x: exakter Wert, x* Näherungswert von x
- absoluter Fehler: Dx = |x* - x|
- relativer Fehler: dx = |Dx| / |x|
Was versteht man unter Kondition eines Problems?
Kondition beschreibt man die Abhängigkeit der Lösung eines Problems von der Störung der Eingangsdaten.
Wann ist ein Problem schlecht konditioniert?
- eine kleine Störung der Eingangsdaten hat große (gravierende) Änderungen der Ergebnisse zur Folge
- | k(x) | >> 1
k(x) sind Konditionszahlen, also der Faktor, um den der Eingangsfehler im ungünstigen Fall verstärkt wird:
Multikplikation ist immer gut konditioniert
Wann Fehlerdämpfung?
Wie berechnet man Konditionszahlen?
k = | (f' / f) * x |
Unterschied Stabilität und Kondition
- Kondition ist die Eigenschaft des Problems
- Stabilität ist die Eigenschaft des Algorithmus (durch Implementierung, Fließkommazahldarstellung)
Man sollte lieber den stabileren Algorithmus wählen, auch wenn der Rechenaufwand größer ist...
Was versteht man unter Interpolation?
zu diskreten Daten soll eine stetige Funktion gefunden werden, die diese Daten abbildet.
--> Polynom finden, das die Interpolationsbedinung erfüllt
Unterschied Approximation und Interpolation
- Interpolation: Zuordnung eines Elements g€P zur Funktion F durch Fixieren von Funktionswerten (n+1 Stützstellen)
- Approximation: g€P ist als "beste" Dartellung von f zu bestimmen (Gauß-Approximation)
z.B. max | f(x) - g(x) | soll minimal werden für g (Stützstellen müssen nicht zwingend berührt werden)
Formuliere die Lagrange Interpolationsaufgabe
Lagrange Interpolationsaufgabe besteht darin, zu n + 1 paarweise verschiedenen Stützstellen x0, .. xn €R und gegebenen Knotenwerten y0, .. yn €R ein Polynom p € Pn zu bestimmen mit der Eigenschaft:
p(xi) = yi , i = 0, .... n
Die Lagrange Interpolationsaufgabe ist eindeutig lösbar
Wie viele Stützstellen benötigt man, um die Lagrange-Interpolationsaufgabe eindeutig zu lösen?
Gibt es auch Fälle in denen man mit weniger Sützstellen auskommt?
n + 1
Wenn alle Punkt auf einer Linie liegen, reichen 2 Sützstellen?
Monom-, Lagrange-, Newton-Darstellung eines Polynoms p € P
y[x0, ..., xi] bezeichnen die zu den Punkten (xi, yi) gehörenden dividierten Differenzen
- Monom: O(n) (Horner)
- Newton: O(n) (Horner)
- Lagrange: O(n2)
Was ist das Neville-Schema?
Welchen Vorteil bietet es im Vergleich zu den voher genannten Darstellungen?
Mit dem Neville-Schema kann die Auswertung von P rekursiv erfolgen:
- direkt auswertbar
- erweiterbar, Hinzunahme einer weiteren Stützstelle ist problemlos
- numerisch stabil
Gut geeignet, wenn ein Interpolationspolynom nur an ganz wenigen Stellen ausgewertet werden soll, dabei ist der Algorithmus weniger anfällig gegen Auslöschung.
(Bei Newton Algorithmus für Auswertung an vielen Stellen, aber Gefahr der Auslöschung bei Bestimmung der dividierten Differenzen, wenn die Stützstellen zu nahe beieinander liegen)
Was besagt die Fehlerabschätzung für den Interpolationsfehler?
p € Pn Interpolationspolynom zu f € Cn+1[a,b] in den n+1 paarweise verschiedenen Stützstellen
An welchen Stellen verschwindet der Interpolationsfehler und warum?
Wenn x ein Knoten (Stützstelle) ist, so ist der Interpolationsfehler Null
da das Produkt (x - x_i) Null wird
Wie verhält sich das Interpolationspolynom gegenüber lokalen Störungen in einer Stütztstelle xi d.h wie wirkt sich ein Fehler eps im zugehörige Funktionswerten aus, wenn also anstatt (xi, yi) der Punkt (xi, yi + eps) für ein i interpoliert wird?
Lagrange-Interpolation: Störung hat Auswirkung auf alle Lagrange-Poylsnome insbesondere auf das gesamte Interpolationsintervall
Unter welchen Voraussetzungen folgt gleichmäßige Konvergenz des Interpolationspolynoms gegen die Funktion f(x)?
Sind Ableitungen von f beschränkt auf [a,b] so gilt:
max | f(x) - p(x) | ----> 0 für n ----> 0
Meist haben die Ableitungen der zu interpolierenden Funktionen jedoch ein zu starkes Wachstum für n ---> inf so dass gleichmäßige Konvergenz des Approximationsprozesses nicht mehr zu erwarten ist
Gegenbeispiel: 1(1+x2) --> Ableitungen sind nicht beschränkt
Was ist der Unterschied zwischen der Hermite- und Lagrange-Interolationsaufgabe?
Wie gehen die Stützstellen in die Interpolationsfehlerabschätzung?
Die Aufgabenstellung der Lagrange-Interpolation lässt sich verallgemeinern zur Hermite-Interpolation
Lagrange:
- paarweise verschiedene Stützstellen
- die Basisfunktion ist von den Stützstellen unabhängig, dadurch kann man bei bekannter Basisfunktion verschiedene Sätze von Stützwerten schnell interpolieren.
- Nachteil: bei Hinzunahme einer Stützstelle alle Basisvektoren neu berechnet werden müssen
Hermite:
- berücksichtigt zusätzlich zu den Stützstellen auch die Ableitung der zu interpolierenden Funktion
- einzelnen GItterknoten sind mehrfach zugelassen (Vielfachheit wegen Ableitung)
Prinzip der Extrapolation zum Limes (Richardsonsche Extrapolation) ?
Ein numerischer Prozess liefert für jeden Wert eines Parameters h einen Wert a(h)
- gesucht: die nicht direkt berechenbare Größe: a(0) = lim a(h)
- zur Annäherung von a(0) berechnet man a(hi) für gewisse Werte hi und nimmt den Wert p(0) des zugehörigen Interpolationspolynoms als Schätzung von a(0)
Beispiel: Differenzenquotient ist nicht stabil
Trigonometrisches Interolationspolysnoms (komlex)
Zu gegebenen Zahlen y0, ... , yn € C gibt es genau eine FUnktion der Gestalt, welche den Interpolationsbesdinungen genügt
Diskrete Fourier-Analyse
Ziel: Interpolations periodischer Funktionen
cos(kx) und sin(kx) ~ Grundschwingungsdormen eines 2pi-periodischen Prozesses und duch die DFT werden die Anteile ak, bk dieser Grundschwingungen am Prozess bestimmt
Rechenaufwand O(n2)
Den n+1 Werten yj= f(xj) einer Funktion f:[0,2pi]-->R werden die n+1 Koeffizienten ak, bk des trigonometrischen Interpolationspolynoms zugeordnet. Die Abbildung {yj} --> {ak, bk} heißt DFT uns ist umkehrbar.
Wie kann man aus der komplexen Darstellung des trigonometrischen Interpolationspolynoms im Falle reeller Werte yi € R die Koeffizienten des zugehörigen rellen Interpolationspolynoms (DFT) bestimmen?
Es gilt: ??
- tn*(xj) = tn(xj) = yj
Prinzip der FFT (Fast Fourier Transformation)
- Effiziente Berechnung des trigonometrischen Interolationspolynom: Rechenaufwand O(n log(n))
- Das FFT-Verfahren arbeitet am besten für n = 2q (Anzahl der Sützstellen sind eine Zweierpotenz)
- Idee: die Berechnung einer DFT der Größe 2n wird in zwei Berechnungen der DFT der Größe n audgeteilt: in Vektor mit geraden/ungeraden Indizies
--> beide Teilergebnisse nach der Transformationzu einer Fouriertransformation der Größe 2n zusammengefügt - Vorteil: zur Berechnung einer DFT der halben Länge benötigt man nur ein Viertel des Rechenaufwands (Vorschrift ist merhmals anwendbar)
Welche geometrische Eigenschaft erfüllt die Bestapproximation g € S von f?
|| f - g|| = min || f - phi ||
Ein g € S mit dieser Eigenschaft heißt dann Bestapproximation von g (in S bzgl ||•|| )
geometrisch: f-g wird minimal wenn orthogonal: (f - g, phi) = 0 für alle phi € S (Orthogonalitätsbedingung)
Wie lautet die Höldersche Ungleichung?
| (f,g) | <= ||f|| ||g||
Wo sind Normen äquvalent?
Welche Norm wird bei der Gauß-Approximation verwendet?
das quadratische Mittel
Was besagt die allgemeine Gauß-Approximation?
Seien H ein unitärer (orthogonal A*A = 1 mit A ist transponiert und komplex konjugiert) Raum und S c H ein endlich dimensionale Teilraum. Dann existiert zu jedem f € H eine eindeutig bestimmte beste Approximation g € S:
|| f - g|| = min || f - phi ||
Wie kann die Bestapproximation g € S explizit über ein Gleichungsystem berechnet werden, d.h. wie wird dieses Gleichungssystem aufgestellt?
Besonders einfach wenn die Basis {Psi} ei Orthonormalsystem ist, (Psik, Psii ) = deltaki --> alphak = (f, Psik)
- g : beste Appoximation
- Funktion f € H
- Gleichungssystem Summe (Psik, Psii ) alphak = (f, Psii )
Warum nutzt man zur Berechnung der Best-Approximation g bzgl. der L2 - Norm nicht die Monom-Basis?
Monome (1, t, ..., tn)
Welche Basispolynome nutzt man stattdessen?
Man erhält bei Grauß Approximation als Gramsche Matrix die sogenannte Hilbert-Matrix, die für größere Werte von n schlecht konditioniert ist
--> mit einer orthogonalen Basis erhält man Legendre-Polynome (nicht normalisiert)
--> man erhät eine Diagonalmatrix, die im Falle normierter Legendre-Polynome die Einheitsmatrix ergibt
(Normiert bzgl Skalarprodukt (-1,1))
Was ist die Gramsche Matrix?
Koeffizientenmatrix G(Psi), die symmetrisch und unitär ist.
Sie entsteht bei der Berechnung der Best-Approximation (f, Psi)
Für Monome als Basis erhält man für die Gramsche Matrix die HIlbert-Matrix, die für größere Werte von n schlecht konditioniert ist
Was ist der Gram-Schmidt-Algorithmus?
Er erzeugt zu jedem System linear unabhängiger Vektoren ein Orthogonalsystem
Was sind Tschebyscheff-Polynome?
Durch Orthogonaliserung der natürlichen Monombasbs bzgl des gewichteten Skalarprodukts mit dem Gram-Schmidt-Algorithmus ergeben sich die Tschebyscheff-Polynome
- k gerade : gerader Exponent
- k ungerade: ungerader Exponent
Was ist die Hilbert-Matrix?
quadratisch, symmetrisch, positiv definit und regulär, aber Invertierung extrem schlecht konditioniert und für große n unmöglich
