Участник: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]-факторизацию можно воспользоваться процессом ортогонализации Грама-Шмидта, однако в условиях машинной арифметики, матрица [math]Q[/math] может получиться далекой от ортогональной.Чтобы этого избежать, на определенных итерациях нужно проводить процесс реортогонализации .

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]\tilde{Q}_{m} \in \mathbb{R}^{n × m}[/math]. Если [math]||\tilde{Q}_{m}^{T} \tilde{Q}_{m} - I|| \gt k[/math], запускается процесс реортогонализации. [math]k[/math] произвольная и задает точность ортогональности матрицы [math]Q[/math]. В посвященной методу реортогонализации статье [math]k[/math] рекомендуется брать равным корню из машинной точности.

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

[math] \begin{align} & \tilde{p}_{j} = \tilde{q}_{j} - \sum_{i=1}^{j-1} \tilde{q}_{i} (\tilde{q}_{i}^{T} \tilde{q}_{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] умножений векторов на число.

3 Литература

<references \>

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

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