Использование сдвига для улучшения сходимости
Лекция 11 Степенной метод и метод Якоби
Степенной метод
Обоснование степенного метода
В случае симметричной матрицы все ее собственные значения вещественны, и этим собственным значениям соответствуют линейно независимых собственных векторов . Система векторов образует базис в пространстве размерности , иными словами, любой вектор размерности можно представить в виде разложения по . Недоверчивые могут найти доказательство этих утверждений в книге [11.1]. Здесь и в дальнейшем будем нумеровать собственные значения в порядке возрастания . (11.1) Возьмем произвольный вектор размерности . Хотя собственные вектора матрицы нам еще не известны, мы знаем, что можно представить в виде линейной комбинации собственных векторов: . (11.2) Вычислим вектор : . (11.3) Здесь было использовано определение собственного вектора: . Повторяя эту операцию раз, получаем . (11.4) Согласно принятой нумерации (11.1), максимальным из собственных значений будет . Поэтому в конце концов последнее слагаемое (11.4) должно намного превзойти все остальные, и в пределе должно совпасть по направлению с -м собственным вектором, а отношение длин векторов -го и -го приближений стремится к наибольшему собственному значению: . (11.5) Единственное замечание, которое осталось сделать перед тем, как перейти к практическому применению степенного метода: вектор следует каким-либо образом нормировать после каждого шага. Иначе этот вектор очень быстро вырастет до совершенно неприличных размеров. Например, можно очередное приближение вычислять следующим образом: , (11.6) где – значение первой компоненты произведения . Кстати, в этом случае последовательность значений должна сходиться к .
Пример. Найдем степенным методом максимальное собственное значение и соответствующий собственный вектор матрицы: . Примем в качестве начального вектора и выполним несколько приближений: Как видим, результаты неуклонно приближаются к точному решению: . Точное решение этого примера получено на предыдущей лекции.
Замечание. Сходимость степенного метода может быть медленной, когда , или даже вообще отсутствовать (так как возможно ). Поэтому на практике степенной метод обычно применяют, используя для итераций не один, а несколько ортогональных векторов: (11.7) После каждой итерации ортогональность векторов, естественно, нарушается. Поэтому перед очередным приближением полученные вектора ортогонализируют по методу Грама ‑ Шмидта. Помимо улучшения сходимости такой подход позволяет вычислить не одно, а несколько пар собственных значений и собственных векторов. Обратный степенной метод
Применяя степенной метод, мы получаем наибольшее собственное значение и соответствующий собственный вектор . В задачах механики, как правило, наиболее интересны минимальные собственные значения . Так, в задачах о собственных колебаниях конструкции обычно практический интерес представляют несколько низших частот собственных колебаний. В таких случаях удобнее использовать обратный степенной метод. Метод называется так потому, что итерации, аналогичные (11.6), выполняются не с самой исследуемой матрицей , а с обратной к ней матрицей : . (11.8) Здесь используется тот факт, что матрица имеет те же самые собственные вектора, что и матрица , а соответствующие собственные значения являются величинами, обратными собственным значениям : . В самом деле, пусть и – собственная пара матрицы . (11.9) Тогда, умножая (11.9) слева на , получаем . (11.10) Таким образом, в результате использования итераций (11.8), мы должны получить максимальное собственное значение матрицы и соответствующий собственный вектор , а, значит, и минимальное собственное значение матрицы с тем же собственным вектором .
Следует заметить, что обратный степенной метод вовсе не требует, как может показаться на первый взгляд, трудоемкого обращения матрицы. Выражение (11.8) можно переписать таким образом: (11.11) Следовательно, для получения очередного приближения надо только решить систему линейных уравнений (11.11) одним из методов, рассмотренных в первой части. Если, например, используется метод Холецкого: , (11.12) треугольное разложение матрицы достаточно выполнить только один раз. Тогда на каждой очередной итерации требуется только решить две треугольные системы.
Пример. Попробуем применить обратный степенной метод крассмотренной в разд. 6.1 матрице . Напомним, что в предыдущей лекции было получено точное решение: ; . Нетрудно убедиться, что , тогда, приняв в качестве начального приближения , получим ; ; .
Использование сдвига для улучшения сходимости
Так же, как и прямой степенной, обратный степенной метод может оказаться медленно сходящимся. Напомним (см формулу (11.2)), что вектор , принятый как начальный, можно представить как линейную комбинацию собственных векторов исследуемой матрицы : . (11.13) Тогда после -го шага обратного степенного метода . (11.14) Ясно, что вектор тем скорее станет доминирующим, чем больше будет отношение . Быстрее всего последовательность (11.14) сходилась бы, если бы было очень малой величиной, близкой к нулю. К сожалению, мы поменять не можем – ведь это и есть та величина, которую надо определить. Вспомним, однако, свойство операции сдвига матриц: Операцией сдвига по отношению к матрице называется вычитание из всех ее диагональных элементов одного и того же числа. Так, выражение означает, что матрица получена в результате сдвига матрицы на . Для приложений очень важно следующее свойство этой операции: в результате операции сдвига собственные значения матрицы изменяются на величину сдвига, а соответствующие собственные вектора остаются прежними. В самом деле, пусть собственное значение матрицы , а – соответствующий собственный вектор. Тогда
.
Если – собственные значения матрицы и – соответствующие собственные векторы, то матрица имеет собственные значения и собственные векторы . Согласно этому свойству, если нам будет известно достаточно хорошее приближение , то обратный степенной метод для матрицы будет сходиться значительно быстрее, чем для матрицы . Полученные для минимальное собственное значение (обозначим его ) и собственный вектор позволяют определить минимальное собственное значение и собственный вектор матрицы . Остается вопрос, откуда взять хорошее приближение для ? Практика и теоретические исследования показали, что лучшим выбором является отношение Рэлея: , (11.15) где, вообще говоря, – произвольный вектор; мы же будем брать в качестве вектор, полученный в результате очередной итерации. Более подробно это отношение и его свойства будут рассмотрены в следующих лекциях. Здесь же отметим еще, что для произвольного вектора , (11.16) причем равенство достигается в случае, если является первым собственным вектором матрицы . Пример. Вновь рассмотрим ту же матрицу с тем же начальным вектором . Кстати, поясним несколько странный выбор начального вектора в трех примерах этого параграфа. Обычно при применении степенных методов, не мудрствуя лукаво, в качестве начального вектора берут вектор с единичными элементами, т.е. следовало бы принять . Однако в этом случае точно совпало бы с собственным вектором матрицы . Поэтому для того, чтобы показать, как в процессе итераций от исходного неточного вектора происходит постепенное приближение к собственному, пришлось немного «испортить» начальный вектор.
1-я итерация:
Как видим, уже первая итерация дала такую точность, какую методы без сдвига достигали лишь после третьей итерации. Для убедительности примера все-таки проведем еще одну итерацию. 2-я итерация:
Метод Якоби Вспомним, что если – ортогональная матрица, приводящая матрицу к диагональному виду: , то столбцы – собственные вектора матрицы , а элементы диагональной матрицы – ее собственные значения.
Ортогональные матрицы Определение. Матрица называется ортогональной, если ее столбцы ортонормированны, то есть . Следствие. Для ортогональной матрицы ее обратная матрица равна ее транспонированной, т.е. или, что то же самое, . Еще одно следствие. Произведение ортогональных матриц есть ортогональная матрица. В самом деле, если и , то .
Воспользуйтесь поиском по сайту: ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|