Застосування мішаної розрядності для розв’язування систем нелінійних рівнянь квазіньютонівськими методами
The paper deals with Quasi-Newtonian Methods for solving large-orders nonlinear equation systems. The paper proposes Dennis-More algorithm of the Quasi-Newtonian method with the usage of mixed precision arithmetic in calculation for solving mentioned nonlinear equation&...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Теми: | |
| Онлайн доступ: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/300 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Репозитарії
Physico-mathematical modeling and informational technologies| _version_ | 1867479671375921152 |
|---|---|
| author | Nesterenko, Alla Duchenko, Oleksandr |
| author_facet | Nesterenko, Alla Duchenko, Oleksandr |
| author_institution_txt_mv | [
{
"author": "Alla Nesterenko",
"institution": "м. н. с., Інститут кібернетики ім. В.М. Глушкова НАН України, пр. Академіка Глушкова, 40, 03187, Київ"
},
{
"author": "Oleksandr Duchenko",
"institution": "м. н. с., Інститут кібернетики ім. В.М. Глушкова НАН України, пр. Академіка Глушкова, 40, 03187, Київ"
}
] |
| author_sort | Nesterenko, Alla |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:31:10Z |
| description | The paper deals with Quasi-Newtonian Methods for solving large-orders nonlinear equation systems. The paper proposes Dennis-More algorithm of the Quasi-Newtonian method with the usage of mixed precision arithmetic in calculation for solving mentioned nonlinear equation systems. Mixed precision usage allows significantly reduce the time of solving mentioned nonlinear equation systems for the same number of iterations without losing the accuracy of the obtained solution. The obtained results of the numerical experiments for the solving nonlinear equation systems of various orders using mixed precision indicate a significant reduction in the time of solving the specified systems in comparison with calculations on double precision. |
| first_indexed | 2026-06-09T01:09:58Z |
| format | Article |
| fulltext |
32
doi.org/10.15407/fmmit2023.37.032
Застосування мішаної розрядності для розв’язування
систем нелінійних рівнянь квазіньютонівськими методами
Алла Нестеренко1, Олександр Дученко2
1 м. н. с., Інститут кібернетики ім. В.М. Глушкова НАН України, пр. Академіка Глушкова, 40, 03187, Київ,
e-mail: alla.nest1958@gmail.com
2 м. н. с., Інститут кібернетики ім. В.М. Глушкова НАН України, пр. Академіка Глушкова, 40, 03187, Київ,
e-mail: duchen@ukr.net
У роботі розглядаються квазіньютонівські методи розв’язання систем нелінійних рівнянь
великих порядків. Для розв’язування зазначених систем нелінійних рівнянь у роботі
пропонується алгоритм квазіньютонівського методу Деніса-Море з використанням
арифметики з мішаною розрядністю в обчисленнях. Застосування мішаної розрядності
дозволяє значно зменшити час розв’язування зазначених задач за однакову кількість
ітерацій без втрат точності отриманого розв’язку. Отримані результати чисельних
експериментів розв’язування систем нелінійних рівнянь різних порядків з використанням
мішаної розрядності свідчать про суттєве скорочення часу розв’язування зазначених
систем в порівняні з обчисленнями на подвійній розрядності.
Ключові слова: системи нелінійних рівнянь, мішана розрядність,
обернена матриця, високопродуктивні обчислення.
Вступ. При моделюванні різноманітних процесів та явищ досить часто
доводиться розв’язувати системи нелінійних рівнянь (СНР). Знаходження
розв’язку СНР може бути як самостійною задачею, так і задачею, що виникає на
проміжному етапі розв’язування більш складних математичних задач. Як
правило, це задачі надвисоких порядків, які дозволяють краще враховувати
локальні особливості процесу або явища, що моделюється особливо, якщо мова
йде про необхідність розрахунків у реальному часі. Отже, наразі виникає потреба
у створенні методів, які дозволяють швидше та ефективніше розв’язувати такі
системи. Розв’язання проблеми прискорення обчислень може бути вирішено за
рахунок виконання обчислень на довільній розрядності.
У цій роботі пропонується ефективний алгоритм, спрямований на
скорочення часу розв’язування СНР шляхом застосування мішаної розрядності.
Для розв’язування СНР поряд з методами, що базуються на методі Ньютона,
часто застосовуються квазіньютонівські методи. На відміну від метода Ньютона
квазіньютонівські методи не потребують обчислення наближеної матриці Якобі
та розв’язування системи лінійних алгебраїчних рівнянь (СЛАР) на кожній
ітерації. Натомість на початку ітераційного процесу лише один раз обчислюється
наближена матриця Якобі та матриця обернена до неї. Слід зазначити, що на
обчислення наближеної матриці Якобі, розв’язування СЛАР або знаходження
УДК 519.6
mailto:alla.nest1958@gmail.com
mailto:duchen@ukr.net
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 32-36
33
оберненої матриці Якобі витрачається значний час від загального часу
розв’язування усієї задачі. Цей час можна суттєво скоротити, якщо при
обчисленні елементів матриці Якобі і елементів матриці оберненої до неї
виконання необхідних арифметичних операцій здійснювати на одинарній (float)
розрядності, а для подальших обчислень подвійної (double) розрядності.
В даній статті розглядається квазіньютонівський метод Деніса-Море [1].
1. Постановка задачі з наближеними вихідними даними
Нехай дана система n нелінійних рівнянь
0)( xf , (1)
де Tn
T
n xfxfxfxfxxxx ,,,,,,, 2121 n-вимірний вектор
шуканого розв’язку та n-вимірна вектор-функція відповідно.
Задача (1) є деяким наближенням до точної системи нелінійних рівнянь
(x)=0, і для цих вектор-функцій виконується нерівність:
uuf
для будь-якого n-вимірного вектора u.
Для розв’язування задачі (1) задаються наступні вихідні дані: область
nibxaD iii ,,2,1, , в якій шукається розв’язок; точність отримання
наближення до розв’язку системи; початкове наближення 0x , що належить
визначеній області Dx 0 .
Нижнім індексом у формулах позначаються номери компонент векторів, а
верхнім індексом будуть позначатися номери ітерацій.
Якщо H деяке наближення до матриці Якобі системи (1)
n
jii
i
x
f
1,
, то
ітераційний процес методу Деніса–Море знаходження розв’язку при заданому
початковому наближенні можна записати у вигляді:
)( )()()()1( kk
k
kk xfBxx
, де k = 0, 1 ... – номер ітерації, (2)
)()()(
)()()()()(
)()1(
kkTk
kTkkkk
kk
yBw
BwyBw
BB
, (3)
де )1()()(
kk HB , )()1()( kkk xxw , )()1()( kkk xfxfy .
Для отримання розв’язку системи нелінійних рівнянь (1) з заданою точністю
xx k
ітераційний процес необхідно закінчувати при виконанні умови [2]
Алла Нестеренко, Олександр Дученко
Застосування мішаної розрядності для розв’зування систем нелінійних рівнянь …
34
)(k
k
B
xf
, (4)
2. Алгоритм методу Деніса–Море
Отже, при заданих вхідних даних в методі Деніса–Море на основі початкового
наближення до розв’язку обчислюється наближення до матриці Якобі і
визначається обернена до неї. Далі в ході ітераційного процесу обчислення
наближень до розв’язку системи обернена матриця Якобі лише апроксимується,
замість розв’язування СЛАР на кожній ітерації.
Отже, для знаходження розв’язку СНР пропонується наступний алгоритм:
1. Обчислюються компоненти вектор-функції 0xf .
2. Обчислюється наближена матриця Якобі H(x
(0)
) за формулою
h
xxxfxhxxf
xH nini
0
1
0
10 ),...,,...,(),...,,...,(
;
3. Обчислюється обернена матриця Якобі 0xB методом Гауса-Жордана
(далі будемо позначать 0)0( xBB );
4. Обчислюються компоненти вектора 0)0( xfB .
5. Для k = 0, 1, :
а) за формулою (2) обчислюється наступне наближення до розв’язку
1kx . Початкове значення параметру k у формулі (2) задається
рівним одиниці.
b) обчислюються компоненти вектор-функції 1kxf .
c) перевіряється умова kk xfxf 1
якщо умова виконана, то переходимо на пункт «d»;
якщо умова не виконана, то параметр k ділиться навпіл. Якщо
k/2 >10
-5
переходимо на пункт «5.а». В протилежному випадку
покладемо x
(0)
= x
(k)
і переходимо на пункт «2»;
d) перевіряється умова закінчення ітераційного процесу (4). Якщо умова
виконана, ітераційний процес закінчується. В протилежному випадку
переходимо на пункт «5.e».
e) обчислюється уточнення оберненої матриці
1kB за формулою (3);
i) обчислюються компоненти вектора 11 kk xfB . Переходимо на
пункт «5.а» і продовжуємо обчислення для наступного значення k.
6. Після завершення ітераційного процесу обчислюється похибка
отриманого наближення до розв’язку задачі з наближеними даними
відносно точного розв’язку системи з точними даними:
)(k
k Bxx ,
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 32-36
35
де x точний розв’язок точної СНР [2], а Δ похибка задання вектор-функції.
Звідси випливає, що при розв’язуванні СНР значна частина арифметичних
операцій припадає на обчислення значень вектор-функції ( fN ), обчислення
матриці Якобі ( fNn 23 ) та матриці оберненої до неї ( )( 3nO ). З метою скорочення
часу розв’язування СНР пропонується пункти 2 та 3 наведеного алгоритму
виконувати з використанням обчислень на одинарній розрядності, а решту – на
підвищеній розрядності.
Згідно з наведеними вище алгоритмами розроблено програми та проведено
наступні чисельні експерименти.
3. Апробація алгоритму
Обчислювальні експерименти по розв’язуванню СНР проводилися на вузлах
суперкомп’ютера СКІТ [3] з наступними характеристиками:
– 2 чотирьох ядерних процесори Intel Xeon 5345 з тактовою частотою
2.2 ГГц;
– інтегрований із загальним сховищем даних кластерного комплекса обсягом
200 ТБ;
– 64 ГБ оперативної пам’яті.
– гібридні вузли додатково мають 3 прискорювача NVidia Tesla M2075.
Методом Деніса-Море розв’язувалась система нелінійних рівнянь:
02122135.0
2
2
1
n
i
n
i
xnx i
n
j
j , i=1, 2, , n (5)
порядку n в області ,10001000 ixD 1,,1,0 ni ; = 10
-10
, = 10
-10
,
початкове наближення
n
i
xi
2
1
10
.
Таблиця 1
Часи розв’язування СНР при використанні різної розрядності
Порядок СНР
Час (сек.)
S
double + float double
3000 22 38 1,73
4000 52 90 1,73
5000 107 186 1,74
6000 182 319 1,75
7000 297 515 1,73
10000 835 1511 1,81
В табл. 1 представлені часи розв’язування СНР (5) різних порядків при
Алла Нестеренко, Олександр Дученко
Застосування мішаної розрядності для розв’зування систем нелінійних рівнянь …
36
використанні мішаної (double + float) розрядності та подвійної (double)
розрядності обчислень. Розв’язки для обох варіантів були отримані за однакову
кількість ітерацій без втрат точності отриманого розв’язку при використанні
мішаної розрядності. В останньому стовпчику таблиці наведено коефіцієнти
прискорення, які визначаються як відношення часу розв’язування СНР з
використанням подвійної розрядності до часу розв’язування тієї ж СНР з
використанням мішаної розрядності ( fdd TTS ).
Висновки. У роботі розглянуто розв’язання систем нелінійних рівнянь великих
порядків. Запропоновано алгоритм квазіньютонівського методу Деніса-Море з
використання мішаної розрядності. Отримані результати розв’язування СНР
різних порядків з використанням мішаної розрядності свідчать про суттєве
скорочення часу розв’язування зазначених СНР в порівняні з обчисленнями на
подвійній розрядності.
У випадку розрідженої структури матриці Якобі матриця, обернена до неї в
загальному випадку буде щільною. Не зважаючи на те, що застосування методу
Деніса-Море не є доцільним в такому випадку, використання арифметики з
мішаною розрядністю при розв’язуванні СНР іншим методом також дозволяє
підвищити ефективність обчислень без втрати точності.
Літерарура:
[1] J.E. Dennis, Jr., Jorge More. Quasi-Newton Methods, Motivation and Theory. SIAM Review. v.
19, № 1.January 1977, р. 46-89.
[2] Нестеренко А.Н., Химич А.Н., Яковлев М.Ф. Некоторые вопросы решения систем
нелинейных уравнений на многопроцессорных вычислительных системах с
распределенной памятью. Вестник компьютерных и информационных технологий, М.:
2006. № 10. С. 54 – 56.
[3] URL: http://icybcluster.org.ua.
Application of mixed precision for solving systems of nonlinear
equation by quasi-Newtonian methods.
Alla Nesterenko, Oleksandr Duchenko
The paper deals with Quasi-Newtonian Methods for solving large-orders nonlinear equation
systems. The paper proposes Dennis-More algorithm of the Quasi-Newtonian method with the
usage of mixed precision arithmetic in calculation for solving mentioned nonlinear equation
systems. Mixed precision usage allows significantly reduce the time of solving mentioned
nonlinear equation systems for the same number of iterations without losing the accuracy of the
obtained solution. The obtained results of the numerical experiments for the solving nonlinear
equation systems of various orders using mixed precision indicate a significant reduction in the
time of solving the specified systems in comparison with calculations on double precision.
Отримано 15.03.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-300 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:58Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/73/2b498a936d16c725daf582fa7a85d073.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-3002025-02-21T17:31:10Z Application of mixed precision for solving systems of nonlinear equation by quasi-Newtonian methods Застосування мішаної розрядності для розв’язування систем нелінійних рівнянь квазіньютонівськими методами Nesterenko, Alla Duchenko, Oleksandr системи нелінійних рівнянь, мішана розрядність, обернена матриця, високопродуктивні обчислення The paper deals with Quasi-Newtonian Methods for solving large-orders nonlinear equation systems. The paper proposes Dennis-More algorithm of the Quasi-Newtonian method with the usage of mixed precision arithmetic in calculation for solving mentioned nonlinear equation systems. Mixed precision usage allows significantly reduce the time of solving mentioned nonlinear equation systems for the same number of iterations without losing the accuracy of the obtained solution. The obtained results of the numerical experiments for the solving nonlinear equation systems of various orders using mixed precision indicate a significant reduction in the time of solving the specified systems in comparison with calculations on double precision. У роботі розглядаються квазіньютонівські методи розв’язання систем нелінійних рівнянь великих порядків. Для розв’язування зазначених систем нелінійних рівнянь у роботі пропонується алгоритм квазіньютонівського методу Деніса-Море з використанням арифметики з мішаною розрядністю в обчисленнях. Застосування мішаної розрядності дозволяє значно зменшити час розв’язування зазначених задач за однакову кількість ітерацій без втрат точності отриманого розв’язку. Отримані результати чисельних експериментів розв’язування систем нелінійних рівнянь різних порядків з використанням мішаної розрядності свідчать про суттєве скорочення часу розв’язування зазначених систем в порівняні з обчисленнями на подвійній розрядності. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-27 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/300 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 32-36 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 32-36 2617-5258 1816-1545 10.15407/fmmit2023.37 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/300/268 Авторське право (c) 2023 Алла Нестеренко, Олександр Дученко (Автор) |
| spellingShingle | системи нелінійних рівнянь мішана розрядність обернена матриця високопродуктивні обчислення Nesterenko, Alla Duchenko, Oleksandr Застосування мішаної розрядності для розв’язування систем нелінійних рівнянь квазіньютонівськими методами |
| title | Застосування мішаної розрядності для розв’язування систем нелінійних рівнянь квазіньютонівськими методами |
| title_alt | Application of mixed precision for solving systems of nonlinear equation by quasi-Newtonian methods |
| title_full | Застосування мішаної розрядності для розв’язування систем нелінійних рівнянь квазіньютонівськими методами |
| title_fullStr | Застосування мішаної розрядності для розв’язування систем нелінійних рівнянь квазіньютонівськими методами |
| title_full_unstemmed | Застосування мішаної розрядності для розв’язування систем нелінійних рівнянь квазіньютонівськими методами |
| title_short | Застосування мішаної розрядності для розв’язування систем нелінійних рівнянь квазіньютонівськими методами |
| title_sort | застосування мішаної розрядності для розв’язування систем нелінійних рівнянь квазіньютонівськими методами |
| topic | системи нелінійних рівнянь мішана розрядність обернена матриця високопродуктивні обчислення |
| topic_facet | системи нелінійних рівнянь мішана розрядність обернена матриця високопродуктивні обчислення |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/300 |
| work_keys_str_mv | AT nesterenkoalla applicationofmixedprecisionforsolvingsystemsofnonlinearequationbyquasinewtonianmethods AT duchenkooleksandr applicationofmixedprecisionforsolvingsystemsofnonlinearequationbyquasinewtonianmethods AT nesterenkoalla zastosuvannâmíšanoírozrâdnostídlârozvâzuvannâsistemnelíníjnihrívnânʹkvazínʹûtonívsʹkimimetodami AT duchenkooleksandr zastosuvannâmíšanoírozrâdnostídlârozvâzuvannâsistemnelíníjnihrívnânʹkvazínʹûtonívsʹkimimetodami |