Lineær algebra er en betegnelse for en
samling af matematiske emner, der alle
er relateret til løsninger af lineære
ligningssystemer. Lineære ligningssystemer
udgør dermed grundstenen i
lineær algebra, og det er derfor afgørende
at have en detaljeret viden
om løsningerne hertil. Som udgangspunkt er vi
hovedsagelig interesseret i lineære ligningssystemer
over de reelle eller de komplekse tal, men da teorien
viser sig at give mening og have anvendelser
for andre typer af tal, også kaldet legemer (se Appendiks A), så vælger vi at behandle
lineære ligningssystemer over et generelt legeme
. Hermed betegner en mængde, hvorpå der er
defineret addition og multiplikation,
så de egenskaber, som vi er vant til fra
de reelle tal, er opfyldt. Specielt giver det mening
at dividere med elementer forskellig fra .I det følgende vil vi anvende notationen indført
i Appendiks A. Læseren der alene ønsker at fokusere på det reelle eller det komplekse tilfælde, kan i det følgende (og i Appendiks A) erstatte notationen med hhv. eller .
1.1 Lineære ligninger
Med en lineær ligning i ordnede
ubekendte menes der en ligning af formen
hvor og er på forhånd valgte elementer i
. At de ubekendte er ordnede betyder blot, at vi på forhånd har
fastlagt en rækkefølge af dem. I dette tilfælde er rækkefølgen
understøttet af den valgte notation; dvs. er den første
ubekendte, er den anden ubekendte etc. I det følgende vil
ubekendte altid være antaget ordnet på denne vis, og vi vil derfor
alene omtale som værende ubekendte. Elementerne
kaldes for den
lineære lignings koefficienter.
Med en løsning til menes der en ordnet samling af skalarer
, der opfylder relationen
i . Sædvanligvis samler man skalarerne
i en vektor
og omtaler herefter denne vektor som en løsning til . Delmængden
af bestående af alle løsninger til kaldes for den lineære
lignings løsningsmængde.
1.2 Lineære ligningssystemer
Med et lineært ligningssystem
bestående af ligninger i ubekendte , menes
der en ordnet samling af lineære ligninger
i ubekendte. I det følgende vil vi også anvende notationen
om ovenstående lineære ligningssystem.
Skalarerne , for , kaldes for ligningssystemets koefficienter. Hvis
for alle , så kaldes ligningssystemet
homogent.
Et element i kaldes en løsning til (1.2), hvis er
en løsning til hver af de lineære ligninger . Delmængden af bestående af alle løsninger til
(1.2) kaldes for
løsningsmængden til (1.2).Opgaven består nu i at besvare spørgsmål af følgende type:
Hvordan bestemmer og beskriver man løsningsmængden til
(1.2)?
Hvor stor er løsningsmængden til (1.2); er den tom, er
den endelig eller er den uendelig stor?
Hvis løsningsmængden er en endelig mængde, hvor mange
løsninger er der så?
Hvis løsningsmængden er tom kaldes ligningssystemet for
inkonsistent; i
modsat fald kaldes systemet konsistent. Det er et
ikke-trivielt udsagn, at et lineært ligningssystem aldrig kan have
præcis løsninger. Tilsvarende er præcis , , , ,
og løsninger udelukket. Alle andre (positive) tal under
kan optræde som antallet af løsninger til et lineært
ligningssystem; dog aldrig når er eller hvor der
altid er præcis løsning, hvis antallet af løsninger er endeligt
(og ikke nul). Følgende eksempel illustrerer, hvad vi kan forvente i
det simpleste tilfælde.
Betragt et lineært ligningssystem
bestående af en enkelt ligning i en enkelt ubekendt . Løsningerne
hertil er givet ved:
Hvis , så er der præcis en løsning; nemlig .
Hvis og , så er løsningsmængden lig .
Hvis og , så er løsningsmængden tom.
1.3 Elementære operationer
Vi vil nu fokusere på konkrete metoder til bestemmelse af
løsningsmængden til et generelt lineært ligningssystem
(1.2). I første omgang ønsker vi at sammenligne med
løsningsmængder for andre lineære
ligningssystemer. Betragt, i den forbindelse, et lineært
ligningssystem givet ved
og betegn løsningsmængden for dette system med . Vi er
interesseret i at undersøge, hvornår og er identiske, og
vi definerer:
[Ækvivalente ligningssystemer]
To lineære ligningssystemer, bestående af ligninger i
ubekendte, kaldes ækvivalente, såfremt
deres løsningsmængder er identiske.
Ækvivalente ligningssystemer fremkommer oftest ifm. anvendelse af de
såkaldte elementære operationer. Elementære operationer
anvendes på et lineært ligningssystem ,
og resulterer i et nyt ækvivalent lineært ligningssystem
. Der er tre typer af elementære operationer, der
hver især kun involverer en eller to af ligningssystemets lineære
ligninger. I første omgang indfører vi følgende operationer på mængden
af lineære ligninger:
Lad
betegne en lineær ligning i ubekendte. For en skalar defineres som den lineære ligning
Givet endnu en lineær ligning
i de samme ubekendte, så defineres som den lineære ligning
Den præcise definition af elementære operationer er da:
[Elementære operationer]
En elementær operation på et
lineært ligningssystem er en af følgende tre
typer af operationer ()
Det oplyses, at det lineære ligningssystem
givet ved
fremkommer fra det lineære ligningssystem :
via en enkelt elementær operation. Angiv hvilke type af
elementær operation, der kan være tale om.
Type I
Type II
Type III
Observer nu følgende vigtige pointe: hvis
fremkommer fra ved anvendelse af en elementær
operation, så fremkommer også fra ved anvendelse af en
elementær operation på . Antag f.eks., at vi har udført en
elementær operation af type (Ⅰ.) for at opnå
fra . Så er identisk med , på nær at der er byttet rundt på
ligning og ligning . Vi kan altså opnå fra ved at
ombytte ligning og ligning i ; det sidste svarer til at
udføre en elementær operation af type (Ⅰ.) på . Hvis
derimod fremkommer fra ved at gange den 'te ligning i
med , så skal man blot gange den
'te ligning i med for at komme tilbage til
. Endelig ses, at hvis fremkommer ved, at man erstatter den
'te ligning i med , så skal man blot
erstatte den 'te ligning i med for
at opnå . Med denne observation kan vi nu let bevise:
Hvis det lineære ligningssystem fremkommer
fra ved anvendelse af en successiv følge af
elementære operationer, så er ligningssystemerne og
ækvivalente.
Det er tilstrækkeligt at vise udsagnet i tilfældet, hvor
fremkommer fra ved anvendelse af en enkelt elementær
operation. Start med at bemærke, at en løsning til også vil være
en løsning til de lineære ligninger og . Specielt vil løsningsmængden for være en
delmængde af løsningsmængden for . Et symmetrisk
argument viser, at er en delmængde af , og vi konkluderer
derfor, at ligningssystemerne og er ækvivalente.
Det modsatte af udsagnet i Lemma 1.6 er ikke
nødvendigvis rigtig. Som eksempel herpå kan man betragte de lineære
ligninger
i to ubekendte og . De lineære ligningssystemer
og er da ækvivalente, idet
løsningsmængden i begge tilfælde er tom. Derimod kan man ikke opnå
ud fra via en successiv følge af elementære operationer
(hvorfor?).
1.4 Reducerede ligningssystemer
Vi skal nu beskrive en speciel type af lineære ligningssystemer,
kaldet reducerede, hvor de tilsvarende løsningsmængder kan bestemmes
via såkaldt baglæns substitution.
Reducerede systemer er karakteriseret ved placeringen af de såkaldte
ledende koefficienter. Vi siger, at
er den ledende koefficient for en lineær ligning
hvis og for . I givet fald siger vi, at
er den ledende ubekendte for . Dette
begreb kan selvfølgelig kun defineres, hvis ikke alle 'erne er lig
.
Angiv den ledende ubekendte for den lineære ligning
Såfremt er den ledende koefficient for (1.5), så
skriver vi også
At ikke indgår i notationen (1.6)
betyder dog ikke, at nu alene opfattes
som en ligning i de ubekendte . Ligning er stadig en
lineær ligning i alle ubekendte , og såfremt vi
ønsker at understrege dette, så anvender vi notationen
(1.5). F.eks. kunne vi vælge at skrive
for at understrege, at den betragtede ligning er en ligning i to
ubekendte og .
[Reducerede ligningssystemer]
Et lineært ligningssystem
kaldes reduceret,
hvis der findes en voksende følge af naturlige tal
opfyldende
er den ledende ubekendte for for .
For har ingen ledende koefficienter; dvs.
for .
Ovenstående definition inkluderer tilfældet , hvor alle
koefficienter er nul.
For et reduceret ligningssystem som ovenfor, der
omtales de ubekendte som ledende (til tider også
bundne) ubekendte. De resterende ubekendte kaldes frie ubekendte.
Angiv de frie ubekendte for det reducerede
lineære ligningssystem
Reducerede lineære ligningssystemer kan løses via en metode kaldet
baglæns substitution. For at
beskrive denne metode, så vil vi anvende notationen
indført i
Definition 1.10. Idet der er ledende
ubekendte, så må der være frie ubekendte.
De frie ubekendte betegnes med , for heltal
opfyldende, at
Baglæns substitution foregår nu på følgende vis: Såfremt
der eksisterer et med , så vil
ligning være givet ved
og den vil dermed ikke have løsninger. Løsningsmængden
til (1.7) er dermed tom, med mindre
for alle . Hvis derimod
for alle , så kan vi se bort fra ligningerne , for alle ,
idet de alle er trivielle; dvs. på formen
og dermed er opfyldt for alle konkrete værdier af de ubekendte. Vi
har dermed reduceret til tilfældet, hvor . Omskriv nu ligning til formen
og bemærk, at dette angiver værdien af , såfremt værdierne for
de efterfølgende ubekendte allerede er
fastlagt. Dette leder nu frem til følgende procedure til bestemmelse
af samtlige løsninger til det lineære ligningssystem: start med at
vælge vilkårlige værdier for
de frie ubekendte . Herefter bestemmer ligning værdien af
, og med denne værdi for så bestemmer ligning
nu værdien af . Derefter fastlægger
værdien af , etc.Vi konkluderer:
Løsningsmængden til det reducerede lineære ligningssystem
(1.7) kan beskrives ved:
Hvis for , så vil ethvert valg af skalarer
kunne entydigt
udvides til en løsning til
(1.7).
Hvis der eksisterer et med , så er
løsningsmængden til (1.7) den tomme mængde.
Såfremt der ikke er frie ubekendte (dvs. hvis
), så skal første udsagn ovenfor forstås,
som at ligningssystemet har en entydig løsning.Ovenstående sætning illustreres bedst via et eksempel:
Vi ønsker at bestemme løsningsmængden for det reducerede lineære
ligningssystem ()
og starter med at bemærke, at bestemmer placeringen af
de ledende koefficienter. Specielt er , og vi vil, ifølge
Proposition 1.12, have en (entydig) løsning for ethvert
valg af værdier og for hhv. og . Vi
anvender baglæns substitution for at opnå de tilsvarende værdier for
og . Først bestemmer værdien af
og herefter opnås værdien for via ligning :
Løsningsmængden til (1.9) består altså af mængden af
vektorer på formen
hvor og kan vælges frit blandt elementerne i
. Bemærk, at vi også kan omskrive (1.10) til
hvor de indgående vektorer er karakteriseret ved:
Vi introducerer nu begrebet fuldstændigt reduceret lineært ligningssystem,
der betegner et reduceret lineært ligningssystem af en speciel pæn form.
[Fuldstændigt reducerede lineære ligningssystemer]
Et reduceret lineært ligningssystem (1.7) kaldes fuldstændigt
reduceret, hvis der for
og gælder, at koefficienten
, til i , er lig
hvis og lig hvis .
Angiv værdierne for skalarerne og
så det lineære ligningssystem
er fuldstændigt reduceret.
Det bemærkes, at de bundne ubekendte
i et fuldstændigt reduceret lineært
ligningssystem kun optræder med
koefficient forskellig fra i
en enkelt af systemets ligninger.
Dermed kan værdierne af de bundne
ubekendte umiddelbart aflæses
ud fra værdierne af de frie ubekendte.
Mere præcist er den 'te ligning
i systemet ækvivalent med
Baglæns substitution er dermed simplere at udføre end for almindelige
reducerede ligningssystemer.
Ligningssystemet
fra Eksempel 1.13 er ikke fuldstændigt
reduceret. Multiplicerer man med , så opnår man
som heller ikke er fuldstændigt reduceret. Til gengæld kan man nu
trække fra og opnå et
ligningssystem
der er fuldstændigt reduceret og ækvivalent med
(1.12). I ovenstående proces er alle de indgående
ligningssystemer reducerede. Bemærk også, at og
umiddelbart bestemmer en løsning
ud fra værdierne af
og . Mere præcist giver at
mens bestemmer
hvilket er identisk med, hvad vi fandt i Eksempel 1.13.
1.5 Gauss elimination
I starten af 1800-tallet beskrev C.F. Gauss
banen for en asteroide ved navn Pallas. Beskrivelsen byggede på flere
års observationer og dertilhørende databehandling. En del af
databehandlingen bestod i at løse et lineært ligningssystem bestående
af seks ligninger i seks ubekendte, og i den forbindelse anvendte Gauss en
algoritme til løsning af lineære ligningssystemer, som vi nu skal
beskrive.
Gauss elimination er en algoritme til at omforme et generelt lineært
ligningssystem
til et reduceret lineært ligningssystem ved hjælp af elementære
operationer. Sammen med Lemma 1.6 og
Proposition 1.12 opnår man herved en metode til at løse
generelle lineære ligningssystemer.Den grundlæggende observation ifm. Gauss elimination er, at man via en følge af
elementære operationer på (1.15) kan opnå et nyt ligningssystem
på formen
dvs. et ligningssystem hvor alle koefficienter til er nul for
ligningerne . Dette kan f.eks. gøres på følgende vis:
Hvis der eksisterer et med , så udføres
følgende successive følge af elementære operationer på
(1.15):
Erstat ligning med , for .
Ombyt ligning med ligning (hvis så udelades dette).
Vi er nu parate til at beskrive algoritmen bag Gauss elimination. Algoritmen er rekursiv i antallet af ubekendte , så vi antager, at vi allerede har beskrevet, hvordan systemer med ubekendte kan bringes på reduceret form. Vi skal da beskrive,
hvordan et ligningssystem (1.15) med ubekendte kan bringes på reduceret form. Vi
starter med at bringe (1.15) på formen (1.16) som beskrevet ovenfor. Hvis ,
så har vi hermed opnået et reduceret system.
Hvis derimod , så opdeler vi i tilfældene
og . I tilfældet
hvor , der kan vi opfatte (1.16)
som et system i de ubekendte , og dette system kan bringes på
reduceret form via vores rekursive antagelse. Hvis
derimod , så er en ledende ubekendt for . Ligningssystemet kan vi samtidig opfatte
som et system i de ubekendte ,
og hvis vi bringer denne del på reduceret
form , så vil også være et reduceret ligningssystem.
Lad os beskrive løsningsmængden til det lineære ligningssystem ()
Vi starter med at anvende Gauss elimination for at opnå et
ækvivalent reduceret lineært ligningssystem. Først trækker vi den
øverste ligning fra den midterste, samt gange fra den nederste.
Herved opnås
Den beskrevne algoritme beder os herefter om at koncentrere os om de
nederste to ligninger, og om at opfatte disse som ligninger i de
ubekendte og . Herefter skal vi udføre elementære
operationer, så vi opnår en form lignende (1.16). Da det sidste
allerede er tilfældet, går vi videre til næste skridt i algoritmen.
Her bliver vi bedt om at opfatte de to nederste ligninger som
ligninger i de ubekendte og . Vi sørger herefter for, at
disse ligninger har formen præciseret ved (1.16). Dette opnås
ved at ombytte de to nederste ligninger. I alt har vi nu opnået
ligningssystemet
som er reduceret, og som derfor kan løses via baglæns
substitution. Vi kan anvende samme fremgangsmåde som i
Eksempel 1.13, og finder, at løsningsmængden består af
elementer på formen
hvor kan vælges frit blandt elementerne i .
Den opmærksomme læser har formentlig allerede observeret, at vi ifm. Gauss elimination alene har anvendt elementære
operationer af type (Ⅰ.) og
type (Ⅲ.).
Såfremt man også anvender
type (Ⅱ.) operationer, så kan det betragtede ligningssystem
bringes på fuldstændigt reduceret form via en algoritme kaldet
Gauss-Jordan elimination. Idet vi allerede har introduceret Gauss
elimination, så vil vi her alene beskrive, hvordan et reduceret lineært
ligningssystem kan bringes på fuldstændigt reduceret form.Så betragt et reduceret lineært ligningssystem
Vi anvender notation som i Definition 1.10, og kan da
betragte følgende successive operationer på (1.21). Vi
starter med at udføre de elementære operationer
For ganges ligning med
.
der bringer (1.21) på en form
hvor alle de ledende koefficenter er lig .
Herefter kan man udføre
For et givet erstattes
ligning med for .
på det lineære ligningssystem (1.22) og
opnå et fuldstændigt reduceret
ligningssystem. Det overlades til læseren at indse dette (se evt.
Eksempel 1.16 for et eksempel på denne metode).
1.6 Et vigtigt resultat
Det følgende resultat beskriver løsningsmængden
til et homogent lineært ligningssystem med flere
ubekendte end ligninger. Resultatet er yderst
vigtigt, og danner bl.a. grundlaget for basisbegrebet, som vi skal studere i Kapitel 7.
Et homogent lineært ligningssystem
med har en løsning forskellig fra .
Hvilke af nedenstående homogene ligningssystemer har en løsning forskellig fra
Ved anvendelse af Gauss elimination kan vi antage, at (1.23) er
et homogent reduceret lineært ligningssystem. Idet antallet af
ledende ubekendte er mindre end eller lig antallet af ligninger ,
så vil der eksistere mindst frie ubekendte. Samtidig
fortæller Proposition 1.12, at der vil eksistere
løsninger til ligningssystemet, der antager arbitrære værdier for de
frie ubekendte. Dermed eksisterer der nødvendigvis en løsning
forskellig fra .