Застосування паралельних обчислень при наближеному розв’язуванні однобічних матричних рівнянь

Matrix equations are widely used in optimization problems of control systems. Most often, these are the&nbsp;Ricatti and Sylvester equations, but there are other types of matrix equations. There is no general&nbsp;approach to solving problems of this type, so the development of appro...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2023
Автори:	Nedashkovska, Anastasija, Gusak, Ivan
Формат:	Стаття
Мова:	Українська
Опубліковано:	Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023
Теми:	ітераційний метод матричні рівняння однобічні поліоміальні матричні рівняння метод Хованського
Онлайн доступ:	https://www.fmmit.lviv.ua/index.php/fmmit/article/view/298
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Physico-mathematical modeling and informational technologies
Завантажити файл:

Репозитарії

Physico-mathematical modeling and informational technologies

_version_	1867479668887650304
author	Nedashkovska, Anastasija Gusak, Ivan
author_facet	Nedashkovska, Anastasija Gusak, Ivan
author_institution_txt_mv	[ { "author": "Anastasija Nedashkovska", "institution": "к. фіз.-мат. наук, доцент кафедри обчислювальної математики Львівського національного університету імені Івана Франка, м. Львів, вул. Університетська, 1," }, { "author": "Ivan Gusak", "institution": "студент кафедри обчислювальної математики Львівського національного університету імені Івана Франка, м. Львів, вул. Університетська, 1" } ]
author_sort	Nedashkovska, Anastasija
baseUrl_str	http://www.fmmit.lviv.ua/index.php/fmmit/oai
collection	OJS
datestamp_date	2025-02-21T17:31:10Z
description	Matrix equations are widely used in optimization problems of control systems. Most often, these are the&nbsp;Ricatti and Sylvester equations, but there are other types of matrix equations. There is no general&nbsp;approach to solving problems of this type, so the development of approximate solution schemes is&nbsp;actual. In one of the previous publications, Khovanskyi's method was generalized. An iterative scheme&nbsp;for solving one-sided matrix equations of the form&nbsp;XnAn+Xn-1An-1+…+X2A2+XA1+A0=0.&nbsp;is obtained.&nbsp;The publication presented a recurrent formula for calculating an approximate solution of equations in&nbsp;the form of a continued matrix fraction. Also, the convergence of the proposed method was&nbsp;investigated. In this article, a modification of the previously considered scheme is proposed. Parallel&nbsp;algorithms are applied for matrix multiplication, matrix addition operations and for finding the inverse matrix.
first_indexed	2026-06-09T01:09:56Z
format	Article
fulltext	22 doi.org/10.15407/fmmit2023.37.022 Застосування паралельних обчислень при наближеному розв’язуванні однобічних матричних рівнянь Анастасія Недашковська1, Іван Гусак2 1к. фіз.-мат. наук, доцент кафедри обчислювальної математики Львівського національного університету імені Івана Франка, м. Львів, вул. Університетська, 1, anastasiya.nedashkovska@lnu.edu.ua 2студент кафедри обчислювальної математики Львівського національного університету імені Івана Франка, м. Львів, вул. Університетська, 1, ivan.husak@lnu.edu.ua Найчастіше матричні рівняння використовуються у задачах оптимізації систем керування. Переважно це рівняння Рікатті та Сильвестра, однак зустрічаються й інші типи матричних рівнянь. Оскільки загального підходу до розв’язування задач такого типу не існує, то розробка схем наближеного розв’язування є актуальною. У одній із попередніх публікацій було узагальнено метод Хованського для побудови ітераційної схеми розв'язування однобічних матричних рівнянь вигляду 1 2 1 2 1 0=0.n n n nX A X A X A XA A      У публікації наведена рекурентна формула для обчислення наближеного розв'язку рівнянь у вигляді ланцюгового матричного дробу, досліджено збіжність запропонованого методу. У даній роботі запропонована модифікація розглянутої раніше схеми. Застосовані паралельні алгоритми множення та додавання матриць, а також знаходження оберненої матриці. Ключові слова: ітераційний метод, матричні рівняння, однобічні поліоміальні матричні рівняння, метод Хованського. Вступ. У задачах оптимізації систем керування [4], [5] чаcто виникає потреба у розв'язуванні матричних рівнянь. Однак загального підходу до розв’язування задач цього класу не існує. У роботі [7] було узагальнено метод Хованського [6] для побудови ітераційної схеми розв'язування поліноміальних матричних рівнянь. Схожу схему було застосовано до наближеного розв’язування однобічних матричних рівнянь у випадку, коли коефіцієнти рівняння розташовані праворуч [2]. 1. Обчислювальна схема методу Розглянемо однобічне поліноміальне матричне рівняння вигляду 1 2 2 1 2 2 1 0 = 0.n n n n n nX A X A X A X A XA A         (1) Тут матриці 1 2 0, , , m m n n nA A A A R     – задані коефіцієнти, m mX R  – невідомий розв’язок. У роботі [2] була запропонована схема наближеного розв’язування рівняння (1). Розглянемо її коротко. УДК 519.6 mailto:anastasiya.nedashkovska@lnu.edu.ua Фізико-математичне моделювання та інформаційні технології 2023, вип. 37, 22-26 23 Припустимо, що X – невироджена m m матриця. Введемо позначення 1 0 =Y X  . Помножимо рівність (1) зліва на 1X  і отримаємо: 1 2 3 1 2 2 1 0 0 = 0.n n n n n nX A X A X A XA A Y A          (2) Далі введемо позначення   2 1 1 1 0= =Y X Y X  і помножимо рівняння (2) зліва на 1 :X  2 3 4 1 2 2 0 1 1 0 = 0.n n n n n nX A X A X A A Y A Y A          Після  2n множень зліва на 1X  рівняння (1) отримаємо 2 1 2 0 3 5 2 4 1 3 0 = 0,n n n n n n nX A XA A Y A Y A Y A Y A            (3) де       1 2 2 1 1 1 0 1 3= , = , , = . n nY X Y X Y X      Введемо параметри, деякі невироджені матриці , m mL K R  . Легко бачити, що рівняння (3) еквівалентне 2 1 2 0 3 5 2 4 1 3 0 = 0.n n n n n n nX A L XA L XK XK A L Y A L Y A L Y A L Y A L              Звідси, припускаючи, що  det 0nXA L K  , отримуємо:     1 1 2 4 1 3 0= .n n n n nX X K A L A L Y A L Y A L XA L K              (4) Можна показати [2], що          1 0 0 1 1 0 1 1 3 2 3 ; = ; = . n n n n n n n n n Y Y A L Y K XA L Y A L Y A K Y X K Y Y A L K A K K L X L              (5) Далі, використовуючи формули (4) і (5), отримуємо алгоритм для обчислення розв'язків поліноміального матричного рівняння (1): 1. Задати похибку > 0; 2. Задати початкове наближення, невироджену матрицю (0) ;m mX R  3. Встановити лічильник =1;n 4. Обчислити          1 2 2 1 1 1 (0) (0) (0) (0) (0) (0) 0 1 3= , = , , = ; n nY X Y X Y X      5. Обчислити Анастасія Недашковська Застосування паралельних обчислень при наближеному розв’язуванні … 24       1 ( ) ( 1) ( 1) 0 0 1 ( ) ( ) ( 1) ( 1) 1 0 1 = ; = ; n n n n n n n n n n n Y A L Y K X A L K Y Y A L Y K X A L K              1 ( ) ( ) ( 1) ( 1) 3 2 3= .n n n n n n n n nY Y A L Y K X A L K        (6) 6. Обчислити 0 2 0 3 5 2 4 1 3 0= ;n n n n nA A Y A Y A Y A Y A         7. Нехай 2 1 1= , = ,n nA A A A  тоді    1 ( ) ( 1) ( 1) 0 2 1= .n n nX X K A L X A L A L K      (7) Перевірити умову ( ) ( 1) < .n nX X  Якщо умова не задовольняється, встановити лічильник = 1n n  і перейти на крок 5, інакше повернути ( )nX . 2. Про збіжність алгоритму Із використанням узагальненої в монографії [1] достатньої умови збіжності Ворпіцького, у роботі [2] показано, що достатньою умовою збіжності ітераційного процесу (7) буде виконання нерівності 2 2 1 1 2 2 1 1 2 2 1 2 2 0 22 1 , 4 k k k A A A E A A A A A l l l                    де коефіцієнти 0 2 0 3 5 2 4 1 3 0= ,n n n n nA A Y A Y A Y A Y A         2 1 1, = , = .n nA A A A  3. Деякі критерії для оцінки паралельних алгоритмів Для оцінки якості паралельних алгоритмів використовуються такі критерії [3], як коефіцієнт прискорення 1 p p T S T  і коефіцієнт ефективності , p p S E p  де p – кількість процесів, що використовуються для розв’язування задачі на MIMD- комп’ютері; pT – час розв’язування задачі на MIMD-комп’ютері із використанням p процесів; 1T – час розв’язування тієї ж задачі на гіпотетичному однопроцесорному комп’ютері із швидкодією одного процесора і оперативною пам’яттю, що рівна сумарній пам’яті, що використовується p процесами. Нехай t – середній час виконання однієї операції; ot – час, необхідний для обміну одним машинним словом між двома процесами; звt – час, необхідний для встановлення зв’язків між двома процесами. Окрім того введемо наступні позначення: ; .o звt t o звt t    Тоді 1 1 ,T Ot а   ,p p зв зв o oT O O O t    Фізико-математичне моделювання та інформаційні технології 2023, вип. 37, 22-26 25 де 1O – кількість операцій необхідна для розв’язування задачі однопроцесорним комп’ютером, pO – кількість операцій, що виконується кожним із p процесів, звO – кількість взаємодій одного із p процесів із іншими, oO – обмінів одним машинним словом для процесу, що розглядається. 4. Паралельна модель алгоритму наближеного розв’язування однобічних рівнянь Ітераційний процес (7) було реалізовано у Visual Studio 2022. При цьому було використано систему MIMD (множинний потік команд, множинний потік даних) організації архітектури обчислювального процесу. При реалізації запропонованого алгоритму основний об’єм роботи виконується на етапі обчислення кроків 4-7. Для множенні матриць на кроках 4-7 використовався паралельний алгоритм скалярних добутків, а при знаходженні обернених матриць на кроках 4,5 та 7 ijk  форма LU розкладу [3]. Відомо [3], що загальна кількість арифметичних операцій необхідна для знаходження оберненої матриці розмірності m m оцінюється величиною 3 22 1, 3 ( ).обO m O m  Відповідно кількість операцій, що виконує один із p процесорів при знаходженні оберненої матриці буде оцінюватись, як 3 22 , 3 ( )m m p об p p O O  [3]. Для виконання множення двох матриць розмірності m m необхідно 3 2 1, ( )мнO m O m  арифметичних операцій множення та додавання. А, отже, кількість операцій, що виконує один із p процесорів при знаходженні дабутку матриць, наприклад, методом скалярних добутків буде оцінюватись, як 3 2 , ( ).m m p мн p p O O  Кількість арифметичних операцій, що використовується при додаванні двох матриць розмірності m m необхідно 2 1, .додO m Тоді для одного із p процесів така кількість становитиме 2 , .m p дод p O  Також будемо вважати, що пошук максимуму для знаходження норми матриці 1 1 1 max m ij j m i A a      буде виконуватися з допомогою найшвидшого алгоритму і потребуватиме m арифметичних операцій. Тож для знаходження норми потрібно 1, ( )нормO O m арифметичних операцій. При використанні p процесів для кожного із них кількість арифметичних операцій теж буде становити , ( ).р нормO O m Провівши деякі нескладні обчислення, отримуємо:     3 2 1 4 1 2 1T O n m n m t    та       3 24 1 2 1 . n m n m p зв зв o op T O O O t        А отже Анастасія Недашковська Застосування паралельних обчислень при наближеному розв’язуванні … 26 1= , 1. p p p p ST S p E T p    Таким чином, для даного алгоритму на обчислювальній системі типу MIMD вдається досягти практично тих же оцінок pS та pE , що і для концепції необмеженого паралелізму, що свідчить про доцільність використання такого підходу при наближеному розв’язуванні рівняння (1). Висновки. У роботі запропонована модифікація розглянутої раніше схеми розв’язування однобічних матричних рівнянь. Застосовані паралельні алгоритми множення та додавання матриць, а також знаходження оберненої матриці. Обчислені коефіцієнти прискорення та ефективності отриманого паралельного алгоритму. Встановлено, що для даної схеми на обчислювальній системі типу MIMD вдається досягти оцінок прискорення і ефективності близьких до оцінок при концепції необмеженого паралелізму, що свідчить про доцільність використання такого підходу при наближеному розв’язуванні однобічного матричного рівняння. Література [1] Боднар Д.И. Ветвящиеся цепные дроби. − К.: Наукова думка, 1986. −176 c. [2] Недашковська А. Узагальнення методу Хованського для наближеного розв'язування однобічних поліноміальних матричних рівнянь/ Анастасія Недашковська // Вісн. Львів. ун-ту ім. І.Франка. Сер. прикл. матем. та інформ. – 2022. – Вип. 30. – С. 60–68. [3] Химич А.Н., Молчанов И.Н., Попов А.В., Чистякова Т.В., Яковлев М.Ф. Параллельные алгоритмы решения задач вычислительной математики: монография. – Київ: Наук.думка, 2008. – 248 с. [4] Beavers A.N., Denman E.D. A New Solution Method for the Lyapunov Matrix Equation// SIAM Journal on Applied Mathematics. – Vol. 29, No. 3, – 1975. – P. 416–421. [5] Boichuk A.A., Krivosheya S.A. Criterion of solvability of matrix equations of Lyapunov type// Ukrainian Mathematical Journal, 1998. – 50, №8. – P.1162–1169. [6] Khovanskii A.N. The Application of continued fractions and their generalizations to problems in approximation theory. P. Noordhoff, 1963. – 212 p. [7] Nedashkovska A. Generalization of the Khovanskii's method for solving matrix polynomial equations// Журнал обчислювальної та прикладної математики. – 2015. – № 2. – С. 42–49. Using of parallel calculations in the approximate solving of one-sided matrix equations Anastasija Nedashkovska, Ivan Gusak Matrix equations are widely used in optimization problems of control systems. Most often, these are the Ricatti and Sylvester equations, but there are other types of matrix equations. There is no general approach to solving problems of this type, so the development of approximate solution schemes is actual. In one of the previous publications, Khovanskyi's method was generalized. An iterative scheme for solving one-sided matrix equations of the form 1 2 1 2 1 0=0n n n nX A X A X A XA A      is obtained. The publication presented a recurrent formula for calculating an approximate solution of equations in the form of a continued matrix fraction. Also, the convergence of the proposed method was investigated. In this article, a modification of the previously considered scheme is proposed. Parallel algorithms are applied for matrix multiplication, matrix addition operations and for finding the inverse matrix. Отримано 31.03.23
id	oai:ojs2.www.fmmit.lviv.ua:article-298
institution	Physico-mathematical modeling and informational technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2026-06-09T01:09:56Z
publishDate	2023
publisher	Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
record_format	ojs
resource_txt_mv	wwwfmmitlvivua/96/77f8e6c789d86f7244f5c70b42102196.pdf
spelling	oai:ojs2.www.fmmit.lviv.ua:article-2982025-02-21T17:31:10Z Using of parallel calculations in the approximate solving of one- sided matrix equations Застосування паралельних обчислень при наближеному розв’язуванні однобічних матричних рівнянь Nedashkovska, Anastasija Gusak, Ivan ітераційний метод, матричні рівняння, однобічні поліоміальні матричні рівняння, метод Хованського Matrix equations are widely used in optimization problems of control systems. Most often, these are the&nbsp;Ricatti and Sylvester equations, but there are other types of matrix equations. There is no general&nbsp;approach to solving problems of this type, so the development of approximate solution schemes is&nbsp;actual. In one of the previous publications, Khovanskyi's method was generalized. An iterative scheme&nbsp;for solving one-sided matrix equations of the form&nbsp;XnAn+Xn-1An-1+…+X2A2+XA1+A0=0.&nbsp;is obtained.&nbsp;The publication presented a recurrent formula for calculating an approximate solution of equations in&nbsp;the form of a continued matrix fraction. Also, the convergence of the proposed method was&nbsp;investigated. In this article, a modification of the previously considered scheme is proposed. Parallel&nbsp;algorithms are applied for matrix multiplication, matrix addition operations and for finding the inverse matrix. Найчастіше матричні рівняння використовуються у задачах оптимізації систем керування. Переважно це рівняння Рікатті та Сильвестра, однак зустрічаються й інші типи матричних рівнянь. Оскільки загального підходу до розв’язування задач такого типу не існує, то розробка схем наближеного розв’язування є актуальною. У одній із попередніх публікацій було узагальнено метод Хованського для побудови ітераційної схеми розв'язування однобічних матричних рівнянь вигляду&nbsp;XnAn+Xn-1An-1+…+X2A2+XA1+A0=0.&nbsp;&nbsp;У публікації наведена рекурентна формула для обчислення наближеного розв'язку рівнянь у вигляді ланцюгового матричного дробу, досліджено збіжність запропонованого методу. У даній роботі запропонована модифікація розглянутої раніше схеми. Застосовані паралельні алгоритми множення та додавання матриць, а також знаходження оберненої матриці. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-27 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/298 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 22-26 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 22-26 2617-5258 1816-1545 10.15407/fmmit2023.37 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/298/266 Авторське право (c) 2023 Анастасія Недашковська, Іван Гусак (Автор)
spellingShingle	ітераційний метод матричні рівняння однобічні поліоміальні матричні рівняння метод Хованського Nedashkovska, Anastasija Gusak, Ivan Застосування паралельних обчислень при наближеному розв’язуванні однобічних матричних рівнянь
title	Застосування паралельних обчислень при наближеному розв’язуванні однобічних матричних рівнянь
title_alt	Using of parallel calculations in the approximate solving of one- sided matrix equations
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/298
work_keys_str_mv	AT nedashkovskaanastasija usingofparallelcalculationsintheapproximatesolvingofonesidedmatrixequations AT gusakivan usingofparallelcalculationsintheapproximatesolvingofonesidedmatrixequations AT nedashkovskaanastasija zastosuvannâparalelʹnihobčislenʹprinabliženomurozvâzuvanníodnobíčnihmatričnihrívnânʹ AT gusakivan zastosuvannâparalelʹnihobčislenʹprinabliženomurozvâzuvanníodnobíčnihmatričnihrívnânʹ

Застосування паралельних обчислень при наближеному розв’язуванні однобічних матричних рівнянь

Репозитарії

Схожі ресурси