Главная > Математика > Вычислительные методы для инженеров
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 8.2. Степенной метод

Пусть требуется вычислить максимальное по модулю собственное значение матрицы А, причем известно, что

Замечание. Собственное значение в данном случае должно быть вещественным, поскольку в противном случае собственным значением было бы также равное ему по модулю число

1. Степенной метод без сдвигов.

Опишем простейший вариант степенного метода, применяемого для вычисления А. Возьмем произвольный начальный вектор и построим последовательности векторов и приближений к А], используя формулы

Замечание. Правая часть формулы (8.14) — это просто отношение Рэлея, вычисленное при . В самом деле,

Справедлива следующая теорема.

Теорема 8.11. Пусть А — матрица простой структуры, для которой выполнено условие (8.12). Предположим, что в разложении

по базису из собственных векторов коэффициент не равен нулю. Тогда при к и верна оценка относительной погрешности

Как легко установить, вектор удовлетворяет равенству получается из умножением на степень матрицы

А (отсюда и название метода). Так как то следовательно,

Положим и заметим, что при к причем

Так как для всех то

Теперь нетрудно установить, что

при Более того,

Используя неравенство Коши-Буняковского , имеем

Из равенства (8.19) и оценок (8.18), (8 20) следует, что

Замечание 1. В действительности теорема 8 11 справедлива для произвольных матриц, удовлетворяющих условию (8.12). Предположение о том, что матрица А — простой структуры, потребовалось лишь для упрощения доказательства.

Замечание 2. Если то при (см. формулу и при вычислении на ЭВМ возможно переполнение. Если же то и возможно исчезновение порядка. Для предупреждения этих ситуаций обычно вектор нормируют, например, так, чтобы для всех Одна из используемых модификаций такова:

Предполагается, что

Теорема 8.11 для метода (8.21) остается справедливой. Более того, последовательность сходится к собственному вектору по направлению, т.е. при где — угол между векторами

Замечание 3. Крайне маловероятно, чтобы в разложении (8.15) вектора по собственным векторам коэффициент при оказался равным нулю. Теоретически в этой исключительной ситуации метод не должен давать сходящуюся к последовательность. Однако при вычислении на ЭВМ по формулам (8.12) через несколько итераций вследствие погрешностей округления почти наверняка появится ненулевой коэффициент при в разложении вектора Итерационный процесс снова окажется сходящимся (правда, потребуется выполнить большее число итераций).

2. Апостериорная оценка погрешности.

В общем случае для решения проблемы собственных значений не существует эффективных апостериорных оценок погрешности, в особенности для собственных векторов Более простой эта проблема выглядит для симметричных матриц

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

Теорема 8.12. Пусть А — произвольное число, произвольный ненулевой вектор. Тогда для любой симметричной матрицы А существует собственное значение этой матрицы А такое, что справедлива оценка

Если приближенно вычисленный собственный вектор, то неравенство (8.22) позволяет дать простую апостериорную оценку погрешности вычисленного собственного значения . В частности, для степенного метода (8.13), (8.14) из (8.22) следует такая апостериорная оценка:

(напомним, что здесь предполагается симметричность матрицы А).

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

Теорема 8.13. Пусть А — ближайшее к собственное значение симметричной матрицы соответствующий собственный вектор и угол между векторами Тогда справедливы оценки

Здесь расстояние от до ближайшего из отличных от А собственных значений матрицы А.

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

Оценка (8.23) может оказаться очень полезной для обратного анализа ошибок (о существе такого подхода к анализу ошибок мы говорили в § 3.6). Например, очень часто матрица А, для которой на ЭВМ производится вычисление собственных значений, является лишь

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

Пример 8.5. Используя степенной метод, найдем для матрицы (8.5) максимальное по модулю собственное значение а также отвечающий ему собственный вектор.

Возьмем и будем вести вычисления по формулам (8.21).

1 итерация. Вычисляем

Тогда

Далее,

Результаты десяти первых итераций с шестью знаками мантиссы приведены в табл 8.1.

Таблица 8.1 (см. скан)

Продолжение табл. 8.1 (см. скан)

Хотя мы не имеем в данном случае обоснованного критерия окончания, по-видимому, при следует прекратить вычисления и, округляя результаты, положить

Важными достоинствами степенного метода являются его простота, возможность эффективного использования разреженности матрицы и отсутствие необходимости преобразования матрицы А.

Недостаток метода в применении к многим прикладным задачам — довольно медленная сходимость. Часто в приложениях значение оказывается близким к Так как скорость сходимости степенного метода определяется величиной и 1, то в этом случае сходимость будем очень медленной.

3. Степенной метод со сдвигами.

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

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

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

Существует несколько способов избавления от уже вычисленных собственных чисел и соответствующих собственных векторов с целью избежать их повторного вычисления. Эти способы принято называть исчерпыванием. Более подробную информацию о них можно найти, например, в [19], [62].

<< Предыдущий параграф Следующий параграф >>
Оглавление