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

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

Більшість ітераційних методів визначення власних значень і векторів матриці А ґрунтуються на приведенні матриці А за допомогою невиродже-

них перетворень до такої матриці A* , для якої проблема власних значень є простою. Наприклад, якщо А – дійсна матриця з різними дійсними власними значеннями 1, , n , то матриця перетворення Т, що переводить А

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

Стовпці матриці Т утворюють повну систему власних векторів А, а

діагональні елементи матриці A* є власними значеннями А.

Але щоб визначити власні значення матриці (за тими же припущеннями відносно i ), не обов’язково приводити її до діагонального виду.

Достатньо привести матрицю до трикутного вигляду, тому що на діагоналі трикутної матриці будуть розташовані власні значення А:

Дійсно, характеристичне рівняння для A*

det A* E 0

представляється у формі

5

Визначення власних векторів ei* трикутної матриці A* є простою за-

дачею, тому що вона еквівалентна розв’язанню системи лінійних однорідних рівнянь

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

Знаючи власні вектори матриці A* , можна одержати власні вектори А за допомогою матриці перетворення Т

ei Tei* ,

оскільки з рівності

T 1ATei* aii*ei*

випливає співвідношення

A Tei* aii* Tei* .

Найпростішим з алгоритмів обчислення власних значень, що ґрунтується на приведенні матриці до трикутного вигляду, є метод, який використовує ідею LU-розкладу матриці.

За ува ж ен ня . Якщо дійсна матриця має комплексні власні значен-

ня, вона не може бути приведена до трикутної матриці A* за допомогою дійсного перетворення. Матрицею, до якої можна привести будь-яку матрицю А за допомогою дійсного й навіть ортогонального перетворення, є

ма й ж е тр и ку тна ма тр и ц я A* (вер хня фо р ма Хе с сен бер га ):

6

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

A* , яких при великих n майже вдвічі менше, ніж у вихідної матриці А. Для симетричних матриць форма (1) приймає тридіагональний вигляд:

1.2.LU-алгоритм пошуку власних значень матриці

В несиметричному випадку для пошуку власних значень матриці часто використовують ідею перетворення заданих матриць до подібних матриць трикутного вигляду. Найпростішим з таких алгоритмів є алгоритм, що ґрунтується на ідеї LU-розкладу матриці.

Нехай задано невироджену матрицю А порядку n, яку можна представити у вигляді

7

Отже, матриця A 1 подібна до матриці A 2 , тому їх власні значення співпадають. Підстановка (5) в (4) дає вираз вихідної матриці А через A 2 :

A LL1 A 2 L1 1 L 1 LL1 A 2 LL1 1 ,

звідки випливає рівність власних значень матриць А і A 2 .

Такий процес побудови послідовності подібних матриць A k є основою LU-алгоритму пошуку власних значень матриці, що був запропо-

A k 1 U k L k , k 0,1, 2, .

Сформулюємо тв ер д же н ня п р о зб і жн іс ть LU - а л го р и т му .

Нехай матриця А – невироджена, має різні власні значення i , i 1, n , модулі яких, за винятком комплексно-спряжених, також різні й упорядковані в порядку незростання, тобто 1 2 n . Тоді при нескін-

ченної кількості ітерацій, тобто при k , отримана послідовність матриць збігається до трикутної матриці U k вигляду

8

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

Приклад 1. Розглянемо застосування LU-алгоритму для пошуку

9

Факторизуємо цю матрицю аналогічно до попереднього:

Звідси

Наступний крок дає:

точних власних значень матриці А приблизно на 0,143, а матриці A 4 – на 0,049. Проте швидкість спадання до нуля модулів піддіагональних елементів матриці не дуже висока.

10