Анализ компьютерных схем метода базисных матриц
Рассматриваются задачи решения прямоугольных СЛАУ и СЛАН с матрицами ограничений общего вида с помощью метода базисных матриц. Предлагается методика уточнения решения. Проведены вычислительные эксперименты, показывающие эффективность предложенных модификаций МБМ. Розглядаються задачі розв’язання пря...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2009 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84541 |
| 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. — С. 3-12. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860269819816837120 |
|---|---|
| author | Богаенко, В.А. Кудин, В.И. Скопецкий, В.В. |
| author_facet | Богаенко, В.А. Кудин, В.И. Скопецкий, В.В. |
| citation_txt | Анализ компьютерных схем метода базисных матриц / В.А. Богаенко, В.И. Кудин, В.В. Скопецкий // Компьютерная математика. — 2009. — № 2. — С. 3-12. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Рассматриваются задачи решения прямоугольных СЛАУ и СЛАН с матрицами ограничений общего вида с помощью метода базисных матриц. Предлагается методика уточнения решения. Проведены вычислительные эксперименты, показывающие эффективность предложенных модификаций МБМ.
Розглядаються задачі розв’язання прямокутних СЛАР і СЛАН з матрицями обмежень загального вигляду за допомогою методу базисних матриць. Пропонується методика уточнення розв’язку. Проведені обчислювальні експерименти, які показують ефективність запропонованих модифікацій МБМ.
Solution to general rectangular linear algebraic systems of equations and inequalities using basic matrix method is considered. Solution refinement method is proposed. Numerical experiments, which demonstrate the efficiency of the proposed BMM modifications are made.
|
| first_indexed | 2025-12-07T19:05:27Z |
| format | Article |
| fulltext |
Компьютерная математика. 2009, № 2 3
Ìàòåìàòè÷åñêîå
ìîäåëèðîâàíèå
Рассматриваются задачи реше-
ния прямоугольных СЛАУ и СЛАН
с матрицами ограничений общего
вида с помощью метода базисных
матриц. Предлагается методика
уточнения решения. Проведены
вычислительные эксперименты, по-
казывающие эффективность пред-
ложенных модификаций МБМ.
© В.А. Богаенко, В.И. Кудин,
В.В. Скопецкий, 2009
ÓÄÊ 519.852:519.876
Â.À. ÁÎÃÀÅÍÊÎ, Â.È. ÊÓÄÈÍ, Â.Â. ÑÊÎÏÅÖÊÈÉ
ÀÍÀËÈÇ ÊÎÌÏÜÞÒÅÐÍÛÕ ÑÕÅÌ
ÌÅÒÎÄÀ ÁÀÇÈÑÍÛÕ ÌÀÒÐÈÖ
Введение. Известно, что математический ап-
парат анализа линейных систем уравнений
(СЛАУ) и неравенств (СЛАН), является
основополагающим при проведении иссле-
дований более сложных нелинейных задач.
Разработаны десятки точных методов и сот-
ни итерационных методов решения СЛАУ.
В общем случае нахождение их решений
является одной из задач анализа линейной
системы [1, 2].
При моделировании многих процессов
движения жидкостей характерными пробле-
мами являются: неадекватность процесса и
математической модели, математической и
машинной модели [3]; некорректность зада-
чи; накопление ошибок округления, усечения
и других в ходе вычислений [3–5] при реали-
зации вычислительного метода и алгоритмов.
Разработаны различные подходы, направлен-
ные на “смягчение” эффекта недостоверно-
сти вычислений: проведение вычислений с
удвоенной точностью; включение процедур
нормализации модели; проведение эквива-
лентных преобразований исходной модели с
целью понижения обусловленности матрицы
ограничений; построение вариантов выбора
ведущего элемента (в методах типа Гаусса)
[4–6]; методы и алгоритмы (типа SVD) раз-
ложения исходной матрицы ограничений [6];
использование математического аппарата
интервального анализа [7]. Следует отме-
тить, что наличие таких проблем в объекте
исследования существенно понижают эф-
фективность процедур нахождения двусто-
ронних оценок границ компонент вектора
решения (например, построения на основе
В.А. БОГАЕНКО, В.И. КУДИН, В.В. СКОПЕЦКИЙ
Компьютерная математика. 2009, № 2 4
метода простой итерации сжимающихся отображений для локализации непод-
вижной точки). Одним из вариантов улучшения параметров решения, в таких
случаях, является уточнение найденного приближенного решения в конусе об-
щих решений соответствующей СЛАН.
В данной работе на типовых моделях плохо обусловленных матриц ограни-
чений СЛАУ, которые отражают (по структуре матрицы ограничений, обуслов-
ленности) особенности задач предметной области, построены методы и алго-
ритмы нахождения приближенного решения СЛАУ и на их основе, процедуры
уточнения ранее найденного решения.
На стадии исследования дискретных аналогов (СЛАУ) математических мо-
делей процессов, используется метод базисных матриц (МБМ) [8]. На основе
положений МБМ построено алгоритмическое и программное обеспечение для
проведения вычислительного эксперимента. Эксперимент проводился по не-
скольким направлениям:
– проверке эффективности МБМ и его алгоритмов нахождения решения, об-
ратной матрицы и величины невязок с использованием (так и без использова-
ния) процедуры выбора главного элемента и уточнения решения;
– определение на моделях заданной размерности точности обращения
матрицы и величины невязок при разных значениях числа обусловленности
матрицы ограничений и машинного нуля;
– исследование зависимости точности нахождения решения и обращения
матрицы от размерности модели, значения машинного нуля при фиксированном
числе обусловленности матрицы ограничений;
– нахождение временных характеристик МБМ на моделях разной размерности.
На основе формул связи элементов метода в соседних решениях предложе-
на итерационная процедура нахождения величины ранга матрицы ограничений
и решения СЛАУ. Установлено условие единственности решений СЛАУ. При
построении процедуры уточнения использована формула аналитического пред-
ставления общих решений СЛАН с разным типом ограничений (в случае невы-
рожденности матрицы ограничений).
Основные положения МБМ. Введем в рассмотрение СЛАУ вида
,Au C= (1)
где матрица А (со строками 1 2, , ... , ma a a , 1 2( , ,..., ), 1,j j j jma a a a j m= = ) –
квадратная матрица размерностью ( )m m× , в которой 1 2( , ,.., )T
mu u u u= ,
вектор ограничений 1 2( , ,...., )T
mC c c c= имеют размерность m.
Введем соответственно системе (1) изменением знака ″=″ на ″≤″ СЛАН вида
Au C≤ . (2)
АНАЛИЗ КОМПЬЮТЕРНЫХ СХЕМ МЕТОДА БАЗИСНЫХ МАТРИЦ
Компьютерная математика. 2009, № 2 5
При наличии целевой функции вида
1 maxf Bu= , (3)
модель приобретет вид задачи линейного программирования (1)–(3), в которой
1 2( , ,..., )mB b b b= – вектор целевой функции.
В основу МБМ положена идея базисной матрицы.
Определение 1. Матрицу бA , составленную из m линейно независимых
нормалей гиперплоскостей (ограничений (2)), будем называть искусственной
базисной, а решение 0u соответствующей ей системы уравнений 0
бA u C= ,
где
1 2
0 ( , ,..., )
m
T
i i iC c c c= , искусственным базисным.
Определение 2. Две базисных матрицы с отличной одной строкой будем
называть смежными.
Базисные матрицы в ходе итераций последовательно изменяются вводом-
выводом из нее нормалей ограничений задачи.
Введем в рассмотрение векторы 1 2, , ... ,i i ima a a – нормали ограничений
(в дальнейшем будем называть строками) , ,T
j j бa u c j J≤ ∈ где
1 2{ , , ... , }б mJ i i i= – индексы ограничений, нормали которых образовывают
строки базисной матрицы бA , lа – нормаль ограничения l la u c≤ ,
1 2( , ,..., )l l l lmα = α α α – вектор разложения вектора la по строкам базисной
матрицы бA .
Пусть rіe – элементы матрицы 1,бА
− обратной к бA , 0 01 02 0( , ,..., )T
mu u u u=
– базисное решение, 1 2( , ,..., )r r r rmα = α α α – вектор разложения нормали огра-
ничения r ra u c≤ по строкам базисной матрицы бA , 0 01 02 0( , ,..., )mα = α α α
вектор разложения нормали целевой функции (3) по строкам базисной матрицы
бA , 0r r ra u cΔ = − – невязка r-го ограничения в вершине.
Между коэффициентами разложения нормалей ограничений (1), целевой
функции (3) по строкам искусственной базисной матрицы, элементами обратных
матриц, базисными решениями, невязками ограничений (1) и значениями целе-
вой функции в двух смежных базисных матрицах при замене к-й строки в базис-
ной матрице бA строкой la имеют место связывающие соотношения [8].
Далее приведены основные стадии алгоритмической схемы нахождения
величины машинного ранга, базисной матрицы и решения системы (2) на основе
известных свойств тривиальной СЛАУ той же размерности:
– проводим симплексные итерации по замещению строк тривиальной
базисной матрицы с известными элементами метода строками ограничений
системы (4), согласно соотношениям [8];
– проверяем выполнение условий невырожденности на каждой итерации;
В.А. БОГАЕНКО, В.И. КУДИН, В.В. СКОПЕЦКИЙ
Компьютерная математика. 2009, № 2 6
– находим соответствующие элементы метода: вектора разложения по стро-
кам базисных матриц ограничений (2), обратную базисную матрицу, искусст-
венные базисные решения ( )
0
ru , где r – номер итерации;
– контролируем количество итераций r замещения строк вспомогательной
системы строками основной системы (1) для которых выполняются условия
невырожденности.
Если количество итераций, для которых ( ) 0i
lkα ≠ , равно m , находим един-
ственное решение из соотношения: 1 0 0
бA c u− ⋅ = . В противном случае при
выполнении условия r m< для СЛАУ (4) не выполняется условие единствен-
ности решения. Модель требует дальнейшего анализа разрешимости задачи.
Свойства общих решений СЛАН. На основе формул связи элементов
метода в смежных базисных матрицах можно получить аналитические пред-
ставления общих решений соответствующей системы линейных алгебраических
неравенств (СЛАН) с разным типом ограничений в случае невырожденности
матрицы ограничений. Также можно проанализировать влияние количествен-
ных изменений в элементах модели на величину ранга и свойства матрицы
ограничений.
Построение общего решения СЛАН (2) основывается на свойствах решения
соответствующей СЛАУ (1).
Теорема 1. Общее решение СЛАН (2) ранга m является конус UK с остри-
ем 0u – решением СЛАУ(1) и образующими 1( ) , 1,i б ie A i m−= = , который пред-
ставляется соотношением
0
1
/ , 0
m
U i i i
i
K u u u e
=
⎧ ⎫= = − λ λ >⎨ ⎬
⎩ ⎭
∑ . (4)
Доказательство приведено в [8].
Рассмотренная методология может быть применена для анализа соответст-
вующих моделей линейного программирования (МЛП) и для решения ряда дру-
гих задач. В частности, на основе формул связи элементов метода в смежных
базисных матрицах можно анализировать величину ранга матрицы ограничений,
а также уточнять найденное решение СЛАУ.
Далее рассмотрено применение МБМ для уточнения ранее найденного
решения.
Процедура уточнения приближенного решения. Известно, что одной из
причин неадекватности представления математической модели в виде машин-
ной, наряду с накопленными ошибками в ходе вычислений, является усечение
длины мантиссы при представлении чисел с плавающей точкой. Это приводит к
ненулевой невязке найденного решения. Возникает необходимость в уточнении
найденного решения на основе полученного ранее, например, с помощью МБМ.
АНАЛИЗ КОМПЬЮТЕРНЫХ СХЕМ МЕТОДА БАЗИСНЫХ МАТРИЦ
Компьютерная математика. 2009, № 2 7
Пусть в результате проведения основных итераций найдено решение:
1 20 01 02 0( , , ... , ), ( , , ... , )mmu u u u= Δ = Δ Δ Δ ,
1
бA
−
, где 0Au C− = Δ невязки
ограничений, причем , 0ii I∃ ∈ Δ ≠ .
Элементы решения можно интерпретировать, как нахождение точного
решения некоторой возмущенной СЛАУ б бA u c= с матрицей бA , которая обла-
дает свойством
1
б бA A E
−
× = , 0ббc A u= . Проведем преобразования строк
исходной матрицы (нормалей) ограничений
1
2
3
...
m
a
a
A a
a
⎛ ⎞
⎜ ⎟
⎜ ⎟
⎜ ⎟=
⎜ ⎟
⎜ ⎟
⎜ ⎟
⎝ ⎠
в
1
2
...
б
m
a
aA
a
⎛ ⎞
⎜ ⎟
⎜ ⎟
= ⎜ ⎟
⎜ ⎟
⎜ ⎟
⎝ ⎠
,
1
2
3
...
m
c
c
C c
c
⎛ ⎞
⎜ ⎟
⎜ ⎟
⎜ ⎟=
⎜ ⎟
⎜ ⎟
⎜ ⎟
⎝ ⎠
в
1
2
...
б
m
c
cC
c
⎛ ⎞
⎜ ⎟
⎜ ⎟
= ⎜ ⎟
⎜ ⎟
⎜ ⎟
⎝ ⎠
,
( 1 2( , ,...., )mΔ = Δ Δ Δ в 1 2( , ,...., ), 0, )m i i IΔ = Δ Δ Δ Δ < ∈ .
Если для i -го ограничения (2) выполнено условие 0iΔ > , то проведем пре-
образования , , ii ii i ia a c c= − = − Δ = −Δ , 1 2( , , ... , )T
б mC c c c= , в противопо-
ложном случае компоненты оставим без изменений.
Введем в рассмотрение вектор бu A= −Δ× и следующую задачу линейного
программирования
2 maxf uu= , (5)
б бA u C≤ , (6)
б бA u c≤ . (7)
Следует отметить, что оптимизационная задача разрешима, поскольку для
0 01 02 0( , , ... , ), 0,m iu u u u i I= Δ ≤ ∈ . Для нее справедливы следующее утвер-
ждение и теорема.
Утверждение 1. При невырожденности матрицы бA , общим решением (6)
является конус
0uK (образующие – столбцы матрицы 1
бA− , острие
0 01 02 0( , , ... , )mu u u u= – решения соответствующей СЛАУ, причем целевая
функция (5) достигает на острие конуса максимального значения.
Доказательство утверждения следует из теоремы 1. Для решения
0 01 02 0( , , ... , )mu u u u= задачи (5)–(6) выполняется условие
1 1
0 01 02 0( , , ... , ) 0m б б бuA A A− −α = α α α = − = −Δ × × = −Δ ≥ , которое является
условием оптимальности.
В.А. БОГАЕНКО, В.И. КУДИН, В.В. СКОПЕЦКИЙ
Компьютерная математика. 2009, № 2 8
Теорема 2. Если
00 uu K∈ (решение (7)), то оно оптимальное для (5)–(7)
и точное решение для СЛАУ (1).
Если
00 uu K∉ (не является решением (7)), то оптимальное решение задачи
(5)–(7) определяет промежуточное решение (1), которое является уточнением
решения 0u .
Методика вычислительного эксперимента. Для проведения тестирования
свойств метода, алгоритмов нахождения решения и обратной матрицы было
разработано алгоритмическое и программное обеспечение. Программные моду-
ли, реализующие рассмотренные алгоритмы, написаны на языке С++ и интегри-
рованы в систему САРПОК3D [9]. Использованная для тестирования аппаратная
платформа – процессор AMD Athlon64 c реальной тактовой частотой 1.8Ghz,
512 Mb оперативной памяти.
Для вычислительного эксперимента были выбраны модели систем линей-
ных алгебраических уравнений со 100 % заполнением матрицы ограничений.
Генерировались системы полного ранга с заполненной матрицей вида
1
( (1.0),..., (1.0)) , 0
( (1.0),..., (1.0)), 0,
i
i i
a rnd rnd i
A
a a rnd rnd i
n−
= =⎧
⎪= α⎨
= + >⎪⎩
где 2|| ||i ja a− < α .
Проводилось три типа тестов:
1) определялась невязка решения и точность обращения различными алго-
ритмами для матриц размерностью 256 х 256: с различными значениями α и
машинного нуля ε (без использования процедуры выбора главного элемента
и уточнения решения);
2) исследовалась зависимость невязки и быстродействия от размерности
задачи при 410−α = и 1210−ε = ;
3) исследовалась эффективность процедур уточнения решения и выбора
главного элемента при вычислении невязки решения и точности обращения
матрицы ограничений различными алгоритмами для матриц размерностью
256 х 256 с различными значениями α и машинного нуля ε .
Рассматривались два алгоритма метода базисных матриц:
– BM-I ( *
0C I= ) – алгоритм с единично-диагональной начальной базисной
матрицей;
– BM-R ( *
0 (0,1)C rand= ) – алгоритм с начальной базисной матрицей,
заполненной случайными числами.
АНАЛИЗ КОМПЬЮТЕРНЫХ СХЕМ МЕТОДА БАЗИСНЫХ МАТРИЦ
Компьютерная математика. 2009, № 2 9
Результаты вычислительного эксперимента. Из серии тестов 1) (табл. 1)
можно сделать следующие выводы:
– при 410−α < метод базисных матриц дает машинно-точное решение за
наименьшее время;
– при 410−α = метод базисных матриц имеет допустимые погрешности ре-
шения;
– при 410−α > не дает допустимые погрешности решения.
В среднем, для обоих алгоритмов, уменьшение коэффициента α на 2 по-
рядка приводит к снижению точности на 4 порядка.
Под машинно-точным решением для вычислений с плавающей запятой
двойной точности понимается решение, значение максимальной невязки которо-
го меньше 1210− . Под допустимыми погрешностями – значение невязки в диапа-
зоне от 1210− до 510− . Решения с невязкой > 510− считаются неверными.
Решения, получаемые алгоритмом BM-R, во всех тестах худшие по крите-
рию точности, чем получаемые алгоритмом BM-I. К тому же, быстродействие
первого алгоритма ниже. В дальнейшем под методом базисных матриц понима-
ется алгоритм BM-I.
Серия тестов 2) (табл. 2, 3.) показывает зависимость точности решения от
размерности матриц. Для матриц размерностью n>1000, при увеличении раз-
мерности на 1000 элементов точность падает на порядок для всех алгоритмов.
В табл. 4 приведены результаты по тестированию времени (в мс) работы алго-
ритмов МБМ для квадратных матриц ограничений.
ТАБЛИЦА 1. Невязки решения в зависимости от значения машинного нуля
Метод Максимальные невязки при машинных нулях
1.00E-08 1.00E-10 1.00E-12 1.00E-14
α=1.00E-02
BM-I 1.19749e-013 6.21815e-013 7.38705e-015 6.88064e-012
BM-R 1.7837e-010 1.05435e-008 3.01975e-010 1.2352e-009
α=1.00E-03
BM-I 1.7854e-011 5.50958e-010 1.30243e-010 3.03231e-011
BM-R 7.37512e-007 1.15638e-007 1.27955e-009 6.03063e-010
α=1.00E-04
BM-I 2465.61 0.000146138 2.58376e-008 3.11594e-010
BM-R 356603 5.43382e-007 1.74224e-005 2.11747e-006
α=1.00E-05
BM-I 169414 693968 0.000111571 3.56436e-006
BM-R 162248 0.000943858 0.023773 7.2919e-006
В.А. БОГАЕНКО, В.И. КУДИН, В.В. СКОПЕЦКИЙ
Компьютерная математика. 2009, № 2 10
ТАБЛИЦА 2. Невязки решения в зависимости от размерности задачи
α BM-I
N 1 1.00E-02 1.00E-04 1.00E-06
1000 7.59E-16 1.02E-12 1.37E-08 0.004137
2000 1.25E-15 5.93E-12 6E-07 5897
3000 1.24E-13 2.1E-09 0.013045 1.007973
4000 5.09E-11 1.55E-07
5000 1.27E-10 2.03E-07
ТАБЛИЦА 3. Невязки решения в зависимости от размерности задачи
α BM-R
N 1 1.00E-02 1.00E-04 1.00E-06
1000 7.37E-13 1.08E-09 8.73E-06 0.553564
2000 7.66E-12 2.25E-06 0.000283 4.76763
3000 4.85E-09 3.38E-05 0.131495 174.57
4000 2.79E-10 3.86E-06
5000 1.6E-08 0.000477
ТАБЛИЦА 4. Время работы алгоритмов
N BM-I BM-R
1000 5060 6780
1500 16720 22590
2000 40150 54430
2500 78680 106950
3000 137000 186840
Вычислительная сложность обоих тестированных алгоритмов – O(n3).
Серия тестов 2) состояла в проведении эксперимента по тестированию про-
цедуры уточнения решения СЛАУ, полученной при дискретизации методом
функций Грина следующей краевой задачи:
2 2 2
2 2 2 0, ( , , ) {0 1, 0 1, 0 1},H H H HD x y z x y z
x y z x
⎛ ⎞∂ ∂ ∂ ∂
+ + + = ∈Ω = ≤ ≤ ≤ ≤ ≤ ≤⎜ ⎟∂ ∂ ∂ ∂⎝ ⎠
,)(},10,10,0{,0,1 121
2
1
ГГГzyxГ
n
HH
Г
Г
−Ω=≤≤≤≤===
∂
∂
=
где )(ΩГ – граница области Ω , D – варьируемый коэффициент конвективной
диффузии.
АНАЛИЗ КОМПЬЮТЕРНЫХ СХЕМ МЕТОДА БАЗИСНЫХ МАТРИЦ
Компьютерная математика. 2009, № 2 11
Здесь при уменьшении параметра D обусловленность матрицы существенно
падает. Для этой задачи проводилось сравнение точности полученного решения
методом базисных матриц с (и без) использования процедуры уточнения реше-
ния. Полученные значения невязки решения приведены в табл. 5. Значения мак-
симального и минимального расстояния между строками матриц
|| ||i ja a− min , maxα α приведены в табл. 6. Допустимым решением считалось
решение с невязкой 410−ε < .
ТАБЛИЦА 5. Невязка решения СЛАУ
Алгоритм БМ (№ итерации)
D 1 2 3 4
1 1.26684e-006 4.56585e-010 5.29279e-010 5.29279e-010
0,1 0.00228699 1.50172e-007 1.82447e-007 1.82447e-007
0,05 0.00675934 7.17727e-006 5.82492e-006 8.8568e-006
0,025 1071.5 0.10663 0.105179 0.1155
0,015 17032.2 0.317572 0.42029 0.233579
ТАБЛИЦА 6. Характеристики матриц
D minα maxα
1 0.0013667 48.9676
0,1 3,8811 434950
0,05 21.8713 6.15539e+006
0,025 288.497 9.53489e+007
0,015 2040.47 7.06335e+008
Из полученных результатов можно сделать вывод, что для матриц полного
ранга достаточно проведения одной итерации уточнения, а все дальнейшие ите-
рации существенно не изменяют точность. Для матриц, ранг которых был опре-
делен как неполный, достаточно одной итерации уточнения после того как был
достигнут максимальный машинный ранг.
В дальнейшем предполагается проведения работы по улучшению свойств
процедуры уточнения найденного приближенного решения.
Особенности исследования СЛАУ на основе МБМ. МБМ является релак-
сационным методом, поскольку: на каждом шаге в процесс вычислений включа-
ется одно ограничение; нормали ограничений СЛАУ (1) последовательно заме-
щают нормали тривиальной СЛАУ; начальные обратная матрица и решение для
(1) являются заданными; найденное приближенное решение может быть улуч-
шено применением процедуры уточнения; структурно прямая и обратные смеж-
ные матрицы являются эквивалентными; объем вычислений по замещению
нормалями ограничений (1) постепенно возрастает, причем максимальное
количество шагов по нахождению ранга системы при её невырожденности огра-
ничивается числом m. Метод может находить число обусловленности как
промежуточных, так и конечной базисных матриц. Идеология симплексных
преобразований может быть применена для анализа вырожденности матрицы
ограничений, величины машинного ранга и решения СЛАУ (1) при возмущении
ее элементов.
В.А. БОГАЕНКО, В.И. КУДИН, В.В. СКОПЕЦКИЙ
Компьютерная математика. 2009, № 2 12
В.О. Богаєнко, В.І. Кудін, В.В. Скопецький
АНАЛІЗ КОМП’ЮТЕРНИХ СХЕМ МЕТОДУ БАЗИСНИХ МАТРИЦЬ
Розглядаються задачі розв’язання прямокутних СЛАР і СЛАН з матрицями обмежень загаль-
ного вигляду за допомогою методу базисних матриць. Пропонується методика уточнення
розв’язку. Проведені обчислювальні експерименти, які показують ефективність запропоно-
ваних модифікацій МБМ.
V.O. Bohaienko, V.I. Kudin, V.V. Skopetskyj
ANALYSIS OF COMPUTATIONAL SCHEMES FOR BASIC MATRIX METHOD
Solution to general rectangular linear algebraic systems of equations and inequalities using basic
matrix method is considered. Solution refinement method is proposed. Numerical experiments,
which demonstrate the efficiency of the proposed BMM modifications are made.
1. Самарский А.А., Гулин А.В. Численные методы / Гл. ред. физико-математической литера-
туры. – М.: Наука, 1989. – 432 с.
2. Воеводин В.В. Вычислительные основы линейной алгебры / Гл. ред. физико-математи-
ческой литературы. – М.: Наука. – 1977. – 303 с.
3. Химич А.М., Молчанов И.Н. и др. Численное программное обеспечение интеллектуально-
го мини-компьютера Инпарком. – Киев: Наук. думка, 2007. – 220 с.
4. Деммель Дж. Вычислительная линейная алгебра // Теория и приложение. – М.: Мир,
2001. – 430 с.
5. Уилкинсон Дж. Алгебраическая проблема собственных значений. – М.: Наука, 1970. – 564 с.
6. Беклемишев Д.В. Дополнительные главы линейной алгебры. – М.: Наука, 1983. – 335 с.
7. Кулиш У., Рац Д., Хаммер Р., Хокс М. Достоверные вычисления // Базовые численные
методы. – Москва-Ижевск, 2005. – 496 с.
8. Кудін В.І., Ляшко С.І., Яценко Ю.П., Хритоненко Н.В. Метод штучних базисних матриць
// Доп. НАН України. – 2007. – 9. – С. 30–34.
9. Скопецкий В.В., Стоян В.А., Благовещенская Т.Ю., Богаенко В.А. Программный ком-
плекс моделирования динамики систем с распределенными параметрами // Управляющие
системы и машины. – 2006. – № 2. – С. 32–41.
Получено 12.05.2009
Îá àâòîðàõ:
Богаенко Всеволод Александрович,
кандидат технических наук, научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины,
Кудин Владимир Иванович,
доктор технических наук, старший научный сотрудник
Киевского национального университета имени Тараса Шевченко,
Скопецкий Василий Васильевич,
доктор физико-математических наук,
член-корреспондент НАН Украины,
заведующий отделом Института кибернетики имени В.М. Глушкова НАН Украины.
|
| id | nasplib_isofts_kiev_ua-123456789-84541 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T19:05:27Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Богаенко, В.А. Кудин, В.И. Скопецкий, В.В. 2015-07-10T11:34:12Z 2015-07-10T11:34:12Z 2009 Анализ компьютерных схем метода базисных матриц / В.А. Богаенко, В.И. Кудин, В.В. Скопецкий // Компьютерная математика. — 2009. — № 2. — С. 3-12. — Бібліогр.: 9 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84541 519.852:519.876 Рассматриваются задачи решения прямоугольных СЛАУ и СЛАН с матрицами ограничений общего вида с помощью метода базисных матриц. Предлагается методика уточнения решения. Проведены вычислительные эксперименты, показывающие эффективность предложенных модификаций МБМ. Розглядаються задачі розв’язання прямокутних СЛАР і СЛАН з матрицями обмежень загального вигляду за допомогою методу базисних матриць. Пропонується методика уточнення розв’язку. Проведені обчислювальні експерименти, які показують ефективність запропонованих модифікацій МБМ. Solution to general rectangular linear algebraic systems of equations and inequalities using basic matrix method is considered. Solution refinement method is proposed. Numerical experiments, which demonstrate the efficiency of the proposed BMM modifications are made. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Математическое моделирование Анализ компьютерных схем метода базисных матриц Аналіз комп’ютерних схем методу базисних матриць Analysis of computational schemes for basic matrix method Article published earlier |
| spellingShingle | Анализ компьютерных схем метода базисных матриц Богаенко, В.А. Кудин, В.И. Скопецкий, В.В. Математическое моделирование |
| title | Анализ компьютерных схем метода базисных матриц |
| title_alt | Аналіз комп’ютерних схем методу базисних матриць Analysis of computational schemes for basic matrix method |
| title_full | Анализ компьютерных схем метода базисных матриц |
| title_fullStr | Анализ компьютерных схем метода базисных матриц |
| title_full_unstemmed | Анализ компьютерных схем метода базисных матриц |
| title_short | Анализ компьютерных схем метода базисных матриц |
| title_sort | анализ компьютерных схем метода базисных матриц |
| topic | Математическое моделирование |
| topic_facet | Математическое моделирование |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84541 |
| work_keys_str_mv | AT bogaenkova analizkompʹûternyhshemmetodabazisnyhmatric AT kudinvi analizkompʹûternyhshemmetodabazisnyhmatric AT skopeckiivv analizkompʹûternyhshemmetodabazisnyhmatric AT bogaenkova analízkompûternihshemmetodubazisnihmatricʹ AT kudinvi analízkompûternihshemmetodubazisnihmatricʹ AT skopeckiivv analízkompûternihshemmetodubazisnihmatricʹ AT bogaenkova analysisofcomputationalschemesforbasicmatrixmethod AT kudinvi analysisofcomputationalschemesforbasicmatrixmethod AT skopeckiivv analysisofcomputationalschemesforbasicmatrixmethod |