На головну

 Власні значення. - Математика

1. ВСТУП

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

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

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

2. ДЕЯКІ ОСНОВНІ ВІДОМОСТІ, НЕОБХІДНІ ПРИ ВИРІШЕННІ ЗАВДАНЬ НА ВЛАСНІ ЗНАЧЕННЯ

У загальному вигляді задача на власні значення формулюється таким чином:

AX = lX,

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

Основні визначення матричного числення

1. Матриця A називається симетричною, якщо

аij = аij, де i, j = 1, 2,. . ., N.

Звідси випливає симетрія щодо діагоналі

аkk, де k == 1, 2,. . ., N.

Матриця

 1 5 квітень

 4 3 7

 5 7 лютого

є прикладом симетричною.

2. Матриця A називається трехдіагональной, якщо всі її елементи, крім елементів головної і прилеглих до неї діагоналей, дорівнюють нулю. У загальному випадку трехдіагональной матриця має вигляд

 * * 0

 * * *

 * * *

 . . . . . .

 * * *

 0 * * *

 * *

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

3. Матриця A називається ортогональною, якщо

АТА = Е,

де Ат-транспонована матриця A, а Е-одинична матриця. Очевидно, матриця, зворотна ортогональної, еквівалентна транспонованою.

4. Матриці А та В називаються подібними, якщо існує така несінгулярная матриця Р, що справедливе співвідношення

В = Р-1АР.

Основні властивості власних значень.

1. Усі п власних значень симетричною матриці розмірності ПХП, що складається з дійсних чисел, дійсні. Це корисно пам'ятати, так як матриці, що зустрічаються в інженерних розрахунках, часто бувають симетричними.

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

Xi, де i == 1 ,. . ., N,

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

n

Y = S aiXi.

i = 1

3. Якщо дві матриці подібні, то їх власні значення збігаються. З подоби матриць A і В випливає, що

В = Р-1АР.

Так як

АХ = LХ,

то

Р-1АХ = lр-1Х.

Якщо прийняти Х == рy, то

Р-1АРY = lY,

а

Вy == lY.

Таким чином, матриці A і В не тільки мають однакові власні значення, а й їхні власні вектори пов'язані співвідношенням

Х = Р Y.

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

3. ітераційні методи РІШЕННЯ.

Мабуть, найбільш очевидним способом вирішення задачі на власні значення є їх визначення із системи рівнянь

(A - lE) Х == 0,

яка має ненульове рішення лише у випадку, якщо det (A - lE) = 0. Розкривши визначник, отримаємо многочлен п-го ступеня щодо l, коріння якого і будуть власними значеннями матриці. Для визначення коренів можна скористатися будь-яким з методів, описаних в гл. 2. На жаль, в задачах на власні значення часто зустрічаються кратні корені. Так як ітераційні методи, в цих випадках не гарантують отримання рішення, то для визначення власних значень слід користуватися іншими ітераційними методами.

Визначення найбільшого власного значення методом ітерацій

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

AХ = LХ.

Процедура починається з пробного нормованого вектора X (0). Цей вектор множиться зліва на матрицю A, і результат прирівнюється твору постійної (власне значення) і нормированному вектору X (0) .. Якщо вектор X (0) збігається з вектором X (0), то рахунок припиняється. В іншому випадку новий нормований вектор використовується в якості вихідного і вся процедура повторюється. Якщо процес сходиться, то постійний множник відповідає істинному найбільшому власному значенню, а нормований вектор - відповідному власному вектору. Швидкість збіжності цього ітераційного процесу залежить від того наскільки вдало обраний початковий вектор. Якщо він близький до істинного власному вектору, то ітерації сходяться дуже швидко. На швидкість збіжності впливає також і ставлення величин двох найбільших власних значень. Якщо це відношення близьке до одиниці, то збіжність виявляється повільної.

Рис. 1. Блок-схема алгоритму іітераціонного методу розв'язання задач на власні значення.

Приклад 1

Досліджуємо тривісне напружений стан елемента тіла, представленого на малюнку 2. Матриця напруг для нього має вигляд

 10 5 червня

 5 20 4 * 106 Н / м2

 6 30 квітня

Малюнок 2.Трехосное напружений стан елемента тіла.

Якщо виходити з того, що руйнування відбудеться при максимальній напрузі, то необхідно знати величину найбільшого головного напруги, яка відповідає найбільшому власному значенню матриці напруг. Для знаходження цієї напруги скористаємося методом ітерації Нижче наведена програма для ЕОМ, за допомогою якої итерационная процедура здійснюється до тих пір, поки різниця між власними значеннями, обчисленими в послідовних ітераціях, чи не стане менше 0,01%. У програмі використані дві підпрограми - GMPRD з пакету програм для наукових досліджень фірми IВМ, що служить для перемноження матриць і NORML, нормується власні вектори по найбільшому елементу.

{************************************************* *********************}

Програма визначення власних значень Програма дозволяє визначити найбільшу головне напруга (власне значення) для даного трехосного напруженого стану. Застосовується метод ітерацій. Рахунок припиняється, коли зміна власного значення стає менше 0,01 відсотка або число ітерацій перевищує 50.

{************************************************* *********************}

DIMENSION S (3,3), X (3), R (3)

S (1,1) = 10.E06

S (1,2) = 5.ЕО6

S (2,1) = S (1,2)

S (1,3) = 6.E06

S (3,1) = S (1,3)

S (2,2) = 20.E06

S (2,3) = 4.E06

S (3,2) = S (2,3)

S (3,3) = З0.Е06

X (1) = 1.

Х (2) = 0.0

Х (3) = 0.0

XOLD = 0.0

I = 0

WRITE (6100)

WRITE (6101)

WRITE (6102)

WRITE (6100)

WRITE (6104) I, X (1), X (2), X (3)

DO 1 січня = 1,50

CALL GMPRD (S, X, R, 3, 3, 1)

DO 2 J = 1,3

2 X (J) = R (J)

CALL NORML (XLAM, X)

WRITE (6,103) I, XLAM, X (1), X (2), X (3)

IF (ABS ((XOLD-XLAM) / XLAM) .LE.0.0001) GO TO 3

XOLD = XLAM

3 WRITE (6,100)

100 FORMAT (1X 54C'- ''))

FORMAT (2X 'ITERATION', зх 'ITERATION', 11X, 'EIGENVECTOR')

FORMAT (3X 'NUMBER ", 6X,' (N / M ** 2) ', 5X,' X (1) ',

6X, 'X (2)', 6X, 'X (3)')

103 FORMAT (1X, I5,7X, E12.5,3F10.5)

104 FORMAT (1X, I5,19X, 3F10.5)

STOP

END

{************************************************* *********************}

SUBROUTINE NORML (XL, X)

DIMENSION X (3)

{************************************************* *********************}

Підпрограма norml.

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

{************************************************* *********************}

# FIND THE LARGEST ELEMENT

XBIG = X (1)

IF (X (2) .GT.XBIG) XBIG = X (2)

IF (X (3) .GT.XBIG) XBIG = X (3)

# Нормування за XBIG

X (l) = X (1) / XBIG

X (2) = X (2) / XBIG

X (3) = X (3) / XBIG

XL = XBIG

RETURN

END

{************************************************* *********************}

Результат роботи програми отримуємо у вигляді:

 Номер

 Ітерації

 Власне

 Значення

 (N / M ** 2) Власний вектор

 X (1) X (2) X (3)

 0. 1.00000 0. 0.

 0.10000 Е 08 1,00000 0.50000 0.60000

 0.26000Е 08 0.61923 0.66923 1.00000

 0.36392Е 08 0.42697 0.56278 1.00000

 0.34813Е 08 0.37583 0.49954 1.00000

 0.34253Е 08 0.35781 0.46331 1.00000

 0.34000Е 08 0.34984 0.44280 1.00000

 0.33870Е 08 0.34580 0.43121 1.00000

 0.33800Е 08 0.34362 0.42466 1.00000

 0.33760Е 08 0,34240 0.42094 1.00000

 0.33738Е 08 0.34171 0.41884 1.00000

 0.33726Е 08 0.34132 0.41765 1.00000

 0.33719Е 08 0,34110 0.41697 1.00000

 0.33714Е 08 0.34093 0.41658 1.00000

 0.33712Е 08 0.34091 0.41636 1.00000

Відзначимо, що для досягнення необхідної точності знадобилося 14 ітерацій.

Визначення найменшого власного значення методом ітерацій

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

А-1АX = Lа-1X.

Якщо обидві частини цього співвідношення помножимо на 1 / l, то отримаємо

1 / l Х = A-1X.

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

Визначення проміжних власних значень методом ітерацій

Знайшовши найбільше власне значення, можна визначити наступне за ним по величині, замінивши вихідну матрицю матрицею, що містить лише решту власні значення. Використовуємо для цього метод, званий методом вичерпування. Для вихідної симетричною матриці A з відомим найбільшим власним значенням l1 і власним вектором X1 можна скористатися принципом ортогональности власних векторів, т. Е. Записати

ХIT Хj = 0 при i j і ХIT Хj = 1 при i = j.

Якщо утворити нову матрицю A * відповідно до формули

A * = A-l1Х1 Х1T,

то її власні значення і власні вектори будуть зв'язані співвідношенням

А * Xi = liXi.

З наведеного вище вирази для матриці A * випливає, що

A * Хi = AХi -lХ1 Х1TXi.

Тут при i = 1 властивість ортогональності дозволяє привести праву частину до виду

A Х1 - l1 Х1.

Але за визначенням власних значень матриці A це вираз повинен дорівнювати нулю. Отже, власне значення l1 матриці A * дорівнює нулю, а всі інші її власні значення збігаються з власними значеннями матриці A. Таким чином, матриця A * має власні значення 0, l2, l3 ,. . ., Ln та відповідні власні вектори Х1, Х2, Хз ,. . . .... Хn. В результаті виконаних перетворень найбільше власне значення l1 було вилучено, і тепер, щоб знайти наступне найбільше власне значення l2, можна застосувати до матриці A * звичайний ітераційний метод. Визначивши l2 і Х2, повторимо весь процес, використовуючи нову матрицю A **, отриману за допомогою A *, l2 і Х2. Хоча на перший погляд здається, що цей процес повинен швидко привести до мети, він має істотні недоліки. При виконанні кожного кроку похибки у визначенні власних векторів будуть позначатися на точності визначення наступного власного вектора і викликати нагромадження помилок. Тому описаний метод навряд чи застосуємо для знаходження більш ніж трьох власних значень, починаючи з найбільшого або найменшого. Якщо потрібно отримати більше число власних значень, слід користуватися методами перетворення подібності.

4. ВИЗНАЧЕННЯ ВЛАСНИХ ЗНАЧЕНЬ МЕТОДАМИ ПЕРЕТВОРЕНЬ ПОДОБИ

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

Метод Якобі

Метод Якобі дозволяє привести матрицю до діагонального вигляду, послідовно, виключаючи всі елементи, які стоять поза головною діагоналі. На жаль, приведення до строго діагонального вигляду вимагає нескінченно великого числа кроків, так як освіта нового нульового елемента на місці одного з елементів матриці часто веде до появи ненульового елемента там, де раніше був нуль. На практиці метод Якобі розглядають, як итерационную процедуру, яка в принципі дозволяє досить близько підійти до діагональної формі, щоб це перетворення можна було вважати закінченим. У разі симетричною матриці A дійсних чисел перетворення виконується за допомогою ортогональних матриць, отриманих в результаті обертанні в дійсній площині. Обчислення здійснюються таким чином. З вихідної матриці А утворюють матрицю A1 == Р1АР1T. При цьому ортогональна матриця Р1 вибирається так, щоб в матриці А1 з'явився нульовий елемент, що стоїть поза головною діагоналі. Потім з А1 за допомогою другої перетворюючої матриці Р2, утворюють нову матрицю A2. При цьому Р2, вибирають так, щоб в A2 з'явився ще один нульовий внедіагональний елемент. Цю процедуру продовжують, прагнучи, щоб на кожному кроці в нуль звертався найбільший внедіагональний елемент. Перетворююча матриця для здійснення зазначеної операції на кожному кроці конструюється таким чином. Якщо елемент аkl матриці Ат-1 має максимальну величину, то Рт відповідає

Pkk = Pll = cos q,

Pkl = - Plk = sin q,

Pii = 1 при i k, l, Pij = 0 при i j.

Матриця Ат буде відрізнятися від матриці Am-1 тільки рядками і стовпцями з номерами k і l. Щоб елемент аkl (m) дорівнював нулю, значення q вибирається так, щоб

2 akl (m-1)

tg 2 q = -------------------------.

akk (m-1) - all (m-1)

 k l

1

1

1

1

1

 Cos q. . . . . . sin q k

1

1

 Pm = 1

1

1

1

 - Sin q Cos q l

1

1

1

1

Значення q укладені в інтервалі

p p

- - <= Q <= -.

4 квітня

Приклад 2

Нехай потрібно знайти значення всіх головних напруг для напруженого стану, показаного на малюнку прикладу 1. Для цього необхідно знайти всі власні значення матриці напруг. Така потреба виникає, якщо конструктор замість теорії руйнування при максимальному нормальному напрузі намір користуватися якою-небудь іншою теорією руйнування. Щоб знайти всі власні значення, звернемося до методу перетворень Якобі, для реалізації якого скористаємося підпрограмою Е1GЕМ з пакету програм для наукових досліджень фірми IВМ, призначеної для симетричних матриць. Так як матриця симетрична, то вона містить лише шість різних елементів. Для економії пам'яті підпрограма ЕIGЕМ використовує матрицю 3х3 в компактній формі, при якій потрібно лише шість осередків пам'яті. Програма для вирішення даної задачі має вигляд:

{************************************************* *********************}

Програма визначення всіх головних напрузі тривісної матриці напруг.

У програмі використано підпрограма ЕIGЕМ з пакету програм для наукових досліджень фірми IВМ

{************************************************* *********************}

DIMENSION S <6), R (?) З

# Завдання матриці в компактній формі

S (1) = 10 Е06

S (2) = 5 Е06

S (3) = 20 Е06

S (4) = 6 Е06

S (5) = 4 Е06

S (6) = 30 Е06

# Визначення всіх власних значень методом Якобі

CALL EIGEN (S, R, 3,0)

# Друк власні значенні

WRITE (6,100)

WRITE (6,101) S (1), S (3), 3 (6)

100 FORMAT (1Х, 'ТНЕ EIGENVALUES ARE' ')

101 FORMAT (1X, E15.8)

STOP

END

Результат роботи програми отримуємо у вигляді:

Власні значення рівні

0.33709179E 08

0.19149061E 08

0.71417603E 07

Метод Гивенса для симетричних матриць

Метод Гивенса заснований на перетворенні подібності, аналогічному застосовуваному в методі Якобі. Однак у цьому випадку алгоритм побудований таким чином, що новоутворені нульові елементи при всіх наступних перетвореннях зберігаються. Тому метод Гивенса вимагає виконання кінцевого числа перетворень і в порівнянні з методом Якобі пов'язаний з меншими витратами машинного часу. Його єдиний недолік полягає в тому, що симетрична матриця призводить не до діагонального, а до трехдіагональной увазі. Нижче буде показано, що така форма матриці може бути досить корисною і виправдовує зусилля, витрачені на її отримання.

У разі матриці розмірності п х п метод Гивенса вимагає п - 2 основних кроків, на кожному з яких виконується ряд перетворень, число яких залежить від числа нулів, яке хочуть отримати в даному стовпці або рядку. На k-му кроці звертають в нулі елементи, які стоять поза трьох діагоналей k-го рядка і k -го стовпця, зберігаючи в той же час нульові елементи, отримані на попередніх кроках. Таким чином, перед початком k -го кроку перетворена матриця є трехдіагональной, якщо обмежитися розглядом її перших k - 1 рядків і стовпців. У міру перетворень симетрична матриця розмірності 5х5 набуває таких форм:

 * * * * *

 * * * * *

 A0 = * * * * * вихідна матриця,

 * * * * *

 * * * * *

 * * 0 0 0

 * * * * *

 A1 = 0 * * * * після першого основного кроку,

 0 * * * * складається з трьох перетворень,

 0 * * * *

 * * 0 0 0

 * * * 0 0

 A2 = 0 * * * * після другого основного кроку,

 0 0 * * * складається з двох перетворень,

 0 0 * * *

 * * 0 0 0

 * * * 0 0 після третього основного кроку,

 A3 = 0 * * * 0 складається з одного перетворення.

 0 0 * * * Тепер матриця має трехдіагональной вигляд.

 0 0 0 * *

На кожному основному кроці змінюються лише ті елементи матриці аij, які розташовані в її правій нижній (заштрихованої) частини. Таким чином на k-му кроці перетвориться тільки матриця порядку (п - k + 1), що займає правий нижній кут вихідної матриці. Ясно, що на кожній наступній стадії виконується менше число перетворень, ніж на попередній. Всього для приведення матриці до трехдіагональной увазі потрібно виконати (n2 - Зп + 2) / 2 перетворень.

Наш досвід застосування методу Гивенса показує, що можна при виконанні одного кроку перетворень звернути в нуль відразу всі елементи цілого рядка і стовпчика, що стоять поза трьох діагоналей матриці. Метод, що дозволяє виконати таке перетворення, запропонував Хаусхолдера.

Метод Хаусхолдера для симетричних матриць

Метод Хаусхолдера дозволяє привести матрицю до трехдіагональной увазі, виконавши майже вдвічі менше обчислень у порівнянні з іншими методами. Це обумовлено тим, що при його застосуванні стають нульовими відразу всі елементи рядків і стовпців, що стоять поза трьох діагоналей матриці. Метод Хаусхолдера дозволяє отримати необхідний результат швидше, ніж метод Гивенса, так як пов'язаний з виконанням меншого числа, хоча і більш складних перетворень. Це його властивість особливо яскраво проявляється стосовно великих матриць. Хоча в методі Хаусхолдера замість плоских обертанні використовуються ермітовим ортогональні перетворення матриць, трехдіагональной форма матриці, яку отримують цим методом, має ті ж власні значення, що і трехдіагональной матриця, одержувана методом Гивенса. При використанні методу Хаусхолдера на п - 2 основних кроках виконуються наступні перетворення:

Аk = РkAk-1Рk, k = 1, 2, ..., п-2,

де AО == А.

Кожна перетворююча матриця має вигляд

uk ukT

Pk = E - --------------,

2Kk2

де

ui, k = 0 при i = 1, 2, ..., k,

ui, k = ak, i при i = k + 2, ..., n,

uk + 1, k = ak, k + 1 ± Sk.

Тут

n 1/2

Sk = S a2k, i

i = k + 1

2K2k = S2k ± ak, k + 1 Sk.

У цих рівняннях береться знак, відповідний елементу ak, k + 1. Це дозволяє зробити значення іk + 1, k максимальним. Відзначимо, що методами Гивенса і Хаусхолдера можна користуватися і в разі несиметричних матриць, приводячи їх, правда, не до трехдіагональной, а іншому приватному увазі трикутної матриці відомої як матриця Гессенберга:

 * * 0 0 0 0

 * * * 0 0 0

 * * * * 0 0

 * * * * * 0

 * * * * * *

 * * * * * *

5. ВИЗНАЧЕННЯ ВЛАСНИХ ЗНАЧЕНЬ симетрично трехдіагональной МАТРИЦІ

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

dеt (А-lE) = 0,

де А - симетрична трехдіагональной матриця. Раcкрив вираз в дужках, отримаємо

 a1 - l b2 0

 b1 a2 - l = 0

 bn

 0 bn an - l

Довільний визначник порядку п можна виразити через п миноров порядку п - 1, кожен з яких в свою чергу виражається через п - 1 миноров порядку п - 2. Зручність трехдіагональной форми в тому, що на кожному кроці все мінори, крім двох, виявляються рівними нулю . В результаті вихідний визначник представляється послідовністю поліномів

fm (l) = (am - l) fm-1 (l) - b2 m fm-2 (l).

Прийнявши

f0 (l) = 1 і f1 (l) = a1 - l при r = 2, .... п,

отримаємо сукупність поліномів, відому як послідовність Штурма і що володіє тим властивістю, що коріння полінома fj (l) розташовуються між країнами полінома fj + 1 (l). Тому для f1 (l) = a1- l можна стверджувати, що значення lк = а1 укладена між країнами полінома f2 (l) == (a2 - l) (a1 - l) -b22. Це полегшує ітераційне визначення коренів полінома, так як якщо відомі межі інтервалів, в яких лежать значення коренів полінома, то їх можна знайти методом половинного ділення. Так послідовно знаходять коріння всіх поліномів, і останній з них fn (l) дає всі шукані п власні значення. Цю процедуру можна проілюструвати графічно (див. Рис. 3).

Послідовність Штурма має ще й такою властивістю: для будь-якого значення b, при якому fn (b) 0, число власних значень матриці A, великих b, дорівнює числу змін знака послідовності

1, f1 (b), f2 (b), ..., (1) n fn (b).

Якщо ціле число, рівне числу змін знака, позначити через V (b), то число власних значень в інтервалі дійсних чисел [b, с] дорівнюватиме V (b) -V (c).

 Корінь многочлена

 f 1 (l)

 f 1 (b)

 Корені многочлена

 f 2 (l)

 f 1 (b)

 Корені многочлена

 f 3 (l)

 f 1 (b)

.......................................................................................................................

 Корені многочлена

 f n - 1 (l)

 f 1 (b)

 Корені многочлена

 f n (l)

 f 1 (b)

Рис. 3. Ітераційне визначення коренів полінома

6. ІНШІ МЕТОДИ ОБЧИСЛЕННЯ ВЛАСНИХ ЗНАЧЕНЬ

У цьому розділі ми розглянемо два методи визначення власних значень, що мають велике практичне значення. Обидва розроблені в останні 20 років і найбільш ефективні в тих випадках, коли потрібно знайти всі власні значення довільної матриці дійсних чи комплексних чисел. В обох використовуються перетворення, що дозволяють отримати послідовність подібних матриць, сходящуюся до матриці блокової трикутної форми:

 X1 * ... ... * * *

 x2 * ... ... * * *

 x3 ... ... * * *

 ... ... * * *

 ... * * *

 ... * *

 0 ... *

*

де блоки Хm, являють собою матриці розмірності 2 х 2, розташовані на головній діагоналі. Власні значення блоків Хm, є в той же час власними значеннями вихідної матриці розмірності п x п. Така форма зручна, оскільки детермінант другого порядку блоків Хm дозволяє визначати комплексні власні значення, не вводячи комплексних елементів в остаточну матрицю. Якщо всі власні значення вихідної матриці дійсні, то в остаточному вигляді вона буде трикутної, причому власні значення будуть розташовані на діагоналі.

Метод LR

Цей метод спочатку був розроблений Рутісхаузера в 1958 р Метод заснований на представленні матриці A у вигляді добутку

А = LR,

де L - ліва трикутна матриця з одиничними діагональними елементами, а R - права трикутна. Застосовуючи перетворення подібності L-1 AR, бачимо, що,

A2 = L-1 A R = L-1 (RL) L = R L.

Отже,

Am-1 = L m-1 Rm-1,

Am = R m-1 Lm-1.

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

Метод QR

Метод QR. запропонований Френсісом в 1961 р Відповідний йому алгоритм визначається співвідношенням

Am = Q m Rm.

де Q m - ортогональна матриця, а Rm - верхня трикутна матриця. При використанні методу послідовно отримуємо

Am + 1 = Q mT Am Q m = Q mT Q m Rm Q m = Rm Q m.

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

Приклад 3

Нехай потрібно знайти всі власні значення довільної матриці розмірності 6 x 6

 2,3 4,3 5,6 3,2 1,4 2,2

 1,4 2,4 5,7 8,4 3,4 5,2

 2,5 6,5 4,2 7,1 4,7 9,3

 3,8 5,7 2,9 1,6 2,5 7,9

 2,4 5,4 3,7 6,2 3,9 1,8

 1,8 1,7 3,9 4,6 5,7 5,9

Зробимо це в два прийоми, привівши спочатку матрицю за допомогою перетворення подібності до виду Гсссенберга, потім за допомогою різновиду методу QR знайдемо власні значення. У наведеній нижче програмі використані дві підпрограми з пакету програм для наукових досліджень фірми IВМ. Підпрограма НSВС перетворює матрицю розмірності 6 x 6 до форми Гессенберга, а підпрограма АТЕIG дозволяє знайти власні значення.

{************************************************* *********************}

Програма визначення всіх власних значень довільної матриці розмірності 6х5. Використовуються підпрограми НSВС і АТЕIG з пакету програм для наукових досліджень фірми IBM

{************************************************* *********************}

DIMENSION A (6,6), RR (6), RI (6), IANA (6)

READ (5,100) ((A (I, J), J = 1,6), I = 1,6)

WRITE (6,104)

104 FORMAT (/// lX, 'THE ORIGINAL MATRIX IS AS FOLLOWS')

WRITE (6,103)

103 FORMAT (1X, 65 (-'-- '))

WRITE (6,101) ((A (I, J), J = 1,6), I = 1,6)

WRITE (6,103)

FORMAT (6 (1X, F10.5))

100 FORMAT (6F10.5)

CALL HSBG (6, A, 6)

WRITE (6,105)

105 FORMAT (/// 1X, 'THE MATRIX W HESSENBUR5 FORM IS') WRITE (6,103)

WRITE (6,101) ((A (I, J), J = 1,6), I = 1,6)

WRITE (6,103)

CALL ATEIG (6, A, RR, RI, IANA, 6)

WRITE (6,106)

FORHAT (/// 1X, 'THE EIGENVALUES ARE AS FOLLOUS')

WRITE (6,107)

107 FORMAT (1X, 23 ('-'), /, 4X, 'REAL', 12X, 'IMAG', /, 23 ('-'))

WRITE (6,102) (RR (I), PKI), I = 1,6)

WRITE (6,108)

108 FORMAT (1X, 23 ('-'))

FORMAT <2 (2X, F10.5) »

STOP

END

Результат отримуємо у вигляді

Вихідна матриця має вигляд

 2.30000 4.30000 5.60000 3.20000 1,40000 2.20000

 1.40000 2.40000 5.70000 8.40000 3.40000 5.20000

 2.50000 6.50000 4.20000 7.10000 4.70000 9.30000

 3.80000 5.70000 2.90000 1.60000 2.50000 7.90000

 2.40000 5.40000 3.70000 6.20000 3.90000 1.80000

 1.80000 1.70000 3.90000 4.60000 5.70000 5.90000

Матриця у формі Гессенберга.

 -1.13162 3.20402 -0, -0.05631 3.88246 1.40000 2.20000

 -0.75823 0.07468 0, 0.48742 6.97388 5.37А35 10.36283

 0. 1.13783 -2, -2.63803 10.18618 7.15297 17.06242

 0. 0. 3.35891 7. 50550 7.09754 13.92154

 0. 0. 0. 13.36279 10.58947 16.78421

 0. 0. 0. 0. 5.70000 5.90000

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

-----------------------------------

Действит. Мінім.

-----------------------------------

 25.52757 0.

 -5.63130 0.

 0.88433 3.44455

 0.88433 -3.44455

 -0.68247 1.56596

 -0.68247 -1.56596

7. ВИБІР алгоритму розв'язання задачі НА ВЛАСНІ ЗНАЧЕННЯ

Вибір відповідного алгоритму для вирішення тієї чи іншої задачі на власні значення визначається типом власних значень, типом матриці і числом шуканих власних значень. Чим складніше завдання, тим менше число алгоритмів, з яких можна вибирати. Таблиця 1 дозволяє полегшити цей вибір. Зазвичай пакети математичного забезпечення ЕОМ містять підпрограми, в яких використовуються всі ці алгоритми або деякі з них. Одним з ефективних способів використання наявного математичного забезпечення є одночасне застосування двох підпрограм, що дозволяє поєднати їх найкращі якості. Наприклад, маючи матрицю загального вигляду, можна методом Хаусхолдера звести її до виду Гессенберга, а потім за допомогою алгоритму QR знайти власні значення. При цьому будуть використані як швидкість, що забезпечується методом Хаусхолдера, так і універсальність алгоритму QR.

Таблиця 1 Вибір алгоритму розв'язання задачі на власні значення

 Назва алгоритму Застосовується для Результат

 Рекомендується для

 відшукання власних значень Примітка

 Найбільшого або найменшого Всіх <= 6 Всіх> = 6

 Визначник (ітерація) Матриць загального вигляду Власні значення * Вимагає знаходження коренів полінома загального вигляду

 Ітерація

 (Ітерація) Те ж Власні значення і власні вектори * * * Забезпечує найкращу точність для найбільшого і найменшого власних значень

 Метод Якобі (перетворення) Симетричних матриць Діагональна форма матриці * * Теоретично вимагає нескінченного числа кроків

 Метод Гивенса

 (Перетворення) Те ж Трехдііональльная форма матриці * * Вимагає знання коренів простого полінома

 Несиметричних матриць Форма Гессенберга * * Вимагає застосування додаткового методу

 Метод Хаусхолдера (перетворення) Симетричних матриць трехдіагональной форма матриці * * Вимагає знання коренів простого полінома

 Метод Хаусхолдера (перетворення) несиметричних матриць Форма Гессенберга * * Вимагає застосування додаткового методу

 Метод LR (перетворення) Матриць загального вигляду Квазідіагональная форма матриці * * Буває нестійкий

 Метод QR (перетворення) Те ж Те ж * * Кращий метод, що володіє найбільшою спільністю

Список літератури

Для підготовки даної роботи були використані матеріали з сайту http://www.refcentr.ru/

© 8ref.com - українські реферати
8ref.com