Сингулярное разложение двухдиагональной матрицы

Следуя [17], изложим алгоритм сингулярного разложения двухдиагональной матрицы. С помощью так называемого QR-метода можно привести двухдиагональную матрицу J⁽⁰⁾ к диагональной форме D, так что выполняется последовательность преобразований

(4.3.1.IV)

где S⁽ⁱ⁾ и T⁽ⁱ⁾ — ортогональные матрицы, которые выбирают так, чтобы J⁽ⁱ⁺¹⁾ сохраняли свою двухдиагональную форму, а симметричная трехдиагональная матрица J⁽ⁱ⁾^TJ⁽ⁱ⁾ стремилась к диагональному виду.

Для удобства опустим индексы и введем следующие обозначения:

Переход осуществляется с помощью последовательности преобразований вращения. Таким образом,

. (4.3.1.V)

Здесь S_k и T_k — элементарные матрицы вращения вида

причем Для общего случая коэффициенты c и s вычисляются по формулам Гивенса

где a_i_,_j — вытесняемый элемент.

Очевидно, что умножение справа на матрицу вращения изменяет лишь (k-1) и k столбцы матрицы, а умножение слева на матрицу вращения — лишь (k-1) и k строки. Формулы преобразования для столбцов имеют вид

для строк

Коэффициенты c₂, s₂ матрицы T₂ оставим пока неопределенными, в то время как остальные коэффициенты c_k, s_k будем выбирать так, чтобы матрица имела ту же форму, что и J. Следовательно, матрица T₂ не аннулирует ни одного элемента, но добавляет элемент J₂₁, матрица S₂ аннулирует J₂₁, но добавляет J₁₃, матрица T₃ аннулирует J₁₃, но добавляет J₃₂и т. д. и окончательно матрица аннулирует J_n_,_n_-1 и ничего не добавляет.

При этом справедливы следующие соотношения:

Таким образом, ортогональное преобразование (4.3.1.V) эквивалентно преобразованию подобия симметричной трехдиагональной матрицы

(4.3.1.VI)

где матрица будет также трехдиагональной, поэтому матрицу T₂, которая пока еще не определена, необходимо выбирать так, чтобы преобразование было QR-преобразованием со сдвигом, равным s.

Обычно QR-алгоритм можно записать в следующем виде:

(4.3.1.VII)

где — верхняя треугольная матрица. Но не обязательно выполнять вычисления по формулам (4.3.1.VII). Сдвиг можно осуществлять и неявным образом. Доказано, например, в работе [17], что определенным выбором T₂ можно добиться того, чтобы преобразование (4.3.1.VI) было эквивалентно QR-преобразованию для M с заданным сдвигом s.

Пусть T и T_s ортогональные матрицы такие, что выполняются следующие условия:

то есть элементы первого столбца T_s равны элементам первого столбца T и

Тогда, если поддиагональные элементы матрицы M ненулевые, то матрица связана с следующим образом:

где D — диагональная матрица, элементы которой равны ±1.

Следовательно, задача заключается лишь в том, чтобы первый столбец матрицы T выбрать равным первому столбцу матрицы T_s. Далее, имеем

Учитывая тот факт, что обратная матрица к верхней треугольной будет также верхней треугольной, можно сделать вывод, что первый столбец искомой матрицы T_s будет пропорционален первому столбцу матрицы M — sE.

Таким образом, матрица T будет матрицей QR-преобразования со сдвигом s, если ее первый столбец будет пропорционален первому столбцу матрицы M — sE. А так как T = T₂T₃…T_n, окончательно приходим к выводу, что T₂ в (4.3.1.V) необходимо выбирать так, чтобы ее первый столбец был пропорционален первому столбцу M — sE. В этом случае преобразование (4.3.1.V) будет эквивалентно QR-преобразованию со сдвигом s для матрицы M. Параметр сдвига s выбирается равным собственному значению нижнего минора матрицы M,