Övning 1: Använd Gram-Schmidt för att ortogonalisera {v₁, v₂} = {(1,1), (1,-1)}

u₁ = v₁ = (1,1) Beräkna proj_{u₁}(v₂): ⟨v₂,u₁⟩ = ⟨(1,-1),(1,1)⟩ = 1·1 + (-1)·1 = 0 proj_{u₁}(v₂) = (0/2)(1,1) = (0,0) u₂ = v₂ - proj_{u₁}(v₂) = (1,-1) - (0,0) = (1,-1) Resultat: {(1,1), (1,-1)} redan ortogonal! Kontroll: ⟨(1,1),(1,-1)⟩ = 1 - 1 = 0 ✓ Svar: Ortogonal bas: {(1,1), (1,-1)} (redan ortogonal!)

Övning 2: Ortogonalisera {(1,0,1), (1,1,0)} och gör ortonormal

u₁ = v₁ = (1,0,1) proj_{u₁}(v₂) = (⟨v₂,u₁⟩/⟨u₁,u₁⟩)u₁ ⟨v₂,u₁⟩ = ⟨(1,1,0),(1,0,1)⟩ = 1·1 + 1·0 + 0·1 = 1 ⟨u₁,u₁⟩ = 1² + 0² + 1² = 2 proj_{u₁}(v₂) = (1/2)(1,0,1) = (1/2,0,1/2) u₂ = v₂ - proj_{u₁}(v₂) = (1,1,0) - (1/2,0,1/2) = (1/2,1,-1/2) Normalisera: ||u₁|| = √2 → q₁ = (1/√2,0,1/√2) ||u₂|| = √(1/4+1+1/4) = √(3/2) → q₂ = (1/√6,2/√6,-1/√6) Svar: Ortonormal bas: {(1/√2,0,1/√2), (1/√6,2/√6,-1/√6)}

Övning 3: Hitta QR-faktorisering av A = [[1,1],[1,0],[0,1]] via Gram-Schmidt

Kolonnor: v₁ = (1,1,0), v₂ = (1,0,1) Gram-Schmidt: u₁ = (1,1,0), ||u₁|| = √2 → q₁ = (1/√2,1/√2,0) proj_{u₁}(v₂) = (1/2)(1,1,0) = (1/2,1/2,0) u₂ = (1,0,1) - (1/2,1/2,0) = (1/2,-1/2,1) ||u₂|| = √(3/2) → q₂ = (1/√6,-1/√6,2/√6) Q = [[1/√2,1/√6],[1/√2,-1/√6],[0,2/√6]] R-element: r₁₁ = ||u₁|| = √2 r₁₂ = ⟨v₂,q₁⟩ = 1/√2 r₂₂ = ||u₂|| = √(2/3) R = [[√2,1/√2],[0,√(2/3)]] Svar: Q = [[1/√2,1/√6],[1/√2,-1/√6],[0,2/√6]], R = [[√2,1/√2],[0,√(2/3)]]

Avancerad

Gram-Schmidt-processen

Ortogonalisering och ortonormalisering av vektorer.

Gram-Schmidt ortogonalisering ortonormal bas QR-faktorisering

Gram-Schmidt är som att rensa upp i en rörig garderob! Du tar en uppsättning linjärt oberoende vektorer (som kläder i en hög) och organiserar dem till en perfekt ortogonal bas (som kläder snyggt hängda på olika krokar). Processen tar vilken basis som helst och förvandlar den till ortogonal magi!

Fördjupning

Gram-Schmidt-processen konstruerar systematiskt en ortogonal (eller ortonormal) bas från en godtycklig bas av linjärt oberoende vektorer. Processen bygger vektorer steg för steg genom att eliminera komponenter i tidigare riktningar via ortogonala projektioner. Detta är fundamental för QR-faktorisering och numerisk stabilitet.

Grundidén bakom Gram-Schmidt

Start med bas {v₁, v₂, ..., vₙ}. Konstruera ortogonal bas {u₁, u₂, ..., uₙ} genom: u₁ = v₁, sedan för varje ny vektor subtrahera projektioner på alla tidigare ortogonala vektorer. Som att bygga koordinatsystem steg för steg!

Grundprincipen: eliminera komponenter i tidigare riktningar

Intuition i 2D

Start: v₁ = (1,0), v₂ = (1,1) (linjärt oberoende men inte ortogonala)

Steg 1: u₁ = v₁ = (1,0) ✓

Steg 2: u₂ = v₂ - proj_{u₁}(v₂)

proj_{u₁}(v₂) = ⟨v₂,u₁⟩/⟨u₁,u₁⟩ · u₁ = 1/1 · (1,0) = (1,0)

u₂ = (1,1) - (1,0) = (0,1) ✓

Resultat: {(1,0), (0,1)} - perfekt ortogonal bas!

Klassiska Gram-Schmidt algoritmen

Klassisk version: u₁ = v₁, u₂ = v₂ - proj_{u₁}(v₂), u₃ = v₃ - proj_{u₁}(v₃) - proj_{u₂}(v₃), osv. Varje ny vektor rensas från alla tidigare riktningar.

Klassisk Gram-Schmidt formel steg för steg

Komplett 3D exempel

Ortogonalisera {v₁, v₂, v₃} = {(1,1,0), (1,0,1), (0,1,1)}

Steg 1: u₁ = v₁ = (1,1,0)

Steg 2: u₂ = v₂ - proj_{u₁}(v₂)

⟨v₂,u₁⟩ = ⟨(1,0,1),(1,1,0)⟩ = 1

⟨u₁,u₁⟩ = 1² + 1² + 0² = 2

proj_{u₁}(v₂) = (1/2)(1,1,0) = (1/2,1/2,0)

u₂ = (1,0,1) - (1/2,1/2,0) = (1/2,-1/2,1)

Steg 3: u₃ = v₃ - proj_{u₁}(v₃) - proj_{u₂}(v₃)

proj_{u₁}(v₃) = (⟨v₃,u₁⟩/⟨u₁,u₁⟩)u₁ = (1/2)(1,1,0) = (1/2,1/2,0)

proj_{u₂}(v₃) = (⟨v₃,u₂⟩/⟨u₂,u₂⟩)u₂ = (1/3)(1/2,-1/2,1) = (1/6,-1/6,1/3)

u₃ = (0,1,1) - (1/2,1/2,0) - (1/6,-1/6,1/3) = (-2/3,2/3,2/3)

Resultat: ortogonal bas {(1,1,0), (1/2,-1/2,1), (-2/3,2/3,2/3)}

Modifierad Gram-Schmidt (numeriskt stabil)

Modifierad version är numeriskt mer stabil! Istället för att subtrahera alla projektioner samtidigt, gör det steg för steg: rensa u₁-komponenten, sedan u₂-komponenten, etc. Bättre för datorberäkningar!

Modifierad Gram-Schmidt för numerisk stabilitet

Skillnad i numerisk stabilitet

Problem med klassisk GS: avrundningsfel ackumuleras

Ex: v₁ = (1,1,1), v₂ = (1,1,1.0001), v₃ = (1,1.0001,1)

Klassisk GS kan ge nästan linjärt beroende resultat

Modifierad GS behåller ortogonaliteten bättre

I praktiken: använd alltid modifierad Gram-Schmidt för numeriska beräkningar!

Från ortogonal till ortonormal

Gram-Schmidt ger ortogonal bas. För ortonormal bas: normalisera varje vektor! qᵢ = uᵢ/||uᵢ||. Nu har alla vektorer längd 1 och står vinkelrätt mot varandra. Perfekt koordinatsystem!

Normalisering för att få ortonormal bas

Slutsteg: normalisering

Från föregående: u₁ = (1,1,0), u₂ = (1/2,-1/2,1), u₃ = (-2/3,2/3,2/3)

Normalisera:

||u₁|| = √(1² + 1² + 0²) = √2

q₁ = (1/√2, 1/√2, 0)

||u₂|| = √((1/2)² + (-1/2)² + 1²) = √(1/4 + 1/4 + 1) = √(3/2)

q₂ = (1/√6, -1/√6, 2/√6)

||u₃|| = √((-2/3)² + (2/3)² + (2/3)²) = √(12/9) = 2/√3

q₃ = (-1/√3, 1/√3, 1/√3)

Resultat: ortonormal bas {q₁, q₂, q₃}

QR-faktorisering via Gram-Schmidt

Bonus! Gram-Schmidt ger automatiskt QR-faktorisering A = QR där Q har ortonormala kolonner och R är övre triangulär. Q från normaliserade vektorer, R från projektionslängderna!

QR-faktorisering från Gram-Schmidt processen

Konstruera R-matrisen

A = [v₁ v₂ v₃], Q = [q₁ q₂ q₃] från Gram-Schmidt

R-elementens: rᵢⱼ = ⟨vⱼ, qᵢ⟩ för i ≤ j, annars 0

Exempel:

r₁₁ = ⟨v₁,q₁⟩ = ||u₁|| = √2

r₁₂ = ⟨v₂,q₁⟩ = proj-längd av v₂ på q₁

r₂₂ = ||u₂|| = √(3/2)

R = [[√2, r₁₂, r₁₃],[0, √(3/2), r₂₃],[0, 0, 2/√3]]

Kontroll: A = QR ✓

Tillämpningar och varianter

Gram-Schmidt är överallt! Minsta kvadrat-lösningar (QR istället för normalekvationers), principal component analysis, signalbehandling (ortogonala baser), och kvantmekanik (ortonormala tillstånd).

Minsta kvadrat via QR

Lös Ax = b (overdeterminerat)

Traditionellt: Ax = b → AᵀAx = Aᵀb (normalekvationers)

Problem: AᵀA kan vara dåligt konditionerad

Med QR: A = QR → QRx = b → Rx = Qᵀb

R är triangulär → löses enkelt med back-substitution

Numeriskt stabilare än normalekvationers!

Vanliga misstag

❌ Använda ortogonala vektorer som ortonormala

Gram-Schmidt ger ortogonal bas. För ortonormal måste man normalisera!

Exempel: Efter GS: u = (2,0,0) är ortogonal men ||u|| = 2 ≠ 1. Behöver q = (1,0,0).

❌ Fel projektionsformel

proj_u(v) = (⟨v,u⟩/⟨u,u⟩)u, inte ⟨v,u⟩u.

Exempel: Om u = (2,0): proj_u(v) = (v₁/4)(2,0), inte v₁(2,0).

❌ Glömma kontrollera linjärt oberoende

Gram-Schmidt kräver linjärt oberoende input. Annars division med noll!

Exempel: Om v₂ = 2v₁ blir u₂ = 0 → kan inte normalisera.

❌ Använd klassisk GS för numeriska problem

Modifierad Gram-Schmidt är numeriskt stabilare för datorberäkningar.

Exempel: Med avrundningsfel förlorar klassisk GS ortogonalitet snabbare.

Tillämpningar

Numerisk linjär algebra - QR-faktorisering

Gram-Schmidt ger QR-faktorisering för stabila minsta kvadrat-lösningar

Exempel: MATLAB/Python: scipy.linalg.qr() använder modifierad Gram-Schmidt

Signalbehandling - ortogonala transformationer

Konstruera ortogonala baser för signalrepresentation utan korsinterferens

Exempel: Walsh funktioner, wavelets, custom ortogonala filter

Dataanalys - principal component analysis

Ortogonalisera kovariansmatrisens egenvektorer för huvudkomponentanalys

Exempel: Dimensionsreduktion med oberoende komponenter

Kvantmekanik - tillståndskonstruktion

Konstruera ortonormala kvantillstånd från godtyckliga tillstånd

Exempel: Symmetrisera våg funktioner för atomorbital

Datorgeometri - mesh processing

Skapa lokala koordinatsystem på ytor med ortogonala tangentbaser

Exempel: UV-mapping, normal/tangent/bitangent koordinatsystem

Övningar

1 Lätt

Använd Gram-Schmidt för att ortogonalisera {v₁, v₂} = {(1,1), (1,-1)}

Tips

Börja med u₁ = v₁, sedan u₂ = v₂ - proj_{u₁}(v₂)

Visa facit

u₁ = v₁ = (1,1)
Beräkna proj_{u₁}(v₂):
⟨v₂,u₁⟩ = ⟨(1,-1),(1,1)⟩ = 1·1 + (-1)·1 = 0
proj_{u₁}(v₂) = (0/2)(1,1) = (0,0)
u₂ = v₂ - proj_{u₁}(v₂) = (1,-1) - (0,0) = (1,-1)
Resultat: {(1,1), (1,-1)} redan ortogonal!
Kontroll: ⟨(1,1),(1,-1)⟩ = 1 - 1 = 0 ✓

Svar: Ortogonal bas: {(1,1), (1,-1)} (redan ortogonal!)

2 Medel

Ortogonalisera {(1,0,1), (1,1,0)} och gör ortonormal

Tips

Första Gram-Schmidt, sedan normalisera båda vektorerna

Visa facit

u₁ = v₁ = (1,0,1)
proj_{u₁}(v₂) = (⟨v₂,u₁⟩/⟨u₁,u₁⟩)u₁
⟨v₂,u₁⟩ = ⟨(1,1,0),(1,0,1)⟩ = 1·1 + 1·0 + 0·1 = 1
⟨u₁,u₁⟩ = 1² + 0² + 1² = 2
proj_{u₁}(v₂) = (1/2)(1,0,1) = (1/2,0,1/2)
u₂ = v₂ - proj_{u₁}(v₂) = (1,1,0) - (1/2,0,1/2) = (1/2,1,-1/2)
Normalisera:
||u₁|| = √2 → q₁ = (1/√2,0,1/√2)
||u₂|| = √(1/4+1+1/4) = √(3/2) → q₂ = (1/√6,2/√6,-1/√6)

Svar: Ortonormal bas: {(1/√2,0,1/√2), (1/√6,2/√6,-1/√6)}

3 Svår

Hitta QR-faktorisering av A = [[1,1],[1,0],[0,1]] via Gram-Schmidt

Tips

Ortogonalisera kolonnerna, bygg Q och R samtidigt

Visa facit

Kolonnor: v₁ = (1,1,0), v₂ = (1,0,1)
Gram-Schmidt:
u₁ = (1,1,0), ||u₁|| = √2 → q₁ = (1/√2,1/√2,0)
proj_{u₁}(v₂) = (1/2)(1,1,0) = (1/2,1/2,0)
u₂ = (1,0,1) - (1/2,1/2,0) = (1/2,-1/2,1)
||u₂|| = √(3/2) → q₂ = (1/√6,-1/√6,2/√6)
Q = [[1/√2,1/√6],[1/√2,-1/√6],[0,2/√6]]
R-element:
r₁₁ = ||u₁|| = √2
r₁₂ = ⟨v₂,q₁⟩ = 1/√2
r₂₂ = ||u₂|| = √(2/3)
R = [[√2,1/√2],[0,√(2/3)]]

Svar: Q = [[1/√2,1/√6],[1/√2,-1/√6],[0,2/√6]], R = [[√2,1/√2],[0,√(2/3)]]

Sammanfattning

Gram-Schmidt transformerar linjärt oberoende vektorer till ortogonal bas genom systematisk elimination av komponenter i tidigare riktningar. Klassisk: u_k = v_k - ∑proj_{uᵢ}(v_k). Modifierad version numeriskt stabilare. QR-faktorisering följer automatiskt. Fundamental för numerisk linjär algebra, signalbehandling, och många optimeringsmetoder.