Choliy.NumericaMethods.2011Dec01

51

6. Власнi числа та вектори

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

Власнi числа λi та вiдповiднi їм власнi вектори ~xi задовольняють рiвняння:

A~xi = λi~xi, i = 1, . . . , n.

Записане спiввiдношення еквiвалентне такому:

|A − λE| = 0.

Це полiномiальне рiвняння (характеристичний полiном матрицi) вiдносно λ. Воно має n коренiв, у загальному випадку - комплексних.

Бiльшiсть сучасних алгоритмiв знаходження власних чисел та векторiв використовує теорему про подiбнi матрицi.

Теорема. Перетворення матрицi виду A0 = S−1AS не змiнює власнi числа, для довiльної невиродженої матрицi S. Це також означає, що власнi числа матриць A та A0 спiвпадають.

Для доведення, запишемо.

|A0 − λE| = |S−1AS − λE| = |S−1AS − S−1λES| = |S−1(A − λE)S| = = |S−1||A − λE||S| = |A − λE|.

Властивiсть бути власним вектором iнварiантна перетворенню подiбностi. Так, якщо A~x = λ~x, i ~y = S~x, то

AS~x = λS~x, S−1AS~x = λ~x,

тобто, ~x буде власним вектором також i матрицi S−1AS.Кiнець теореми.

52

Якщо вибрати матрицю S ортогональною, то S−1AS можна замiнити на ST AS. Нехай ми знайшли таку ортогональну матрицю S, що ST AS = D, а D - дiагональна матриця. В такому випадку AS = SD. Розглянемо це останнє рiвняння детальнiше, розписавши його i позначивши вектори-стовбчики, з яких складається матриця A, додатковим верхнiм iндексом:

Цi останнi рiвняння показують, що di - власнi числа, а ~x(i) - вiдповiднi їм власнi вектори. Суть алгоритму одночасного знаходження власних значень та векторiв, таким чином, полягає в дiагоналiзацiї матрицi A за допомогою ортогональних матриць Pi, таких, що

Y

S = Pi.

i

Симетричнi матрицi мають дiйснi власнi числа. Для несиметричних дiйсних матриць це не так. Якщо ж власнi числа матрицi комплекснi, то вони попарно спряженi. Цей факт не дозволить дiагоналiзувати будь-яку матрицю, але її завжди можна буде привести до тридiагонального виду, навiть бiльше - до такого вигляду, при якому на головнiй дiагоналi розмiщуються клiтинки розмiром 1 або 2. У випадку матрицi загального виду навiть тридiагонального вигляду досягти не завжди вдається. Тому матрицi загального виду приводять до канонiчної форми Хессенберга: верхньої трикутної з одною додатковою дiагоналлю зразу пiд головною. Це сильно зменшує кiлькiсть подальших обчислень.

Метод Якобi. Розглянемо матрицю Ppq, таку, що утворена з одиничної, але на перетинах p-х та q-х рядочкiв та стовбчикiв записується клiтинка

53

Приклад такої матрицi наведено нижче:

Ця матриця ортогональна, що легко перевiряється множенням. Далi:

54

Скористаємось цими формулами для того, щоб обнулити саме цi недiагональнi елементи. У випадку симетричної матрицi це приведе до обнулення зразу обидвох елементiв, якщо ж матриця несиметрична, зосередимось на елементi, що знаходиться пiд дiагоналлю, тобто покладемо a0qp = 0. У такому випадку

cs(app − aqq) + c2aqp − s2apq = 0,

а пiсля приведення

c2 − s2 = aqq − app . 2cs 2apq

Тепер пригадаємо, що створена на основi c та s матриця є клiтинкою елементарної матрицi повороту, а c та s мають смисл косинуса та синуса кута. Тому цiлком можливо переписати останню рiвнiсть так:

Введемо позначення s/c = t = tan (α/2), тодi з попереднього рiвняння:

55

√

Iз знайдених значень t отримуєм c = 1/ t2 + 1, s = tc, взявши той корiнь, що вiдповiдає куту, меншому, нiж π/2. Метод Якобi дозволяє дiагоналiзувати довiльну симетричну матрицю, отже знайти одночасно її власнi числа та власнi вектори, якщо методично, крок за кроком обнуляти недiагональнi елементи, вiдповiдно пiдбираючи матрицi-множники. Цей процес виключення елементiв iтерацiйний, якщо в процесi роботи деякi елементи знову стали ненульовими, то їх потрiбно обнулити ще раз.

Метод Крилова. Цей метод оснований на використаннi теореми Келi-Гамiль- тона, згiдно з якою будь-яка матриця задовольняє своєму характеристичному

полiному:

An + p1An−1 + p2An−2 + · · · + pn−1A + pnE = 0,

де pi - коефiцiєнти характеристичного полiнома D(λ) = |A − λE|. Вiзьмемо довiльний ненульовий вектор ~y(0) i домножимо його справа на характеристичний полiном:

An~y(0) + p1An−1~y(0) + p2An−2~y(0) + · · · + pn−1A~y(0) + pnE~y(0) = 0.

Нехай тепер

~y(k) = Ak~y(0), ~y(k) = A~y(k−1),

тобто

~y(n) + p1~y(n−1) + p2~y(n−2) + · · · + pn−1~y(1) + pn~y(0) = 0,

або

Це система лiнiйних рiвнянь вiдносно pi, розв’язок якої дасть коефiцiєнти характеристичного полiнома. Знайдений характеристичний полiном D(λ)

n

Y

D(λ) = λn + p1λn−1 + p2λn−2 + · · · + pn−1λ + pn = (λ − λi),

i=1

треба факторизувати, тобто знайти всi його коренi, якi i будуть власними числами.

Знаючи коренi, перейдемо до знаходження власних векторiв. Надалi власнi вектори позначенi буквою ~x. Розкладемо вектори, використанi нами для

56

знаходження характеристичного полiнома, за власними векторами:

~y(0) = c1~x(1) + c2~x(2) + c3~x(3) + · · · + cn~x(n).

~y(1) = A~y(0) = c1A~x(1) + c2A~x(2) + c3A~x(3) + · · · + cnA~x(n) = = c1λ1~x(1) + c2λ2~x(2) + c3λ3~x(3) + · · · + cnλn~x(n).

Далi аналогiчно:

~y(2) = A~y(1) = c1λ21~x(1) + c2λ22~x(2) + c3λ23~x(3) + · · · + cnλ2n~x(n),

i навiть

~y(k) = c1λk1~x(1) + c2λk2~x(2) + c3λk3~x(3) + · · · + cnλkn~x(n).

Вiзьмемо тепер набiр n довiльних полiномiв:

ϕi(λ) = λn−1 + q1,iλn−2 + q2,iλn−1 + · · · + qn−2,iλ + qn−1,i,

i утворимо лiнiйнi комбiнацiї векторiв ~y( ) з коефiцiєнтами, рiвними коефiцiєнтам полiномiв:

~y(n−1) + q1,i~y(n−2) + q2,i~y(n−3) + q3,i~y(n−4) + · · · + qn−2,i~y(1) + qn−1,i~y(0) =

=c1λn1−1~x(1) + c2λ2n−1~x(2) + · · · + cnλnn−1~x(n)+ +c1q1iλn1−2~x(1) + c2q1iλn2−2~x(2) + · · · + cnq1iλnn−2~x(n)+

+c1q2iλn1−3~x(1) + c2q2iλn2−3~x(2) + · · · + cnq2iλnn−3~x(n) + · · · =

=c1(λn1−1 + q1iλn1−2 + q2iλn1−3 + . . . )~x(1)+ +c2(λn1−1 + q1iλn1−2 + q2iλn1−3 + . . . )~x(2)+

+ · · · =

=c1ϕi(λ1)~x(1) + c2ϕi(λ2)~x(2) + · · · + cnϕi(λn)~x(n).

Як полiном ϕi(λ) виберемо:

ϕi(λ) = D(λ)/(λ − λi).

Тут очевидно

ϕi(λj) = 0, i 6= j, ϕi(λi) = D0(λi) 6= 0.

Пiдставимо i приведемо подiбнi, маємо (оскiльки з кожної суми у правiй частинi рiвнянь залишається лише один доданок ϕi(λi)):

ciϕi(λi)~x(i) = ~y(n−1) + q1,i~y(n−2) + · · · + qn−1,i~y(n).

57

Таким чином, лiнiйна комбiнацiя векторiв ~y( ) дає значення власного вектора з точнiстю до множника. Коефiцiєнти qj,i знаходяться так:

q01 = 1,

qji = λiqj−1,i + pj.

Випадок комплексної ермiтової матрицi. Як вiдомо з курсу алгебри, ермiтова матриця - це комплексна версiя дiйсної симетричної матрицi. Власнi числа та вектори такої комплексної матрицi можна шукати звичайними методами, однак саме в цьому випадку можна запропонувати звести задачу з комплексними коефiцiєнтами до задачi з дiйсними.

Нехай матриця A = C +iB, де C та B - вiдповiдно дiйсна та уявна частини матрицi. Оскiльки матриця ермiтова, то CT = C, BT = −B. Нехай також ~x = ~u + i~v - власний вектор, а λ - дiйсне власне число. Рiвняння для знаходження власних чисел

A~x = λ~x,

запишемо так:

(C + iB)(~u + i~v) = λ(~u + i~v),

або в виглядi двох систем:

C~u − B~v = λ~u

B~u + C~v = λ~v,

або навiть у матричному виглядi:

Усi елементи такої системи рiвнянь - дiйснi числа, тож до неї можна використовувати методи знаходження власних чисел та векторiв, придатнi для дiйсних матриць. Власними векторами будуть ~u + i~v чи −(~u + i~v).

58

Задачi. У всiх задачах цього роздiлу потрiбно знайти всi власнi числа та

59

60