Numerik

wenn die Lipschitz-Konstante q < 1 ist

keiner bzw O(1), da die y-Werte der Stützstellen direkt als Koeffizienten verwendet wwerden können

mit dem Neville-Schema

die Tschebyscheff-Polynome

n=3

Trapezregel wird für jedes Intervall angewendet --> kleinerer Fehler

z.B. 4 Stützstellen, 3 Intervalle!

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

• allgemeines w(x) > 0:
  Konstruiere Orthogonalpolynom p bzg. (•,•)_w durch orthogonalisieren der Monombasis
• w(x) = 1 --> Legendre-Polynome
• w(x) = 1/sqrt(1+x²)  -->  Tschebycheff-Polynome

p € P⁴ = P²ⁿ⁺¹  ----> 4 = 2n + 1 ---> n = 2

benötigte Stützstellen: n+1  = 3

Die Anzahl der Nullstellen von p^ort € P³ = Pⁿ⁺¹  ist gleich der Anzahl der benötigten Stützstellen

p € P³ =  P²ⁿ⁺¹   -->  3 = 2n +1  --> n = 1

T = p^ort  € Pⁿ⁺¹   --> T ist von Grad 2

• 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

direkt (exakt):  Cholesky, QR, LR

iterativ: Newton  (Approximative Lösung von x)

• a priori: vor Berechnung, hängt also nicht von berechneten Daten ab
• a posterori: Fehlerabbhängigkeit von Approximation

durch Gauß-Elimination
j = 1, ... , n-1

• Einträge in L:  (n-j) Divisionen
• Einträge in R: (n-j)² Multiplikationen

--> 1/3 n³ + O(n²)

~ Aufwand LR

1/3 n³ + O(n²)

PA = LR wobei P  eine Permutationsmatrix ist.

Falls P = I ist die Zerlegung von A eindeutig bestimmt

Sei A € R^{n x n} regulär und diagonal-dominant: Dann existiert eine Zerlegung A = LR die mit Gaußscher Elimination ohne Pivotierung bestimmt werden kann.

• natürlich = induzierte Matrixnorm: A = max ( ||Ax|| / ||x||)
• verträglich wenn: ||Ax|| <= ||A|| ||x||

Falls alle (reellen) Eigenwerte von A positiv sind

--> alle Diagonalelemente von A positiv
--> das betragsmäßig größte Elemente steht auf der Diagonalen
 

falls <  dann strikt-diagonal-dominant

A = LR = L D L^T = L' L'^T

• L'₁₁ = sqrt( a₁₁) 
• L'_j1 = a_j1 / sqrt( a₁₁) mit j = 2, ... n

Eine Kontraktion eines (nichtleeren) vollständigen metrischen Raumes besitzt genau einen Fixpunkt, also einen Punkt mit .

Anzahl der notwendigen Operationen

(Eine elementare Operation ist eine Multiplikation und Addition.)

A(n) = 2n

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

• Basis b € N 
• Exponent e € N_0
• Mantisse m € R

Diese Darstellung ist nicht eindeutig --> normierte Fließkommazahl-Darstellung mit m₁ =/= 0  für x =/= 0

• 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

Verlust an Genauigkeit bei Subtraktion fast gleich großer Gleitkommazahlen

x: exakter Wert, x* Näherungswert von x

• absoluter Fehler: Dx =  |x* - x|
• relativer Fehler: dx = |Dx| / |x|

Kondition beschreibt man die Abhängigkeit der Lösung eines Problems von der Störung der Eingangsdaten.

• 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

k = | (f' / f) * x  |

• 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...

zu diskreten Daten soll eine stetige Funktion gefunden werden, die diese Daten abbildet.

--> Polynom finden, das die Interpolationsbedinung erfüllt

• 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)

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(x_i) = y_i     ,    i = 0, .... n

Die Lagrange Interpolationsaufgabe ist eindeutig lösbar

n + 1

Wenn alle Punkt auf einer Linie liegen, reichen 2 Sützstellen?

y[x0, ..., xi] bezeichnen die zu den Punkten (xi, yi) gehörenden dividierten Differenzen

• Monom: O(n) (Horner)
• Newton: O(n) (Horner)
• Lagrange: O(n²)

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)

p € Pⁿ Interpolationspolynom zu f € Cⁿ⁺¹[a,b]   in den  n+1 paarweise verschiedenen Stützstellen