Два представления о сходимости QR-, QL-алгоритмов
Рассмотрим вопрос о сходимости -алгоритма. Если сдвиги не используются, то -алгоритм называется основным.
Вообще с , -алгоритмами связаны два представления о сходимости. Строго говоря, сходимость , -алгоритмов нужно понимать как сходимость матричной последовательности . В общем случае можно показать, что такая последовательность сходится к диагональной матрице, на диагонали которой находятся собственные значения исходной матрицы (симметричной). Если - несимметричная матрица, то матричная последовательность сходится к блочно-диагональной матрице, каждый диагональный блок которой отвечает собственному значению.
Однако можно понимать сходимость несколько иначе.
Теорема (случай симметричной матрицы). Пусть собственные значения матрицы удовлетворяют условию:
.
Пусть матричная последовательность получена основным -алгоритмом, тогда имеет место равенство:
,
где .
В соответствии с приведенной теоремой сходимость понимается как стремление к 0 внедиагональных элементов первого столбца матрицы. На практике как только становится малой, это означает, что элемент можно рассматривать как приближенное значение собственного значения . После этого, если не является кратным, итерационный процесс можно продолжить для матрицы размера , отбросив первую строку и первый столбец, и т.д.
Дата добавления: 2015-03-20; просмотров: 511;