College 7 - TU Delft

Het orthogonaliseringsproces van Gram-Schmidt
Voor het berekenen van een orthogonale projectie van een vector y op een deelruimte W van
Rn is een orthogonale basis {u1 , . . . , up } zeer gewenst. De orthogonale projectie is dan gelijk
aan de som van de orthogonale projecties langs de (orthogonale) basisvectoren :
y · u1
y · up
projW y =
u1 + . . . +
up .
u1 · u1
up · up
Een interessante vraag is nu : Hoe kunnen we een orthogonale basis van een deelruimte W
construeren als we slechts een willekeurige (niet-orthogonale) basis kennen ? Hiervoor dient
het orthogonaliseringsproces van Gram-Schmidt :
Stelling 1. Stel dat {x1 , . . . , xp } een basis is van een deelruimte W van Rn . Definieer dan :
v 1 = x1
v2
v3
vp
x2 · v 1
= x2 −
v1
v ·v
1 1
x3 · v 1
x3 · v 2
= x3 −
v1 −
v2
v1 · v1
v2 · v2
..
.
xp · v 1
xp · v 2
xp · v p−1
= xp −
v1 −
v2 − . . . −
v p−1 .
v1 · v1
v2 · v2
v p−1 · v p−1
Dan geldt : {v 1 , . . . , v p } is een orthogonale basis van W .
Opmerking. In elke stap wordt van de basisvector xk de orthogonale projecties langs de
nieuwe (orthogonale) basisvectoren v 1 , . . . , v k−1 afgetrokken. De resulterende vector v k staat
dan loodrecht op alle vectoren v 1 , . . . , v k−1 , die al orthogonaal zijn.
Bovendien geldt : Span{v 1 , . . . , v k } = Span{x1 , . . . , xk } voor iedere k.
Een orthogonale basis kan eenvoudig omgezet worden naar een orthonormale basis door elke
vector te normeren (of schalen) : als {v 1 , . . . , v p } een orthogonale basis van W is, dan is
1
v voor alle i = 1, 2, . . . , p een orthonormale basis van W .
{u1 , . . . , up } met ui =
||v i || i
Voorbeeld 1. Stel W = Span{x1 , x2 , x3 , x4 } met





1
0
1
 −1 
 1 
 1




x1 = 
 0  , x2 =  2  , x3 =  1
1
−1
1





en

2
 1 

x4 = 
 3 ,
1
dan is W dus een deelruimte van R4 . We bepalen eerst een basis van W :

 
 
 
1
0 1 2
1
0 1
2
1 0
1
2
 −1



1 1 1 
1 2
3 
2
3 

∼ 0
∼ 0 1
∼
 0
2 1 3   0
2 1
3   0 0 −3 −3  
1 −1 1 1
0 −1 0 −1
0 0
2
2
1
1
0
0
0
0
1
0
0
1
2
1
0

2
3 
.
1 
0
Hieruit volgt dat {x1 , x2 , x3 , x4 } lineair afhankelijk is, dat x4 ∈ Span{x1 , x2 , x3 } en dat
{x1 , x2 , x3 } lineair onafhankelijk is (in elke kolom een pivot). Dus : {x1 , x2 , x3 } is een basis
van W . Nu passen we het orthogonaliseringsproces van Gram-Schmidt toe :


1
 −1 

v 1 = x1 = 
 0 ,
1


1
 −1 

0 1 2 −1 


 0  1 
0
 −1 
 1 
1
x2 · v 1
−

v 2 = x2 −
v1 = 


 0 


2
v1 · v1
1
 −1 
−1
1

1 −1 0 1 
 0 
1



 





0
1
0
1
2
 1  0 − 1 + 0 − 1  −1   1  2  −1  1  1 



 




= 
 2  − 1 + 1 + 0 + 1  0  =  2  + 3  0  = 3  6 ,
−1
1
−1
1
−1


1
 −1 

1 1 1 1 
 
 0   1 
1
 −1 
 1 
1
x3 · v 1
x3 · v 2

−
v 3 = x3 −
v1 −
v2 = 


 0 


1
v2 · v2
v1 · v1
1
 −1 
1
1

1 −1 0 1 
 0 
1


2
 1 

1 1 1 1 
 6   2 
 1 
−1

−


 6 
2
 1 
−1

2 1 6 −1 
 6 
−1
 




1
1
2
 1  1 − 1 + 0 + 1  −1 
 1 
2
+
1
+
6
−
1





= 
 1  − 1 + 1 + 0 + 1  0  − 4 + 1 + 36 + 1  6 
1
−1
1
 



  




1
1
2
1
1
2
 1  1  −1 
  



8 
4 



 1   1  1  −1 
 1 
= 
 1  − 3  0  − 42  6  =  1  − 3  0  − 21  6 
1
1
−1
1
1
−1
2




21 − 7 − 8
6
2

 24  1  8
1 
1
21
+
7
−
4
=
= 


21  21 − 0 − 24  21  −3  7  −1
21 − 7 + 4
18
6

=


.

Omdat de lengte (of norm) van de vectoren niet van belang is voor de orthogonaliteit volgt
nu dat
 
 


1
2
2
 −1   1   8 
 
 

{
 0  ,  6  ,  −1 }
1
−1
6
een orthogonale basis van W is. Dat deze drie vectoren orthogonaal zijn kan eenvoudig
gecontroleerd worden door de (drie) onderlinge inwendige producten uit te rekenen.
Hieruit kan eenvoudig een orthonormale basis geconstrueerd worden door de drie vectoren te
normeren :




1
2
√
√


 −1 
√
√
 || = 1 + 1 + 0 + 1 = 3, ||  1  || = 4 + 1 + 36 + 1 = 42
|| 
 0 
 6 
−1
1
en
Dus :


2
√
 8 
√

|| 
 −1  || = 4 + 64 + 1 + 36 = 105.
6



1
2



1
−1  1  1
{√ 
,√ 

0 
6
3
42
1
−1



2



 , √ 1  8 }

105  −1 
6
is een orthonormale basis van W .
Het orthogonaliseringsproces van Gram-Schmidt kan gebruikt worden om een QR-ontbinding
van een matrix te maken :
Stelling 2. Als A een (m × n)-matrix is met lineair onafhankelijke kolommen, dan kan A
geschreven worden als A = QR, waarbij Q een (m × n)-matrix is waarvan de kolommen een
orthonormale basis van Col A vormen en R een inverteerbare (n × n)-bovendriehoeksmatrix.
Bewijs. Het bewijs volgt meteen uit de constructie. Omdat de kolommen van A lineair
onafhankelijk zijn vormen deze een basis van Col A. Passen we het proces van Gram-Schmidt
toe op die kolommen van A dan vinden we uiteindelijk een orthonormale basis van Col A.
De vectoren van deze basis vormen de kolommen van Q. Dat R een bovendriehoeksmatrix is
volgt uit het feit dat de eerste k kolommen van A lineaire combinaties zijn van de eerste k
kolommen van Q. Stel nu dat Rx = o, dan volgt Ax = QRx = Qo = o. Omdat de kolommen
van A lineair onafhankelijk zijn volgt hieruit dat x = o. Dit betekent dat Rx = o slechts de
triviale oplossing x = o heeft en dat betekent dat R inverteerbaar is.
3
Opmerking. De matrix Q wordt verkregen met behulp van het proces van Gram-Schmidt.
Omdat de kolommen van Q orthonormaal zijn geldt QT Q = I. Hieruit volgt dat QT A =
QT (QR) = (QT Q)R = IR = R. De matrix R kan dus heel eenvoudig gevonden worden uit
R = QT A.


1
0 1
 −1
1 1 
. In voorbeeld 1 hebben we gezien dat de kolommen
Voorbeeld 2. Stel A = 
 0
2 1 
1 −1 1
van A lineair onafhankelijk zijn en dat






1
2
2




1  −1 
 , √1  1  , √ 1  8 }
{√ 
3 0 
42  6 
105  −1 
1
−1
6
een orthonormale basis van Col A is. Dus :



Q=

√1
3
− √13
0
√1
3
√2
42
√1
42
√6
42
− √142
√2
105
√8
105
1
− √105
√6
105
√
√
√
70
2
5
2
√
√
√2


1  − 70

√ 5 8√ 2
= √

0
6

210
√
√5 −√2
70 − 5 6 2




.

Voor R vinden we dan
R = QT A =
=

√
√ 
 √
1
0
70 − √70
√0
√70  −1
1  √
1
√
2√ 5
5 6√5 −√5  

√
0
2
210
2 2
8 2 − 2 6 2
1 −1
√
√ 
 √
3 70 −2 √70
√70
1 
√
0
14 5 8√5  .
210
0
0 15 2

1
1 

1 
1
Kleinste-kwadratenproblemen
Een stelsel vergelijkingen Ax = b is alleen oplosbaar als b ∈ Col A. In de praktijk komt het
vaak voor dat zo’n stelsel vergelijkingen niet oplosbaar is, bijvoorbeeld door meetfouten en/of
afrondfouten. Dit is vaak erg onbevredigend. Om het stelsel oplosbaar te maken vervangt men
dan de vector b door een vector die wel in Col A zit. Om de ’fout’ daarbij zo klein mogelijk te
houden wordt d´ıe vector in Col A gekozen die het dichtst bij b ligt : de (orthogonale) projectie
van b op Col A. Een oplossing van een op deze manier verkregen stelsel vergelijkingen heet
een kleinste-kwadratenoplossing van Ax = b :
Definitie 1. Stel dat A een (m × n)-matrix is en b ∈ Rm . Dan heet x
ˆ ∈ Rn een kleinstekwadratenoplossing van Ax = b als ||b − Aˆ
x|| ≤ ||b − Ax|| voor alle x ∈ Rn .
4
Het vinden van zo’n kleinste-kwadratenoplossing komt dus neer op het minimaliseren van
de afstand ||b − Ax|| of van ||b − Ax||2 , een som van kwadraten. Dat verklaart de term
”kleinste-kwadratenprobleem”.
We gaan nu op zoek naar zo’n kleinste-kwadratenoplossing. Stel dat ˆb = projCol A b, dan
geldt dat Ax = ˆb oplosbaar is. Stel dat x
ˆ een oplossing is, dan geldt dus : Aˆ
x = ˆb.
Dan geldt dat b − ˆb loodrecht staat op Col A. Dus : b − Aˆ
x staat loodrecht op elke kolom van
x) = 0 oftewel aTj (b − Aˆ
x) = 0. Dit
A. Als aj zo’n kolom van A is, dan geldt dus : aj · (b − Aˆ
geldt voor iedere j, dus :
x) = o
AT (b − Aˆ
⇐⇒
AT b − AT Aˆ
x=o
⇐⇒
AT Aˆ
x = AT b.
Dit laatste stelsel vergelijkingen wordt aangeduid met de term normale vergelijking(en) :
Stelling 3. De verzameling van kleinste-kwadratenoplossingen van Ax = b komt overeen met
de niet-lege verzameling van oplossingen van de normale vergelijking(en) : AT Aˆ
x = AT b.
Bewijs. Hierboven hebben we al gezien dat een kleinste-kwadratenoplossing van Ax = b
moet voldoen aan de normale vergelijkingen AT Aˆ
x = AT b. Omgekeerd, als x
ˆ een oplossing
T
T
is van A Aˆ
x = A b, dan staat b − Aˆ
x dus loodrecht op alle rijen van AT en dus op alle
kolommen van A. Dus : b − Aˆ
x staat loodrecht op Col A. Dit betekent dat b = Aˆ
x + (b − Aˆ
x)
een ontbinding van b is met Aˆ
x ∈ Col A en b − Aˆ
x ⊥ Col A. Aangezien zo’n ontbinding uniek
is geldt dus dat Aˆ
x de orthogonale projectie van b op Col A moet zijn. Dus : Aˆ
x = ˆb en dat
betekent dat x
ˆ een kleinste-kwadratenoplossing van Ax = b is.
Opmerking. Een kleinste-kwadratenoplossing is uniek als de matrix AT A inverteerbaar is.
Dit is het geval als de kolommen van A lineair onafhankelijk zijn. We zullen dit niet bewijzen.
De afstand ||b − ˆb|| = ||b − Aˆ
x|| wordt wel de kleinste-kwadratenfout genoemd.


 
1
1 0



1 1
2 , dan is Ax = b niet oplosbaar (ga na !).
Voorbeeld 3. Als A =
en b =
2
0 1
We vinden nu


 
1 0
1
1
1
0
2
1
1
1
0
T
T
 1 1 =
 2 = 3 .
A A=
en A b =
0 1 1
1 2
0 1 1
4
0 1
2
Dus :
T
T
A Aˆ
x=A b :
2 1 3
1
2
∼
1 2 4
0 −3
4
3 0
−5 ∼
0 3
2
5
=⇒
1
x
ˆ=
3
Er geldt dus dat

 

1 0 2
1
1
2
ˆb = Aˆ
x=  1 1 
=  7 
5
3
3
0 1
5
de orthogonale projectie van b op Col A is. De kleinste-kwadratenfout is dus
 

 

1
2
1
1
1
1√
||b − ˆb|| = ||b − Aˆ
x|| = ||  2  −  7  || = ||  −1  || =
3.
3
3
3
5
1
2
5
2
5
.


 
1 0 1
1
 1 0 1 
 3 

 
Voorbeeld 4. Stel dat A = 
 0 1 1  en b =  1 . Dan zijn de kolommen van
0 1 1
3
A duidelijk afhankelijk (de derde kolom is de som van de eerste twee kolommen). Ook is
onmiddellijk duidelijk dat Ax = b niet oplosbaar is. We vinden nu :



 1 0 1


1 1 0 0 
2 0 2

1 0 1  
0 2 2 
AT A =  0 0 1 1  
 0 1 1 =
1 1 1 1
2 2 4
0 1 1
en

 
1
1 1 0 0  
4
3   
4 .
AT b =  0 0 1 1  
=
 1 
1 1 1 1
8
3



Dus :
 
2 0 2 4
2 0 2
AT Aˆ
x = AT b :  0 2 2 4  ∼  0 2 2
2 2 4 8
0 2 2

 
4
1 0 1
4 ∼ 0 1 1
4
0 0 0

2
2 .
0
In dit geval zijn er dus oneindig veel oplossingen :

x1 = 2 − x3



  




2 − x3
2
−1

x2 = 2 − x3
=⇒ x
ˆ =  2 − x3  =  2  + x3  −1  .


x3
0
1



x3 is vrij
De orthogonale projectie van b

1 0
 1 0
ˆb = Aˆ
x=
 0 1
0 1
op Col A is (uiteraard) wel uniek :



1 
2 − x3 + x3
2 − x3


1 
2 − x3 + x3
2 − x3  = 
 2 − x3 + x3
1 
x3
1
2 − x3 + x3



2
  2 
 =  .
  2 
2
De QR-ontbinding van een matrix kan helpen om het rekenwerk te bekorten :
Stelling 4. Als A een (m × n)-matrix is met lineair onafhankelijke kolommen en A = QR is
een QR-ontbinding van A, dan geldt : Ax = b heeft voor iedere b ∈ Rm een unieke kleinstekwadratenoplossing x
ˆ bepaald door : Rˆ
x = QT b.
Opmerking. De kleinste-kwadratenoplossing x
ˆ is uniek omdat de kolommen van A lineair
onafhankelijk zijn. Omdat R een bovendriehoeksmatrix is kan Rˆ
x = QT b (snel) opgelost
worden via terugsubstitutie.
Bewijs. Voor een QR-ontbinding van A geldt dat QT Q = I (want Q heeft orthonormale
kolommen) en dat R inverteerbaar is. Dus : AT A = (QR)T QR = RT QT QR = RT IR = RT R
6
en AT b = (QR)T b = RT QT b. Als R inverteerbaar is (det R 6= 0), dan is RT ook inverteerbaar,
want : det RT = det R 6= 0. Dus :
AT Aˆ
x = AT b
RT Rˆ
x = RT QT b
⇐⇒
⇐⇒
Rˆ
x = QT b.
Toepassingen van de kleinste-kwadratenmethode
De kleinste-kwadratenoplossing wordt gebruikt om bijvoorbeeld een grafiek (zoals een rechte
lijn) te vinden die zo goed mogelijk ’door’ een ’puntenwolk’ loopt.
Voorbeeld 5. Beschouw de ’puntenwolk’ : (−3, −2), (−1, 0), (1, 2) en (2, 5). We zoeken
nu een rechte lijn y = ax + b die het best bij deze puntenwolk past. Door invullen van de
verschillende waarden voor x en y zien we dat a en b zouden moeten voldoen aan :





−3a
+
b
=
−2
−3
1
−2



 −1 1 


−a + b =
0
 en b =  0  .
⇐⇒ Ax = b met A = 
 1 1 
 2 
a + b =
2



2a + b =
5
2 1
5
Al snel is duidelijk dat Ax = b niet oplosbaar is. De vier punten liggen blijkbaar niet netjes
op een rechte lijn. We bepalen nu een kleinste-kwadratenoplossing van Ax = b :


−3 1
−3 −1 1 2 
−1 1 
15 −1
T


=
A A=
1
1 1 1  1 1 
−1
4
2 1
en

AT b =
−3 −1 1 2
1
1 1 1

−2
 0 

 = 18 .
 2 
5
5
Dus :
T
T
A Aˆ
x=A b
We kiezen nu : a =
=⇒
T
−1
x
ˆ = (A A)
1
A b=
60 − 1
T
4 1
1 15
18
5
1
=
59
77
93
.
77
93
77
93
en b = . We vinden zo de kleinste-kwadratenlijn : y = x+ .
59
59
59
59
Op deze manier kunnen ook andere kleinste-kwadratenkrommen door een puntenwolk
worden gevonden. Het invullen van de verschillende waarden voor x en y levert een stelsel
vergelijkingen op met de co¨effici¨enten als onbekenden. Hiervoor kiezen we dan de co¨ordinaten
van kleinste-kwadratenoplossing. Zie § 6.6 van Lay voor meer voorbeelden.
7

Download Report