Решение линейных систем с помощью декомпозиции
Введены и исследованы специальные подмножества уравнений линейной системы, именуемые кланами. Предложено использовать декомпозицию на кланы для ускорения решения линейной системы. Сложность декомпозиции равна кубу от размера системы. Поэтому ускорение вычислений получено для методов, сложность котор...
Gespeichert in:
| Datum: | 2005 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2005
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/13813 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Решение линейных систем с помощью декомпозиции / Д.А. Зайцев // Систем. дослідж. та інформ. технології. — 2005. — № 2. — С. 131-143. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860076120974557184 |
|---|---|
| author | Зайцев, Д.А. |
| author_facet | Зайцев, Д.А. |
| citation_txt | Решение линейных систем с помощью декомпозиции / Д.А. Зайцев // Систем. дослідж. та інформ. технології. — 2005. — № 2. — С. 131-143. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| description | Введены и исследованы специальные подмножества уравнений линейной системы, именуемые кланами. Предложено использовать декомпозицию на кланы для ускорения решения линейной системы. Сложность декомпозиции равна кубу от размера системы. Поэтому ускорение вычислений получено для методов, сложность которых превышает кубическую. Для целочисленных систем, решаемых в целой неотрицательной области, ускорение вычислений является экспоненциальным.
Special subsets of equations of linear system named by clans were introduced and studied. It was proposed to use the decomposition into clans for the acceleration of linear system solving. Decomposition complexity equals cube depending on size of system. Therefore, acceleration of computations was obtained for methods with complexity exceeding cube. For integer systems solving in nonnegative integer numbers acceleration of computations obtained is exponential.
Введені і та досліджені спеціальні підмножини рівнянь лінійної системи, названі кланами. Запропоновано використовувати декомпозицію на клани для прискорення вирішення лінійної системи. Складність декомпозиції дорівнює кубу від розміру системи. Тому прискорення обчислень отримано для методів, складність яких перебільшує кубічну. Для цілочисельних систем, що вирішуються в цілочисельній невід’ємній області, прискорення обчислювань експоненційне.
|
| first_indexed | 2025-12-07T17:13:34Z |
| format | Article |
| fulltext |
Д.А. Зайцев, 2005
Системні дослідження та інформаційні технології, 2005, № 2 131
УДК 512.8+519.74
РЕШЕНИЕ ЛИНЕЙНЫХ СИСТЕМ С ПОМОЩЬЮ
ДЕКОМПОЗИЦИИ
Д.А. ЗАЙЦЕВ
Введены и исследованы специальные подмножества уравнений линейной сис-
темы, именуемые кланами. Предложено использовать декомпозицию на кланы
для ускорения решения линейной системы. Сложность декомпозиции равна
кубу от размера системы. Поэтому ускорение вычислений получено для мето-
дов, сложность которых превышает кубическую. Для целочисленных систем,
решаемых в целой неотрицательной области, ускорение вычислений является
экспоненциальным.
ВВЕДЕНИЕ
Задача решения линейной системы — классическая задача линейной алгеб-
ры [1]. Известны различные методы решения линейной системы [1,2]. Сле-
дует отметить, что выбор метода существенно зависит от множества ис-
пользуемых чисел. Точнее, от алгебраической структуры, образуемой
переменными и коэффициентами. Наиболее полно изучено решение систем
в полях и телах, например, в действительных и рациональных числах. Эти
алгебраические структуры содержат всюду определенную операцию деле-
ния, что удобно для построения простых и мощных методов. Различают
точные и приближенные методы решения систем. Наиболее известен метод
Гаусса, состоящий в последовательном исключении переменных и получе-
нии треугольной матрицы.
Алгебраическая структура кольца, например, целых чисел, требует раз-
работки специальных методов, так как деление не является всюду опреде-
ленной операцией в кольце. Известный универсальный метод решения сис-
тем в кольцах основан на использовании унимодулярных преобразований
матрицы системы для приведения ее к нормальной форме Смита [1,2]. Ре-
зультирующая матрица имеет диагональную форму и позволяет получить
простую форму представления решений. К сожалению, этот метод экспоне-
нциальный. К настоящему времени предложены более сложные, но полино-
миальные методы [3,4,5]. Наиболее интересные из них основаны на после-
довательном решении систем в полях классов вычетов по модулям простых
чисел и последующем построении общего решения исходной системы [3].
Развитие таких областей компьютерных наук, как теория сетей Петри
[6], логическое программирование [7], искусственный интеллект [8], потре-
бовало решения целочисленных систем на множестве неотрицательных це-
лых чисел. Заметим, что неотрицательные целые имеют алгебраическую
структуру моноида, в котором даже вычитание не всюду определено. Все
известные методы решения целочисленной системы в неотрицательных це-
лых числах являются экспоненциальными [9,10,11], что создает значитель-
ные трудности в применении этих методов для анализа реальных систем и
процессов.
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 132
Например, если сложность метода приближенно равна q2 , где q — ра-
змер системы, то для решения системы размера 100 потребуется около 3010
операций. Компьютер с быстродействием 910 операций в секунду будет
выполнять эту работу в течение 2110 секунд или 1210 лет.
Таким образом, задача разработки эффективных методов решения ли-
нейных систем, особенно в целых неотрицательных числах, является доста-
точно актуальной. Цель настоящей работы — представление метода реше-
ния линейной системы с помощью декомпозиции на кланы. Применение
этого метода позволяет существенно ускорить вычисления. В случае экспо-
ненциальной сложности исходного метода решения системы полученное
ускорение также экспоненциально.
ПРЕДСТАВЛЕНИЕ ОБЩЕГО РЕШЕНИЯ ЛИНЕЙНОЙ СИСТЕМЫ
Рассмотрим линейную однородную систему из m уравнений с n неизвест-
ными
0=xA , (1)
где A — матрица коэффициентов размерности nm× ; x — вектор-столбец
неизвестных размерности n . Мы не будем указывать точно множества зна-
чений переменных и коэффициентов. Предположим только, что известен
метод, позволяющий решить систему (1) и представить общее решение в
форме
yGx = , (2)
где G — матрица базисных решений, а y — вектор-столбец свободных пе-
ременных. Каждый из столбцов матрицы G является базисным решением.
Для получения частного решения системы значения компонент вектора y
могут быть выбраны произвольно из множества значений переменных x .
Заметим, что система (1) всегда имеет, по крайней мере, тривиальное нуле-
вое решение. Для краткости назовем однородную систему несовместимой,
если она имеет только тривиальное решение.
Рассмотрим неоднородную систему
bxA = , (3)
где b — вектор-столбец свободных членов размерности m . Предположим,
что существует метод решения системы (3), позволяющий представить об-
щее решение в форме
Gyxx +′= , (4)
где Gy — общее решение соответствующей однородной системы (1), а
x′ — минимальное частное решение неоднородной системы (3).
В соответствии с [1] приведенные выше результаты справедливы для
произвольных полей и колец, а в соответствии с [11] они также справедливы
для решений структуры моноида при структуре кольца элементов матрицы
A и вектора b . В последнем случае для неоднородной системы следует
рассматривать множество минимальных решений x′ .
Решение линейных систем с помощью декомпозиции
Системні дослідження та інформаційні технології, 2005, № 2 133
ДЕКОМПОЗИЦИЯ СИСТЕМЫ
Представим систему (1) в виде предиката
)(...)()()( 21 xLxLxLxS m∧∧∧= , (5)
где )(xLi — уравнения системы
)0()( == xaxL i
i ;
ia — i-я строка матрицы A . Предположим также, что ia — ненулевой век-
тор, т. е., по крайней мере, одна из компонент ia ненулевая. Обозначим X
множество неизвестных системы. Рассмотрим множество уравнений
}{ iL=ℑ системы S . Введем отношения на множестве ℑ .
Определение 1. Отношение близости. Два уравнения ℑ∈ji LL , близ-
ки и обозначаются как ji LL , если и только если Xxk ∈∃ : 0, ,, ≠kjki aa ,
)(sign)(sign ,, kjki aa = .
Утверждение 1. Отношение близости рефлексивно и симметрично.
Доказательство.
• Рефлексивность: ii LL . Так как ia — ненулевой вектор, то сущест-
вует Xxk ∈ : 0, ≠kia . Тогда тривиально )(sign)(sign ,, kiki aa = .
• Симметричность: ijji LLLL ⇒ . Отношение симметрично в соот-
ветствии с симметричностью отношения равенства ⇒= )(sign)(sign ,, kjki aa
)(sign)(sign ,, kikj aa = .
Определение 2. Отношение клана. Два уравнения ℑ∈ji LL , принад-
лежат к одному и тому же клану и обозначаются ji LL , если и только ес-
ли существует последовательность (возможно пустая) уравнений
klll LLL ,...,,
21
таких, что jlli LLLL
k
...
1
. Заметим: отношение клана пред-
ставляет собой транзитивное замыкание отношения близости.
Теорема 1. Отношение клана является отношением эквивалентности.
Доказательство. Требуется доказать, что отношение клана рефлексив-
но, симметрично и транзитивно.
• Рефлексивность: ii LL . Так как определение 2 допускает пустые
последовательности уравнений и отношение близости рефлексивно в соот-
ветствии с утверждением 1, то и отношение клана рефлексивно.
• Симметричность: ijji LLLL ⇒ . Так как ji LL , то в соответ-
ствии с определением 2 существует последовательность
klll LLL ,...,,
21
та-
кая, что jlli LLLL
k
...
1
. Так как отношение близости симметрично в
соответствии с утверждением 1, то для обратной последовательности
11
,...,, lll LLL
kk −
выполняется illj LLLL
k
1
... . Тогда ij LL .
• Транзитивность: liljji LLLLLL ⇒, . Так как ji LL ,
lj LL , то в соответствии с определением 2 существуют
kiii LLL ,...,,
21
=σ и
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 134
rlll LLL ,...,,
21
=ς такие, что jiii LLLL
k
...
1
и lllj LLLL
r
...
1
. Рас-
смотрим конкатенацию ςσ jL . Эта последовательность связывает элементы
iL и lL цепочкой из элементов, удовлетворяющих отношению близости.
Таким образом li LL .
Следствие. Отношение клана задает разбиение множества ℑ : =ℑ
j
j
C= , ∅=ji CC , ji ≠ .
Определение 3. Клан. Элемент разбиения },{ ℑ назовем кланом и обо-
значим jC .
Определение 4. Переменные { ≠∈∃∈== ik
j
kii
jj aCLXxxCXX ,:,)(
}0≠ назовем переменными клана jC . Переменные )( j
i CXx ∈ являются
внутренними переменными клана jC , если и только если для всех осталь-
ных кланов lC , jl ≠ выполняется l
i Xx ∉ . Множество внутренних пере-
менных клана jC обозначим jX
. Переменная Xxi ∈ является контактной
переменной, если и только если существуют такие кланы jC и lC , что
j
i Xx ∈ , l
i Xx ∈ . Множество всех контактных переменных обозначим 0X .
Обозначим также множество контактных переменных клана jC как jX
таким образом, что jjj XXX
= и ∅=jj XX
.
Лемма 1. Контактная переменная 0Xxi ∈ не может принадлежать раз-
личным кланам с одним и тем же знаком.
Доказательство. Предположим противное. Пусть переменная Xxi ∈
содержится в различных кланах kjjj CCC ,...,, 21 с одним и тем же зна-
ком, причем 1>k . Следовательно, в соответствии с определением 3 су-
ществуют уравнения 1
1
j
l CL ∈ , 2
2
j
l CL ∈ , … , k
k
j
l CL ∈ такие, что 0,1
≠ila ,
0,2
≠ila ,…, 0, ≠ilka и )(sign...)(sign)(sign ,,, 21 iiilil k
aaa === . Тогда в соот-
ветствии с определениями 2 и 3 уравнения
klll LLL ,...,,
21
принадлежат к од-
ному и тому же клану. Таким образом получаем противоречие.
Теорема 2. Контактная переменная 0Xxi ∈ содержится ровно в двух
кланах.
Доказательство. Предположим противное. Пусть контактная перемен-
ная Xxi ∈ содержится в q различных кланах, и 2≠q .
Рассмотрим отдельно два случая:
• 2<q . Тогда в соответствии с определением 5 переменная ix не яв-
ляется контактной.
• 2>q . Получаем противоречие с леммой 1, так как существуют
только два различных знака: плюс и минус.
Определение 5. Клан jC назовем входным кланом контактной пере-
менной 0Xxi ∈ и обозначим )( ixI , если и только если он содержит эту пе-
Решение линейных систем с помощью декомпозиции
Системні дослідження та інформаційні технології, 2005, № 2 135
ременную со знаком плюс. Клан jC назовем выходным кланом контактной
переменной 0Xxi ∈ и обозначим )( ixO , если и только если он содержит эту
переменную со знаком минус. Аналогичную классификацию на входные и
выходные можно ввести также и для контактных переменных.
Таким образом, получено, с одной стороны, разбиение множества ура-
внений на кланы, а с другой — разбиение переменных на внутренние и кон-
тактные. Введем новую нумерацию уравнений и переменных. Нумерацию
уравнений начнем с уравнений первого клана и так далее до последнего
клана разбиения. Нумерацию переменных начнем с контактных переменных
и продолжим для внутренних переменных в порядке возрастания номеров
кланов. Упорядочим множества уравнений и переменных в соответствии с
новой нумерацией. В результате получим следующую блочную форму
представления матрицы A:
kk AA
AA
AA
A
000
000
000
,0
22,0
11,0
= .
Более наглядно матрица A показана в таблице, в которой хорошо вид-
ны кланы и подмножества переменных, соответствующие блокам матрицы.
Блочное представление матрицы системы
Клан
Переменные
0X 1X
2X
. . . kX
1C 1,0A 1A
0 . . . 0
2C 2,0A 0 2A
. . . 0
kC kA ,0 0 0 . . . kA
Заметим, что строка матрицы представляет клан, а ее столбцы соответ-
ствуют вектору разбиения множества переменных ( )kXXXX
210 . Рас-
смотрим более подробно структуру матрицы для контактных переменных.
В соответствии с определением 4 jX
обозначает контактные переменные
клана jC . Тогда j
j
XX
=0 , но это не является разбиением множества 0X ,
так как каждая контактная переменная 0Xxi ∈ в соответствии с теоремой 2
принадлежит двум кланам. Далее будем использовать также матрицы jA
.
Заметим, что в отличие от jA ,0 , которая содержит значения для всех конта-
ктных переменных 0X , матрица jA
содержит значения только для контак-
тных переменных jX
клана jC . Другими словами, матрица jA
содержит
только ненулевые столбцы матрицы jA ,0 . Применение теоремы 2 к матрице
A показывает, что каждая контактная переменная 0Xxi ∈ содержится с
ненулевыми коэффициентами ровно в двух матрицах множества jA ,0 ,
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 136
kj ,1= , и, кроме того, появляется в одной из матриц с положительными
коэффициентами, а в другой — с отрицательными.
РЕШЕНИЕ СИСТЕМЫ
Решим систему отдельно для каждого клана. Если рассматривать только пе-
ременные клана, то имеем систему уравнений
0=jj xA , (6)
где
jjj AAA
= , j
j
j
x
xx
= .
Систему (6) обозначим )(xS
jC . Заметим, что значения jXX \ могут
быть выбраны произвольно. Более подробно:
)()( & xLxS l
CL
C
j
l
j
∈
= .
Теорема 3. Если система (1) имеет нетривиальное решение, то каждая
из систем (6) также имеет нетривиальное решение.
Доказательство. Рассмотрим представление (5) системы (1). Так как в
соответствии с теоремой 1 отношение клана задает разбиение множества
уравнений, то представление (5) может быть записано в форме
)(...)()()( 21 xSxSxSxS kCCC ∧∧∧= . (7)
Таким образом, произвольное решение (1) является решением каждой
из систем (6).
Следствие. Если, по крайней мере, одна из систем (6) несовместима, то
и вся система (1) несовместима.
Пусть общее решение системы (6) в соответствии с (2) имеет вид
jjj yGx = . (8)
Каждая внутренняя переменная j
i Xx
∈ входит ровно в одну систему
(6). Таким образом, для всех внутренних переменных кланов справедливо
jjj yGx
= .
Каждая контактная переменная j
i Xx
∈ в соответствии с теоремой 2
принадлежит ровно двум системам )(xS
jC и )(xS
lC , где )( i
j xOC = ,
).( i
l xIC = Следовательно, ее значения должны совпадать
l
i
j
i xx = или ll
i
jj
i yGyG = ,
где j
iG обозначает строку матрицы jG , соответствующую переменной ix .
Таким образом, получаем систему
Решение линейных систем с помощью декомпозиции
Системні дослідження та інформаційні технології, 2005, № 2 137
==∈=
==
).(),(,,
,,1,
0
i
l
i
j
i
ll
i
jj
i
jjj
xICxOCXxyGyG
kjGyx (9)
Так как выражение (7) является эквивалентным представлением исход-
ной системы (1) и имеется разбиение множества X на контактные и внут-
ренние переменные, то приведенные выше рассуждения доказывают сле-
дующую теорему.
Теорема 4. Система (9) эквивалентна системе (1).
Уравнения системы (9) для контактных переменных
ll
i
jj
i yGyG =
можно представить как
0=− l
j
l
i
j
i y
yGG .
Занумеруем все переменные jy так, чтобы получить общий вектор
Tkyyyy ...21= ,
и объединим матрицы j
iG , l
iG− в общую матрицу F . Тогда получим сис-
тему
0=yF .
Эта система имеет вид (1), следовательно, ее общее решение имеет вид (2)
zRy = . (10)
Построим объединенную матрицу G решений (8) системы (6) для всех
кланов таким образом, что
yGx = . (11)
Матрица имеет такую блочную структуру:
T
kk GJ
GJ
GJ
G
000
000
000
22
11
= .
Поясним структуру первого столбца блочного представления, который
соответствует контактным переменным. Для каждой контактной перемен-
ной 0Xxi ∈ строим столбец так, что либо блок jJ , либо lJ содержит соот-
ветствующий столбец из jG
, либо lG
, где )( i
j xOC = , )( i
l xIC = . Дейст-
вительно, так как контактная переменная принадлежит двум кланам, то ее
значения могут быть вычислены в соответствии с общим решением как для
входного клана, так и для выходного.
Подставим (10) в (11):
zRGx = .
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 138
Таким образом,
zHx = , RGH = . (12)
Так как были использованы только эквивалентные преобразования,
приведенные выше рассуждения доказывают следующую теорему.
Теорема 5. Выражение (12) — общее решение однородной системы (1).
Выполним аналогичные преобразования для неоднородной системы (3).
Общее решение системы для каждого клана в соответствии с (4) имеет вид
jjjj yGxx +′= . (13)
Уравнения для контактных переменных можно представить следую-
щим образом:
ll
i
l
i
jj
i
j
i yGxyGx +′=+′
и
i
ll
i
jj
i byGyG ′=− , j
i
l
ii xxb ′−′=′
либо в матричной форме
byF ′= .
Общее решение этой системы в соответствии с (4) можно записать так:
zRyy +′= .
Используя объединенную матрицу G , представим (13) как
yGxx +′=
или
( ) zRGyGxzRyGxx +′+′=+′+′=
и
zHyx +′′= , yGxy ′+′=′′ , RGH = . (14)
Так как были использованы только эквивалентные преобразования, до-
казана следующая теорема.
Теорема 6. Выражение (14) представляет общее решение неоднород-
ной системы (2).
Таким образом построены общие решения однородных и неоднородных
линейных систем, полученные с помощью декомпозиции системы на кланы.
ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ СИСТЕМЫ
В соответствии с теоремами 3 и 5 решение линейной однородной системы
уравнений (1) с помощью декомпозиции состоит из следующих этапов:
Этап 1. Выполнить декомпозицию системы (1) на множество кланов
}{ jC .
Этап 2. Для каждого из кланов jC решить систему (6) jjj Gyx = . Ес-
ли, по крайней мере, одна из систем (6) несовместима, то исходная система
(1) также несовместима. Останов.
Решение линейных систем с помощью декомпозиции
Системні дослідження та інформаційні технології, 2005, № 2 139
Этап 3. Построить и решить систему (9) для контактных переменных
Rzy = . Если система несовместима, то исходная система (1) также несов-
местима. Останов.
Этап 4. Скомпоновать матрицу G и вычислить матрицу H базисных
решений GRH = . Останов.
Заметим, что этапы 2 и 3 используют известный метод решения линей-
ной системы. Выбор этого метода определяется используемым множеством
чисел. Например, это может быть метод Гаусса для рациональных чисел,
приведение к нормальной форме Смита для целых чисел и метод Тудика
при нахождении целых неотрицательных решений. Кроме того, аналогич-
ный подход в соответствии с теоремой 6 может быть применен также и для
неоднородных систем.
Опишем более подробно алгоритм декомпозиции, используемый на
этапе 1. Пусть q — максимальный размер матрицы A : ),(max nmq = . От-
ношение клана может быть вычислено стандартным способом как транзити-
вное замыкание отношения близости. Но этот способ с вычислительной то-
чки зрения достаточно трудоемкий.
Приведенный ниже алгоритм декомпозиции имеет вычислительную
сложность, пропорциональную 3q .
;1:=j
while ∅≠ℑ
do
;: ∅=jC
);(,:cur ℑ∈= LLC
;\: Lℑ=ℑ
do
;:new ∅=C
for L′ in Ccur
for L ′′ in ℑ
if LL ′′′ then do ;\: L ′′ℑ=ℑ ;new:new LCC ′′= od;
;cur: CCC jj =
;new:cur CC =
od until ∅=Cnew
;1: += jj
od;
Алгоритм формирует кланы jC из исходного множества уравнений ℑ
системы. Для построения транзитивного замыкания алгоритм сравнивает
каждое уравнение множества Ccur с каждым уравнением множества ℑ .
Уравнения, включенные в клан, исключаются из множества ℑ . Использо-
вание двух вспомогательных подмножеств Ccur и Cnew позволяет срав-
нивать каждую пару уравнений однократно. Так как вычисление отношения
близости имеет линейную трудоемкость, то общая сложность алгоритма
пропорциональна 3q .
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 140
Пусть )(qM — сложность решения линейной системы размера q .
Оценим общую сложность решения линейной системы с помощью декомпо-
зиции.
Пусть исходная система (1) состоит из k кланов. Тогда размер каждого
из них можно оценить как kqp /= . Остаток от деления рассматривать не
будем. Предположим также, что количество контактных позиций имеет тот
же порядок, что и p . Следующее выражение дает оценку сложности реше-
ния системы с помощью декомпозиции
33 )()()()()()( pkpMpMkpkpkVqV +++== .
Каждое из слагаемых этого выражения — оценка вычислительной
сложности соответствующего этапа. Упростим выражение
)()()1(2)( 3333 pMkpkpMkpkpkV +≈++= .
Оценим ускорение вычислений от использования декомпозиции. Иско-
мое выражение имеет вид
)(
)()( 33 pMkpk
pkMpkAcc
+
= .
Таким образом, даже для полиномиальных методов степени, превы-
шающей кубическую, получаем ускорение больше единицы. Оценим уско-
рение для методов, имеющих экспоненциальную сложность qqM 2)( = та-
ких, как, например, метод Тудика [9,10]
pq
p
q
p
q
kpk
qEAcc −=≈
+
= 2
2
2
2
2)( 33 .
Получено экспоненциальное ускорение, что является достаточно хоро-
шим результатом.
ПРИМЕР РЕШЕНИЯ СИСТЕМЫ
Решим однородную систему вида (1) из девяти уравнений с десятью пере-
менными. Пусть матрица системы имеет вид
0000011000
1100010000
1120010000
2011000010
0011000010
0100001100
0100201100
0001100001
0001100201
−
−−
−−
−−
−−
−−
−−
−−
−−
=A .
Решение линейных систем с помощью декомпозиции
Системні дослідження та інформаційні технології, 2005, № 2 141
Этап 1. Декомпозиция. Система состоит из двух кланов
},,,{ 6521
1 LLLLC = , },,,,{ 98743
2 LLLLLC = .
Она имеет такие множества переменных кланов:
},,,,,,{ 72110863
1 xxxxxxxX = , },,,,,,{ 95410863
2 xxxxxxxX = .
В том числе:
контактные
},,,{ 10863
210 xxxxXXX ===
и внутренние
},,{ 721
1 xxxX =
, },,{ 954
2 xxxX =
.
В соответствии с новой нумерацией переменных
( )95472110863=nx
и новой нумерацией уравнений
( )987436521=Ln
матрица A имеет вид
0110000000
1100001000
1100000200
1010000001
1010000021
0001102100
0001100100
0001010010
0001010012
−
−−
−
−−
−−
−−
−−
−−
−−
=A .
Этап 2. Решение систем для кланов. Применение алгоритма Тудика
[9,10] дает следующие матрицы базисных решений для кланов:
T
G
1110000
0101100
1100011
1 = ,
T
G
1110000
10011112 =
по отношению к векторам свободных переменных Tyyyy ),,( 1
3
1
2
1
1
1 = и
Tyyy ),( 2
2
2
1
2 = .
Этап 3. Решение системы для контактных переменных. Система урав-
нений для контактных переменных
Д.А. Зайцев
ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 142
=−
=−
=−
=−
.0
,0
,0
,0
2
1
1
2
2
1
1
2
2
1
1
1
2
1
1
1
yy
yy
yy
yy
Отметим, что уравнения соответствуют контактным переменным
10863 ,,, xxxx . Первое уравнение совпадает со вторым, третье — с четвер-
тым. Базисные решения системы
T
R
10000
00100
01011
= .
Этап 4. Компоновка решения исходной системы. Как было ранее отме-
чено, матрица G может быть построена различными способами:
T
G
1110000000
1000000000
0001110000
0000101100
0001100011
=
либо
T
G
1110000000
1000001111
0001110000
0000100000
0001100000
= .
И, наконец, результирующая матрица базисных решений системы (1)
T
GRH
1110000000
0001110000
1001201111
== .
Полученный результат совпадает с базисными решениями, вычислен-
ными обычным способом с помощью алгоритма Тудика [9,10].
ЗАКЛЮЧЕНИЕ
В настоящей работе предложен новый метод решения линейных систем с
помощью декомпозиции на кланы. Применение метода целесообразно, если
используемый алгоритм решения системы имеет вычислительную слож-
ность, превышающую полином третьей степени, а также в случае, если сис-
тема может быть разложена не менее чем на два клана.
Решение линейных систем с помощью декомпозиции
Системні дослідження та інформаційні технології, 2005, № 2 143
В результате применения рассмотренного метода к решению конкрет-
ных систем уравнений можно сделать вывод, что хорошая способность к
разложению присуща разреженным матрицам. А это достаточно реалистич-
ная ситуация, так как модели реальных объектов большой размерности со-
держат, как правило, хорошо локализованные взаимосвязи элементов.
Следует отметить взаимосвязь декомпозиции систем уравнений и сетей
Петри [12]. Действительно, матрицу )(sign AD = можно рассматривать как
матрицу инцидентности некоторой сети Петри.
Наиболее существенное ускорение вычислений получено для целочис-
ленных систем, решаемых на множестве неотрицательных целых чисел. Для
таких систем известны только экспоненциальные методы решения. Полу-
ченное ускорение вычислений является экспоненциальным.
ЛИТЕРАТУРА
1. Б.Л. ван дер Варден. Алгебра. — М: Наука, 1979. — 624 c.
2. Схрейвер А. Теория линейного и целочисленного программирования. В 2 т. —
М.: Мир, 1991. — 726 c.
3. Фрумкин М.А. Алгоритм решения систем линейных уравнений в целых числах
// Исследования по дискретной оптимизации. — М.: Наука, 1976. — С. 97–
127.
4. Pottie L, Minimal Solutions of linear Diophantine systems: bounds and algorithms //
Proc. of the Fourth Intern. Conf. on Rewriting Techn. and Appl., Como, Italy,
1991. — Р. 162–173.
5. Contejan E., Ajili F. Avoiding slack variables in solving linear Diophantine equa-
tions and inequations // Theoretical Computer Science. — 1997. — 173. —
Р. 183–208.
6. Мурата Т. Сети Петри: Свойства, анализ, приложения // ТИИЭР. — 1989. —
77, № 4. — С. 541–580.
7. Lloyd J. Foundation of logic programming. — Berlin: Springer-Verlag, 1987. —
216 р.
8. Baader F., Ziekmann J. Unification theory. Handbook of logic in artificial intelli-
gence and logic programming. — Oxford: Univ. Press, 1994. — Р. 1–85.
9. Toudic J.M. Linear Algebra Algorithms for the Structural Analysis of Petri Nets //
Rev. Tech. Thomson CSF. — 1982. — 14, № 1. — P. 136–156.
10. Zaitsev D.A. Formal Grounding of Toudic Method // Proceedings of the 10th Work-
shop «Algorithms and Tools for Petri Nets». — Eichstaett, Germany, September
26–27, 2003. — Р. 184–190.
11. Крывый С.Л. О некоторых методах решения и критериях совместимости сис-
тем линейных диофантовых уравнений в области натуральных чисел // Ки-
бернетика и системный анализ. — 1999. — № 4. — С. 12–36.
12. Zaitsev D.A. Subnets with Input and Output Places // Petri Net Newsletter, April
2003. — 64. — P. 3–6, Cover Picture Story.
Поступила 13.02.2004
РЕШЕНИЕ ЛИНЕЙНЫХ СИСТЕМ С ПОМОЩЬЮ ДЕКОМПОЗИЦИИ
Д.А. ЗАЙЦЕВ
ВВЕДЕНИЕ
ПРЕДСТАВЛЕНИЕ ОБЩЕГО РЕШЕНИЯ ЛИНЕЙНОЙ СИСТЕМЫ
ДЕКОМПОЗИЦИЯ СИСТЕМЫ
РЕШЕНИЕ СИСТЕМЫ
ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ СИСТЕМЫ
ПРИМЕР РЕШЕНИЯ СИСТЕМЫ
ЗАКЛЮЧЕНИЕ
|
| id | nasplib_isofts_kiev_ua-123456789-13813 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-12-07T17:13:34Z |
| publishDate | 2005 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Зайцев, Д.А. 2010-12-02T15:09:48Z 2010-12-02T15:09:48Z 2005 Решение линейных систем с помощью декомпозиции / Д.А. Зайцев // Систем. дослідж. та інформ. технології. — 2005. — № 2. — С. 131-143. — Бібліогр.: 12 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/13813 512.8+519.74 Введены и исследованы специальные подмножества уравнений линейной системы, именуемые кланами. Предложено использовать декомпозицию на кланы для ускорения решения линейной системы. Сложность декомпозиции равна кубу от размера системы. Поэтому ускорение вычислений получено для методов, сложность которых превышает кубическую. Для целочисленных систем, решаемых в целой неотрицательной области, ускорение вычислений является экспоненциальным. Special subsets of equations of linear system named by clans were introduced and studied. It was proposed to use the decomposition into clans for the acceleration of linear system solving. Decomposition complexity equals cube depending on size of system. Therefore, acceleration of computations was obtained for methods with complexity exceeding cube. For integer systems solving in nonnegative integer numbers acceleration of computations obtained is exponential. Введені і та досліджені спеціальні підмножини рівнянь лінійної системи, названі кланами. Запропоновано використовувати декомпозицію на клани для прискорення вирішення лінійної системи. Складність декомпозиції дорівнює кубу від розміру системи. Тому прискорення обчислень отримано для методів, складність яких перебільшує кубічну. Для цілочисельних систем, що вирішуються в цілочисельній невід’ємній області, прискорення обчислювань експоненційне. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Решение линейных систем с помощью декомпозиции Linear system solving with the help of decomposition Вирішення лінійних систем за допомогою декомпозиції Article published earlier |
| spellingShingle | Решение линейных систем с помощью декомпозиции Зайцев, Д.А. Нові методи в системному аналізі, інформатиці та теорії прийняття рішень |
| title | Решение линейных систем с помощью декомпозиции |
| title_alt | Linear system solving with the help of decomposition Вирішення лінійних систем за допомогою декомпозиції |
| title_full | Решение линейных систем с помощью декомпозиции |
| title_fullStr | Решение линейных систем с помощью декомпозиции |
| title_full_unstemmed | Решение линейных систем с помощью декомпозиции |
| title_short | Решение линейных систем с помощью декомпозиции |
| title_sort | решение линейных систем с помощью декомпозиции |
| topic | Нові методи в системному аналізі, інформатиці та теорії прийняття рішень |
| topic_facet | Нові методи в системному аналізі, інформатиці та теорії прийняття рішень |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/13813 |
| work_keys_str_mv | AT zaicevda rešenielineinyhsistemspomoŝʹûdekompozicii AT zaicevda linearsystemsolvingwiththehelpofdecomposition AT zaicevda viríšennâlíníinihsistemzadopomogoûdekompozicíí |