Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі

• Date: 2020
• Main Authors: Хіміч, О.М., Сидорук, В.А., Нестеренко, А.Н.
• Format: Article
• Language: Ukrainian
• Published: Інститут програмних систем НАН України 2020
• Series: Проблеми програмування
• Subjects: Теоретичні та методологічні основи програмування
• Online Access: http://dspace.nbuv.gov.ua/handle/123456789/180466
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі / О.М. Хіміч, В.А. Сидорук, А.Н. Нестеренко // Проблеми програмування. — 2020. — № 2-3. — С. 208-217. — Бібліогр.: 10 назв. — укр.

Системи нелінійних рівнянь часто виникають при моделюванні процесів різної природи. Це можуть бути як самостійні задачі, що описують фізичні процеси, так і задачі, що виникають на проміжному етапі вирішення складніших математичних задач. Зазвичай це задачі великих порядків з великою кількістю невідомих, які краще враховують локальні особливості процесу або явища, що моделюється. Крім того, більш точні дискретні моделі дозволяють отримати більш точні розв’язки. Зазвичай матриці таких задач мають розріджену структуру. Часто структура розріджених матриць є однією з наступних: стрічкова, профільна, блочно-діагональна з обрамленням і т. д. У багатьох випадках матриці дискретних задач є симетричними і додатно визначеними або напіввизначеною. Розв’язання систем нелінійних рівнянь здійснюється в основному ітераційними методами на основі методу Ньютона, який має високу швидкість збіжності (квадратичну) поблизу розв’язку за умови, що початкове наближення лежить в області гравітації розв’язку. В цьому випадку метод вимагає на кожній ітерації обчислення матриці Якобі і подальшого розв’язання систем лінійних алгебраїчних рівнянь. Як наслідок, складність однієї ітерації дорівнює . Використання паралельних обчислень на етапі розв’язання систем лінійних алгебраїчних рівнянь значно прискорює процес знаходження розв’язку систем нелінійних рівнянь. У роботі запропоновано новий метод розв’язання систем нелінійних рівнянь високого порядку з блочною матрицею Якобі. Основою нового методу є об'єднання класичного алгоритму методу Ньютона з ефективним дрібно-плитковим алгоритмом для розв’язання систем лінійних рівнянь з розрідженими матрицями. Наведено часи розв’язання систем нелінійних рівнянь різних порядків на вузлах суперкомп'ютера СКІТ.