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

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

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

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

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

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

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

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

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

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

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

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