Методичка 2 Численные

ВСТУП

З розвитком обчислювальної техніки велика увага приділяється чисельним методам, які широко застосовуються для розв’язку математичних, технічних і економічних задач. Серед них виділяють клас чисельних мето-

дів, які називаються чисельними методами лінійної алгебри. Сюди належать методи розв’язування систем лінійних алгебраїчних рівнянь, а також методи знаходження власних значень і векторів матриць.

Задача знаходження власних значень і векторів матриць є важливою для вирішення широкого кола питань обчислювальної математики. Її застосовують у диференціальних рівняннях, зокрема у проблемі стійкості. Важливу роль власні значення відіграють у механіці, радіофізиці та інших галузях. Але обчислення власних значень і власних векторів є однією з найважчих задач лінійної алгебри.

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

В методичних вказівках наведені основні теоретичні положення, на яких ґрунтуються прямі методи знаходження власних значень і векторів матриць, та докладно виконана постановка задач на лабораторну роботу. Методичні вказівки містять у собі велику кількість детально пояснених прикладів, які охоплюють розглянуті прямі методи знаходження власних значень і векторів матриць.

3

1. ТЕОРЕТИЧНИЙ МАТЕРІАЛ

1.1. Класифікація методів знаходження власних значень і векторів

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

Характеристичним або віковим рівнянням матриці A aij

називається рівняння

Ліва частина цього рівняння, яку можна записати скорочено у вигляді det A E , називається характеристичним поліном матриці:

det A E 1 n n p1 n 1 p2 n 2 pn .

Власними значеннями або власними числами матриці А на-

зивають корені її характеристичного полінома.

Множину всіх власних значень матриці називають її спектром. Ненульовий вектор xi називається власним вектором, відповід-

ним власному значенню i , якщо виконується рівність

Визначення компонентів власного вектора вимагає розв’язання системи n однорідних рівнянь із n невідомими. Для обчислення всіх власних векторів матриці, загалом кажучи, необхідно вирішити n систем:

A i E xi 0 ,

де xi x1i , x2i , , xni – власний вектор матриці А, що належить власному значенню i .

4

Більшість класичних методів розв’язання повної проблеми власних значень використовує попереднє обчислення коефіцієнтів характеристичного полінома, що здійснюється без обчислення множини мінорів. Потім власні значення обчислюються за будь-якому з методів наближеного обчислення коренів полінома. Одним із кращих способів знаходження коре-

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

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

Звичайно прямі методи застосовуються до щільних матриць і вимагають порядку O n3 і більше операцій для обчислення власних значень і

власних векторів. Ця величина практично не залежить від характеру елементів матриці.

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

Ітераційні методи також більше пристосовані до розв’язку часткової проблеми власних значень, тобто задачі знаходження одного або декількох власних значень і відповідних їм власних векторів. Серед ітераційних методів у цей час найпоширеніші QR-алгоритм зі зрушеннями, що практично завжди збігається за фіксовану кількість ітерацій, а також методи Релея-Рітца та Ланцоша.

1.2. Властивості власних значень і векторів

Позначимо через i , xi – власну пару матриці А, тобто її деяке власне значення i та відповідний йому власний вектор xi . Тоді можна сформулювати основні властивості власних значень і векторів.

1. Якщо i , xi – власна пара матриці А і – деяке число ( 0 ), то i , xi також буде власною парою для А.

Справді, помноживши правильну для заданих i і xi рівність (2) на число , отримаємо правильну рівність

A xi i xi .

Вона означає, що кожному власному числу i відповідає нескінченна

множина власних векторів, відмінних лише скалярним множником. Такі вектори задають один напрям у n-вимірному просторі. У відповідність цьому напряму можна поставити нормований вектор або орт. При цьому одному власному значенню може відповідати і декілька лінійно незалежних власних векторів.

Розглянемо рівність (2) при i i z

Axi i z xi .

Вона рівносильна (3), тому можна зробити висновок, що i , xi – власна

пара матриці А.

Таким чином, додавання до заданої матриці скалярної матриці zE не змінює її власних векторів, а лише зміщує спектр вихідної матриці на число z (ліворуч при z 0 ).

власна пара матриці A 1 .

Помноживши рівність (2) ліворуч на матрицю 1 A 1 , отримаємо

i

1 xi A 1xi ,

i

що й означає твердження.

4. Власними значеннями діагональних і трикутних матриць є їхні діагональні елементи.

Цей факт випливає з характеристичного рівняння

n

aii 0 .

i 1

Отже, діагональні і трикутні дійсні матриці мають тільки дійсні власні значення (точно n з урахуванням можливої їх кратності). Дійсні власні значення мають також і симетричні матриці, які часто зустрічаються на практиці.

фіксованого ненульового вектора х досяжний при x . Нехай А – симетрична матриця і х – дійсний вектор. Тоді

22 Ax x, Ax x Ax, Ax 2 Ax, x 2 x, x f x, x ,

7

завжди має мінімум при x , а оскільки x, x 0 , то це значення λ надає мінімум величині 22 , а отже, і 2 .

Інакше кажучи, якщо деякий вектор х уважають наближенням до власного вектора матриці А (тобто ξ – його відхил), то співвідношення Релеяx буде найліпшим наближенням до відповідного цьому вектору влас-

ного значення в евклідовій метриці.

7. Нехай i , xi – власна пара матриці B C 1AC . Тоді i ,Cxi – власна пара матриці А.

Підставимо вираз B C 1AC у правильну для пари i , xi рівність

Bxi i xi :

C 1ACxi i xi ,

звідси після множення ліворуч на матрицю С отримаємо ACxi iCxi , що

і доводить істинність твердження.

Отже, перетворення подібності зберігає незмінним спектр довільної матриці. Подібні матриці мають також однакові характеристичні поліноми.

У зв’язку зі простою структурою матриці А всі її власні вектори, тобто стовпці матриці Х, лінійно незалежні, тому матриця Х – оборотна.

Помножимо зліва (4) на матрицю X 1 , отримаємо потрібне X 1 AX . Оскільки для діагональної матриці Λ, утвореної із власних значень, власними векторами можуть бути одиничні вектори вихідного базису

8

1.3. Стійкість проблеми власних значень

При постановці проблеми власних значень для матриць, елементи яких задані приблизно, виникає питання про стійкість отриманого розв’язку.

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

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

Для вимірювання чутливості власних значень матриці А до змін вихідних даних A уводять поняття зумовленості матриці у задачі знаходження власних значень і векторів. У проблемі власних значень поняття зумовленості матриці не збігається з таким же поняттям у разі розв’язання системи лінійних алгебраїчних рівнянь. Погано зумовлена матриця щодо розв’язування системи лінійних рівнянь може бути добре зумовленою щодо власних значень і навпаки. Крім того, добре зумовлена матриця щодо задачі знаходження власних значень може бути погано зумовленою при знаходженні власних векторів.

Нехай задано матриці А і A A , що близька до неї. З'ясуємо, як змінюються власні значення й власні вектори матриці А, коли вона одержує

де H – матриця, складена з власних векторів матриці А. З формули (5) видно, що повна похибка визначена як похибкою у вихідних даних, так і величиною

9

яку називають спектральним числом зумовленості матриці А

щодо задачі знаходження власних значень. Оскільки матриця H неєдина, будемо уважати, що спектральне число зумовленості матриці А щодо проблеми власних значень – це найменше значення K H для всіх

припустимих H. У будь-якому випадку

K H H 1 2 H 2 H 1H 2 1 .

Якщо А – нормальна матриця, зокрема ермітова, тоді K H 1.

Таким чином, проблема власних значень завжди добре зумовлена для нормальних матриць, зокрема ермітових та симетричних, хоча це не обов’язково справедливо для проблеми власних векторів.

Спектральне число характеризує зумовленість матриці в разі знаходження всіх власних значень у цілому й у випадку її поганої зумовленості не завжди свідчить про погану зумовленість окремого власного значення.

Для вимірювання чутливості окремого власного значення до змін вихідних даних уведено поняття s-чисел, яки визначаються за формулою

si yiT xi ,

де xi – нормованих власний вектор, що відповідає власному значенню i

Якщо матриця А має прості власні значення, то число зумовленості для кожного з них можна визначити за формулою

бути тим більше, чим більше відповідне цьому власному значенню число зумовленості. Тобто для довільних матриць задача визначення власних значень буде не стійкою при великому коефіцієнті перекосу.

Таким чином, задача знаходження власних векторів буде нестійкою, якщо великий хоча б один з коефіцієнтів перекосу або якщо є близькі власні значення.

Для нормальних матриць власні вектори xi і yi співпадають, тому,

виходячи з формул (8) і (9) при обчисленні власних значень близькість точного та наближеного розв’язків визначена лише похибкою у вихідних даних

i A 2 .

Для власних векторів нормальних матриць з формул (8)–(10) одержимо оцінку відносної похибки

яка залежить як від норми похибки матриці, так і від близькості власних значень i і j .

11

Розглянемо зміну власних значень дійсної матриці при випадкових змінах її елементів. Нехай елементи матриці A є незалежними випадковими величинами з математичними очікуваннями aij та однією й тією же

дисперсією 2 . Тоді будь-яке дійсне значення буде випадковою величиною, що має в першому наближенні дисперсію c 2 , де c – коефіцієнт перекосу, що відповідає цьому власному значенню. Для симетричних матриць, тобто у випадку aij a ji , дисперсія кожного власного значення

2 . При припустимих симетричних змінах елементів симетричних мат-

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

нює 2 , а недіагональних 12 2 . Власні значення в цьому випадку також у

першому наближенні є незалежними випадковими величинами. При цьому дисперсії коефіцієнтів характеристичного полінома можуть бути досить великими, однак його коефіцієнти вже не будуть незалежними випадковими величинами і ймовірні їхні зміни пов'язані так, що вони не призводять до великої зміни власних значень.

Приклад. Нехай є матриця А і близька до неї матриця A A .

Матриця А є погано зумовленою щодо задачі розв’язку системи лінійних рівнянь, тобто серед її власних значень є малі за модулем у порівнянні з іншими. Характеристичні поліноми

A : 4 35 3 146 2 100 1 0,

A A : 4 35.1 3 149 2 110.6 7.8 0.

Власні значення:

Таким чином, зміна першого елемента матриці викликала зміну власних значень максимально на 0,069, у той час як коефіцієнти

12

характеристичного полінома змінилися значно не тільки відносно, але й абсолютно, а саме, максимально на 10,6.

1.4. Метод А.М. Крилова для визначення власних значень

Ідея методу А.М. Крилова (1931 р.) полягає в попередньому перетворенні рівняння (1) в еквівалентне йому рівняння вигляду

розгортання якого за степенями λ здійснюється простіше шляхом розкладання визначника за мінорами 1-го стовпця.

Рівність нулю визначника (1) є необхідною й достатньою умовою того, щоб система однорідних рівнянь

xn an1x1 an2 x2 ann xn

мала розв’язок x1, x2 , , xn , відмінний від нуля.

Перетворимо систему (12) у такий спосіб. Помножимо перше рівняння на λ і замінимо x1, , xn їхніми виразами через x1, , xn . Одержимо

2 x1 b21x1 b22 x2 b2n xn ,

n

де b2k a1sask . s 1

Помножимо далі отримане рівняння на λ і замінимо x1, , xn їхніми виразами через x1, , xn , використовуючи вихідну систему. Одержимо

3x1 b31x1 b32 x2 b3n xn .

Повторюючи цей процес (n–1) раз, перейдемо від системи (12) до системи

13

полінома тільки чисельним множником.

Нехай всі корені різні. Оскільки всі корені є коренями D , то D ділиться на . При цьому степені D і однакові, отже, частка повинна бути постійною, тобто не залежати від λ. Порівнюю-

чи коефіцієнти при n , одержимо D N .

Якщо має кратні корені, рівність

зберігається з міркувань безперервності.

Якщо N 0 , то D 0 і зазначене перетворення не приводить до розв’язку.

14

Очевидно, що перетворювати систему (12) можна, наприклад, виходячи із другого рівняння системи. У цьому випадку λ увійде в другий стовпець визначника D , а коефіцієнти bik будуть визначатися відповідно

за формулами (16), де b0 0,1,0, ,0 .

Метод Крилова можна узагальнити на випадок вектора b0 довільного вигляду. Нехай

b0 b01,b02 , ,b0n ,

u b01x1 b02 x2 b0n xn ,

де x1, x2 , , xn є розв’язком системи (13). Тоді, повторюючи попередні міркування, одержимо:

невідомими u, x1, x2 , , xn , одержимо, що ненульовий розв’язок можливий тільки в тому випадку, коли визначник

15

Повторюючи попередні міркування, знайдемо, що

Також як і для окремого випадку, перетворення не приводить до розв’язку, якщо N 0 . Тому припустимо спочатку N 0 . На підставі рівності (15) коефіцієнти pi характеристичного полінома визначаються як

pi 1 n 1 Ni ,

N

де Ni – алгебраїчні доповнення елементів n i у визначнику D . При цьому можна визначити коефіцієнти pi без обчислення алгебраїчних доповнень. Дійсно, у зв’язку з тим, що елементи рядків визначника (18) є

Покажемо, що коефіцієнти цього співвідношення і є коефіцієнтами pi характеристичного полінома, записаного у вигляді

1 n n p1 n 1 pn .

Віднявши з останнього рядка визначника D лінійну комбінацію попередніх рядків з відповідними коефіцієнтами q1, q2 , , qn , на підставі рівності (19) одержимо

16

qn pn як розв’язок системи лінійних рівнянь, що еквівалентна цій векторній рівності.

Очевидно, що замість системи (19) для визначення коефіцієнтів pi

полінома матриці. Його корені будуть збігатися з усіма коренями характеристичного полінома, але будуть мати меншу кратність.

Якщо мінімальний поліном не збігається з характеристичним, то

C0 , AC0 , , An 1C0 лінійно залежні.

Таким чином, метод Крилова дозволяє визначити коефіцієнти характеристичного полінома, якщо N 0 , або деякого його дільника, загалом кажучи, мінімального полінома, якщо N 0 .

Рівність N 0 проявляється в процесі прямого ходу методу Гаусса при розв’язанні системи (19). У частині рівнянь виключаються всі коефіцієнти одночасно і ці рівнянь стають тотожностями 0 0 . Тоді ці рівнян-

17

ня можна відкинути. Нехай число таких рівнянь n m . У системі, що залишилася, необхідно відкинути n m стовпців, починаючи зі стовпця вільних членів, тобто з C0 . Останній зі стовпців, що залишилися, складений з компонентів вектора Cm , необхідно прийняти як вектор вільних членів

нової системи. В результаті розв’язування цієї системи знаходяться коефіцієнти лінійної залежності Cm від C0 , C1, ,Cm 1 , тобто коефіцієнти мі-

німального полінома, що анулює вектор C0 .

Приклад. Знайдемо за методом Крилова коефіцієнти характеристи-

ристичного полінома. Причому коефіцієнт при старшому степені дорівнює 1. Таким чином, характеристичний поліном має вигляд:

4 35 3 146 2 100 1 0 .

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

1.5. Визначення власних векторів за методом А.М. Крилова

Нехай за методом А.М. Крилова знайдені коефіцієнти характеристичного полінома та обчислені всі його власні значення, які виявилися різними. Розглянемо, як визначити власні вектори матриці.

Нехай C0 – вихідний вектор в алгоритмі А.М. Крилова і нехай x1, x2 , , xn – власні вектори матриці А, що належать власним значенням

1, 2 , , n . Тоді вектори x1, x2 , , xn лінійно залежні. Розкладемо C0 за власними векторами:

C0 1x1 2 x2 n xn .

Тоді

C1 AC0 1 1x1 2 2 x2 n n xn ,

Cn 1 An 1C0 1 n1 1x1 2 n2 1x2 n nn 1xn.

Вектори C1,C2 , ,Cn 1 обчислені у процесі знаходження власних

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

при відповідному виборі коефіцієнтів ij . Розглянемо лінійну комбінацію:

10Cn 1 11Cn 2 1n 1C0

19

n p1 n 1 pn .1

Тут – характеристичний поліном, коефіцієнти і корені якого вже обчислені.

Коефіцієнти 1 можна обчислити за рекурентними формулами

(так звана схема Горнера):

Таким чином,

10Cn 1 11Cn 2 1n 1C0 1 1 1 x1 ,

тобто складена лінійна комбінація є власним вектором x1 з точністю до числового множника. При цьому коефіцієнт 1 повинен бути не рівним

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

Аналогічно,