Zusammenfassung Numerik PDF

Preview

Summary

Zusammenfassung Numerik...

Description

Numerik Prof. A. Prohl Zusammenfassung: Cornelia Schulz

SS 2013

Alle Angaben wie immer ohne Gew¨ahr.

Inhaltsverzeichnis 1 Fehleranalyse 1.1 Numerische Fehler . . . . . 1.2 Rundungsfehler . . . . . . . 1.3 Konditionierung numerischer 1.4 Konditionierung numerischer

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

2 2 2 2 2

2 Theorie der Eliminationsverfahren 2.1 Vektor- und Matrizennormen . . . . . . . . . . . . . . . . . 2.2 Kondition und Fehlerabsch¨atzung . . . . . . . . . . . . . . . 2.3 Cholesky-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . 2.4 LR-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Lineare Ausgleichsrechnung . . . . . . . . . . . . . . . . . . 2.6 QR-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.1 Gram-Schmidt’sches Orthonormalisierungsverfahren . 2.6.2 Householder-Verfahren . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

3 3 3 4 4 4 4 4 5

3 Interpolation und Approximation 3.1 Polynominterpolation . . . . . . . . . . . . 3.1.1 Lagrange . . . . . . . . . . . . . . . 3.1.2 Newton . . . . . . . . . . . . . . . 3.2 Richardson’sche Extrapolation zum Limes 3.3 Gauß-Approximation . . . . . . . . . . . .

. . . . . . . . . . . . . . . . Aufgaben . . Algorithmen

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

5 5 5 5 6 6

4 Theorie der Quadraturverfahren 4.1 Interpolatorische Quadraturformeln . . . . . . 4.1.1 Lagrange’sches Interpolationspolynom 4.1.2 Newton-Cotes-Formeln . . . . . . . . . 4.2 Romberg’sches Integrationsverfahren . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

7 7 7 7 7

5 Theorie von Iterationsverfahren 5.1 Nullstellen reeller Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8

1

. . . . .

1 1.1

Fehleranalyse Numerische Fehler Diskretisierungsfehler: Ungenauigkeit in einzelnen iterativen Schritten Abbruchfehler: Abbruch unendlicher Algorithmen nach endlich vielen Schritten Rundungsfehler: endliche Genauigkeit durch Rundungen

1.2

Rundungsfehler Gleitpunktzahlen: Form: g = ±.d1 ...dm · β e ; mit 0 ≤ di < β β ∈ N Basis, m ∈ N Genauigkeit, e ≤ e ≤ e ∈ Z untere/obere Schranke Maschinengenauigkeit: eps = 12 β 1−m ; β, m architekturabh¨ angig, typischerweise: β = 2, m = 48 ∼

∼

aherung von x absoluter und relativer Fehler: x, x ∈ R, x N¨ ∼

– absoluter Fehler: |x − x| ∼

– relativer Fehler: | x−x x | ∀x ∈ G′ , x 6= 0 : | rd(xx)−x | ≤ eps, rd(x) = x(1 + ǫ)

1.3

Konditionierung numerischer Aufgaben

Betrachte Auswirkung relativ kleiner Datenfehler |∆xj | ≪ |xj | Taylorentwicklung: ∆yi = fi (x+∆x)−fi (x) =

m P

j=1 i | ∆y |≤| yi

m P

j=1

j ∂fi (x) ∆x | ∂xj yi

+

∂fi (x)∆xj +Rf (x, ∆x), i ∂xj

o(|∆x|) |yi |

≤

m P

j=1

∂fi j || | ∂x (x)fix(x) j

∆xj xj

= 1, ..., m, Rf (x, ∆x) = o(|∆x|)

|+

o(|∆x|) |yi |

x

∂fi j (x)fi(x) relative Konditionszahlen: kij (x) = | ∂x | j

Konditionierung: – schlecht konditioniert: ∃|kij (x)| ≫ 1, sonst gut konditioniert – Fehlerd¨ ampfung: |kij (x)| < 1 ∀i, j, sonst Fehlerverst¨ arkung

1.4

Konditionierung numerischer Algorithmen

Algorithmus: Folge hintereinander ausgef¨uhrter elementarer Abbildungen ϕ(k) mit: ∼ x = x(0) → ϕ(0)(x(0)) = x(1) → ... → ϕ(k) (x(k) ) = x(k+1) → ... → y schlecht konditionierte Teilalgorithmen sollte man zuerst ausf¨ uhren Problemfehler: | ∆y |, Berechnung s.o. y gut konditioniert, wenn gilt: relativer Fehler | ∆y | (aus Rechnung) ≤ Problemfehler y 2

2 2.1

Theorie der Eliminationsverfahren Vektor- und Matrizennormen ur die gilt: Vektornorm: Abbildung ||.|| : K n → R+0 , f¨ 1. ||x|| > 0(x ∈ K n \ {0}) (Definitheit) 2. ||α · x|| = |α| · ||x||(x ∈ K n , α ∈ K) (positive Homogenit¨at) 3. ||x + y|| ≤ ||x|| + ||y ||(x, 0(x ∈ K n \ {0}) (Definitheit) Matrizenklassen: T

– hermitesch: A = A bzw. ajk = akj , 1 ≤ k, j ≤ n (A : komplex konjugiert) – positiv definit: xT Ax > 0 ∀x bzw. alle Eigenwerte > 0 – orthogonal: AAT = AT A = , damit AT = A−1 , ||Ax||2 = ||x||2 , (Ax, Ay) = (x, y ) Spektralradius: ρ(A) = max(|λi |, λi Eigenwert von A); A hermitesch: ρ(A) = |||A|||2

2.2

Kondition und Fehlerabsch¨ atzung ∼

Betrachte Problem Ax = b mit Fehler x − x = δx. wenn |||A||| < 1, dann gilt: |||( + A)−1 ||| ≤ Konditionszahl: cond(A) = |||A||| · |||A−1 ||| 3

1 , 1−|||A|||

A ∈ K n×n , |||.||| : K n×n → R+0

−1 −1 St¨ orungssatz: A ∈ K n×n  < |||A ||| . Dann gilt:  und |||δA||| ||δx|| cond(A) ||δb|| ≤ 1−cond(A) + |||δA||| |||δA ||| |||A||| ||x|| ||b|| |||A|||

f¨ ur hermitesche Matrizen gilt: cond2 (A) =

2.3

|λmax| |λmin |

(Spektral-Konditionszahl von A)

Cholesky-Zerlegung

n×n Zerlege symmetr. und pos.def. in A  = LLT , L linke untere Dreiecksmatrix:  Matrix A ∈ R 0 i < j    s     i−1   P   j 2 P i = j lik aii − aij = lik ljk , damit: lij = k=1   k=1   j−1  1 P      ljj (aij − lik ljk i > j  k=1

2.4

LR-Zerlegung

Zerlege A = LR in linke untere Dreiecksmatrix L und rechte obere Dreiecksmatrix R Gaußsches Eliminationsverfahren:(k) (i) (k+1) a (k) (k) = aij − lik akj , rij = aij , 1 ≤ i ≤ j ≤ n ur k = 1, ..., n : lik = aik(k) , aij A = A(1). F¨ kk

L¨ose Ax = b: L¨ ose Ly = b und Rx = y Pivotisierung: Falls dabei Teilen durch 0, vertausche Zeilen in Matrix und L¨osung

2.5

Lineare Ausgleichsrechnung

Finde zu gegebenen Punktepaaren (ai , bi ) Funktion f : R → R : f (ai ) ≈ bi . bestimme Linearkombination u(a) =

n P

xk uk (a)

k=1

setze b = (yi )T ∈ Rm , x = (xi )T ∈ Rn , an = (uk (a1 ), ..., uk (am ))T , A = (ai ) ∈ Rm×n finde L¨ osung x ∈ Rn : ||Ax − b||2 = minn ||Ax − b||2 x∈R

l¨ ose Gaußsche Normalengleichung: AT Ax = AT b

2.6

QR-Zerlegung

Zerlege A = QR ∈ Rm×n , m ≥ n, rg(A) = n in eindeutig bestimmte Matrizen Q und R, Q orthogonale Matrix, R rechte obere Dreiecksmatrix mit Diagonaleintr¨ agen rii > 0 N ormalengl. T T T T T T T T = R Q b ⇒ Rx = QT b Es gilt: A Ax = (QR) (QR)x = R Q QR x = R Rx 2.6.1

Gram-Schmidt’sches Orthonormalisierungsverfahren A = (a1 , ..., an ), ai Spaltenvektor von A ∼

q1 = ||a1 ||−1 ur k = 2, ..., n : q k = ak − 2 a1 , f¨

k−1 P i=1

∼

hohe Rundungsfehleranf¨alligkeit, daher in der Praxis ungeeignet 4

∼

(ak , qi )qi , qk = ||q k ||−1 2 q k , rik = (ak , qi )

2.6.2

Householder-Verfahren S=

− 2vv T ∈ Rm×m Householder-Transformation, S symmetrisch und orthogonal

A = (a1 , ..., an ), ai Spaltenvektor von A, anfangs ist Q0 = , A0 = A ∼

vi =

∼T ai −||ai ||2 ei , vi ||ai −||ai ||2 ei ||2

=

ai +||ai ||2 ei , Hi ||ai +||ai ||2 ei ||2

=

0 ∼ ∼T

− 2 vi vi

0

!

=



 01  ...   − 2vv T ,v =  0i−1  ∼ vi

berechne in jedem Schritt Ai = Hi · Ai−1 , Qi = Qi−1 · Hi , Ende: Q = Qm−1 , R = Am−1 numerisch stabiler als LR-Zerlegung, aber O( 23 n3 ) (doppelt so groß wie bei LR-Zerlegung)

3

Interpolation und Approximation Interpolation: Funktion g ∈ P durch Fixieren von Funktionswerten: g(xi ) = yi Approximation: Ann¨ aherung, z.B. minimiere max ||f (x) − g(x)|| a≤x≤b

3.1 3.1.1

Polynominterpolation Lagrange (n) Lagrange’sche Basispolynome: Li (x) =

n Q

j=0,j6=i

setze p(x) =

n P

i=0

(n)

yi Li (x) ∈ Pn , es gilt: p(xj ) =

x−xj xi −xj n P

i=0

∈ Pn ; Li (xj ) = δij ,

n P

Li (x) = 1

i=0 (n)

yi L i (xj ) = yj , 0 ≤ j ≤ n

Nachteile: n → n + 1: komplette Neuberechnung ggf. keine gleichm¨aßige Konvergenz von Polynom(folgen) schlecht konditioniert f¨ ur große n (Oszillation) 3.1.2

Newton Newton’sche Basispolynome: N0 (x) = 1, Ni (x) =

i−1 Q

(x − xj ), i = 0, ..., n

j=0

setze p(x) =

n P

αi Ni (x) ∈ Pn mit αi = y[x0 , ..., xi ] (dividierte Differenzen)

i=0

dividierte Differenzen: y[xi ] = yi , y[xi , ..., xi+k ] =

y [xi+1 ,...,xi+k ]−y [xi ,...,xi+k−1 ] ,1 xi+k −xi

  y0 y[x0 , x1 ] y[x0 , x1 , x2 ] ... y[x0 , ..., xn ]   y1 y[x1 , x2 ] ... ...  Neville’sche Darstellung:    ... yn

Approximationseigenschaften: Sei f ∈ C n+1 ([a, b]). Dann gilt: n Q (n+1) ∀x ∈ [a, b]∃ξx ∈ [x0 , ..., xn , x] : f (x) − p(x) = f (n+1)!(ξx) (x − xj ) j=0

5

≤ k ≤ n−1

3.2

Richardson’sche Extrapolation zum Limes

approximiere a(x) = lim a(h), z.B. x = 0: h→x

Sei f ∈ C 2 ([a, b]), x ∈ [a, b]. a(h) =

f (x+h)−f (x) h

∼

Falls f ∈ C 3 ([a, b]), verwende a(h) =

= f ′ (x) + 2hf ′′(ξx ), ξx ∈ (x, x + h)

f (x+h)−f (x−h) 2h

∼

Es gilt: falls f ∈ C ∞ ([a, b]), dann: a(h) = f ′ (x) +

∞ P

a2i (x)h2i .

i=1 ∼

sin(h)−sin(−h)

Beispiel: f (x) = sin(x), (a, b) = (−1, 1), x = 0. a(h) = 2h ∼ ∼ ∼ 1 ∼ ) = 0, 9993 Bspw. a(h0 ) = a( 18 ) = 0, 997, a(h1 ) = a( 16

=

sin(h) . h

Alternative: Stelle Interpolationspolynom auf und werte an Stelle x aus. Modifikation: Berechne Ableitung an der Stelle x0 . h1 = h, q Exponent 2R −Ri,j (x0 −hi+1 ) , 1 ≤ j < nmax hi+1 = h2i , Ri+1,1 = f (x0 +hi+12h)−f , Ri+1,j+1 = i+1,j 2jq −1 i+1 ′ f (x0 ) ≈ Rnmax,nmax

3.3

Gauß-Approximation

Rb 1 Bestapproximation: ||f − g|| = min ||f − ϕ||, S Menge von Funktionen, ||f || = ( |f (x)|2 dx) 2 ϕ∈S

a

Rb Skalarprodukt: (., .) : (C([a, b]))2 → R mit (f, g) = f (t)g(t)dt a

gewichtetes Skalarprodukt: (f, g)ω =

R1

−1

1 ω(x)f (x)g(x)dx mit ω(x) = √1−x 2

n von S (Gram-Schmidt): Orthonormalisiere Basis {ψi }i=1 ∼ ∼ i−1 P ∼ ∼ ϕ1 ϕ ϕ1 = ψ1 , ϕ1 = ∼ , ϕi = ψi − (ψi , ϕk )ϕk , ϕi = ∼i , damit {ϕ1 , ..., ϕn } ONS ||ϕ1 ||

||ϕi ||

k=1

Stelle g ∈ S mit {ϕ1 , ..., ϕn } dar: n n n n P P P P αi (ϕi , ϕk ) = ( αi ϕi , ϕk ) = (g, ϕk ) αi δik = αk ϕk mit αk = g= k=1

i=1

i=1

i=1

Vorteile: verbesserte Stabilit¨atseigenschaften (gleichm¨ aßige Konvergenz), verbesserte Konvergenzaussage

Tschebycheff-Polynome: x ∈ [−1, 1], Tk (x) = cos(k · arccos(x)). rekursiv: T0 = 1, T1 (x) = x, Tk+1 (x) = 2x · Tk (x)  − Tk−1 (x) π k = j = 0   R1 es gilt: ω(x)Tk (x)Tj (x)dx = π2 k = j 6= 0   −1 0 k 6= j q q Monom-Basis: ϕ1 (x) = π1 , ϕk (x) = π2 Tk−1 (x)

6

4

Theorie der Quadraturverfahren

n¨ aherungsweise Berechnung eines bestimmten Integrals

Rb

f (x)dx

a

Ansatz: f¨ ur f ∈ C([a, b]) : I(f ) =

Rb

f (x)dx ∼ In (f ) =

αi f (xi )

i=0

a

4.1

n P

Interpolatorische Quadraturformeln

4.1.1

Lagrange’sches Interpolationspolynom

pn (x) =

n P

i=0

(n)

(n) f (xi )Li (x) mit Li (x) =

j=0,j6=i

Rb

⇒ In (f ) = pn (x)dx =

n P

i=0

a

4.1.2

n Q

Rb

x−xj xi −xj

f (xi ) L(n) i (x)dx, also αi =

Rb

(n) Li (x)dx

a

a

Newton-Cotes-Formeln abgeschlossene Newton-Cotes-Formeln: xi = a + ih, 0 ≤ i ≤ n, h =

b−a n

b−a offene Newton-Cotes-Formeln: xi = a + (i + 1)h, 0 ≤ i ≤ n, h = n+2

also: αi =

Rb

(n) Li (x)dx = h ·

Rn

n Q

0 j=0,j6=i

a

t−j dt i−j

Beispiele: I1 (f ) = 2h (f (a) + f (b)) (Trapez-Regel, abgeschl. NC) ) + f (b)) (Simpson-Regel, abgeschl. NC) I2 (f ) = 3h(f (a) + 4f ( a+b 2 3h I3 (f ) = 8 (f (a) + 3f (a + h) + 3f (b − h) + f (b)) (83-Regel, abgeschl. NC) ) (Mittelpunktsregel, offene NC) I0 (f ) = (b − a)f ( a+b 2 Problem: ab n = 7 (abgeschl.) bzw. n = 2 (offene) treten negative αi auf, dadurch erh¨ohte Rundungsfehleranf¨ alligkeit (Ausl¨ oschung) L¨osung: summierte Quadraturformel: Teilintervalle der L¨ ange h: N −1 P (n) InΣ(f ) = I[xi,xi+1 ] (f ) mit h = b−a , Idee: N groß, n moderat N i=0

4.2

Romberg’sches Integrationsverfahren h= Rb a

b−a , x j N

= a + jh, 0 ≤ j ≤ N .

f (x)dx = h(21f (a) +

a(h) = h

NP −1 j=0

N −1 P j=1

f (xj ) + 21f (b)) − h2 b−a f ′′(ξ) 12

f (xj ) + 2h (f (a) − f (b)), lim a(h) = h→0

a0,i = a(hi ), 0 ≤ i ≤ m, ak,i = ak−1,i +

Rb

f (x)dx (Extrapol. der Trapezregel)

a

ak−1,i −ak−1,i−1 (

7

hi−k 2 hi ) −1

, k ≤ i ≤ m ⇒ am,m ≈ a(0)

5 5.1

Theorie von Iterationsverfahren Nullstellen reeller Funktionen Intervall-Schachtelungs-Verfahren bzw. Bisektionsverfahren (trivial)

8...