~
Technische Hogeschool Eindhoven
Onderafdeling der Wiskunde
Wiskunde 37 voor tweedejaarsstudenten van de afdeling Bouwkunde
Lineaire Algebra Syllabus van het college van prof. dr. S.T. M. Ackermans
Dictaatnr. 2.267
Prijs
f
4,50
TECHNISCHE HOGESCHOOL EINDHOVEN Afdeling Algemene Wetenschappen
Onderafdeling der Wiskunde
WISKUNDE 37 Syllabus van het college
Lineaire Algebra van Prof. Dr. S.T.M. Ackermans
voor tweedejaarsstudenten van de afdeling Bouwkunde
Najaarssemester 1977
TECHNISCHE HOGESCHOOL EINDHOVEN Onderafdeling der Wiskunde
Wiskunde 37 Syllabus van het college over LINEAIRE ALGEBRA voor tweedejaarsstudenten van de afdeling BOUWKUNDE gegeven door PROF.DR. S.T.M. ACKERMANS
Najaarssemester !977
- 3 -
VOORWOORD Lineaire algebra is het deel van de wiskunde dat gegroeid is uit de theorie van de stelsels van eerstegraads vergelijkingen in meerdere onbekenden. Wiskundige beschrijvingen met behulp van eerstegraads (ook wel genoemd lineaire) betrekkingen worden in zeer veel gebieden van onderzoek gebruikt. Om die reden worden methoden en resultaten van de lineaire algebra toegepast in talrijke uiteenlopende gebieden van wetenschap. De grondslag van het succes van de lineaire algebra is de synthese van twee geheel verschillende benaderingswijzen, nl. de rekenkundige en de (abstract) meetkundige. In de eerste benadering is de lineaire algebra een techniek ontwikkeld om doelmatig en systematisch te rekenen met stelsels lineaire betrekkingen; in de meetkundige benadering worden de objecten uit de lineaire algebra voorgesteld als meetkundige grootheden, waardoor ze een aanschouwelijke inhoud krijgen. In dit college worden beide gezichtspunten besproken: het rekenkundige in hoofdstuk I, waarin men tevens een aantal toepassingsgebieden van de lineaire algebra aangeduid vindt, het meetkundige in hoofdstuk 2. Het laatste hoofdstuk vat de verkregen inzichten samen. De voorbeelden uit toepassingsgebieden zijn gekozen met als enig oogmerk de te ontwikkelen theorie te motiveren en illustreren; uiteraard geven zij een beeld van de bruikbaarheid van de behandelde ideeën, maar dit college geeft geen min of meer volledig overzicht over de toepassingen van de lineaire algebra. Het voor de toepassingen uiterst belangrijke aspect van het numeriek uitwerken van problemen met behulp van een computer kan in dit college niet aan de orde komen.
-
5 -
INHOUDSOPGAVE HOOFDSTUK I . MATRIXREKENING §
l.I. Bewerkingen met matrices
§
1.2. Toepassingen en voorbeelden
HOOFDSTUK 2. LINEAIRE RUIMTEN, LINEAIRE AFBEELDINGEN
7 7 18
32
§
2. I. De ruimte IRn
32
§
2. 2. Lineaire deelruimten
41
§
2.3. Afhankelijkheid en onafhankelijkheid
44
§
2.4. Bases
48
§
2.5. Het bepalen van een basis
SI
§
2.6. Lineaire afbeeldingen
56
HOOFDSTUK 3. LINEAIRE VERGELIJKINGEN EN ONGELIJKHEDEN
67
§
3. I. Homogene lineaire vergelijkingen
67
§
3.2. Inhomogene lineaire vergelijkingen
68
§
3.3. Positieve oplossingen van stelsels lineaire vergelijkingen
72
§
3.4. Lineaire ongelijkheden
81
§
3.5. Iets over lineaire programmering
83
APPENDIX. DETERMINANTEN
87
- 7 -
HOOFDSTUK I §
MATRIXREKENING
l.I. Bewerkingen met matrices
1.1.1. Matrices zijn rechthoekige schema's van getallen. Voorbeelden I , 4 , 4 ,
[
x]
2
2 , a
3
0,0,6
['2]
[3' 5' 0' 4' 7] •
0
We spreken van rijen, kolommen, elementen. De volgende notaties voor een matrix met m rijen en n kolommen zijn gebruikelijk all
al2
a21
a22
a mi
am2
A = A(mxn) = [a .. J = lJ a
mn
Is A= [a .. ] een matrix dan duidt A.. aan het element in de i-de rij en j-de lJ lJ kolom; dus A.. = a •.• Als de duidelijkheid er om vraagt gebruike men komma's: lJ lJ [I, 2, 3, 7]; ai+l,j+I' Matrices met slechts één rij of slechts één kolom noemt men vectoren: (zie 2.1.1) rijvectoren, kolomvectoren; we noteren kolomvectoren vaak met onderstreepte letters: Vanuit het rekenkundige standpunt zijn
~·
matrices niet meer dan een hulpmid-
del om ingewikkelde algebraïsche en numèrieke berekeningen te systematiseren. We zullen voor matrices bewerkingen definiëren die generalisaties zijn van de bewerkingen met reële getallen (een reëel getal is op te vatten als een matrix met één rij en één kolom). Zijn A en B matrices met hetzelfde aantal rijen en hetzelfde aantal kolommen (we zeggen dan dat A en B van hetzelfde formaat zijn) dan betekent A a ..
lJ
~
b ..
lJ
voor alle i en j.
~
B dat
- 8 -
1.1.2. Optelling Als A en B matrices zijn van hetzelfde formaat dan is de som A + B gedefinieerd door (A + B) .. := A •. + B.. • 1J 1J 1J
Anders geformuleerd: A+ B C = [c .. ] 1J
betekent:
= C met
A= [a .. ], B = [b .. ] • 1J
1J
A, B en C hebben hetzelfde formaat en a .. + b .. = c .. 1J
1J
1J
voor alle voorkomende i en j. 4
0
x
4
5
0
y
5
2
6
0
z
0
a
0
8
3
JO
2
y+3
6
a
z+l
x
1.1.3. Scalaire vermenigvuldiging € ~(keen
Is A= [a .. ] een m x n matrix, k 1]
reëel getal), dan is kA de m x n
matrix [ka .. ]. Dus 1J
0 28 0
7x] 7y
•
7z
We schrijven -A voor -IA. Duidt ~een matrix aan waarvan alle elementen nul zijn (een zgn. nulmatrix) dan is OA (mxn) = 0' =
1]
1]
A+B=B+A A + Cf = Cf + A = A
(0" stelt hierin een nulmatrix voor van
hetzelfde formaat als A) A - A : = A + (-A) = 0' (p + q)A = pA + qA p(A + B) = pA + pB p(qA) = (pq)A
- 9 -
1.1.5. Blokmatrices Vaak is het handig matrices opgebouwd te denken uit kleinere: bijvoorbeeld r
a12
al I
al3
-
a!4
al?
a21 =:
a31 a4 I
~
Q
:J '
T
a57
aS!
'-
waarbij
p
:=
a
GJa21I
12 a22J' • • • ' U
34
=
r
a35
a44 a54
a36
·~']
a57
Als alle formaten van overeenkomstige blokken overeenstemmen kan men ma trices optellen door de blokken op te tellen:
1.1.6. De getransponeerde matrix Is A een
m x
n matrix dan is de getransponeerde AT een n
A ontstqat door rijen en kolommen te verwisselen. Is 6
A=
2
7
3
8
4
9
5
0
dan is 2
3
4
7
8
9
~] .
x m
matrix die uit
- JO -
We hebben dus: T A .. =A·· ~J J~
de getransponeerde van een rijvector is een kolomvector. 1.1.7. Het inwendig product van vectoren Zijn UI
VI
u2
v2
u=
en u
V
= V
n
n
vectoren met een gelijk aantal elementen, dan is het inwendige product
(~,~)
gedefinieerd door: n
r
u.v.
i= I
~
~
Eenvoudig ziet men in dat:
(k
e JR) 0 0
(~,~)
~
0 en uit
(~,~)
0 volgt u = Q, waarin 0 =
,de nulvector. 0
We definieerden het inwendig product voor kolomvectoren; het kan met dezelfde formule ook voor rijvectoren of voor een kolom- en een rijvector.
- 11 -
1.1.8. Het matrixproduct Van twee matrices A en B zullen we het product in de volgorde AB alleen definiëren indien het aantal kolommen van A gelijk is aan het aantal rijen van B. IsA
(mxn)
=[a .. ]; B(nxp) 1J
=
[b •• ] , 1J
dan is AB= C
[ c .. ] een
matrix
m x p
1J
gedefinieerd door n
i = 1 , ••• ,m; k = I, ... ,p.
a .. b.k
L:
j=l
1J J
* *
* *
* *
* *
* *
* *
a31
a32
a33
a34
a35
a36
*
*
*
*
*
*
* * * * * *
A(4x6)
Is AB
= C dan
bl2 b22 b32 b42 b52 b62 8
* * * * * = * * * * *
(6x3)
=
* * c32
*
* * * *
c<4x3)
is het element in de i-de rij en de k-de kolom van C het in-
wendige product van de i-de rijvector van A met de k-de kolomvector van B. In de notaties van 1.1.8 en 1.1.6 is
(~,~)
= uTv.
Nog een voorbeeld:
(bij een I x I matrix, d.i. een getal, laten we de haken weg);
Men ziet dat de factoren in een matrixproduct niet verwisseld mogen worden. Bij A( 4 x6 ) en s< 6 xJ) is AB wel maar BA niet gedefinieerd. Is A vierkant (d.i. n x n) dan is AA gedefinieerd; we schrijven AA= A2 . De volgende eigenschappen zijn door napuzzelen te verifiëren (denk aan de afspraak uit 1.1.4):
- 12 -
A(B
= AB
C)
+
(A + B)C
=
+
AC
AC + BC
(AB)C
= A(BC)
(AB)T
= BTAT
•
1.1.9. Voorbeeld Een steenfabriek fabriceert stenen in vijf kwaliteiten. De fabriek heeft vier magazijnen met verkooppunten. ministreerd met 4
Voorraadgegevens worden nu handig gead-
5 matrices waarbij de rijen overeenkomen met de magazij-
x
nen, de kolommen met de kwaliteiten. januari 1970 voor
Stelt A de aanwezige voorraad op _,.
magazijn
2 _,. 3 _,. 4 _,.
a !I
a12
al3
al4
alS
a21
a22
a23
a24
a25
a31
a32
a33
a34
a35
a41
a42
a43
a44
a45
t 2
t 3
t 4
t 5
t kwaliteit I
(a
is het aantal op 1-1-1970 aanwezige stenen in magaz1Jn 3 van kwaliteit 34 (4xS) . 4); Stelt B de door de fabr1ek aan de verkooppunten geleverde hoeveelheden en c< 4xs) de verkoop gedurende 1970 voor, dan is A + B - C de voorraadsmatrix per 1-1-1971. Laten we aannemen dat grondstofkosten, fabricagekosten en verkoops·prijs afhangen van de kwaliteit. Laat g ,g , .•• ,g de grondstofkosten, f 1 ,f 2 , ••• ,f 5 1 2 5 de fabricagekosten en v ,v , ••• ,v de verkoopskasten per steen zijn. Laat 1 2 5
all
a12
* *
* * *
a41
* * * * A
gl
fl
VI
* * *
alS
g2
f2
v2
*
g3
f3
v3
*
g4
f4
*
a45
gs
fs V
p !I
pl2
pl3
*
v4
* *
*
* *
vs
p41
*
p43
=
=
p
Dan stelt de k-de rij van P voor achtereenvolgens de in de voorraad van magazijn k geinvesteerde grondstofkosten (= PkJ), de geinvesteerde fabricagekosten <= Pkz l • de verkoopswaarde (= pk3).
- 13 -
Als
* * dan is
~
*
*
*
*
* *
*
[l
de winst die gemaakt zou worden bij totale uitverkoop van magazijn
k. Noemen we
dan is de winst gemaakt per magazijn in 1970:
CVd
i=
Is
=
[1, I, I, IJ, dan 1s de totale winst
iCV~;
verder is iC een I x 5 ma-
trix: [s , s , s , s , s J waar sm het aantal door alle 4 magazijnen geza2 3 4 5 1 menlijk verkochte stenen van kwaliteit m (m = I , •.. ,5) voorstelt; Vd is een 5
x
I matrix:
waarin tk de winst bij verkoop van één steen van kwaliteit k voorstelt.
- 14 -
1.1.10. Opmerkingen
ll 21 ra "] Lo oJ Lo -1
(I)
= 0" =
[Io o2J Lora -4] rl~ =
2
ol jo
zj Lo
-4] 2
Dus uit PA= PB volgt niet A= B; uit CQ = DQ volgt niet C = D; uit QR = r:f volgt niet Q = 0" of R = 0". (2) Als A en B n x n
matrices zijn, dan is
(A + B) (A - B) = A2 - AB + BA - B2 en omdat AB in het algemeen ongelijk aan BA is, is dit niet verder te vereenvoudigen. (3) Eenheidsmatrix
0
0
0 1
(nxn) =
0
0
0 0 0
0
d.w.z. I.. = ~J
{~
als i f. j als i = j
Nu is A(mxn) 1 (nxn) = A(mxn) r
B(nxp)
(4) Diagonaalmatrix 0 (nxn) = [d .. ] heet diagonaalmatrix indien d .. = 0 als i f. j. Rechtsver~J
~J
menigvuldiging met een diagonaalmatrix betekent vermenigvuldiging van de kolommen, linksvermenigvuldiging betekent vermenigvuldiging van de rijen
-
~"
a12
a21
a22
a31
a32
""] ~ a23
a33
0
[: ~ ["
al2
q
a21
a22
0
a31
a32
~·" :J
0
q
0
15 -
."J
qal2
= pa21
qa22
pa31
qa32
r·.
'""] '""] ra23 ra 33
pal2
a23
= qa12
qa22
a33
ra31
ra32
qa23
'
ra33
= A.
(5) Een (vierkante) matrix heet symmetrisch als AT
Met iedere homogene kwadratische vorm in n veranderlijken korrespondeert een symmetrische matrix. Bijvoorbeeld met n
ax 2 + 2bxy + 2cxz + dy
2
+ 2eyz + fz
2
=3
=
[x
y
Z
~bac
l ~
b:
J
c:l [x:]
Is A een (n x n) matrix en
x=
x
n
T
dan is x Ax een homogene kwadratische vorm in x 1 , ..• ,xn. Bovendien is T x Ax =
T
T
~~ (A + A )~ •
(6) Veranderingen van de volgorden van de rijen of kolommen van een matrix kan men verkrijgen door links- of rechtsvermenigvuldiging met zgn. permutatiematrices. We geven de algemene definitie maar beperken ons verder tot een voorbeeld van een 3 x 3 matrix. Zij f een één-éénduidige afbeelding van {1,2,3, ••. ,n} op {1,2,3, ••• ,n} (f heet een permutatie van {1,2, •.• ,n}), dan is de permutatiematrix P behorende bij f gedefinieerd door: p~t;xn) l.J
=
{ I als i
= f (j)
0 als i " f (j)
(i,j
=
I , ... , n)
in elke rij en kolom van P staat dus precies één I.
'
- 16 -
Laat nu een permutatief van {1,2,3} gegeven zijn door f(l) = 3, f(2) = I, f(3) = 2, dan is de permutatiematrix
,_~: ;] Nu is
en
~~
G
0
o
~l 1:~:
~J b~
Merk op dat de i-de kolom van AP gelijk is aan de f(i)-de kolom van A, terwijl voor PA geldt dat de i-de rij van A als f(i)-de rij van PA optreedt. (7) Stelsels lineaire vergelijkingen zijn te beschouwen als speciale gevallen van matrixvermenigvuldiging. Is
A(mxn)
= [ a.. ] ~J
b =
x=
'
b
:
... + a1n xn
=
bi
a21xl + a22x2 +
...
=
b2
+ a
(*)
x
2n n
+ a x = b mn n m
ook te schrijven als: Ax
= b.
m
- 17 -
Als we dus een matrix G(nxm) kunnen vinden zó dat G(nxm) A(mxn) = r(nxn) dan is GAx = Ix = x = Gb een oplossing van (*). (8) Laat A een
n x n
matrix zijn. Als er een matrix B bestaat zodat
BA= I(nxn), dan heet B de inverse van A, notatie A-l. Later (2.6.11) zullen we bewijzen dat dan ook AA-l = I en dat een vierkante matrix ten hoogste één inverse heeft. Eén voorbeeld: Als we de inverse willen bepalen van·
G
~]
moeten we x, y, u en v vin-
den zó dat
[:
:]
[~ ~] = [~ ~]
Of: rx + 7y = 2x + 5y = 0 We vinden: x
{3u + 7v = 0 • 2u + 5v = I
5' y
-2, u = -7,
\5 -2l L-7 3J Merk op dat
\3 2J 15 -2J lJ 5 l-7 3
=
\I ol lo d
V
.
= 3, en dus:
-
§
18 -
1.2. Toepassingen en voorbeelden
Uit de veelheid van toepassingen van de matrixrekening kiezen we er enkele die een goede illustratie zijn van de overzichtelijkheid die door het gebruik van rnatrices gewonnen wordt. Men moet echter niet uit het oog verliezen dat we ons beperken tot eenvoudige problemen, en dat het voordeel van het benutten van lineaire algebra groter wordt naarmate de problemen gecompliceerder worden. 1.2. 1. Een transportnetwerk Vier steden P , P , P 3 , P4 bevatten ieder een gasfabriek. Er liggen zes 1 2 pijpleidingen, I t/rn 6, volgens onderstaand plaatje, die we willekeurig van een richting voorzien.
PI ~------------------~
3
4
5
De prijs van een rn3 gas in Pk is wk. Uit Pk wordt per tijdseenheid uk gas uitgevoerd
(~
en beginpunt van
rn3
<0 betekent invoer); het prijsverschil tussen eindpunt
pijp~
is
v~.
Langs
pijpleiding~
wordt per tijdseenheid
t~
m3 gas vervoerd (t~ < 0 betekent dat het transport tegen de pijlrichting in geschiedt). We nemen aan dat geen gas verloren gaat.
-
19 -
Zij
wl w=
ui
w2
u2
u =
w3
t =
u3 u4
w4
ti
VI
t2
v2
t3 t4
V=
v3 v4
ts
vs
t6
v6
De onderlinge ligging van de steden en pijpleidingen wordt beschreven door een matrix A( 4 xG) =[a .. ] waarvan '-J
a .. = '-J
{-~
als p.l. beginpunt is van pijp j ; als p.l. eindpunt is van pijp j; anders.
Dus 0
A=
0
We
kunnen
de
0
-I
0
0
-I
-I
0
-I
-I
0
0
0
~· ~·
0
-I
0
De samenhang tussen
0
v en w wordt nu gegeven door
beschrijving uitbreiden met beschouwingen over transportkos-
ten; we zullen dit niet doen. We wijzen er op dat volkomen analoge beschouwingen gelden voor electrische netwerken. Een systeem bestaande uit eindig veel punten met gerichte verbindingen heet een gerichte graaf. Een matrix zoals A heet de incidentiematrix van de gerichte graaf. Ook in andere problemen waarin de gerichte graaf een rol speelt is de incidentiematrix een machtig hulpmiddel.
- 20 -
1.2.2. Evenwicht van de prijsbalans Een n tal producenten P 1 , ••• ,Pn produceren elk één product g 1 , ••• ,gn. Pi koopt en verbruikt per jaar een deel, nl. aij• van de jaarproductie van het product gj. We nemen aan dat het systeem van producenten en producten gesloten is, d.w.z. dat de gehele productie aan g 1 , ••• ,gn door P , ••• ,Pn wordt 1 verbruikt en dat niets van buiten het systeem wordt toegevoegd. (Deze aanname is iets minder streng dan op het eerste gezicht lijkt omdat we altijd kunnen veronderstellen dat een overproductie aan gi door Pi wordt opgenomen en dus verrekend wordt in a ..• ) ~~
Voor de matrix A= [a .. ] geldt nu: ~J
(i)
a .. ~J
"'
0
(i,j = I , ... , n)
dus
A"' 0
n (ii)
l:
i=l
a .. =
(j = I , ... , n)
~J
(P 1 , ••• ,Pn gebruiken per jaar de hele geproduceerde hoeveelheid gj). Een matrix A die voldoet aan (i) en (ii) heet ruilmatrix. Laat de prijs van
î
a .. w.; de inde jaarproductie van gj zijn wj. De uitgave van Pi is dan j=l ~J J komst van P.~ is w.~ (interpreteer dit goed als a ~~ •. > 0).
Beschouw de prijsvector
w =
w
n
Het productiesysteem met ruilmatrix A heet in evenwicht als er een prijsvector ::'."' Q, ::'.I Q bestaat zó dat geen van de producenten P 1 , ... ,Pn genoodzaakt is meer uit te geven dan hij ontvangt. Evenwicht betekent dus dat er w ;" Q, ::'_ 1 0 bestaat zó dat Aw ,; w Een vector w die aan (*) voldoet heet een stabiele prijsvector van A. Het lijkt alsof dit een ongelijkheid is; dit is echter niet zo, want:
Voor iedere w die aan Aw ,; w voldoet is Aw n
Aw ,; w
en
.L
J=l dan is
= w.
Stel nl.
- 21 n
n
.l:
w. > ~
~=1
n
l:
i=l
n
l:
(
a .. w.) = 1J J
j=l
l:
n
l:
w.
j=l
J i=l
n
l:
a ..
~J
w.
j=1
J
hetgeen onmogelijk is. De stabiele prijsvectoren zijn dus oplossingen ~ ~
(I -
Q,
~ ~
A)~=
Q van
Q·
A~=~(~ ~
Als
heet een eigenvector van A, zie 2.6.11) ofwel
een oplossing is en r
~
0, dan is ook
~
een oplossing;
voor evenwicht is alleen de onderlinge verhouding der prijzen van belang.
Men kan bewijzen dat er bij iedere A die aan (i) en (ii) voldoet een
~ ~ ~
w I 0 bestaat met Aw = w.
1.2.3. Input-output-analyse Een concern bestaat uit n fabrieken F 1 , ••• ,Fn die elk één product maken: g 1 , ••• ,gn resp. Voor de bereiding van één eenheid g. gebruikt fabriek F. een J
J
hoeveelheid van b .. eenheden van product g .• 1J
~
De matrix B = [b .. ] heet de consumptiematrix van het productiesysteem. Ken-
cr.
nelijk is B ~
~J
Als e: de hoeveelheid van product g. is die niet binnen het 1
1
concern gebruikt wordt, x. de geproduceerde hoeveelheid vang., dan is ~
~
n
x.
~
=
e. + ~
l:
b •. x.
j=l
~J
J
(i = I , ... ,n) .
Met
kan dit geschreven worden Laat nu B
~~gegeven
als:~=~+ B~
of
(I-
B)~
= e •
zijn; we willen nu B beschouwen als de consumptiema-
trix van een productiesysteem als zoëven beschreven. Nu doen zich de volgende vragen voor.
- 22 -
(i)
Is dit mogelijk, d.w.z. bestaat er een x ~
~
f Q zó dat
Q?
(I - B)~ ~
(ii)
Q,
Zo ja, welke van de producten g , ••• ,gn worden in overschot door het 1 systeem geleverd; we zeggen dat het systeem gi effectief produceert ~
indien er een x (I -
B)~ ~
0 bestaat zó dat
0
en
x.].
J
J=l
b .• x. > 0 •
l.J J
(iii) Gegeven een systeem dat alle producten g 1 , ••• ,~ kan produceren, dan is het uiteraard mogelijk een gevraagde productie~ te maken; d.w.z. er is
een~~
Q zó dat (I -
B)~ ~ ~·
Men kan bewijzen dat het dan ook
mogelijk is de gevraagde productie precies te leveren zonder enig overschot van één van de producten. D.w.z. men kan een niet negatieve oplossing vinden van het stelsel in x 1, ••. ,xn (de benodigde hoeveelheden): (I - B)~ = ~ •
Voor elke
~ ~
Qblijkt
de oplossing dan éénduidig bepaald te Zl.Jn:
x = (I - B) -I~
1.2.4. De methode der kleinste kwadraten Het gebeurt in de praktijk heel vaak dat we metingen verrichten van een verschijnsel dat afhangt van een veranderlijke. Meten we bijv. de afgelegde weg van een deeltje dat zich met constante snelheid beweegt, dan is de gemeten grootheid, y, afhankelijk van de tijd, t. Laat het volgende tabelletje de meetresultaten weergeven:
- 23 -
~
11
0
3
5
8
10
2
5
6
9
II
Anderzijds weten we dat het verband tussen y en t lineair is: y
= vt
+ a.
Als we in een grafiek de waarnemingsuitkomsten uitzetten blijkt er geen rechte door te gaan. y
11
9
•
6
5
2
5
3
8
10
t
Dit brengt ons op het probleem de rechte te vinden die het "best" past bij de gevonden resultaten. We moeten een criterium hebben dat aangeeft wat we onder "best" verstaan. Men gebruikt meestal het volgende: Laat t -
= [t 1, .•• ,t n l
de waarden van de onafhankelijke veranderlijke
x_= Ly 1 , ... ,yn] de gemeten waarden. Dan is yi = vti + a + ri
zijn,
(i = 1, ••• ,n).
We trachten nu die waarden van de getallen v en a te vinden waarvoor
n
2
LI r.1
minimaal is.
We moeten dus v en a bepalen zó dat n
s
=
l:
i=l
(y. - vt. - a) 1
2
1
minimaal is. Laat e = [ 1,1,1, ... ,1] zijn. Nu is (zie l.I. 7): S = (x_ -
v~
= v 2 (~,!)
-
a~,
x_ -
V! -
a~) =
+ 2av(!,~ + a 2 (~,~) - 2v(x_,!) - 2~(x_,e) +
(x_,x_) •
- 24 -
S is dus een gewone tweedegraads vorm in a en v.
Dit zijn 2 vergelijkingen waaruit de ven a te berekenen zijn (zie§ 3.1). Omdat (!,!)(~,~) ~ (!,~)
2
(zie 2.!.6), is er sprake van een minimum.
In ons voorbeeld vinden we voor (*) {198v + 26a = 227 26v + Sa = 33 met als oplossing V "" 0,88, a .. 2,01.
!.2.5. Markov processen. Een bevolkingsprobleem In een land trekt elk jaar 2!% van de plattelandsbevolking naar de stad en vestigt zich 1% van de stadsbevolking op het platteland. In het jaar t = 0 woont 60% van de bevolking in de stad; 40% op het land. Hoe is de situatie I
jaar later en 10 jaar later en op den duur?
Zij
~t
= [::]
waarbij st het gedeelte van de totale bevolking, N, is dat in jaar t in de stad woont en it het gedeelte dat op het land woont. Dan is: 0,99 s 0N + 0,025 i N 0 o,ot s N + o,97S i N 0 0
- 25 -
Met p
10,99
lo,o1
o,oz5l
0,97~
staat hier: ~I = P~o· Hieruit volgt ~IO = P 10 ~ 0 • (Merk op dat de Markov matrix, P, een matrix is van het soort dat in 1.2.3 ruilmatrix genoemd werd.) De verdeling op den duur zou iets betekenen als lirn Pt~o· Als we een eigent-"" vector~
2.6.11)
bij eigenwaarde I (zie
x I 0 van Px = p =
~·
kunnen vinden, d.w.z. een oplossing
dan is dat een stabiele verdeling. Schrijven we
1-p [ p
dan is de oplossing van Px
=x
de vector:
In de stabiele toestand woont dus
-,----:q'--::- = ~ p + q I
deel van de bevolking in de
stad. 1.2.6. Nog een Markov proces De totale cernentmarkt in een land is in handen van slechts drie leveranciers A, B, C. Elk jaar verliest A 5% van zijn klanten aan B en 10% aan C; 35% van de klanten blijft A trouw. Leverancier B behoudt 75% van zijn klanten; hij verliest 15% aan A en 10% aan C. C behoudt 90%, verliest 5% aan A en 5% aan B. In zeker jaar was de verdeling van de kopers over A, B en C resp. 40%, 20% en 40%. Hoe was het een jaar later; en twee jaar later? Welke verdeling van de klanten aantallen is de stabiele? Het antwoord op deze vragen geeft aanleiding tot rekenwerk als in
1.2.5.
1.2.7. Kevers uit Birma In Birma leeft een soort kevers, waarvan de maximale levensduur drie jaar is. Voortplanting vindt alleen in het derde jaar plaats. Neem aan dat het gedeelte van de éénjarigen dat het tweede levensjaar ingaat p is; het gedeelte van de tweejarigen dat overleeft tot in het derde jaar zij q; en het gemiddelde aantal nakomelingen van een driejarige kever zij r. (We rekenen alsof elke driejarige precies r nakomelingen heeft.)
- 26 -
Zij het aantal eenjarige kevers in jaar t
xt, het aantal tweejarige Yt en
het aantal driejarige zt' dan is 0 0 q
Hieruit volgt pqr
dat
~t+) =
pqr
~t'
zodat de keverpopulatie uitsterft als
I, toeneemt als pqr > I, stabiel is (gerekend per driejarige cyclus:)
<
als pqr =I. 1.2.8. Het dieetprobleem We bespreken nu enkele voorbeelden waar het essentieel gaat om het vinden van het maximum of minimum van een lineaire vorm
f(~)
:=
(~,~)
in
~·
als
~
te-
vens voldoet aan een aantal vergelijkingen of ongelijkheden. Optimaliseringsproblemen als deze behoren tot het terrein der lineaire programmering (zie
§
3.5). In het klassieke voorbeeld van het dieet gaat het over de sa-
menstelling van een gezonde voeding tegen minimale kosten. Laat er n levensmiddelen L 1 , ••• ,Ln beschikbaar zijn, bijv. brood, aardappelen, bonen, enz. Een dieet
is een lijst bevattende de dagelijks te eten hoeveelheden van L 1 , ••• ,Ln. De benodigde voedingsstoffen zijn s , ••• ,Sm, bijv. eiwit, vet, koolhydraat, 1
calcium, vitamine A, enz. Laat in A(mxn) =[a .. ] het element a .. aangeven lJ . l.J het aantal eenheden Si in een eenheid Lj. Laaf de dagelijkse behoefte aan Si zijn b.1 eenheden; zii
Voor een goed dieet is
A~~ ~·
Als Pj de prlJS is van een eenheid Lj en
p = [p , ..• ,pn]' dan is de dagelijkse prijs van het dieet: 1
pr(~)
:=
(~,~).
- 27 -
De taak van de diëtist 1s nu: vind bij gegeven A, b en
E
onder alle vectoren
d die voldoen aan: d "' 0 Ad <: 0
er een waarvoor
(E,~)
minimaal is.
We zullen in 3.5.2 zien dat we zulke problemen steeds kunnen schrijven als: vind onder de positieve oplossingen Bx
=c
~ <:
0 van een stelsel vergelijkingen
er één waarvoor een lineaire vorm
(S,~)
minimaal is.
1.2.9. De volgende opgave 1s een voorbeeld van het type problemen aangegeven in 1 . 2. 8. Grondstof voor beton is een mengsel van zand, grint en beton. Het gewicht van zand, grint, cement per m3 zij resp. 3, 4, 2 ton. De prijs van zand,
grint en cement per m3 bedraagt 20, 30, 50 gulden resp. Wegens kwaliteitseisen moet een betonmengsel voor tenminste 30 volume
% uit cement en voor
ten hoogste 20 volume % uit grint bestaan. Typische vragen zijn nu: 1. Wat is de mengverhouding van het goedkoopste mengsel?
2. Hoeveel weegt het zwaarste mengsel dat aan de kwaliteitseisen voldoet; wat kost dit per m3 ; wat is de samenstelling van dit beton? 3. Wat is het zwaarste mengsel dat voor ten hoogste f 30,-- per m3 geleverd kan worden?
1.2. 10. Klassificatie van kegelsneden Beschouw de kromme K in het XY vlak met vergelijking ax
2
+ 2k xy + by
2
Merk op dat de oorsprong punt van symmetrie 1s: als (x ,y ) 0 0
(-xo,-Yol " K.
( I)
= c . E
K, dan 1s ook
- 28 -
We proberen door een draaiing van het assenkruis de vergelijking in de vorm a.~ 2 + Bn 2 = c te krijgen. y
p
ry
x
De samenhang tussen oude en nieuwe coÖrdinaten is: x = t; cos y
t; sin
q>
"'
- n sin
"'
(2)
+ n cos q>
We schrijven ' A = [:
Nu
~s
kl , S = bj
[c~s
s~n
q> q>
- sin
cos
:J .
(I) te schrijven als
T x Ax
=
c
en (2) is te schrijven als
x = St; waaruit volgt T
s_=s~
(3)
In het (t;,n) stelsel heeft K als vergelijking (4)
Als
- 29 -
[: :J dan 1.s
2 a = a cos ~ + 2k cos
~
sin
y = (b - a) sin
cos
~
+ k(cos
- 2k sin
~
cos
B = a sin We bepalen
~
2
~
zó dat tan
De vorm (4) is nu
a~
2
~
2k a-b
2~
+ Bn
2
,
~
~
+ b sin 2~
2
~
-
sin
+ b cos
2
2
~)
~
dan is y = 0 en
= c.
Uit (3) volgt STS = SST = I. We zetten s =
dan 1s S =
~c~qJ; ~lil ~
[~,!].
t = [-sin cos
~J
~
Nu is AS = SD ofwel As
ex~,
At
Bt (zie 2.6.11).
1.2.11. Een productieproces We besluiten deze paragraaf met een iets ingewikkelder voorbeeld. Een drinkwaterfabriek maakt ruw grondwater geschikt voor levering aan een waterleidingbedrijf door het viermaal een periode van biologische zuivering te laten doormaken. Deze vier perioden zijn even lang. Het bedrijf beschikt over vier bassins, genummerd 1,2,3,4 waarin achtereenvolgens de eerste, twee-
de, derde en vierde zuivering plaatsvindt. Alle vier bassins zijn gelijktijdig in bedrijf. Na afloop van elke zuiveringsperiade wordt water overgepompt van bassin 4 naar het waterleidingbedrijf, van bassin 3 naar 4, van 2 naar 3 en van I naar 2. Bij het overpompen van water uit bassin i (i= 1,2,3,4) blijft een vast deel, d, van de inhoud in bassin i achter, een vast deel b, komt in de volgende productiefase, de rest, I - b- d, gaat bij het overpompen verloren. Tenslotte wordt voor de nieuwe periode ingaat N m3 onbewerkt grondT
water in bassin I gebracht. In de vector ~(t) = [s 1 (t) ,s (t) ,s (t) ,s (t)J 2 3 4 stelt s. (t) het aantal m3 water voor, dat zich gedurende periode t in bassin l i bevindt. Aan het einde van periode t wordt dan bs 4 (t) m3 aan het waterleidingbedrijf geleverd. Zij
- 30 -
d
0
0
0
b
d
0
0
0
0
b
d
0
0
0
0
b
d
N V :=
dan is
~(t
0
A :=
A~(t).
V+
+ I)
We willen berekenen hoe groot de inhoud van de bassins moet zijn opdat deze 4 elke periode dezelfde is. Dit betekent dat we moeten proberen een s € lli te vinden die voldoet aan s = v + As. Anders geschreven: (I-
A)~
= v. We kunnen
dit direct oplossen en vinden dan s = N[
b
I
I - d '
(I - d)
2
'
(I - d)
3 '
We bespreken echter een andere gedachtengang. Als we over een inverse van I- A zouden beschikken zou de oplossing zijn: s =(I-A)
-I
:!._·Nu is
Dit doet ons aan machtreeksen denken. We definiëren ean limietbegrip voor matrices aldus: lim B
n
n-+oo
ben en dat lim (B ) .• n~
n ~J
B betekent dat alle Bn en B hetzelfde formaat heb-
=
= B. .
1)
voor alle i en j •
2 2 We zullen nu bewijzen dat de matrix-machtreeks I+ A+ A +A + ..• con vergeert. Het 1s dan duidelijk dat de som de inverse is van I - A. Zij 0
z dan
:=
0
0
0
0
0
0
0
0
0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
' z3 = 0
0
0
0
0
0
0
0
0
0
l.S
0
0
en A3
0
0
z4 = 0. = d3 I +
2 2 2 2 Nu geldt A = di + bZ; A = d I + 2bdZ + b z (denk aan IZ 4 2 2 2 3 3 3d bz + 3bd z + b z • Omdat z = 0 is algemeen:
(We gebruiken hierin het binomium van Newton.)
ZI
Z)
- 31 -
Hieruit volgt: 00
dn)I + ( L
(~)dn-l)bZ
00
+
+ <
(~)dn-2)b2Z2
+
n;O
n~O
n~o
(I
I
n~O
Op grond van de convergentie van de machtreeks 00
L
dn ~ (I - d)-1
n~o
en van haar afgeleiden naar d vinden we
l:
n~o
(I - d)-
1 2
(I- d)- b
(l-d)- 3b 2 4
(I - d) - b 3
0 (I -d)-l (I - d)
-zb
(I - d) -3b2
0
0
0
0
1 (I - d) 2
(I- d)- b
;
0
(1-d)-l
(I-A)- 1
.
-
32 -
LINEAIRE RUIMTEN EN LINEAIRE AFBEELDINGEN
HOOFDSTUK 2
2.1. De ruimte Rn
§
2. l.I. De verzameling van alle kolomvectoren met n rijen noemen we Rn (n
=
I
,2, •.• ). In het verleden (wiskunde IB) schreven we de elementen van R2
en R 3 als rijvectoren; voor de meetkundige interpretatie maakt het echter geen verschil of we de coÖrdinaten van een punt onder of naast elkaar schrijven. Voor elementen a en b van IRn definieerden we in
~ + !?_, r~ (r
§ I. I:
E
JR),
(~,!?_). Als we de elementen van een vector uit JR2 en lR 3 beschouwen als coör-
dinaten van een punt hebben deze bewerkingen een meetkundige betekenis. Als we een punt opvatten als het eindpunt van een pijl (deze pijl noteren we met~)
ook weer ten) en
r~
die in
~begint,
dan zijn a+!?_ (parallellogram van krach-
juist de bewerkingen die men in de mechanica met zulke pijlen
(daar eveneens geheten vectoren) toepast. We zullen in de toekomst de pijlbeschouwing en de puntbeschouwing gelijktijdig toepassen.
2
2. 1.2. Het inwendig product in JR Zij
~ [:~] =
dan is
1(~,~)
=
laf +
a~
de afstand van a tot 0. We noemen dit
ook de lengte van de pijl !!:• notatie 11 a 11. Eveneens is l(a- È_, !!: - È_) de afstand van a tot b. Volgens de cosinusregel 1s: (~- !?_,~-
!?_) =
(~,!!:)
+ (È_,È_)-
211~11
ll!?_llcos
~,
(q> is de hoek tussen ~en È_:
hieruit volgt (~_,È_)
=
Nu betekent (~,È_)
11 a 11 llb llcos
=0
~
.
dat de lijnstukken d~ en ~È_-onderling loodrecht zijn.
Opmerking. De analoge interpretatie van (!!:,~) en (~,È_) voor a en b
E JR
3
1s
eenvoudig te verifiëren.
Opmerking. Als een massapunt van
~
naar È_ verplaatst wordt onder invloed van
een kracht die in grootte en richting overeenkomt met arbeid:
(~,È-
-
~).
~'
dan is de verrichte
- 33 -
2.1.3. Meetkunde met vectoren in De verzameling {~ = [x,y]
I
rn2 a + À~, À
x
€
R} is bij vaste ~ en ~· ~ # 0
2
uit ~ , de verzameling van alle (pijlen met beginpunten in~ en eind-) punten op een rechte door a waarvan de richting dezelfde is als van (het seg-
cr en
ment beginnend in
eindigend in)
~·
De uitdrukking
~
= a + Àv heet een
parametervoorstelling van deze rechte; a heet steunvector, v heet richtingsvector.
Voorbeeld 1.
~
= [1,2] + À[3,1]
(À
E ~).Op
deze rechte ligt
x= [10,5],
want we kunnen een À vinden zo dat 10 = I + 3À { 5 = 2 + À nl.
À
= 3. Het punt [4,-1] ligt niet op de rechte. Het snijpunt met de x-as
is te vinden uit: of
+ 3À
2 +
À
waaruit volgt: À = -2, p = -5. Om de vergelijking van de rechte te vinden moeten we À elimineren uit + 3À
2 +
À
Resultaat x - 3y + 5 = 0. Is omgekeerd een vergelijking gegeven: 2x + y - 12 = 0, dan zijn heel gemakkelijk parametervoorstellingen te vinden. Bijv. neem x = À, dan is y = - 2À + 12. Dus
Voorbeeld 2. Zij
~
= [2, IJ + À[3, I] een parametervoorstelling van R- 1 ; 2x + y - 12 = 0 de vergelijking van R- , dan vinden we het snijpunt door À te 2 berekenen uit 2(2 + 3À) + (I + À) - 12 = O, À= I, en in te vullen in de parametervoorstelling van R- 1 : het snijpunt is [5,21.
- 34 -
Voorbeeld 3. De vergelijking van een lijn
L
v is:
(~,~)
= C.
De richtings-
vector van een normaal van een rechte met vergelijking ax + by + c
=0
is
[a,b]. Een vector met de grootte en richting van het verbindingasegment van A= [a ,a J en B = [b 1 ,b 2 J is [a 1 - b , a 2 - b 2 J. Een parametervoorstelling 1 1 2 van de lijn door AB is nu:
We illustreren vectorbeschouwingen nu aan enkele bekende stellingen uit de planimetrie. Voorbeeld 4. De hoogtelijnen van een driehoek gaan door één punt.
B
c
=
A= a
er
Plaats de driehoek als in de figuur: C = er, Vergelijking van h : (~.~) a
<~.~)
~: (~.~) = (~.~)
Het snijpunt
s
=
=b
s voldoet aan
A=~·
B = b.
- 35 -
crs heeft
richtingsvector~ (paramete~oorstelling ~=À~).
tingsvector
~
~·
-
Nu is
(~- ~,~)
=0
AB heeft rich-
dus ÓS is een hoogtelijn, q.e.d.
Voorbeeld 5. De diagonalen in een ruit delen elkaar loodrecht middendoor.
B
=b
c
s
A= a
Plaats de ruit met één hoekpunt in
a.
Uit het feit dat OACB een ruit is
volgt:
Parametervoorstelling van ÓC is: x=
À(~+~),
van AB: x=
a+~(~-~).
Nu
is
dus ÓC
L
BA. S volgt uit: À(~+~) = ~ + ~(~- ~)
of
(À + ~ -
1 )~ = (11 -
À)~ •
Van deze twee laatste vectoren valt de linker langs óA, de rechter langs ÓB, dus beide zijn
Q (vergelijk
À + 11 -
f
11 -
À
1
=0 =
0
met
§
2.3). Dus
ós
= !de
q.e.d.
- 36 -
Voorbeeld 6. Stelling van de Ceva. S is een willekeurig punt binnen
~
ABC;
AS, BS en CS snijden de overstaande zijden in A', B', C'. Nu geldt: AB' A'B
BC' B'C
CA' = C'A
~-~-::::!....
(AB' duidt de lengte van AB' aan).
c•
A= a
B= b
We kiezen S = Q_, A=: ~· B =: ~. C =: ~· Dan is lijn SA': x = À~; lijn BC: x= b + \!(~ - ~); omdat A' op BC ligt zijn er getallen r en r zó dat 3 1 Noem r + dan I := geldt c = 0. rl~ = ~ + r3(~-~). rz, rl~ + rz!?. + r 33 (Zie ook § 2.3.) We kunnen nu lijn BC ook schrijven met dA' als steunvector:
1
r ~ + v(~- ~)
x=
.
Een vector, v (b - c) met grootte en richting van het lijnstuk CA', is nu c-
-
te vinden uit: = - r !?_ -
2
=
Ir 2 1
3 + v c(b-
- c) • -
+ v )c = (v - r )~ en dus (zie voorbeeld 5) cc 2 3 11~ - ~11. Evenzo vinden we: A'B = Jr 3 J 11~- ~ll en
Hieruit volgt: (I + r CA'
r ~
CA' A'B
=
lr 2 l ïr;ï
V
c
- 37 -
Analoog:
AB'
BC' --= c'A
-- =
B'C
q.e.d.
Voorbeeld 7. De vergelijking van een cirkel met middelpunt a en straal ris: (x-~· ~- ~) = r 2 • De poollijn van~ is (~- ~· ~- ~) = r 2 ; deze gaat door~ als (~- ~· ~- ~) = r 2 • De poollijn van q: (~- ~· S- ~) = r 2 gaat dan ook door
~·
2.1.4. Meetkunde met vectoren in ~ 3 In
m3
~ = ~
hebben we analoog aan wat we in 2.1.3 voor
[x,y,z] =
~
+
À~, ~
§
dat
(richtingsvector).
Zijn v en w twee vectoren zó dat (zie
vaststelden
# Q, de parametervoorstelling is van een rechte door
richting~
(steunvector) met
m2
~.
v en w niet op een rechte liggen
2.3), dan is X
=a
+
ÀV
+
\lW
de parametervoorstelling van een vlak door
~
evenwijdig aan het vlak door
~.
v en w.
Een vlak wordt ook gekarakteriseerd door een vergelijking, ax + by + cz uit een parametervoorstelling vindt men de vergelijking door mineren. Merk op dat x= a+ Àv x = a (
y
=
a
1
2
+ l.v + ).v
z = a + 3
1
2
ÀVJ
+ llW + \1W +
+~drie
1
2
].lWJ
als
À
en
\1
= d;
te eli-
lineaire betrekkingen zijn, nl.:
-
Voorbeeld 1. De
rechte~=
38 -
[1,1,1] + À[O,I,2].
Het punt [1,3,5] ligt op deze rechte (neem À= 2 !). Het snijpunt met het xy-vlak (vergelijking z = 0) vinden we uit: 0
=z
= I + 2À, À= - !; snij-
punt [I,!,OJ. De rechte snijdt het yz-vlak (x= 0) niet, omdat (de verbindingslijn
van~
tot) [0,1,2] evenwijdig is aan het vlak x= 0.
Voorbeeld 2. Beschouw het vlak ~
= [1,2,3] + À[O,I,I J + 11[1,0,-2]
Het snijpunt met de y-as vinden we uit: + 11
0 = x =
11
{ 0 = z = 3 + À - 211
= -1
À =
snijpunt [0,-3,0] •
-5
De vergelijking van het vlak is 2x + y + z = 3. De snijlijn met het x,y-vlak wordt gegeven door het paar vergelijkingen:
z =0 { 2x - y + z = 3 of ook door {
z2x= 0 - y
=3
•
Deze snijlijn heeft bijv. als parametervoorstelling (neem x = À, dan y
= 2À-
3, z
= 0):
x= [0,-3,0] + À[l,2,0] • Voorbeeld 3. Het snijpuntS van de
rechte~=
[1,1,1] + À[0,1,2] met vlak
2x - y + z = 3 vinden we door À op te lossen uit 2(1) - (I + À) + (1 + 2À)
=3
;
À
=I
S=[l,2,3].
Voorbeeld 4. Om een parametervoorstelling te vinden van het vlak met vergelijking 2x- 4y + 3z = 12 stellen we bijv. y =À, z x= 6 + 2À - 311, zodat we hebben verkregen x= [6,0,0] + À[2,t,O] + ~[-3,0,2]
= 211,
dan is
- 39 -
Voorbeeld 5. Om een parametervoorstelling te vinden van de snijlijn van de vlakken x+ y
= I,
2x- y + z = 3 stellen we bijv. x=
À;
dan is y = I
-À,
z = -)À + 4, zodat we als parametervoorstelling vinden: x= [O,I,4] + À[I,-I,-3] • Voorbeeld 6. De vergelijking van een vlak ~ ~ is: (~,~)
= C.
Een lijn lood-
recht op het vlak met vergelijking ax + by + cz = d is de lijn door
~
en
[a,b,c]. Het vlak door de punten A=~= [ai,a 2 ,a J, B = b = [bi,b 2 ,b J en 3 3 C = ~ = [ci,c ,c 3 J (A, Ben C liggen niet op een rechte, zie§ 2.3) heeft 2 bijv. als parametervoorstelling:
of: x
=a
+ À(~- ~) + ~(~- ~)
Voorbeeld 7. De vergelijking van de bol met 2
(~- ~· ~- ~) = r • Het poolvlak van
middelpunt~
en straal ris:
R t.o.v. deze bol heeft als vergelij-
king: (x - a, p - a) = r 2 • Dit vlak staat dus loodrecht op op de bol ligt (dus (R - ~·
R-
R-
~· Als
R zelf
~) = r 2 ) is het poolvlak een raakvlak.
We beperken ons tot één echt meetkundig voorbeeld. Voorbeeld 8. Als va~ een viervlak twee paren overstaande ribben elkaar loodrecht kruisen, is ook het derde paar onderling loodrecht.
c
B
A
- 40 -
Bewijs. Zij
cr = Q,
A
= ~·
B
= ~.
zullen nu laten zien dat ook crc (~.~
-
= 0,
~)
(~.~
- ~)
= 0;
C i
=~
en zij gegeven crA
i
BC,
dB
AC. We
i
AB. Het gegeven luidt in vectorvorm
=
hieruit volgt (~,~)
(~.~)
dus (~,~- ~)
= 0,
q.e.d.
2.1.5. Meetkundige terminologie in Rn (n > 3) Ook voorn> 3 voeren we meetkundige terminologie in. Neem bijv. n punt
Q=
De verzameling{~ E R4 vector
I
[0,0,0,0] heet de oorsprong; {[a,O,O,O]
en~
I
We noemen /(~- b
E R}
Het
heet de x-as, enz.
~=~+À~, À ER} heet.een rechte met a als steun-
als richtingsvector
Evenzo zeggen we voor
a
= 4.
(~,~)
= 0:
(~
f Q).
~ i~·
x loodrecht op
~·
~- ~) =: 11~ - yll de afstand van x en ~· Dat dit een te-
rechte naamgeving is, m.a.w. dat
11~
- ~11 > 0
11~
-
~11 = 11~
-
~11
11~
-
~11
-
~11
,;
11~
als x # ~
(driehoeksongelijkheid)
+ 11~ - ~11
is direct duidelijk met uitzondering van de driehoeksongelijkheid die volgt uit 2.1.6. 2.1.6. Stelling (Cauchy-Schwarz). Voor alle~·~
Bewijs. Als x = 0 is er niets te bewijzen. Als vierkantsvorm
~
E
~n geldt
# Q is voor alle
À
ER de
- 41 -
Voor de discriminant geldt derhalve
Opgave. Zij ~ E JRn, ~ fo .Q. en bestaat zo dat
§
(!_,~) (z,z). Bewijs dat er een r E 1R
=
z = rx. z fo
.Q.· Bepaal bij elke!. het getal a(~) zó dat de vector x loodrecht staat op~· (We noemen a(~)~ de projectie van~ op y4)
Opgave. Zij zE JRn, a(~)y-
(!_,zl
2.2. Lineaire deelruimten
2.2.1. Definitie. Een niet lege verzameling L van vectoren uit JRn heet een lineaire deelruimte van JRn indien: (a) voor alle x E L,
zEL
geldt x +
z E L;
(b) voor alle x E L, r E IR geldt rx E L. (We spreken in plaats van over lineaire deelruimte ook wel kortweg over deelruimte of lineaire ruimte,) Voorbeelden
I
x E JR} is een deelruimte van JR2 ,
I.
L := {[x,OJ
2.
JRn is een deelruimte van zichzelf.
3.
Als 0
=
[O, ••• ,O] de nulvector uit JRn is, dan is {O} een deelruimte van
IRn, geheten nulruimte. Uit (b) en 4.
Q=
0~ volgt dat 0 EL voor elke deelruimteL van JRn,
Voortgebrachte deelruimte. Als
~~·~ ,
2
n .
•..• ~k een aantal vectoren uit 1R
een deelruimte van JR0 deelruimte met
1
L(~ ,
•
•.•
~s,
dan is
We noteren deze zgn. voortgebrachte lineaire ,~k).
Een vector
r ~
1 1
+ ••• + rk~k noemen we een
lineaire combinatie van ~l'''''~k' Is Meen willekeurige verzameling van vectoren, dan is ook de verzameling van alle lineaire combinaties van
- 42 -
eindig veel elementen uitMeen lineaire deelruimte; notatie: L(M). Beschouwt men nu b~v. de lineaire deelruimte van ~4 opgespannen door a:= [ 1,1,2,0],
~
:= [0,2,0,1]
en~:=
[0,0,1,3], dan is de vraag: is
d := [d 1 ,d 2 ,d 3 ,d 4 J element van 1(~.~·~), in feite de vraag naar het bestaan van reële getallen x 1 , x 2 , x 3 zó dat d = x ~ + x h + x ~. Dit is 1 2 3 een stelsel lineaire vergelijkingen in x , x 2 , x , nl. 1 3 dl = XI d2 = XI + 2x d3 = 2x 1 d4 =
2 +
x3 xz + 3x3
Zo is E 1(~,~.~)
[1,3,4,7] en
[1,3,4,6] i 1(~.~·~) 5.
Oplossingsruimte. Oplossingen van het stelsel
= 0
+ ••• +
zijn vectoren uit ~n. De verzameling van alle oplossingen vormt een deelruimte van ~n, de oplossingsruimte van het stelsel. Deze noteren we wel als N(A) indien A = A(mxn) =[a .. ]. Dus 1.]
N(A) := {~ 6.
E
IRn
Ax = O}
Orthogonaal complement. Zij M een deelverzameling van IRn. Als ~ l we
~ 1
M; dit noteren we wel als
(~,M)
Is Meen deelverzameling van IRn, dan is M.L := {~
E
~n
I~
.L M}
z voor
= 0.
alle
z
E
M dan zeggen
- 43 -
een deelruimte van Rn: het orthogonaal complement ("orthoplement") van M. .L Voorbeeld 6 bevat 5 als een bijzonder geval want N(A) = R als R de verzameling is van de rijvectoren van A. Dit laatste voorbeeld leidt tot de volgende belangrijke stelling. 2.2.2. Stelling. Is
~
1 , ••.
een aantal vectoren
,~k
. u~t
!Rn , d an LS .
In woorden: het orthoplement van een eindige verzameling vectoren is gelijk aan het orthoplement van de door die vectoren voortgebrachte lineaire deelruimte. Opmerking. De stelling geldt ook voor oneindige verzamelingen vectoren maar dat zullen we niet gebruiken. Bewijs. Afkortingen: M := {~ , ••• ,ykl, L := L(M).
1
(i)
Als~
r 1y
1
(ii) Daar
E
M.L, dan is (~,yi) = 0
(i= I, .•• ,k). Voor elke vector uit 1:
+ ••• + rkyk geldt dan:
~I E
L, ••. ,yk
L volgt uit x .L Look x .L y 1 , .•• x .L H. Conclusie: L.L c M.L. E
,~
.L yk, dus
Eindconclusie: L.L =~.q.e.d. 2.2.3. Definitie. Een verzameling vectoren van de gedaante a + L
{a +
~
I
~
E
L}
waarbij a € !Rn en L een deelruimte van Rn is heet een lineaire variëteit. Voorbeeld. Is a een oplossing van oplossing van Ax
=~de
lineaire
~
=
~.
d.w.z.
variëteit:~+
A~= ~.
dan is de algemene
N(A).
We zien zonder moeite dat a + L zelf een deelruimte is dan en slechts dan als a
E
L.
- 44 -
2.2.4. Meetkundige betekenis van de begrippen lineaire deelruimte en lineaire variëteit 2
In R is een lineaire deelruimte, verschillend van {Q} en van R 2 , een rechte door
§
2.3. Afhankelijkheid en onafhankelijkheid
2.3.1. Definitie. De vectoren y 1 ,y , ••• ,yk uit Rn heten afhankelijk (of li2 neair afhankelijk) als er reële getallen r , ••• ,rk bestaan, die niet alle 1
nul zijn zodanig dat
Anders gezegd: y , ••• ,yk zijn afhankelijk als 1
Q op
meer dan een manier als
lineaire combinatie (2.2.1) van y , ••• ,yk te schrijven is. (Steeds is 1 '.) 0 0 0 - = Yt + • • • + Yk Voorbeeld. De vectoren a := [1,1,2,3], b := [O,I,O,I] en c := [!,3,2,5] zijn afhankelijk want 0 = a + 2b - c
Het homogene stelsel 0 = xa +
y~
+ ze
of 0 =
x
0
x + y + 3z
0
= 2x
+
z
+ 2z
0 = 3x + y + Sz
heeft een van x= 0, y = 0, z = 0 (de nuloplossing) verschillende oplossing, bijv.: x = I, y = 2, z = -I.
- 45 -
2.3.2. Definitie. De vectoren y ,y , ••• ,yk uit mn heten onafhankelijk als ze 1 2 niet afhankelijk zijn. Anders gezegd: y 1 , .•• ,yk zijn onafhankelijk als uit r y 1 + •.• + rkyk 1 volgt r = r = ••. = rk = 0. 1 2 Voorbeeld.~:=
[1,1,2,3],
~ :=
=
0
[0,1,0,1] end:= [1,3,2,6] zijn onafhanke-
Q volgt: +
r1
r3 3r r1 + r2 + 3 2r + 2r 3 1 3r + r2 + 6r 1 3
=
0
=
0
=
0
=
0
Vooruitlopend op beschouwingen over stelsels vergelijkingen schrijven we dit stelsel nu met behulp van de R 3 vectoren ~ := [1,0,1], ~ := [1,1,3], ~
3
:=
[2,0,2],
~
1
4
[3,1,6], r := Cr ,r ,r J als: 1 2 3
:=
2
(~1 ,E_) = 0
(~2 .~) = 0 (~3 ,E_) =
0
(~4 ,E_) = 0 (~
4
- ~
2
0, dus r 3 = 0. Daarna volgt uit (~ ,E_) = 0 1 dat ook r 1 = 0 en tenslotte uit (~ ,r_) = 0 dat r = 0. (Merk op dat we ge2 2 bruik gemaakt hebben van 2,2.2.)
Hieruit volgt:
3
- ~ ,E_) =
2.3.3. Meetkundige betekenis van afhankelijkheid In R2 en (I)
m3
geldt:
Twee rechten zijn evenwijdig (of samenvallend) als hun richtingsvectoren afhankelijk zijn.
(2) Een vlak door
~bestaat
uit alle vectoren die een lineaire combinatie
zijn van twee onafhankelijke vectoren. (3) De rechte x = x
=b
~
+
À~
is evenwijdig met (of ligt in) het vlak
+ ~~ + v~ als ~· ~ en ~ afhankelijk zijn. Omdat ~ ;
x - a +
\~geen
rechte) en omdat
~en ~onafhankelijk
in dit geval uit de afhankelijkheid van combinatie is vanven w (ga na).
~· ~
Q (anders
is
zijn (vlak!) volgt
en w dat u een lineaire
- 46 -
(4) De punten
~·
b en c liggen op een rechte als b - a en c - a afhankelijk
zijn. (5) De punten ~· ~. c en ~ liggen in een vlak als b - ~· c - ~· d - a af-
hankelijk zijn. 2.3.4. Eigenschappen Door nauwgezette toepassing van de definities zijn de volgende eigenschappen te bewijzen: 1.
0 is een afhankelijk stelsel.
2.
Als
3.
Is een van de vectoren y , ••. ,yk de nulvector, dan is y 1 , ••• ,yk afhanke1 lijk.
4.
Het iStelsel y 1 ,y , ••• ,yk is dan en slechts dan onafhankelijk als 2 ~ + y ,y , ••• ,yk onafhankelijk is. 1 2
1
~ , •••
,yk een afhankelijk stelsel is, dan is ook y 1 , ••• ,yk' afhankelijk.
1
~ , ••• ,~i
2
a+
0; het stelsel y 1 ,y 2 , .•• ,~k is dan en slechts dan onafhankelijk als ay 1 ,~ 2 , ••• ,~k onafhankelijk is.
5.
Zij
6.
Als y 1 , ••• ,yk een afhankelijk stelsel is, dan is tenminste één der yi een lineaire combinatie van de overige vectoren uit het stelsel. Is nl. r 1y 1 + ••• + rkyk v.
-~
rl r. -1
--V
=0
en ri
ri-l
-
~
---v. r. ~
-~
+ 0,
dan is
ri+l r. -i+!
- --v ~
rk r. -k
- -v ~
2.3.5. Het onderzoek naar de afhankelijkheid van een stelsel Door herhaalde toepassing
van de eigenschappen 4 en 5 tracht men het onder-
zoek naar de afhankelijkheid van een stelsel te vervangen door het onderzoek van een ander, eenvoudiger stelsel. Het systematisch uitvoeren van dit procédé noemen we "vegen" .
- 47 -
Voorbeeld I.
Zijn~=
[-J,I,l],
~
= [1,2,3],
~
= [5,1,3] afhankelijk?
Schrijf de vectoren onder elkaar en veeg de tweede kolom schoon: a= [-1,1,1]
a= [-1,1,1] b
=
[J ,2,3]
b- 2a = [3,0,1]
Omdat blijkbaarc-a =
a= [6,0,2]
c-
c = [5, I , 3]
2(~- 2~),
dus 3a- 2b + c =
~.
is het stelsel af-
hankelijk. Voorbeeld 2. Is!!.= [1,2,3], a = [I ,2,3]
~
= [2,7,0],
a + 3c
=
~=[1,2,-1]
[4,8,0]
afhankelijk?
a + 3c - 2b = [0,-6,0]
b = [2,7,0]
b = [2,7,0]
b = [2,7,0]
c = [1,2,-l]
c=[1,2,-l]
c=[l,2,-l]
Het laatste stelsel is onafhankelijk en !!.•
~. ~
dus ook.
r C0,-6,0] + r C2,7,0] + r [1,2,-l] = Q volgt: 2r + r = 0, 2 2 3 1 3 - 6r + 7r + 2r 3 = 0, r = 0 en dus r r 2 = r = 0. 2 1 1 3 3 Immers uit
Voorbeeld 3. Het ~
stelsel~=
[7,8,0,0],
~=[I
,2,4,3],
~
= [0,0,4,3] is afhankelijk, daar 2a- llb- 3c + 8d = 0
= [1 ,-2,-4,-3], (ga na!).
2.3.6. Stelling. Indien L(y 1 , ••• ,yk) ~ {Q}, dan heeft y 1 , •.. ,yk een onafhankelijk deelstelsel dat ook L(y 1 , ••• ,yk) voortbrengt. Bewijs. Als y , ••• ,yk onafhankelijk is, dan is er niets te bewijzen, anders 1 is een der vectoren, zeg v., een lineaire combinatie van de overige -~
(2.3.4.6). In dit laatste geval is: L := L(v- 1, ... ,vk) = L(v ,v.+l'"''vk) - 1 , ••• ,v. -~- 1 -~
-
-
Indien y 1 , .•. ,yi-l'Yi+l'''''yk nog steeds een afhankelijk stelsel is kunnen we wederom een der vectoren weglaten. Dit herhalen we tot we een onafhankelijk stelsel voortbrengenden bereikt.
overhouden. Daar L
~
{O} wordt dit inderdaad
- 48 -
2.3.7. Een orthorrormaal stelsel vectoren is een stelsel y 1 , •.• ,yk waarvoor geldt: (v. , v.) = { OI -1 -J
als i = j als i .f J
(In woorden: alle v. hebben lengte -1
en zijn onderling loodrecht.)
We hebben nu: Stelling. Een orthorrormaal stelsel is onafhankelijk.
(i = I , ••• , k)
Als y 1 , ••• ,yk orthorrormaal is, is echter (r 1y 1 + ••• + rkyk,yi) = ri, dus r. = 0 (i = I, ••• ,k), q.e.d. 1
§
2.4. Bases
2.4.1. Definitie. Zij~~·····~ een onafhankelijk stelsel in Rn dat de deelruimteL .f {Q} voortbrengt, dan heet ~ 1 , ••• ,~ een basis van L. Voorbeeld.
~I
:= [I,O,O, ••• ,O], ~
2
:= [O,I,O, ••• ,O], ••• , e
-n
:= [0,0, ••. ,IJ
is een basis van Rn. Deze noemen we de standaardbasis. In 2,3,5 is bewezen dat L(y , ••• ,yk)' mits# {Q}, een basis heeft. 1
2.4.2. Stelling. Is w , ••• ,w een basis voor de deelruimteL van Rn, dan is -1 -m elk element van L op éénduidige wijze te schrijven als lineaire combinatie van
~
1
, •••
,~.
Bewijs. Omdat L =
L(~
1 , ••• ,~)
is elke x EL te schrijven als lineaire com-
binatie van~~·····~· Stel
en x = s
1~1
+ ••• +
sm~
- 49 -
dan is
Omdat
~l'''''~m
onafhankelijk zijn is nu q.e.d.
Een lineaire ruimte kan verschillende bases hebben. Zo zijn a= [1,1,0,0] en b = [1,2,0,0] bases voor L(~ .~ )
1 2
2.4.3. Stelling. Is
~l'''''~k
c
~ 4 • Echter:
een basis van de lineaire ruimte L, en is
~ ,
1 •.. ,~ een onafhankelijk stelsel vectoren in L, dan is m ~ k.
Bewijs. Stel m
1 1
~I= r ~
~I
#
>
k. Daar
~l'''''~k
een basis van L vormen , is
+ ... + rk~k' Omdat ~I voorkomt in een onafhankelijk stelsel, is
Q
(2.3.4.3), dus [r 1 , ••• ,rk] # [0, ••. ,0]. Uitsluitend voor het gemak van de notatie nemen we aan dat r # 0 is (verandering van de volgorde van 1
de ~~·····~k). Nu is a-I
= _I r
r2
rk
b --a -1 r -2 I I
--a r
I
Als we in iedere lineaire combinatie van
-k ~l'''''~k' ~I
vervangen door de nu
gevonden uitdrukking zien we dat
Hieruit volgt:
Hierin is [s , ..• ,sk] # [0, ••• ,0] (anders was ~ .~ afhankelijk en volgens 2 1 2 2.3.4.2 ook ~ , •.. ,~). Neem gemakshalve aan dat s # 0. Dan is 2 1 SI
b a =_I b - s -1 -2 s2 - 2 2
en dus
s3
s
~3
2
- ... -
- 50 -
We herhalen nu dit uitwisselingsproces. Nakstappen hebben we verkregen dat L
Q
L(~ 1 ,
••• ,~k). Maar dan, daar
2m
spraak met de onafhankelijkheid van
EL, is~= t 1 ~ 1 + ••• + tk~k in tegen-
~~·····èm·
Dus m >kis onjuist, q.e.d.
2.4.4. Gevolg. Elk (n+l)-tal vectoren uit Rn is afhankelijk. 2.4.5. Gevolg. Elke deelruimte van Rn wordt door ten hoogste n vectoren voortgebracht. 2.4.6. Gevolg. Elke deelruimte van Rn heeft een basis. 2.4.7. Gevolg. Elke basis van een deelruimte van Rn bestaat uit evenveel vectoren. ~ ,
1 ••• ,~k en
Bewijs. Als
1 ••• ,~ bases zijn van L, dan is k s men m s k.
~ ,
2.4.8. Definitie. Het aantal vectoren in een basis van de lineaire ruimte L heet de dimensie van L ("dim L"). De dimensie van een lineaire variëteit, ~ +
L, is gedefinieerd door
We hebben: dim Rn
Q
dim(~
n; dim {O}
Q
+ L) := dim L.
0; voor elke deelruimte L van Rn geldt
0 ,; dim L ,; n. 2.4.9. Stelling (uitbreidingsstelling). Zij Leen deelruimte van Rn, dim L
Q
k < n; zij y 1 , ••• ,yk een basis van L, dan heeft Rn een basis ~ , .•• ,yk' ~~·····~-k" (Deze basis van Rn ontstaat dus door uitbreiding van =
1
de basis van L met n- k vectoren.) n
n
Bewijs. Neem een basis u , ••• ,u van R, d.w.z. L(u , ••• ,u) R. Het stel-1 -n -1 -n sel y , •.• ,~k is onafhankelijk. Volgens het uitwisselingsprincipe (zie 2.4.3) 1 zijn k van de u's uit de basis van Rn uit te wisselen voor y 1, ••• ,yk' q.e.d. Q
2.4.10. We onderzoeken het verband tussen een k-dimensionale deelruimteL n
k
van R en R. Laat
~~·····~keen
basis van L zijn; elke vector uitLis nu
eenduidig bepaald door een !. = [r 1 , ••• , rk J E Rk, nl. middels ~ r 1y + ••. + rkyk. De getallen r , ••• ,rk heten de coÖrdinaten (ook wel 1 1 componenten) van x t.o.v. de basis y 1 , ••• ,~k" Q
- 51 -
Dit één-éénduidige verband tussen L en Rk draagt ook de optelling en scalai-
'
re vermenigvuldiging over:
Als nl.
= a 1 ~ 1 + ••. +
~
ak~k' È_
~
= b 1 ~ 1 + •.• +
,_, Ca 1 , ..• ,akJ, È. +-+ Cb , ••• ,bkJ' dan a+ b 1 a~ <-+ [ aa , ••• , aak ] •
bk~k'
+-+
met andere woorden
Ca 1 + b 1 , •.• ·~ + bkJ;
1
Iedere k-dimensionale lineaire ruimte ziet er precies zo uit als (we zeggen: . 1S
. f 1SOIDOr
met ) ~k •
2.4.11. De basis ~~····•~n van Rn is tevens een orthonormaal stelsel;
we
noemen een basis die tevens orthonormaal is een orthonormale basis. Stelling. Elke deelruimte L van Rn heeft een orthonormale basis. Bewijs. Laat
~~·····~keen
basis voor L zijn. We construeren uit deze basis
een orthonormale basis door middel van het zogenaamde orthonormalisatieproces van Gram en Schmidt
~,
I := ~ ~,
I
~2 := 11!:!:211 :!2
enzovoort. Op deze wijze verkrijgt men een orthonormale basis y 1 , •••• ~k· §
2.5. Het bepalen van een basis
2.5.1. Stelling (veegstelling). Voor alle stelsels y 1 , ••• ,~ uit Rn geldt:
(i i i )
L (V- I • V- 2 ••••• VI ••••• V -<. -m ) ~ L (V- I 'V- 2 •••• ,o.v- k ••••• V -m )
(iv)
L(v- ,v- , ••• ,vk, •.• ,v) - •.. ,v,, -~ -m = 1 2 (S
E
R) •
(>< ' lH. "
I
0)
- 52 Het bewijs van deze stelling bestaat uit een herhaling van reeds gegeven argumenten. Deze stelling drukt uit dat de veegtechniek, geintroduceerd in 2.3.5, ook gebruikt kan worden voor het bepalen van bases. 2.5.2. Voorbeeld.~= [O,O,I,I,I], ~ ~
= [0,1,2,3,4],
= [0,2,3,5,7],
~ = [0,3,6,2,-2],
~
= [0,0,0,0,1]. Bepaal een basis voor 5 L := L(~.~·~·~·~) c R • Bij de nu volgende berekening zullen we vele malen een beroep moeten doen op de regels (i), (ii), (iii) en (iv) van stelling 2. 5. I.
Allereerst: L = L(~·~·~·~·~). x= [0,1 ,2,3,4]
x = [ 0,1 ,2,3,4] V
= [ Ü, 2, 3, 5, 7]
w
=
[0,3,6,2,-2]
v- 2x = [0,0,-1,-1,-I] w- 3x = [0,0,0,-7 ,-14]
u= [O,O,l,l,I]
u= [O,O,I,l,I]
~
~
= [ O,O,O,O,I]
= [O,O,O,O,l]
We zien nu:
L
= L(~, ~- 2~, ~- 3~, ~· ~)
= L(~,
~·-
7I
(~- 3~), ~)
Van dit laatste viertal voortbrengenden is onmiddellijk te zien dat het lineair onafhankelijk en dus een basis is. We krijgen een fraaiere basis (waarom?) als we nog even verder werken. Zij
t
:=-!7 (w-
3x). -
= [0,1,0,1,2] = [0,0,1,1,1]
x= [0,1,2,3,4]
x - 2u
u = [0,0,1,1,1]
u
t = [O,O,O,l,2]
t = [0,0,0,1,2]
~=
[0,0,0,0,1]
x - 2u - t = [0,1 ,0,0,0] u- t = [O,O,I,0,-1] t = [0,0,0,1,2] ~=
[0,0,0,0,1]
~=
[0,0,0,0,1] x-
2u -
u-
t + t
-
t = [0,1 ,0,0,0] ~=
[O,O,I,O,O]
= [O,O,O,I,O] ~= [O,O,O,O,l]
2~
Conclusie: L = L(~2'~3'~4'~5). 2.5.3. Het met de hand uitvoeren van het veegproces kan op vele manieren; de ene manier 1s handiger dan de andere. We willen het nu ook nog op een meer systematische manier beschouwen, die in de praktijk tot een computerprogramma zou kunnen worden uitgebouwd. We wijzen er met klem op dat de rekentechniek van het vegen het fundament is waar de hele verdere ontwikkeling op rust.
- 53 -
Laat~~·····~ vectoren uit Rn zijn. Beschouw een matrix A(mxn) waarvan de rijen de vectoren y 1, ••• ,~ zijn. We kunnen nu het veegprogramma uitvoeren voor de rijen van A. Voor later gebruik zullen we nu de rijen Q niet weglaten. De overige veegbewerkingen zijn nu geformuleerd voor rijen van A: (a) Verwisseling vandek-de en de
~-de
rij.
(I') Vermenigvuldiging van de k-de rij met
<1
c JR,
<1
+ 0.
(y) Vcrvanging vandek-de rij door de som vandek-de rij en B maal de
~-de
rij. Het standaardveegprogramma is nu het volgende: I
Begin bij de eerste kolom van A; is deze 0 (uit Rm) neem dan de tweede het laagste rangnummer zijn van een kolom die ongelijk Q 1 niet bestaat is A(mxn) = [0]); verwissel, zo nodig, rijen zo-
kolom; laat k is (als k
1 dat het eerste element van de k 1-de kolom+ 0 wordt; deel daarna de eerste rij door het element dat dan in de k 1-de kolom op de eerste plaats staat. De matrix heeft nu de vorm (m
= 4,
n
7, bijv. k 1 = 2, . duidt een ele-
ment aan waarvan we nog niets weten) 0
0 0 0
Trek veelvouden van de eerste rij van de tweede t/m m-de rij af zó dat de k -de kolom de §.I uit !Rm wordt ("veeg de k 1-de kolom schoon met de 1 eerste rij"). A wordt dan 0
II
0
0
0
0
0
0
Als in de nu verkregen matrix de tweede t/m m-de rij alle gelijk
Q (uit
!Rn) zijn, dan zijn we klaar. Laat anders k 2 het rangnummer zijn van de eerste kolom van links af aan die een element 0 heeft in de tweede t/m
+
m-de rij (gevolg k
2
>
k ); verwissel, zo nodig, rijen om te verkrijgen 1
- 54 -
+
dat het tweede element van de k 2-de rij 0 wordt; deel de tweede rij door dit element; veeg de k 2 -de kolom met de tweede rij schoon. We hebben dan (gesteld k
= 4)
2 0
0 0
0
0
0
0
0
0
0
0
0
0
III Herhaal de procedure nu; k
is het rangnummer van de nu meest linkse ko3 in de derde t/m m-de rij een element 0 heeft. Verwis-
+
lom die ergens
sel, zonodig, rijen zodat het element in de derde rij, k -de kolom onge3 lijk 0 wordt; veeg de k -de kolom schoon. Daarna met k , enz. 3 4 Op zeker moment hebben we het volgende bereikt: de k -de kolom is tot e r -r (uit Rm) veranderd; verder gaan is niet mogelijk, hetzij doordat r = m, hetzij doordat r < m en de rijen met nummers r+l, ... ,m zijn 0. We zijn nu klaar; A heeft zijn normaalvorm gekregen, Bijvoorbeeld: 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
kt = 2, k2 = 4, k3 = 5 0
of 0 0
0
0
0
0
0
0
0
0
0
0
0
kt = 2, k2
4, k3 = 5, k4 = 6
.
0
2.5.4. We geven dit programma in een zgn. blokdiagram. Wat men doen moet is volgens de pijlrichting het schema doorlopen tot men bij klaar uitkomt. Op elk moment heeft men op papier of in het geheugen van de computer een matrix A= A(mxn) en twee natuurlijke getallen i en j. Een rond hokje duidt op een vraag, een rechthoek op een opdracht. Een opdracht is steeds het veranderen van A, i of j. De oude waarden van deze grootheden worden dan weggeveegd. Met j := j +
bedoelen we: maak de nieuwe waarde van j gelijk aan de oude
plus t; j := J + t is dus de opdracht verhoog j met t. We beginnen met A: de oorspronkelijke matrix; i= t en j = t.
- 55 -
[iegin: A
= ;,;:-
~orspronkelijke matrix,
----------- ---- f
~ Zijn aij'ai+l,j'
=
I, -_j
-d-
;Î
\\-;----<11~-------l[[:~JT
ai+Z,j'''''amj alle ''-._geil_' jk aan nul? ' ------------
j
1 \
ja ~
neen
Is~~
!
l
i
Zoek het eerste element uit
neè!J
\ja '
a . . , a. • , ••• , a . dat onge1J 1+ 1 ,J mJ
lijk aan nul is; laat dit I
a . zijn PJ
-------.---
I
!
neen~ i?
ja
Verwissel de i-de en de p-de rij
I
j
rij door a ..
1J
Trek voor q
=
1 ,2, ... ,i-1 ,i+l, ... ,m
a qJ. ______________________ maal de i-de rij van de q-de rij af~
Is i = m ?
a
Klaar~
De matrix A heeft --~n~e~e~n~--~,Is
nu cte normaalvorrn
J
n/?~·~--~~a----~-----------1
- 56 -
Opmerking. Om de afrondingsfouten te verkleinen zal men in de praktijk in plaats van ! een andere opdracht geven. Opmerking. Als men bovendien de kolomnummers k , ... ,kr van de eenheidsvecto1 ren ~~·····~r (uit ffim) wil vastleggen, kan dit door op de plaats aangeduid met* de opdracht: jzet ki- jl in te lassen. ~~-'
2.5.5. De verkregen normaalvorm kan nu beschreven worden met: ~
k 1 < k 2 < ••• < kr s n en de ki-de kolom is
I.
Er zijn getallen I !Rm.
2.
ledere kolom met rangnummer ki
<
k
<
~i
uit
is ~; iedere kolom met rangnummer k met 1 ki+l heeft nullen op de laatste (m-i) plaatsen; iedere kolom <
k
met rangnummer groter dan kr heeft nullen op de laatste (m-r) plaatsen. Gevolg. De eerster rijen zijn+ 0 (uit Rn); de laatstem- r rijen zijn+ 0. Resultaat. De eerste r rijen van de normaalvorm van A vormen een basis (de zgn. standaardbasis) van de door de rijen v , ••. ,v opgespannen deelruimte. - 1 -m Deze standaardbasis heeft het voordeel dat de componenten van elke vector uit de deelruimte t.o.v. deze basis direct af te lezen zijn.
§
2.6. Lineaire afbeeldingen
2.6.1. Definitie. Een afbeelding A van Rn in Rm heet lineair indien (i)
voor alle x c Rn en
y_ E Rn geldt:
(i i) voor alle x E Rn en a ER
geldt:
A(~
+ y_) =
A(a~) =
N.B. We schrijven voor het beeld van x vaak Ax.
-
~
aAx.
-
+ Ay_;
- 57 -
Als n
= m spreekt
Als m =
men wel van een lineaire operator.
spreekt men wel van een lineaire functionaal.
Voorbeeld. Beschouw in ~3 de orthogonale projectie op het x,y-vlak, dit is de afbeelding A: [x,y,z]
+
[x,y,O]; deze is lineair.
We beschouwen nu een algemener voorbeeld. 2.6.2. Voorbeeld. Zij A(rnxn) een matrix. Voor elke~ duct ~
E
schouwd
worden;~
E
~nis het matrixpro-
.IRm (herinner U dat de elementen uit .IRn en ~m als kolomvectoren beduidt hier matrixvermenigvuldiging aan). De afbeelding
die aan x toevoegt:
a
mn
x
n
1s lineair. We duiden deze"parabus de language" weer aan met A. We merken op
dat de kolommen van de matrix A juist de beelden zijn van de eenheidsvectoren e , ••• , e u1. t IRn . - 1
-n
We zullen bewijzen (2.6.4) dat dit voorbeeld volkomen algemeen is, dat nl. . bij elke lineaire afbeelding van IRn 1n
~m
· hoort en omgek eerd. een matr1x
Eerst enige eigenschappen: · · A: IRn 2 •6•3• Z1J
+
IRm 11nea1r, · · dan ge ld t:
(i)
A.Q_ = A(O . .Q_)
(ii)
A(-
~) = -
= OAO =
0 (E IRm !) ;
Aa
(iii)
2.6.4. Stelling. Laat ren e , •••• ~ - 1
n
.
n
u1t IR
A: !Rn geldt:
+ ~m
lineair zijn. Als voor de eenheidsvecto-
- 58 -
all
al2
Ag! =
aln
... '
A~2 =
a mi
Ae-n = a
am2
mn
dan geldt voor elke x uit IRn dat a12
all
aln
XI
x2 Ax=
a mn
am2
a mi
x
Bewijs. Voor elke x
n
IRn geldt: x= x e + ••• +x e ; wegens 2.6.3 (iii) is 1- 1 n-n en wegens de definitie van matrixvermenigvuldiging ~ = xlA~l + •.. +xn Ae -n klopt dit. E
Voorbeeld. De matrix van de afbeelding uit het voorbeeld 2.6.1 is
Opmerking. Voor elke lineaire functionaal IRn +Ris er een ~
= [a 1 , •.• ,an]
E
IRn zodat de functionaal is x+(~,~).
2.6.5. Stelling 2.6.4 geeft aan hoe de matrix van een lineaire afbeelding opgebouwd wordt uit de beelden van de eenheidsvectoren. Als we de beelden van een andere basis geven, dan zullen we de matrix bepalen op de wijze als nu besproken aan de hand van een !R 3 + !R4 afbeelding. Laat van A gegeven zijn
·ll
3
10 5
Al:l
2 =
2 8
0
·l:l·
3 I
6
- 59 -
I
Programma. Neem de gegeven basisvectoren van R3 als rijen van een matrix M; hun beelden als de overeenkomstige rijen van een matrix N. Dus
M=
[:
N=
;]
0
3
10
2
8
[:
6
i]
Omdat de rijen van M een basis van R 3 vormen is de normaalvorm (zie 2.5.5) van M (ga na):
r: : :J De normaalvorm van M wordt uit M gevormd door herhaalde uitvoering van de bewerkingen (a), (S) en (y) uit 2.5.3. Voer met de rijen van N precies dezelfde bewerkingen uit; het resultaat is een matrix S. De matrix T van A is nu S (ga na). ll
Uitvoering
~
3
10
r:
2
8
~ J ~ :J r: ~ j [;
2
8
3
10
[:
0
+
+
0
[;
+
-I
0
+
0
0
r:
0
:]
+
~
0
r:
+
0
:1 r:
:J
6
;]
6
2
8
3
10
-1
-2
;]
-1
-2
3
10
2
8
-1
-2
3
10
4 -1
-2
2
6
4
-:] -:] -:J 2
3
.
- 60 -
De matrix van A is dus 0 -I
2
-2
6
4
-5
2
3
Controleer het antwoord! Voorbeeld. Projecteer de R3 met orthogonale projectie op het vlak V: x + 2y + z = 0. Dit is een lineaire afbeelding P. Om de matrix te bepalen merken we op dat voor vectoren in het vlak Px
=~geldt,
terwijl voor vecto-
ren loodrecht op het vlak Px = 0 is. Dus
Volgens het zoeven beschreven procédé is de matrix van P:
p =
i [-~ -~ =~] -1
-2
5
Een andere methode om dit te doen is de volgende: breng door aan
.l
~
c IR 3 een rechte
V; snijd deze met V en druk de coÖrdinaten van het snijpunt uit in de co-
ordinaten van a. Dit snijpunt is Pa. 2. 6. 6. !Je gaan voort met de bestudering van een afbeelding A: Rn
->-
Rm. De
matrix t.o.v. de standaardbases geven we ook aan met A. (Merk op dat het hele betoog nu verder op twee wijzen geïnterpreteerd kan worden, nl. doordat men Ax nu kan lezen als "het beeld van x onder de afbeelding A", en ook als "het matrixproduct van A met de (n x I) matrix x".) Eigenschappen I.
Is Leen deelruimte van Rn dan is A(L) een deelruimte van Rm. Bewijs. Zij A~ 1
O.QI
= Q1 ,
A~
21
E
A(L) en
22
E
A(L) en r
2 = Qz• Nu is Ql + 22
o.A~I = A(~l)
E
E
R. Er zijn
=~I+ ~
A(L), q.e.d.
2
~I
~
en
= A(~l + ~ 2 )
E
2 in L zodat
A(L) en
- 6! -
De bewijzen van de overige eigenschappen zijn van hetzelfde eenvoudige karakter. 2.
Is V een deelruimte van Rm, dan is A+(V) een deelruimte van Rn.
3.
In het bijzonder is A(Rn) een deelruimte van Rm.
Definitie. A(Rn) heet de beeldruimte van A.
4.
In het bijzonder is A+({O}) een deelruimte van Rn.
Definitie. 5.
+ A({~})
heet de kern van A; notatie N(A).
A(Rn) = L(A~ 1 ,A~ 2 , •.. ,A~n). De beeldruimte wordt opgespannen door de kolommen van de matrix.
6.
N(A) is de nulruimte van de matrix A.
7.
Stellen
e 1, ••• ,Sm
de rijen van A voor, dan is N(A)
_L
== {a , ••• , a } .
-1
-m
Definitie. De rang van A is de dimensie van A(IRn). 8.
De rang van A is de dimensie van de ruimte opgespannen door de kolomvectoren.
9.
+
Als Aa = ~. dan is A ({~}) = ~ + N(A).
10. A is dan en slechts dan één-éénduidig als N(A) = {O}. 2.6.7. Dimensiestelling. Zij A: IRn ~ Rm lineair, dan is
dim N(A) + dim A(Rn) = n • Bewijs. Daar N(A).c Rn geldt k :=dim N(A)
$
n. Als k =nis N(A) = IRn en
A = [O] en dim A(Rn) = 0, klaar. Stel k
zijn van N(A), vul die aan (2.4.9) met 1 , •.. ,~ een basis n y , .•. ,yn-k tot een basis van R. Daar A~ 1 = ••• =A~=~. is 1 <
n; laat
~
- 62 -
Het bewijs is geleverd als we hebben laten zien dat Ay 1 , ••• ,Ayn-k een onafhankelijk stelsel is. Stel r 1Av- 1 + •.• + r n- kAv-n-k = 0 dan is
en dus
Daar
~
1
, ••• ,~k
een basis voor N(A) is, is
Hieruit volgt 0 = r 1 = ••. = rn-k (= s 1 = ••• = sk) omdat y 1 , ••• ,yn-k een onafhankelijk stelsel is, q.e.d. .
. . (mxn)
2. 6. 8. Stel 1 1ng. Z1J ft.
~ , ••• ,~k'
1
een matrix. De dimensie van de ruimte opgespannen
door de rijen (deelruimte van Rn) is gelijk aan de dimensie van de ruimte opgespannen door de kolommen (deelruimte van Rm) en derhalve gelijk aan rang A. Bewijs. Laat Q. 1 := [a 11 , ••• ,a 1nJ'.••• , zijn, dan is
12m
:= [am 1 , ••• ,amn] de rijen van A
N(A)
(2.2.2).
Wegens 2.6.7 is dim(N(A))
= dim(L(Q. 1 , ••• ,Q.m)) 1 = n-
rang(A)
Hieruit volgt dim(L(b , ••• ,b )) = n- dim(L(b , ••• ,b ))
-1
~
-1
~
1
=rang A,
q.e.d.
Gevolg. De rang van een matrix is gelijk aan de rang van zijn normaalvorm. Gevolg. Het getal r uit 2.5.5 is de rang van de matrix.
- 63 -
.,
... h. 'I.
(mxn)
1.aat A
. . . n . m lnx ,) een 1 lneatre afbeeldtng van IR 1n U< bepalen en B' 1 een
afbeelding van IRP in IR.n. ZijC(mxw =AB de productmatrix. Deze bepaalt een afbeelding van IRP in IR.m, die de samengestelde,AoB,is van A en B; met de definitie van afbeeldingssamenstelling kunnen we dit aldus formuleren: Stelling. Voor alle x uit IRP geldt: Cx
= A(B::c_)
•
Bewijs. We zullen laten zien dat het element in de i-de rij en j-de kolom van A0 B overeenkomt met c .. (zie 1.1.8). De j-de kolom van AoB is A(Be.), lJ ~ e. uit IRP. Dit is -J
A b . !TIJ
Het i-de element van deze vector is: q.e.d.
2.6.10. Laat in het bijzonder A een lineaire afbeelding vanIR.nop IR.n zijn. Uit 2.6.8 volgt dat iedere lineaire afbeelding van IR.n ~IR.n automatisch éénéénduidig is. De afbeelding A heeft nu een inverse. Uit 2.6.9
volgt dat de
matrix van de inverse afbeelding de inverse matrix is. Merk op dat I de matrix van de identieke afbeelding is. Dit geeft ons een mogelijkheid om met behulp van de techniek uit
§
2.5 de inverse van een matrix te bepalen. Uit
het voorafgaande volgt dat een
n x n
matrix dan en slechts dan inverteer-
baar is als de rang n is. Het is vanwege de eigenschappen van functiesamenstelling ook evident dat de rechter en linker inverse van een inverteerbare matrix gelijk zijn (zie 1.1.10.8). We behandelen een voorbeeld: Zij
- 64 -
Als A inverteerbaar is vormen de kolommen een basis van R3 (dit is het geval!). De inverse matrix wordt nu op de wijze van 2.6.5 berekend uit: -1 -1 -1 A [1,2,0] = [1,0,0]; A [I,I,I] = [O,I,O]; A [1,0,3] = [0,0,1}. Resultaat
Controleer het antwoord! 2.6.11. Eigenwaarden en eigenvectoren Definitie. Zij A: Rn A indien er een v
E
+
Rn lineair. Een getal À
Rn, ~ #
Q,
E
bestaat zó dat Av
een eigenvector bij de eigenwaarde
R heet een eigenwaarde van
= Àv.
Deze vector v heet
À.
We hebben al verschillende malen gezien hoe eigenwaarden en eigenvectoren in de toepassingen een rol spelen. Meetkundig zijn eigenvectoren vectoren
rr
waarvan het beeld op de lijn door
Stelling. Als À een eigenwaarde van
~
#Q
en v ligt.
A(nx~ is, dan is {~
E
!Rn
I
Av =
À~} een
deelruimte van Rn met positieve dimensie. Stelling. Een getal
À
is een eigenwaarde van A dan en slechts dan als
dim N(A - ÀI) > 0 is. Alle vectoren # 0 uit N(A- Àl) zijn eigenvectoren van A bij eigenwaarde À. Het vinden van eigenwaarden en eigenvectoren komt neer op het vinden van een À
en een
~
# Q die voldoen aan: al2v2 +
+
a21 v I + (a2 2 - À)v 2 +
+
(all -À)vl +
a
v
n2 2
+ ••• + (a
nn
-
À
)v
n
= 0 •
We behandelen een voorbeeld van het bepalen van eigenwaarden m.b.v. het vegen.
- 65 -
Zij
Een getal
À
is een eigenwaarde van A als dim(N(A - U))
A- U
t_, -3
we willen: rang(A - Àl)
1-À
-']3
2
-À
;
3. Dan moeten de rijen afhankelijk zijn. Tel de
<
eerste rij 3 maal bij de tweede en
-À
-I
À
0;
-I
2
Opdat
>
maal bij de derde op. Er komt:
2 -
À
-IJ
2 +
À
0
0
.
een eigenwaarde is moeten dus [3(À-2), À+2, O]
[(À-2)(À-I), À+2, 0]
en
afhankelijk zijn. Dit is het geval bij
À
= 2,
À
= -2,
À -
I = 3, dus
À
= 4.
Omdat eigenvectoren bij verschillende eigenwaarden onafhankelijk zijn (ga dit na:) heeft een n
x
n matrix ten hoogsten verschillende eigenwaarden.
Het berekenen van de eigenvectoren homogene stelsels (zie
{_
XI - xz -
3x 1 - x
Oplossing:~=
2
§
1S
nu een kwestie van het oplossen van
3. I). Bijv. voor x3 = 0
+ 3x
3
= 0
of
r
À
-
= 2 vinden we xz - x3
- 4x
2
0
= 0
a[I,O,I]; controleer dit!
Het berekenen van eigenwaarden op deze manier is niet erg handig: er bestaan handigere methoden die buiten het bereik van dit college vallen. (Zie appendix.)
- b7 -
HOOFDSTUK 3 §
LINEAIRE VERGELIJKINGEN EN ONGELIJKHEDEN
3.1. Homogene lineaire vergelijkingen
3.1.1. We beschouwen het stelsel: a 11 x
+ a x + 12 2 1 a21"1 + a22x2 +
+ a
x
1n n
= 0
+ a2 n x n = 0
(I )
Zij A=A(mxn) = [a .. J; zij a ~J
-1
[a
=
11
, ... ,a nJ' ... , ~ = [aml '' '' ,amn]· 1
We hebben al gezien dat de oplossingen van (I) een deelruimte van Rn vormen, nl. N(A) = is een van
_L
(L(~ ,
1 ••• ,~m)) , We noemen N(A) ook oplossingsruimte van
(I). Er
Q verschillende oplossing dan en slechts dan indien rang A
Het berekenen van de oplossing gaat via de algoritme van 3.1.2. Stelling. Laat
Ade
§
n.
<
2.5:
normaalvorm zijn van A, dan is N(A) = N(A).
Bewijs. De rijen van A en A spannen dezelfde deelruimte op. (mxd
een matrix zijn in normaalvorm. Laat k ,k , ••• ,kr de kolom1 2 men zijn waarin de eenheidsvectoren uit Rm staan, dan vindt men elke oplos3.1.3. Laat A
sing van Ax = 0 door aan alle x 1 , ••• ,xn met uitzondering waarden toe te kennen en
de~
van~,
I
••.
,~
r
, •.• ,xk uit te rekenen. r
I
Voorbeeld 0
A=
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
kl = 2, k 2 = 4, k3 = 6., rang A = 3, dus dim N(A) = 7 - 3 = 4. De oplossing van Ax= 0 is nu = ÀI ' x3 = À2' "s = À3' x7 = À4' derhalve "2 = - 2 À2 - À3 - À4' x4 = - À4' x6 = - À4.
x,
- 68 -
Dit kunnen we ook schrijven als:
x
= À
+
À
1[I ,o,o,o,o,o,oJ 3
+
À
2co,-2, 1,o,o,o,oJ
+
[0,-I,O,O,I,O,O] + \[O,-I,O,-I,0,-1,1]
Uit het feit dat dim N(A)
=
4 volgt ook dat we de algemene oplossing hebben.
We formuleren het nog eens anders: Laat A een Ax
mx n
= Q krijgt
matrix zijn. Een basis voor de oplossingsruimte van
men aldus:
(I) Breng A op normaalnorm.
(2) Splits de veranderlijken in twee x~
I
, ..• ,x 1
groepen:~,
••.
,~
I
n-r
(3) Voor elke iE {1,2, ••. ,n-r} neemt men xt. = I, xt. 1
kent
en de overige, zeg: r
men~,
I
••.
,~.
=0
(j f i) en bere-
J
Zo verkrijgt men telkens een oplossing.
r
(4) Den-roplossingen die men zo vindt vormen een basis van N(A).
§
3.2. Inhomogene lineaire vergelijkingen
3.2. I. We beschouwen het stelsel
= bi
allxl + al2x2 +
+ alnxn
a21xl + a22x2 +
+ a2nxn = b2
(2) = b
m
- 69 -
A,
~!
, ••.
·~zijn
als in 3.2.!; zij
We kunnen (2) schrijven als Ax = b. Volgens de bloknotatie is
[A,~]
=
a mn
Men noemt A en
[A,~]
de bij (2) horende kleine en grote matrix.
Door herhaling van reeds gegeven argumenten kan men alle onderstaande beweringen bewijzen. (a) Het stelsel (2) is dan en slechts dan niet strijdig (= oplosbaar) indien b E A(!Rn). (b) Het stelsel (2) is dan en slechts dan oplosbaar indien rang A=
rang[A,~].
(c) Als Aa = b dan is het stelsel (2) oplosbaar en de algemene oplossing is x= a+
N(A).
(M.a.w.~+
N(A) is de verzameling van alle oplossingen.)
(d) Als (2) oplosbaar is, is de dimensie van de oplossingsvariëteit (gelijk aan dim N(A)) gelijk aan: n- rang A. (e) Als
[A,IJ
de normaalvorm is van [A,b] dan hebben Ax = b en Ax = b de-
zelfde oplossingen. (f) Als n = m en A is één-éénduidig (d.w.z. N(A) = {Q}) dan is Ax = b één1 duidig oplosbaar met oplossing x = A- b. 3.2.2. Uit bewering (e) volgt tevens een methode om het stelsel (2) op te lossen. !.
[A,~]
Breng (i)
kr = n + 1 en rang [A,b] > rang A en het stelsel is strijdig.
(ii) k 2.
op normaalvorm. Er zijn nu twee mogelijkheden:
r
~
n en rang [A,b] = rang A; het stelsel is oplosbaar.
Laat het stelsel oplosbaar zijn en grote matrix, dan is
[À,fJ
de normaalvorm zijn van de
- 70 -
~I b2
b =
b
r
0
0
Is nu r = n dan is het stelsel éénduidig oplosbaar, is r < n dan is er een (n - r) dimensionale oplossingsvariëteit. Op grond van (c) is het voldoende één oplossing aan te geven en verder N(A) volgens
§
3.1. te
bepalen (dit is, als A bekend is, niet veel werk meer). Een oplossing is:
~
I
=bi' ~
2
= b2'
... '
~
= b r
r
en de eventuele ove-
rige x-en zijn gelijk aan 0. 3. 2. 3. Voorbeelden I.
I
x2 +
x3 = 10
x3 = 8 + 2x = 6 3
x\ + x2 + XI
[A,!:_]
=
[A,!:_] =
Oplossing: x 1
r: r:
0
2
0
0 0
0
·:] -:1
(zie 2.6.5 II)
= -2, x 2 = 6, x 3 = 4 of x = [-2,6,4].
.
- 71 -
\ ,,
2.
+ 2x
+ 3x
-
x4 = 2x + 3x - 2x + 3x = 1 2 3 4 4x + 7x + 4x + x4 = 2 1 2 3
[A,~] =
cA..IJ
3.
~
- [:
c'A,~J
rang
2
> rang
3
2
3
-I
3
-2
3
7
4
0
-13
9
8
-:5
0
0
0
A.
;]
:J
.
Het stelsel is strijdig; er zijn geen oplossingen.
-
+ 2x
x4 = 2 + 3x 3 + 3x - 2x + 3x = 2 3 4 + 7x + 4x + x4 = 3 2 3
[A,~] =
cA.,:fJ
rang
c'A,:fJ
=
•
~ ~
2
3
-I
3
-2
3
7
4
0
-13
9
8
-5
0
0
0
;]
-;] .
-
rang A = 2. Dimensie oplossingsvariëteit: 4 - 2 = 2. Een oplossing: x = -1' x = 1, x = x = 0. 1 2 3 4 Algemene oplossing: =
x = [-1,1,0,0] + À[J3,-8,1,0] +
~[-9,5,0,1]
- 72 -
§
3.3. Positieve oplossingen van stelsels lineaire vergelijkingen
3.3.1. In veel van de toepassingen van stelsels lineaire vergelijkingen, ~
d.w.z. van
=
~.
ging het er niet slechts om een oplossing te vinden, maar
om een oplossing te vinden die bovendien voldoet
aan~~
Q,
~
#
Q·
Zie bijv.
1.2.2, 1.2.3. We zullen ons met dit soort oplossingen gaan bezighouden.
Als voorbereiding bestuderen we convexe verzamelingen in Rn. ~
Afspraak. Een vector x
Q,
~
Q noemen
#
we positief.
"efinitie. Een vector x e IRn heet een convexe combinatie van x_ en z indien er een getal À bestaat met 0 ~
= ÀY._ + (I -
~À~
I, zó dat:
À)~
De verzameling van alle convexe combinaties van x_ en z noemen we het segment tussen "i.. en !:
3.3.2. Definitie. Een deelverzameling U van Rn heet convex indien voor elke
x_ e U en elke z e U en elke À e [O,I] geldt: ÀY._ + (I -
À)~ e U
3.3.3. Voorbeelden van convexe verzamelingen I.
In R2 is de cirkelschijf x~+ x~~ I convex.
2.
Het binnengebied van een driehoek in R2 , van een viervlak in R 3 , ••• ,is convex.
3.
In Rn is {x
4.
Zij ~
E
x
~
O} convex.
Rn, r e R; de verzamelingen {~
I
(~,~) > r} en {~
I
(~,~) ~ r}
zijn convexe verzamelingen (geheten open en gesloten halfruimten). 3.3.4. Definitie. Laat ~~·~z·····~n e Rn; ~heet een convexe combinatie van ~~·····~n indien~= Àl~l + À 2 ~
en Àl + ÀZ + ••. + Àn =I.
2
+ ••• + Àn!n met Àl ~ 0, Àz ~ 0, •.• , Àn ~ 0
- 73 -
Eigenschappen:
u1
I. Als
en UZ convex zijn, dan is
u1 n
UZ convex.
De doorsnede van een willekeurige collectie convexe verzamelingen is convex~
Z. Iedere lineaire variëteit (in het bijzonder iedere deelruimtel is convex.
3. Als U convex is en als binatie van
1
~ ,
~I
EU, ..• ,~ EU, dan ligt ook elke convexe com-
••• ,~ in U.
Bewijs. Voor k = Z is dit de definitie van convexe verzameling. Laat bewezen zijn dat iedere convexe combinatie van een (k- !)-tal elementen uit
U in U ligt. Zij~= Àl~l + .•• + Àk~' Ài ~ 0, IÀi = I; als Àl = I zijn de overige Àz, ... ,Àk gelijk 0 en is x EU, anders is x
z
daar
U krachtens aanname, is x
E
E
U, q.e.d.
4. Een convexe combinatie van convexe combinaties van x , ... 1 convexe combinatie van XI, ••• ·~·
,~
is zelf een
5. Bij iedere verzameling V is er een kleinste convexe verzameling die V bevat; dit is de doorsnede van alle convexe verzamelingen die V bevatten.
Notatie: C(V); naam: convexe omhulsel van V.
1
6. Als V= {~ , ..• ,~k}' dan is
C({:'! 1 , ••• ,:'!kl) heet het convexe polytoop opgespannen door :'!t•···•:'!k· 7. Als~
C({!! 1 , ••• ,!!k}) dan is C({!>•!'!t''"'~k}) = C({~ 1 , ... ,~k}).
E
8. Er bestaat een eenduidig bepaalde verzameling {~ , ••• ,~ } c {!! , ••• ,!!kl 2 1 1
zó dat: i i) Geen der b. is gelegen in het convexe polytoop opgespannen door de -L
overige
.!::' s.
Bewijs. Probeer !! ,. ··•:'!k achtereenvolgens weg te laten. 1
De b. heten de hoekpunten van het polytoop. -1
9. {~
I
~
"
0, x 1 + •.. + xn
I} is een convex polytoop met als hoekpunten
~ 1 ' • • • '~n ·
3.3.5. Definitie. Zij U een convexe verzameling. Een vector x
E
U heet een
extreem elem~nt van U als uit x= À~+ (I - À)~,~ EU, z EU,~ f ~· volgt À
=
I en x
~
of
À
0 en x = z.
- 74 -
We kunnen het ook zo formuleren: x is extreem element als uit x= ~y + (I-~)~, zE U, zE U, 0 < ~ < I, volgt:
~
=
z = ~;
of
x is extreem element als x niet tussenpunt is van een segment in U, of als x geen convexe combinatie is van twee andere elementen van U. Voorbeelden I.
Open en gesloten halfruimten hebben geen extreme elementen.
2.
De hoekpunten van een convex polytoop zijn extreme elementen.
3.3.6. Stelling. De positieve oplossingen van Ax = b vormen een convexe verzameling. Bewijs. De verzameling van positieve oplossingen kan leeg zijn. De lege verzameling is convex. Zijnzen is ook ÀZ + (I Voorbeeld.
À)~
~positieve
oplossingen en is 0 s
À
s I, dan
een positieve oplossing.
een idee te krijgen van wat verzamelingen positieve oplossingen kunnen zijn, schetsen we de positieve oplossingen van x+z=l Om
a
'
''
•
y
y
'
b
[O,b]
[a,O] ------------f-----~~,~--x
''
-------------+----~----~x / /
/
'
/
/ /
/ / /
a > 0, b > 0
a > 0, b < 0 y
''
'
''
''
'
' '
x
'
'
'' ' ' a <
o,
b < 0
''
- 75 We zien dat er twee, een, geen extreme elementen zijn.
In het geval dat de verzameling oplossingen begrensd is, is deze gelijk aan het convexe polytoop opgespannen door de extreme elementen. (We spreken van extreme oplossingen.) Laat de kolomvectoren van A zijn: êl•êz····•ên; d.w.z.
a . mJ
Ax =bis nu te schrijven als x ~
1 1 + .•• + xnên = b.
Zij~=
3.3.7. Stelling.
[x ,x , ... ,xp,O,O, ... ,O] met x 1
2
1
> 0,
x
2
> 0,
... ,
x
> 0 een positieve oplossing van ~ = ~· Nu is ~ een extreme oplossing p dan en slechts dan als a , ••• ,a een onafhankelijk stelsel is. -1 -p
Bewijs
(i)
Stel ~ , ••• ,~p onafhankelijk en stel~= ÀO~ + (l - À 0 )~ voor zekere ÀO
1
met 0
Uit
ÀO
<
<
Ào~ +
I en positieve oplossingen
(I -
0 )vk
À
= ...
We hebben dus: up+l xl~l
+
uk
~
= u
0
0, vk =
~
O, vp+I
en
~·
0, volgt
=
~ =
0, vk
= Vn = 0.
=
0.
Nu is
+ x a = b p-p + u a = b p-p + v a = b p-p
Ulêl + Vlêl + Omdat
= 0,
~
~ , •••
1
,ëp onafhankelijk is, volgt
hieruit~=~=~·
(i i) Stel dat het stelsel a , ••• ,a
-1 -p niet onafhankelijk is; er zijn nu getal+ y p-p a = 0. len y , ••• ,yp niet alle gelijk aan nul, zó dat y 1 ~ 1 + 1 Beschouw~:= [y 1 ,y , ••• ,yp,O,O, •.• ,OJ E Rn, dan is~# 0 (n.b. ~kan 2
negatieve componenten hebben!).
Z ~J· ~
m . Nu Z~Jn • . ~ := ~ + €l, en v := x - ez. twee verschil= 12 M lende positieve oplossingen en x = !~ + !~, dus x is geen extreme op-
M > 0•
€
lossing, q.e.d. 3.3.8. Stelling. Zij~= [x 1 , ••. ,xn] een positieve oplossing van~=~· Nu is ~ een extreme oplossing dan en slechts dan indien het stelsel van de kolomvectoren van A met rangnummers i, waarvoor xi # 0 is, een onafhankelijk stelsel is.
- 76 -
Bewijs. Pas 3.3.7 toe, eventueel na hernummering van de onbekenden. 3.3.9. Stelling. Ax
=b
heeft hoogstens eindig veel extreme positieve oplos-
singen. Bewijs.
1 •••• ~n} heeft eindig veel deelverzamelingen; alleen die deelver-
{~ ,
zamelingen die een onafhankelijk stelsel vormen hebben kans met een extreme oplossing verbonden te zijn. Stelling 3.3.8 geeft ons tevens een mogelijkheid de extreme oplossingen te bepalen. We gaan daarbij als volgt te werk: Bepaal een onafhankelijk stelsel kolomvectoren van A, bijv. Probeer op te lossen:
x ~
+ x ~
1 1
3 3 = a 1,
+ x ~
8 8 = ~;
+ x ~
7 7 = a3 , x 7 3
3 7 8
~~·~ .~ .~ •
er is ten hoogste één
= a , x = a • Beschouw nu 1 8 8 7 [a ,o,a ,o,o,o,a 7 ,a8 ,o, ... ,OJ; als deze vector positief is, is het een ex1 3 treme oplossing.
oplossing. Laat deze zijn x
x
He kunnen ons bij het zoeken naar extreme oplossingen beperken tot lineair onafhankelijke kolomstelsels van maximale omvang. Immers is rang A = r, en, bijvoorbeeld
~~·~
2 , •.. ,~r een onafhankelijk stelsel kolommen, terwijl er een
extreme positieve oplossing bestaat (x ,x , ... ,xp,O, ... ,O), met x 1 1 2 x ' 0 t._'ll 11 < r, dan hL"Cft het stelsel I'
>
0,
'
Yl"l + •.• + y r-r a -
=b
als enige oplossing:
Omdat elk stelsel van p onafhankelijke kolommen met p
<
r
= rang
A uit te
breiden is tot een stelsel van r onafhankelijke kolommen vinden we derhalve alle extreme oplossingen door het zojuist beschreven zoekproces uit te voeren voor alle onafhankelijke r tallen van kolommen.
- 77 -
Belangrijk zijn gevallen waarin de verzameling van de positieve oplossingen begrensd is. Een voldoende (maar niet nodige!) voorwaarde hiervoor is: m
I
m
a .. > 0
lJ
i=!
(j = I , ... , n)
I
en
i= I
b. ;:, 0 1
(ga na!). Als de verzameling van positieve oplossingen begrensd is gelden fraaie stellingen.
----3-:J~io. Stelli;g~L~·,;z·d~-._-;~;ling van positieve oplossingen van
Ax
·,;b
begrensd zijn; laat ~O zo'n positieve oplossing zijn en laat~ E N(A) zijn, dan vormen alle positieve oplossingen van de vorm ~O + ta met t E IR een segment in IRn. Bewijs. Triviaal. We komen nu tot de hoofdstelling van deze paragraaf. 3.3.!!. Stelling, Laat de verzameling V van de positieve oplossingen van Ax
=b
niet leeg en begrensd zijn, dan bestaat V uit alle convexe combina-
ties van de extreme oplossingen, m.a.w. V is het convexe polytoop met de extreme oplossingen als hoekpunten. Bewijs. We geven een bewijs uit het ongerijmde. Stel dat er een positieve oplossing
~
~
is die geen convexe combinatie van extreme oplossingen is;
is
dan zelf zeker geen extreme oplossing. Er zijn dan twee verschillende positieve oplossingen u en v en een Alle vectoren van de vorm singen van
~ = ~-
t~
met 0 <
À
+ (I - t)~
À < l
=v
zo
dat z =
À~+
À)~.
(I -
+ t(~- ~) met t E IR zijn oplos-
Wegens stelling 3.3.10 vormen de positieve oplossingen
van deze vorm een segment S in IR0
•
Laat u * en v * de eindpunten van S zijn;
convexe combinaties van u* en~* , terwijl dan zijn u en ~' en dus ook ~· * Als u * en v * nu be1'd e convexe combinaties van ex~* I "!..._* , u* r.J.. ~'* v *
"~-
treme oplossingen zouden zijn, dan zou hetzelfde gelden voor
. u * of v * , zeg maar van belde oplossingen. Laat er in
~
~·
Minstens een
*, 1s . dus geen convexe combinatie van extreme
~
p coördinaten gelijk aan 0 zijn, dan zijn ook in
. u* u * en v * de overeenkomende coördinaten 0. We zullen laten zien dat er 1n tenminste p + I coÖrdinaten 0 zijn. Als dit nl. niet zo was, dan konden we als in het bewijs van 3.3.7 een getal
*
en~
-
* -
s(~
*
~)
E
. v1nden . zo kle1n dat u * +
*
E: (~
-
u*)
. positieve oplossingen zijn, in tegenspraak met het be1de
feit dat u* een eindpunt is van het segment van positieve oplossingen van de vorm u* +
*
t(~
*
-~);dit
segment is immers hetzelfde als S.
- 78 -
Het aantal coÖrdinaten gelijk 0 in u* is dus~ p +I. Herinneren we ons dat
*
~
van
geen convexe combinatie van extreme oplossingen is. We laten nu u* de rol ~
spelen en herhalen het bovenstaande betoog. We vinden dan een positie-
ve oplossing die geen convexe combinatie van extreme oplossingen is met tenminste p + 2 coördinaten gelijk aan nul. We herhalen het argument; zodoende vinden we positieve oplossingen die geen convexe combinatie van extreme oplossingen zijn, met steeds meer nullen. Op een gegeven moment (ga na!) zijn er nog zo weinig positieve coÖrdinaten over, dat de overeenkomstige kolomvectoren van A onafhankelijk zijn en de vector zelf een extreme oplossing is. Tegenspraak. q.e.d. 3.3.12. Voorbeelden I.
Bepaal alle positieve oplossingen van: -I 2
Er kunnen geen onbegrensde positieve oplossingen zijn; immers elke oplossing moet ook voldoen aan: 3x
+ x = I. Voor we de extreme op1 + x2 3 lossingen zoeken gaan we over op de normaal vorm.
Zij [A,È_] =
G
-I
3
2
-2
-~J
(verwisseling der vergelijkingen!), dan is 0
-2 De oplossing van Ax =bis dus:~=
[i,- i, O]
+ À[-1,2,1]. Er is dus
(3.3.10) een segment van positieve oplossingen, derhalve twee extreme oplossingen. Om deze te vinden kunnen we twee wegen bewandelen:
5 0 en - - + 2À 4 5 (minstens eenmaal moet er echt groter komen); dus 8
3 (a) Oplossingen zijn positief als 7i - À
~
~
,;
0 en À ~ 0 À ,; 3 De ex-
4"
I 3 3 I 5 treme oplossingen zijn (À = 8): [8 ,0, '5] S" en (À = 4): [0, 7i '4].
- 79 -
Alle positieve oplossingen zijn:
~
=
t[~
,0,
~]
+ (I .., t)[O,
~
•fJ
(0 ;; t ;; I) •
(b) Beschouw alle lineair onafhankelijke tweet"llcn uit
en probeer voor elk van deze deelstelsels een oplossing te vinden die alleen voor de componenten overeenkomend met de vectoren uit het stelsel ongelijk nul is. Onafhankelijk deelstelsel
op te lossen vergelijkingen
XI
[~]
oplossing [x I ,x2 ,x3]
•,[:]- [_ tl
+
r: l., -
x3
2x
3
x3 = 0
= 43
5
[4 ' - 4
,O]
niet positief
~] 8 ' ' 8
[.!_ 0
5 3 = -4
extreme oplossing!
x2 = 0
x3
[~] '[j
3
=4
2x 3 =
5
4 extreme oplossing!
XI = 0
2.
xl - x {x
2
- x
3
3
= I
=I
De algemene oplossing
is~=
[1,1,0] + À[l,l,l].
We zien dat de verzameling positieve oplossingen onbegrensd is. Iedere oplossing is positief waarvoor
À 2
0 is. Er is één extreme oplossing,
nl. [1,1,0]. We zullen nog eens direct laten zien dat [1,1,0] een extreem element is van de verzameling {[l+a,l+a,a]
a 2 O}. Zij nl.
[1,1,0] = À[l+a,l+a,a] + ( I - i..)[I+S,I+S,SJ
- 80 -
met 0
I, dan volgt:
<À<
(l+a)À + (1+13) (1-À) = { en dus
aÀ <XÀ
=0
+ (I-À)I3
= 0
en (I - À)l3
= 0;
a = 0, 13
= o.
De enige extreme oplossing van 2 is ook te vinden op de manier van 3.3.9. IA,~]= ~lot ~I
0
:]
-1 -I
~2
~3
b
Merk op dat rang A = 2 Onafhankelijk t«eetallen
op te lossen vergelijkingen
oplossingen
XI = I ' x2 = I ' x3 = 0
[1,1,0], extreem
-
r~ - x3
x3 = I ' x2 = 0
x3
{ x 2-
=x3
[0,0,-1], niet positief
=
= I' =
XI = 0
[0,0,-1], niet positief
3.
2
Merk op dat niet geldt:
I
a .• > 0 1]
i= I
(j
= 1,2,3).
Toch is de verzameling
positieve oplossingen begrensd, want een positieve oplossing moet ook 3 voldoen aan (z x de eerste vergelijking+ I x de tweede):
We zoeken nu de extreme oplossingen zonder eerst op normaalvorm over te gaan: a
-I
=
[:] '
a = -2
[-~]
'
!!3 =
[_:] '
b =
[~]
.
Wederom is rang A = 2 Onafhankelijke tweetallen
vergelijkingen
oplossing
-
On;~
fh;mkc• lij kc twL•c.tallL"n
0 I
--
VL'rge l. ijkingen
!!: I '!!:2
!!J ·!!3
-
oplossi.ng
r~XI
x2 = 2, x3 = 0 + 2x = 2 2
oplossing,
r~XI
+ x3 = 2, x2 = 0
[2,0,0]
!!2'!!;3 {
-2:~
[2,0,0] extreme
x3 = 2 + x3 = 2, XI = 0
[0,4,6], extreme
- x3 = 2
oplossing
Alle positieve oplossingen: x = À[2,0,0] + (1-À)[0,4,6] = [2À,4-4À,6-6À]
§
(0 ,;
À ,;
I) .
3.4. Lineaire ongelijkheden
3.4.1. We beschouwen stelsels ongelijkheden van de vorm +ax
:S:;a
+bx
«8
n n n n
+ ••• + f x
n n
" n •
Door vermenigvuldiging van sommige ongelijkheden met -1 kan elk stelsel geschreven worden in de vorm Ax ,; b
(I)
Laat de rijvectoren van A zijn: y 1 := Ca 11 , ... ,a 1nJ, ... , dan is het stelsel Ax ,; b ook te schrijven als:
Ym
:= [aml, .. • ,amn];
(2) (v , x) ,; b -mm
3.4.2. Stelling. De verzameling V van de vectoren x
Ax
~
E
Rn die voldoen aan
b is convex.
Bewijs. In de schrijfwijze (2) is duidelijk dat V de doorsnede is van convexe halfruimten.
3.4.3. In een stelsel als (2) kunnen overtollige ongelijkheden voorkomen; deze kan men weglaten zonder dat de oplossingsverzameling verandert.
-
Voorbeeld -2x
-
I - XI +
x2 s 4 x2 s 2
- XI - 2x 2
$
0
xz
<;
2
XI +
82 -
xz
2
. 2 Elk van deze ongelijkheden bepaalt een halfvlak 1n ffi , We tekenen de begren-
zende lijnen van deze halfvlakken.
We zien dat de eerste en laatste ongelijkheid overbodig zijn en dat de oplos4 2 sing het convexe polytoop is met hoekpunten [0,2], [4,-2] en [- 3•3]. 3.4.4. Ook voor een stelsel
ongelijkheden~
s
~geldt
dat de oplossingsver-
zameling, indien begrensd, een convex polytoop is met extreme elementen als hoekpunten (zie ook 3.5.2).
- 83 -
§
3.5. Iets over lineaire programmering
].5.1. W(' hebhen
gL'Zit'll
h\J.t vinden is v.:m
Cl'll
in l.:!~B d;1t t'L~Il typisch I ilJc.t:Jir p!"n)'.l"Jillllll'I"ÎII)',~;prt,hlt•t'lll
x die voldoet aan:
x " 0
(*)
of
A'x s: b'
waarvoor een lineaire vorm (~.~) minimaal of maximaal is. Korter geformuleerd luidt het probleem: vind onder de positieve oplossingen van een stelsel lineaire ongelijkheden er een waarvoor een lineaire functionaal maximaal of minimaal is. In 3.4.2 hebben we gezien dat de oplossingen van (*) een (eventueel lege) convexe verzameling vormen. Het gaat dus om het probleem extreme waarden te vinden van een lineaire functionaal op een convexe verzameling.
1. 5. 2. Loze vcrander U jken
Ooor een eenvoudige kunstgreep is het mogelijk het stelsel lineaire ongelijkheden te vervangen door gelijkheden zodat we in de situatie van
§
3.3
terechtkomen. Laat het stelsel zijn: a 11 X I + " ' + alnxn,;; hl (I)
Aan de x , ... ,x voegen we nu toe m nieuwe veranderlijken y 1 , ... ,ym' de zgn. 1 0
loze veranderlijken. We proberen op te lossen: + al I xl + •.. + alnxn = hl
yl + Y2 (2)
l
..,
+ a21 XI + ••• + a2nxn ~
Ym + amlxl + ••• + a mn xn
~2 • b
yl <: 0' ... ,y m <: O,x 1 <: 0, . .. 'xn <: 0
m
.
Als [0 , .. , ,Bm'''l' ... '"n] een oplossing van (2) is, is [a. 1 , ... ,a.n] een op1 lossing van (1), de afgesneden oplossing. Omgekeerd 1s x=~ een oplossing van (1), dan vindt men een oplossing [B 1 , ••• ,Bm,a 1 , ••. ,un] van (2) door te stellen
s. = b.1 ~
- (a. a + .•. +a. u) 1 1 1 tn n
(i = I , ... ,m) •
- 84 -
N.B. Met een oplossing#
#
Q van
(2) correspondeert niet steeds een oplossing
0 van(!). Voorbeeld: [b , ... ,bm,O, ... ,O], 1
Eigenschap. Als we een extreme oplossing van (I) uitbreiden tot een oplossing van (2), dan is dit een extreme oplossing. (Bewijs dit!)
Als wij dus
alle extreme oplossingen van (2) kennen, dan komen alle extreme oplossingen van (I) voor onder de afgesneden oplossingen. 3.5.3. Voorbeeld. Beschouw
(*)
- x + y
,;
4x - y
,;
-
2x - y
,;
-
x
;,
;,
0
0, y
12 2
(Telt men 2x de eerste ongelijkheid op bij de tweede, dan komt er 2x + y s 14 waaruit volgt dat de verzameling oplossingen begrensd is.) We hebben nu twee methad ter beschikking voor de bepaling van de hoekpunten van het convexe pol ytoop ( *) : (a) grafisch, (b) door toevoeging van loze veranderlijken en de techniek van
§
3.3.
(Voor het resultaat zie verderop.) We formuleren nu de hoofdstelling van deze paragraaf. 3.5.4. Stelling. Zij C een convex polytoop in Rn met hoekpunten ~ 1 , •••• ~k' dan neemt de lineaire vorm
(~,~)
op C een minimum en een maximum aan.
Het minimum wordt aangenomen in een hoekpunt (maar mogelijk ook elders); hetzelfde geldt voor het maximum. Bewijs. We spreken slechts over een minimum; voor het maximum is het bewijs analoog. Zoek het kleinste onderdek getallen en laat
(~'~i)
= m. Het is mogelijk dat m
i. Voor een willekeurige x=
Àl~l
+
=
1
(~.~ ),
(~.~i)
•••
,(~.~k).
Zij dit m
voor meerdere waarden van
+ Àk~ (Ài;, 0, E Ài = I) uit C
geldt nu
q.e.d.
- 85 -
3.5.5. Stelling. Als de verzameling V van de positieve oplossingen van ~
=~
(of ~ s È) begrensd is wordt het minimum (of maximum) van (R,~) aan-
genomen in een extreme oplossing. Bewijs. 3.5.4 en 3.3.11 (3.4.4). Opmerking. Als de verzameling oplossingen niet begrensd is hoeft een maximum of minimum van
(E,~)
niet te bestaan. We beschouwen dit geval niet verder.
In het geval dat de verzameling positieve oplossingen van is, biedt de techniek van (E,~)
§
~
=~
begrensd
3.3 dus de mogelijkheid een x te vinden waarvoor
minimaal is.
Opmerking. l1en ziet gemakkelijk dat alle x waar het minimum wordt aangenomen het convexe polytoop is opgespannen door die extreme oplossingen waarvoor de waarde van
(E,~)
gelijk aan het minimum 1s.
In het wiskundige vakgebied der operations research is een belangrijk deel gewijd aan het vinden van goede algoritmen voor het oplossen van lineaire programmeringsproblemen. De op
§
3.3 berustende werkwijze is in de praktijk
vaak omslachtig. 3.5.6, We laten nog aan een voorbeeld zien hoe lineaire programmeringspro-
blemen in twee veranderlijken grafisch opgelost kunnen worden. Bepaal het minimum van x+ y = {Ct,l],~)
= f(~)
op de oplossingsverzameling
van voorbeeld 3.5.3. De oplossingsverzameling heeft vier extreme elementen:
C1 ,oJ, C3,oJ, c; De waarde van
f(~)
3
6 , ; J, ei, tJ
29 · 1, 3 , 3 in d eze h oek punten 1s
[J,O]. Dit blijkt ook uit de hoogtekaart.
, 34 .
· He t m1'n1'mum l.S
in
- 86 -
16] [.!2 3 •r
f(~) =
3
4
5
6
29
3
- 87 -
APPENDIX
DETERMINANTEN
Wc zullen in deze appendix summier kennismaken met een rekentechniek die in oudere verhandelingen over lineaire algebra een grote rol speelt, maar door ons niet gebruikt is, De determinant van een vierkante matrix A is een getal, det A, dat we aangeven door het blok getallen tussen rechte strepen te zetten. De definitie van de determinant geven we recursief naar het aantal rijen en kolommen. (i)
Als A = [a] 1s det A = a.
(ii) Stel dat we voor elke
n x n
matrix een determinant hebben berekend,
dan definiëren we: a
I ,n+ I
:=
a
a
n+ I, I
n+l,n+l
waarin D. . de determinant is van de n x n matrix die uit A ontstaat 1,J door de i-de rij en j-de kolom weg te laten. Enkele gevolgen: (a)
(b)
all
a12
a21
a22
all
al2
al3
a21
a22
a23
a31
a32
a33
=
alla22 - a12a21
.
=
De determinant heeft allerlei mooie eigenschappen, waarvan we enkele zonder bewijs vermelden.
- 88 -
I.
det A = (-1)
i+l
(aiiDil - ai2Di2 +
...
+ (-l)n-1 a. D. )
...
+ (-I)n-1 a .D . ) nJ nJ
1.n 1n
(ontwikkeling naar een rij). 2.
det A= (-1)
j+l
(a 1jDij - azlzj +
(ontwikkeling naar een kolom). 3.
det AB = det A det B.
4.
det A = det A ; det A = - det B als B uit A ontstaat door verwisseling
T
van twee rijen of kolommen. 5.
det A = det B als B uit A ontstaat door de i-de rij (of kolom) te vervangen door de som van de i-de rij (kolom) en p maal de j-de rij (kolom) (i
6.
# j).
det A I 0 dan en slechts dan als rang A
= n,
dus als de kolommen van A,
zowel als de rijen een basis van Rn vormen. We vermelden slechts een toepassing van determinanten. Deze heeft betrekking op een (de enige?) situatie waar het gebruik van determinanten duidelijk handiger is dan de rekentechniek die wij gebruikt hebben (2.6.11). Stelling. Een getal
À
is een eigenwaarde van A indien
det(A - H) = 0 De vergelijking in lijking van A.
À
(*)
(van den-de graad!) (*)heet de karakteristieke verge-
