Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва

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

Full description

Saved in:

Bibliographic Details
Published in:	Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
Date:	2009
Main Author:	Семчишин, Л.М.
Format:	Article
Language:	Ukrainian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2009
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/18604
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:	Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва / Л.М. Семчишин // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2009. — Вип. 2. — С. 121-133. — Бібліогр.: 6 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859787878425427968
author	Семчишин, Л.М.
author_facet	Семчишин, Л.М.
citation_txt	Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва / Л.М. Семчишин // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2009. — Вип. 2. — С. 121-133. — Бібліогр.: 6 назв. — укр.
collection	DSpace DC
container_title	Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
description	У статті розглянено новий підхід до розв’язання системи лінійних алгебраїчних рівнянь В. Леонтьєва із прямокутними λ-матрицями. Створено оптимізаційну модель з матрицями міжгалузевого балансу та запропоновано ефективний обчислювальний метод реалізації цієї моделі. Проаналізовано деякі нові підходи до обчислювальних алгоритмів. Описано ефективний метод розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами. New approach to the V. Leontiev’s linear algebraic equation with right angled λ-matrix system solution is considered. The optimization models with inter branch balance matrix are made and the effective calculating method of this model realization is suggested. Some new approaches to calculative algorithms are analyzed. The effective method of linear algebraic equation with block elements rarefied system solution is described.
first_indexed	2025-12-02T11:06:58Z
format	Article
fulltext	Серія: Фізико-математичні науки. Випуск 2 121 УДК 518.25 Л. М. Семчишин, викладач Чортківський інститут підприємництва і бізнесу, Тернопільський на- ціональний економічний університет, м. Тернопіль РОЗВ’ЯЗАННЯ ПРЯМОКУТНИХ ТА РОЗРІДЖЕНИХ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ З λ-МАТРИЦЯМИ В МОДЕЛЯХ В. ЛЕОНТЬЄВА У статті розглянено новий підхід до розв’язання системи лінійних алгебраїчних рівнянь В. Леонтьєва із прямокутними −λ матрицями. Створено оптимізаційну модель з матрицями міжгалузевого балансу та запропоновано ефективний обчис- лювальний метод реалізації цієї моделі. Проаналізовано деякі нові підходи до обчислювальних алгоритмів. Описано ефекти- вний метод розв’язування розріджених систем лінійних алгеб- раїчних рівнянь із блочними елементами. Ключові слова: статична модель Леонтьєва, прямокутні −λ матриці, розріджені системи, ланцюгові дроби, кількість записів, обчислювальні алгоритми. Вступ. Успішне розв’язання численних задач економіки стало можливим лише завдяки широкому використанню математичних мо- делей, обчислювальних методів і комп’ютерних технологій. Застосу- вання математики в економіці дозволяє виділити й формально описа- ти найголовніші зв’язки між економічними змінними та параметрами об’єктів дослідження, індуктивним шляхом одержати нові відомості про об’єкт, зробити важливі теоретичні висновки і прийняти прави- льні економічні рішення. Головні переваги математики як засобу на- укового пізнання найповніше розкриваються саме у процесі побудови математичних моделей. Постановка проблеми. Під моделлю економіки розумітимемо опис математичними методами процесів з метою встановлення кіль- кісних і логічних залежностей між різними елементами економічних систем (факторами, інгредієнтами). Залежно від того, на який еконо- мічний процес звертається основна увага, при побудові й дослідженні моделі використовується відповідний математичний апарат. Обчислювальний експеримент дозволяє за найменший час екс- плуатації ЕОМ із заданою точністю кількісно та якісно описати дос- ліджувану проблему, інакше кажучи побудувати математичну мо- дель, аналіз якої в свою чергу дозволяє глибше проникнути в суть явища, що вивчається. Процес дослідження певних явищ за допомогою математичного моделювання, можна умовно розділити на 4 етапи. © Л. М. Семчишин, 2009 Математичне та комп’ютерне моделювання 122 Перший етап — формулювання і запис у математичних термі- нах і символах якісних уявлень про зв’язки між параметрами процесу або об’єктами, здійснених на основі глибокого вивчення функціону- вання досліджуваного явища. Другий етап — дослідження одержаної математичної моделі. Тут основним є отримання кількісної вихідної інформації, яку дає розв’язання математичної задачі. Третій етап — з’ясування того, чи задовольняє прийнята гіпо- тетична модель критерію практики, тобто чи узгоджуються результа- ти спостережень з теоретичними висновками моделі в межах точності спостережень. Четвертий етап — повторний аналіз моделі у зв’язку з накопи- ченням даних про досліджуванні явища. Аналіз останніх публікацій. У роботі [6, с. 128—135] запропо- новано новий підхід до розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами. Проведено підрахунок кількостей записів та операцій при чисельній реалізації алгоритму множення матриць. Актуальність теми. Розв’язання прямокутних та розріджених систем лінійних рівнянь з λ -матрицями великого розміру в моделях В. Леонтьєва вимагає застосування ефективних чисельних методів. Слід зауважити, що питання розв’язання розріджених систем лі- нійних рівнянь з λ -матрицями розглядалися у працях [5]. Однак, лише в окремих з них розглядаються питання щодо розв’язання пря- мокутних систем лінійних рівнянь [1]. Мета роботи. Метою роботи є проведення аналізу розв’язання, одержання деяких теоретичних оцінок та розгляд підходів розв’язку одержаних систем числових рівнянь. Основна частина. У міжгалузевому балансі технологічні зв’язки між галузями ви- значаються коефіцієнтами прямих матеріальних витрат ; 1, , 1, ,ij ij j x a i n j n x = = = (1) які показують витрати продукції −i ої галузі на виробництво одиниці продукції j-ої галузі. Очевидно, що валова продукція кожної i-ої галу- зі виробника ix складається з проміжної (продукції виробничого споживання) 1 n ij j x = ∑ та кінцевої продукції iy , тобто ( ) 1 , 1, n i jij j x x y i n = = + =∑ (2) Серія: Фізико-математичні науки. Випуск 2 123 Враховуючи співвідношення (1) запишемо ( ) 1 , 1, n i jj j j x a x y i ni i − = + =∑ (3) або в матрично-векторній формі ,X Ax y= + (4) де ( )Tnxxxx ,...,, 21= та ( )Tnyyyy ,...,, 21= — відповідно вектори ва- лової й кінцевої продукції, а матриця ( ) ( )njiaA ij ,1,, == — матриця коефіцієнтів прямих матеріальних витрат. В економіко-математичній літературі систему (4) прийнято називати статичною моделлю Леон- тьєва [3, с. 8]. Розглянемо систему лінійних алгебраїчних рівнянь В. Леонтьєва із прямокутними −λ матрицями. Запишемо систему (4) у вигляді ( ) ( ) ( ) ( ),λλλλ yXAX += (5) Звідси ( )( ) ( ) ( ),λλλ yXEA −=− де ( )λA — матриця розміру mn × , елементи якої є поліномами від λ . Припустимо, що значення для λ і коефіцієнтів многочленів беруться з деякого поля F таким чином: елементи матриці ( )λA обчислюються для деякого часткового значення λ , наприклад, .0 mnF ×∈= λλ ( )λy — вектор ( ) ( ) ( )( )1, 2, ,, ,..., . T m m n ma a aλ λ λ Мат- риця ( )λA і вектор ( )λy мають степінь l , тобто ( ) ( ), 0 , 1, , 1, 1 l l k ij i j k a a i n j mλ λ − = = = = +∑ . Подамо матрицю ( )λA і вектор ( )λy у вигляді матричних мно- гочленів: ( ) l ll AAAA +++= − ...1 1 0 λλλ та ( ) l ll yyyy +++= − ...1 1 0 λλλ . Розв’язок системи шукається у вигляді частки двох поліномів з невідомими коефіцієнтами. ( ) 0 0 , nl nl i i i nl nl i i i x X t z λ λ − = − = = ∑ ∑ (6) де K — ранг матриці ( ) ,EA −λ ln10 ,...,, xxx — вектори розмірності r, а ln10 ,...,, zzz — скалярні величини. Тоді систему (5) можна записати наступним чином. Математичне та комп’ютерне моделювання 124 ( )10 0 0 1 1 0 0 0 ... nl nl nl i nl i i i l l l l ii i l l inl nl nl i nl i i i i i i x x A A A A y z z λ λ λ λ λ λ λ λ − − − −= = − − − = = = = + + + + ⋅ + ∑ ∑ ∑ ∑ ∑ Домноживши, праву і ліву частини рівності на 0 nl nl i i i zλ − = ∑ мати- мемо: ( )1 0 1 1 0 0 0 0 ... . nl nl i l l i l l i nl l nl nl i l i nl i i i i i i i x A A A A x y x λ λ λ λ λ λ λ − − − = − − − = = = = + + + + × × + ⋅ ∑ ∑ ∑ ∑ Звідси, ( ) ( ) ( ) ( ) 1 2 2 0 1 2 2 1 1 1 0 1 1 0 1 1 2 2 0 1 2 2 1 ... ... ... ... 0. nl nl nl nl nl nl l l l l l l l nl nl nl nl nl nl x x x x x x E A A A A y y y z z z z z z λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ − − − − − − − − − − − + + + + + + × × − − − − − + + + + × × + + + + + + = Відкривши дужки та згрупувавши члени у лівій і правій части- нах рівності при однакових степенях λ запишемо: ( ) ( ) ( ) ( ) 1 2 2 0 1 2 2 1 1 1 2 0 1 1 0 1 2 2 1 2 1 0 1 1 1 2 2 0 1 2 2 1 ... ... ... ... ... . nl nl nl nl nl nl l l nl nl nl l l l l nl nl nl l l nl nl nl nl nl nl x x x x x x A A A A x x x x x x y y y y z z z z z z λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ − − − − − − − − − − − − − − − − + + + + + + = = + + + + ⋅ + + + + + + + + + + + + × × + + + + + + Звідси, 0 1 2 2 ( 1) 0 1 2 2 1 0 0 ( 1) 1 1 ( 1) 1 ( 1) 2 0 1 0 1 0 1 0 1 1 1 ( 1) 2 ( 1) 3 1 1 1 1 2 0 2 1 2 1 2 ... ... ... ... nl nl nl l n nl nl nl l n l n l n l n l n l l n l n l n l n l n l l l l n x x x x x x x A x A x A x A x A x A x A x A x A x A x A λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ − − + − − + − + + − + − − − + − + − − − − −  + + + + + + − − − − − − − − − − − − − − − − − 2 1 3 2 2 2 0 2 1 2 1 2... ...l l l nl nl nl l nl lx A x A x A x A x Aλ λ λ λ+ + − − − − −− − − − − − − − 3 2 1 1 0 1 1 1 1 1 0 1... ...l l l nl nl nl l nl l nl nlx A x A x A x A x A x Aλ λ λ λ λ λ − − − − − −− − − − − − − − ] 0 ( 1) ( 1) 1 ( 1) 2 1 0 0 1 0 2 l n l n l n nl l nl lx A x A y z y z y zλ λ λ λ+ + − + − − − − + + + + 2 1 ( 1) 1 ( 1) 2 0 2 0 1 0 1 0 1 1 l l l l n l n nl nl nly z y z y z y z y zλ λ λ λ λ+ + + − + − − −+ + + + + + Серія: Фізико-математичні науки. Випуск 2 125 ] ( 1) 3 1 1 1 2 1 2 1 1 1 0 1 2 2 1 2 2 1 ... ... ... 0 . l n l l l nl nl nl nl l nl nl l l l nl nl l nl l y z y z y z y z y z y z y z y z z y z y λ λ λ λ λ λ λ λ λ + − + − − − − − − − + + + + + + + + + + + + + + = Оскільки ( ) ,n mA Fλ ×∈ а ( ) nFy ∈λ , то в загальному випадку, прирівнявши коефіцієнти при однакових степенях, одержимо число- ву систему ( )1++ slm рівнянь з ( )1+sm невідомими ijx і ( )1+s неві- домими jz 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 2 0 2 1 1 0 0 0; 0; 0; ........................................ ................. 0; ........................................ ................. l l s p s s p s s s A x y z A x A x y z y z A x A x y z y z A x y z− − = = − − = − − − − = − − − − = − − =∑ ∑ 1 1 1 1 0; 0 nl l nl nl l nl l nl l nl nl l x A x x A z y x A x z y − − − −             − − − =  − − = (7) Даний підхід дозволяє проводити аналіз розв’язання прямокут- них систем, а також одержувати деякі теоретичні оцінки. Можна застосувати кілька обчислювальних алгоритмів для розв’язання одержаних систем числових рівнянь (7). Розглянемо де- які найбільш ефективні підходи. Стрічкова схема розрізання. Схематична матриця числової сис- теми може бути подана у вигляді: ,                           × ×× ××× ×××× ×××× ××× ×× × I II III IIII IIII III II I (8) де через ""× позначені квадратні клітки, а через "" I — прямокутні блоки. Математичне та комп’ютерне моделювання 126 Для визначеності будемо вважати, що система (7) складається з ( )1++ slm рівнянь і має ( ) kslm +++ 1 невідомих ( )1≥k . Нехай, { }nmArank ,min0 = . Перестановкою стовпців систему (8) можна перетворити таким чином, щоб її матриця набула заповнення: ,                           × ×× ××× ×××× ×××× ××× ×× × I II III IIII IIII III II I (9) Загальна стратегія розв’язання цієї системи залежить від її рангу. Спочатку розглянемо найбільш трудомісткий з обчислювальної точки зору варіант числової системи. Для цього припустимо, що всі головні мінори схематично нарисованої матриці не дорівнюють нулю. Тоді перші ( )1++ slm невідомих можуть бути виражені через k останніх розв’язків системи (7). При зроблених припущеннях про характер мат- риці (9) підматриця, утворена блоками ""× буде невиродженою. Таким чином, схематично процес перетворення матриці системи може бути представлений у вигляді                           ⇒                           × ×× ××× ×××× ×××× ××× ×× × IIIII IIIII IIIII IIIII IIII III II I I II III IIII IIII III II I O O O O O Для реалізації алгоритму на ЕОМ потрібно виконати з точні- стю до головного члена 34lCm арифметичних операцій. При цьому величина константи C залежить від вибраного алгоритму зведення матриці до діагонального вигляду. Серія: Фізико-математичні науки. Випуск 2 127 Схема діагоналізації. Економічні алгоритми можна також одер- жати з врахуванням того, що матриця системи (7) має клітково- тепліцеве стрічкове заповнення. Не зважаючи на те, що клітки не є квадратними , а прямокутними, в загальному випадку цю обставину вдається використати досить вдало. Однорідну кліткову систему з прямокутними блоками (7) для наглядності подальших міркувань, запишемо у матричному вигляді: ,0 ... ... ... ... ... ............ ... ... ... ... ............ ............ ... ... ... .................. 1 2 1 0 2 1 2 1 0 111 1001 001 01 011 012 011 0211 2012 101 00 =                                                                                                             − −− −− − − − − − + −+ + + + −− − − − − −− NNl NNl NNl N N N ll lll l ll ll l l ll lll y y y y y X X X X X X X BA BBAA BBAAA BAAA AAA AAA AAAA AAAA BAAAA BAAA BAA BA де ijA — прямокутні клітки розмірності ( )1+nn . Процес перетворення матриці системи схематично може бути поданий у вигляді І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І ×       × ×       × × ×     × × × ×   ⇒ ⇒   × × × ×     × × ×       × ×      ×    O O O O O Математичне та комп’ютерне моделювання 128 . І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І І              ⇒               O O O O O O O O O Опишемо схему обчислень: Крок 1. Переставимо місцями стовпці матриці таким чином, щоб у лівій частині залишилось 1++ sl кліткових стовпців, по m стовпців у кожному. Якщо ранг хоча б однієї з матриць 0A чи lA дорівнює m , то в лівому блоці матриць можна позбутись піддіагональних або над- діагональних елементів відповідно. Крок 2. Без обмеження загальності припустимо, що mArank =0 і саме m стовпців, які є лінійно незалежними, залишаються зліва в кожному з кліткових стовпців. Шляхом еквівалентних перетворень можна в лівому блоці матриці системи позбутись піддіагональних елементів. Цей блок матриці має клітково–тепліцеву структуру. З урахуванням цього достатньо провести перетворення одного клітко- вого стовпця ( )0 1 T m m mlA A A а тоді одержати з його елементів реш- ту. Для виконання елементарних перетворень лівого блоку достатньо виконати 222334 mllmm ++ операцій множення і додавання. Виявляється, що при цьому достатньо просто можна врахувати і зміни всіх стовпців у правій частині матриці. Оскільки еквівалентні перетворення не змінюють тепліцевої структури заповнення правого блоку матриць [2], то права частина теж залишиться клітково- тепліцевою. В силу цього достатньо виконати всі перетворення над першим клітковим стовпцем правого блоку. А отже, ненульові еле- менти решти стовпців отримаємо шляхом послідовного зсуву елеме- нтів попереднього стовпця на m позицій вниз. Таким чином, для пе- ретворення елементів правого блоку потрібно виконати з точністю до головного члена ( )( )( )2211 3 4 lmmslmn +++−+ адитивних і таку ж кількість мультиплікативних операцій на ЕОМ. Крок 3. На даному етапі виконаємо зведення матриці до трапе- цевидної форми. Після виконання попереднього кроку в правому Серія: Фізико-математичні науки. Випуск 2 129 блоці позбудемося піддіагональних елементів в останніх (l+1)m рів- няннях. Для цього необхідно виконати не більше, ніж 3334 ml опе- рацій множення і додавання. Крок 4. На цьому етапі розв’язується система з матрицею трапе- цевидної форми. Для цього потрібно не більше, ніж ( ) 21 mlsl ++ арифметичних дій. Загальна кількість операцій всіх кроків розгляну- того алгоритму з точністю до головного члена може бути порахована в наступний спосіб: ( )( ) ( )++−+++++= 111234 223 lmmnsllmmQ 3334 ml+ . На початку було зроблено припущення, що { }nmArank ,min0 = . Нехай також без обмеження загальності найбільший головний мінор       rank rank A ...321 ...321 є ненульовим. Тоді блок з клітково-тепліцевим заповненням можна звести до трикутної, а потім і до діагональної форми, затративши по 2332 nln + додавань і множень. У силу тепліцевого заповнення відпадає необхідність у перетво- ренні решти кліткових стовпців. Виявляється, що при цьому достат- ньо просто врахувати зміни стовпців правого блоку. Дійсно, оскільки елемент ija даного стовпця ( ) ( )( ),...31,21 22 ++++= lnlnj може бути одержаний з ( )2 1 1n l + +  -го стовпця зсувом його елементів на ( )2 2 1 1n j n l − + +  позицій вниз. Крок 5. Після виключення в системі (6) векторів lX залишиться система порядку nl відносно ....,,, 10 nlyyy Якщо позначити через r її ранг ( )nlr ≤ , то розв’язання системи у загальному випадку вимага- тиме 3342 rnlr + операцій. Таким чином, загальна складність розглянутого алгоритму скла- дає ( )333332 nmnln ++ адитивних і ( )333332 nmnln ++ мультипліка- тивних операцій. Для реалізації методу на ЕОМ потрібно ( ) 22 nl + комірок пам’яті машини. Опис блочного варіанту методу розв’язування розріджених сис- тем лінійних рівнянь. Розглянемо систему лінійних алгебраїчних рівнянь [6]. Математичне та комп’ютерне моделювання 130                     =                                         + +− + + + − − −−−−− 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 , елементи якої ijA — це блоки розмірності m × m. Позначимо через       k k jjj iii A ... ... 21 21 мінор, розміщений на перетині блочних стрічок kiii ,..., 21 та блочних стовпців kjjj ,..., 21 . За узагальненим правилом Крамера [1] і розкладаючи чисельник за мінорами, можна записати ( ) ×   −              = ∑ = + + − n k nk ki A n n Aix 1 1, 1 1 21 21 … …          + + ∏⋅      − − × − += + nk nk AA i i A k is ss …… …… … … 1 1 121 121 1 1 1, (10) Якщо ввести позначення .,1,, 1 1 121 121 1 1 1, nki nk nk AA i i A k is ssik =      + + ⋅      − − = ∏ − += + …… …… … … α то тоді для визначення невідомої ix пропонуються співвідношення (2, 1, 1 , 1 1, 1, 1 1, 1 1, 2 3 ... 2 3 ... ... / 1 2 ... 1 2 ... n i n n n n n n n n n A n x A E A A n A n α α α α + + − + −      = × × + +       ), 1 1, 1, 1 1, 1/ n n n n n nE A Aα α+ − + −− , (11) де ( ) ×             =−              = ∑ = + + − 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 … … … … … … α Серія: Фізико-математичні науки. Випуск 2 131 1,11,1 ,11, 1,11,1,11, 2,11,2 3,11,3 2,11,23,11,3 2,11,1 2,11,2 1,11,12,11,2 1,1 / / / −+− + −+−+ + + ++ + + ++ + − + +− +− + × nnn nnn nnnnnn n n nn n n nn n A A E AA A A E AA A A E AA E A α α αα α α αα α α αα O O (12) Тут E — означає одиничну матрицю. Вираз kk ,1 1 1,1 αα ⋅− + ( )…,2,1=k також можна розкласти в ланцюгові дроби 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 α α + + + +      = = −    −   −    … … … … … … =       − − −            = ++++ 11 11 1 1 1 1 1,,11,1 ,1 k k AAA k k AA k k A kkkkkk k … … … … … … =             − − − = − ++++ k k A k k AAAA E kkkkkk … … … … 1 1 11 11 1 1,,11,1 =               − −       − = − ++++ T T T kkkkkk k k A k k AAAA E 11 11 1 11 1,,11,1 … … … … .,1. 1,1 1,22,1 1,1 1,,1 , 1,,1 1,1 nk A AA A AA A AA A E kk kkkk kk kkkk kk = − − − == − −− −− ++ ++ O O … Математичне та комп’ютерне моделювання 132 За аналогічною схемою знаходимо решту невідомих ix . А для кожного відношення 1,, / +kiki αα в свою чергу можна записати: =       + +       − −       + +       − − = ∏ ∏ += + − += + + k is ss k is ss ki ki nk nk AA i i A nk nk AA i i A 1 1, 1 1 1, 1, , 2 2 121 121 1 1 121 121 …… …… … … …… …… … … α α =       + +       + + = + nk nk AA nk nk A kk …… …… …… …… 1 1 1 1 1, . / , 1,,1 4,4 3,44,3 3,3 3,22,3 2,2 1,1,22,1 1, 1,1 nn nnnn kk kkkk kk kkkk kk kkkkkk kk kk A AA A AA A AA A AAA A A −− ++ ++++ ++ ++++ ++ +++++ + ++ − − − − −== O … O Отже, одержуємо аналітичне розвинення невідомих xj даної ро- зрідженої системи лінійних алгебраїчних рівнянь у скінчені матричні ланцюгові дроби. Обчислювальні характеристики алгоритму Тепер підрахуємо необхідну кількість записів при символьному розв’язуванні задачі та кількість операцій під час чисельної реалізації алгоритму множення матриць .klij AA ⋅ Використаємо твердження [6, с. 132] для оцінки складності алго- ритму з точки зору комп’ютерної алгебри [4]. Для чисел ix ( )ni ,1= на одному поверсі реалізація алгоритму вимагає одне блочне множення, одне блочне ділення, одне блочне додавання, а для n поверхів — 3n операцій, тобто по n блочних множень, ділень та додавань. Обчислення показують, що для визначення всіх Ai, k / Ai, k + 1 пот- рібно 5k записів, якщо k < i, і 5(n — k), якщо k > i. Таким чином не- обхідно виконати 1 2 2 (1 ) ( )( 1)5 5 5 ( 1) 2 2 5 . 2 2 i n k k i i i i n n ik n k n n i n ni ni = = + + − + + − = + − + − =     = + + −    ∑ ∑ Серія: Фізико-математичні науки. Випуск 2 133 Отже, загальна складність методу становить 2 2 3 1 55 ( ). 2 2 2 n i n ni ni n n =   + + − = +    ∑ Висновки. У статті розглянено новий підхід до розв’язання сис- теми лінійних алгебраїчних рівнянь В. Леонтьєва із прямокутними −λ матрицями. Створено оптимізаційну модель з матрицями міжга- лузевого балансу та запропоновано ефективний обчислювальний ме- тод реалізації цієї моделі. Проаналізовано деякі підходи до обчислювальних алгоритмів. Описано метод розв’язування розріджених систем лінійних алгебраї- чних рівнянь із блочними елементами. Запропонований алгоритм може ефективно використовуватися в системах комп’ютерної алгебри, в економіко-математичних дослі- дженнях та для аналітично-числового розв’язання інженерних прик- ладних задач. На основі запропонованого підходу в пакеті MatLab були прове- дені числові експерименти для лінійних алгебраїчних рівнянь із бло- чними елементами. Вони підтверджують ефективність алгоритму. Список використаних джерел: 1. Беллман Р. Теория матриц / Р. Беллман. — М. : Мир, 1985. — 366 с. 2. Воеводин В. В. Вычислительные процессы с теплицевыми матрицами / В. В. Воеводин, Е. Е. Тыртышников. — М. : Наука, 1987. — 320 с. 3. Григорків В. С. Моделювання економіки. Частина 2. / В. С. Григорків. — Чернівці : Рута, 2006. — 100 с. 4. Дэвенпорт Дж. Компьютерная алгебра / Дж. Дэвенпорт, И. Сирэ, Э. Турнье. — М. : Мир, 1991. — 352 с. 5. Недашковський М. О. Обчислення з −λ матрицями / М. О. Недашковсь- кий, О. Я. Ковальчук. — К. : Наук. думка, 2007. — 294 с. 6. Семчишин Л. М. Розв’язання розріджених систем лінійних алгебраїчних рівнянь із блочними елементами / Л. М. Семчишин // Фізико-математичне моделювання та інформаційні технології. — Вип. 6. — Львів 2007. — С. 128—135. New approach to the V. Leontiev’s linear algebraic equation with right angled −λ matrix system solution is considered. The optimization models with inter branch balance matrix are made and the effective calcu- lating method of this model realization is suggested. Some new ap- proaches to calculative algorithms are analyzed. The effective me- thod of linear algebraic equation with block elements rarefied sys- tem solution is described. Key words: Leontiev’s static model, right-angled −λ matrix, rarefied system, chain fractions, the number of registrations, calculative algorithms. Отримано: 08.04.2009
id	nasplib_isofts_kiev_ua-123456789-18604
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	XXXX-0059
language	Ukrainian
last_indexed	2025-12-02T11:06:58Z
publishDate	2009
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Семчишин, Л.М. 2011-04-05T18:40:23Z 2011-04-05T18:40:23Z 2009 Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва / Л.М. Семчишин // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2009. — Вип. 2. — С. 121-133. — Бібліогр.: 6 назв. — укр. XXXX-0059 https://nasplib.isofts.kiev.ua/handle/123456789/18604 518.25 У статті розглянено новий підхід до розв’язання системи лінійних алгебраїчних рівнянь В. Леонтьєва із прямокутними λ-матрицями. Створено оптимізаційну модель з матрицями міжгалузевого балансу та запропоновано ефективний обчислювальний метод реалізації цієї моделі. Проаналізовано деякі нові підходи до обчислювальних алгоритмів. Описано ефективний метод розв’язування розріджених систем лінійних алгебраїчних рівнянь із блочними елементами. New approach to the V. Leontiev’s linear algebraic equation with right angled λ-matrix system solution is considered. The optimization models with inter branch balance matrix are made and the effective calculating method of this model realization is suggested. Some new approaches to calculative algorithms are analyzed. The effective method of linear algebraic equation with block elements rarefied system solution is described. uk Інститут кібернетики ім. В.М. Глушкова НАН України Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва Article published earlier
spellingShingle	Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва Семчишин, Л.М.
title	Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва
title_full	Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва
title_fullStr	Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва
title_full_unstemmed	Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва
title_short	Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва
title_sort	розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях в. леонтьєва
url	https://nasplib.isofts.kiev.ua/handle/123456789/18604
work_keys_str_mv	AT semčišinlm rozvâzannâprâmokutnihtarozrídženihsistemlíníinihrívnânʹzmatricâmivmodelâhvleontʹêva

Розв’язання прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва

Institution

Similar Items