Intro
De flesta av de problem vi stöter på i våra liv kan lösas på flera sätt. Därmed inte sagt att vi är lika nöjda med var och en av de olika lösningarna.
Optimering är en gren av matematiken som inte bara syftar till att lösa problem utan också att hitta den bästa möjliga lösningen, givet vissa begränsningar. Processen innefattar ofta att titta på lösningsrum för problemen.
Tekniken har tillämpningar inom ett brett spektrum av ämnen, från att bestämma hur man bäst planerar produktionen i en fabrik, till att effektivt hantera energinätssystem.
Koncept
För problem med flera lösningar talar vi ofta om deras lösningsmängd . Som namnet antyder är det helt enkelt den mängden värden som uppfyller problemets ekvationer eller ojämlikheter.
Ta som exempel ekvationen:
Lösningsmängden innehåller alla kombinationer av värden där .
Ett lösningsrum är en mängd lösningar, med vissa begränsningar
Eftersom denna mängd lösningar uppfyller följande kriterier:
är en lösning.
Summan av två valfria lösningar är också en lösning.
Att multiplicera en lösning med valfritt tal ger en lösning.
då kvalificerar även lösningsmängden som ett lösningsrum .
Summering
Att lösa homogena system av linjära ekvationer är en speciell typ av problem som vi kan skriva i formen:
Vi kan använda Gauss-Jordan-metoden för att hitta lösningen på ett sådant system. Om mängden vi hittar uppfyller de tidigare nämnda kraven är det ett lösningsrum.
Dessutom är lösningsrummet till ett homogent linjärt system ett delrum av .
Delrum
En samling vektorer som är slutet under addition respektive skalär multiplikation innebär att
om och finns i så finns i (slutet under addition)
om finns i så finns i för alla (slutet under skalär multiplikation)
de två ovan punkterna leder till att måste finnas i
Det leder oss till definitionen för delrum:
En icketom mängd av vektorer i kallas delrum till om det är slutet under addition och slutet under skalär multiplikation.
Notera att tack vare att ett delrum är slutet under addition och skalär multiplikation så är det även slutet under samtliga linjärkombinationer. I tillägg måste -vektoren tillhöra rummet för att vara ett delrum till . Lägg även märke till att oavsett dimension till så finns alltid två delrum som kallas för de triviala delrummen, nämligen och själv. Att delrummet uppfyller definitionen faller ofta naturligt, men att alltid är ett delrum visar vi nu:
(slutet under addition)
för alla (slutet under skalär multiplikation)
Som exempel tar vi ett plan i . Låt ekvationen respektive parameterformen vara
Då är ett delrum till eftersom att
Nollvektorn ligger i
om och finns i finns även i (slutet under addition)
om finns i finns även i för alla (slutet under skalär multiplikation)
Vi visar nu de ovan tre påståendena.
finns i eftersom att
Låt och finnas i . Det betyder att det finns skalärer , , och som uppfyller parameterformen. Då har vi att
vilket följer parameterformen för och därmed finns i .
Låt finnas i . Då finns skalärer och som uppfyller parameterformen. Då har vi att
vilket följer parameterformen för och därmed finns i .
Samtliga delrum i faller alla inom ett av tre kategorier:
Nollvektorns delrum
Linjer som går genom origo
Hela
Samtliga delrum i faller inom ett av fyra kategorier
Nollvektorns delrum
Linjer som går genom origo
Plan som går genom origo
Hela
Lägg därför märke till att alla linjer och plan som inte korsar origo inte är delrum, men de är ett translaterat delrum och brukar kallas för linjär mångfald. Låt vara ett sådant translaterat delrum medans är ett delrum i , då finns det en vektor så att kan uttryckas som
Kom ihåg linjens och planets generella parameterformer där punkten används som en fixpunkt, som ovan är noterat som .
Linjärt hölje (spann)
Ett linjärt hölje, eller spann, avser det delrum som en samling vektorer spänner upp under alla dess möjliga linjärkombinationer, och benämns som
Det innebär att för alla vektorer i detta spann finns en uppsättning skalärer så att
det vill säga, det finns en linjärkombination av -vektorerna för att uttrycka . Vidare, så gäller det att alla vektorer i spannet är linjärt beroende av .
Som exempel tar vi ett plan i . Låt parameterformen vara
Då är ett delrum till och vi kan skriva
Lösningsrum
Ett lösningsrum är vad vi hänvisar till vår samling av punkter som löser det linjära ekvationssystemet
för vår -matris . För specialfallet med ett homogent linjärt ekvationssystem, vilket betyder att högerled är , har vi att vårt lösningsrum uppfyller definitionen av ett delrum till . Låt oss säga att vi har
vilka lösningar kan uttryckas som:
som också är ett delrum till . Dessutom är denna uppsättning lösningar den triviala lösningen om, och endast om, kolonnvektorerna till är linjärt oberoende.
För icke-homogena system , det vill säga att den högra sidan är nollskild, är lösningsrummen inte delrum till . Dessa är translaterade delrum, så kallade linjära mångfald, och kan alltid refereras till deras associerade homogena system . Dessa två är associerade enligt följande:
Observera att lösningsrummen ovan endast skiljer sig åt med ett enda element, nämligen .
Geometrisk tolkning
Lösningsrummen för varje linjärt ekvationssystem följer ett, och endast ett, av de tre fallen
en (unik) punkt
oändligt många punkter eller
inga punkter
där just termen punkt oftast uttryckas som lösning, men har valts just för att göra en poäng i detta avsnitt.
En punkt
Då lösningsrumen till ekvationen
består av en enda punkt innebär det att inversen existerar, och kan därför uttryckas som
Dimensionen till lösningsrummet är därmed 0.
Oändligt många punkter
I detta fall finns inte inversen till , och det må låta kaotiskt men punkterna ligger aldrig slumpmässigt utspridda i rummet utan följer alltid en vacker form. Detta fall är det mest intressanta eftersom geometrisk tolkning kan göras, vilket i sin tur kan delas upp i tre delfall:
en linje
ett plan
ett hyperplan
Linje
Då lösningsrummet är en linje så är punkterna placerade längs med en enda riktning, tex , och dess dimensionen är 1. Då kan vi säga att parameterformen för linjen, och därmed lösningsrummet, är:
där utgör bidraget till det translaterade delrummet och utgör lösningsmängden till det associerade homogena systemet . Om korsar linjen origo och lösningsmängden kan uttryckas som
Plan
Då lösningsmängden är ett plan så har lösningsmängden en utbredning i två riktningar och dimensionen är 2, varav parameterformen skrivs som
Om korsar planet origo och lösningsmängden kan uttryckas, likt för linjen, som
Hyperplan
Ett hyperplan är det allmänna uttrycket för en ekvation i på formatet:
och dess dimension är . Det betyder att dimensionen på hyperplanet är beroende på rummet , och har speciella namn för när och när , som är linje respektive plan. Hyperplanet har därför inga speciella namn för när . Om , korsar hyperplanet origo, och dess lösningsmängd kan uttryckas som:
där är riktningsvektorerna för hyperplanet.
Inga punkter
Sista fallet är att inga punkter löser ekvationen . Det innebär att lösningsmängden är tom, eller som vi matematiker säger, "tomma mängden" och noterar det med
Sammanfattning för
För varje konsistent, homogent och linjärt ekvationssystem i så gäller för lösningsrummet att
is not defined is nothing.
is a point, the origin.
is a line through the origin.
is a plane through the origin.
is all of .
Satser för lösningsrum
Om är ett homogent system av linjära ekvationer med okända, så är dess lösningsmängd ett delrum till .
Beviset formas av att stämma av de tre kraven för underrum: nollvektorn, slutet under addition och slutet under skalär multiplikation.
uppfyller uppenbart ekvationen och är en del av lösningsmängden.
Låt och vara lösningar till systemet. Då gäller att
alltså är lösningsmängden stängd under addition
Låt vara en skalär multiplikation av . Då gäller att
för alla . Alltså är lösningsmängden stängd under skalär multiplikation.
Det leder till att generella lösningsmängden till ett homogent systemet av linjära ekvationer kan uttryckas som
vilket dessutom är ett delrum till . Dessutom är denna lösningsmängd den triviala lösningen om, och endast om, kolonnvektorerna till är linjärt oberoende.
För ickehomogena system , det vill säga att högerledet är nollskilt, gäller det att lösningsrummen inte är delrum till . Dessa är translaterade delrum, så kallade linjär mångfald, men kan alltid refereras till sitt associerade homogena system . Dessa två associeras på följande sätt:
Lägg märke till att lösningsrummen ovan skiljer sig endast åt med ett enda element, nämligen . Det leder till följande sats:
Om är ett konsistent, icke-homogent, linjärt ekvationssystem, låt då vara lösningsmängden till det associerade homogena systemet . Då är lösningsrummet till det translaterade delrummet
där är en godtycklig lösning till .
Först bevisar vi att om är en vektor i så är det även en lösning till , och därefter bevisar vi det omvända, att varje lösning till tillhör mängden .
Låt vara en vektor i och en vektor i , vilket betyder att vi kan uttrycka
där tillhör . Då har vi att
vilket visar att är en lösning till .
Låt vara en godtycklig lösning till . Då har vi har att
vilket pekar på att kan uttryckas som som tillhör .
Fler nyttiga satser på området är:
En generell lösning till ett konsistent linjärt ekvationssystem kan konstrueras genom att addera en partikulärlösning till till den generella lösningen av dess associerade homogena system, .
Om är en -matris så är följande ansatser förenliga:
har endast den triviala lösningen
har antingen en lösning eller inga lösningar för varje i
Om är en -matris, så är lösningsrummet (lösningsmängden) till det homogena systemet det som består av samtliga vektorer i som är ortogonala till varje radvektor till matrisen .
Resonemanget bakom denna sats handlar om att systemet kan utvecklas till
där varje radekvation kan betraktas som ett hyperplan i , och systemets lösningsrum kan betraktas som skärningen av alla dessa hyperplan. En förenkling av ovan system är att betrakta varje radekvations konstanter till en vektor som multipliceras med variabeln . Då får vi
vilket innebär att skalärprodukten mellan och är 0 och därmed är vinkeln dem emellan ortogonal.
