Post on 17-Jan-2016
description
transcript
Ausgleichungsrechnung IGerhard Navratil
Mathematische Grundlagen
• Lineare Algebra• Matrizenalgebra• Einfaches Eigenwertproblem• Singulärwertzerlegung• Generalisierte Inverse• Iterative und numerische Verfahren• Differentialrechnung• Optimierung
Ausgleichungsrechnung IGerhard Navratil
Lineare Algebra
Lösen linearer Gleichungen und Gleichungssysteme
Werkzeug: Matrizenrechnung
15294
15753
15618
321
321
321
xxx
xxx
xxx
3333232131
2323222121
1313212111
bxaxaxa
bxaxaxa
bxaxaxa
Koeffizienten
Unbekannte
Konstante
Ausgleichungsrechnung IGerhard Navratil
Arten von linearen Gleichungssystemen
Homogenes Gleichungssystem: alle Konstanten gleich Null
Inhomogenes Gleichungssystem: mindestens eine Konstante ungleich Null
Beispielsystem:3 Gleichungen in 3 Unbekannten
Mehr Gleichungen als Unbekannte: Überbestimmt
Mehr Unbekannte als Gleichungen: Unterbestimmt
Ausgleichungsrechnung IGerhard Navratil
Begriff ‚Algebra‘
Abu Ja'far Muhammad ibn Musa Al-Chwarismi: ‚Hisab al-gabr w'al-muqabala‘ (Wiederherstellen und Zusammenführen) um 800 – Auflösen von Gleichungen
lat. Übersetzung: ‚Algoritmi‘ (Algorithmus)
Algebra später: Lehre vom Auflösen von Gleichungs- und Ungleichungssystemen
Ausgleichungsrechnung IGerhard Navratil
Moderne Algebra
Beziehungen mathematischer Größen zu-einander – formale Behandlung
Lineare Algebra: n-dimensionaler Vektor-raum und lineare Transformationen in ihm
Algebra auch: mathematische Struktur mit bestimmten Eigenschaften Menge der Matrizen und ihre Operationen sind eine Algebra
Ausgleichungsrechnung IGerhard Navratil
Matrizenalgebra
Eine (m,n)-Matrix ist eine rechteckige Anordnung von m x n Elementen in m Zeilen und n Spalten.
nm
mnmm
n
n
ik
aaa
aaa
aaa
a A
21
22221
11211
Ausgleichungsrechnung IGerhard Navratil
Dimension einer Matrix
Definiert durch Anzahl der Spalten und Zeilen
quadratisch, wenn Anzahl der Spalten und Zeilen gleich
rechteckig sonst
(m,1)-Matrix: Spaltenvektor
(1,n)-Matrix: Zeilenvektor
(1,1)-Matrix: Skalar
Ausgleichungsrechnung IGerhard Navratil
Elemente der Matrix
Können Variablen, Zahlen aus C (R, Z, N), Polynome, Matrizen etc. sein
Angesprochen über den Index– Zeilenindex: Nummer der Zeile– Spaltenindex: Nummer der Spalte
Index: Erst Zeile, dann Spalte angegeben
Ausgleichungsrechnung IGerhard Navratil
Gleichungssysteme mit Matrizen
Gleichungssystem von vorher: Ax=b
• Koeffizientenmatrix A
• Unbekanntenvektor x
• Konstantenvektor b
3
2
1
,
15
15
15
,
294
753
618
x
x
x
xbA
Ausgleichungsrechnung IGerhard Navratil
Schreibweise von Matrizen
Runde und eckige Klammern erlaubt
In der Lehrveranstaltung:Eckige Klammern für Matrizen mit Zahlen
Blockweise auftretende Nullen oft weggelassen (Lesbarkeit)
8300
0600
0250
0104
83
6
25
14
MM statt
Ausgleichungsrechnung IGerhard Navratil
Alter der Matrizenschreibweise
Albrecht Dürer: ‚Die Melancholie‘ (1514)
magischesQuadrat
Ausgleichungsrechnung IGerhard Navratil
Submatrizen
Jeder Teilblock einer Matrix kann wieder als Matrix aufgefasst werden
sr
qPA
294
753
618
P, q, r, s sind Submatrizen
Ausgleichungsrechnung IGerhard Navratil
Spezialformen
• Nullmatrix: Alle Elemente gleich Null
• Diagonalmatrix: Nur Hauptdiagonale besetzt
• Dreiecksmatrix: Dreieck besetzt– obere Dreiecksmatrix R oder U– untere Dreiecksmatrix L
• Treppenform: nicht-quadratische Matrizen in Dreiecksform
Ausgleichungsrechnung IGerhard Navratil
Symmetrie
• Symmetrische Matrix: quadratisch und
• Schief-symmetrische Matrix: quadratisch und Elemente der Hauptdiagonale gleich Null
njiaa jiij ...1,
njiaa jiij ...1,
Ausgleichungsrechnung IGerhard Navratil
Gleichheit von Matrizen
Zwei Matrizen sind gleich, wenn sie • vom gleichen Typ sind (die gleiche Dimension
haben) und• alle Elemente gleich sind, also wenn gilt
njmiba ijij ...1,...1
Ausgleichungsrechnung IGerhard Navratil
Spur einer Matrix
Nur für quadratische Matrizen
Summe der Hauptdiagonal-Elemente
abgekürzt mit ‚tr‘ (engl. ‚trace‘)
n
iiia
1
tr A
Ausgleichungsrechnung IGerhard Navratil
Determinante einer Matrix
Nur für quadratische Matrizen
Berechnet nach Entwicklungssatz von Laplace
abgekürzt mit ‚det A‘ oder |A|
n
k
ikkiik
n
i
ikkiik aa
11
11det AAA
Minor
Submatrix nach Streichen der i-ten Zeile und k-ten Spalte, auch StreichungsmatrixKofaktor, oder auch
algebraisches Komplement
Ausgleichungsrechnung IGerhard Navratil
Regeln über Determinanten
• Vertauschen zweier Zeilen (Spalten) wechselt das Vorzeichen
• Addition (Subtraktion) eines Vielfachen einer Zeile (Spalte) zu einer anderen Zeile (Spalte) lässt die Determinante unverändert
• Determinante einer Dreiecks- oder Diagonal-matrix ist das Produkt der Hauptdiagonal-Elemente
• verschwindende Determinante: Sind zwei Zeilen (Spalten) gleich oder proportional, so wird det(A)=0 (die Determinante verschwindet)
Ausgleichungsrechnung IGerhard Navratil
Reguläre und singuläre Matrizen
• Singuläre Matrix: Quadratische Matrix mit verschwindender Determinante – det(A)=0
• Reguläre Matrix: Quadratische Matrix, bei der die Determinante nicht verschwindet
Ausgleichungsrechnung IGerhard Navratil
3231
2221
1211
333231
232221
131211
aa
aa
aa
aaa
aaa
aaa+ ++
- --
Spezialfälle
(2,2)-Matrix
(3,3)-Matrix: Regel von Sarrus
211222112221
1211 aaaaaa
aa
333231
232221
131211
aaa
aaa
aaa
Ausgleichungsrechnung IGerhard Navratil
Matrizenoperationen
• Transposition
• Addition/Subtraktion
• Multiplikation mit einem Skalar
• Multiplikation zweier Matrizen
Ausgleichungsrechnung IGerhard Navratil
Transposition
Elemente wechseln ihre Position durch Vertauschen des Zeilen- und Spaltenindex
Abgekürzt mit AT
Spaltenvektor wird zu Zeilenvektor und umgekehrt
njmiaa jiTij ...1,...1
Ausgleichungsrechnung IGerhard Navratil
Symmetrie und Transposition
• Symmetrische Matrix:
• Schiefsymmetrische Matrix:
TAA
TAA
Ausgleichungsrechnung IGerhard Navratil
Aufspaltung einer quadratischen Matrix
Jede quadratische Matrix kann aufgespalten werden in eine symmetrische und eine schiefsymmetrische Matrix:
T
ssym
Tsym
ssymsym
mit
AAC
AAB
CBA
2
12
1
Ausgleichungsrechnung IGerhard Navratil
Addition und Subtraktion
Elementweises addieren/subtrahieren
Addition ist assoziativ
Addition ist kommutativ
Addition hat Nullelement
Transposition einer Summe
ijik ba BA
CBACBA
ABBA
AA00A TTT BABA
Ausgleichungsrechnung IGerhard Navratil
Multiplikation Matrix-Skalar
Jedes Element wird mit dem Skalar multipliziert
Es gilt:
ijij aa A
BABA
AAA
AA
AA
Ausgleichungsrechnung IGerhard Navratil
Element an Position (i,j) ist Produkt aus Zeilenvektor ai und Spaltenvektor bj
Potenzen nur für quadratische Matrizen möglich
AB=0 bedeutet, dass mindestens eine Matrix singulär (nicht: Nullmatrix!)
Matrizenmultiplikation
ji
n
k
kj
ki
kj
ik
pmpnnm
bababa
1
BA
CBA
Ausgleichungsrechnung IGerhard Navratil
Eigenschaften der Multiplikation
Assoziativ: (AB)C = A (BC)
Neutrales Element ist Einheitsmatrix I (E) mit
Multiplikation mit Einheitsmatrix ist kommutativ
Sonst NICHT kommutativ (ABBA)
Multiplikation ist distributiv: A(B+C)=AB+AC
jifür
jifürmit ijijij 0
1I
Kroneckersymbol
Ausgleichungsrechnung IGerhard Navratil
Potenzieren von Matrizen
qpqp
qpqp
AA
AAA
Ausgleichungsrechnung IGerhard Navratil
Skalarmultiplikation
Mit Einheitsmatrix kann die Skalarmultiplikation in eine Matrizenmultiplikation rückgeführt werden:
AIA
Ausgleichungsrechnung IGerhard Navratil
Transponieren von Produkten
TTTTT ABCZZCBA
Ausgleichungsrechnung IGerhard Navratil
Falk‘sches Schema
C=ABA
B
m
n
n
p
ABCDA
BCDB
C CD
D
Ausgleichungsrechnung IGerhard Navratil
Determinante und Spur von Matrizenprodukten
• Determinante einer (n,n)-Matrix:
• Spur einer Matrix:
T
n
n
AA
BAAB
AA
AA
1
AA
BABA
AA
trtr
trtrtr
trtr
T
Ausgleichungsrechnung IGerhard Navratil
Gauß‘sche Transformation
Produkt
N ist quadratisch, symmetrisch
Elemente nij von N: Skalarprodukt der Spalten i und j von A
Diagonalelemente positiv (Quadrate!)
Matrix positiv definit (bzw. semidefinit wenn auch Null in Hauptdiagonale)
Auch für Produkte möglich:
AAN T
PAAPA T
Ausgleichungsrechnung IGerhard Navratil
Positiv definit
Alle Subdeterminanten, die durch Streichung der letzten k Zeilen und Spalten entstehen (Minoren) sind 0
Hinweise auf positive definite Matrix:– Diagonalelemente positive reelle Zahlen– Jede Untermatrix ist positiv definit– Spur, Determinante und Minoren positiv– A+B positiv definit, wenn A und B positiv definit– Symmetrische Matrix mit positiven Eigenwerten ist
positiv definit
Ausgleichungsrechnung IGerhard Navratil
Orthogonale Matrizen
Quadratische Matrix
Skalarprodukt aus beliebigen Spaltenvektoren (Zeilenvektoren) ist 0 oder 1 orthonormal
Es gilt
Determinante ist ±1
Determinante +1: eigentlich orthogonal
Determinante -1: uneigentlich orthogonal
Multiplikation orthogonaler Matrizen ist kommutativ
1. QQIQQ TT bzw
IQQQQ TT
Ausgleichungsrechnung IGerhard Navratil
Inversion
Inverse Matrix (Kehrmatrix) von A ist definiert über
Matrix A quadratisch mit Determinante 0
Inverse ist eindeutig
A*: Adjungierte Matrix zu A, transponierte Matrix der Kofaktoren von A
IAAAA 11
*1
det
1A
AA
Ausgleichungsrechnung IGerhard Navratil
Inversion einer (2,2)-Matrix
ac
bd
dc
ba
AAA
det
11
Ausgleichungsrechnung IGerhard Navratil
Weitere Regeln
orthogonale Matrizen
A symmetrisch A-1 symmetrisch
A Diagonalmatrix A-1 Diagonalmatrix mit
Diagonalmatrix mit weiterer Zeile/Spalte besetzt
TAA 1
iiii aq 1
jjii
ijij
iiii aa
aqaq
,1
Ausgleichungsrechnung IGerhard Navratil
Submatrizen
11111
111
111
11
1
~
~
~
~
~~
~~
QSRQSPRSSS
RQSPRSR
QSRQSPQ
RQSPP
SR
QPA
SR
QPA
ssps
sppp
ssps
sppp
Ausgleichungsrechnung IGerhard Navratil
Spezialfälle von Submatrizen
ID
0I
ID
0I
B0
0AB0
0A
C0
BCAAC0
BA
1
1
11
1
1111
Ausgleichungsrechnung IGerhard Navratil
Neumann‘sche Reihe
Matrizeninversion kann auch über Reihenentwicklung berechnet werden:
Beweis: Von links mit (I+A) multiplizieren
Konvergenz, wenn Ai bei wachsendem i gegen Nullmatrix strebt
4321 AAAAIAI
Ausgleichungsrechnung IGerhard Navratil
Auflösen von Gleichungssystemen
Gegeben: Ax=b
Multiplikation von links mit A-1:
A-1Ax= A-1b
ergibt: (I)x= A-1b
Voraussetzungen:
Anzahl der Zeilen in A = Anz. Zeilen in b
Anzahl der Spalten in A = Anz. Zeilen in x
A invertierbar (quadratisch, Determinante Null)
Ausgleichungsrechnung IGerhard Navratil
Auflösung wenn nicht quadratisch
Gauß‘sche Transformation:Multiplikation von links mit AT:ATAx=ATbAuch: Normalgleichungen
Jetzt quadratisch und symmetrisch, wenn regulär ist das System lösbar
Abkürzung N=ATA Normalgleichungsmatrix
Ausgleichungsrechnung IGerhard Navratil
Lineare Abhängigkeit
• Vektorrechnung: Ein k-Tupel von Vektoren heißt linear abhängig wenn gilt
mit (1, …, n) 0
• Matrizenrechnung: Lineare Abhängig-keiten zwischen Zeilenvektoren bzw. Spaltenvektoren
k
iiix
1
0
Ausgleichungsrechnung IGerhard Navratil
Rang
Rang: Anzahl der linear unabhängigen Vektoren – rank(A)
Zeilen- und Spaltenrang sind immer gleich
Es gilt: rank(A)=rank(AT)
Ausgleichungsrechnung IGerhard Navratil
Rangdefekt
Anzahl der linearen Abhängigkeiten: Rangdefizit oder Rangdefekt d
rank(A)=n-d
Ausgleichungsrechnung IGerhard Navratil
Rang einer Matrix
Maximaler Rang einer (n,n)-Matrix: nDann: d = 0 (voller Rang) und det(A)0Also: Matrix invertierbar!
Wenn d > 0, dann det(A)= 0
Maximaler Rang einer (n,m)-Matrix: min(n,m)
Ausgleichungsrechnung IGerhard Navratil
Rang bei Gleichungssystemen
Gleichungssystem Ax=b
(n,n)-Matrix A muss Rang n haben
Zusätzlich: rank(A)=rank(A,b)
Ausgleichungsrechnung IGerhard Navratil
Bestimmung des Ranges (1)
Gauß‘scher Algorithmus: Man bringt die Matrix auf Treppen-(Dreiecks-)Form
Erlaubte elementare Umformungen:– Vertauschen von Zeilen/Spalten– Multiplizieren mit Skalar– Addieren einer mit einem Skalar
multiplizierten Zeile/Spalte zu einer anderen Zeile/Spalte
Ausgleichungsrechnung IGerhard Navratil
Bestimmung des Ranges (2)
Zeilen/Spalten, die das Vielfache anderer Zeilen/Spalten sind, werden eliminiert
Anzahl der nicht verschwindenden Zeilen/ Spalten ist der Rang
Verschwindende Zeilen: Nullen in Hauptdiagonale Determinante wird Null
Algorithmus auch zur Lösung von Gleichungssystemen verwendbar
Ausgleichungsrechnung IGerhard Navratil
Elementare Umformungen
Sind auch über Matrizenmultiplikationen möglich: z.B. Vertauschung von Zeilen
neuik AAJ
294
618
753
294
753
618
100
001
010
Ausgleichungsrechnung IGerhard Navratil
Gauß-Jordan-Verfahren
Basiert auf Gauß‘schem Algorithmus
Nur Umformungen der Zeilen
Ziel ist Zeilennormalform:– Elemente unterhalb der Hauptdiagonale Null– Erstes nicht verschwindendes Element jeder
Zeile Eins– Oberhalb dieser nicht verschwindenden
Elemente stehen nur Nullen
Ausgleichungsrechnung IGerhard Navratil
Vorgangsweise
xxxx
xxxx
xxxx
xxxx
00
00
00
00
xxxx
xxxx
xxxx
xxx
00
00
00
100
xxx
xxx
xxx
xxx
000
000
000
100
100000
10000
1000
100
x
xx
xxx
100000
010000
001000
000100
Erste vom Nullvektor verschiedene Spaltegrößtes Element (Pivotelement)
Zeilenvertauschen
Zeile durch diesen Wert dividieren
Ausgleichungsrechnung IGerhard Navratil
Hinweis
Gauß-Jordan-Verfahren kann auch zur Matrizeninversion verwendet werden
Beginn: A | I
Umwandlung der Matrix A, wobei jede Umformung auf beide Matrizen angewendet wird
Resultat: I | A-1
Ausgleichungsrechnung IGerhard Navratil
Einfaches Eigenwertproblem (1)
Quadratische Matrix A, gesucht sind die Vektoren x, für die giltAx=xmit dem Skalar
Umgeformt: (A-x=0(charakteristische Gleichung)
Annahme: (A- ist invertierbar: (A-(A-x=(A-0 x=0 triviale Lösung
Ausgleichungsrechnung IGerhard Navratil
Einfaches Eigenwertproblem (2)
Nicht-triviale Lösungen, wenn (A- singulär, alsodet(A-=0
charakteristische Determinante von A
Ausgleichungsrechnung IGerhard Navratil
Eigenwertproblem
allgemeine Form des Eigenwertproblems:Ax=Bx (für uns nicht wichtig)
Außerdem existiert jeweils eine zweite Art (Multiplikation mit dem Vektor von links)
Für uns ist bei Eigenwertproblem immer das einfache Eigenwertproblem erster Art gemeint
Ausgleichungsrechnung IGerhard Navratil
Eigenwerte
Lösung der charakteristischen Gleichung für eine (n, n)-Matrix liefert n Werte 1 bis n (Eigenwerte)
Eigenwerte im Allgemeinen konjugiert komplex
n ungerade: mindestens ein reeller Eigenwert
einfache, zweifache und mehrfache Eigenwerte
Ausgleichungsrechnung IGerhard Navratil
Kontrolle der Eigenwerte
n
ii
n
ii
1
1
tr
det
A
A
Ausgleichungsrechnung IGerhard Navratil
Weitere Eigenschaften
det(A)=0 mindestens ein Eigenwert gleich Null
Rangdefizit d d Eigenwerte gleich NullDie Eigenwerte einer Dreiecks- oder
Diagonalmatrix sind die Hauptdiagonal-elemente
A und AT haben dieselben Eigenwerte
A, i An, (i) n (speziell: Inverse!)
A, i A+cI, i+c; cA, ci
Ausgleichungsrechnung IGerhard Navratil
Eigenvektoren
Zu den Werten gehörende nicht triviale Lösungen für x
Eigenvektor zum Eigenwert Da (A-i singulär, ist der Eigenvektor nicht
eindeutig!Rangdefizit von 1: Eigenrichtung (Vektor auf
Länge 1 bringen um einheitliche Lösung zu erhalten – Normieren liefert Eigenvektor)
Rangdefizit >1: Entsprechende Anzahl linear unabhängiger Eigenrichtungen
Ausgleichungsrechnung IGerhard Navratil
Begriffe
Menge aller Eigenwerte: Spektrum der Matrix
Betragsmäßig größter Eigenwert: Spektralradius
Eigenwerte werden in Spektralmatrix zusammengefasst (Diagonalmatrix)
Eigenvektoren als Spaltenvektoren in Modalmatrix X zusammengefasst
Ausgleichungsrechnung IGerhard Navratil
Eigenschaften von und X
A = XX-1 (Eigenwertzerlegung)X-1AX = (Hauptachsentransformation)AX = XA und sind ähnliche Matrizen:
Es gibt eine Matrix U für die gilt:A = U-1U oder allgemein: S = U-1RU (Ähnlichkeitstransformation)
A symmetrisch X orthogonal A = XXT und XTAX =
Ausgleichungsrechnung IGerhard Navratil
Weitere Eigenschaften
Ist A eine Diagonalmatrix, so gilt = A und X = I
A und Am haben dieselben Eigenvektoren
Bei einer symmetrischen Matrix A gilt:A2 = ATA, die Matrix ATA hat dieselben Eigenvektoren, die Eigenwerte sind die Quadrate der Eigenwerte von A
Ausgleichungsrechnung IGerhard Navratil
Geometrische Interpretation
Darstellung einer Ellipse ist möglich mit
Eigenvektoren von A:Richtung der Haupt- und Nebenachse
Eigenwerte von A:Länge von Haupt- und Nebenachse
Modalmatrix dreht die Ellipse in Hauptlage
1.1
AxxTbzw
y
x
dc
bayx
Ausgleichungsrechnung IGerhard Navratil
Singulärwertzerlegung
Ähnlich der Eigenwertzerlegung
Auch für rechteckige Matrizen definiert
Die (m,n)-Matrix A zerlegen wir in– eine orthogonale (m,m)-Matrix U,– eine orthogonale (n,n)-Matrix V und– eine (m,n)-Diagonalmatrix S.
Bedingung für die Zerlegung: A = USVT
Ausgleichungsrechnung IGerhard Navratil
Bestimmung der Matrizen (1)
Gauß‘sche Transformation
Weil U orthogonal gilt UTU=I
Mit der Abkürzung D=STS=S2 erhalten wir
Rechter Teil entspricht formal einer Eigenwertzerlegung von ATA.
TTTTTTT USVUVSUSVUSVAA
TT VDVAA
Ausgleichungsrechnung IGerhard Navratil
Bestimmung der Matrizen (2)
Somit D Diagonalmatrix mit Eigenwerten von ATA.
S hat die Wurzeln der Eigenwerte in der Hauptdiagonale, mit Nullen aufgefüllt zur richtigen Dimension
V aus Eigenvektoren von ATA.
U über AAT=USVT(USVT)T=USSTUT
D=SST=S2Singular Value Decomposition (SVD)
Ausgleichungsrechnung IGerhard Navratil
Inversion singulärer Matrizen (Generalisierte Inverse)
Moore-Penrose Inverse
Bestimmung über Singulärwertzerlegung:Da nur für reguläre Matrizen (i0) möglich, Eigenwerte gleich Null gestrichen
AAAA
AAAA
AAAA
AAAA
T
T
Ausgleichungsrechnung IGerhard Navratil
Numerische Lösung
Bisher gesehene Verfahren und Formeln sehr rechenintensiv und fehleranfällig
Im Allgemeinen sollte auf vorhandene, getestete Programme zurückgegriffen werden
Im Weiteren einige wichtige Methoden
Ausgleichungsrechnung IGerhard Navratil
Lösung von Gleichungssystemen
• Eliminationsverfahren nach Gauß
• Eliminationsverfahren nach Gauß-Jordan
• LU-Verfahren
• Cholesky-Verfahren
• Gauß-Seidel-Verfahren
Ausgleichungsrechnung IGerhard Navratil
Eliminationsverfahren nach Gauß
Koeffizientenmatrix durch elementare Umformungen in Dreiecks- oder Treppenform bringen liefert eine Unbekannte
Rückwärtseinsetzen in das umgeformte Gleichungssystem
Ausgleichungsrechnung IGerhard Navratil
Eliminationsverfahren nach Gauß-Jordan
Koeffizientenmatrix durch elementare Umformungen in Zeilennormalform gebracht
Direkte Ermittlung der Unbekannten
Ausgleichungsrechnung IGerhard Navratil
LU-Verfahren (LR-Verfahren)
Lower-Upper-Decomposition
(n,n)-Matrix A in obere (U) und untere (L) Dreiecksmatrix zerlegt: A = LU
Ax = (LU)x = L(Ux) = b Ly = b
Vorteil: Zerlegte Matrix A kann mit jedem Konstantenvektor b ohne neuerliche Auflösung verwendet werden
Ausgleichungsrechnung IGerhard Navratil
Cholesky-Verfahren
Anwendung des LU-Verfahrens auf symmetrische, positiv definite Matrizen
A = UTU
Ax = b Ux = s mit
2,1
22
21
2
,1,12211
iiiiiiii
ii
kiiikikiikik
uuuau
u
uuuuuuau
ii
i
kkiki
i u
sub
s
1
1
Ausgleichungsrechnung IGerhard Navratil
Partielle Reduktion mit dem Cholesky-Verfahren (1)
Ax = b aufgespaltet in A11x1 + A12x2 = b1
A21x1 + A22x2 = b2
Erlaubt Aufspaltung der Dreiecksmatrix in
22
1211
U0
UUU
Ausgleichungsrechnung IGerhard Navratil
Partielle Reduktion mit dem Cholesky-Verfahren (2)
Aus A = UTU können wir ableiten:
2222221212
121211
111111
AUUUU
AUU
AUU
TT
T
T
Ausgleichungsrechnung IGerhard Navratil
Partielle Reduktion mit dem Cholesky-Verfahren (3)
2222221212
121211
111111
AUUUU
AUU
AUU
TT
T
T
2222121
1212111
:
:
bxAxA
bxAxA
II
I
111
11212111 sbUxUxU T
1
11TU
III 11121AA
11
11212)(
2
121
112122)(
22
)(22
)(22
bAAbb
AAAAA
bxA
p
p
pp
mit
Ausgleichungsrechnung IGerhard Navratil
Gauß-Seidel-Verfahren
Schwach besetzte Matrix: An vielen Stellen Null
Iterative Verfahren gut geeignetz.B. Gauß-Seidel-Verfahren
Näherungslösung so lange verbessert, bis gewünschte Genauigkeit erreicht
Nachteil: Iteration nicht immer konvergent
Ausgleichungsrechnung IGerhard Navratil
Bestimmung von Eigenwerten und –Vektoren
• QR-Algorithmus – Zerlegung in ortho-gonale Matrix Q und Dreiecksmatrix RA = QR, Iteration Ak+1 = RkQk, Haupt-diagonalelemente von Ak kovergieren zu Eigenwerten
• Jacobi-Verfahren – Symmetrische Matrix wird näherungsweise in eine Diagonal-matrix übergeführt (Eigenwerte in Hauptdiagonale)
Ausgleichungsrechnung IGerhard Navratil
Matrixnorm
Reelle Funktion der Elemente mit der Eigenschaft
||A||0 mit ||A|| = 0 für A=0
Unterschiedliche Normen vorhanden
BABA
BABA
AA
cc
… für quadratische Matrizen
Ausgleichungsrechnung IGerhard Navratil
Wichtige Matrixnormen
• Frobenius/Schur-Norm (Euklidische Norm)
• Spektral-/Hilbert-Norm
m
i
n
kikF
a1 1
2A
maxS
A
maximaler Eigenwert
Ausgleichungsrechnung IGerhard Navratil
Gestörte Gleichungssysteme
Störung eines Gleichungssystems durch kleine Abweichungen eines oder mehrerer Parameter
Frage: Wie wirken sich die Störungen auf die Lösung aus?
bbxxAA
Ausgleichungsrechnung IGerhard Navratil
Beispiel
20201
,1
1
1,,0
1
1
1
a
ay
ax
aRay
x
a
a
gestörtes System:
22 1,
1
1
1,,1
1
1
a
ay
a
ax
aRay
x
a
a
Differenz:2020
1
1,
1 ayy
a
axx
Bei a nahe 1 wirkt sich ein geringer Fehler bereits stark aus!
Ausgleichungsrechnung IGerhard Navratil
Allgemeine Behandlung
AxbAAx 1
Bestimmung von
x
x
Ergebnis: Für kleine Störungen wird der relativeFehler um den Faktor verstärkt.AA 1
Gut konditioniert: kleine Eingangsfehler bewirkenkleine ErgebnisfehlerSchlecht konditioniert: kleine Eingangsfehlerbewirken unverhältnismäßig große Ergebnisfehler
Kondition p der Matrix A
Ausgleichungsrechnung IGerhard Navratil
Kondition einer Matrix
(A)1
Große Konditionszahl weist auf unangenehme numerische Eigenschaften der Matrix hin eventuell Probleme beim Auflösen des Gleichungssystems
Singuläre Matrizen erhalten =Symmetrische Matrizen: (A)=|max|/|min|
Ausgleichungsrechnung IGerhard Navratil
Differentialrechnung
Funktion: Abbildung xf(x)
Differenzenquotient:Steigung der Sekante im Intervall [x,x0]
Differentialquotient (erste Ableitung)
Steigung der Funktion im Punkt x
Lineare Funktionen: Steigung und Sekante in jedem Punkt gleich
000 )()()(
xxxmitx
xfxxf
x
xf
h
xfhxfxf
h
)()(lim)(' 00
0
Ausgleichungsrechnung IGerhard Navratil
Rechenregeln
• Konstantenregel• Faktorregel• Potenzregel• Summenregel• Produktregel• Quotientenregel
• Kettenregel
0'c)('))'(( xfcxfc
1)'( nn xnx )(')('')()( xgxfxgxf ''')()( gfgfxgxf
2
'''
)(
)(
g
gfgf
xg
xf
)('))((''))(( xgxgfxgf
Ausgleichungsrechnung IGerhard Navratil
Numerische Differentiation
Wenn analytische Ableitung aufwendig
Differentialquotient durch Differenzen-quotient angenähert
oder (numerisch besser)
mit 10-8h 10-4
h
xfhxfxf
)()()('
h
hxfhxfxf
2
)()()('
Ausgleichungsrechnung IGerhard Navratil
Höhere Ableitungen
Zweite Ableitung: Erste Ableitung der ersten Ableitung – f‘‘(x)=(f‘(x))‘
Ebenso dritte Ableitung etc.
Allgemein:
n
nn
dx
xfdxf
)()()(
Ausgleichungsrechnung IGerhard Navratil
Taylorreihe (1)
Approximation durch Potenzreihenz.B.
Funktionswerte einer differenzierbaren Funktion f in der Umgebung der Stelle x0 näherungsweise berechenbar
unendliche Potenzreihe (n ): Taylorreihe
)(!
)()(
00
0)(
xRxxk
xfxf n
n
k
kk
n-tes Taylorpolynom
Ausgleichungsrechnung IGerhard Navratil
Taylorreihe (2)
Auch geschrieben als
Voraussetzung: Funktion (n+1)-fach differenzierbar
Entwicklung um x0=0: Maclaurin-Formel
Beispiele: Sinus-/Cosinusentwicklung
Ist x klein: Abbruch nach ersten beiden Gliedern - Linearisierung
nn xxfn
xxfxxfxfxxf )(!
1)(''
!2
1)(')()( 0
)(20000
Ausgleichungsrechnung IGerhard Navratil
Funktionen in mehreren Variablen
Abbildung, die jedem Vektor x eine (reelle) Zahl f(x) zuordnet
Funktion in n Variablen entsprechend der Dimension des Vektors
Ausgleichungsrechnung IGerhard Navratil
Partielle Ableitungen
Alle Parameter außer xi einer Funktion in n Variablen als Konstante angesehen
Ableitung nach diesem Parameter heißt partielle Ableitung (erster Ordnung) nach xi an der Stelle x
Analog partielle Ableitungen höherer Ordnung
Ausgleichungsrechnung IGerhard Navratil
Totales Differential
Totales Differential der Funktion f an der Stelle x:
nn
dxx
xfdx
x
xfdx
x
xfdf
)()()(
22
11
Ausgleichungsrechnung IGerhard Navratil
Taylorentwicklung für Funktion in zwei Variablen
y
y
yxfx
x
yxfyxfyyxxf
),(),(
!1
1),(),( 0000
0000
n
n
Ryy
yxfx
x
yxf
n
yy
yxfx
x
yxf
)(
0000
)2(
0000
),(),(
!
1
),(),(
!2
1
Wobei die Klammerausdrücke nach dem binomischen Lehrsatz aufzulösen sind:
n
k
kknn bak
nba
0
pmp
mpmp
yx
f
y
f
x
f
und folgendes gilt:
Ausgleichungsrechnung IGerhard Navratil
Linearisieren einer Funktion in mehreren Variablen
Taylorentwicklung
Abbruch nach der ersten Ableitung
Anwendbar nur in einer entsprechend kleinen Umgebung um x0 (Glieder höherer Ableitungen vernachlässigbar klein)
Ausgleichungsrechnung IGerhard Navratil
Differentiation von Matrizenfunktionen
Formal gleich bzw. ähnlich den gewöhnlichen Differentiationsregeln
Hier nur für Ausgleichung wichtige Fälle
Differentialvektor: dxT=(dx1 dx2 … dxn)
f=aTx df=aTdx
Ausgleichungsrechnung IGerhard Navratil
Ableitung der Bilinearform
Bilinearform: Produkt der FormZeilenvektor-Matrix-Spaltenvektor
f=xTAl df = dxTAl = lTATdx
Sonderfall: Vektoren identisch – Quadratische Form
f=xTAx df = dxTAx + xTAdx = xT(AT+A)dx
Symmetrische Matrizen: df = 2xTAdx
Ausgleichungsrechnung IGerhard Navratil
Optimierung
Festlegung von Parametern so, dass eine Funktion der Parameter einen extremen Wert annimmt (Maximum oder Minimum)
z.B. kürzester Weg zwischen zwei Punkten, maximale Fläche bei gegebenem Umfang
Eindimensionaler Fall: Erste Ableitung gleich Null setzen – liefert Extremwert
Mehrdimensionaler Fall: Ersten partiellen Ableitungen gleich Null gesetzt
Ausgleichungsrechnung IGerhard Navratil
Unterscheidung Maximum-Minimum
Zweite Ableitung
Bei Funktion in mehreren Variablen: Hesse-Matrix
• positiv definit: Minimum(alle Eigenwerte positiv)
• negativ definit: Maximum (alle Eigenwerte negativ)
22
2
12
221
2
21
2
x
f
xx
f
xx
f
x
f
H
Ausgleichungsrechnung IGerhard Navratil
Nebenbedingungen
Gesucht: lokale Extrema von f(x1…xn), Bedingung g(x1…xn) muss erfüllt sein
• f Zielfunktion• g Nebenbedingung
Ausgleichungsrechnung IGerhard Navratil
Beispiel (1)
f(x1,x2)=x12+2x2
2
g(x1,x2)=x1+x2-3=0
Lösung: x1 in g durch x2 ausdrücken und in f einsetzen – liefert quadratische Gleichung in einer Unbekannten
Diese einfache Lösung nicht immer möglich!
Ausgleichungsrechnung IGerhard Navratil
Beispiel (2)
Graphische Lösung: Nebenbedingung berührt Niveaulinie
Ausgleichungsrechnung IGerhard Navratil
Beispiel (3)
Mathematisch: Nebenbedingung und Niveaulinie in diesem Punkt parallel
Somit: Gradienten von f und g haben gleiche Richtung:
bzw.
)()( agaf
0)()( agaf
Ausgleichungsrechnung IGerhard Navratil
Beispiel (4)
Somit erhalten wir das Gleichungssystem
0,,
0
0
1
11
n
nn
xxg
x
g
x
f
x
g
x
f
Ausgleichungsrechnung IGerhard Navratil
Beispiel (5)
Formal gleiche Lösung: Lagrange-Funktion
nnn xxgxxfxxL ,,,,,,, 111 Lagrange-Multiplikator
Ableitung der Lagrange-Funktion nach allenVariablen x1, …, xn und und gleich Null setzen liefert dasselbe Gleichungssystem wie vorher.
Ausgleichungsrechnung IGerhard Navratil
Zusammenfassung (1)
Gleichungssysteme können mit Matrizen einfach angeschrieben und behandelt werden
Eigenschaften durch Kennzahlen beschrieben (Determinante, Rang, etc.)
Linearisieren von Funktionen geschieht mit Taylorreihen
Zum Optimieren mit Nebenbedingungen nimmt man die Lagrange-Funktion
Ausgleichungsrechnung IGerhard Navratil
Zusammenfassung (2)
Vorsicht bei numerischen Problemen: Die Hälfte aller vom Computer darstellbarer Zahlen liegt zwischen -1 und 1
Schlechte Numerik kann den Rechengang empfindlich stören, daher die Ergebnisse IMMER kritisch hinterfragen