Einführung in die Numerische Mathematik

• Titel: Einführung in die Numerische Mathematik
• Organisation: UNI HEIDELBERG
• Seitenzahl: 280

Skript herunterladen (PDF)

Inhalt

• Einfuhrung in die Numerische Mathematik Numerik
• Institut fur Angewandte Mathematik Universitat Heidelberg
• Vorlesungsskriptum SS April
• Stabilitt numerischer Algorithmen a
• Auswertung von Polynomen Ubungsaufgaben
• Interpolation und Approximation
• Interpolatorische Quadraturformeln iii
• Lineare Gleichungssysteme I Direkte Verfahren
• Nicht regulre Systeme a
• Die Singulrwertzerlegung a Ubungsaufgaben
• Gedmpftes NewtonVerfahren a Ubungsaufgaben
• Lineare Gleichungssysteme II Iterative Verfahren
• Ein Modellproblem Ubungsaufgaben
• Verfahren der Sturmschen Kette Ubungsaufgaben
• Lineare Optimierung Index Das SimplexAlgorithmus
• Punktbelastung f t
• Zahldarstellung und Rundungsfehler
• m m e fr m u
•  Zahldarstellung und Rundungsfehler
• Konditionierung numerischer Aufgaben
• yi fi x x fi x
• fi f x xj Ri x x xj
•  Konditionierung numerischer Aufgaben
• Fr den komponentenweisen relativen Fehler gilt dann u
• fi xj x xj yi
• f Ri x x x O yi yi
• Andernfalls darf der Restgliedterm nicht vernachlssigt werden a
• fi yj y yj xi
• n n kik kkj k
• fi fk ij xk xj
• y y p y y
• y y q y y q
•  Stabilitt numerischer Algorithmen a
• Stabilitt numerischer Algorithmen a
• dh dieser Algorithmus ist stabil
• Beispiel u v w
• liefert den Funktionswert p b des Polynoms px
• x gut konditioniert
• x xj xi xj jji
• k xi Li i n n
• x R k n
•  Interpolation und Approximation
• minimal fr u
• u max f xi gxi minimal fr
• x xj Pn xi xj jji
• falls i k falls i k
• Denition Das Polynom
• yx xi Ni x
• was den Beweis vervollstndigt a
• Die Koezienten des Polynoms pnj seien mit ak
• bezeichnet j n
• j n an k n j ak
• an ak yj xkj ak bj aj
• f x px f x xn x
• f x xn x
• f n x t x x
• f x tx x dt
• f x pn x f x
• f x pn x f x xn
• x xj f x xn
• und folglich nach Denition der dividierten Dierenzen
• f n dtdtn dt QED
• Dies vervollstndigt den Beweis a
• Im Extremfall x xn wird
• f n x dtn dt dt
• i f x x x i i
• LagrangePolynom zum Aufpunkt xm
• x xj fr x u
• Abbildung Strungsverlauf bei wachsendem Polynomgrad o
• i m k i
• x xj j x xi r
• yxi xi xi yi
• yxi xi yi yxi xi xi xi xi
•  Extrapolation zum Limes
• Extrapolation zum Limes
• x x x x ah ah
• f i x i h i
• sinh sinh sinh h h
• ah ergibt dann p h ah
• aj hjq an hhnq
• a pk Ohk n
• z zkl zki zkl
• Damit erschließen wir
• j n Lki i n
• j n aj zki an hkizki n n
• n zki Lki i i
• zu garantieren Wegen
• ergibt sich gleichmßig fr alle k a u
• aik aik hik hi q
• hq ikj ohik
• hi q kq ak k ohik hik
• Abbildung Stckweise lineare Interpolation u
• a b p Ca b pIi linear
• h max f x xab
• s xw x dx s
• s bw b s aw a
• Speziell fr w s N ist also u
• s x dx QED
• s xw x dx n
• Wegen der Identitt a
• s x w x dx n
• s xw x dx n
• folgt die Behauptung
• und ergeben a
• hi hi a hi a
• yi yi yi yi hi hi
• ist symmetrisch dh aij aji und strikt diagonaldominant
• als die Lagrangeschen Interpolationspolynome Allgemein konvergiert
• max f x sn x h
• sogar fr absolutstetiges f mit u
• Beweis Siehe WernerSchaback II
• kx kx bk sin
• wk eixk eikn
• k n pn Pn
• n j yj wk ck n j
• bzw ck n Dies vervollstndigt den Beweis a
• ak coskx bk sinkx
• m n falls n ungerade
• Die Koezienten sind bestimmt durch ak n
• yj eijxk ck
• ak coskx bk sinkx am cosm x
• ck ck coskxj i ck ck sinkxj
• ck coskxj i sinkxj
• ck eikxj cm eimxj
• ck eikxj yj
• yj eijxk eijxk
• yj i eijxk eijxk
• Abbildung Periodische Fortsetzung
• Fr k m folgt u ck
• f x k m n k n n
• yk ynk k n
• yj einjxk cnk ck
• bk ick ck ak ck n n
• ynj einjxk yj yj eijxk n m
• eijxk eijxk y ym cosjxk
• f xk k m n
• y w k y w k w k
• y w k y w k w k
• yj w jk w k
• k p k k mod p
• und somit g g
• i k k i g g
• n nach Konstruktion
• ipi pj j pj
• Es ergibt sich
• f pk d pk x
• gk xgj xx dx
• mit den Koezienten
• xk pi pi pi
• pk xpk pk Pk
• so ergibt sich mit
• pi x pk x QED
• schließlich die Behauptung
• S g gx x R
• Beweis Ein g S mit
• kann keine beste Approximation sein da
• f g g f f f inf
• ai gi xj yj
• Abbildung Schema der Alternantenregel
• sowie die Grße n f g o
• aus dem linearen Gleichungssystem k n
• i i xk k n f xk
• das Optimalittskriterium a
• ex e e
• Abbildung Anwendung der Alternantenregel
• xxk n max Tn x
• und damit die behauptete Optimalittseigenschaft a
• TschebyscheffPolynome yAchse xAchse
• tpx tpx tpx tpx tpx
• b an n f n n
• max f x pn x n
• hk xk xk xk xk
• p f p f p f
• fr k und stelle sie graphisch dar u
• und dann gesetzt
• f x xn x
• x xj xi xj
• a tH a jH a iH a jH
• ab f b H f b
• f a ab b xx ax
• f a ab b ab
• Nach dem verallgemeinerten Mittelwertsatz der Integralrechnung folgt
• f a ab ab b xx ax
• If Ih f Summierte SimpsonRegel m
• Summierte Mittelpunktregel m Ih f
• Die interpolatorischen Quadraturformeln
• so ergbe sich der Widerspruch a
• px dx I n p QED
• If I n f If
• Wir schreiben fr i n n u
• b i a j b n i
• Pn Die n Polynome
• x xn x xn x xn
• x xj qx dx q Pn
• Die obige Bedingung besagt dann daß das Polynom
• x xj xn rx
• xk pj pj x pj
• x i fr Nn m u
• pn xqxx dx QED
• x j dx i j
• und erhalten wegen li Pn n
• j li j i ij
• f x hx f n n x
• f n n x
• x i dx QED
• und fr die Restglieder gilt u
• ba f y dy ba
• I sind gegeben durch
• i n die Quadraturformeln
• f xj h f xj h
• Das Rombergsche Integrationsverfahren
• mit den Bernoulli Zahlen Bk
•  Das Rombergsche Integrationsverfahren
• k m i k m
•  Praktische Aspekte der Integration
• Praktische Aspekte der Integration
• f hk k Ohk
• Ubung Mit wievielen Funktionsauswertungen kann das Integral
• cosx dx x
•  Lineare Gleichungssysteme I Direkte Verfahren
• Beispiel Gebruchliche Beispiele von Vektornormen sind a
• S und folglich
• Ax sup x xKn x
• ii Weiter ist die maximale Zeilensumme wegen
• ajk max xk A
• vertrglich mit a
• und es gilt sup
• iii Im Falle A
• ist A dh trivialerweise A
• und m n ein Index mit der Eigenschaft
• A Wir setzen fr k n u
• zk dh z zk n Kn z k
• amk amk fr amk u sonst
• Fr v Az gilt dann u
• Folglich ist A was zu zeigen war
• max Eigenwert von A
• max Eigenwert von AT A
• w i w j ij
• x Ax Hiermit folgt A
• i i j j w w
• Ax sup x xKn
• n i i i n i i
• i i j w i w j
• aij ik jk Aek ek
• erhlt man die behauptete Ungleichung a
• A Ax b Ax b A
• x folgt schließlich A
• condA condA A
• was zu zeigen war
• verliert man s Stellen Genauigkeit
• P r r
• q G qn
• i qii qni
• rn rn rn rin i ain ann
• r l r rn rn c c
• c c ci i bi i bn
• Satz LRZerlegung Die Matrizen
• L l R r r rn rn rnn
• k b k k akk
• Beispiel Mit wird das Pivotelement markiert
• x x Elimination x Pivotierung Pivotierung
• x x x
• im Rahmen der Maschinengenauigkeit korrekt
• T stellige Rechnung
• Die approximative Korrekturgleichung
• Vorwrtselimination a A r rn
• rnn Skalierung A
• Rckwrtselimination u a r rnn
• Beispiel Es markiere das Pivotelement
• A Zeilenvertauschung Vorwrtselimination a
• Rckwrtselimination u a
• ajq apq ajq apn xq ajn apq apq
• j m j p k n k q
• x nr x nr r A nr
• Austauschschritte Mit wird das Pivotelement markiert
• x x x x y y x y
• y x x y y x
• x y y y x x x
• n n n n n
• nn n n On
• li rik rk ak
• ljiri lj r aj
• li rik rk ak l rk
• und allgemein fr j n u
• a c b bn an cn
• Hier lassen sich die Elemente der LRZerlegung
• L n R
• n cn n n an n n
• ajk ajk qj ak
• ajk aj qj
• ajk xj xk x
• ak xk a x a
• Mit der Eindeutigkeit der LRZerlegung folgt aus
• j i n
•  Nicht regulre Systeme a
• Nicht regulre Systeme a
• min Ax b n
• ajk xk bj AT A AT bi x
• A a an
• Beispiel Zu den Meßdaten xi
• Die zugehrige Normalgleichung lautet o a b
• und der maximalen Abweichung max yxi yi
• Abbildung Lsung der Tschebyscheschen Ausgleichsaufgabe o
• R R Dies vervollstndigt den Beweis a
• Q AR AR Q
• Denition Fr einen Vektor v Kn mit u
• heißt die Matrix
• Dies ergibt die Darstellung
• Spiegelungsachse aae a aae
• Abbildung Schema der HouseholderTransformation
• a a e a a e
• ak ak ak v v
• ai ai ak ak
• k i n
•  Die Singulrwertzerlegung a
• Die Singulrwertzerlegung a
• fr i minm n Daraus ergibt sich u
• AT Avi i vi AAT ui i ui
• existiert ein x Rn mit
• w w wT
• die Abschtzung a
• aus dieser Menge Es gilt dann
• Bz und somit AB
• T i vi z k
• Hier wurde ausgenutzt daß z
• k T i vi zvi
• V T x U T b
• Wir nennen die Matrix A V U T
• Die PseudoInverse ist die eindeutige Lsung von o
• mit der FrobeniusNorm
• RangA n RangA n m
• Ubung Man betrachte das lineare Gleichungssystem
• Ax x Kn x x
• Eigenwert von AT A
• und der Lsung x T o
• mit Hilfe des HouseholderVerfahrens
• bt at bt at t b a
• f xt STOP
• bt xt bt bt
• f at f xt at xt
• Das NewtonVerfahren im R
•  Das NewtonVerfahren im R
• Mit Hilfe der Voraussetzung erhalten wir
• s ds und nden
• Abbildung NewtonIteration zur Wurzelberechnung
• Startwert ndern sei a ja x wird akzeptiert
• NewtonKorrektur q Iterationsschritt
•  Das Konvergenzverhalten iterativer Verfahren
• Das Konvergenzverhalten iterativer Verfahren
• xt z gxt gz und folglich
• max g p xt zp p
• f xt f xt xt xt
• xt xt f xt f xt
• Abbildung Geometrische Interpretation des SekantenVerfahrens
• dr d f x ry x dr xy
• f x ry x dr
• M xt z xt z m
• der quadratischen Gleichung
• Methode der sukzessiven Approximation im Rn
•  Methode der sukzessiven Approximation im Rn
• gi x sy xy xj xj
• und den Stetigkeitseigenschaften der Vektornorm folgt
• Dies impliziert die Bahauptung
• g x sinhx
• Z gZ Z B
• I Z I B A
• Das NewtonVerfahren im Rn
•  Das NewtonVerfahren im Rn
• und bei Iteration dieser Abschtzung a
• xjl flk ypq
• flk ypq xpq
• Y f f Y
• c xt xt ext
•  Lineare Gleichungssysteme II Iterative Verfahren
• fhren wir die Aufu
• a an ann
• Satz Fixpunktiteration Die durch xt Bxt c
• t lim sup
• r r rn rnn rnn
• und haben damit
• T S R S T x
• mit der Konstante
• Also ist sup
• und die Behauptung folgt mit
• ark arr fr ein r n u
• ask v asi vi
• i i H folgt notwendigerweise
• spr H max i
• insbesondere ist das GaußSeidelVerfahren konvergent
• eine obere Schtzung opt mit a spr H
• gerade daß gilt Q x xi xi
• ajk xj xk xi
• aik xk bi QED
• grad Qy A AT y b Ay b
• xt xt t r t
• Unter Verwendung der Notation y Qy Ay b
• By y gilt b
• Wir setzen g n n
• Abbildung Skizze zu Beweis des Lemma von Kantorowitsch
• Daraus folgt dann durch sukzessive Anwendung xt x
• Abbildung Oszillierende Konvergenz des Gradientenverfahrens
• so zu bestimmen daß Qxt min Qy
• t j dj Kt d A
• d Ad g Ad
• t g t Adt t dt Adt
• zu den Formeln
• g t Adt dt Adt
• dt g t t dt
• Startwerte fr t u
• gt dt Adt g t t g t
• Bt spand dt
• Dann gilt xt x
• Beweis Unter Beachtung der Beziehung xt xA min
• I ApAx x I ApA
• und folglich pAy Dies impliziert
• pA und damit die Behauptung
• Aus der Darstellung Tt
• AT Ay y AT b y Ay b
• lii aii lji aji
• i n j i n
• Gitterweite Anzahl der gesuchten Knotenwerte
• Abbildung Zur Diskretisierung des Modellproblems
• coskh coslh k l m h Oh
• Ubung Fr die Matrizen u A
• Cm z zm m
• RangCm I m
• z j z z j b b
•  Konditionierung des Eigenwertproblems
• Konditionierung des Eigenwertproblems
• max jn ajj
• d h liegt in einem der GerschgorinKreise
• Hilfssatz ergibt dann die Behauptung
• Ferner ist Az
• t n n t n n
• cosh cosh h Oh
• detT detB zI detT detB zI
• Die Zahlen rk
• sind dabei bis auf die Reihenfolge eindeutig bestimmt
• auf Cn Fr zwei ahnliche u
• B B T A A T
• und Permutationsmatrizen p q
• Ai Ti Ai Ti
• Ti Ppi qi Epi
• Tridiagonal und HessenbergMatrizen
•  Tridiagonal und HessenbergMatrizen
• lim Qt I lim Rt
• Beweis Wegen E t I
• Qt Rt Qt Qt
• qjk t t
• lim Rt lim Qt E t I
• Wir nden also A zIwz wn z
• at bt at bt
• Zu minimieren sind die Gesamtkosten
• unter den Nebenbedingungen xjk und
• Zielfunktion Qxx xx
• xx Niveaulinie der Zielfunktion Qxx
• Abbildung Grasche Lsung eines Linearen Programms o
• Der Vektor x x d xk dk T
• xi x ai i
• ik xk x i k xk cT x
• j m k n
• y x x y y x
• x y y x x
• x i i I cT x
• k xk cT x cT x
• pq qp iq ip
• iq pq q q p pq pk pq
• x p pq iq pk pq
• x x pq x pq p p p
• iI start kI start
• xj x r max rq jq jq
• die Vektoren u
• r rm x r rq rq rq
• q q q k p q
• cT x cT x k
• Hieraus entnehmen wir mit der Induktionsannahme
• kq Dies vervollstndigt den Beweis a

Vorschau