Процес Грама — Шмідта

Процес ортогоналізації Грама — Шмідта на трьох лінійно незалежних, неортогональних векторах

Процес Грама - Шмідта — найвідоміший алгоритм ортогоналізації, в якому за лінійно-незалежною системою ${𝐯}_1,{𝐯}_2,\dots ,{𝐯}_k$ будується ортогональна система ${𝐮}_1,{𝐮}_2,\dots ,{𝐮}_k$ така, що кожний вектор ${𝐮}_i$ лінійно виражається через ${𝐯}_1,{𝐯}_2,\dots ,{𝐯}_i$, тобто матриця переходу від $\{{𝐯}_i\}$ до $\{{𝐮}_i\}$ ― верхня трикутна матриця.

Можна пронормувати систему $\{{𝐮}_i\}$ і зробити, щоб діагональні елементи матриці переходу були додатніми; ці умови однозначно визначають систему$\{{𝐮}_i\}$ та матрицю переходу.

Процес Грама — Шмідта застосований до матриці з лінійно-незалежними стовпцями є QR розкладом матриці (розклад на ортогональну і верхню трикутну матрицю з додатніми діагональними елементами).

Алгоритм

Перші 2 кроки ортогоналізації

Визначимо ортогонально-проєкційний оператор

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{𝐮}𝐯=\frac{⟨𝐮,𝐯⟩}{⟨𝐮,𝐮⟩}𝐮=\frac{𝐮{𝐮}^{\mathrm{\top }}}{⟨𝐮,𝐮⟩}\cdot 𝐯=𝐞{𝐞}^{\mathrm{\top }}\cdot 𝐯,𝐞=\frac{𝐮}{\Vert 𝐮\Vert },$

де <u, v> означає скалярний добуток векторів u and v. Цей оператор проектує вектор v ортогонально на вектор u.

Приймемо ${𝐮}_1={𝐯}_1$ та запишемо рекурсивну формулу

${𝐮}_i={𝐯}_i-\sum _{j=1}^{i-1}\frac{⟨{𝐯}_i,{𝐮}_j⟩}{⟨{𝐮}_j,{𝐮}_j⟩}{𝐮}_j={𝐯}_i-\left(\sum _{j=1}^{i-1}{𝐞}_j{𝐞}_j^{\mathrm{\top }}\right){𝐯}_i.$

Нормуючи вектори ${𝐮}_i$, отримаємо ортонормовану систему о$\{{𝐞}_i\}$.

Геометричний зміст процесу в тому, що вектор ${𝐮}_i$ є проєкцією вектора ${𝐯}_i$ на перпендикуляр до лінійної оболонки векторів ${𝐯}_1,\dots ,{𝐯}_{i-1}.$

Властивості

• Для кожного $i$ лінійні оболонки систем ${𝐯}_1,\dots ,{𝐯}_i$ та ${𝐮}_1,\dots ,{𝐮}_i$ збігаються.
• Добуток довжин ${𝐮}_i$ дорівнює об'єму паралелепіпеда, побудованого на векторах системи $\{{𝐯}_i\}$, як на ребрах.

Числова стійкість

Коли процес втілено на комп'ютері, вектори ${𝐮}_k$ часто не точно ортогональні, через похибки заокруглювання. Для процесу Грама — Шмідта у вигляді описаному вище (іноді згадуваному як «класичний Грам — Шмідт») ця втрата ортогональності особливо шкідлива; кажуть, що (класичний) процес Грама — Шмідта числово нестійкий.

Процес Грама — Шмідта можна стабілізувати завдяки маленькій зміні; цю версію іноді згадують як модифікований Грам — Шмідт. Цей підхід дає той самий результат що й оригінальна формула в точній арифметиці і вводить менші похибки в арифметиці скінченної точності. Замість того, щоб обчислювати вектор u_k як

${𝐮}_k={𝐯}_k-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_k)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐯}_k)-\cdots -{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_{k-1}}({𝐯}_k),$

його обчислюють як

$\begin{array}{cc}{𝐮}_k^{(1)}& ={𝐯}_k-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_k),\\ {𝐮}_k^{(2)}& ={𝐮}_k^{(1)}-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐮}_k^{(1)}),\\ & ⋮\\ {𝐮}_k^{(k-2)}& ={𝐮}_k^{(k-3)}-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_{k-2}}({𝐮}_k^{(k-3)}),\\ {𝐮}_k^{(k-1)}& ={𝐮}_k^{(k-2)}-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_{k-1}}({𝐮}_k^{(k-2)}).\end{array}$

Кожен крок знаходить вектор ${𝐮}_k^{(i)}$ ортогональний до ${𝐮}_k^{(i-1)}$. Таким чином, ${𝐮}_k^{(i)}$ також ортогональний похибкам введеним під час обчислення ${𝐮}_k^{(i-1)}$.

Джерела

• Шаблон:Гантмахер.Теорія матриць
• Шаблон:Гельфанд.Линейная алгебра