Шукати в цьому блозі

понеділок, 15 лютого 2016 р.

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


Матеріал з Вікіпедії — вільної енциклопедії.
Процес ортогоналізації Грама — Шмідта на трьох лінійно незалежних, неортогональних векторах
Процес Грама - Шмідта — найвідоміший алгоритм ортогоналізації, в якому за лінійно-незалежною системою \mathbf{v}_1, \mathbf{v}_2,\dots,\mathbf{v}_k будується ортогональна система \mathbf{u}_1,\mathbf{u}_2,\dots,\mathbf{u}_k така, що кожний вектор \mathbf{u}_i лінійно виражається через \mathbf{v}_1,\mathbf{v}_2,\dots,\mathbf{v}_i, тобто матриця переходу від \{\mathbf{v}_i\} до \{\mathbf{u}_i\} ― верхня трикутна матриця.
Можна пронормувати систему \{\mathbf{u}_i\} і зробити, щоб діагональні елементи матриці переходу були додатніми; ці умови однозначно визначають систему\{\mathbf{u}_i\} та матрицю переходу.
Процес Грама — Шмідта застосований до матриці з лінійно-незалежними стовпцями є QR розкладом матриці (розклад на ортогональну і верхню трикутну матрицю з додатніми діагональними елементами).

Алгоритм

Перші 2 кроки ортогоналізації
Визначимо ортогонально-проекційний оператор
\mathrm{proj}_{\mathbf{u}}\,\mathbf{v} = {\langle \mathbf{u,v} \rangle \over \langle \mathbf{u,u} \rangle} \mathbf{u} = {\mathbf{u u^{\top}} \over \langle \mathbf{u,u} \rangle} \cdot \mathbf{v} = \mathbf{e e^{\top}} \cdot \mathbf{v}, \qquad \mathbf{e} = {\mathbf{u} \over \| \mathbf{u} \|},
де <u, v> означає скалярний добуток векторів u and v. Цей оператор проектує вектор v ортогонально на вектор u.
Приймемо \mathbf{u}_1=\mathbf{v}_1 та запишемо рекурсивну формулу
\mathbf{u}_i = \mathbf{v}_i-\sum_{j=1}^{i-1}\frac{\langle \mathbf{v}_i,\mathbf{u}_j\rangle}{\langle \mathbf{u}_j,\mathbf{u}_j\rangle} \mathbf{u}_j =\mathbf{v}_i- \bigg( \sum_{j=1}^{i-1} \mathbf{e}_j \mathbf{e}_j^{\top} \bigg) \mathbf{v}_i.
Нормуючи вектори \mathbf{u}_i, отримаємо ортонормовану систему о\{\mathbf{e}_i\}.
Геометричний зміст процесу в тому, що вектор \mathbf{u}_i є проекцією вектора \mathbf{v}_i на перпендикуляр до лінійної оболонки векторов \mathbf{v}_1,\dots,\mathbf{v}_{i-1}.

Властивості

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

Немає коментарів:

Дописати коментар

Примітка: лише член цього блогу може опублікувати коментар.

Підписатися на: Дописати коментарі (Atom)