Normat 57:4, 173–179 (2009) 173
Gram–Schmidt’s algoritm för en allmän vinkel
Tord Sjödin
Institutionen för matematik och matematisk statistik
Umeå universitet,
tord.sjodin@math.umu.se
Inledning.
Låt V vara ett reellt vektorrum med inre produkt x·y och norm ||x|| = (x·x)
1/2
, där
x, y är vektorer i V . Vi säger att två vektorer x och y i V är ortogonala om x·y = 0.
En ändlig summa
k
P
j=1
c
j
· x
j
, där c
j
är reella tal och x
j
är vektorer i V , 1 ≤ j ≤ k,
kallar vi en linjär kombination av vektorerna {x
1
, x
2
, . . . , x
k
}. En delmängd E av
V säges vara linjärt oberoende om för varje ändlig delmängd {x
1
, x
2
, . . . , x
k
} av
E och godtyckliga reella tal {c
1
, c
2
, . . . , c
k
}, villkoret
k
P
j=1
c
j
· x
j
= 0 medför att
c
j
= 0, för alla 1 ≤ j ≤ k. Vi säger att mängden E är en parvis ortogonal mängd
om x · y = 0, för varje par x och y av olika vektorer i V . En parvis ortogonal
mängd av enhetsvektorer, vektorer med norm ett, kallas en ortonormal mängd
eller helt enkelt en ON−mängd. Det är välkänt, och lätt att bevisa, att varje parvis
ortogonal mängd också är linjärt oberoende. Omvändningen till detta påstående
är naturligtvis inte sant. Det som däremot är sant är att givet en ändlig eller
numrerbart oändlig och linjärt oberoende mängd E, så kan man konstruera en
ON−mängd E
0
som har samma linjära hölje som E. Detta är i huvudsak innehållet
i Gram-Schmidt’s algoritm och fullt tillräckligt för de flesta tillämpningar. Att två
vektorer x och y är ortogonala kan i vissa fall tolkas geometriskt som att vinkeln
mellan x och y är 90 grader. Vi ska ge en mera allmänn algoritm, som vi kallar
Gram–Schmidt’s p−algoritm, och som konstruerar en mängd vektorer som parvis
bildar samma vinkel med varandra i samtliga fall där detta är möjligt.
Det linjära höljet till en mängd E ⊂ V är mängden av alla linjärkombinationer
av vektorer i E och betecknas med span(E). Det är lätt att se att span(E) är
ett linjärt delrum av V , det vill säga att span(E) är ett vektorrum med samma
operationer som V .
Vi definierar vinkeln θ mellan två vektorer x and y i V , som inte är nollvektorer,
genom
cos θ =
x · y
||x|| · ||y||
, 0 ≤ θ ≤ π.
174 Tord Sjödin Normat 4/2009
Om x = 0 eller y = 0 definierar vi vinkeln θ som noll. Två vektorer x och y är alltså
ortogonala om och endast om vinkeln mellan vektorerna är 90 grader. Det är nu
vanligt, och naturligt, att man identifierar vinkeln θ med dess cosinusvärde p, det
vill säga att man definierar p = cos θ, där −1 ≤ p ≤ 1.
Gram – Schmidt’s algoritm konstruerar en ortogonal mängd av vektorer från en lin-
järt oberoende mängd. Vi formulerar detta resultat på följande sätt, se exempelvis
[1], Ch. 6, [4], Theorem 31, [2] eller [3].
Sats 1. Låt E = {x
i
} vara en ändlig, eller numrerbart oändlig, och linjärt obero-
ende delmängd av V . Då finns en mängd E
0
= {y
i
} av vektorer i V med följande
egenskaper:
span({y
1
, y
2
, . . . , y
i
}) = span({x
1
, x
2
, . . . , x
i
}), för i = 1, 2, . . . , (1)
span(E
0
) = span(E), (2)
mängden E
0
är en ON−mängd. (3)
Följande sats och dess korollarium är vårt huvudresultat.
Sats 2. Låt {x
i
}
n
i=1
vara en linjärt oberoende delmängd av V . Då finns en mängd
vektorer {z
i
}
n
n=1
i V så att
span({z
1
, z
2
, . . . , z
i
}) = span({x
1
, x
2
, . . . , x
i
}), 1 ≤ i ≤ n, (4)
och
z
i
· z
j
=
1, i = j,
p, i 6= j,
(5)
för alla 1 ≤ i, j ≤ n, om och endast om −
1
n−1
< p < 1.
Korollarium 1. Låt {x
i
}
∞
n=1
vara en numrerbart oändlig och linjärt oberoende
mängd vektorer i V . Då finns en mängd vektorer {z
i
}
∞
n=1
i V så att (4) och (5)
gäller för alla i, j = 1, 2, . . . , om och endast om 0 ≤ p < 1.
Anmärkning. Sats 2 and Korollarium 1 kan också formuleras i termer av längden
av vektorerna istället för vinklarna mellan vektorerna, ty om ||x|| = ||y|| = 1 så
gäller ||x − y||
2
= 2(1 − x · y). Sats 2 får då följande ekvivalenta formulering:
Låt {x
i
}
n
i=1
vara en linjärt oberoende mängd i V . Då finns vektorer {z
i
}
n
i=1
i V
som uppfyller (4) och
||z
i
|| = 1 and ||z
i
− z
j
|| = d
för i 6= j, 1 ≤ i, j ≤ n, om och endast om 0 < d <
q
2n
n−1
.
Korollarium 1 har en liknande omformulering med 0 < d ≤
√
2, vilken vi övernäm-
nar åt läsaren.
Anmärkning. Om vi väljer d = 1 ovan får vi en mängd {0, z
1
, z
2
, . . . , z
n
} med
n + 1 punkter som har parvis samma avstånd. Sådana mängder kallas ekvilaterala
mängder och studeras för allmänna vektorrum i [5].
Normat 4/2009 Tord Sjödin 175
Bevis
Denna sektion innehåller bevisen för Sats 2 and Korollarium 1. Vi börjar med
beviset av Sats 2.
Bevis av Sats 2. Låt {x
i
}
n
i=1
vara som i satsens formulering, låt −
1
n−1
< p < 1 och
utför Gram–Schmidt’s algoritm på vektorerna {x
i
}
n
i=1
. Detta ger vektorer {y
i
}
n
i=1
som uppfyller (1) och (3). Vi skall nu induktivt definiera vektorerna {z
i
}
n
i=1
och
vi börjar med z
1
= y
1
. Låt sedan w = y
2
+ a · z
1
. Då gäller ||w||
2
= 1 + a
2
och
w ·z
1
= a. Vi väljer nu a så att w ·z
1
= p ·||w||, vilket ger a = p/
p
1 − p
2
. Slutligen
definierar vi z
2
= w/||w||.
Antag nu att vi har definierat z
1
, z
2
, . . . , z
k
så att ||z
i
|| = 1 och z
i
· z
j
= p, i 6= j,
i, j = 1, 2, . . . k. Låt w = y
k+1
−
k
P
j=1
c
j
· z
j
. Då gäller
w · z
i
= −c
i
− p ·
X
j6=i
c
j
, 1 ≤ i ≤ k,
och
||w||
2
= 1 + ||
k
X
j=1
c
j
· z
j
||
2
,
eftersom y
k+1
är ortogonal mot span{z
1
, z
2
, . . . , z
k
} ⊂ span{y
1
, y
2
, . . . , y
k
}. Detta
ger
w · z
i
= −c
i
− p ·
X
j6=i
c
j
= p · ||w||,
for 1 ≤ i ≤ k. Vi subtraherar nu de sista ekvationerna parvis och får att c
1
= c
2
=
··· = c
k
= d och
d(1 + p(k − 1)) = −p · ||w||. (6)
Vidare har vi
||w||
2
= 1 + d
2
· ||
k
X
i=1
z
i
||
2
= 1 + d
2
(k + p(k
2
− k)). (7)
Genom att kombinera (6) och (7) får vi
d
2
· (1 + p(k − 1)) · (1 − p) · (1 + pk) = p
2
.
Denna ekvation kan lösas med avseende på d, eftersom p > −
1
n−1
≥ −
1
k
. Slutligen
definierar vi z
k+1
= w/||w||. Genom att fortsätta på detta sätt får vi vektorer
{z
i
}
n
i=1
som uppfyller (5). Det är också lätt att se att {z
i
}
n
i=1
är linjärt oberoende,
vilket bevisar (4).
För att bevisa omvändningen av satsen antar vi att {z
1
, z
2
, . . . , z
n
} är vektorer i
V som uppfyller (4) och (5). Då är {z
1
, z
2
, . . . , z
n
} linjärt oberoende och formeln
176 Tord Sjödin Normat 4/2009
0 < ||z
1
+ z
2
+ ··· + z
n
||
2
= n(1 + p(n − 1)) bevisar att p > −1/(n − 1). 4
Bevis av Korollarium 1. Låt {x
i
}
∞
i=1
vara som i korollariet och låt 0 ≤ p < 1.
Beviset av Sats 2 ger oss nu vektorer {z
i
}
∞
i=1
med de önskade egenskaperna.
För att bevisa omvändningen av korollariet antar vi att {z
i
}
∞
i=1
har egenskaperna
(4) och (5). Då är {z
i
}
∞
i=1
linjärt oberoende och 0 < ||z
1
+ z
2
+ ···z
n
||
2
= n(1 +
p(n − 1)), n ≥ 1. Låter vi nu n → ∞ så följer att p ≥ 0. 4
Gram–Schmidt’s p-algoritm
I den här sektionen skall vi beskriva den algoritm som konstruerar vektorerna
{z
i
}
n
i=1
i Sats 2. Låt {y
i
}
n
i=1
vara en ON−mängd i V och låt −
1
n−1
< p < 1. Vi
definierar induktivt vektorer {z
i
}
n
i=1
med metoden i beviset för Sats 2. Sätt z
1
= y
1
och antag att z
2
, z
2
, . . . z
k
har definierats. Låt
w = α · y
k+1
+ β · (z
1
+ z
2
+ ··· + z
k
),
där α och β uppfyller
||w||
2
= α
2
+ β
2
(k + k(k − 1)p) = 1
och
w · z
i
= β · (1 + (k − 1)p) = p · ||w||, 1 ≤ i ≤ k.
En enkel uträkning ger att
α
2
=
(1 − p)(1 + pk)
1 + p(k − 1)
och β =
p
1 + p(k − 1)
, (8)
och vi får följande algoritm.
Gram–Schmidt’s p-algoritm (GS
p
).
Input är en linjärt oberoende mängd {x
1
, x
2
, . . . , x
n
} i ett reellt vektorrum V med
inre produkt och ett reellt tal p som uppfyller −
1
n−1
< p < 1. Output är en mängd
{z
1
, z
2
, . . . , z
n
} av vektorer i V med egenskaperna (4) and (5) i Sats 2.
Steg 0. Genomför Gram–Schmidt’s algoritm enligt Sats 1 och få följden {y
1
, y
2
, . . . , y
n
}.
Steg 1. Definiera z
1
= y
1
.
Steg 2. För 1 ≤ k ≤ n − 1, låt
z
k+1
=
s
(1 − p)(1 + pk)
1 + p(k − 1)
· y
k+1
+
p
1 + p(k − 1)
· (z
1
+ z
2
+ ··· + z
k
). (9)
Steg 3. Den mängd {z
1
, z
2
, . . . , z
n
} som har konstruerats efter det att Steg 2 har
Normat 4/2009 Tord Sjödin 177
upprepats (n − 1) gånger har alla de önskade egenskaperna (4) och (5).
Vi ska nu låta V vara det Euklidiska vektorerummet R
n
, vars element är n−tupler
x = (x
1
, x
2
, . . . , x
n
) av reella tal. Skalärprodukten mellan två vektorer x och w
definieras av x · w = x
1
w
1
+ x
2
w
2
+ ··· + x
n
w
n
och normen av vektorn x ges
av ||x|| =
√
x · x. Vi låter {y
k
}
n
1
vara standardbasen i R
n
, det vill säga y
k
=
(0, . . . , 0, 1, 0, . . . , 0) och ettan är på den k:e platsen. Vi ska nu härleda explicita
uttryck för vektorerna z
k
. Det visar sig då att de (k −1) första koordinaterna i z
k
inte ändras när vi går från z
k
till z
k+1
. Vi bevisar det i följande lemma.
Lemma 1. Låt {y
k
}
n
1
var som ovan och definiera {z
k
}
n
1
genom (9). Då gäller att
z
k+1
(i) = z
k
(i), för 1 ≤ i ≤ k − 1.
Bevis. Om k = 1 finns inget att bevisa. Anta att lemmat gäller för något visst
k, 2 ≤ k ≤ n − 1. Då gäller
z
k+1
(i) =
1
1 + p(k − 1)
· (z
1
(i) + ··· + z
k−1
(i) + z
k
(i))
och
z
k
(i) =
1
1 + p(k − 2)
· (z
1
(i) + ··· + z
k−1
(i)).
En enkel uträkning ger oss slutsatsen i Lemma 1. 4
Vi kan nu härleda explicita formler för z
k
, 1 ≤ k ≤ n och börjar med att definiera
följden
a
m
(p) =
p
1 + p(m − 1)
·
s
(1 − p)(1 + p(m − 1))
1 + p(m − 2)
, (10)
m=1,2,. . . . Med hjälp av följden {a
m
(p)}
n
1
får vi följande explicita formler för
vektorerna {z
k
}
n
1
.
Sats 3. Låt {y
k
}
n
1
vara standardbasen i R
n
och låt {z
k
}
n
1
vara definierad av (GS
p
).
Då gäller z
1
= (1, 0, . . . , 0) och z
k
ges av
z
k
= (a
1
(p), a
2
(p), . . . , a
k−1
(p),
1 + p(k − 1)
p
· a
k
(p), 0, . . . , 0),
för 2 ≤ k ≤ n.
Bevis. Man ser lätt att satsen gäller för k = 2. Antag att satsen gäller ett visst
k, 2 ≤ k ≤ n − 1 och betrakta z
k+1
. Vi observerar att z
k+1
(i) har rätt värde för
1 ≤ i ≤ k − 1 och i = k + 1, på grund av Lemma 1 och (9). Vidare får vi
z
k+1
(k) =
p
1 + p(k − 1)
· z
k
(k) = a
k
(p),
på grund av (9) och (10). 4
178 Tord Sjödin Normat 4/2009
En asymptotisk formel.
Återstoden av denna artikel skall vi ägna åt att undersöka det asymptotiska upp-
förandet hos z
k
för stora värden på k. Vi ska använda oss av vektorrummet l
2
,
som består av alla oändliga följder {x
k
}
∞
1
sådana att summan
∞
P
1
x
2
k
är ändlig.
Skalärprodukten mellan två vektorer x och w i l
2
och normen av x definieras av
x·w =
∞
P
1
x
k
w
k
och ||x|| =
√
x · x, respektive. Vi antar att 0 < p < 1 och identifierar
R
n
med ett delrum av l
2
, genom att vektorn x = (x
1
, x
2
, . . . , x
n
) i R
n
identifieras
med vektorn x = (x
1
, x
2
, . . . , x
n
, 0, . . . ) i l
2
. Slutligen definierar vi följden
z
0
= (a
1
(p), a
2
(p), . . . , a
n
(p), . . . ).
Man bevisar lätt att z
0
tillhör l
2
och ||z
0
|| =
√
p. Vi kan nu använda z
0
till att
bevisa en asymptotisk formel för z
k
.
Sats 4. Låt {z
k
}
∞
1
vara som ovan, då gäller z
k
≈ z
0
+
√
1 − p · y
k
, as k → ∞, i
den meningen att
lim
k→∞
√
k · ||z
k
− z
0
−
p
1 − p · y
k
|| ≤
p
p(1 − p) ≤ 1/2.
Bevis. Genom triangelolikheten får vi att ||z
k
− z
0
−
√
1 − p · y
k
|| är högst
∞
X
k
|a
m
(p)|
2
!
1/2
+ |
s
(1 − p)(1 + p(k − 1))
1 + p(k − 2)
−
p
1 − p| = A + B.
För den första termen får vi formeln
A
2
=
∞
X
k
|a
m
(p)|
2
=
p
2
(1 − p)
1 + p(k − 2)
med hjälp av en teleskopserie och en enkel uträkning ger uppskattningen
B ≤
1
2
·
p
√
1 − p
1 + p(k − 2)
.
Sats 4 följer nu genom att kombinera uppskattningarna för A och B och ta övre
limes då k → ∞. 4
Exempel. I fallet då p = 1/2, vilket svarar mot vinkeln π/3 radianer mellan vekto-
rerna, blir formlerna särskilt enkla. En uträkning för vektorn z
0
∈ l
2
i Sats 4 ger
då att
z
0
=
1
√
2
· (
1
√
1 · 2
,
1
√
2 · 3
,
1
√
3 · 4
,
1
√
4 · 5
, ··· ,
1
p
n · (n + 1)
, ···)
=
1
2
· (
1
q
2
2
,
1
q
3
2
,
1
q
4
2
,
1
q
5
2
, ··· ,
1
q
n
2
, ···).
Normat 4/2009 Tord Sjödin 179
Vi överlämnar åt läsaren att på samma sätt beräkna vektorerna {z
k
}
n
1
i Sats 3.
Anmärkning. Jørgen Pedersen Gram, 1850 – 1916, var en dansk matematiker
som arbetade med både ren och tillämpad matematik. Hans bidrag till Gram–
Schmidt’s metod kom från hans avhandling om serieutvecklingar med användning
av minstakvadratmetoden. Den tyske matematikern Erhard Schmidt, 1876 – 1959,
avlade sin doktorsexamen i Göttingen under ledning av David Hilbert, en av den
tidens ledande matematiker. Schmidt bidrog till att utforma teorin för Hilbertrum
och betraktas som en av grundarna av den moderna funktionalanalysen. Gram–
Schmidt’s algorithm upptäcktes emellertid långt före både Gram och Schmidt av
den inom många områden berömde franske matematikern Pierre – Simon Laplace,
1749 – 1827.
Referenser
[1] H. Anton, C. Rorres, Elementary linear algebra. Applications version, John Wiley
& Sons. Inc., Ninth edition, 2005
[2] D. L. Kreider, R. G. Kuller, D. R. Ostberg, F. W. Perkins, An introduction to
linear analysis, Addison–Wesley, Massachusetts, 1966
[3] M. Reed, B. Simon, Methods of Modern Mathematical Physics, Vol. 1: Functional
Analysis. Academic Press, New York, 1972
[4] G. E. Shilov, An introduction to the theory of linear spaces, Prentice Hall, New
Jersey, 1961
[5] K. J. Swanepoel, R Villa, A lower bound for the equilateral number of normed
spaces, Proc. Amer. Math. Soc. 136(2008)1, pp. 127 – 131
