User:GrishinaAnna/Метод Якоби вычисления сингулярных чисел и векторов
Свойства и структура алгоритма
Общее описание алгоритма
Метод Якоби позволяет получить разложение произвольной матрицы [math]\displaystyle{ G }[/math] размера [math]\displaystyle{ n }[/math]×[math]\displaystyle{ n }[/math] в виде [math]\displaystyle{ G=USV^* }[/math], где [math]\displaystyle{ U }[/math] и [math]\displaystyle{ V }[/math] — унитарные матрицы, [math]\displaystyle{ S }[/math] — диагональная матрица с вещественными положительными числами на диагонали. Диагональные элементы матрицы называются сингулярными числами матрицы [math]\displaystyle{ G }[/math], а столбцы матриц и левыми и правыми сингулярными векторами соответственно.
В основе метода лежит утверждение о том, что собственными значениями симметричной матрицы [math]\displaystyle{ G^TG }[/math] являются квадраты сингулярных чисел, а соответствующие ортонормированные собственные векторы – правыми сингулярными векторами. Для вычисления собственных значений и собственных векторов симметричной матрицы [math]\displaystyle{ G^TG }[/math] используется метод односторонних вращений (неявный метод Якоби), на каждом шаге которого вычисляется вращение Якоби [math]\displaystyle{ J }[/math]. С его помощью матрица [math]\displaystyle{ G^TG }[/math] неявно пересчитывается в [math]\displaystyle{ J^TG^TGJ }[/math]. Вращение выбрано так, чтобы пара внедиагональных элементов из [math]\displaystyle{ G^TG }[/math] обратилась в нуль в матрице [math]\displaystyle{ J^TG^TGJ }[/math]. Однако, ни [math]\displaystyle{ G^TG }[/math], ни [math]\displaystyle{ J^TG^TGJ }[/math] не вычисляются в явном виде; вместо них вычисляется матрица [math]\displaystyle{ GJ }[/math], которая подается на вход на следующем шаге алгоритма. Алгоритм выполняется, пока [math]\displaystyle{ G^TG }[/math] не станет достаточно близка к диагональной матрице, после чего вычисляются собственные числа матрицы [math]\displaystyle{ G }[/math], полученной на последнем шаге, которые принимаются за сингулярные числа. Правые сингулярные векторы получаются в результате накопления произведений вращений Якоби.
Метод Якоби для вычисления сингулярных значений и векторов является самым медленным из имеющихся, но тем не менее, интерес к нему сохраняется, потому что для некоторых типов матриц [math]\displaystyle{ G }[/math] он способен вычислять числа и сингулярные векторы намного точнее, чем другие методы. Так, например, метод Якоби вычисляет сингулярные числа матрицы [math]\displaystyle{ G }[/math] с высокой точностью, если [math]\displaystyle{ G }[/math] может быть представлена в виде [math]\displaystyle{ G=DX }[/math], где [math]\displaystyle{ D }[/math] – диагональная матрица, а [math]\displaystyle{ X }[/math] – хорошо обусловлена. Выигрыш метода Якоби в этом случае перед другими алгоритмами объясняется следующим образом: в методе Якоби заданная матрица обрабатывается без предварительного приведения к двухдиагональному виду, в то время как другие алгоритмы включают в себя приведение матрицы к двухдиагональной форме, из-за чего и теряют все верные разряды во всех сингулярных числах, кроме старшего.
Следует иметь в виду, что метод Якоби эффективен при не очень больших размерах матрицы – максимум до [math]\displaystyle{ n }[/math] ~ [math]\displaystyle{ 100 }[/math]. Дело не только в том, что метод не будет сходиться за конечное время, дело еще и в излишне большом количестве операций, которое приведет к ошибкам округления и потере точности.
Математическое описание алгоритма
Исходные данные: матрица [math]\displaystyle{ G }[/math] размера [math]\displaystyle{ n }[/math]×[math]\displaystyle{ n }[/math]. Вычисляемые данные: Матрица [math]\displaystyle{ S=\sigma_{i} }[/math], где [math]\displaystyle{ \sigma_{i} }[/math] - сингулярные числа, матрица [math]\displaystyle{ U }[/math] левых сингулярных векторов и матрица [math]\displaystyle{ V }[/math] правых сингулярных векторов. Описание используемой в алгоритме процедуры одностороннего вращения входной матрицы G One-Sided-Jacobi-Rotation (G, j, k):
Вычисляемые данные: Матрица S = diag(σi ), где σi - сингулярные числа, матрица U левых сингулярных векторов и матрица V правых сингулярных векторов. Описание используемой в алгоритме процедуры одностороннего вращения входной матрицы G One-Sided-Jacobi-Rotation (G, j, k):