Сдвиг Уилкинсона в численных методах¶

Сдвиг Уилкинсона — это алгоритмический приём в численных методах линейной алгебры, применяемый при вычислении собственных значений матриц, который заключается в выборе специального сдвига для ускорения сходимости итерационных методов, прежде всего QR-алгоритма. Метод назван в честь британского математика Джеймса Харди Уилкинсона, который предложил его в 1960-х годах для решения проблемы медленной сходимости при наличии близких или комплексных собственных значений.

¶Суть алгоритма

Сдвиг Уилкинсона используется в неявном QR-алгоритме для нахождения собственных значений симметричных и несимметричных матриц. Идея состоит в том, чтобы на каждом шаге итерации сдвигать матрицу на величину, приближённо равную собственному значению, которое находится в правом нижнем углу матрицы. Это позволяет значительно ускорить сходимость к треугольной форме.

Для матрицы порядка n сдвиг вычисляется на основе подматрицы размера 2×2, расположенной в правом нижнем углу текущей матрицы. Пусть a, b, c — элементы этой подматрицы:

`` | a b | | c d | ``

Тогда сдвиг μ выбирается как собственное значение этой подматрицы, которое ближе к элементу d. Формула для вычисления сдвига имеет вид:

μ = d + δ − sign(δ) · √(δ² + b·c)

где δ = (a − d) / 2, а sign(δ) — знак числа δ (при δ = 0 берётся знак «+»).

¶Преимущества перед другими сдвигами

До появления сдвига Уилкинсона в QR-алгоритме использовались более простые стратегии, например, сдвиг на элемент d (правый нижний элемент матрицы) или сдвиг Рэлея. Однако эти подходы имели существенные недостатки:

• Медленная сходимость для матриц с близкими собственными значениями — скорость сходимости могла быть лишь линейной.
• Проблема комплексных собственных значений для вещественных несимметричных матриц — простые вещественные сдвиги не могли эффективно обрабатывать комплексные пары.

Сдвиг Уилкинсона решает обе проблемы. Он обеспечивает кубическую сходимость для симметричных матриц и квадратичную — для несимметричных. Кроме того, он позволяет корректно обрабатывать комплексные собственные значения вещественных матриц, что делает QR-алгоритм универсальным инструментом.

¶Применение в QR-алгоритме

В классическом QR-алгоритме со сдвигом на каждом шаге выполняется QR-разложение матрицы A − μI, после чего матрица обновляется как A = RQ + μI. Сдвиг Уилкинсона встраивается в этот процесс следующим образом:

1. Вычисляется сдвиг μ на основе правой нижней подматрицы 2×2.
2. Выполняется QR-разложение матрицы A − μI.
3. Формируется новая матрица A = RQ + μI.
4. Шаги повторяются до тех пор, пока поддиагональные элементы не станут достаточно малыми.

Особенность сдвига Уилкинсона в том, что он позволяет работать с матрицами, у которых собственные значения образуют комплексно-сопряжённые пары. Для этого используется двойной сдвиг (implicit double shift), при котором на каждом шаге применяются два последовательных сдвига, соответствующих комплексно-сопряжённым значениям. Это позволяет оставаться в области вещественной арифметики и не переходить к комплексным числам.

¶Сходимость и устойчивость

Сдвиг Уилкинсона считается одним из наиболее эффективных практических методов ускорения сходимости. Для симметричных матриц он даёт кубическую сходимость, что означает увеличение числа верных знаков примерно втрое на каждой итерации. Для несимметричных матриц сходимость обычно квадратичная.

Важным свойством является глобальная сходимость для симметричных матриц — алгоритм сходится к собственным значениям независимо от начального приближения. Для несимметричных матриц глобальная сходимость не гарантируется, однако на практике метод работает надёжно для большинства задач.

Сдвиг Уилкинсона также обладает свойством устойчивости к вырожденным случаям: если подматрица 2×2 имеет кратные собственные значения, формула остаётся корректной и не приводит к делению на ноль или другим численным аномалиям.

¶Критика и ограничения

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

Кроме того, для очень больших разреженных матриц QR-алгоритм со сдвигом Уилкинсона неэффективен, поскольку QR-разложение разрушает разреженность. Для таких задач используются другие методы, например, методы Крылова (арнольди, ланцоша) с их собственными стратегиями сдвигов.

¶Источники

• Уилкинсон Дж. Х., Райнш К. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра. — М.: Машиностроение, 1976.
• Голуб Дж., Ван Лоун Ч. Матричные вычисления. — М.: Мир, 1999.
• Уилкинсон Дж. Х. Алгебраическая проблема собственных значений. — М.: Наука, 1970.