Hopp til innhald

Gram–Schmidts ortogonaliseringsprossess

Frå Wikipedia – det frie oppslagsverket

Gram–Schmidts ortogonaliseringsprossess er ein algoritme for å generera ein ortonormalisert basis (ortogonal basis med norm 1) frå ei gjeven mengde vektorar knytte til eit indreproduktrom med eit gjeve skalarprodukt ⟨⋅,⋅⟩.

Metoden vart oppkalla etter Erhard Schmidt og Jørgen Pedersen Gram, sjølv om han tidlegare vart teken i bruk i verka til Laplace og Cauchy.

Han vert nytta i dei høva ein ønskjer ein ortonormal/ortogonal basis. Å finna QR-faktoriseringa av ei matrise er i røynda Gram-Schmidts ortogonaliseringsprossess.

Algoritmen er basert på definisjonen av projeksjonar. Ein projeksjon er definert som;

proj𝐯𝐱=⟨𝐱,𝐯⟩⟨𝐯,𝐯⟩𝐯.

La v1,..vn vera resulatet av algoritmen, altså den ortonormale basisen. La x1,..,xn vera vektorane det skal konstruerast ein ortonormal basis av. Ein let v1=x1 og normaliserer vektoren. Vidare vert vektoren x2 projektert på vektoren v1. Ut i frå dette vert v2vektoren som står ortogonalt på denne projeksjonen, altså v2=x2−projv1x2=x2−x2⋅v1v1⋅v1v1. Vidare vert x3 projektert på flata utspend av v1 og v2. Vektoren som står ortogonalt på denne flata er v3. Med andre ord så vert v3=x3−projv1x3+projv2x3. Slik held algoritmen fram til ein har konstruert ein ortonormal basis.

Heile algoritmen kan oppsummerast stegvis som

𝐯1=𝐱1, 𝐞1=𝐯1||𝐯1||
𝐯2=𝐱2−proj𝐯1𝐱2, 𝐞2=𝐯2||𝐯2||
𝐯3=𝐱3−proj𝐯1𝐱3−proj𝐯2𝐱3, 𝐞3=𝐯3||𝐯3||
⋮ ⋮
𝐯k=𝐱k−∑j=1k−1proj𝐯j𝐱k, 𝐞k=𝐯k||𝐯k||

For kvart steg vert vektoren vknormalisert.