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
-
Lernkarten
Welche Norm wird bei der Tschebyscheff-Approximation verwendet?
die Maximumsnorm
Vorteil: größte Abweichung soll kleiner werden, immer im Mittel jedoch größer als L2-Norm (Gauss)
Was sind die Newton-Cotes-Formeln?
Wie sind die Stützstellen verteilt?
Die Stützstellen sind äquidistant verteilt
- abgeschlossene NCF: (a,b sind Stützstellen)
xi = a + iH, H = (b-a)/n - offene NCF: (a,b sind keine Stützstellen)
xi = a + (i+1)H, H = (b-a)/n
Was sind Quadratur-Formeln?
zur näherungsweisen Berechnung bestimmter Integrale
Eine Quadraturformel In wird mindestens von der Ordnung m genannt, wenn durch sie wenigstens alle Polynome aus Pm-1 exakt integriert werden
Was ist die Trapenzregel?
Welche Fehlerabschätzung gilt?
abgeschlossene Newton-Cotes-Formel:
Was ist die Simpsonregel?
abgeschlossene NCF
Was ist die Mittelpunktregel?
offene Newton-Cotes-Formel
Polynome bis zu welcher Ordnung werden bei n+1 verschiedener Stützstellen von der Newton-Cotes-Formeln exakt integriert?
allgemeine Ordnung zu n+1 verschiedenen Stützstellen: Quadraturformel I(p) von Ordnung n+1 --> Polynome p € Pn
falls n gerade: I(p) von Ordnung n+2 und p € Pn+1 weil Polynome mit ungeradem Exponent punktsymmetrisch zum Ursprung sind.
Wie lassen sich die Gewichte der Newton-Cotes-Formeln berechnen?
- bei Trapez (n=1): alpha0 = alpha1 = H/2 mit H=(b-a)/n
- bei Simpson (n=2): alpha0 = alpha2 = H/3, alpha1 = 4H/3
Wie viele Stützstellen benötigt, damit ein Interpolationspolynom von Grad n Polynome der Ordnung 2n +2 exakt integriert?
n+1
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! p € P2n+1
Die xi sind dann gerade die Nullstellen des Orthogonalpolynoms port(x) vom Grad n+1 bzgl des betrachteten Skalarprodukts.
Was ist das Romberg-Integrationsverfahren?
Welches schon bekannte Prinzip taucht wieder auf?
Idee: Extrapolation der Trapezregel. Es wird ausgenutzt, dass sich der Fehler für die Trapezregel T(h) in eine Potenzreihe in h2 (statt nur h) entwickeln lässt --> es ist eine Extrapolation in Quadraten der Schrittweite möglich, die deutlich schneller konvergiert als die einfache Extrapolation zum Limes. (Schrittweite = Breite der Trapeze)
Prinzip der Extrapolation zum Limes (Richardson Extrapolation)
Während der Durchführung einer Gauß-Elimation ist ein Diagonalelement fast Null, welche Probleme ergeben sich hieraus?
Wie löst man das Problem in der Praxis?
A ist fast singulär (nicht invertierbar) --> LR Zerlegung ist instabil
Das Problem lässt sich durch Pivotisierung und Zeilenäquilibrierung stabilisieren
3 wichtigsten Vektornormen?
- Maximumsnorm = maximale Zeilensumme
- l1-Norm = maximale Spaltensumme
- euklidische Norm = Spektralnorm, wobei max ( |EW| )0,5 für hermitesche Matrizen einfach nur max ( |EW| )
Was heißt hermitesch?
selbstadjungiert, A stimmt mit der transponierten und komplex konjugierten Matrix überein
Wie erhält man bei einer Gauß-Elimination automatisch eine LR-Zerlegung?
(Die L Matrix wird in den freien Plätzen der R Matrix gespeichert)
Man muss beim "auf die Stufenform bringen" bestimmte Regeln befolgen:
- am besten keine Zeilen vertauschen, sonst PA = LR
- von der 2.Zeile , mit dem zu elimnierenden Betrag, wird die 1.Zeile mit passend multiplizierten Faktor abgezogen, sodass eine Null entsteht
R ist dann die Matrix in Stufenform (obere Dreiecksmatrix)
L sind die multiplizierten Faktoren, bei der Gauß-Elimination (1.Schritt in 1. Spalte, auf Diagonalen mit 1 auffüllen)
In welcher Situation ist die Durchführung einer LR-Zerlegung von A einer Gauß-Eliminationdes LGS Ax=b vorzuziehen?
wenn man das Lösen eines quadratischen, eindeutig lösbaren LGS als Computerprogramm umsetzen will
gleicher Rechenaufwand, aber in der Praxis tritt häufig der Fall auf, dass sich die Rechte Seite b ändert, während die Matrix unverändert bleibt --> auch L und R bleiben auch bei sich ändernden b gleich
Was ist Pivotisierung?
- Gaußsche Elimination erfordert oft Zeilenvertauschung, da z.B. das Pivotelement (a11) ungleich 0 sein muss.
- Am geschicktesten wählt man eine 1, bei Berechnung mit dem Computer am sinnvollsten as betragsgrößte Element, um einen möglichst stabilen Algrotihmuss zu erhalten (Totalpivotisierung)
Pivotisierung ist ohne nennenswerten Zusatzaufwand durchführbar, wenn die Vertauschungen in einem Indexvektor gespeichert werden.
Was besagt der Sörungssatz für lineare Gleichungssysteme?
Störungssatz gilt nur für Näherung: dA < ( || A-1 || )-1
Matrix A sei regulär
--> gestörte Matrix ist ebenfalls regulär A' = A + dA
Ist die Kondition der Matrix groß, so ist auch der Fehler in der Lösung groß!
Wie ist allgemein die Kondition einer Matrix definiert?
Ist A symmetrisch und positiv definit (s.p.d bzw. hermitesch), dann gilt
Meistens verwendet man die Maximumsnorm (oder die euklidische Norm)
Wann werden Fehler in den Eingansdaten enorm verstärkt? (bei LGS)
Kondition cond(A) ist der Verstärkungsfaktor
Je größer cond(A) desto schlechter konditioniert ist das Problem.
Ist das Gram-Schmidt-Verfahren wegen Rundungsfehler ...
Was ist die QR-Zerlegung?
Die Zerlegung A = Q • R ist eindeutig für eine rechteckige Matrix A € Km x n mit m >= n und Rang(A) = n
- Q = orthogonale (bzw unitäre für m=n) Matrix
- R = obere Dreiecksmatrix
Es gibt verschiedene Algorithmen z.B. Housholder-Verfahren, Gram-Schmidt-Verfahren
Welchen Vorteil hat das Newton-Verfahren gegenüber direkten Verfahren wie z.B. der LR-Zerlegung bzgl der Anwendbarkeit?
- gilt auch für nichtlineare Gleichungen
- konvergiert lokal quadratisch (d.h. Startwert muss nahe an Lösung sein)
Was ist das Newton-Verfahren?
zum Lösen nichtlinearer Probleme
iterativ:
Wie ist die Konvergenzordnung definiert?
~ Konvergenzgeschwindigkeit
- superlineare Konvergenz: c --> 0
(für steigende Interationen immer schneller gegen Lösung) - lineare Konvergenz: c = konstant
Was ist ein Fixpunkt?
Ein Fixpunkt erfüllt die Gleichung f(xi) = xi
Was für zwei Typen von Fixpunkten gibt es?
- stabil | f'(x) | < 1 (Im Schnittpunkt)
- instabil | f'(x) | > 1
Anschaulich: Man kann die Funktion auf den Punkt selbst anwenden, ohne ihn zu verändern, wobei eine Störung wenig bzw. viel ändert, indem sie zum Fixpunkt hinführt bzw. wegführt
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)
