Уровень алгоритма

Участник:Grinch96/QR-факторизация методом Грама-Шмидта с последующей реортогонализацией

Материал из Алговики
Перейти к навигации Перейти к поиску


QR-факторизация
Последовательный алгоритм
Последовательная сложность [math]O(n^3)[/math]
Объём входных данных [math]n^2[/math]
Объём выходных данных [math]2\cdot n^2[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]O(n)[/math]
Ширина ярусно-параллельной формы [math]O(n^2)[/math]


Автор: Г. А. Балыбердин

1 Свойства и структура алгоритма

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

Пусть [math]A = (a_1, ..., a_n)[/math] - вещественная матрица [math]n × n[/math], определитель которой не равен [math]0[/math]. Во многих приложениях требуется решать линейную систему [math]Ax=b[/math] c плохо-обусловленной матрицей [math]A[/math]. При решении данной задачи, чтобы не увеличивать число обусловленности матрицы [math]A[/math], ее можно представить в виде [math]A=QR[/math], где матрица [math]Q \in \mathbb{R}^{n×n}[/math] состоит из ортонормированных строк, а матрица [math] R \in \mathbb{R}^{n×n}[/math] является верхнетреугольной. В итоге мы получаем так называемую [math]QR[/math]-факторизацию.

Чтобы построить [math]QR[/math]-факторизацию можно воспользоваться процессом ортогонализации Грама-Шмидта[1], однако в условиях машинной арифметики, матрица [math]Q[/math] может получиться далекой от ортогональной.Чтобы этого избежать, на определенных итерациях нужно проводить процесс реортогонализации [2].

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

Исходные данные: квадратная матрица [math]A[/math] порядка [math]n[/math] (элементы [math]a_{ij}[/math]), определитель которой не равен [math]0[/math].

Вычисляемые данные: верхнетреугольная матрица [math]R[/math] порядка [math]n[/math] (элементы [math]r_{ij}[/math]), унитарная матрица [math]Q[/math] порядка [math]n[/math] (элементы [math]q_{ij}[/math]); выполняется соотношение [math]QR=A[/math].

Формулы процесса ортогонализации:

[math] \begin{align} & p_{j} = a_{j} - \sum_{i=1}^{j-1} q_{i} (q_{i}^{T} a_{j}), \\ & q_{j} = p_{j} / ||p_{j}||_{2}, \\ & r_{ij} = q_{i}^{T} a_{j},\quad j = 1, \ldots , i - 1.\\ \end{align} [/math]

Здесь [math]q_{i}, \, a_{i} [/math] столбцы матриц [math] Q, \, A [/math] соответственно.

На [math]m[/math]-ом шаге получаем [math]p_{m} \in \mathbb{R}^{n}[/math]. Если [math]||a_{m}||_{2}/||p_{m}||_{2} \gt k[/math], запускается процесс реортогонализации. [math]k[/math] произвольная и задает точность ортогональности матрицы [math]Q[/math]. В посвященной методу реортогонализации статье [3] [math]k[/math] рекомендуется брать равным [math]10[/math], однако приводятся примеры алгоритмов, где [math]k=\sqrt{2}[/math] или [math]k=\sqrt{5}[/math]. Мы исследуем [math]k=10[/math].

Суть процесса реортогонализации - это процесс ортогонализации Грама-Шмидта, примененный повторно к вектору [math]p_{m}[/math] на [math]m[/math]-оm шаге алгоритма. Более формально:

[math] \begin{align} & \tilde{p}_{m} = p_{j} - \sum_{i=1}^{m-1} q_{i} (q_{i}^{T} p_{m}), \\ & q_{m} = \tilde{p}_{m} / ||\tilde{p}_{m}||_{2}, \\ & \tilde{r}_{mj} = q_{j}^{T} p_{m}, \quad j = 1, \ldots , m - 1, \\ & r_{mj} = \tilde{r}_{mj} + r_{mj}^{0}, \quad j = 1, \ldots , m - 1, \\ & r_{mm} = ||\tilde{p}_{m}||_{2}. \end{align} [/math]

Здесь [math]\tilde{q}_{i}[/math] столбцы матриц [math] \tilde{Q}_{m}[/math], [math]r_{mj}^{0}[/math] - элементы матрицы [math]R[/math], вычисленные до реортогонализации.

1.3 Вычислительное ядро алгоритма

Вычислительное ядро алгоритма, если не требуется реортогонализация, состоит из вычисления:

  • [math]\dfrac{n(n+1)}{2}[/math] скалярных произведений векторов, включая вычисление длины вектора;
  • [math]\dfrac{(n-1)n}{2}[/math] умножений векторов на число.

На каждом шаге реортогонализации добавляется [math] j-1 [/math] вычислений скалярных произведений векторов на число и столько же умножений вектора на число. Здесь реортогонализация производится на [math]j[/math]-ом шаге. Однако сколько раз алгоритм будет реортогонализовывать вектора зависит от свойств матрицы.

1.4 Макроструктура алгоритма

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

1.6 Последовательная сложность алгоритма

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

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

<references \>

[[Категория:]]

[[Категория:]]

  1. Тыртышников Е.Е. Методы численного анализа // М.: 2006. 83 с.
  2. Luc Giraud, Julien Langou, Miroslav Rozložník, Jasper van den Eshof. Rounding error analysis of the classical Gram-Schmidt orthogonalization process // Springer-Verlag, 2005.
  3. Luc Giraud and Jilien Langou. A robust criterion for the modified Gram–Schmidt algorithm with selective reorthogonalization // Society for Industrial and Applied Mathematic, 2003.