Знаходження власних значень матриці використовуючи алгоритм LU-розкладання

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

Зауваження: більш детальну інформацію про обчислення елементів матриць  і  можна знайти за посиланням Розв’язок СЛАР методом LU-факторизації.

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

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

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

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

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

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

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

Власні значення матриці – приклад знаходження:

Для деякої матриці  розмірності , знайти власні значення, з точністю , використовуючи при цьому розглянутий вище  алгоритм методу LU розкладання.

Для цього, на першому кроці, покладемо , та запишемо матрицю у вигляді добутку двох (трикутних) матриць , де:

Зауваження: елементи матриць та обчислюються за формулами (1):

Далі, скориставшись однією з формул (2) обчислюємо елементи матриці , та виконуємо перевірку умови закінчення ітераційного процесу:

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

Далі, переходимо до обчислення елементів матриці і знову-таки перевірки умови зупинки:

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

Блок-схема алгоритму знаходження власних значень матриці використовуючи алгоритм методу LU-факторизації