|
Метод Якоби состоит из цепочки ортогональных преобразований подобия матрицы. Каждое преобразование (ротация Якоби) -- это плоский поворот с целью обнуления одного из внедиагональных элементов матрицы. Последовательные преобразования не сохраняют уже установленные нулевые элементы, но вместе с тем внедиагональные элементы становятся меньше и меньше до тех пор, пока матрица не станет диагональной с точностью до машинного нуля. Накопление в процессе преобразований произведения трансформационных матриц дает матрицу собственных векторов, в то время как диагональные элементы являются собственными значениями.
Метод Якоби всегда является робустным для действительных симметричных матриц. Для матриц размера, скажем больше 10, этот алгоритм более медленный, чем метод QR (см. ниже). Однако алгоритм Якоби значительно проще других более эффективных методов, таким образом он рекомендуется в случаях, когда время выполнения не является критическим.
Базовая матрица ротации Якоби имеет вид:
Ppq = (1 )
( … )
( c…s )
( …1… )
( -s…c )
( … )
( 1)
Все диагональные элементы матрицы ротации Якоби равны 1, за исключением двух элементов в строках (и столбцах) p и q. Все внедиагональные элементы равны нулю, за исключением двух элементов, равных s и (-s). Числа c и s являются косинусом и синусом угла поворота f, так что c2+s2=1.
Ротация Якоби преобразует матрицу A согласно формуле:
A' = PpqTAPpq.
Произведение PpqTA изменяет только строки p и q матрицы A, в то время как APpq меняет только столбцы p и q. Отметим, что нижние индексы p и q в обозначении Ppq не означают элемент этой матрицы, а скорее индексируют тип ротации, т.е. плоскость, в которой она происходит. Таким образом, измененные элементы в матрице A' расположены только в строках и столбцах p и q:
( ... a'1p ... a'1q ... )
(… ... ... ... )
(a'p1 ... a'pp ... a'pq ... a'pn)
A' =( ... ... ... ... )
(a'q1 ... a'qp ... a'qq ... a'qn)
(… ... ... ... )
( ... a'np … a'nq ... )
Для измененных элементов матрицы (с учетом приведенного выше и ее симметрии) получаются явные формулы:
a'rp = carp - sarq (r!=p, r!=q)
a'rq = carq + sarp (r!=p, r!=q)
a'pp = c2app + s2aqq - 2csapq
a'qq = s2app + c2aqq + 2csapq
a'pq = (c2 - s2)apq + cs(app- aqq)
Идея метода Якоби в том, чтобы постараться обнулить внедиагональные элементы серией ротаций. Для того, чтобы обнулилось a'pq, угол ротации, согласно формулам, приведенным выше, должен быть следующим:
q = cot(2f) = (c2 - s2)/(2cs) = (aqq- app)/(2apq).
Полагая t=s/c, для определения t прийдем к следующему уравнению:
t2 + 2tq - 1 = 0.
Меньший по модулю корень этого уравнения соответствует вращению на угол, меньший p/4; выбор этого угла на каждой из стадий дает наиболее устойчивый алгоритм. Используя формулу для решения квадратного уравнения с дискриминантом в знаменателе, меньший корень определяется как:
t = sign(q)/(|q|+sqrt(q2+1)).
Если величина q такова, что q2 даст переполнение, полагаем t = 1/(2q). По значению t определяются c и s:
c = 1/sqrt(t2+1), s = tc.
При численной модификации элементов матрицы мы стремимся к уменьшению ошибки округления. Идея состоит в том, чтобы переписать их как прежнее значение плюс малая корректирующая добавка. В этом случае коэффициенты матрицы после преобразования будут выглядеть как:
a'pp = app - tapq
a'rp = arp - s(arq + garp)
a'rq = arq + s(arp - garq) ,
где t (тангенс половины угла поворота) определяется, как t = s/(1+c).
Сходимость метода Якоби можно оценить, рассматривая сумму квадратов внедиагональных элементов S; уравнения преобразований дают для этой суммы после трансформации следующее соотношение:
S = Sr!=s(|ars|2); S' = S - 2|apq|2.
Поскольку преобразования ортогональные, сумма диагональных элементов при этом возрастает соответственно на |apq|2. Сумма же квадратов внедиагональных элементов монотонно убывает. Поскольку она ограничена снизу нулем и поскольку мы можем каждый раз выбирать какой хотим элемент apq для обнуления, сумма будет стремиться к нулю.
После цепочки преобразований получается матрица D, диагональная с точностью до машинного нуля. Ее диагональные элементы образуют собственные значения первоначальной матрицы A, поскольку выполняется
Do'stlaringiz bilan baham: |
