Итерационный степенной метод

Среди классических методов, помимо редко используемого на практике метода непосредственного разворачивания векового определителя, для вычисления наибольших по абсолютному значению собственных чисел больших разреженных матриц иногда оказывается полезным так называемый степенной метод, основанный на следующем. Пусть собственные числа матрицы А вещественны и наибольшее по модулю не является кратным. При заданном векторе х₀ формируется последовательность

x_k+1=Ax_k.

Вектор x₀ может быть разложен по направлениям собственных векторов v₁, v₂, …, v_n матрицы А:

x₀=c₁v₁+…+c_nv_n.

Если, например, c¹0, то, учитывая, что A^kv_i=λ^kv_i, получим

x_k= =

=

При k→∞ множители с дробными отношениями в круглых скобках стремятся к нулю, а векторы x_k стремятся по направлению к собственному вектору v₁; их модули будут либо стремится к нулю (если |λ₁|<1), либо к бесконечности (|λ₁|>1). Если текущие значения векторов x_k нормировать по его наибольшей по абсолютному значению – координате σ_k, то σ_k→λ₁ и x_k®c₁v₁ при k®¥.

Другими словами, последовательность {x_k} сходится к вектору, пропорциональному v₁.

Достоинство метода – отсутствие преобразований матрицы А, а главный недостаток – медленная сходимость, особенно при близких значениях первого и второго по величине собственных чисел. При кратном наибольшем собственном числе метод вообще не сходится. Другая проблема возникает при необходимости вычисления следующих после наибольшего собственных чисел – если не блокировать уже найденное значение, то итерации снова будут сходиться к λ₁. Обычно применяемый прием сводится к процедуре сдвига диагональных элементов матрицы А на величину р, тогда

(A–pE)x_i=(l–p)x_i

и соответствующим подбором р можно привести итерации к другому собственному значению. Например, если взять р равным уже найденному наибольшему с обратным знаком, то можно повторной итерацией найти наименьшее по модулю собственное число. Но каждое последующее будет вычисляться все с большей погрешностью.