Чисельне рішення алгебраїчних проблем власних значень

Чисельне рішення алгебраїчних проблем власних значень: ступеневій метод.
Єкатеринбург 2006

Введення
Вибір найбільш ефективного методу визначення власних значень і власних векторів для конкретної інженерної задачі залежить від ряду факторів, таких, як тип рівнянь, число шуканих власних значень і їх характер. Розрізняють повну (алгебраїчну) проблему власних значень, яка передбачає знаходження всіх власних пар {λ, v} матриці А, і часткову проблему власних значень, що складається як правило, в знаходженні одного або кількох власних чисел λ і, відповідних їм власних векторів v. Досить часто виникають задачі пошуку найбільшого і найменшого за модулем власних значень квадратної матриці - знання таких характеристик матриці дозволяють, наприклад, робити висновки про збіжність ітераційних процесів, оптимізувати параметри ітераційних методів, враховувати вплив на результати вирішення алгебраїчних завдань похибок вихідних даних. Інший приклад: є матриця розміру 5000 * 5000, в кожному рядку якій міститься близько десяти відмінних від нуля елементів (розріджена матриця), і потрібно знайти лише кілька, можливо, чотири або п'ять, власних значень. Знаходження всіх власних пар розрідженій матриці представляє собою досить складну обчислювальну проблему.
Ітераційні методи дозволяють знаходити власні значення та вектори, минаючи процедуру побудови характеристичного полінома. Відмінною рисою цих методів є те, що власні значення перебувають лише після визначення власних векторів. Розглянемо метод, який дозволяє знайти найбільше за модулем власне значення матриці і відповідний власний вектор - ступеневій метод.

Степенній метод
Класичним методом, який іноді виявляється корисним для великих розріджених систем, хоча і страждає серйозними недоліками, є ступеневій метод. Припустимо, що власні значення матриці речовинні і задовольняють умові
(1)
При заданому векторі розглянемо послідовність
(2)
Припустимо, що матриця має n лінійно незалежних власних векторів відповідних власним значенням (Це має місце, наприклад, у випадку симетричної матриці А). Розкладемо за власним векторах:

Нехай , Тоді, враховуючи (2):

Розділимо обидві частини рівності на λ ₁ ^k ≠ 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с.