View
12
Download
0
Category
Preview:
Citation preview
3.9. Die QR-Zerlegung einer Matrix
Schon vorher haben wir bemerkt:
- cond(U) in der Gauß-Elimination ev. groß, auch
bei kleinem cond(A);
- falls A schlecht konditioniert: was ist der Rang von A?
Welche Pivotelemente werten wir als 0?
- cond(AT A) oft sehr groß.
71
Andererseits: cond(QA) = cond(A), falls Q orthogonal.
Also sind orthogonale Matrizen sehr gut für äquivalente
Umformungen von A geeignet (vgl. LU-Zerlegung).
Außerdem gilt: Q–1 = QT .
Also sind Gleichungssysteme in Q sehr leicht zu lösen.
72
Versuche daher, analog zur LU-Zerlegung A=LR ,
eine Zerlegung der Form
A = QR
zu bestimmen mit
Q orthogonal
R obere Dreiecksmatrix
Vorteile:
- numerisch stabiler als LU
- ähnliche Kosten
- Systeme in Q und R leicht zu lösen
73
)cos()sin(
)sin()cos(
G
;10
01
)(cos)(sin)sin()cos()cos()sin(
)cos()sin()sin()cos()(sin)(cos
)cos()sin(
)sin()cos(
)cos()sin(
)sin()cos(
22
22
GGGGT
3.9.2 Elementare orthogonale Matrizen
Orthogonale 2 x 2 – Matrix :
heißt Givensreflexion. Denn
Frage: orthogonale 1 x 1 – Matrix?
74
Wilkinson, Givens, Forsythe, Householder, Henrici, F.L.Bauer
75
)cos()sin(
)sin()cos(
Alternativ Givensrotation:
0)cos()sin()cos()sin(~!
2111
21
11
21
aa
a
aa
Dazu muss gelten:
2221
1211
~~
~~~
aa
aaGAA
G ist eindeutig bestimmt durch den ‘Winkel’ .
Bestimme nun so, dass
obere Dreiecksmatrix wird.
76
;)cot(21
11
a
a
21
11
a
aarcctg
11
21
a
aarctg
Lösung:
oder
Ist a21 =0, so ist keine weitere Transformation nötig!
Numerisch stabilere Art der Berechnung :
(a21 oder a11 könnten fast 0 sein):
;)sin(;)cos(;)( 21112
21
2
1111
aa
aaasign
;1;0)cos()sin(
2
11
2
2121
1111
212111
aaa
aa
aaa
3.9.3. Givens-Reflexion für den
allgemeinen n x n – Fall:
n-dimensionale Givens-Reflexion ist im Wesentlichen wie
die Einheitsmatrix, bis auf den gerade zu betrachtenden
2 x 2 – Block.
Dieser Block wird wieder - wie oben definiert - abhängig
von bestimmt.
77
Man eliminiert wieder in der ersten Spalte a2,1,…,am,1,
und dann entsprechend in der zweiten Spalte die
Unterdiagonale, usw. wie bei Gauss.
78
i
j
Gij
1
1
)cos()sin(
1
1
)sin()cos(
1
1
j i
Gestalt der allgemeinen Givens-Matrix
Zur Elimination eines Elementes aij der Matrix A
multiplizieren wir Gij A .
Dieses Produkt verändert nur die i-te und die j-te Zeile von A.
Es genügt, vom Gesamt-System nur diesen 2 x 2 – Teil zu
betrachten. Also muss wieder
gesetzt sein wie oben. (1 j und 2 i )
79
ij
jj
a
aarcctg
cs
scG
I
GG
)cos()sin(
)sin()cos(,
0
021
Mit einer solchen Matrix G21 wird dann im ersten Schritt
a21 zu Null gemacht.
verändert nur j-te und i-te Zeile;
i-te Zeile: für k=j,...,n
speziell: soll Null werden
Legt daher fest.
80
ikjkik casaa
!0 ijjjij casaa
Genauere Analyse eines allgemeinen Eliminationsschritts:
AG
aa
aa
cs
sc
i
j
ji
iiij
jijj
,
0
00
0
j-te Zeile: für k=j,...,n
mit c und s zu obigen ikjkjk sacaa
Keine Pivotszeile!
k
81
13121 ,,, nGGG
13121 ,,, naaa
24232 ,,, nGGG 221 , nnnn GG 1nnG
24232 ,,, naaa 221 , nnnn aa1nna
Verwende der Reihe nach
, ..... , , und
um , ..... , , und
zur Bearbeitung der ersten Spalte,
also um zu Null zu machen,
und danach
zu Null zu machen.
Jeweils nötig ist eine Multiplikation mit Givens-Reflexion
G i,j , i=1,...,n-1 und j=i+1,...,n.
Also benötigt man insgesamt n(n-1)/2 Givensreflexionen
um eine quadratische n x n –Matrix auf Dreiecksgestalt zu
transformieren. 82
Die Reihenfolge, in der die aj,i zu Null gemacht werden,
ist gegeben durch:
.2/)1(321
.
.2
.1
..
nnnn
n
83
2112,12,1,: GGGGGQ nnnnnnn
T
RAGGGGGAQ nnnnnnn
T 2112,12,1,
Man benutze also immer das Diagonalelement ajj und eine
Kombination von i-ter/j-ter Zeile, um aij zu Null zu machen.
mit einer oberen Dreiecksmatrix R.
1,121 nnn GGGQ ij
T
ij GG und A=Q*R.
Daher ist
, da
Q ist gegeben durch die einzelnen Gij;
jedes Gij ist eindeutig gegeben durch das ij, das nötig war,
um genau ein aij zu eliminieren.
Wie bei der Gauss-Elimination eliminiert man also mit den
Diagonalelementen der Reihe nach sämtliche
Unterdiagonalelemente.
84
Genauso kann man für eine m x n Matrix A (m>n) mit
rank(A)=n eine QR- Zerlegung berechnen
A = Q . R
Der Vorteil der QR-Zerlegung:
cond(A) = cond(QR) = cond(R)
Gut für schlecht konditionierte Systeme
Anwendbar auf rechteckige Systeme
Andere Orthogonalisierungsverfahren:
- Gram-Schmidt (orthonormalisiere Vektoren)
- Householder (erzeuge in einem Schritt eine
ganze Nullspalte). H = I – 2 u uT
R ist obere Dreiecksmatrix der R1
Dimension m x n und vollen R =
Ranges n.
85
3.9.4. Anwendung bei Linearer Ausgleichsrechnung:
22
22
minmin
minmin
bQRxbQRxQ
bQRxbAx
T
x
T
x
xx
da Q orthogonal und euklid’sche Norm.
0
86
211min
2
11min
1min
~~~
~
00
2
2
2
2
2
2
2
2
bbxRb
bxRbQx
Rxxx
T
11
~bxR
Das obige Minimum erhält man wegen
aus der Lösung des Dreieckssystems
22
~bDer Wert des Minimums ist gegeben durch
.
87
Beispiel: QR-Zerlegung für Least Squares:
Erster Schritt: a21 0 :
2
2
min
1
0
0
10
11
11
min bAxx xx
4/,2/1 sc
mit
10
00
22
1010
11
11
100
0
0
cscs
scsc
cs
sc
88
00
10
22
0
0
22
10
00
22
0
0
001
c
s
cs
sc
2/,1,0 sc
Zweiter Schritt: a32 0 :
mit
00
10
22
10
11
11
100
02/12/1
02/12/1
010
100
001
QT A = R
89
010
2/102/1
2/102/1
QAlso
22
22
1
0
10
22min
0
1
0
10
22
min
1
0
0
02/12/1
100
02/12/1
00
10
22
min
1
0
0
min
xx
xAx
xx
xx
Anwendung auf Minimierungsproblem :
Lösung x als Lösung des Dreiecksgleichungssystems:
90
1
1x
In diesem Fall liefert x sogar eine genaue Lösung von Ax=b,
da der Fehlerterm ||b2|| gleich Null ist.
QR-Zerlegung ist in dieser Form anwendbar für beliebige
rechteckige Matrix A, so lange A vollen Rang besitzt.
Kosten des QR-Verfahrens mit Givens für n x n – Matrix:
2n3 + O(n2) (also teuerer als Gauss-Elimination mit 2n3/3)
Ein Eliminationsschritt bei Spalte k:
(2 mult +1 add)2k = 6k flop
Insgesamt:
Bei m x n – Matrix mit m>n und Rang(A)=n: n2 (3m-n)
91
2
1
23 )(26*)1(nk
nOnkk
Anwendung des QR-Verfahren bei
- schlecht konditioniertem Gleichungssystem
- überbestimmtem Gleichungssystem mit vollem Rang
(an Stelle der Normalgleichung), wie oben beschrieben
- allgemeinem nichtquadratischen System in der Form
QAP = R mit Permutation P zum Vertauschen von Spalten.
(P ist nötig, um einen Block vollen Ranges nach vorne/oben zu
transportieren)
Beispiel:
92
10
00
00
- Entdeckung fast linear abhängiger (eigentlich
überflüssiger) Gleichungen oder Unbekannter
(numerische Bestimmung des Rangs von A)
- Reduktion der Matrix auf den wesentlichen Teil
(Noise-reduction)
93
SQRQSRQSR
QQA 111210
)(
3.10 Regularisierung
In vielen praktischen Anwendungen hat man zwar ein
überbestimmtes lineares Gleichungssystem vorliegen, aber so,
dass die Normalmatrix ATA auch noch (fast) singulär ist!
Dadurch erhält man bei der Lösung dieses Problems einen
Vektor x, der extrem groß ist:
Ist in Bx=b die Matrix B (fast) singulär
||inv(B)|| sehr groß
|| x || = || inv(B)*b || sehr groß
94
Durch Mess/Rundungsfehler enthält aber die rechte Seite b
viele kleine Störungen (noise, Rauschen), die in der
berechneten Näherungslösung x dann sehr groß werden, so
dass - selbst bei exakter Rechnung - x unbrauchbar ist.
95
bBxbBbBbbBx 1111 )(~
Störanteil
Viel größer als x
96
2
2
22
2min xbAxx
Ausweg:
Suche ‚vernünftige’ Least Squares Lösung durch
Minimierung mit Nebenbedingung:
‚x soll nicht zu groß werden’.
bAxIAA TT 2
Minimerung Nullstelle der Ableitung führt auf das sog.
regularisierte Gleichungssystem
Idee: Verschiebe ATA durch Aufaddieren von 2 I , so dass
die neue Matrix besser konditioniert ist.
Dann ist
Daher führen in dem neuen Gleichungssystem die Rausch-
komponenten in b nicht mehr zu einem extremen Anwachsen
der Lösung x.
Man weiß, dass die gesuchte Lösung x nicht zu groß sein
kann, und dies wird durch die Regularisierung gewährleistet.
97
22
2 )( AAinvIAAinv TT
γ heißt Regularisierungsparameter und die hier
beschriebene Methode heißt
Tikhonov-Regularisierung.
Regularisierung muss häufig angewendet werden bei
Problemen der Bildverarbeitung
(z.B. bei verrauschten, unscharfen Bilder)
98
- Gauss-Elimination,
- Normalengleichung und QR-Zerlegung,
- Regularisierung
sind die wichtigsten Werkzeuge zur direkten Lösung von
Ax=b.
Regularisierende Zusatzbedingungen:
- Beschränktheit der Lösung ||x||
- Ev. Dünnbesetztheit der Lösung (x1,0,…0,xk,0,…,0)
- Ev. Glattheit der Lösung Δxi ≈ 0
- Nähe zu schon bekannter Näherungslösung ||x-xapprox||
IV. Interpolation und Quadratur
4.1. Interpolation
4.1.1. Beispiel: Interpolation mit Tafelwerken für exp, sin, cos, log
Gesucht: exp(0.454) ;
Tabelliert: exp(0.45) und exp(0.46)
Lineare Interpolation.
1
x:
exp(x):
0.42
...
0.43
...
0.44
...
0.45
1.5683
0.46
1.5841
4.1.2. Allgemeine Problemstellung:
Gegeben:
Punktepaare (xj, yj), j=0,1,...,n , paarweise verschieden,
und linear unabhängige Funktionen gk(x) , k=0,1,...,n
Gesucht: Koeffizienten ck , k=0,1,...,n mit
für j=0,1,...,n
2
n
k
jjkkj yxgcxG0
!
)()(
nnnnn
n
y
y
c
c
xgxg
xgxg
00
0
000
)()(
)()(
(n+1)(n+1) lineares Gleichungssystem
3
Interpolation führt auf quadratisches Gleichungssystem!
Genauso viele Bedingungen wie Freiheitsgrade.
Man unterscheide Interpolation und Approximation!
Beispiel zu Approximation:
Ausgleichsgerade führt auf überbestimmtes Gleichungssystem
(Normalgleichung, QR)
4.1.3. Spezialfall Polynom-Interpolation:
Ansatzfunktionen gk(x) sind Polynome xk
Gesucht: Koeffizienten ck , k=0,1,...,n mit
für j=0,1,...,n
4
n
k
j
k
jkj yxcxp0
!
)(
nn
n
nn
n
y
y
c
c
xx
xx
0000
1
1
n+1 Gleichungen für n+1 Unbekannte: Teuer! O(n3)
4.1.4. Lösung mit Lagrange-Polynomen
Definiere geschickt Basis-Polynome:
n+1 Polynome vom Grad n, besser als 1, x, x2, .., xn
5
)())(()(
)())(()(:)(
110
110
,0 njjjjjj
njjn
jii ij
ij
xxxxxxxx
xxxxxxxx
xx
xxxL
jifalls
jifallsxL ij
0
1)(
Eigenschaften der Lagrange-Polynome: Grad n mit
n
jjj
xLcxp0
)()(Gesucht
das die Interpolationsbedingungen erfüllt.
6
nnnnnn
n
y
y
c
c
c
c
xLxL
xLxL
000
0
000
10
01
)()(
)()(
Aus diesen Eigenschaften ergibt sich zur Lösung des
Interpolationsproblems ein lineares Gleichungssystem für die
Koeffizienten:
1 -
0 -
Die Lösung ist cj = yj ; daher ist das Interpolationspolynom:
denn es ist .
Damit ist die Existenz eines interpolierenden Polynoms gezeigt!
Eindeutigkeit?
7
Hauptsatz der Algebra:
Jedes Polynom p(x) vom Grad n kann als Produkt von n
linearen Faktoren (den ev. komplexen Nullstellen zk )
geschrieben werden in der Form
)())(()(21 n
zxzxzxxp
n
j
jj xLyxp0
)()(
iiii
n
j
ijji yxLyxLyxp
)()()(0
Annahme: Es gibt zwei Polynome p und q vom Grad <= n,
die beide die Interpolationsbedingungen erfüllen.
Definiere neues Polynom h(x) := p(x) - q(x) . Dann gilt
und für j=0,1,...,n
8
)())(()(21 n
zxzxzxxh
0)()(:)( jjj xqxpxh
Lagrange zur Lösung der Interpolation nicht geeignet,
da numerisch problematisch und teuer.
Daher hat das Polynom h(x) den Grad n und n+1 Nullstellen.
Aus dem Hauptsatz der Algebra folgt daher, dass
= 0 sein muss, und daher ist h(x) 0, oder
p(x) q(x).
Also es existiert genau ein Interpolationspolynom!
9
Setze dazu als das interpolierende Polynom vom
Grade l, das genau an den Stellen die
Interpolations-Bedingungen erfüllt.
Zur Bestimmung von verwende die interpolierenden
Polynome vom Grade l-1 und , die
zu den Stützstellen , bzw. , gehören.
liii xxx ,,, 1
lii xx ,,1 1,, lii xx
4.1.5. Berechnung des Interpolationspolynoms
Löse nicht das lineare Gleichungssystem, da dies zu teuer ist!
Außerdem wird oft nur der Wert des Polynoms an einer einzigen
Stelle gesucht!
Idee: Berechne induktiv interpolierende Polynome für immer
mehr Stützstellen.
10
)()()()()(
)( 1,,,,1
,,
ili
liililiii
liixx
xpxxxpxxxp
li
ili
liilililii y
xx
yxxxp
0)()(,,
Wesentliche Formel :
i
ili
iliiilii y
xx
yxxxp
)(0)(,,
Beweis: Nachprüfen der Interpolationsbedingung.
und für alle anderen j mit i < j < i+l :
j
ili
jlijjij
jlii yxx
yxxyxxxp
)()()(,,
Wegen der Eindeutigkeit des interpolierenden Polynoms ist
jedes der so definierten Polynome genau die eindeutige
Lösung des jeweiligen Interpolationsproblems!
Daher ist die gesuchte Lösung!
11
)(,, xp lii
Anwendung der Formel (*) zur punktweisen Auswertung des
Interpolationspolynoms an einer Stelle :
Eingabe: Stützwerte (xj , yj ), j=0,...,n und Stelle ;
Ausgabe: .
x
x
?)( xp
)(,, xp lii
xTableau-artige Berechnung der Interpolationspolynome
aufsteigenden Grades, aber nur an der Stelle .
Erste Spalte sind konstante interpolierende Polynome, also
genau die jeweils vorgegebenen Werte yi .
Zweite Spalte sind interpolierende lineare Polynome zu
jeweils zwei benachbarten Stützstellen.
Letzte Spalte enthält das interpolierende Polynom zu allen
vorgegebenen Stützstellen. 12
Neville-Tableau:
Neue Stützstelle x_4 mit Wert y_4 kann in das Tableau
eingefügt werden und führt zu einer neuen ‚Zeile’ und einer
neuen Endspalte p_01234(x).
Auswertung des Tableaus jeweils nur an einer festen Stelle
x möglich.
13
1,0 00 yx
3,1 11 yx 2,3 22 yx
Beispiel: ,
,
Auswertung des interpolierenden Polynoms an der Stelle x=2
mit Lagrange, bzw. Neville-Tableau:
14
)30)(10(
)3)(1()(0
xxxL
)31)(01(
)3)(0()(1
xxxL
)13)(03(
)1)(0()(
2
xxxL
Lagrange:
, und
3
10
3
123
3
1)2(2)2(3)2(1)2( 210012 LLLp
153
10
03
5)32(2
5)02()2(012
pund daher auch
2
5
13
3)32(2)12()2(12
p
501
1)12(3)02()2(01
p
Neville-Tableau:
Da nach (*)
01
011001
)2()2()2()2()2(
xx
pxpxp
16
Folge von Interpolationspolynomen
zu 3 und 4 Stützstellen:
interpol.m
Recommended