Участник:Grinch96/QR-факторизация методом Грама-Шмидта с последующей реортогонализацией: различия между версиями
Grinch96 (обсуждение | вклад) |
Grinch96 (обсуждение | вклад) |
||
| Строка 36: | Строка 36: | ||
Здесь <math>q_{i}, \, a_{i} </math> столбцы матриц <math> Q, \, A </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}|| > k</math>, запускается процесс реортогонализации. <math>k</math> произвольная и задает точность ортогональности матрицы <math>Q</math>. В посвященной методу реортогонализации статье <ref>Luc Giraud and Jilien Langou. A robust criterion for the modified Gram–Schmidt algorithm with selective reorthogonalization // Society for Industrial and Applied Mathematic, 2003.</ref> <math>k</math> рекомендуется брать равным <math>10</math>, однако приводятся примеры алгоритмов, где <math>k=\sqrt{2}</math> или <math>k=\sqrt{5}</math>. Мы исследуем <math>k=10</math>. | + | На <math>m</math>-ом шаге получаем <math>p_{m} \in \mathbb{R}^{n}</math>. Если <math>||a_{m}||_{2}/||p_{m}||_{2} > k</math>, запускается процесс реортогонализации. <math>k</math> произвольная и задает точность ортогональности матрицы <math>Q</math>. В посвященной методу реортогонализации статье <ref>Luc Giraud and Jilien Langou. A robust criterion for the modified Gram–Schmidt algorithm with selective reorthogonalization // Society for Industrial and Applied Mathematic, 2003.</ref> <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>p_{m}</math> на <math>m</math>-оm шаге алгоритма повторно. Более формально: | ||
Версия 19:41, 25 ноября 2017
| 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 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 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 Литература
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}, \quad j = 1, \ldots , n\\ & r_{ij} = q_{i}^{T} a_{j}. \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}_{j} = q_{j} - \sum_{i=1}^{j-1} q_{i} (q_{i}^{T} p_{j}), \\ & q_{j} = \tilde{p}_{j} / ||\tilde{p}_{j}||_{2}, \quad j = 1, \ldots , m \\ & \tilde{r}_{ij} = \tilde{q}_{i}^{T} \tilde{q}_{j}. \\ & r_{ij} = \tilde{r}_{ij} + r_{ij}^{0} \end{align} [/math]
Здесь [math]\tilde{q}_{i}[/math] столбцы матриц [math] \tilde{Q}_{m}[/math], [math]r_{ij}^{0}[/math] - элемент матриц [math]R[/math], вычисленный до реортогонализации.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро алгоритма состоит из вычисления:
- [math]\dfrac{n(n+1)}{2}[/math] скалярных произведений векторов, включая вычисление длины вектора;
- [math]\dfrac{(n-1)n}{2}[/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 \>
[[Категория:]]
[[Категория:]]
- ↑ Тыртышников Е.Е. Методы численного анализа // М.: 2006. 83 с.
- ↑ 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.
- ↑ Luc Giraud and Jilien Langou. A robust criterion for the modified Gram–Schmidt algorithm with selective reorthogonalization // Society for Industrial and Applied Mathematic, 2003.
