Ortogonalizacja Grama-Schmidta

Z testwiki
Przejdź do nawigacji Przejdź do wyszukiwania

Ortogonalizacja Grama-Schmidta – przekształcenie układu liniowo niezależnych wektorów przestrzeni unitarnej w układ wektorów ortogonalnych. Przestrzenie liniowe rozpinane przez układy przed i po ortogonalizacji są tożsame, tak więc proces może służyć do ortogonalizowania bazy.

Opisana w tym artykule metoda nazwana została na cześć Jørgena Grama, matematyka duńskiego oraz Erharda Schmidta, matematyka niemieckiego.

Proces ortogonalizacji

Dwa pierwsze kroki procesu ortogonalizacji

Operator rzutowania ortogonalnego wektora 𝐯 na wektor 𝐮 definiujemy jako:

proj𝐮𝐯=⟨𝐯,𝐮⟩⟨𝐮,𝐮⟩𝐮.

Wówczas dla układu k wektorów {𝐯1,…,𝐯k} proces przebiega następująco:

𝐮1=𝐯1,
𝐮2=𝐯2−proj𝐮1𝐯2,
𝐮3=𝐯3−proj𝐮1𝐯3−proj𝐮2𝐯3,
⋮
𝐮k=𝐯k−∑j=1k−1proj𝐮j𝐯k,

czyli wektor uk to wektor vk po odjęciu od niego rzutu wektora vk na podprzestrzeń rozpiętą przez wektory u1,...,uk−1. Otrzymany zbiór {𝐮1,…,𝐮k} jest zbiorem wektorów ortogonalnych.

Aby zbudować w ten sposób zbiór ortonormalny, każdy wektor należy podzielić przez jego normę:

𝐞n=𝐮n||𝐮n||,n=1,2,...,k

Proces ortogonalizacji pozwala na wskazanie bazy ortogonalnej w dowolnej przestrzeni unitarnej (niekoniecznie skończenie wymiarowej).

Własności numeryczne tego algorytmu nie są zbyt dobre i uzyskane wektory nadal nie są ortogonalne (za sprawą błędów zaokrągleń), toteż w praktyce powtarza się proces dokonując reortogonalizacji.

Dowód ortogonalności otrzymanej bazy

Dowód ortogonalności tak otrzymanego układu opiera się na indukcji.

Niech 𝐮1,…,𝐮k jest układem wektorów uzyskanym w procesie ortogonalizacji Grama-Schmidta z bazy 𝐯1…𝐯k. Załóżmy, że wektory 𝐮1,…,𝐮k−1 są wzajemnie prostopadłe, czyli spełniają ⟨𝐮s,𝐮t⟩=0 dla wszystkich t,s∈{1…k−1},t≠s oraz 𝐮s≠0 dla s∈{1…k−1}.

Pokażemy, że wektor 𝐮k otrzymany z algorytmu ortogonalizacji Grama-Schmidta jest prostopadły z dowolnym wektorem 𝐮l, gdzie l∈{1,…,k−1}.

𝐮k=𝐯k−∑j=1k−1⟨𝐯k,𝐮j⟩⟨𝐮j,𝐮j⟩𝐮j

Mnożąc skalarnie 𝐮k i 𝐮l i korzystając z własności iloczynu skalarnego (rozdzielności iloczynu względem sumy, przemienności i zgodności z mnożeniem przez skalar) otrzymujemy:

⟨𝐮k,𝐮l⟩=⟨ 𝐯k−∑j=1k−1⟨𝐯k,𝐮j⟩⟨𝐮j,𝐮j⟩𝐮j,𝐮l⟩=⟨𝐯k,𝐮l⟩−∑j=1k−1⟨𝐯k,𝐮j⟩⟨𝐮j,𝐮j⟩⟨𝐮j,𝐮l⟩

Na mocy założenia indukcyjnego w ostatniej sumie wszystkie składniki o indeksie j≠l są zerowe, więc:

⟨𝐮k,𝐮l⟩=⟨𝐯k,𝐮l⟩−⟨𝐯k,𝐮l⟩⟨𝐮l,𝐮l⟩⟨𝐮l,𝐮l⟩=0

co oznacza, że wektor 𝐮k jest prostopadły z każdym innym wektorem 𝐮1,…,𝐮k−1

Wektor 𝐮k jest kombinacją liniową wektorów 𝐮1,…,𝐮k−1,𝐯k. Z kolei 𝐮k−1 jest kombinacją liniową wektorów 𝐮1,…,𝐮k−2,𝐯k−1. Analogicznie dla wektora 𝐮k−2 i tak dalej. Ostatecznie wektor 𝐮k jest kombinacją liniową wektorów 𝐯1,…,𝐯k−1,𝐯k a dokładniej

𝐮k=α1𝐯1+…+αk−1𝐯k−1+1⋅𝐯k.

Gdyby 𝐮k=0, to układ 𝐯1,…,𝐯k−1,𝐯k wbrew założeniom byłby liniowo zależny, bo nie wszystkie współczynniki liczbowe kombinacji są zerowe.

Ponieważ ortogonalny układ wektorów jest liniowo niezależny, a każdy z wektorów 𝐮i jest kombinacją liniową elementów z bazy 𝐯1,…,𝐯k, więc tak wyznaczone wektory 𝐮1,…,𝐮k istotnie są bazą.

Przykłady

Przestrzeń R²

Rozważmy zbiór wektorów w 𝐑2 (ze standardowym iloczynem skalarnym):

S={𝐯1=[31],𝐯2=[22]}.

Teraz przeprowadzamy ortogonalizację, aby otrzymać wektory parami prostopadłe:

𝐮1=𝐯1=[31]
𝐮2=𝐯2−proj𝐮1(𝐯2)=[22]−proj[31]([22])=[−2/56/5].

Sprawdzamy, że wektory u1 i u2 rzeczywiście są prostopadłe:

⟨𝐮1,𝐮2⟩=⟨[31],[−2/56/5]⟩=−65+65=0,

ponieważ jeśli dwa wektory są prostopadłe, to ich iloczyn skalarny wynosi 0.

Następnie normalizujemy wektory, dzieląc każdy przez ich normy:

𝐞1=110[31]
𝐞2=14025[−2/56/5]=110[−13].

Przestrzeń wielomianów

W przestrzeni wielomianów R[x] wielomiany postaci xk stanowią bazę. Iloczyn skalarny w tej przestrzeni można wprowadzić np. w ten sposób:

⟨f,g⟩w=∫−11f(x)g(x)dx   f,g∈R[x]

Przeprowadzając proces ortogonalizacji układu 1,x,x2,x3,…, dostaniemy układ ortogonalny 1,x,x2−13,x3−35x,…

Są to z dokładnością do czynnika wielomiany Legendre’a:

Pn(x)=dndxn(x2−1)n(n=0,1,…).

Po znormalizowaniu powstanie układ

Pn~(x)=n+12⋅1(2n)!!Pn(x).

Zobacz też

Bibliografia

Linki zewnętrzne

Szablon:Otwarty dostęp Piotr Stachura, nagrania dla Khan Academy na YouTube [dostęp 2024-06-22]:

Szablon:Formy na przestrzeniach liniowych

Źródło: „https://pl.wiki.beta.math.wmflabs.org/w/index.php?title=Ortogonalizacja_Grama-Schmidta&oldid=901”