Gram-Schmidts ortogonaliseringsprocess

Efter denna lektion kommer du att kunna tillämpa Gram-Schmidts ortogonaliseringsprocess för att omvandla en godtycklig bas i ett vektorrum till en ortogonal och ortonormerad bas (ON-bas), samt förstå kopplingarna till QR-faktorisering.

Introduktion till ortogonala och ortonormerade baser

Inom linjär algebra är baser för vektorrum ett helt centralt verktyg. En godtycklig bas består av linjärt oberoende vektorer, men vektorerna kan bilda godtyckliga vinklar med varandra och ha olika längder. Detta gör ofta beräkningar som koordinatbestämning, projektioner och matrisinversioner komplicerade.

En ortogonal bas är en bas där alla vektorpar är vinkelräta mot varandra (deras skalärprodukt är 0). Om vi dessutom kräver att varje vektor har längden 1 (dvs. normen ||u|| = 1), kallas basen för en ortonormerad bas (ofta förkortad ON-bas).

Fördelarna med en ON-bas är enorma:

1. Enkel koordinatberäkning: Om e₁, e₂, ..., eₙ utgör en ON-bas kan varje vektor x skrivas som x = (x · e₁) e₁ + (x · e₂) e₂ + ... + (x · eₙ) eₙ, helt utan att lösa ett ekvationssystem.

2. Numerisk stabilitet: Ortogonala transformationsmatriser bevarar avstånd och vinklar, vilket minskar avrundningsfel vid datorberäkningar.

Gram-Schmidts ortogonaliseringsprocess är en algoritm som tar en godtycklig bas v₁, v₂, ..., vₙ och steg för steg bygger om den till en ortogonal bas u₁, u₂, ..., uₙ, som sedan enkelt kan normaliseras till en ON-bas e₁, e₂, ..., eₙ.

Ortogonal projektion: Byggstenen i Gram-Schmidt

Kärnan i Gram-Schmidts process är begreppet ortogonal projektion. Om vi har en vektor v och en nollskild vektor u, kan vi dela upp v i två komponenter: en som är parallell med u och en som är ortogonal (vinkelrät) mot u.

Den parallella komponenten kallas projektionen av v på u och beräknas med formeln:

proj_u(v) = ((u · v) / (u · u)) u

Den ortogonala komponenten blir då w = v − proj_u(v).

Vi kan lätt verifiera att w faktiskt är vinkelrät mot u genom att ta skalärprodukten:

w · u = (v − ((u · v) / (u · u)) u) · u = (v · u) − ((u · v) / (u · u)) (u · u) = (v · u) − (u · v) = 0.

Exempel:

Låt u = (2, 0) och v = (3, 4).

Skalärprodukten u · v = 2×3 + 0×4 = 6.

Skalärprodukten u · u = 2² + 0² = 4.

Projektionen proj_u(v) = (6 / 4) × (2, 0) = 1.5 × (2, 0) = (3, 0).

Den ortogonala komponenten w = (3, 4) − (3, 0) = (0, 4).

Notera att (0, 4) · (2, 0) = 0, så de är ortogonala!

Gram-Schmidts algoritmiska steg i 3D

Nu sätter vi ihop projektionerna till en fullständig algoritm. Givet en bas {v₁, v₂, v₃} konstruerar vi en ortogonal bas {u₁, u₂, u₃} steg för steg:

1. Första vektorn: Välj den första ursprungliga vektorn som den är:

u₁ = v₁

2. Andra vektorn: Dra bort projektionen av v₂ på u₁:

u₂ = v₂ − proj_u₁(v₂)

där proj_u₁(v₂) = ((u₁ · v₂) / (u₁ · u₁)) u₁

3. Tredje vektorn: Dra bort projektionerna av v₃ på BÅDE u₁ och u₂:

u₃ = v₃ − proj_u₁(v₃) − proj_u₂(v₃)

där proj_u₁(v₃) = ((u₁ · v₃) / (u₁ · u₁)) u₁ och proj_u₂(v₃) = ((u₂ · v₃) / (u₂ · u₂)) u₂

Processen kan generaliseras till n dimensioner. För varje ny vektor vₖ drar vi bort projektionerna av vₖ på alla redan skapade ortogonala vektorer u₁, u₂, ..., uₖ₋₁.

Resultatet {u₁, u₂, u₃} är en ortogonal bas. Om vi avslutningsvis dividerar varje vektor med dess längd ||uᵢ|| erhåller vi en ON-bas {e₁, e₂, e₃}.

Normalisering till ON-bas och QR-faktorisering

När vi har en ortogonal bas {u₁, u₂, ..., uₙ} kan vi enkelt skala om varje vektor så att den får längden 1. Detta kallas normalisering:

eᵢ = uᵢ / ||uᵢ||, där ||uᵢ|| = √(uᵢ · uᵢ)

Mängden {e₁, e₂, ..., eₙ} bildar då en ortonormerad bas (ON-bas).

Kopplingen till QR-faktorisering:

Gram-Schmidt-processen ligger till grund för en mycket viktig matrisreducering kallad QR-faktorisering.

Om vi samlar ursprungsvektorerna v₁, ..., vₙ som kolumner i en matris A, kan A faktoriseras som:

A = Q R

där:

• Q är en matris vars kolumner är ON-basvektorerna e₁, e₂, ..., eₙ. (Detta innebär att Qᵀ Q = I).
• R är en övre triangulär matris som innehåller skalärprodukterna och normerna från Gram-Schmidt-beräkningarna.

QR-faktorisering används i beräkningsmatematik för att lösa minstakvadratproblem (t.ex. vid linjär regression) och för att beräkna egenvärden numeriskt stabilt.