Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант)

1 Описание свойств и структуры алгоритма

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

Метод Гивенса (в советской математической литературе называется также методом вращений) используется для разложения матриц в виде [math]A = QR[/math] ([math]Q[/math] - унитарная, [math]R[/math] — правая треугольная матрица). При этом матрица [math]Q[/math] хранится и используется не в своём явном виде, а в виде произведения матриц вращения. Каждая из матриц вращения может быть определена её индексами и одним параметром. Это позволяет в классическом исполнении метода Гивенса хранить результаты разложения на месте матрицы [math]A[/math] без использования дополнительных массивов. [math]QR[/math]-разложение матрицы [math]A[/math] может быть использовано в разных целях: как для решения СЛАУ вида [math]Ax = b[/math], так и в качестве одного из шагов так называемого [math]QR[/math]-алгоритма нахождения собственных чисел матрицы.

На каждом шаге алгоритма две строки преобразуемой матрицы подвергаются преобразованию вращения. При этом параметр такого преобразования подбирается так, чтобы один из поддиагональных элементов преобразуемой матрицы стал нулевым. Сначала в 0 последовательно обращаются элементы 1-го столбца, затем 2-го, и т.д. до n-1-го, после чего получившаяся матрица - это и есть матрица [math]R[/math]. Сам шаг алгоритма распадается на две части: подбор параметра вращения и выполнение вращения над двумя строками матрицы. Поскольку слева от "рабочего" столбца элементы вращаемых строк равны 0, то там выполнять вращение не нужно. Вращение элементов строк в текущем столбце выполняется одновременно с подбором параметра вращения. Таким образом, вторая часть шага алгоритма заключается в выполнении вращения двумерных векторов, составленных из элементов вращаемых строк в столбцах справа от "рабочего". Каждое такое вращение эквивалентно перемножению двух комплексных чисел (или в сумме 4 умножениям, 1 сложению и 1 вычитанию действительных), одно из которых имеет модуль 1. Подбор параметра вращения по двум элементам "рабочего" столбца является более сложной операцией, что связано в том числе и с необходимостью минимизации влияния ошибок округления. Обычно для хранения матрицы вращения используется тангенс половинного угла [math]t[/math], с которым простыми формулами (т.н. "боевыми формулами тригонометрии") связаны косинус [math]c[/math] и синус [math]s[/math] самого угла:

[math]c = (1 - t^2)/(1 + t^2), s = 2t/(1 + t^2)[/math]

Именно [math]t[/math] обычно и хранится в соответствующем элементе массива.

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

Граф алгоритма без отображения входных и выходных данных. n=4. F1 - операция вычисления параметров поворота, F2 - выполнение поворота 2-мерного вектора (эквивалентно операции умножения двух комплексных чисел).

Внутренний граф вершин F2 с входными и выходными параметрами

3 Литература

1. В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.