Articles /

Gram-Schmidt-processen

af Marco Taboga, PhD

Gram-Schmidt-processen (eller -proceduren) er en række operationer, der gør det muligt at omdanne et sæt af lineært uafhængige vektorer til et sæt ortonormale vektorer, der dækker det samme rum som det oprindelige sæt.

Indholdsfortegnelse

Preliminarier

Lad os gennemgå nogle begreber, der er væsentlige for at forstå Gram-Schmidt-processen.

Husk, at to vektorer $r$ og $s$ siges at være ortogonale, hvis og kun hvis deres indre produkt er lig nul, det vil sige,

Givet et indre produkt kan vi definere normen (længden) for en vektor $s$ som følger:

Et sæt af vektorer kaldes ortonormalt, hvis og kun hvis dets elementer har enhedsnorm og er ortogonale til hinanden. Med andre ord er et sæt af K vektorer ortonormalt, hvis og kun hvis

Vi har bevist, at vektorerne i et ortonormalt sæt er lineært uafhængige.

Når en basis for et vektorrum også er et ortonormalt sæt, kaldes det en ortonormal basis.

Projektioner på ortonormale sæt

I Gram-Schmidt-processen anvender vi gentagne gange den næste sætning, som viser, at enhver vektor kan nedbrydes i to dele: 1) dens projektion på et ortonormalt sæt og 2) en rest, der er ortogonal til det givne ortonormale sæt.

Sætning Lad $S$$ være et vektorrum udstyret med et indre produkt . Lad være et ortonormalt sæt. For en hvilken som helst $sin S$ har vihvor $arepsilon _{S}$ er ortogonal til $u_{k}$ for en hvilken som helst $k=1,ldots ,K.$

Bevis

DefinereSå har vi for hver $j=1,ldots ,K$, athvor: i trin $rame{A}$ og $rame{B}$ har vi brugt den kendsgerning, at det indre produkt er lineært i sit første argument; i trin $rame{C}$ har vi anvendt det faktum, at hvis $keq j$, da vi har at gøre med et ortonormalt sæt; i trin $rame{D}$ har vi anvendt det faktum, at normen for $u_{j}$ er lig med 1. Derfor er $arepsilon _{S}$, som defineret ovenfor, ortogonal til alle elementerne i det ortonormale sæt, hvilket beviser sætningen.

Udtrykketkaldes den lineære projektion af $s$ på den ortonormale mængde , mens udtrykket $arepsilon _{S}$ kaldes residualen af den lineære projektion.

Normalisering

En anden måske indlysende kendsgerning, som vi vil bruge gentagne gange i Gram-Schmidt-processen, er, at hvis vi tager en hvilken som helst vektor, der ikke er nul, og vi dividerer den med dens norm, så er resultatet af divisionen en ny vektor, der har enhedsnorm.

Med andre ord, hvis så har vi ved normens definitionsegenskab, at

Som følge heraf kan vi definereog ved normens positivitet og absolut homogenitet, har vi

Overblik over proceduren

Nu hvor vi ved, hvordan man normaliserer en vektor, og hvordan man dekomponerer den i en projektion på et ortonormalt sæt og en rest, er vi klar til at forklare Gram-Schmidt-proceduren.

Vi vil give et overblik over fremgangsmåden, hvorefter vi vil udtrykke den formelt som en sætning, og vi vil diskutere alle de tekniske detaljer i beviset for sætningen.

Her er overblikket.

Vi får et sæt af lineært uafhængige vektorer .

For at starte processen normaliserer vi den første vektor, dvs. vi definerer

I det andet trin projicerer vi $s_{2}$ på $u_{1}$:hvor $arepsilon _{2}$ er restværdien af projektionen.

Derefter normaliserer vi residualet:

Vi vil senere bevise, at (således at normaliseringen kan foretages), fordi startvektorerne er lineært uafhængige.

De to vektorer $u_{1}$ og $u_{2}$, der således opnås, er ortonormale.

I det tredje trin projicerer vi $s_{3}$ på $u_{1}$ og $u_{2}$:og vi beregner restværdien af projektionen $arepsilon _{3}$.

Vi normaliserer den derefter:

Vi fortsætter på denne måde, indtil vi får den sidste normaliserede residual $u_{K} $.

Ved processens afslutning danner vektorerne et ortonormalt sæt, fordi:

  1. de er resultatet af en normalisering, og som følge heraf har enhedsnorm;

  2. hver $u_{k}$ fås fra en residual, der har den egenskab at være ortogonal til .

For at supplere denne oversigt skal vi huske, at det lineære spænd af er mængden af alle vektorer, der kan skrives som lineære kombinationer af ; det betegnes medog det er et lineært rum.

Da vektorerne er lineært uafhængige kombinationer af , kan enhver vektor, der kan skrives som en lineær kombination af , også skrives som en lineær kombination af . Derfor er spændvidderne for de to sæt af vektorer sammenfaldende:

Formelt udsagn

Vi formaliserer her Gram-Schmidt-processen som et udsagn, hvis bevis indeholder alle de tekniske detaljer i proceduren.

Sætning Lad $S$ være et vektorrum udstyret med et indre produkt . Lad være lineært uafhængige vektorer. Så findes der et sæt ortonormale vektorer , således atfor enhver $kleq K$.

Bevis

Beviset er ved induktion: Først beviser vi, at sætningen er sand for $k=1$, og derefter beviser vi, at den er sand for en generisk k, hvis den gælder for $k-1$. Når $k=1$, har vektorenenhedsnorm, og den udgør i sig selv et ortonormalt sæt: der er ingen andre vektorer, så ortogonalitetsbetingelsen er trivielt opfyldt. Mængdener mængden af alle skalariske multipla af $s_{1}$, som også er skalariske multipla af $u_{1}$ (og vice versa). Derfor: Nu antager vi, at sætningen er sand for $k-1$. Så kan vi projicere $s_{k}$ på :hvor residualen $arepsilon _{k}$ er ortogonal til . Antag, at $arepsilon _{k}=0$. Så,da vi ved en antagelse har for enhver $jleq k-1$, har vi, at for enhver $jleq k-1$, hvor $lpha _{jl}$ er skalarer. Derfor,Med andre ord fører antagelsen om, at $arepsilon _{k}=0$ til den konklusion, at $s_{k}$ er en lineær kombination af . Men det er umuligt, fordi en af antagelserne i sætningen er, at er lineært uafhængige. Som følge heraf må det være sådan, at . Vi kan derfor normalisere residualet og definere vektorensom har enhedsnorm. Vi ved allerede, at $arepsilon _{k}$ er ortogonal til . Dette indebærer, at også $u_{k}$ er ortogonal til . Således er et ortonormalt sæt. Tag nu en hvilken som helst vektor $sin S$, der kan skrives somhvor er skalarer. Da vi ved en antagelse har vi, at ligning (2) også kan skrives somhvor er skalarer, og: i trin $rame{A}$ har vi brugt ligning (1); i trin $rame{B}$ har vi brugt definitionen af $u_{k}$. Vi har således bevist, at enhver vektor, der kan skrives som en lineær kombination af , også kan skrives som en lineær kombination af . Antagelse (3) gør det muligt at bevise det omvendte på en helt analog måde:Med andre ord er enhver lineær kombination af også en lineær kombination af . Dette beviser, at og afslutter beviset.

Hvert indre produktrum har en ortonormal basis

Følgende sætning præsenterer en vigtig konsekvens af Gram-Schmidt-processen.

Sætning Lad $S$ være et vektorrum udstyret med et indre produkt . Hvis $S$$ har finite dimension , findes der en ortonormal basis for $S$$.

Bevis

Da $S$ har finite dimensioner, findes der mindst én basis for $S$, som består af K vektorer . Vi kan anvende Gram-Schmidt-proceduren på grundlaget og opnå et ortonormalt sæt . Da er en basis, spænder den over $$S$. Derfor er Dermed er en ortonormal basis for $S$.

Løste opgaver

Nedenfor finder du nogle opgaver med forklarede løsninger.

Ovelse 1

Betragt rummet $S$$ af alle $3imes 1$ vektorer med reelle indgange og det indre produkthvor $r,sin S$ og $s^{op }$ er transponeringen af $s$. Definer vektoren

Normalisér $s$.

Løsning

Normen for $s$ erDerfor, normaliseringen af $$s$ er

Ovelse 2

Betragt rummet $S$ af alle $2imes 1$ vektorer med reelle poster og det indre produkthvor $r,sin S$ . Betragt de to lineært uafhængige vektorer

Transformér dem til et ortonormalt sæt ved hjælp af Gram-Schmidt-processen.

Løsning

Normen for $s_{1}$ er Derfor, den første ortonormale vektor erDet indre produkt af $s_{2}$ og $u_{1}$ erProjektionen af $s_{2}$ på $u_{1}$ erRestproduktet af projektionen erRestproduktets norm erog det normaliserede restprodukt erDermed er, det ortonormale sæt, som vi ledte efter, er

Hvordan citeres

Citer venligst som:

Taboga, Marco (2017). “Gram-Schmidt-processen”, Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/Gram-Schmidt-process.

Leave a Reply