Численное решение алгебраических проблем собственных значений

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

(1)

При заданном векторе рассмотрим последовательность

(2)

Предположим, что матрица имеет n линейно независимых собственных векторов соответствующих собственным значениям (это имеет место, например, в случае симметричной матрицы А). Разложим по собственным векторам:

Пусть , тогда, учитывая (2):

Разделим обе части равенства на л₁^k ? 0.

В силу (1) все множители стремятся к нулю при k> ? и вектор по направлению приближается к собственному вектору :

при k> ?, (4)

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

.

Формульно-словесное описание метода:

Выбираем : , k=0, е - точность вычисления компонент собственного вектора

k = k+1

Вычисляем

Ищем координату :

Образуем вектор

Если , то собственным значением является ;

= ; в противном случае перейти к п. 2.

Существует модификация степенного метода, которая отличается от предыдущего алгоритма критерием остановки итерационного процесса.

Формульно-словесное описание метода:

1. Выбираем : , k=0, е - точность вычисления максимального по модулю собственного значения, - некоторый допуск (близость к нулю компонент вектора );

2. k = k+1;

3. Вычисляем ;

4. Ищем координату : ;

5. Образуем вектор ;

6. Вычисляем для таких i, что , где - допуск;

7. Если , то собственным значением является , где j - число индексов, для которых выполняется условие ; в противном случае перейти к п. 2.

Основным достоинством степенного метода является то, что векторы получаются только с помощью умножения матрицы на вектор (плюс некоторая работа по вычислению нормирующих множителей); никаких преобразований самой матрицы при этом не требуется. Главный недостаток этого метода заключается в том, что он может сходиться очень медленно. Скорость сходимости в первую очередь определяется отношением . Если это отношение по модулю близко к 1, что характерно для многих практических задач, то сходимость будет медленной.

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

Задание на лабораторную работу

Цель работы: изучение степенных методов расчета максимального по модулю собственного значения и соответствующего собственного вектора квадратной матрицы.

1. Ознакомиться со степенным методом вычисления максимального по модулю собственного значения матрицы A и его модификациями.

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

3. Элементы матрицы А должны считываться из файла, точность расчета е вводится с клавиатуры.

4. При проверке работоспособности программ для n=2 и n=3 выполнить ручной расчет собственных значений и собственных векторов матрицы А.

5. Нахождение собственных векторов и собственных значений следует провести, используя самостоятельно составленные и предложенные ниже тестовые примеры:

, ,.

6. При заданной точности расчета е фиксировать выполненное число итераций k.

7. Составить отчет, который должен содержать следующие разделы:

описание степенного метода и его модификаций

описание исходных данных

схемы-алгоритмов

тексты программ;

результаты расчетов тестовых примеров с использованием разработанных программ;

анализ полученных результатов, выводы по работе;

список литературы.