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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автор:	Семчишин, Л.М.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2018
Назва видання:	Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/162206
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Застосування розріджених числових систем лінійних алгебраїчних рівнянь в середовищі MatLab / Л.М. Семчишин // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2018. — Вип. 17. — С. 117-132. — Бібліогр.: 8 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-162206
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1622062025-02-09T13:46:23Z Застосування розріджених числових систем лінійних алгебраїчних рівнянь в середовищі MatLab Application of rarefied numerical systems of linear algebraic equations in Matlab environment Семчишин, Л.М. У статті запропоновано новий підхід до розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами. Проведено підрахунок кількостей записів та операцій при чисельній реалізації алгоритму множення матриць. Охарактеризовано складність алгоритму з точки зору комп’ютерної алгебри. Проведено порівняння запропонованого алгоритму та блочного методу прогонки. Обчислено кількість записів для методу прогонки. Протестовано алгоритми розв'язання деяких типів розріджених числових систем лінійних алгебраїчних рівнянь. Показано ефективність запропонованого алгоритму. New approach to the linear algebraic equations rarefied systems with block elements solution and the method of rarefied systems with the specific ways of filling solution is suggested in the article. Calculation of the records number and operations under the numerical realization of the matrix multiplication algorithm is conducted. The algorithm complication from the computer algebra point of view is characterized. The described algorithm is used in the case of systems with the rarefied three-diagonal matrix. 2018 Article Застосування розріджених числових систем лінійних алгебраїчних рівнянь в середовищі MatLab / Л.М. Семчишин // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2018. — Вип. 17. — С. 117-132. — Бібліогр.: 8 назв. — укр. 2308-5878 https://nasplib.isofts.kiev.ua/handle/123456789/162206 518.25 uk Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	У статті запропоновано новий підхід до розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами. Проведено підрахунок кількостей записів та операцій при чисельній реалізації алгоритму множення матриць. Охарактеризовано складність алгоритму з точки зору комп’ютерної алгебри. Проведено порівняння запропонованого алгоритму та блочного методу прогонки. Обчислено кількість записів для методу прогонки. Протестовано алгоритми розв'язання деяких типів розріджених числових систем лінійних алгебраїчних рівнянь. Показано ефективність запропонованого алгоритму.
format	Article
author	Семчишин, Л.М.
spellingShingle	Семчишин, Л.М. Застосування розріджених числових систем лінійних алгебраїчних рівнянь в середовищі MatLab Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
author_facet	Семчишин, Л.М.
author_sort	Семчишин, Л.М.
title	Застосування розріджених числових систем лінійних алгебраїчних рівнянь в середовищі MatLab
title_short	Застосування розріджених числових систем лінійних алгебраїчних рівнянь в середовищі MatLab
title_full	Застосування розріджених числових систем лінійних алгебраїчних рівнянь в середовищі MatLab
title_fullStr	Застосування розріджених числових систем лінійних алгебраїчних рівнянь в середовищі MatLab
title_full_unstemmed	Застосування розріджених числових систем лінійних алгебраїчних рівнянь в середовищі MatLab
title_sort	застосування розріджених числових систем лінійних алгебраїчних рівнянь в середовищі matlab
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2018
url	https://nasplib.isofts.kiev.ua/handle/123456789/162206
citation_txt	Застосування розріджених числових систем лінійних алгебраїчних рівнянь в середовищі MatLab / Л.М. Семчишин // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2018. — Вип. 17. — С. 117-132. — Бібліогр.: 8 назв. — укр.
series	Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
work_keys_str_mv	AT semčišinlm zastosuvannârozrídženihčislovihsistemlíníjnihalgebraíčnihrívnânʹvseredoviŝímatlab AT semčišinlm applicationofrarefiednumericalsystemsoflinearalgebraicequationsinmatlabenvironment
first_indexed	2025-11-26T10:22:28Z
last_indexed	2025-11-26T10:22:28Z
_version_	1849848025294307328
fulltext	Серія: Фізико-математичні науки. Випуск 17 117 УДК 518.25 Л. М. Семчишин, канд. фіз.-мат. наук Чортківський навчально-науковий інститут підприємництва і бізнесу Тернопільський національний економічний університет, м. Чортків ЗАСТОСУВАННЯ РОЗРІДЖЕНИХ ЧИСЛОВИХ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ В СЕРЕДОВИЩІ MATLAB У статті запропоновано новий підхід до розв’язування розрі- джених систем лінійних алгебраїчних рівнянь із блочними елеме- нтами. Проведено підрахунок кількостей записів та операцій при чисельній реалізації алгоритму множення матриць. Охарактери- зовано складність алгоритму з точки зору комп’ютерної алгебри. Проведено порівняння запропонованого алгоритму та блочного методу прогонки. Обчислено кількість записів для методу прого- нки. Протестовано алгоритми розв'язання деяких типів розрідже- них числових систем лінійних алгебраїчних рівнянь. Показано ефективність запропонованого алгоритму. Розв'язування систем лінійних алгебраїчних рівнянь (СЛАР) завжди є одним із актуальних задач обчислювальної математики. При розв’язанні широкого кола прикладних задач більшість су- часних вчених, інженерів і техніків, як правило, використовують пакети комп’ютерної алгебри. Розв’язання математичних задач з допомогою системи MATLAB заслуговує особливої уваги. Зоріє- нтована на роботу з реальними даними, ця система виконує всі обчислення в арифметиці з плаваючою комою на відміну від кон- куруючих систем комп’ютерної алгебри REDUCE, MACSYMA, DERIVE, Maple, Mathematica, Theorist, в яких переважає цілочи- сельне представлення і символьна обробка даних. Хоча для розв’язання проблем на межі символьних обчислень і обчислень з плаваючою комою до складу інтегрованої системи MATLAB включений пакет прикладних програм Extended Symbolic Mathematics Toolbox, котрий реалізує інтерфейс з системою сим- вольних обчислень Maple. Одним з важливих інструментів MatLab є набір процедур лінійної алгебри. В обчислювальному плані розділ лінійної ал- гебри підтриманий пакетами прикладних програм LINPACK, EISPACK, які були створені в 70-ті роки минулого століття провідними фахівцями світу, до яких належить і засновник фі- рми MathWorks Inc. К. Моулер. Власне вихідною задачею сис- теми MatLab і було створення діалогової оболонки для роботи з пакетами лінійної алгебри. Система MatLab — відкрите середовище, яке досить дина- мічно розвивається зусиллями сотень і тисяч дослідників, адже це одночасно і операційна оболонка і досить гнучка мова © Л. М. Семчишин, 2018 Математичне та комп’ютерне моделювання 118 програмування. Однією з найбільш сильних сторін є те, що на мові MatLab можуть бути написані програми і функції для ба- гатократного використання. Ключові слова: розріджені системи, ланцюгові дроби, скінченні суми, кількість записів, складність алгоритму, ком- п'ютерна алгебра, тестування алгоритмів. Вступ. Економіко-математичні дослідження, що проводяться в країні, охоплюють важливі проблеми на різних рівнях планування та управління. Успішне розв'язання численних економіко-математичних задач стало можливим лише завдяки широкому використанню мате- матичних моделей, обчислювальних методів і комп'ютерних техноло- гій. Застосування математики в економіці дозволяє виділити й фор- мально описати найголовніші зв'язки між економічними змінними та параметрами об'єктів дослідження, індуктивним шляхом одержати нові відомості про об'єкт, зробити важливі теоретичні висновки і прийняти правильні економічні рішення. Головні переваги математи- ки як засобу наукового пізнання найповніше розкриваються саме у процесі побудови математичних моделей. Постановка проблеми. Обчислювальний експеримент дозволяє із заданою точністю кількісно та якісно описати досліджувану проблему, інакше кажучи побудувати математичну модель, аналіз якої в свою чер- гу дозволяє глибше проникнути в суть явища, що вивчається. Розв'язу- вання систем лінійних алгебраїчних рівнянь (СЛАР) завжди є одним із актуальних задач обчислювальної математики. Особливо часто їх дово- диться розв'язувати під час дослідження економіко-математичних задач. Обчислювальна математика вивчає чисельні методи розв'язування різ- них математичних задач, тобто методи, які ґрунтуються на побудові скі- нченної послідовності дій над скінченною множиною чисел. Обчислю- вальні методи — одні з базових інструментів математичного моделю- вання і є важливою частиною програмного забезпечення для комп'юте- рів усіх поколінь. За умови використання таких обчислювальних методів застосовують математичне моделювання до розв'язку математичної за- дачі. Тоді розв'язок одержується у вигляді числового результату. Залеж- но від того, на який економічний процес звертається основна увага, при побудові й дослідженні моделі використовується відповідний математи- чний апарат. Його ефективність визначається продуктивністю ЕОМ та якістю обчислювальних алгоритмів і програм, що використовуються. Побудова ефективних методів визначення невідомих для таких сис- тем — потрібна і досить непроста задача. Аналіз останніх публікацій. Багато відомих вітчизняних і закор- донних вчених займалися проблемами розв'язування систем лінійних алгебраїчних рівнянь. Серед них: В. Воєводін [1], Є. Тиртишніков [2], Серія: Фізико-математичні науки. Випуск 17 119 Дж. Уилкинсон [3] та ін. Розв’язуванню розріджених систем лінійних алгебричних рівнянь із блочними елементами присвячені роботи В. Воєводіна [1], Ф. Гантмахера [4]. Однак деякі проблеми не мають однозначного розв'язання і потребують уточнення. У роботі М. Недашковського і О. Ковальчук [5] розглянуто комп'ютерні алгори- тми для систем лінійних алгебраїчних рівнянь. Особлива увага приді- лялась методам аналізу обчислювальної стійкості алгоритмів у працях таких вчених як: С. Ашманов [6], Д. Дэвэнпорт, И. Сирэ, Э. Турнье [7]. У роботі [8, с. 91–99] запропоновано новий підхід до програмної реалі- зацїї розв’язання систем лінійних алгебраїчних рівнянь. Проаналізова- но обчислювальну стійкість запропонованого алгоритму. Актуальність теми. Застосування розріджених числових систем лінійних алгебраїчних рівнянь вимагає використання ефективних чисельних методів. Слід зауважити, що питання програмної реалізації розв’язання систем лінійних алгебраїчних рівнянь розглядалося у праці [8, с. 91– 99]. Однак, у роботі М. Недашковського і О. Ковальчук [5] розгляну- то комп'ютерні алгоритми для систем лінійних алгебраїчних рівнянь. Мета роботи. Метою цієї роботи є дослідження нового підходу до розв’язування розріджених систем лінійних алгебраїчних рівнянь із бло- чними елементами. Проведення підрахунку кількостей записів та опера- цій при чисельній реалізації алгоритму множення матриць. Порівняння запропонованого алгоритму та блочного методу прогонки. Обчислення кількості записів для методу прогонки. Тесту- вання алгоритмів розв'язання деяких типів розріджених числових систем лінійних алгебраїчних рівнянь. Теоретичну та методологічну основу дослідження складають методи оптимізації, математичне моделювання. Основна частина. У значній кількості прикладних задач виникає необхідність розв’язання розріджених числових систем лінійних алге- бричних рівнянь із блочними елементами [1, 2]. Розглянемо метод розв’язування розріджених систем із деякими найхарактернішими спосо- бами заповнення. Розглянемо систему лінійних алгебричних рівнянь 1,1 1,2 1, 11 2,1 2,2 2,3 2, 12 3,2 3,3 3, 13 1, 2 1, 1 1, 1, 11 , 1 , 0 ... 0 0 0 ... 0 0 0 0 ... 0 0 0 ... ... ... ... ... ... ... ...... 0 0 0 ... 0 0 0 ... 0 n n n n n n n n n n nn n n n n n A A Ax A A A Ax A A Ax A A A Ax A A Ax                                        , 1n n                    ,(1) Математичне та комп’ютерне моделювання 120 елементи якої Aij — це блоки розмірності m × m. Позначимо через 1 2 1 2 ... ... k k i i i A j j j       мінор, розміщений на перетині блочних стрічок i1, i2, …, ik та блочних стовпців j1, j2, …, jk. За узагальненим правилом Крамера [2] 1,1 2,1 1, 1 1,2 2,2 2, 1 3,2 3, 1 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 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                             Розкладаючи чисельник за мінорами, можна записати   1 1 , 1 , 1 1 1 1 2 1 2 1 2 1 1 1 1 2 1 1 i kn i k k n s s k s i n x A n 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                            Тоді для визначення невідомої x1 маємо співвідношення   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 1 2 2 1( )C C D D   . Якщо до співвідношення (3) застосувати відому рівність Леона- рда Ейлера [5], яка пов’язує ланцюгові дроби з рядами та скінченними сумами, то для 1x одержимо   1 1 , 1 , 1 2 3 1 2 2 3 1 1 21 2 1 2 n k i k n i k k n A n n x A A nn A n                                 (4) Серія: Фізико-математичні науки. Випуск 17 121 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                                      Тут і далі E — означає одиничну матрицю. Вираз 1 1, 1 1,k k     1,2,k   також можна розкласти в ланцюгові дроби [5] 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                        (5) 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 n A A A A A A A A A A                  В подібний спосіб Математичне та комп’ютерне моделювання 122 1 1,1 2,1 1,2 2 3 2 3 1 2 1 2 2 3 3 4 2 3 3 4 T T n A n n A n E n n A A A A A 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           За аналогічною схемою знаходимо решту невідомих ix     1 1 , 1 , 1 , , 1 , , , 1 , 1 1 1 2 1 2 1 1 2 2 i i n i k i ki n i n i i k n i k i i k n i k k k i n x A n A A 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 ,1 2, 1 ,2 1, 1 ,1 2, 1 ,2 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 A E A A A A E A                                Серія: Фізико-математичні науки. Випуск 17 123   , 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 A E A A A A E A                                   А для кожного відношення , , 1/i k i k   в свою чергу можна записати: 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 1k k k n A k n k n A A k n                    1, 1 1, 2 2, 1 , 1 1 , 1 3 2 3 2 k k k k k k TTk k T k k A A A A k n k n A A A k n k n                                 1, 1 1, 2 2, 1 , 1 3, 2 2, 3, 1 2, 2 3, 4 4, 3 3, 3 4, 4 1, , 1 , / .k k k k k k k k k k k kk k k k k k k k k k k k n n n n n n A A A A A AA A A A A A A A A                                  Отже, одержуємо аналітичне розвинення невідомих даної розрі- дженої системи лінійних алгебраїчних рівнянь у скінчені матричні ланцюгові дроби. Обчислювальні характеристики алгоритму. Тепер підрахує- мо необхідну кількість записів при символьному розв’язуванні задачі Математичне та комп’ютерне моделювання 124 та кількість операцій під час чисельної реалізації алгоритму множен- ня матриць .ij klA A Твердження [5]. Нехай деяка обчислювальна задача з вхідними даними {Ai} розв’язується на ЕОМ за алгоритмом ψ (A1, A2, …, An) i складається з k кроків ψj ( 1,j k ). Якщо на кожному кроці алгоритму ψ(A) реалізується хоча б один запис виду 1 2 ( ) ( )ji jiA A  , який вико- ристовує результат попереднього кроку, то загальна складність Qψ задачі буде не меншою 2k · m2, але не більшою H k записів, де Н — найбільша ширина алгоритму на k кроках. Використаємо це твердження для оцінки складності алгоритму з точки зору комп’ютерної алгебри [7]. Для чисел 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             Відомо [5], що алгоритм прогонки реалізується співвідношеннями 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         , Серія: Фізико-математичні науки. Випуск 17 125 буде оцінюватися відповідно до твердження. Розрахунки свідчать, що для обчислення α 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. Тестування алгоритмів розв'язання деяких типів розрідже- них числових систем лінійних алгебричних рівнянь Опис тестування функції FC_Three_Diag_Sys. Для перевірки алгоритму розв’язання трьохдіагональних систем лінійних алгебрич- них рівнянь методом ланцюгових дробів була використана система рівнянь наступного вигляду: 1 2 1 1.5 1 ... 0 0 3 1 1.5 ... 0 0 0 ...... ... ... ... ... ... 0 0 ... 1.5 1 0 0 0 ... 1 1.5 0 n n x x x x                                         Математичне та комп’ютерне моделювання 126 Це несиметрична система рівнянь, без діагонального домінуван- ня із середнім значенням спектрального числа обумовленості. Для розв’язання систем лінійних алгебричних рівнянь з число- вими елементами в середовищі MatLab написана і протестована фун- кція FC_Three_Diag_Sys. Ця функція реалізує алгоритм розв'язування систем лінійних алгебричних рівнянь методом ланцюгових дробів і написана за допомогою об’єктно-орієнтованої макромови MatLab. Для спрощення її можливого використання поданий текст разом з блоком формуванням системи лінійних алгебричних рівнянь, яка має описану матрицю. function [] =FC_Three_Diag_Sys( ) % Розв'язування трьохдіагональних систем лі- нійних алгебричних рівнянь % Ax=b % за допомогою матричних ланцюгових дробів clc n=25; % формування тестової системи лінійних рівнянь for i=1 : n for j=1: n A(i,j)=0; if (i==j) A(i,j)=1.5; end if(i==j+1) A(i,j)=-1; end if(j==i+1) A(i,j)=1; end end b(i)=0; end; b(1)=3; %, обчислення X(1) і решти невідомих D(n)=A(n,n); i=n; while (i>1); i = i-1; D(i)=A(i,i)-A(i+1,i)A(i,i+1)/D(i+1); end; x(1)=b(1)/D(1); i=1; while (i<n) i=i+1; x(i)=-A(i,i-1)x(i-1)/D(i); end x end Серія: Фізико-математичні науки. Випуск 17 127 Результати тестування функції FC_Three_Diag_Sys для 25n  скопійовані з вікна MatLab і подані в наступній таблиці Таблиця 1 Значення n Значення невідомих ix 25 1.5000 0.7500 0.3750 0.1875 0.0938 0.0469 0.0234 0.0117 0.0059 0.0029 0.0015 0.0007 0.0004 0.0002 0.0001 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 Нескладна перевірка показує високу точність запропонованого методу розв'язання трьохдіагональних систем методом ланцюгових дробів. Опис тестування функції ESSELS. Тут мова піде про розв'язуван- ня систем із стрічковим заповненням. Позначимо через L — кількість наддіагоналей, а через M — кількість піддіагоналей конкретної системи лінійних алгебраїчних рівнянь. В такому разі обчислення можна вести, звичайно, і за формулами (2) та (3). Однак з врахуванням характеру за- повнення стрічкової матриці їх можна привести до вигляду                 1 , , 1 , 1 , , 1 1, 1, , 1 , 1, ; , 1, 1 ; , 1,1 . M k i k i j j j i k M k k k k j j j M k kk k k s k s i s ik i s a a x b i k n a a x z b k n z b b z s k                              (6)                 1 , , 1 , 1 , , 1 1, 1, , 1 , 1, ; , 1, 1 ; , 1,1 . L k i k i j j j i k L k k k k j j j L k kk k k s k s i s ik i s a a x b i k n a a x z b k n z b b z s k                              (7) За рекурентними формулами (6) та (7) на деякому k-му кроці об- числюються лише ті bi,j і bj,i, для яких існує хоча б один ненульовий елемент ai,j початкової матриці. Алгоритм дозволяє розв'язати системи рівнянь як у випадку си- метричного заповнення (кількість піддіагоналей дорівнює кількості наддіагоналей), так і тоді, коли кількість піддіагоналей та наддігона- лей матриці різна. Математичне та комп’ютерне моделювання 128 Для перевірки алгоритму розв'язання стрічкового варіанту алго- ритму відсічених систем була використана система рівнянь наступно- го вигляду: 1 2 3 2 1 1 1 0 0 0 0 2 1 1 1 0 0 0 3 1 1 1 1 0 0 2 0 1 1 1 1 0 2 0 0 1 1 1 1 2 0 0 0 1 1 1 1 n n n x x x x x x                                                                                            Легко бачити, що точним розв’язком системи будуть значення  1, 1,2,..., .ix i n  Це несиметрична система рівнянь, без діагона- льного домінування із значенням спектрального числа обумовленості 6.6837 010.AV e  Для розв'язання систем лінійних алгебричних рівнянь з число- вими елементами в середовищі MatLab написана і протестована фун- кція ESSELS. Ця функція реалізує алгоритм розв'язування систем лінійних алгебричних рівнянь методом відсічених систем і написана за допомогою об'єктно-орієнтованої макромови MatLab. З метою її можливого використання поданий текст разом з бло- ком формування системи лінійних алгебричних рівнянь, яка має опи- сану матрицю. function [] =Essels( Dimension ) % << E S S E L S >> — процедура для розв'язан- ня стрiчкових систем % лiнiйних алгебричних рiвнянь. % Написана для MatLab 2010 року за алгоритмом відсічених систем % Вхiднi параметри: % A — двовимiрний масив розмiрностi Nx(LN+1) для зберiгання % вихiдних елементiв системи Ax=b; % N — кiлькiсть невiдомих системи; % N1- параметр рiвний N+1; % CountOvDiag — параметр рiвний кiлькостi над- діагоналей матрицi; % CountUndDiag — параметр рiвний кiлькостi наддіагоналей матрицi; % B — двохмiрний робочий масив розмiрностi Nx(N+1); Серія: Фізико-математичні науки. Випуск 17 129 % Y — одномiрний робочий масив довжини N. % Формування вхідних даних системи Ах=b clc N=70 CountOvDiag=1; CountUndDiag=2; N1=N+1; Np=1; Epsilon=0.001; for i=1 : N if(i>1) A(i-1,i)=1.0;end if(i<N) A(i+1,i)=1.0; end if(i>2) A(i,i-2)=-1.0; end A(i,i)=1.0+Epsilon; A(i,N+1)=2+Epsilon; end A(2,N1)=3+Epsilon; A(N,N1)=1+Epsilon; % Власне алгоритм програми N1 =N+1; Np=1; for i=1 : N for j=1: N B(i,j)=0.0; end end for m=1 : N if m>1 M1=m-1;end if m>2 M2 =m-2; end MP1=m+1; NKN=m+CountOvDiag; if (NKN>=N+1) NKN=N+1; end NKP=m+CountUndDiag; if (NKP>=N) NKP=N; end for i=m : NKP P=A(i,m); if (m>1) if NKP<M1 NM=M1-NKP;else NM=1;end for j=NM : M1 P=P-A(i,j)X(j); end end B(i,m)=P; end Математичне та комп’ютерне моделювання 130 if(m<N) for i=MP1 : NKP B(i,m)=B(i,m)/B(m,m); end end if(m>1) Y(M1)=B(m,M1); end if(m>2) for jr=1 : M2 j=m-jr-1; Y(j)=B(m,j); js=j+1; if(js+CountUndDiag<=M1) MKP=js+CountUndDiag; else MKP=M1; end for i=js : MKP Y(j)=Y(j)-B(i,j)Y(i); end end end for j=MP1 : N1 P=A(m,j); if (m>1) for i=1:M1 P=P-A(i,j)Y(i);end end B(m,j)=P/B(m,m); end X(m)=B(m,MP1); if(m>1) for ir=1 : M1 i=m-ir; X(i)=B(i,MP1); is=i+1; if(is+CountOvDiag<=m) MKN=is+CountOvDiag; else MKN=m; end for j=is : MKN X(i)=X(i)-B(i,j)X(j); end end end end cond(A) X end Результати порівняння обох програм подані в наступній таблиці. Таблиця 2 Значення 70n  Значення невідомих ix Функція ESSELS 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 Серія: Фізико-математичні науки. Випуск 17 131 Таким чином, запропоновані алгоритми для даної тестової сис- теми середньої розмірності мають суттєві переваги у порівнянні із стандартними функціями пакету MatLab. Висновки. У статті розглянуто новий підхід до розв'язування роз- ріджених систем лінійних алгебраїчних рівнянь із блочними елемента- ми. Проведено підрахунок кількостей записів та операцій при чисельній реалізації алгоритму множення матриць. Охарактеризовано складність алгоритму з точки зору комп'ютерної алгебри. Проведено порівняння запропонованого алгоритму та блочного методу прогонки. Обчислено кількість записів для методу прогонки. Протестовано алгоритми розв'я- зання деяких типів розріджених числових систем лінійних алгебричних рівнянь. Показано ефективність запропонованих алгоритмів. Запропоновані алгоритми можуть використовуватися в системах комп'ютерної алгебри та для аналітично-числового розв'язування ін- женерних та прикладних задач. Список використаних джерел: 1. Воеводин В. В. Линейная алгебра / В. В. Воеводин. — СПб. : Лань, 2008. — 416 с. 2. Тыртышников Е. Е. Матричный анализ и линейная алгебра / Е. Е. Тыр- тышников. — М. : Физматлит, 2007. — 480 с. 3. Уилкинсон Дж. Х. Алгебраическая проблема собственных значений / Дж. Х. Уилкинсон. — М. : Наука, 1970. — 564 с. 4. Гантмахер Ф. Р. Теория матриц / Ф. Р. Гантмахер. — 5-е вид. — М. : Фіз- матліт, 2004. — 560 с. 5. Недашковський М. О. Обчислення з   матрицями / М. О. Недашковсь- кий, О. Я. Ковальчук. — К. : Наук. думка, 2007. — 294 с. 6. Ашманов С. А. Методы оптимизации. Линейное программирование : учеб. пособие / С. А. Ашманов. — 2-е изд., перераб. и доп. — М. : Физма- тлит, 2005. — 255 с. 7. Дэвэнпорт Д. Компьютерная алгебра / Д. Дэвэнпорт, И. Сирэ, Э. Тур- нье. — М. : Мир, 1991. — 352 с. 8. Семчишин Л. М. Програмна реалізація розв'язання розріджених систем лінійних алгебраїчних рівнянь / Л. М. Семчишин // Вісник Запорізького національного університету. Серія: фізико-математичні науки : зб. наук. праць. — Запоріжжя : Запорізький національний університет, 2013. — № 2 — С. 91–99. APPLICATION OF RAREFIED NUMERICAL SYSTEMS OF LINEAR ALGEBRAIC EQUATIONS IN MATLAB ENVIRONMENT New approach to the linear algebraic equations rarefied systems with block elements solution and the method of rarefied systems with the specific ways of filling solution is suggested in the article. Calculation of the records number and operations under the numerical realization of the matrix multiplication al- Математичне та комп’ютерне моделювання 132 gorithm is conducted. The algorithm complication from the computer algebra point of view is characterized. The described algorithm is used in the case of systems with the rarefied three-diagonal matrix. Efficiency of the suggested algorithm is shown in the article. Theoreti- cal and methodological basis of investigation comprise methods of optimi- zation and mathematic modeling. Solving systems of linear algebraic equations (SLAR) is always one of the most important tasks of computational mathematics. When solving a wide range of applications, most modern scientists, engineers and techni- cians, as a rule, use packages of computer algebra. The solution of mathe- matical problems using the MATLAB system deserves special attention. Real-time data-oriented, this system performs all calculations in float-point arithmetic, as opposed to competing computer algebra systems REDUCE, MACSYMA, DERIVE, Maple, Mathematica, Theorist, which are domi- nated by integer representations and symbolic data processing. Although for the solution of problems on the boundary of symbolic computing and floating-point computations into the integrated MATLAB system, the ex- tended Symbolic Mathematics Toolbox application package is implement- ed, which implements the maple symbology system interface. One of the important MatLab tools is a set of linear algebra procedures. In the calculus, the linear algebra section is supported by the LINPACK, EISPACK application packages that were created in the 1970s by leading experts in the world, including the founder of MathWorks Inc. K. Mooleer. Actually, the original task of the MatLab system was to create a dialog box for working with linear algebra packages. The MatLab system is an open environment that is developing dynam- ically by the efforts of hundreds and thousands of researchers, because it is both an operational shell and a fairly flexible programming language. One of the strongest points is that MatLab can be written programs and features for multiple use. Key words: rarefied systems, chain fractions, finite sums, quantity of records, algorithm difficulty, computer algebra, algorithm testing. Отримано: 14.05.2018

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

Репозитарії

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