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