69322

Степеневий метод обчислення власних значень

Лекция

Математика и математический анализ

Для оцінки окремих власних значень матриці можна використовувати теорему Гершгоріна яка стверджує що матриця А порядку nxn має n власних значень кожне з яких лежить в межах круга: 4. Якщо λ власне значення матриці то завжди можна вибрати відповідний йому...

Украинкский

2014-10-03

149.5 KB

18 чел.

Лекція 7.

Степеневий метод обчислення власних значень 

Для оцінки окремих власних значень матриці можна використовувати теорему Гершгоріна, яка стверджує, що матриця А порядку nxn має n власних значень, кожне з яких лежить в межах круга:

 (4.28)

Довести цю теорему можна так. Якщо λ  власне значення матриці, то завжди можна вибрати відповідний йому власний вектор х (х≠0), який задовольняє умові (4.1):

Ах = λх

або

(4.29)

де i індекс компоненти власного вектора, i = 1,2,…,n.

Переходячи до норм у виразі (4.29) з урахуванням |xi| ≤ ||x|| і |xj| ≤ ||x|| отримаємо:

.

В окремому випадку діагональної матриці А всі недіагональні елементи aij = 0, тому ri = 0 і власні значення матриці співпадають з її діагональними елементами λ = aij.

На основі теореми Гершгоріна проводиться оцінка змін значень власних чисел матриці, обумовлених змінами значень її елементів. Нехай А — задана матриця розміру nхn з власними значеннями λ1,…, λn, В  матриця, елементи якої задаються змінами значень елементів матриці А, і нехай μ 1,…, μ n, — власні значення сумарної матриці (А + В). Тоді, як наслідок теореми Гершгоріна,

.

Для симетричної матриці В норми ||B||, обчислені з допомогою елементів різних її рядків, практично співпадають по значенню, що і визначає добру обумовленість власних значень початкової симетричної матриці А при зміні значень її елементів.

Якщо необхідно оцінити лише деякі з власних значень (наприклад, λmax або λmin), то простіше використовувати степеневий метод для формування послідовності векторів

(4.30)

Припустимо, що матриця А має n лінійно незалежних власних векторів і максимальне по величині власне значення λ max = λ1 таке, що |λ1| > |λ2| ≥ |λ3| > … ≥ |λn|.

Якщо розкласти деякий початковий вектор z0 в базисі власних векторів матриці

,

то

Оскільки |λj/λ1| < 1 для ј > 2, то напрямок вектора zk прямує до напрямку власного вектора x1, якщо тільки a1 ≠ 0.

Для підвищення стійкості обчислень проводять масштабування послідовності векторів {zk}, яке простіше всього здійснюється переходом до послідовності {yk} з нормою ||yk|| = 1, яка формується так:

 (4.31)

Тоді замість (4.30) використовують співвідношення

(4.32)

похибка якого прямує до нуля як (λ2/λ1|)k.

Якщо степеневий метод застосувати до оберненої матриці A - 1, то аналогічно можна оцінити величину найменшого власного значення λmin, якщо виконується умова

.

Приклад 4.7.

Знайти найбільше власне значення матриці з Прикладу 4.5:

Спочатку, вибираючи вектор z0 = {1,1,1,1}t, обчислюємо вектор

.

На наступній ітерації у відповідності з (4.22) отримуємо :

при цьому похибка оцінюється значенням:

На третій ітерації знаходимо :

і похибку 

На четвертій ітерації обчислюємо:

і похибку 

Результати обчислень на п’ятій ітерації:

і похибка

і, нарешті, на шостій ітерації отримуємо шуканий результат з похибкою ε = 0,5141 %:

звідки у відповідності з співвідношення (4.32) випливає, що λmax = 8,1638. Цей результат добре корелюється з відповіддю (λmax = 8,1638), отриманою в Прикладі 4.5.

Приклад 4.8.

Знайти найменше власне значення матриці з Прикладу 4.5:

А =

Для цього нам необхідна обернена матриця:

.

Виконаємо по аналогії з попереднім прикладом послідовність ітерацій, користуючись співвідношеннями (4.31) і обираючи початковий вектор z0 = {1,1,1,0}t.

Перша ітерація:

Друга ітерація :

де похибка обчислень складає ε = 53,9123 %.

Третя ітерація :

де похибка обчислень складає ε = 43,8709 %.

Четверта ітерація :

де похибка обчислень складає ε = 0,7471

Враховуючи, що ми отримали оцінку оберненої величини найменшого власного значення матриці, знаходимо

що відповідає результату (λmin = - 2,2209), який отримано в Прикладі 4.5.

Степеневий метод можна розповсюдити і на випадки знаходження других власних значень матриці, які слідують безпосередньо за λmax або попередніх λmin. Для цього необхідно провести редукцію матриці, замінивши початкову матрицю другою матрицею, яка не матиме вже знайдені λmax або λmin. У випадку симетричних матриць така редукція здійснюється з допомогою методу Хотелінга, який базується на використанні властивості ортогональності власних векторів матриці:

 (4.33)

де компоненти векторів нормуються по величині .

Нова матриця A2 будується по початковій матриці A2, яка має найбільше власне значення λ1 = λmax, так:

(4.34)

Ітерації довільного вектора матрицею A2 будуть сходитися до наступного по величині власного значення λ2. Дійсно, якщо рівняння (4.34) помножити справа на вектор {x}1, то отримаємо вираз :

,

який в силу властивості ортогональності власних векторів матриці спрощується до виду:

(4.35)

Отже, випадок λ = 0 і {x} = {x}1 також відповідає розв’язку рівняння A2{x}1 = λ1{x}1, або, іншими словами, матриця A2 має наступний набір власних значень: 0,λ2,λ3,…,λn. Теоретично можна побудувати потім матрицю A3 і так далі, для перебору всіх власних значень. Однак, накопичувана похибка приведе до результатів, які поступаються по точності і швидкодії результатам, які можна отримати з допомогою QR–алгоритму.

Висновки

1. Математична задача обчислення власних значень і векторів матриць значно складніше порівняно із задачею розв’язку лінійних систем рівнянь. Із зростанням розмірності задачі явні переваги виявляються на стороні ітераційних методів типу QRрозкладу.

2. Для лінійних моделей об’єктів і систем, заданих системою лінійних рівнянь, власні значення матриці їх коефіцієнтів співпадають з полюсами моделей, що дозволяє уникнути знаходження передаточних функцій з необхідністю контролю точності обчислення поліномних коефіцієнтів їх чисельників і знаменників і наступним визначенням коренів полінома знаменника. Як відомо, саме через полюси визначаються перехідні процеси в об’єктах, їх смуги пропускання, стійкість та ін., а комплексно–спряжені полюси визначають резонансні явища в поведінці об’єктів.

3. Погана обумовленість лінійних систем рівнянь і жорсткість диференційних рівнянь визначаються різницею максимального і мінімального власних значень відповідних матриць (коефіцієнтів лінійних рівнянь або перших похідних нелінійних рівнянь), яка може досягати на практиці 8–12 порядків. В математичних моделях об’єктів ця різниця визначається конкретними фізичними ефектами і процесами, наприклад, ефектом підсилення в електронних схемах, коли сигнали малої потужності на базі транзистора керують сигналами значно більшої потужності на колекторі транзистора. Крім того, причиною вищезгаданих особливостей математичної моделі об’єкта може бути надмірна ідеалізація характеристик його компонентів

4. Задача знаходження власних значень симетричних матриць виявилася на практиці краще обумовленою порівняно з аналогічною процедурою для несиметричних матриць, тому що власні значення довільної матриці більш чутливі до малих змін елементів матриці.

Вправи

1. Для матриці з прикладу 4.2

скористатися методом Крилова, вибрати довільний вектор x = [1,0,0]t і довести, що система рівнянь (4.10) для коефіцієнтів характеристичного полінома буде виродженою.

2. Для матриці

скориставшись методом Фадєєва–Левер’є, довести, що вектор коефіцієнтів характеристичного полінома рівний p = [1, - 12, - 139,98]t.

3. Використайте метод QR–розкладу для матриці

і доведіть, що вектор власних значень матриці λ = [7,509, 0,745i0,4928,0]t.

4. Нехай задано матрицю
.
Визначте, чи буде розв’язок системи  асимптотично стійким, тобто дійсні частини комплексно–спряжених чи самі дійсні власні значення матриці будуть від’ємними.

5. Безпосередньою підстановкою і застосуванням тригонометричних тотожностей доведіть, що дійсна симетрична матриця порядку n x n 
А =
має власні значення λk = a + 2bcos[/(n + 1)], k = яким відповідають власні вектори xk = {sin[k/(n + 1)], sin[2k/(n + 1)],..., sin[nk/(n + 1)]}, k =

6. Покажіть, що складність одного QRрозкладу повної матриці А складає 4n3/3 операцій. Якщо матриця приведена до форми Хессенберга, яка зберігається при наступних QRітераціях, то складність одного QRрозкладу зменшується до 4n2 операцій для несиметричних матриць і 12n  для симетричних.

PAGE  83