Участник:Pandvik/Ортогонализация Грама - Шмидта

Авторы описания алгоритма: Павлов Андрей, Филимонов Владимир.

1 ЧАСТЬ. Свойства и структура алгоритмов

1.1 Общее описание алгоритма

В конечномерном евклидовом пространстве существует ортонормированный базис. Для доказательства этого факта требуется находить и строить такие базисы. Построить ортонормированный базис можно, отталкиваясь от некоторого исходного базиса, при помощи алгоритма, который называют процессом ортогонализации Грама — Шмидта. Процесс ортогонализации Грама-Шмидта используется для квадратных матриц, которые преобразуются, либо уже преобразованы, к верхнему(нижнему) треугольному виду. Процесс ортогонализации Грама-Шмидта нашёл применение в оптимизации оценивания параметров моделей управления объектом, в протоколах безопасности, в обработке сигналов, в вычислении локальных минимумов целочисленных решёток и многом другом. Обычно, процесс ортогонализации используется как промежуточный шаг в других алгоритмах для уменьшения количества вычислений.

1.2 Математическое описание алгоритма

Исходные данные: квадратная матрица A с линейно независимыми векторами $\mathbf{a}_1,...,\mathbf{a}_N$.

Определяется оператор проекции $\mathbf{proj}_b a = \frac{\left \langle a,b \right \rangle}{\left \langle b,b \right \rangle }b$, где $\left \langle a,b \right \rangle$ - скалярное произведение векторов a и b. Данный оператор используется для проецирования вектора a коллинеарно вектору b.

$\mathbf{b}_1 = \mathbf{a}_1$

$\mathbf{b}_2 = \mathbf{a}_2 - \mathbf{proj}_{\mathbf{b}_1} \mathbf{a}_2$

$\mathbf{b}_3 = \mathbf{a}_3 - \mathbf{proj}_{\mathbf{b}_1} \mathbf{a}_3 - \mathbf{proj}_{\mathbf{b}_2} \mathbf{a}_3$

$\mathbf{b}_4 = \mathbf{a}_4 - \mathbf{proj}_{\mathbf{b}_1} \mathbf{a}_4 - \mathbf{proj}_{\mathbf{b}_2} \mathbf{a}_4 - \mathbf{proj}_{\mathbf{b}_3} \mathbf{a}_4$

$\vdots$

$\mathbf{b}_N = \mathbf{a}_N - \sum_{j=1}^{N-1} \mathbf{proj}_{\mathbf{b}_j} \mathbf{a}_N$

На основе каждого вектора $\mathbf{b}_j (j = 1 \cdots N)$ может быть получен нормированный вектор $\mathbf{e}_j = \frac{\mathbf{b}_j}{||\mathbf{b}_j||}$.

Результаты процесса ортогонализации Грама-Шмидта: $\mathbf{b}_1\cdots\mathbf{b}_N$ - система ортогональных векторов либо система ортонормированных векторов $\mathbf{e}_1\cdots\mathbf{e}_N$.

1.5 Схема реализации последовательного алгоритма

1. $\mathbf{b}_1 = \mathbf{a}_1$

2. $\mathbf{b}_i = \mathbf{a}_i - \sum_{j=1}^{i-1} \mathbf{proj}_{\mathbf{b}_{i-1}} \mathbf{a}_i$ $(i = 2 \cdots N)$, для каждого $\mathbf{proj}_b a$ выполняется $\frac{\left \langle a,b \right \rangle}{\left \langle b,b \right \rangle}b$.

1.7 Информационный граф

Опишем информационный граф алгоритма.

Для вычисления $b_i$ требуется найти $proj_{b_{j}}a_{i}$ для всех $j \in [1, i]$. Следовательно для полного вычисления вектора $b_{i}$ требуется знать все $b_{j}$ с меньшим индексом. Такая зависимость по данным очень не удачна для параллелизма. Однако, если разбить процесс вычисления $b_{i}$ на несколько этапов, соответствующих функциям проекции ($proj_{b_{j}}a_{i}$), то это позволит производить некоторые предварительные вычисления для $b_{j}$ до момента, когда станут известны все предшествующие ей $b_{i}$.

На Рис. 1 изображена зависимость каждого из этапов от предыдущих вычислений. Первая строка овалов содержит все проекции, зависящие от $b_{1}$, вторая строка - все проекции, зависящие от $b_{2}$, $\;\cdots\;$ самая верхняя строка содержит проекцию, которая зависит от $b_{N-1}$.

Рис. 2 показывает зависимость по данным немного в другом формате. Каждая строка представляет собой набор данных, которые требуются для вычисления $b_{i}$ из первого столбца. Второй и последующие столбцы группируют проекции, зависящие от одной из $b_{i}$ и, с помощью стрелки, показывают эту зависимость.

Рис. 1. Информационный граф алгоритма Грама-Шмидта

Рис. 2. Информационный граф алгоритма Грама-Шмидта