РОЗДІЛ 2
АЛГОРИТМИ РОЗВ'ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ З ТЕПЛІЦЕВИМИ ?-МАТРИЦЯМИ ДЛЯ ПОСЛІДОВНИХ МОДЕЛЕЙ ОБЧИСЛЕНЬ, ОЦІНКИ ЇХ ХАРАКТЕРИСТИК
2.1. Алгоритми знаходження матриці, оберненої до тепліцевої матриці з алгебраїчними поліноміальними елементами
Розглянемо клас задач розв'язування систем лінійних алгебраїчних рівнянь з тепліцевими ?-матрицями вигляду (1.1), де елементи ?-матриці та вектора є алгебраїчними поліномами степеня .
Значення для ? та коефіцієнти алгебраїчних многочленів беруться з деякого поля так, що елементи матриці обчислюються для деякого часткового значення ?, наприклад .
Для розв'язування таких СЛАР з тепліцевими ?-матрицями виникає потреба знаходження матриці , оберненої до .
Знаходження матриці, оберненої до довільної тепліцевої ?-матриці.
Використовуючи наведені в розділі 1 результати, побудуємо аналог швидкого алгоритму [39] знаходження оберненої до дійсної матриці на випадок тепліцевої ?-матриці. Ідея полягає в обчисленні першого та останнього стовпців оберненої матриці без відшукання інших її елементів. Позначимо через вектори та , відповідно перший та останній стовпці оберненої матриці для кожної з відсічених систем ,. Алгоритм базується на наступній лемі.
ЛЕМА 2.1. Нехай і тепліцеві матриці і невироджені. Тоді невиродженість матриці необхідна і достатня для того, щоб кожен із стовпців , виражався у вигляді лінійної комбінації стовпців .
Наслідок з леми 2.1. В умовах леми 2.1 стовпці лінійно незалежні і коефіцієнти лінійних комбінацій, які представляють , , виражаються однозначно.
Головним наслідком з леми 2.1 є можливість рекурентного обчислення вектор-стовпців , .
Алгоритм () для відшукання оберненої до тепліцевої ?-матриці.
Запишемо формули для знаходження першого та останнього стовпців оберненої матриці [21]
для ,
для
, ,
, (2.1)
,
.
Теоретично в (2.1) є лише одне місце алгоритму, яке може привести до похибки (ділення на нуль). Це операція ділення, яка визначає величину . Але за лемою 2.1 помилка (теоретично) неможлива, якщо в матриці будуть відмінними від нуля всі ведучі мінори. При цьому гарантується, що для будь-якого k.
Після того, як знайдено перший та останній стовпці оберненої матриці, можна повністю відтворити за такою схемою [21]
Для ілюстрації розглянемо застосування цього алгоритму до тепліцевої матриці третього порядку з поліноміальними елементами.
Приклад 2.1. Задана матриця
. (2.3)
Знайти обернену до неї.
Розв'язування. Застосуємо алгоритм (2.1) до матриці (2.3).
для ,
для ,
,
, ,
, ,
;
для ,
,
,
,
,
.
Для матриці (2.3) запишемо обернену за формулою (2.2)
Безпосередньою перевіркою можна переконатись, що ця матриця є оберненою до матриці (2.3).
Алгоритм з нормуванням () для відшукання оберненої до тепліцевої ?-матриці.
Існує можливість і більш економічної реалізації наведеного алгоритму [21]. За допомогою нормування стовпців, що обчислюються, завжди можна досягти того, щоб один з коефіцієнтів у лінійній комбінації дорівнював 1. При цьому доведеться обчислювати не стовпці та безпосередньо, а деякі інші, колінеарні до них, разом з відповідними нормувальними множниками. Тоді на кожному кроці буде виконуватись менше число множень, а кількість операцій додавання-віднімання не зміниться [39].
Здійснювати нормування можна по-різному [21]. При початкові нормувальні множники взагалі можуть бути будь-якими, відмінними від 0. Деяка довільність може відповідати вибору одного з коефіцієнтів лінійної комбінації, який стане одиницею.
Нехай на k-ому кроці обчислюються вектор-стовпці
,
і нормувальні множники що їм відповідають і забезпечують виконання співвідношень
. (2.4)
Алгоритм з нормуванням () для відшукання оберненої до тепліцевої матриці з поліноміальними елементами можна описати так:
для ,
для
, , ,
,
(2.5)
Слід відзначити, що в процесі виконання (2.5) перші координати векторів і останні координати векторів не змінюються, тобто , для всіх k. Крім того, вибір однакових початкових нормувальних множників призводить до їх співпадання на всіх кроках алгоритму. Звичайно покладають або .
Оцінки характеристик алгоритмів і .
Обчислювальна складність алгоритму знаходження оберненої до тепліцевої ?-матриці. Підрахуємо кількість операцій, необхідних для реалізації формул (2.2) алгоритму на комп'ютері. Для обчислення кожної з величин , на k-ому кроці потрібно виконати по операцій множення та операцій додавання-віднімання. Разом це складає операцій множення та операцій додавання-віднімання. Для визначення величин , та необхідно здійснити операцій множення, операцій віднімання та операцій ділення. Щоб обчислити значення всіх , , треба виконати на кожному кроці операцій додавання-віднімання і операцій множення.
Отже, на k-ому кроці алгоритму (2.1) виконується порядку операцій множення і операцій додавання-віднімання. Тому загальні затрати складають з точністю до головного члена операцій множення і операцій додавання-віднімання. Операції ділення в головний член не входять.
Обчислювальна складність алгоритму з нормуванням знаходження оберненої до тепліцевої ?-матриці. Як бачимо, в алгоритмі (2.5) при обчисленні величин та , на кожному кроці виконується на операцій множення менше, ніж в алгоритмі без нормування. В результаті їх буде замість , як в алгоритмі (2.1).
Оцінка використаної пам'яті. Щоб реалізувати (2.1) на комп'ютері, необхідно забезпечити запам'ятовування, крім елементів початкової матриці , , двох векторів довжиною не більше n, координатами якого є поліноми степеня не вище .
Алгоритм з нормуванням () знаходження оберненої до симетричної тепліцевої ?-матриці. Нехай тепліцева матриця