Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі
Системи нелінійних рівнянь часто виникають при моделюванні процесів різної природи. Це можуть бути як самостійні задачі, що описують фізичні процеси, так і задачі, що виникають на проміжному етапі вирішення складніших математичних задач. Зазвичай це задачі великих порядків з великою кількістю невідо...
Gespeichert in:
| Veröffentlicht in: | Проблеми програмування |
|---|---|
| Datum: | 2020 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут програмних систем НАН України
2020
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/180466 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі / О.М. Хіміч, В.А. Сидорук, А.Н. Нестеренко // Проблеми програмування. — 2020. — № 2-3. — С. 208-217. — Бібліогр.: 10 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-180466 |
|---|---|
| record_format |
dspace |
| spelling |
Хіміч, О.М. Сидорук, В.А. Нестеренко, А.Н. 2021-09-29T16:40:02Z 2021-09-29T16:40:02Z 2020 Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі / О.М. Хіміч, В.А. Сидорук, А.Н. Нестеренко // Проблеми програмування. — 2020. — № 2-3. — С. 208-217. — Бібліогр.: 10 назв. — укр. 1727-4907 DOI: https://doi.org/10.15407/pp2020.02-03.208 https://nasplib.isofts.kiev.ua/handle/123456789/180466 519.6 Системи нелінійних рівнянь часто виникають при моделюванні процесів різної природи. Це можуть бути як самостійні задачі, що описують фізичні процеси, так і задачі, що виникають на проміжному етапі вирішення складніших математичних задач. Зазвичай це задачі великих порядків з великою кількістю невідомих, які краще враховують локальні особливості процесу або явища, що моделюється. Крім того, більш точні дискретні моделі дозволяють отримати більш точні розв’язки. Зазвичай матриці таких задач мають розріджену структуру. Часто структура розріджених матриць є однією з наступних: стрічкова, профільна, блочно-діагональна з обрамленням і т. д. У багатьох випадках матриці дискретних задач є симетричними і додатно визначеними або напіввизначеною. Розв’язання систем нелінійних рівнянь здійснюється в основному ітераційними методами на основі методу Ньютона, який має високу швидкість збіжності (квадратичну) поблизу розв’язку за умови, що початкове наближення лежить в області гравітації розв’язку. В цьому випадку метод вимагає на кожній ітерації обчислення матриці Якобі і подальшого розв’язання систем лінійних алгебраїчних рівнянь. Як наслідок, складність однієї ітерації дорівнює . Використання паралельних обчислень на етапі розв’язання систем лінійних алгебраїчних рівнянь значно прискорює процес знаходження розв’язку систем нелінійних рівнянь. У роботі запропоновано новий метод розв’язання систем нелінійних рівнянь високого порядку з блочною матрицею Якобі. Основою нового методу є об'єднання класичного алгоритму методу Ньютона з ефективним дрібно-плитковим алгоритмом для розв’язання систем лінійних рівнянь з розрідженими матрицями. Наведено часи розв’язання систем нелінійних рівнянь різних порядків на вузлах суперкомп'ютера СКІТ. Системы нелинейных уравнений часто возникают при моделировании процессов различной природы. Это могут быть как самостоятельные задачи, описывающие физические процессы, так и задачи, возникающие на промежуточном этапе решения более сложных математических задач. Обычно это задачи высокого порядка с большим количеством неизвестных, которые лучше учитывают локальные особенности процесса или моделируемого явления. Кроме того, более точные дискретные модели позволяют получить более точные решения. Обычно матрицы таких задач имеют разреженную структуру. Часто структура разреженных матриц является одной из следующих: ленточная, профильная, блочно-диагональная с обрамлением и т. д. Во многих случаях матрицы дискретных задач являются симметричными и положительно определеными или полуопределеными. Решение систем нелинейных уравнений осуществляется в основном итерационными методами на основе метода Ньютона, который имеет высокую скорость сходимости (квадратичную) вблизи решения при условии, что начальное приближение лежит в области гравитации решения. В этом случае метод требует на каждой итерации вычисления матрицы Якоби и дальнейшего решения систем линейных алгебраических уравнений. Как следствие, сложность одной итерации равна . Использование параллельных вычислений на этапе решения систем линейных алгебраических уравнений значительно ускоряет процесс нахождения решения систем нелинейных уравнений. В работе предложен новый метод решения систем нелинейных уравнений высокого порядка с блочной матрицей Якоби. Основой нового метода является объединение классического алгоритма метода Ньютона с эффективным мелко плиточным алгоритмом для решения систем линейных уравнений с разреженными матрицами. Приведены времена решения систем нелинейных уравнений разных порядков на узлах суперкомпьютера СКИТ. Systems of nonlinear equations often arise when modeling processes of different nature. These can be both independent problems describing physical processes and also problems arising at the intermediate stage of solving more complex mathematical problems. Usually, these are high-order tasks with the big count of un-knows, that better take into account the local features of the process or the things that are modeled. In addition, more accurate discrete models allow for more accurate solutions. Usually, the matrices of such problems have a sparse structure. Often the structure of sparse matrices is one of next: band, profile, block-diagonal with bordering, etc. In many cases, the matrices of the discrete problems are symmetric and positively defined or half-defined. The solution of systems of nonlinear equations is performed mainly by iterative methods based on the Newton method, which has a high convergence rate (quadratic) near the solution, provided that the initial approximation lies in the area of gravity of the solution. In this case, the method requires, at each iteration, to calculates the Jacobi matrix and to further solving systems of linear algebraic equations. As a consequence, the complexity of one iteration is. Using the parallel computations in the step of the solving of systems of linear algebraic equations greatly accelerates the process of finding the solution of systems of nonlinear equations. In the paper, a new method for solving systems of nonlinear high-order equations with the Jacobi block matrix is proposed. The basis of the new method is to combine the classical algorithm of the Newton method with an efficient small-tile algorithm for solving systems of linear equations with sparse matrices. The times of solving the systems of nonlinear equations of different orders on the nodes of the SKIT supercomputer are given. uk Інститут програмних систем НАН України Проблеми програмування Теоретичні та методологічні основи програмування Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі Гибридный алгоритм метода Ньютона для решения систем нелинейных уравнений с блочными матрицами Якоби Hybrid algorithm Newton method for solving systems of nonlinear equations with block Jacobi matrix Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі |
| spellingShingle |
Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі Хіміч, О.М. Сидорук, В.А. Нестеренко, А.Н. Теоретичні та методологічні основи програмування |
| title_short |
Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі |
| title_full |
Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі |
| title_fullStr |
Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі |
| title_full_unstemmed |
Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі |
| title_sort |
гібридний алгоритм методу ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями якобі |
| author |
Хіміч, О.М. Сидорук, В.А. Нестеренко, А.Н. |
| author_facet |
Хіміч, О.М. Сидорук, В.А. Нестеренко, А.Н. |
| topic |
Теоретичні та методологічні основи програмування |
| topic_facet |
Теоретичні та методологічні основи програмування |
| publishDate |
2020 |
| language |
Ukrainian |
| container_title |
Проблеми програмування |
| publisher |
Інститут програмних систем НАН України |
| format |
Article |
| title_alt |
Гибридный алгоритм метода Ньютона для решения систем нелинейных уравнений с блочными матрицами Якоби Hybrid algorithm Newton method for solving systems of nonlinear equations with block Jacobi matrix |
| issn |
1727-4907 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/180466 |
| citation_txt |
Гібридний алгоритм методу Ньютона для розв’язування систем нелінійних рівнянь з блочними матрицями Якобі / О.М. Хіміч, В.А. Сидорук, А.Н. Нестеренко // Проблеми програмування. — 2020. — № 2-3. — С. 208-217. — Бібліогр.: 10 назв. — укр. |
| work_keys_str_mv |
AT hímíčom gíbridniialgoritmmetodunʹûtonadlârozvâzuvannâsistemnelíníinihrívnânʹzbločnimimatricâmiâkobí AT sidorukva gíbridniialgoritmmetodunʹûtonadlârozvâzuvannâsistemnelíníinihrívnânʹzbločnimimatricâmiâkobí AT nesterenkoan gíbridniialgoritmmetodunʹûtonadlârozvâzuvannâsistemnelíníinihrívnânʹzbločnimimatricâmiâkobí AT hímíčom gibridnyialgoritmmetodanʹûtonadlârešeniâsistemnelineinyhuravneniisbločnymimatricamiâkobi AT sidorukva gibridnyialgoritmmetodanʹûtonadlârešeniâsistemnelineinyhuravneniisbločnymimatricamiâkobi AT nesterenkoan gibridnyialgoritmmetodanʹûtonadlârešeniâsistemnelineinyhuravneniisbločnymimatricamiâkobi AT hímíčom hybridalgorithmnewtonmethodforsolvingsystemsofnonlinearequationswithblockjacobimatrix AT sidorukva hybridalgorithmnewtonmethodforsolvingsystemsofnonlinearequationswithblockjacobimatrix AT nesterenkoan hybridalgorithmnewtonmethodforsolvingsystemsofnonlinearequationswithblockjacobimatrix |
| first_indexed |
2025-12-01T12:11:29Z |
| last_indexed |
2025-12-01T12:11:29Z |
| _version_ |
1850860209844518912 |
| description |
Системи нелінійних рівнянь часто виникають при моделюванні процесів різної природи. Це можуть бути як самостійні задачі, що описують фізичні процеси, так і задачі, що виникають на проміжному етапі вирішення складніших математичних задач. Зазвичай це задачі великих порядків з великою кількістю невідомих, які краще враховують локальні особливості процесу або явища, що моделюється. Крім того, більш точні дискретні моделі дозволяють отримати більш точні розв’язки. Зазвичай матриці таких задач мають розріджену структуру. Часто структура розріджених матриць є однією з наступних: стрічкова, профільна, блочно-діагональна з обрамленням і т. д. У багатьох випадках матриці дискретних задач є симетричними і додатно визначеними або напіввизначеною. Розв’язання систем нелінійних рівнянь здійснюється в основному ітераційними методами на основі методу Ньютона, який має високу швидкість збіжності (квадратичну) поблизу розв’язку за умови, що початкове наближення лежить в області гравітації розв’язку. В цьому випадку метод вимагає на кожній ітерації обчислення матриці Якобі і подальшого розв’язання систем лінійних алгебраїчних рівнянь. Як наслідок, складність однієї ітерації дорівнює . Використання паралельних обчислень на етапі розв’язання систем лінійних алгебраїчних рівнянь значно прискорює процес знаходження розв’язку систем нелінійних рівнянь. У роботі запропоновано новий метод розв’язання систем нелінійних рівнянь високого порядку з блочною матрицею Якобі. Основою нового методу є об'єднання класичного алгоритму методу Ньютона з ефективним дрібно-плитковим алгоритмом для розв’язання систем лінійних рівнянь з розрідженими матрицями. Наведено часи розв’язання систем нелінійних рівнянь різних порядків на вузлах суперкомп'ютера СКІТ.
Системы нелинейных уравнений часто возникают при моделировании процессов различной природы. Это могут быть как самостоятельные задачи, описывающие физические процессы, так и задачи, возникающие на промежуточном этапе решения более сложных математических задач. Обычно это задачи высокого порядка с большим количеством неизвестных, которые лучше учитывают локальные особенности процесса или моделируемого явления. Кроме того, более точные дискретные модели позволяют получить более точные решения. Обычно матрицы таких задач имеют разреженную структуру. Часто структура разреженных матриц является одной из следующих: ленточная, профильная, блочно-диагональная с обрамлением и т. д. Во многих случаях матрицы дискретных задач являются симметричными и положительно определеными или полуопределеными. Решение систем нелинейных уравнений осуществляется в основном итерационными методами на основе метода Ньютона, который имеет высокую скорость сходимости (квадратичную) вблизи решения при условии, что начальное приближение лежит в области гравитации решения. В этом случае метод требует на каждой итерации вычисления матрицы Якоби и дальнейшего решения систем линейных алгебраических уравнений. Как следствие, сложность одной итерации равна . Использование параллельных вычислений на этапе решения систем линейных алгебраических уравнений значительно ускоряет процесс нахождения решения систем нелинейных уравнений. В работе предложен новый метод решения систем нелинейных уравнений высокого порядка с блочной матрицей Якоби. Основой нового метода является объединение классического алгоритма метода Ньютона с эффективным мелко плиточным алгоритмом для решения систем линейных уравнений с разреженными матрицами. Приведены времена решения систем нелинейных уравнений разных порядков на узлах суперкомпьютера СКИТ.
Systems of nonlinear equations often arise when modeling processes of different nature. These can be both independent problems describing physical processes and also problems arising at the intermediate stage of solving more complex mathematical problems. Usually, these are high-order tasks with the big count of un-knows, that better take into account the local features of the process or the things that are modeled. In addition, more accurate discrete models allow for more accurate solutions. Usually, the matrices of such problems have a sparse structure. Often the structure of sparse matrices is one of next: band, profile, block-diagonal with bordering, etc. In many cases, the matrices of the discrete problems are symmetric and positively defined or half-defined. The solution of systems of nonlinear equations is performed mainly by iterative methods based on the Newton method, which has a high convergence rate (quadratic) near the solution, provided that the initial approximation lies in the area of gravity of the solution. In this case, the method requires, at each iteration, to calculates the Jacobi matrix and to further solving systems of linear algebraic equations. As a consequence, the complexity of one iteration is. Using the parallel computations in the step of the solving of systems of linear algebraic equations greatly accelerates the process of finding the solution of systems of nonlinear equations. In the paper, a new method for solving systems of nonlinear high-order equations with the Jacobi block matrix is proposed. The basis of the new method is to combine the classical algorithm of the Newton method with an efficient small-tile algorithm for solving systems of linear equations with sparse matrices. The times of solving the systems of nonlinear equations of different orders on the nodes of the SKIT supercomputer are given.
|