Однією з найважливіших задач обчислювальної математики є створення ефективних і стійких алгоритмів знаходження власних значень матриці. Ці алгоритми обчислення власних значень можуть також знаходити власні вектори.
Власні значення і власні вектори Якщо задано квадратну матрицю над дійсними або комплексними числами, власне значення і відповідний йому кореневий вектор - це пара, що задовольняє рівності
де ненульовий вектор-стовпець, — одинична матриця, — додатне ціле, а і можуть бути комплексними, навіть якщо дійсне. Якщо , вектор просто називається власним вектором. У цьому випадку . Будь-яке власне значення матриці має простийТермін «простий» тут лиш підкреслює відмінність між «власним вектором» і «кореневим вектором». власний вектор, відповідний йому так, що якщо — найменше ціле, за якого для кореневого вектора , то буде простим власним вектором. Значення завжди можна взяти меншим або рівним . Зокрема, для всіх кореневих векторів відповідних
Для будь-якого власного значення матриці ядро складається з усіх власних векторів, відповідних , (разом з 0) і називається власним підпростором числа , а векторний підпростір складається з усіх кореневих векторів (доповнений нульовим вектором) і називається кореневим підпростором. Геометрична кратність значення є розмірністю його власного підпростору. Алгебрична кратність значення є розмірністю його кореневого підпростору. Подальші терміни пов'язані з рівністю
Тут — визначник, — всі різні власні значення матриці , а — відповідні алгебричні кратності. Функція — це характеристичний многочлен матриці . Отже, алгебрична кратність є кратністю власних значень як коренів характеристичного многочлена. Оскільки будь-який власний вектор є кореневим вектором, геометрична кратність менша або дорівнює алгебричній кратності. Сума алгебричних кратностей дорівнює степеню характеристичного многочлена. Рівняння називають характеристичним рівнянням, оскільки його корені є точно власними значеннями матриці . В теоремі Гамільтона — Келі сама матриця задовольняє тому самому рівнянню: де сталий член множиться на одиничну матрицю .. Як наслідок, стовпці матриці мають бути або 0, або кореневими векторами, відповідними власному значенню , оскільки вони знищуються матрицею
Будь-який набір кореневих векторів різних власних значень лінійно незалежний, так що базис для всього можна вибрати з набору кореневих векторів. Точніше цей базис можна вибрати і вибудувати так, що
якщо і мають одне і те саме власне значення, то це виконуватиметься для будь-якого при між і ; якщо не є простим власним вектором і якщо — його власне значення, то (зокрема має бути простим власним вектором).
Якщо ці базисні вектори розташувати як стовпці матриці , то можна використовувати для перетворення матриці в її нормальну жорданову форму:
де — власне значення, якщо і в інших випадках.
Якщо є оборотною матрицею і — власне значення матриці з відповідним кореневим вектором , то . Отже, є власним значенням матриці з відповідним кореневим вектором . Таким чином, подібні матриці мають однакові власні значення.
Нормальні, ермітові і дійсні симетричні матриці Ермітово-спряжена матриця до комплексної матриці — це транспонована матриця із заміною всіх елементів спряженими значеннями: . Квадратну матрицю називають нормальною, якщо вона комутує з ермітово-спряженою: . Матрицю називають ермітовою, якщо вона дорівнює своїй спряженій: . Всі ермітові матриці нормальні. Якщо має тільки дійсні елементи, то спряжена до неї — це просто транспонована матриця і вона буде ермітовою в тому і тільки в тому випадку, коли вона симетрична. Якщо застосувати це до стовпців, спряженість можна використовувати для визначення канонічного скалярного добутку в : Такому порядку в скалярному добутку (зі спряженим елементом ліворуч) надають перевагу фізики. Алгебристи часто застосовують запис .. Нормальні, ермітові і дійсні симетричні матриці мають низку корисних властивостей:
Кожен кореневий власний вектор нормальної матриці є простим власним вектором. Будь-яка нормальна матриця подібна до діагональної, оскільки її нормальна жорданова форма є діагональною матрицею. Власні вектори, відповідні різним власним значенням нормальної матриці, ортогональні. Для будь-якої нормальної матриці має ортонормальний базис, що складається з власних векторів матриці . Відповідна матриця власних векторів є унітарною. Власні значення ермітової матриці є дійсними числами, оскільки для ненульового власного вектора . Якщо матриця дійсна, існує ортонормальний базис для , що складається з власних векторів матриці , в тому і тільки в тому випадку, коли симетрична.
Як дійсні, так і комплексні матриці, які не є при цьому ермітовими матрицями, можуть мати всі власні значення дійсними. Наприклад, дійсна трикутна матриця має всі свої власні значення на діагоналі, але, в загальному випадку, не симетрична.
Число обумовленості Будь-яку задачу обчислювальної математики можна розглядати як обчислення деякої функції від деякого аргументу . Число обумовленості задачі — це відношення відносної похибки результату обчислення до відносної похибки параметра функції і залежить як від функції, так і від параметра. Число обумовленості описує, наскільки зростає похибка під час обчислень. Десятковий логарифм цього числа говорить про кількість знаків, які ми втрачаємо відносно вихідних даних. Число обумовленості стосується найкращого сценарію, відбиваючи нестабільність самої задачі, незалежно від способу розв'язування. Ніякий алгоритм не може дати результату кращого, ніж визначений числом обумовленості, хіба що випадково. Однак погано розроблений алгоритм може дати істотно гірші результати. Наприклад, як буде згадано нижче, задача знаходження власних значень нормальної матриці завжди добре обумовлена, проте задача знаходження коренів многочлена може бути . Такі алгоритми обчислення власних значень, які працюють шляхом знаходження коренів характеристичного многочлена, можуть виявитися погано обумовленими, навіть якщо сама задача добре обумовлена.
Для задачі розв'язування системи лінійних рівнянь , де є оборотною, число обумовленості визначається виразом , де — операторна норма, підпорядкована звичайній евклідовій нормі на . Оскільки це число не залежить від і є тим самим як для , так і для , його зазвичай називають числом обумовленості матриці . Це значення є також абсолютним значенням відношення найбільшого власного значення матриці до її найменшого власного значення. Якщо є унітарною, то , так що . У загальному випадку для матриць часто складно обчислити операторну норму. З цієї причини для оцінення числа обумовленості зазвичай використовують інші норми матриці.
Для задачі обчислення власних значень , що якщо є власним значенням діагоналізовної матриці з матрицею власних векторів , то абсолютна похибка обчислення обмежена добутом і абсолютною похибкою в : . Як наслідок, число обумовленості для обчислення дорівнює . Якщо матриця нормальна, то є унітарною і . Таким чином, задача обчислення власних значень нормальних матриць добре обумовлена.
Показано, що число обумовленості задачі обчислення власного підпростору нормальної матриці , відповідного власного значення , обернено пропорційне мінімальній відстані між та іншими, відмінними від , власними значеннями матриці . Зокрема, задача визначення власного підпростору для нормальних матриць добре обумовлена для ізольованих власних значень. Якщо власні значення не ізольовані, найкраще, на що можна розраховувати, це визначення підпростору всіх власних векторів довколишніх власних значень.
Алгоритми Будь-який нормований многочлен є характеристичним многочленом супутньої матриці, тому алгоритм для обчислення власних значень можна використовувати для знаходження коренів многочленів. Теорема Абеля — Руффіні показує, що будь-який такий алгоритм для розмірності більшої від 4 має або бути нескінченним, або залучати функції складніші, ніж елементарні арифметичні операції або дробові степені. З цієї причини алгоритми, які обчислюють точно власні значення за скінченне число кроків, існують тільки для спеціальних класів матриць. У загальному випадку алгоритми є ітеративними і дають на кожній ітерації чергове наближення до розв'язку.
Деякі алгоритми дають усі власні значення, інші дають кілька значень або навіть всього одне, однак і ці алгоритми можна використовувати для обчислення всіх власних значень. Як тільки власне значення матриці визначено, його можна використовувати або для зведення алгоритму до отримання іншого власного значення, або для зведення задачі до такої, для якої не є розв'язком.
Зведення зазвичай виконують зсувом: замінюється на для деякої константи . Щоб отримати власне значення матриці , потрібно власне значення, знайдене для , додати до . Наприклад, у степеневому методі . Ітерація степеневого методу знаходить найбільше за абсолютною величиною значення, так що навіть якщо є наближенням до власного значення, ітерація степеневого методу навряд чи знайде його вдруге. І навпаки, методи, засновані на зворотних ітераціях знаходять найменше власне значення, так що вибирається подалі від в надії опинитися ближче до якогось іншого власного значення.
Зведення можна виконати звуженням матриці до простору стовпців матриці . Оскільки вироджена, простір стовпців має меншу розмірність. Алгоритм обчислення власних значень можна тоді застосувати до цієї звуженої матриці. Процес можна продовжувати, поки не буде знайдено всі власні значення.
Якщо алгоритм знаходження власних значень не дає власного вектора, поширеним є застосування алгоритму, заснованого на зворотній ітерації, з прирівнюванням до найближчої апроксимації власного значення. Це швидко приводить до власного вектора найближчого до власного значення. Для невеликих матриць альтернативою є використання стовпцевого підпростору добутку для кожного з решти власних значень
Матриці Гессенберга і тридіагональні матриці Оскільки власними значеннями трикутної матриці є діагональні елементи, в загальному випадку не існує скінченного методу, подібного до винятків Гауса, для зведення матриці до трикутної форми, зберігаючи при цьому власні значення, однак можна отримати щось близьке до трикутної матриці. Верхня матриця Гессенберга — це квадратна матриця, в якій усі елементи нижче від першої піддіагоналі дорівнюють нулю. Нижня матриця Гессенберга — це квадратна матриця, в якій усі члени вище від першої наддіагоналі дорівнюють нулю. Матриці, які є як нижніми, так і верхніми матрицями Гессенберга — це тридіагональні матриці. Матриці Гессенберга і тридіагональні матриці є початковими для багатьох алгоритмів обчислення власних значень, оскільки нульові значення зменшують складність задачі. Існує кілька методів зведення матриць до матриць Гессенберга з тими ж власними значеннями. Якщо початкова матриця симетрична або ермітова, то кінцева матриця буде тридіагональною.
Якщо потрібні тільки власні значення, не потрібно обчислювати матрицю подібності, оскільки перетворена матриця має ті самі власні значення. Якщо також потрібні і власні вектори, матриця подібності необхідна для перетворення власних векторів матриці Гессенберга на власні вектори початкової матриці. МетодЗастосовний до матрицьРезультатЦіна без матриці подібностіЦіна з матрицею подібностіОписПеретворення Хаусхолдеразагального виглядуматриця ГессенбергаВідбиття кожного стовпця відносно підпростору для обнулення нижніх елементів стовпцяПовороти Ґівенсазагального виглядуматриця ГессенбергаЗдійснюється плоске обертання для обнулення окремих елементів. Обертання впорядковані так, що наступні обертання не зачіпають нульових елементівІтерації Арнольдізагального виглядуматриця ГессенбергаЗдійснюється ортогоналізація Грама — Шмідта на підпросторах Криловаермітоватридіагональна матрицяІтерації Арнольді для ермітових матриць
Ітеративні алгоритми