/>
Численное решениеалгебраических проблем собственных значений: степенной метод.
Екатеринбург 2006
Введение
Выборнаиболее эффективного метода определения собственных значений и собственныхвекторов для конкретной инженерной задачи зависит от ряда факторов, таких, кактип уравнений, число искомых собственных значений и их характер. Различаютполную (алгебраическую) проблему собственных значений, предполагающуюнахождение всех собственных пар {λ, v} матрицы А,и частичную проблему собственных значений, состоящую как правило, в нахожденииодного или нескольких собственных чисел λ и, соответствующих имсобственных векторов v. Достаточно часто возникаютзадачи поиска наибольшего и наименьшего по модулю собственных значенийквадратной матрицы – знание таких характеристик матрицы позволяют, например,делать заключения о сходимости итерационных процессов, оптимизировать параметрыитерационных методов, учитывать влияние на результаты решения алгебраическихзадач погрешностей исходных данных. Другой пример: имеется матрица размера 5000*5000,в каждой строке которой содержится порядка десяти отличных от нуля элементов(разреженная матрица), и требуется найти только несколько, может быть, четыреили пять, собственных значений. Нахождение всех собственных пар разреженнойматрицы представляет собой достаточно сложную вычислительную проблему.
Итерационныеметоды позволяют находить собственные значения и векторы, минуя процедурупостроения характеристического полинома. Отличительной чертой этих методовявляется то, что собственные значения находятся лишь после определениясобственных векторов. Рассмотрим метод, который позволяет найти наибольшее помодулю собственное значение матрицы и соответствующий собственный вектор — степеннойметод.
Степенной метод
Классическимметодом, который иногда оказывается полезным для больших разреженных систем,хотя и страдает серьезными недостатками, является степенной метод. Предположим,что собственные значения /> матрицы /> вещественны и удовлетворяютусловию
/> (1)
При заданномвекторе /> рассмотримпоследовательность
/> (2)
Предположим,что матрица /> имеетn линейно независимых собственных векторов /> соответствующихсобственным значениям /> (это имеет место, например, вслучае симметричной матрицы А). Разложим /> по собственным векторам:
/>
Пусть />, тогда,учитывая (2):
/>
Разделим обечасти равенства на λ1k ≠ 0.
/>
В силу (1) всемножители /> стремятсяк нулю при k→ ∞ и вектор /> по направлениюприближается к собственному вектору />:
/> при k→∞, (4)
Если />, то нормавектора /> будетпри этом стремиться к нулю, либо неограниченно возрастать, если />. На практикевычисляемые векторы нормируют на каждой итерации, а в качестве критерияокончания процесса используют условие:
/>.
Формульно-словесноеописание метода:
1. Выбираем />: />, k=0,ε – точность вычисления компонент собственного вектора
2. k = k+1
3. Вычисляем />
4. Ищем координату />: />
5. Образуем вектор />
6. Если />, то собственным значениемявляется />;
/> = />; в противном случае перейтик п. 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. Составить отчет, который должен содержать следующие разделы:
- описание степенного метода и его модификаций
- описание исходных данных
- схемы-алгоритмов
- тексты программ;
- результаты расчетов тестовых примеров с использованием разработанныхпрограмм;
- анализ полученных результатов, выводы по работе;
- список литературы.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. ВержбицкийВ.М. Основы численных методов: Учебник для вузов. – М.: Высш. шк., 2002. –840с.
2. ВолковЕ.А. Численные методы: Учебное пособие. – 3-е изд., испр. – СПб: Лань, 2004. –248с.
3. КетковЮ.Л. MATLAB 6: программирование численных методов. – СПб.: БВХ-Петербург, 2004.– 672с.
4. ТурчакЛ.И. Основы численных методов: Учебное пособие. – М.: Наука. Гл. ред. физ.-мат.лит., 1987. – 320с.