Розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами

У роботі запропоновано новий підхід до розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами. Проведено підрахунок кількостей записів та операцій при чисельній реалізації алгоритму множення матриць. Охарактеризовано складність алгоритму з точки зору комп’ютерної алгеб...

Full description

Saved in:

Bibliographic Details
Published in:	Фізико-математичне моделювання та інформаційні технології
Date:	2007
Main Author:	Семчишин, Л.
Format:	Article
Language:	Ukrainian
Published:	Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України 2007
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/21106
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами / Л. Семчишин // Фіз.-мат. моделювання та інформ. технології. — 2007. — Вип. 6. — С. 128-135. — Бібліогр.: 11 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-21106
record_format	dspace
spelling	Семчишин, Л. 2011-06-15T08:04:57Z 2011-06-15T08:04:57Z 2007 Розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами / Л. Семчишин // Фіз.-мат. моделювання та інформ. технології. — 2007. — Вип. 6. — С. 128-135. — Бібліогр.: 11 назв. — укр. 1816-1545 https://nasplib.isofts.kiev.ua/handle/123456789/21106 518.25 У роботі запропоновано новий підхід до розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами. Проведено підрахунок кількостей записів та операцій при чисельній реалізації алгоритму множення матриць. Охарактеризовано складність алгоритму з точки зору комп’ютерної алгебри. Проведено порівняння запропонованого алгоритму та блочного методу прогонки. Обчислено кількість записів для методу прогонки. Показано ефективність запропонованого алгоритму. The new approach to solving rarefied systems of linear algebraic equations with block elements is offered in the work. Calculation of recording amount and amount of matrixes multiplication in the numerical realization of the algorithm is carried out. The algorithm complexity is characterized from the point of view of computer algebra. Comparisons of the suggested algorithm and the block method of marching are carried out. The amount of recording for marching method is counted. Efficiency of the suggested algorithm is shown. В работе предлагается новый подход к решению разреженных систем линейных алгебраических уравнений с блочными элементами. Проведено подсчет количества записей и количества операций при числовой реализации алгоритма умножения матриц. Охарактеризована сложность алгоритма с точки зрения компьютерной алгебры. Проведены сравнения предложенного алгоритма и блочного метода прогонки. Подсчитано количество записей для метода прогонки. Показана эффективность предложенного алгоритма. uk Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України Фізико-математичне моделювання та інформаційні технології Розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами On solving the rarefied systems of linear algebraic equations with block elements Решение разреженных систем линейных алгебраических уравнений с блочными элементами 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	Семчишин, Л.
publishDate	2007
language	Ukrainian
container_title	Фізико-математичне моделювання та інформаційні технології
publisher	Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
format	Article
title_alt	On solving the rarefied systems of linear algebraic equations with block elements Решение разреженных систем линейных алгебраических уравнений с блочными элементами
description	У роботі запропоновано новий підхід до розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами. Проведено підрахунок кількостей записів та операцій при чисельній реалізації алгоритму множення матриць. Охарактеризовано складність алгоритму з точки зору комп’ютерної алгебри. Проведено порівняння запропонованого алгоритму та блочного методу прогонки. Обчислено кількість записів для методу прогонки. Показано ефективність запропонованого алгоритму. The new approach to solving rarefied systems of linear algebraic equations with block elements is offered in the work. Calculation of recording amount and amount of matrixes multiplication in the numerical realization of the algorithm is carried out. The algorithm complexity is characterized from the point of view of computer algebra. Comparisons of the suggested algorithm and the block method of marching are carried out. The amount of recording for marching method is counted. Efficiency of the suggested algorithm is shown. В работе предлагается новый подход к решению разреженных систем линейных алгебраических уравнений с блочными элементами. Проведено подсчет количества записей и количества операций при числовой реализации алгоритма умножения матриц. Охарактеризована сложность алгоритма с точки зрения компьютерной алгебры. Проведены сравнения предложенного алгоритма и блочного метода прогонки. Подсчитано количество записей для метода прогонки. Показана эффективность предложенного алгоритма.
issn	1816-1545
url	https://nasplib.isofts.kiev.ua/handle/123456789/21106
citation_txt	Розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами / Л. Семчишин // Фіз.-мат. моделювання та інформ. технології. — 2007. — Вип. 6. — С. 128-135. — Бібліогр.: 11 назв. — укр.
work_keys_str_mv	AT semčišinl rozvâzuvannârozrídženihsistemlíníinihalgebraíčnihrívnânʹízbločnimielementami AT semčišinl onsolvingtherarefiedsystemsoflinearalgebraicequationswithblockelements AT semčišinl rešenierazrežennyhsistemlineinyhalgebraičeskihuravneniisbločnymiélementami
first_indexed	2025-11-25T20:39:04Z
last_indexed	2025-11-25T20:39:04Z
_version_	1850524917008695296
fulltext	Розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами Лідія Семчишин Чортківський інститут підприємництва і бізнесу Тернопільського національного економічного університету, вул. С. Бандери, 46, Чортків, Тернопільська область, 48500, e-mail: Lida55718@ukr.net У роботі запропоновано новий підхід до розв’язування розріджених систем лінійних алгеб- раїчних рівнянь із блочними елементами. Проведено підрахунок кількостей записів та опера- цій при чисельній реалізації алгоритму множення матриць. Охарактеризовано складність алгоритму з точки зору комп’ютерної алгебри. Проведено порівняння запропонованого алго- ритму та блочного методу прогонки. Обчислено кількість записів для методу прогонки. По- казано ефективність запропонованого алгоритму. Ключові слова: розріджені системи, ланцюгові дроби, кількість записів, складність алгоритму. Вступ. Математичне моделювання в наукових дослідженнях і практичних засто- суваннях є невід’ємною рисою технічного прогресу. Його ефективність визнача- ється продуктивністю ЕОМ та якістю обчислювальних алгоритмів і програм, що використовуються. Обчислювальні методи алгебри є одним із базових інструмен- тів при моделюванні на ЕОМ і є важливою частиною програмного забезпечення для комп’ютерів усіх поколінь. У значній кількості прикладних задач виникає необхідність розв’язання роз- ріджених систем рівнянь із блочними елементами [1-3]. Розв’язуванню таких сис- тем рівнянь присвячені роботи В. Воєводіна [1-4], В. Воєводіна, Ю. Кузнєцова [5], В. Воєводина, Є. Тиртишнікова [6], В. Дейнеки, І. Сергієнка [8], М. Недашковсь- кого [10, 11], Дж. Дзвенпорта, І. Сіре, Є. Турньє [9]. У цій статті розглянемо метод розв’язування розріджених систем із деякими найхарактернішими способами заповнення. 1. Формулювання задачі Розглянемо систему лінійних алгебраїчних рівнянь                     =                                         + +− + + + − − −−−−− 1, 1,1 1,3 1,2 1,1 1 3 2 1 ,1, ,11,12,1 3,32,3 3,22,21,2 2,11,1 ...... 0...000 ...000 ..................... 000...0 000... 000...0 nn nn n n n n n nnnn nnnnnn A A A A A x x x x x AA AAA AA AAA AA , (1) УДК 518.25 128 ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології 2007, вип. 6, 128-135 129 елементами якої Aij є блоки розмірності m × m. Позначимо через       k k jjj iii A ... ... 21 21 мінор, розміщений на перетині блочних стрічок i1, i2, …, ik та блочних стовпців j1, j2, …, jk. За узагальненим правилом Крамера [4] 1,1 2,1 1, 1 1,2 2,2 2, 1 3,2 3, 1 1, , 1 , 1,1 1,2 2,1 2,2 2,3 3,2 3,3 1, , 0 0 0 0 0 0 0 0 0 0 0 0 0 0 n n n n n n n n n i n n n n A A A A A A A A A A A x A A A A A A A A A + + + − + − = Розкладаючи чисельник за мінорами, можна записати 11 2 1 2i n x A n −    = ×      … … ( ) 1 , 1 , 1 1 1 1 2 1 1 1 1 2 1 1 kn i k k n s s k s i i k n A A A A i k n − + + + = = +  − +    × − ⋅    − +     ∑ ∏ … … … … … … (2) Введемо позначення 1 , 1 1 1 2 1 1 , , 1, 1 2 1 1 k ik s s s i i k n A A A i k n i k n − + = + − +    α = =   − +    ∏ … … … … … … . Тоді для визначення невідомої маємо співвідношення ( ) 1 , 1 , 1 1 2 1 1 2 n i k i k n i k k n x A A n − + + =    = − α      ∑ … … . (3) Для компактності запису надалі будемо позначати результат виконання операції множення на обернену матрицю зліва у вигляді C – 1D = D / C. Тоді вираз D1 / (C1 + D2 / C2) означатиме 1 1 2 1 21 )( DDCC ⋅+ −− . Якщо до співвідношення (3) застосувати відому рівність Леонарда Ейлера [10], яка пов’язує ланцюгові дроби з рядами та скінченними сумами, то для xi одержимо Лідія Семчишин Розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами 130 ( ) ×             =−            = ∑ = + + − n k kink k i n n A n n A A n n Ax 1 ,1, 1 1 21 21 32 32 1 21 21 … … … … … … α 1, 1 2, 1 1,2 1, 1 1,1 2, 1 1,2 3, 1 1,3 2, 1 1,2 3, 1 1,31, 1 1,2 2, 1 1,2 , 1 1, 1, 1 1, 1 , 1 1, 1, 1 1, 1 / / / n n n n n n nn n n n n n n n n n n n n n A A A E A A A E AA E A A A A E A + + + + + + ++ + + − + − + − + − × α α + α α α − + αα − + α α α + α − α … . (4) Тут E — одинична матриця. Вираз 1 1, 1 1,k k − +α α (k = 1, 2, ...) також можна розкласти в ланцюгові дроби [4] 1, 1, 1, 1 1, 1 1, 1 1 1 1 1 1 1 1 k k k k k k k k A A k k k A A A A k k + + + +    α  = = −α     −   −    … … … … … … 1, 1, 1 1, , 1 1 1 1 1 1 1 1 1 k k k k k k k k A k k k A A A A A k k+ + + +      = = −    −   −    … … … … … … 1 1, 1 1, , 1 1 1 1 1 1 1k k k k k k E k k A A A A A k k − + + + + = = −    −    −    … … … … 1 1, 1 1, , 1 1 1 1 1 1 1 TT T k k k k k k E k k A A A A A k k − + + + + = =  −    −     −     … … … … 1, , 1 1, 1 1, , 1 , 1, 1 1,2 2,1 1,1 , 1, k k k k k k k k k k k k k k E k nA A A A A A A A A A + + + + − − − − = = − − − − … (5) ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології 2007, вип. 6, 128-135 131 Аналогічним чином 1 1,1 2,1 1,2 2 3 2 3 1 2 2 3 3 4 1 2 2 3 3 4 T T n A n E n n nA A A A A An n n −       = =          −            … … … … … … … … 2,1 1,2 1,1 2,3 3,2 2,2 3,3 1, , 1 , . n n n n n n E A A A A A A A A A A − − = = − − − − … … За такою ж схемою знаходимо решта невідомих xi ( ) 1 1 , 1 , , 1 , 1 1 2 1 1 2 2 i i ki n i i i k n i k k An x A A n − − ++ + =     = α + − α +        ∑ … … ( ), 1 , , 1 , 1 1 2 n i ki n i i k n i k k i A A++ + = +  + α + − α =  ∑ ( ) ( ) ( ) 12 1 2 2 1 1, , 1 , , 1, , 1 ,1 1 1 /i i i i i i i i i i i i i i i i iA A A −− + − − + +  = − α α + − + − α α ×  ( ) ( ) ( ) ( ) , 1 1 , 1 , 1, 1 , 1 1 , 1 , 1, 1 , 1 1 2, 1 ,2 1, 1 ,1 1 2, 1 ,2 1, 1 ,1 1 2 2 2 i n i n i i i n i i i n i i i n i i n i n i n i n i A A A E E A A A A E A A + − + − + − − + − + − − + + − + +        × α α − + α α −   α α −  + α α … – Лідія Семчишин Розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами 132 ( ) ( ) ( ) ( ) , 1 1 , 1 , 1, 1 , 1 1 , 1 , 1, 1 , 1 1 1, 1 , 1 , 1 , 1 1, 1 , 1 , 1 , 1 2 2 2 i n i n i i i n i i i n i i i n i i n n i n n n i n n n i n n n i n A A A E E A A A A E A A + − + + + + − + + + + − − + − + − − + − +        −  α α −  + α α −   α α −  + α α  … . А для кожного відношення αi, k / αi, k + 1 своєю чергою можна записати 1 , 1 , 1 , 1 , 1 1 1 2 1 1 1 2 1 1 1 2 1 2 1 2 1 2 k s s i k s i k i k s s s i i k n A A A i k n i k n A A A i k n − + = + + + = + − +       α − +   = = − +α        − +    ∏ ∏ … … … … … … … … … … … … 1, 1 , 1 , 1 1 1 1 1 k k k k k k k n A Ak n k n A A A k n + + + + +   + = = − +   +  … … … … … … … … 1, 2 2, 1 1, 1 , 1 1 , 1 3 2 3 2 k k k k k k TT k k T k k A A A Ak n k n A A A k n k n + + + + + + + − + − = = −  + +        + +     … … … … … 1, 2 2, 1 , 1 3, 2 2, 3 2, 2 3, 4 4, 3 3, 3 4, 4 1, , 1 , /k k k k k k k k k k k k k k k k k k k k n n n n n n A A A A A A A A A A A A A + + + + + + + + + + + + + + + + + + + − − − − − − − … . Таким чином одержуємо аналітичне розвинення невідомих xi даної розрідженої системи лінійних алгебраїчних рівнянь у скінченні матричні ланцюгові дроби. ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології 2007, вип. 6, 128-135 133 2. Обчислювальні характеристики алгоритму Тепер підрахуємо необхідну кількість записів при символьному розв’язуванні за- дачі та кількість операцій під час чисельної реалізації алгоритму множення матриць. Твердження. Нехай деяка обчислювальна задача з вхідними даними {Ai} розв’язується на ЕОМ за алгоритмом ψ (A1, A2, …, An) i складається з k кроків ψj ( 1,j k= ). Якщо на кожному кроці алгоритму ψ(A) реалізується хоча б один запис виду 1 2 ( ) ( )ji jiA Aψ ψ , який використовує результат попереднього кроку, то загаль- на складність Qψ задачі буде не меншою, ніж 2k m2, але не більшою від H k записів, де Н — найбільша ширина алгоритму на k кроках [9]. Використаємо це твердження для оцінки складності алгоритму з точки зору комп’ютерної алгебри [9]. Для чисел xi ( )1,i n= на одному поверсі реалізація алгоритму вимагає одне блочне множення, одне блочне ділення, одне блочне додавання, а для n поверхів — 3n операцій, тобто по n блочних множень, ділень та додавань. Обчислення показують, що для визначення усіх Ai, k / Ai, k + 1 потрібно 5k за- писів, якщо k < i та 5(n – k) записів, якщо k > i. Таким чином необхідно виконати таку кількість записів 2 2 1 (1 ) ( )( 1)5 5 5 ( 1) 5 . 2 2 2 2 i n k k i i i i n n i n nk n k n n i i ni = =  + + − + + − = + − + − = + + −      ∑ ∑ Отже, загальна складність методу становить 2 2 3 1 55 ( ). 2 2 2 n i n ni ni n n =   + + − = +    ∑ Відомо [7, 10, 11], що алгоритм прогонки реалізується співвідношеннями 1 1 1i i i ix x+ + += α +β , , 1 , 1 , 1 1 1 , , 1 , , 1 , i i i n i i i i i i i i i i i i i a a a a a a a + + − + + − − + β α = β = − − для прямого та зворотного ходу. Проведемо порівняння запропонованого алгоритму та блочного методу прогонки. Кількість записів для методу прогонки, який реалізується співвідно- шеннями 1 2 2 2 ,x x= α +β 2 1,2 1,1a aα = , 2 1, 1 1,1na a+β = , 2 3 3 3,x x= α +β 2,3 3 2,2 2,1 , a a a α = − 2, 1 3 2,2 2,1 ,na a a +β = − 1 ,n n n nx x− = α +β 1, 1, 1 1, 2 ,n n n n n n n a a a − − − − − α = − 1, 1 1, 1 1,1 n n n n n n a a a − + − − − β = − , Лідія Семчишин Розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами 134 буде оцінюватися відповідно до записаного вище твердження. Розрахунки свід- чать, що для обчислення α i + 1 та β i + 1 необхідно виконати по i операцій блочного додавання, блочного множення та блочного ділення. Тоді для обчислення кожно- го xk треба реалізувати 1 (1 ) 2 i k k i i = = +∑ записів, а для обчислення усіх ( )1,ix i n= потрібно (n3 + n2 + 2n) / 4 записів. Таким чином, із точки зору комп’ютерної алгебри запропонований алгоритм суттєво переважає класичний алгоритм прогонки. Він може бути реалізований, як в аналітичному, так і в числовому вигляді. Для реалі- зації запропонованого алгоритму потрібно по 6n блочних додавань і ділень та 4n блочних множень, оскільки в цьому випадку результати обчислень проміжних дробів можуть використовуватися багаторазово. Відзначимо, що описаний алгоритм можна також застосовувати й у випад- ку систем із прорідженими матрицями наступного вигляду 1,1 1, 2,1 2,2 2,3 2, 1 ,1 , 1,2 , , 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 k k k n k n k n n k n n A A A A A A A A A A A + − + −                        Матриці можуть також бути обрамленими з однієї або двох сторін. Систе- ми з подібним заповненням розпадаються на k систем вигляду (1), кожна з яких матиме порядок n / k. Висновки. У статті розглянуто метод розв’язування розріджених систем ліній- них алгебраїчних рівнянь із блочними елементами. Запропонований алгоритм може ефективно використовуватися в системах комп’ютерної алгебри та для ана- літично-числового розв’язування інженерних прикладних задач механіки. На основі такого підходу в пакеті MatLab були проведені числові експери- менти для лінійних алгебраїчних рівнянь із блочними елементами, які підтвер- джують ефективність запропонованого алгоритму. Література [1] Воеводин В. В.Численные методы алгебры. — М.: Наука, 1966. — 246 с. [2] Воеводин В. В. Ошибки округления и устойчивость в прямых методах линейной алгебры. — М.: Изд-во МГУ,1969. [3] Воеводин В. В. Вычислительные основы линейной алгебры. — М.: Наука, 1977. —303 с. [4] Воеводин В. В. Математические модели и методы в параллельных процессах. — М.: Наука, 1986. — 296 с. ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології 2007, вип. 6, 128-135 135 [5] Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. — М.: Наука, 1984. — 320 с. [6] Воеводин В. В., Тыртышников Е. Е. Вычислительные процессы с теплицевыми матрицами. — М.: Наука, 1987. — 320 с. [7] Гантмахер Ф. Р. Теория матриц. — М.: Наука, 1967. — 324 с. [8] Дейнека В. С., Сергиенко И. В. Модели и методы решения задач в неоднородных средах. — К.: Наук. думка, 2001. — 606 с. [9] Дэвенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра. — М.: Мир, 1991. — 352 с. [10] Недашковський М. О., Скоробогатько В. Я. Розв’язування систем лінійних алгеб- раїчних рівнянь методом гіллястих ланцюгових дробів. В кн.: Теоретичні та при- кладні питання алгебри i рівнянь. — К.: Наук. думка, 1977. — C. 84-92. [11] Недашковський М. О. Ознаки збіжності матричних гіллястих ланцюгових дробів // Математичні методи та фізико-механічні поля. — 2003. — Т. 46, № 4. — C. 50-56. On solving the rarefied systems of linear algebraic equations with block elements Lidiya Semchyshyn The new approach to solving rarefied systems of linear algebraic equations with block elements is offered in the work. Calculation of recording amount and amount of matrixes multiplication in the numerical realization of the algorithm is carried out. The algorithm complexity is characterized from the point of view of computer algebra. Comparisons of the suggested algorithm and the block method of marching are carried out. The amount of recording for marching method is counted. Efficiency of the suggested algorithm is shown. Решение разреженных систем линейных алгебраических уравнений с блочными элементами Лидия Семчишин В работе предлагается новый подход к решению разреженных систем линейных алгебраи- ческих уравнений с блочными элементами. Проведено подсчет количества записей и коли- чества операций при числовой реализации алгоритма умножения матриц. Охарактеризова- на сложность алгоритма с точки зрения компьютерной алгебры. Проведены сравнения предложенного алгоритма и блочного метода прогонки. Подсчитано количество записей для метода прогонки. Показана эффективность предложенного алгоритма. Отримано 12.06.07

Розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами

Institution

Similar Items