Клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях В. Леонтьева
Предлагается новый подход к решению клеточных алгоритмов для систем линейных алгебраических уравнений с блочными элементами. Описаны блочные модели Леонтьева и Форда. Рассмотрено блочный вариант второго алгоритма отсечных систем, а также описан блочный алгоритм для трехдиагональной системы линейных...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2009 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84543 |
| 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. — С. 24-35. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859594998281928704 |
|---|---|
| author | Семчишин, Л.М. |
| author_facet | Семчишин, Л.М. |
| citation_txt | Клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях В. Леонтьева / Л.М. Семчишин // Компьютерная математика. — 2009. — № 2. — С. 24-35. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Предлагается новый подход к решению клеточных алгоритмов для систем линейных алгебраических уравнений с блочными элементами. Описаны блочные модели Леонтьева и Форда. Рассмотрено блочный вариант второго алгоритма отсечных систем, а также описан блочный алгоритм для трехдиагональной системы линейных алгебраических уравнений. Проведено подсчет количества операций, нужных для реализации блочного варианта второго алгоритма отсечных систем на ЭВМ, а также количества операций во время численной реализации алгоритма умножения матриц. Показана эффективность данного алгоритма.
Запропоновано новий підхід до застосування кліткових алгоритмів для систем лінійних алгебраїчних рівнянь з блочними елементами. Описано блочні моделі Леонтьєва і Форда. Розглянуто блочний варіант другого алгоритму відсічних систем, а також описано блочний алгоритм для трьохдіагональної системи лінійних алгебраїчних рівнянь. Проведено підрахунок кількості операцій, потрібних для реалізації блочного варіанта другого алгоритму відсічних систем на ЕОМ, а також кількість операцій під час числової реалізації алгоритму множення матриць. Показано ефективність запропонованого алгоритму.
New approach to the bit-mapped algorithm for the linear algebraic equation system with block elements is suggested. Leontyev’s and Ford’s block models are described. Block variant of the severed system second algorithm and block algorithm for the three-diagonal system of linear algebraic equations are considered. The number of operations necessary for the severed system second algorithm block variant computer implementation and the number of operations needed for numerical implementation of the matrix multiplication algorithm are summarized. The effectiveness of the suggested algorithm is shown.
|
| first_indexed | 2025-11-27T19:46:43Z |
| format | Article |
| fulltext |
24 Компьютерная математика. 2009, № 2
Предлагается новый подход к
решению клеточных алгоритмов
для систем линейных алгебраи-
ческих уравнений с блочными
элементами. Описаны блочные
модели Леонтьева и Форда. Рас-
смотрено блочный вариант
второго алгоритма отсечных си-
стем, а также описан блочный
алгоритм для трехдиагональной
системы линейных алгебраических
уравнений. Проведено подсчет
количества операций, нужных для
реализации блочного варианта
второго алгоритма отсечных си-
стем на ЭВМ, а также коли-
чества операций во время чи-
сленной реализации алгоритма
умножения матриц. Показана эф-
фективность данного алгоритма.
© Л.М. Семчишин, 2009
ÓÄÊ 518.25
Ë.Ì. ÑÅÌ×ÈØÈÍ
ÊËÅÒÊÎÂÛÅ ÀËÃÎÐÈÒÌÛ
ÄËß ÑÈÑÒÅÌ ËÈÍÅÉÍÛÕ
ÀËÃÅÁÐÀÈ×ÅÑÊÈÕ ÓÐÀÂÍÅÍÈÉ
Ñ ÁËÎ×ÍÛÌÈ ÝËÅÌÅÍÒÀÌÈ
 ÌÎÄÅËßÕ Â. ËÅÎÍÒÜÅÂÀ
Введение. Математическое моделирование в
научных исследованиях и практических при-
менениях является неотъемлемой чертой тех-
нического прогресса. Его эффективность опре-
деляется производительностью ЭВМ, каче-
ством вычислительных алгоритмов и про-
грамм, которые используются. Вычисли-
тельные методы алгебры – один из базовых
инструментов при моделировании на ЭВМ и
важная часть программного обеспечения для
компьютеров всех поколений.
В значительном количестве прикладных
задач возникает необходимость решения
клеточных алгоритмов для систем линейных
алгебраических уравнений с блочными эле-
ментами в моделях В. Леонтьева. Решению
таких систем посвящены работы В.В. Вое-
водина [1] , В.В. Воеводина, Ю.А. Кузне-
цова [2], А.Ф. Волошина, Н.Б. Чорней [3],
Дж. Дзвенпорт, И. Сирэ, Э. Турнье [4],
Х.Д. Икрамова [5], М.О. Недашковского,
В.Я. Скоробагатько [6] ,
В данной работе рассматривается решение
клеточных алгоритмов с некоторыми харак-
терными способами заполнения.
Описание блочных моделей Леонтьева,
Форда. Системы линейных алгебраических
уравнений широко применяются на прак-
тике. Обусловлено это многими объективны-
ми факторами, среди которых можно выде-
лить два основных. Во-первых, значительное
количество задач из экономики имеет свой-
ства делимости и аддитивности. Во-вторых,
КЛЕТКОВЫЕ АЛГОРИТМЫ ДЛЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ ...
Компьютерная математика. 2009, № 2 25
в тех случаях, когда математические модели нелинейные, их можно лине-
аризировать, т. е. приближенно заменить адекватной линейной моделью.
В этом случае уступим точности оценки ситуации и сможем осуществить
необходимые вычисления.
Метод "затраты-выпуск" это мощный и эффективный инструмент для
реализации экономико-технических проектов государственного и межгосудар-
ственного масштаба. В определенной степени, по анализу "затраты-выпуск"
можно сделать вывод о динамике развития экономики в общем, что используют
для программного развития передовые государства с рыночной экономикой. Тем
не менее, многосекторная модель – это модель структуры капитала,
перенесенная на макроэкономический уровень, а "затраты-выпуск" по областям
– статический аспект выпуска и распределения большого количества
разнородной продукции без учета причинно-следственных связей. По значитель-
ному возрастанию объемов производства и резкого изменения его
экономической структуры стали очевидными ограниченные возможности этого
метода для решения современных экономических проблем. Примером
простейшей линеаризованной модели является замена функции двух сменных
(которая, например, выражает критерий эффективности) ее развитием в ряд
Тейлора [7]:
( )
(0) (0) 22(0) (0) (0) 01 2
1 2 1 2 1
1
( , )( , ) ( , ) ( ) 0 .i ii
f x xf x x f x x x x x x
x=
∂
= + − + −
∂∑ (1)
Отбросив 0 ( )20x x− и положив cxxf =),( 21 , получим линейное уравне-
ние, которое отвечает фиксированному значению функции (1). Укажем, что
математические модели реальных задач описываются системами линейных
алгебраических уравнений, которые имеют большую измеримость [8]. Они
содержат десятки, сотни или тысячи уравнений и неизвестных, определения
которых требуют использования электронно-вычислительной техники.
Например, если в ситуации, предложенной Франсуа Кене, для вычислений
достаточно системы трехлинейных уравнений, то в расчетах экономики совре-
менного предприятия, которое выпускает десятки единиц продукции, их будет
уже не меньше количества конечного продукта.
Второй особенностью применения линейных уравнений является тот факт,
что почти все коэффициенты матрицы системы уравнений вычисляют
приблизительно. Поэтому вычисления нужно выполнять с определенной точно-
стью (0,1%, четыре знака после запятой и т. п.). Выбирая методы решения
системы уравнений, следует ориентироваться на те, которые не ухудшают
точности вычислений.
Третьей особенностью практических линейных моделей является блочная
структура коэффициентов матрицы системы уравнений, среди которых есть
много нулей или таких, что повторяются. Например, модель планирования
может характеризоваться блочной структурой (рис. 1), где Е – единичные
подматрицы, а заштрихованные прямоугольники – блоки подматрицы с не-
нулевыми коэффициентами. Остальные элементы – нули.
Л.М. СЕМЧИШИН
Компьютерная математика. 2009, № 2 26
РИС. 1. Блочная структура модели планирования
В 20–30-х годах XX столетия американский экономист Василий Леонтьев
положил начало систематизированному исследованию структуры экономики в
частично разукрупненном виде. При таком подходе производственные процессы
в экономике розукрупняются к уровню N секторов (областей) производства,
хотя и не к уровню отдельных предприятий или фирм, и анализируются
перемещения продуктов, товара, услуг между этими областями. Укажем, что
"чистая область" является некоторой экономической абстракцией. Она не
обязательно существует реально в виде некоторого министерства или объеди-
нения. Например, под областью "электроэнергетика" можно понимать совокуп-
ность всех электростанций независимо от ведомственной принадлежности.
Такая отдаленность областей затрудняет практическое применение добытых
результатов, но, с другой стороны, дает возможность провести детальный анализ
технологической структуры общественного производства и распределения.
Основные предположения модели, которые в дальнейшем будем называть
моделями Леонтьева, такие:
1) в экономической системе вырабатывается, покупается, потребляется
и инвестируется n видов продукции, которые будем обозначать индексами
1, 2, 3,..., п;
2) каждая область вырабатывает лишь один вид продукции. Итак, общее
производство разных товаров исключается. Каждая область вырабатывает
разные товары и поэтому область, которая вырабатывает продукцию вида i ,
будем обозначать индексом 1, 2, 3,..., п;
3) под производственным процессом в каждой области будем понимать
преобразование некоторых (возможно, всех) видов продукции, взятых в опреде-
ленных количествах, на некоторое количество продукции одного или другого
вида. При этом полагается, что соотношения израсходованной и выпущенной
продукции являются постоянными.
В модели Леонтьева такой характер преобразований можно описать так:
если для производства единицы продукции в j -й области нужно израсходовать
ija единиц i -й продукции, то выпуск λ единиц j -й продукции требует затрат
ijaλ единиц i -й продукции ),...,1( ni = . Эти n величин ija называют затрат-
ными (или технологическими) коэффициентами. Допускается, что они
постоянные. По терминологии экономистов в модели сохраняется постоянство
удельного выпуска при постоянных пропорциях затрат (независимо от мас-
штабов производства).
КЛЕТКОВЫЕ АЛГОРИТМЫ ДЛЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ ...
Компьютерная математика. 2009, № 2 27
Обозначим iX – общий объем продукции, выпущенной областью под номе-
ром i за единицу времени (например, год). Эти величины определяют валовой
выпуск i -й области. Часть валового выпуска потребляется в виде затрат,
необходимых для производства. Тогда конечную продукцию iY запишем как
различие между валовым выпуском iX i -й области и продукцией, потребля-
емой как производственные затраты во всей экономической системе. Последняя
часть продукции вычисляется по формуле
1
n
ij j
i
a X
=
∑ .
Обозначив конечную продукцию iY , т. е. часть, которая была потреблена
в непроизводственной сфере для создания запасов, инвестиций, экспорта
и т. п., получим систему уравнений
1
( 1,..., ),
n
i ij j i
i
X a X Y i n
=
− = =∑ (2)
которую называют моделью Леонтьева "затраты-выпуск". Система уравнений
(2) имеет все те свойства, что и любая система линейных алгебраических
уравнений. Одна особенность этой системы вызывает повышенный интерес как
у математиков, так и у экономистов. Эта особенность состоит в том, что из
очевидных экономических соображений и коэффициенты, и сменные системы
уравнений (2) должны быть неотрицательными. Другими словами, нормы затрат
ija , валовые выпуски iX и объемы конечной продукции jY удовлетворяют
условию 0,0,0 ≥≥≥ iiij YXa (i, j = 1,…, n). Отсюда вытекает задача, которая
определяет новую математическую проблему сравнительно с теми, которые
рассматривались: при каких коэффициентах ija и iY существует неотрицатель-
ное решение jX системы уравнений (2).
С экономической точки зрения наличие решения системы уравнений (2)
значит, что она "работает", т. е. модель Леонтьева – продуктивна. А поскольку
модель Леонтьева – Форда является обобщением модели Леонтьева, то есте-
ственно, что она унаследовала проблемы своей предшественницы. А именно:
сложность работы с матрицами большой размерности, плохую обусловленность
и вырождение матрицы нормативных коэффициентов, целочисельные сменные,
что значительно уменьшает возможность применения известных численных
методов, нечеткую информацию о значении нормативных коэффициентов,
разреженность матрицы нормативных коэффициентов. Кроме того, в модели
Леонтьева – Форда, в отличие от модели Леонтьева, появилась еще одна компо-
нента, которая входит в модель со знаком "минус", – производство предметов
потребления. Поэтому очевидной становится проблема разработки эффективных
методов решения эколого-экономической балансовой модели и оптими-
зационных моделей, которые бы учитывали указанные обстоятельства.
Л.М. СЕМЧИШИН
Компьютерная математика. 2009, № 2 28
Одним из подходов, на основе которого были разработаны алгоритмы для
широких классов задач, позволяющим решать указанные проблемы, является
последовательный анализ вариантов, общий формализм которого разработан
в шестидесятые годы двадцатого столетия. Схему последовательного анализа
вариантов с успехом применяют для решения многих задач оптимизации плани-
рования и проектирования. В особенности полезным метод последовательного
анализа вариантов оказывается при построении алгоритмов решения оптими-
зационных задач большой размерности.
Модели В. Леонтьева. Модель в матричном виде имеет следующий вид:
X Ax Y= + (3)
при условиях 0A ≥ , где А – нормы затрат, 0Y > , Y – объем конечной про-
дукции, 0≥x , x – неизвестные.
Модели Леонтьева – Форда. Матричный вариант данной модели имеет
такой вид:
Условие:
1 1,1 1 1,2 2 1
2 2,1 1 2,2 2 2
,
.
.
X A X A X Y
X A X A X Y
= + + ⎫
⎬= + − ⎭
(4)
1,1 1,2
2,1 2,2
A A
A A
⎛ ⎞
⎜ ⎟
⎝ ⎠
, ,...., 1211 AA – нормы затрат производства;
,0
2
1 >⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
Y
Y
21 ,YY – объемы выпущенной продукции;
,0
2
1 ≥⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
X
X
21 , XX – валовые выпуски групп товаров.
Обобщенные модели Леонтьева – Форда. В этом случае система уравне-
ний имеет следующий вид:
1 1,1 1 1,2 2 1,3 3 1
2 2,1 1 2,2 2 2,3 2
3 3,1 1 3,2 2 3,3 3
,
,
.
X A X A X A X Y
X A X A X A Y
X A X A X A Y
= + + + ⎫
⎪= + + − ⎬
⎪= + + − ⎭
(5)
Первое уравнение описывает производство средств производства, второе –
производство предметов потребления, третье – очистительные сооружения.
2. Компьютерные алгоритмы для блочных моделей Леонтьева – Форда
2.1. Блочный вариант второго алгоритма усеченных систем. При ком-
пьютерной реализации моделей Леонтьева и Форда (3) – (5) нужно иметь эффек-
тивные клетковые вычислительные методы решения систем линейных
алгебраических уравнений. В начале рассмотрим системы уравнений с плотно
заполненной матрицей. Для этого случая можно использовать обобщение
второго алгоритма отсеченных систем [9, с. 34]. Предположим, что все главные
миноры порядка ( 1, 2,..., )kp k m= не равняются нулю. Кроме того, введем
к рассмотрению следующие отсеченные системы:
КЛЕТКОВЫЕ АЛГОРИТМЫ ДЛЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ ...
Компьютерная математика. 2009, № 2 29
1
1, 1, 111 12 1
2, 2, 121 22 2
, , 11 2
...
...
... ...... ... ... ...
...
k kk
k kk
k k k kk k kk
X AА А А
X AA A A
X AA A A
−
+
+
+
⎛ ⎞ ⎛ ⎞⎛ ⎞
⎜ ⎟ ⎜ ⎟⎜ ⎟
⎜ ⎟ ⎜ ⎟⎜ ⎟ =
⎜ ⎟ ⎜ ⎟⎜ ⎟
⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠
(6)
и
1
1, 1,,111 21 1
2, 1,212 22 2
, 1,1 2
...
...
... ...... ... ... ...
...
k kk
k kk
k k k kk k kk
Y AА А А
Y AA A A
Y AA A A
−
+
+
+
⎛ ⎞ ⎛ ⎞⎛ ⎞
⎜ ⎟ ⎜ ⎟⎜ ⎟
⎜ ⎟ ⎜ ⎟⎜ ⎟ =
⎜ ⎟ ⎜ ⎟⎜ ⎟
⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠
. (7)
Предположим, что все системы вида (6), (7) уже каким-то способом решены
до порядка lk − включительно.
Тогда для неизвестных kkX и kkY на основе [10, с. 129] можно записать:
1
1, 1 2, 1... 1, 1 ,1 ,2 , 1
1, 1, 1 2, 1... 1, 1 1,1 1,2 1, 1
( ... )( ... )
( ... )( ... )
T
kk k k k k k k k k
kk T
k k k k k k k k k k
A X X X A A A
Y
A X X X A A A
−
− − − − −
+ − − − − + + + −
⎫⎡ ⎤− × ⎪⎣ ⎦= ⎬
⎡ ⎤− ⎪⎣ ⎦⎭
и
1
1, 1 2, 1... 1, 1 1, 2, 1,
, 1 1, 1 2, 1... 1, 1 1, 1 2, 1 1, 1
( ... )( ... )
.
( ... )( ... )
T
kk k k k k k k k k
kk T
k k k k k k k k k k
A Y Y Y A А A
X
A Y Y Y A A A
−
− − − − −
+ − − − − + + − +
⎫⎡ ⎤− × ⎪⎣ ⎦= ⎬
⎡ ⎤× − ⎪⎣ ⎦⎭
После вычисления kkX и kkY сразу можно приступать и к определению
skX и skY , ( )1,2,..., 1 .s k= − Для этого при решении (6) можно восполь-
зоваться соотношениями
( )
, , 1 , ,
1
1
1
, , , 1 , , , 1 ,
1 1
,
.
1, 1
k
s k s k s i i k
i=s+
s 1 s
s i i s j s s j s i j s i j
j j
X B B X
B A Y A A Y A i s n
+
−
− −
− −
= =
⎫
= − ⎪
⎪
⎬
⎛ ⎞ ⎛ ⎞ ⎪= − − = + +⎜ ⎟ ⎜ ⎟ ⎪⎜ ⎟ ⎜ ⎟
⎝ ⎠ ⎝ ⎠ ⎭
∑
∑ ∑
(8)
Л.М. СЕМЧИШИН
Компьютерная математика. 2009, № 2 30
( )
, 1, , ,
1
1
1 1
, , , 1 , , , 1 ,
1 1
,
.
1,
k
s k k s i s i k
i s
s s
i s s s j s j s i s j s j i
j j
Y B B Y
B A Y A A X A i s n
+
= +
−
− −
− −
= =
⎫
= − ⎪
⎪
⎬
⎛ ⎞ ⎛ ⎞ ⎪= − − = +⎜ ⎟ ⎜ ⎟ ⎪⎜ ⎟ ⎜ ⎟
⎝ ⎠ ⎝ ⎠ ⎭
∑
∑ ∑
(9)
Обоснования формул (8)–(9) базируется на том, что
ssssss
ss
ss
sissss
is
is
si
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
B
,,1,2,1
2,2,12,22,1
1,1,11,21,1
,,1,2,1
2,2,12,22,1
1,1,11,21,1
,
...
...............
...
...
/
...
...............
...
...
−
−
−
−
−
−
= . (10)
Здесь , ,,i j i sA B – блоки размерностью pp× . В данном детерминантном ра-
венстве элементами являются матрицы pp× . Таким образом, на основе [10,
с. 128], процесс решения начальной системы может быть реализован сово-
купностью рекуррентных соотношений:
( )
1
1 1
, , , 1 , , , 1 ,
1 1
, , 1
, , 1 , ,
1
;
1, ; 1, ; 1,1 ;
s s
k i k k j k j k k i j k j i
j j
k k k k
k
s k s k s i i k
i s
B A Y A A Y A
X B k n i k n s k
X B B X
−
− −
− −
= =
+
+
= +
⎫⎛ ⎞ ⎛ ⎞
⎪= − −⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎪⎝ ⎠ ⎝ ⎠ ⎪⎪= = = + = − ⎬
⎪
⎪= − ⎪
⎪⎭
∑ ∑
∑
и
( )
1
1 1
, , , 1 , , , 1 ,
1 1
, 1,
, 1, , ,
1
;
1, 1, 1, 1,1 ;
.
s s
i k k k j k j k i k j k i j
j j
r k k k
k
s k k s i s i k
i s
B A Y A A X A
Y B k n i k n s k
Y B B Y
−
− −
− −
= =
+
+
= +
⎫⎛ ⎞ ⎛ ⎞
⎪= − −⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎪⎝ ⎠ ⎝ ⎠ ⎪⎪= = − = + = − ⎬
⎪
⎪= − ⎪
⎪⎭
∑ ∑
∑
Процесс вычисления начинается с левого верхнего угла матрицы системы, и
последовательно находятся решения отсеченных клетковых систем всех порядков.
Остановимся теперь на вычислительных характеристиках метода.
КЛЕТКОВЫЕ АЛГОРИТМЫ ДЛЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ ...
Компьютерная математика. 2009, № 2 31
Особенности реализации алгоритма на ЭВМ
Сложность алгоритма. Подсчитаем количество операций, нужных для реа-
лизации алгоритма на ЭВМ. Пусть pmn = , т. е. данная система состоит из m
блоков p -го порядка. Подсчитаем kQ – количество операций, необходимых для
решения системы, которая состоит из k блоков p -го порядка. Для вычисления
произведения
T
kkkkjikikjikjik AAAXXX ),...,,)(,...,,( 1,12,11,1,,2,1 −+++−−−−−−−
нужно 3( 1)k i p− − умножений и 3)1( pik −− операций добавления (отно-
шения). Кроме того, для определения skB ,1+ также используются по 3)1( pik −−
умножениям и добавлений. Несложные подсчеты показывают, что
.3/42)( 233 lkllkmQk ++−=
Всего нужно решить m пар таких систем. Поэтому общее количество ариф-
метических операций может быть подсчитано так:
3 3 2( )2 4 / 3 .
m m
k
k 1 k 1
Q Q m k l l lk
= =
⎡ ⎤= = − + +⎣ ⎦∑ ∑
Итак, окончательно с точностью до главного члена 34 3Q n≅ и при этом
будет выполнено 332 n операций умножения.
2.2. Описание блочного алгоритма решения разреженных систем.
Рассмотрим систему линейных алгебраических уравнений [10]
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
+
+−
+
+
+
−
−
−−−−−
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
,
элементы которой Aij – это блоки размерностью mm× . Обозначим
⎥
⎦
⎤
⎢
⎣
⎡
k
k
jjj
iii
A
...
...
21
21 минор, размещенный на пересечении блочных лент
kiii ,...,, 21 и блочных столбцов kjjj ,...,, 21 . По обобщенному правилу Крамера
[2] и, разлагая числитель по минорам, можно записать
( )
1 1
, 1 , 1
1 1
1 2 1 2 1 1
1 .
1 2 1 2 1 1
n k
i k
i k n s s
k s i
n i k n
x A A A A A
n i k n
− −
+
+ +
= = +
− +⎛ ⎞ ⎛ ⎞⎡ ⎤ ⎡ ⎤ ⎡ ⎤
= − ⋅⎜ ⎟ ⎜ ⎟⎢ ⎥ ⎢ ⎥ ⎢ ⎥− +⎣ ⎦ ⎣ ⎦ ⎣ ⎦⎝ ⎠ ⎝ ⎠
∑ ∏
… … … …
… … … …
(11)
Л.М. СЕМЧИШИН
Компьютерная математика. 2009, № 2 32
Если ввести обозначение
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
−
+
= +
− +⎡ ⎤ ⎡ ⎤
α = ⋅ =⎢ ⎥ ⎢ ⎥− +⎣ ⎦ ⎣ ⎦
∏
… … …
… … …
тогда для определения неизвестной ix предлагаются соотношения
2 3 ...
2 3 ...
1 2 ...
1 2 ...
i
n
A
n
x
n
A
n
⎡ ⎤
⎢ ⎥
⎣ ⎦= ×
⎡ ⎤
⎢ ⎥
⎣ ⎦
2,
1, 1 , 1 1, 1, 1 1, 1
1,
( ... //n
n n n n n n n
n
A E A A+ + − + −
α
× × + + α α
α
( ), 1 1, 1, 1// / )n n n n nE A A+ − +− α , (12)
где
, 1, 1 1, 2 2, 1 , 1
, 1 , 1 2, 2
1, , 1
,
/
,i n n n n n n n n n
i n n n n n
n n n n
n n
A A A A
A A
A A
A
+ + + + + + +
+ + + +
− −
α
= −
α −
−
(13)
nn
nnnn
A
AA
A
AA
A
E
n
n
A
n
n
A
,
1,,1
2,2
2,11,2
1,1...21
...21
...32
...32
−−−
−
−
=
⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
. (14)
Здесь E означает единичную матрицу.
По аналогичной схеме находим остальные неизвестные ix
( ) ( )
1 1
, 1 , 1
, , 1 , , , 1 ,
1 1
1 2 ...
1 1
1 2 ... 2 2
i n
i k i ki n i n
i i i k n i k i i k n i k
k k i
A An
x A A A
n
− −
+ ++ +
+ +
= = +
⎛ ⎞ ⎛ ⎞⎡ ⎤
= α + − α + α + − α =⎜ ⎟ ⎜ ⎟⎢ ⎥
⎣ ⎦ ⎝ ⎠⎝ ⎠
∑ ∑
( ) ( ) ( )
-12 1 2
1, , 1 , , 1, , 1 ,1 / 1 /i i 2i 1
i i i i i i i i i i i i i iA A 1 A− +
− − + +
⎡ ⎤= − α α + − + − α α ×⎣ ⎦
КЛЕТКОВЫЕ АЛГОРИТМЫ ДЛЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ ...
Компьютерная математика. 2009, № 2 33
( ) ( )
, 1 , 1
1 1
, 1 , 1, 1 , 1 , 1 , 1, 1 , 1
1, 1 , 1 1, 1 , 1
, 1 , , 1 ,
1, 1 ,1 , 1 ,
2, 1 ,2 1, 1
1, 1 ,1
2, 1 ,2
1 1
2 2[
2 2
2 2
i n i n
i n i i i n i i i n i i i n i i
i n i i i n i i
i n i i i n i i
n i n n i n
n i n n
n i
n i
A A
A A A A
E EA A
E E
A A
A A
A A
A
E
A
+ +
− −
+ − + − + + + +
− + − + + +
+ +
+ +
+ − +
+
+
× −
α α α α
− −α α
+ − + −
α α
α α
α α
− −α
+
α
, 1
, 1 ,
1, 1 , 1
]
i n
n n i n
n n i n
A
E
A
−
+
− + −
α
+
α
А для каждого отношения , , 1/i k i k+α α в свою очередь можно записать:
1
, 1
, 1
, 1
, 1 , 1
1
1 2 1 1 1
1 2 1 1 1
1 2 1 2 1
1 2 1 2 1
k
s s
i k s i
k
i k
s s k k
s i
i k n k n
A A A A
i k n k n
i k n k n
A A A A A
i k n k n
−
+
= +
+
+ +
= +
− + +⎡ ⎤ ⎡ ⎤ ⎡ ⎤
⎢ ⎥ ⎢ ⎥ ⎢ ⎥α − + +⎣ ⎦ ⎣ ⎦ ⎣ ⎦= = =
− + +α ⎡ ⎤ ⎡ ⎤ ⎡ ⎤
⎢ ⎥ ⎢ ⎥ ⎢ ⎥− + +⎣ ⎦ ⎣ ⎦ ⎣ ⎦
∏
∏
… … … … …
… … … … …
… … … … …
… … … … …
.
/
,
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
−−
++
++++
++
++++
++
+++++
+
++
−
−
−
−
−==…
Итак, получаем аналитическое развитие неизвестных ix данной разре-
женной системы линейных алгебраических уравнений в оконченные матричные
цепные дроби. Схема может приниматься и для разреженных трех диагональных
заполнений матрицы А .
Вычислительные характеристики алгоритма
Теперь подсчитаем необходимое количество записей при символьном
решении задачи и количество операций во время численной реализации
алгоритма умножения матриц .klij AA ⋅
Утверждение [6]. Пусть некоторая вычислительная задача с входными
данными { }iA решается на ЭВМ по алгоритму 1 2( , ,..., )nA A Aψ и состоит из
k шагов jψ . Если на каждом шаге алгоритма ( )Aψ реализуется хотя бы одна
запись вида
1 2
( ) ( )ji jiA Aψ ⋅ψ , которая использует результат предыдущего шага,
то общая сложность Qψ задачи будет не меньшей 2k · m2, но не большей H k
записей, где Н – наибольшая ширина алгоритма на k шагах.
Л.М. СЕМЧИШИН
Компьютерная математика. 2009, № 2 34
Используем это утверждение для оценки сложности алгоритма с точки
зрения компьютерной алгебры [4]. Для чисел xi ( )1,i n= на одном этаже
реализации алгоритма требуется одно блочное умножение, одно блочное
деление, одно блочное добавление, а для n этажей – 3n операций, т.е. по
n блочным умножений, делений и добавлений.
Вычисления показывают, что для определения всех Ai, k
/ Ai, k + 1 нужно 5k
записей, если ik < , и 5(n – k), если ik > . Таким образом необходимо
выполнить
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
=
⎡ ⎤
+ + − = +⎢ ⎥
⎣ ⎦
∑
Заключение. Рассмотрен метод для линейных алгебраических уравнений с
блочными элементами в моделях Леонтьева и Форда. Предложенный алгоритм
может эффективно использоваться в системах компьютерной алгебры и для
аналитически-числового решения инженерных прикладных задач механики. На
основе предложенного подхода в пакете MatLab проведены числовые
эксперименты для линейных алгебраических уравнений с блочными элемен-
тами. Они подтверждают эффективность алгоритма.
Л.М. Семчишин
КЛІТКОВІ АЛГОРИТМИ ДЛЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ
ІЗ БЛОЧНИМИ ЕЛЕМЕНТАМИ В МОДЕЛЯХ В. ЛЕОНТЬЄВА
Запропоновано новий підхід до застосування кліткових алгоритмів для систем лінійних
алгебраїчних рівнянь з блочними елементами. Описано блочні моделі Леонтьєва і Форда.
Розглянуто блочний варіант другого алгоритму відсічних систем, а також описано блочний
алгоритм для трьохдіагональної системи лінійних алгебраїчних рівнянь. Проведено під-
рахунок кількості операцій, потрібних для реалізації блочного варіанта другого алгоритму
відсічних систем на ЕОМ, а також кількість операцій під час числової реалізації алгоритму
множення матриць. Показано ефективність запропонованого алгоритму.
L.M. Semchyshyn
BIT-MAPPED ALGORITHM FOR THE LINEAR ALGEBRAIC EQUATION SYSTEM WITH
BLOCK ELEMENTS IN THE V. LEONTYEV’S MODELS
New approach to the bit-mapped algorithm for the linear algebraic equation system with block
elements is suggested. Leontyev’s and Ford’s block models are described. Block variant of the
severed system second algorithm and block algorithm for the three-diagonal system of linear
algebraic equations are considered. The number of operations necessary for the severed system
second algorithm block variant computer implementation and the number of operations needed for
numerical implementation of the matrix multiplication algorithm are summarized.
The effectiveness of the suggested algorithm is shown.
КЛЕТКОВЫЕ АЛГОРИТМЫ ДЛЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ ...
Компьютерная математика. 2009, № 2 35
1. Воеводин В.В. Численные методы алгебры. – М.: Наука, 1966. – 246 с.
2. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. – М.: Наука, 1984. – 320 с.
3. Волошин А.Ф., Чорней Н.Б. Исследование алгоритма последовательного анализа вариантов
для модели Леонтьева – Форда с разреженной матрицей нормативных коэффициентов //
Проблемы управления и информатики. – 2001.– № 3. – С. 97–103.
4. Дэвенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра. – М.: Мир, 1991. – 352 с.
5. Икрамов Х.Д. Численное решение матричных уравнений. – М.: Наука, 1984. – 192 с.
6. Недашковський М.О., Скоробогатько В.Я. Розв'язування систем лiнiйних алгебраїчних
рiвнянь методом гiллястих ланцюгових дробiв. В кн.: Теоретичнi та прикладнi питання
алгебри i диференцiальних рiвнянь. – К.: Наук. думка, 1977. – С. 84–92.
7. Гантмахер Ф.Р. Теория матриц. – М.: Наука, 1967. – 324 с.
8. Дейнека В.С., Сергиенко И.В. Модели и методы решения задач в неоднородных средах. –
Киев: Наук. думка, 2001. – 606 с.
9. Недашковський М.О., Ковальчук О.Я. Обчислення з λ -матрицями. – К.: Наук. думка,
2007. – 294 с.
10. Семчишин Л.М. Розв’язання розріджених систем лінійних алгебраїчних рівнянь із блоч-
ними елементами. В кн.: Фізико-математичне моделювання та інформаційні технології. –
Львів; 2007. – Вип. 6. – С. 128–135.
Получено 10.03.2009
Îá àâòîðå:
Семчишин Лидия Михайловна,
преподаватель кафедры высшей математики и компьютерной техники
Чортковского института предпринимательства и бизнеса
Тернопольского национального экономического университета.
Lida55718@ukr.net
|
| id | nasplib_isofts_kiev_ua-123456789-84543 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-11-27T19:46:43Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Семчишин, Л.М. 2015-07-10T11:34:23Z 2015-07-10T11:34:23Z 2009 Клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях В. Леонтьева / Л.М. Семчишин // Компьютерная математика. — 2009. — № 2. — С. 24-35. — Бібліогр.: 10 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84543 518.25 Предлагается новый подход к решению клеточных алгоритмов для систем линейных алгебраических уравнений с блочными элементами. Описаны блочные модели Леонтьева и Форда. Рассмотрено блочный вариант второго алгоритма отсечных систем, а также описан блочный алгоритм для трехдиагональной системы линейных алгебраических уравнений. Проведено подсчет количества операций, нужных для реализации блочного варианта второго алгоритма отсечных систем на ЭВМ, а также количества операций во время численной реализации алгоритма умножения матриц. Показана эффективность данного алгоритма. Запропоновано новий підхід до застосування кліткових алгоритмів для систем лінійних алгебраїчних рівнянь з блочними елементами. Описано блочні моделі Леонтьєва і Форда. Розглянуто блочний варіант другого алгоритму відсічних систем, а також описано блочний алгоритм для трьохдіагональної системи лінійних алгебраїчних рівнянь. Проведено підрахунок кількості операцій, потрібних для реалізації блочного варіанта другого алгоритму відсічних систем на ЕОМ, а також кількість операцій під час числової реалізації алгоритму множення матриць. Показано ефективність запропонованого алгоритму. New approach to the bit-mapped algorithm for the linear algebraic equation system with block elements is suggested. Leontyev’s and Ford’s block models are described. Block variant of the severed system second algorithm and block algorithm for the three-diagonal system of linear algebraic equations are considered. The number of operations necessary for the severed system second algorithm block variant computer implementation and the number of operations needed for numerical implementation of the matrix multiplication algorithm are summarized. The effectiveness of the suggested algorithm is shown. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Математическое моделирование Клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях В. Леонтьева Кліткові алгоритми для систем лінійних алгебраїчних рівнянь із блочними елементами в моделях В. Леонтьєва Bit-mapped algorithm for the linear algebraic equation system with block elements in the V. Leontyev’s models Article published earlier |
| spellingShingle | Клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях В. Леонтьева Семчишин, Л.М. Математическое моделирование |
| title | Клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях В. Леонтьева |
| title_alt | Кліткові алгоритми для систем лінійних алгебраїчних рівнянь із блочними елементами в моделях В. Леонтьєва Bit-mapped algorithm for the linear algebraic equation system with block elements in the V. Leontyev’s models |
| title_full | Клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях В. Леонтьева |
| title_fullStr | Клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях В. Леонтьева |
| title_full_unstemmed | Клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях В. Леонтьева |
| title_short | Клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях В. Леонтьева |
| title_sort | клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях в. леонтьева |
| topic | Математическое моделирование |
| topic_facet | Математическое моделирование |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84543 |
| work_keys_str_mv | AT semčišinlm kletkovyealgoritmydlâsistemlineinyhalgebraičeskihuravneniisbločnymiélementamivmodelâhvleontʹeva AT semčišinlm klítkovíalgoritmidlâsistemlíníinihalgebraíčnihrívnânʹízbločnimielementamivmodelâhvleontʹêva AT semčišinlm bitmappedalgorithmforthelinearalgebraicequationsystemwithblockelementsinthevleontyevsmodels |