Intro
Namnet Gram-Schmidt antogs av det matematiska samfundet efter att den tyske vetenskapsmannen Erhard Schmidt publicerade en disposition för denna algoritm 1907.
I sin uppsats erkände Schmidt också att den danske aktuarien och matematikern Jørgen Pedersen Gram hade använt en liknande teknik före honom.
Tyvärr levde Gram inte för att se sitt namn i titeln på den berömda algoritmen, på grund av att han stod inför en helt bisarr och tragisk död.
På väg till ett möte med Den Kungliga Danska Vetenskapsakademien blev Gram påkörd och dödad av en cyklist.
Koncept
Ett koordinatsystem kan byggas upp på många olika sätt. Den form vi är mest bekant med är det kartesiska koordinatsystemet vars axlar är vinkelräta och märkta med samma enheter.
Anledningen till att just detta koordinatsystem har blivit standard är för att det är intuitivt för oss och förenklar mycket av matematiken.
För olika tillämpningar av linjär algebra kanske vi dock inte har turen att problemet vi försöker lösa överlämnas till oss i denna enkla form.
I sådana fall kanske vi vill omvandla ett konstigt koordinatsystem till den form vi är vana vid att arbeta med.
Det är precis vad Gram-Schmidt-metoden gör för oss.
Summering
Givet en mängd av n linjärt oberoende vektorer:
Gram-Schmidt-algoritmen bildar ett vektorrum och konstruerar en ortonormerad bas av :
Gram-Schmidt-proceduren: Först låter vi , och sedan normera vi för att beräkna
För att producera följande ortonormerad bas, betraktar vi varje motsvarande vektor (innan normalisering) och vi subtraherar projektionen av denna vektor på de tidigare beräknade bas . Därför blir formeln:
där det andra steget är att normera den resulterande vektorn, vilket ger oss den ortonormerad bas basvektorn .
Gram-Schmidt
Introduktion
Gram-Schmidt är en algoritm för att skapa en ny ON-bas utifrån en existerande bas. Säg att vi har en bas
som spänner upp ett underrum . Utmaningen är då att definiera en ny bas
som spänner upp samma underrum men som dessutom är en ortonormal bas.
Gram-Schmidt är en algoritm som skapar en ON-bas utifrån en existerande bas
Matematiskt gäller för ovan två baser samt basvektorerna för :
Algoritmen
Vi introducerar algoritmen här och går därefter igenom exempel för 2D och 3D. Vissa av oss har en fallenhet att känna igen mönster medan andra behöver få en geometrisk genomgång av algoritmens varje steg. Rekommendationen är att först läsa igenom algoritmen nedan ytligt och därefter förstå geometrin för våra två exempel.
Låt
spänna upp underrummet . Vi skapar en ON-bas till som vektorerna
och definierar dem som:
där är underrum till och växer med en dimension för varje steg.
Tolkning av algoritmen
Algoritmen och dess steg kan sammanfattas till:
Algoritmen har lika många steg som antal basvektorer . I varje enskilt steg skapar vi en ny ON-basvektor .
För varje steg definierar vi underrummet som spänns upp av alla ON-basvektorer vi dittills har definierat.
För varje steg definierar vi den nya ON-basvektorn som vektorn mellan och projektionen av på underrummet .
Projektionen i algoritmen
För algoritmens andra steg ser vi att är definierad som
där underrummet endimensionellt och spänns upp av
För detta steg kan vi enkelt använda oss av projektionsformeln, men från och med tredje steget där vi har
har underrummet dimension högre än 1. Då räcker inte projektionsformeln till, men vi kan ta stöd av den tack vare att -vektorerna bildar en ON-bas, för då gäller att
eftersom att och är normerade. Skulle de inte vara normerade förkortas inte uttrycket lika vackert, utan det generella uttrycket blir
eftersom att nämnaren i bråken inte längre är lika med 1. Det generella fallet följer analogt, givet att -vektorerna är normerade:
Gram-Schmidt i 2D
Exempel 1
I vårt första exempel har vi basen
där spänner upp och
Vi utför Gram-Schmidt och börjar med första steget: att definiera den första ON-basvektorn som normen av samt att definiera underrummet :
Nästa, och sista, steget för det här exemplet är att definiera den andra ON-basvektorn enligt
Vår nya ON-bas för är alltså
där vektorerna både har längden 1 och är ortogonala mot varandra.
Exempel 2
I vårt andra exempel för 2D tar basen
som spänner upp planet som är ett underrum till och
Men, hur kan ett exempel i rummet kvalificeras för ett exempel för 2D? Det är ett exempel för 2D eftersom att vi skapar en ny ON-bas till underrummet , vars dimension är 2 då dess basvektorer är två.
Vi utför Gram-Schmidt.
Som i första exemplet har vi endast ett steg till, vilket är att definiera den andra ON-basvektorn enligt
Innan vi utför det sista normerande steget kan vi applicera ett enkelt trick för att få en snyggare vektor . Då vi ska normera vektorn spelar dess ursprungliga längd ingen roll för normeringssteget. Se därför vad som sker när vi väljer att förlänga vektorn med två innan vi normerar:
Visst blev den senare vektorn betydligt snyggare än den första? enklare skalär samt inga bråk inom parenteserna. Vår nya ON-bas för blir alltså
Gram-Schmidt i 3D
Låt oss bestämma en ON-bas med hjälp av Gram-Schmidt som spänner upp samma underrum till som basen
spänner upp.
De två första stegen i algoritmen blir då ekvivalenta med andra exemplet för 2D och vi kan återanvända resultaten för och . Vi har att
vilket tar oss till steg tre, nämligen att beräkna
där vi har att
Alltså leder det till att vår nya basvektor uttrycks som
Låt oss angripa de två projektionerna separat för att underlätta beräkningarna.
Vi sätter in våra beräkningar i uttrycket ovan.
Vi normerar nu som sista delsteg av steg 3 i algoritmen, men vi förlänger vektorn först med 3/2 för att underlätta beräkningar och få en snyggare basvektor:
Gram-Schmidt är klart för denna gång och Vi konkluderar vår nya bas som
Ortonormal bas
En bas är ortonormal om dess basvektorer är ortogonala mot varandra och alla har längd ett, det vill säga en ortogonal bas med det ytterligare villkoret att alla basvektorer är normerade. Formellt kan vi definiera det på följande sätt:
Låt vara en bas till underrummet . kallas ortonormal om, och endast om:
Ortogonal bas
En bas är ortogonal om samtliga basvektorer är vinkelräta mot varandra. Formellt kan vi definiera det på följande sätt:
Låt vara en bas till underrummet . kallas för ortogonal om, och endast om:
Ortogonal matris
En matris är ortogonal om den är kvadratisk och alla dess kolonnvektorer är vinkelräta mot varandra samt har längd ett. En mycket naturlig reaktionen är att matrisen då borde heta ortonormalmatris, vilket vissa källor tillåter. Men det konventionella namnet är just ortogonalmatris även om namnet är förvirrande och därför lite olyckligt valt. Det finns ett rykte att en prominent, men virrig, matematiker en gång i tiden valde fel namn och felet har sedan dess aldrig korrigerats. Låt oss formalisera definitionen:
Låt vara en kvadratisk matris
och kallas ortogonalmatris om, och endast om:
