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

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

Отже, нехай маємо деяку тридіагональну матрицю виду:

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

Позначивши головний мінор порядку матриці через і прийнявши рівним одиниці, матимемо:

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

.

Відмітимо, що для тридіагональної матриці, поліноми складають послідовність Штурма (корені таких поліномів являються дійсними та різними). Використовуючи властивості послідовності Штурма, можна визначити число коренів характеристичного полінома, значення яких являються більшим від деякого наперед заданого числа. Розглянемо, яким чином це можна зробити: нехай величини обчислюються для деякого числа . Тоді число (число знаків що збігаються у сусідніх членів цієї послідовності) дорівнює числу тих власних значень матриці , значення яких є строго більшими за значення числа . Якщо вийде так, що , то знак нуля беруть протилежний знаку значення . Зауважимо, що ніякі два послідовних значення не можуть бити рівними нулю.

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

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

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

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

Знаходження власних значень матриці методом половинного ділення — приклад:

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

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

Після цього, підставляємо ліву межу початкового інтервалу в послідовність Штурма, отримаємо:

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

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

На наступному кроці ділимо інтервал навпіл, в результаті отримуємо . Далі, провіряємо чи для даного значення виконується умова зупинки (5):

Виходячи з того, що для значення Ч умова зупинки не виконується, то для даного значення, згідно алгоритму методу половинного ділення, знову ж таки будуємо послідовність Штурма:

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

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

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

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар