close

Вход

Забыли?

вход по аккаунту

?

Решение систем дифференциально-алгебраических уравнений последовательным исключением множителей Лагранжа.

код для вставкиСкачать
31
ИЗВЕСТИЯ ВолгГТУ
случаях, когда функция плотности распределения цифрового шума на изображении неизвестна и необходимо определить эту функцию, и
точность значений μ , σ не важна.
Заключение
В работе была рассмотрена задача определения наиболее подходящей для анализируемого изображения модели аддитивного цифрового
шума. Были рассмотрены основные модели аддитивного шума и их характеристики, а также
условия фото- и видеосъемки, для которых
приемлемо применять данные модели.
Был предложен и подробно описан новый
метод определения наиболее подходящей для
анализируемого изображения модели аддитивного цифрового шума. Предлагаемый метод
был сопоставлен с методом наименьших квадратов, в результате чего были выявлены его
достоинства и недостатки.
Основным преимуществом предлагаемого
метода является то, что он позволяет аналитически оценить степень соответствия шума на
анализируемом изображении моделям аддитивного шума и оценить его статистические характеристики. Недостатки – более низкая точность подсчета статистических характеристик.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Гонсалес, Р. С. Цифровая обработка изображений /
Р. С. Гонсалес, Р. Э. Вудс. – М.: Техносфера, 2006.
2. Фисенко, В. Т. Компьютерная обработка и распознавание изображений / В. Т. Фисенко, Т. Ю. Фисенко. –
СПб.: СпбГУ ИТМО, 2008.
3. Сойфер, В. А. Методы компьютерной обработки
изображений / В. А. Сойфер. – М.: Физматлит, 2003.
4. Бобровский, И. В. О связи характеристик частотных
сигналов с характеристиками формирующих кодовых последовательностей / И. В. Бобровский // Известия Волгоградского государственного технического университета :
межвуз. сб. науч. ст. № 6 (54) / ВолгГТУ. – Волгоград,
2009. – (Сер. Актуальные проблемы управления, вычислительной техники и информатики в технических системах. Вып. 6). – С. 5–7.
УДК 519.688
О. В. Шаповалов, В. В. Гетманский, А. Е. Андреев, А. С. Горобцов
РЕШЕНИЕ СИСТЕМ ДИФФЕРЕНЦИАЛЬНО-АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
ПОСЛЕДОВАТЕЛЬНЫМ ИСКЛЮЧЕНИЕМ МНОЖИТЕЛЕЙ ЛАГРАНЖА
Волгоградский государственный технический университет
E-mail: oshapovalov@mail.com, getman_w@rambler.ru, andan2005@yandex.ru, gorobtsov@avtlg.ru
Рассматривается метод решения дифференциально-алгебраических уравнений Эйлера, допускающий
замену решения системы линейных алгебраических уравнений сверхбольшой размерности на последовательное решение множества систем малой размерности. Данный метод позволяет ускорить расчет, сократить требуемый объем памяти и повысить точность решения.
Ключевые слова: уравнение Эйлера, уравнения связей, механическая система, множитель Лагранжа,
дифференциально-алгебраические уравнения, система линейных алгебраических уравнений, сверхбольшая
размерность.
O. V. Shapovalov, V. V. Getmanskiy, A. E. Andreev, A. S. Gorobtsov
SOLVING OF DIFFERENTIAL ALGEBRAIC EQUATION SYSTEM WITH SUCCESSIVE
ELIMINATION OF LAGRANGE MULTIPLIERS
Volgograd State Technical University
The method of the decision of differential algebraic equation of Euler, which allows the replacement of the decision of system of the linear algebraic equations of extra-large dimension by the serial decision of set of systems of
small dimension, is considered. The given method allows to accelerate calculation, to reduce the demanded memory
size and to raise accuracy of the decision.
Keywords: Euler's Equation, The Equations of Communications, Multiplier Lagrange, Differential Algebraic
Equation, System of the Linear Algebraic Equations, Extra-large Dimension.
Быстрое развитие современной компьютерной техники позволяет проводить все более
сложные исследования различных процессов и
объектов. Для комплексных динамических систем, описываемых системами дифференциально-алгебраических уравнений, в общем случае
найти решение аналитически невозможно.
Единственный метод исследования таких сис-
тем на сегодняшний день – это поиск численного решения дискретных математических моделей. Междисциплинарное моделирование
динамики сложных объектов совместно с протекающими в них процессами сопряжено с выходом на сверхбольшие размерности при представлении описывающих эту систему массивов
данных. Описывающие подобные системы мат-
32
ИЗВЕСТИЯ ВолгГТУ
рицы сильно разрежены, количество ненулевых
элементов в них составляет доли процента. Для
хранения таких матриц Чангом и Густавсоном
была предложена схема разреженного строчного формата (Compressed Sparse Row – CSR) [1],
которая предъявляет минимальные требования
к памяти и удобна при выполнении различных
операций линейной алгебры, необходимых при
решении СЛАУ.
Реализация хранения матриц в таком формате позволяет решить проблему большого
требуемого количества памяти, но затрудняет
работу с данными. К тому же нередко возникают ситуации, когда обработка упакованных
массивов требует распаковки или просто большого количества памяти, например, для факторизации матрицы при решении СЛАУ. Факторизация создает дополнительные накладные
расходы, если в процессе решения меняется
портрет матрицы. Наиболее эффективную реализацию факторизации матрицы содержит высокопроизводительная библиотека PARDISO
[2]. Проведенные исследования показали, что
она позволяет обрабатывать c достаточной точностью матрицы с не более чем 10 млн. ненулевых элементов (невязка составляет менее 1 %),
при этом требуется порядка 8 Гб оперативной
памяти. Увеличение размерности до 15 млн. ненулевых элементов дает погрешность 7 %, что
уже неприемлемо для большинства задач моделирования. Поскольку существует необходимость работы с большими массивами данных,
надо каким-либо образом оптимизировать процесс решения СЛАУ с целью уменьшения требуемого объема памяти и времени решения.
Одним из таких методов является замена одного решения СЛАУ сверхбольшой размерности
на решение нескольких СЛАУ меньшей размерности, основанное на знании структуры
портрета матрицы.
Решаемая матрица представляет собой
уравнения Эйлера для условного экстремума
функционала, включающего в себя функции
одной независимой переменной и их производные, в форме системы дифференциальноалгебраических уравнений [3, 4]:
⎧⎪Mx − DT λ = f ( x, x, t ) ,
⎨
Dx = h ( x, t ) .
⎪⎩
Здесь x – вектор переменных всей системы
размерности N; M – матрица при вторых производных размерности N × N; f (x, x, t ) – вектор
правых частей; D – матрица переменных коэф-
фициентов уравнений связей размерности
K × N (K – число связей); h(x, t ) – вектор правых частей уравнений связей; λ – вектор множителей Лагранжа.
Зная, что M – диагональная матрица, – рассмотрим случай цепной системы тел (рис. 1),
когда все тела последовательно жестко связаны
между собой и имеют единичную массу.
Р
Рис. 1. Цепная система тел со связями
В простейшем случае узлы будут обладать
одной степенью свободы, то есть могут перемещаться только вдоль основного вектора тела.
Данной ситуации будет соответствовать граф
(рис. 2), где точки также соответствуют узлам
тела, а λ – коэффициенты взаимодействия между узлами.
х1
х2
λ1
х3
Р
λ2
Рис. 2. Граф взаимодействия узлов в теле
Данному графу будет соответствовать следующая система дифференциально-алгебраических уравнений:
⎧ x1 + λ1 = 0,
⎪ x − λ + λ = 0,
1
2
⎪⎪ 1
⎨ x1 − λ 2 = P,
⎪ x − x = 0,
⎪ 1 2
⎪⎩ x2 − x3 = 0.
Та же система в матричной форме будет
иметь следующий вид:
0 0
1
0 ⎞ ⎛ x1 ⎞ ⎛ 0 ⎞
⎛1
⎜
⎟ ⎜ ⎟ ⎜ ⎟
1 0 −1 1 ⎟ ⎜ x2 ⎟ ⎜ 0 ⎟
⎜0
⎜0
0
1
0 −1 ⎟ ⋅ ⎜ x3 ⎟ = ⎜ 0 ⎟
⎜
⎟ ⎜ ⎟ ⎜ ⎟
0 0 0 ⎟ ⎜ λ1 ⎟ ⎜ 0 ⎟
⎜ 1 −1
⎜0
1 −1 0 0 ⎟⎠ ⎜⎝ λ 2 ⎟⎠ ⎜⎝ 0 ⎟⎠
⎝
Из графа видно, что каждый узел связан
максимум с двумя соседними, а крайние узлы –
только с одним телом. Если начать рассчитывать поведение модели с одного из крайних узлов, можно последовательно исключить все неизвестные системы. Таким образом, общее решение системы будет состоять из прямого хода,
где на каждом шаге решение будет выражаться
33
ИЗВЕСТИЯ ВолгГТУ
через одну переменной λ i , и обратного хода,
который начинается после того, как будет решена последняя СЛАУ прямого хода, решение
которого уже не будет зависеть ни от каких переменных. Во время обратного хода происходит последовательная постановка рассчитанных ранее значений; данный этап полностью
соответствует соответствующему этапу алгоритма Гаусса.
Для осуществления одного шага прямого
хода необходимо решить систему из двух уравнений:
⎧ xi − λ i −1 + λ i = 0,
⎨
⎩ xi −1 − x1 = 0.
Поскольку зависимость для переменных
xi −1 и λ i −1 установлена на предыдущем шаге
(для первого шага x1 = f ( λ1 ) = −λ1 ), то, подставляя выражение для xi −1 , получаем систему
из двух уравнений и трех неизвестных, которое
можно записать следующим образом:
⎛ x ⎞ ⎛ −λ ⎞
A ⋅⎜ i ⎟ = ⎜ i ⎟,
⎝ λ i −1 ⎠ ⎝ C ⎠
где A – матрица подсистемы; C – константа,
полученная сложением силы, приложенной к
данному узлу, и постоянной части решения из
предыдущего шага.
Пользуясь свойством линейности
⎛ xi ⎞
−1 ⎛ − λ i ⎞
−1 ⎛ 0 ⎞
−1 ⎛ 1 ⎞
⎜
⎟ = A ⋅⎜
⎟ = A ⋅ ⎜ ⎟ − λi ⋅ A ⋅ ⎜ ⎟ ,
⎝ C ⎠
⎝C ⎠
⎝0⎠
⎝ λ i −1 ⎠
каждый раз надо решать одну систему уравнений для двух правых частей. На последнем шаге прямого хода в системе не будет λ N и реше⎛ x ⎞
ние для ⎜ N ⎟ будет определено однозначно.
⎝ λ N −1 ⎠
Обратный ход представляет собой подстановку
и достаточно тривиален.
Был проведен ряд тестов для цепочек разной
длины; результаты тестов приведены в табл. 1.
Таблица 1
Расчет протяженного тела
Размерность
Погрешность, %
Время расчета, с
1,0E+05
0
0,09
1,0E+06
1,0E–04
0,89
1,0E+07
1,0E–02
8,9
1,0E+08
3,42
89,6
1,0E+09
12,73
894
Для сравнения была выбрана самая быстрая
на сегодняшний момент библиотека для решения СЛАУ для разреженных матриц Intel MKL
PARDISO. Для решения СЛАУ сверхбольшой
размерности ей требуется значительный объем
памяти, поэтому тесты проводились на вычислительном сервере кафедры «ЭВМ и системы»
Волгоградского государственного технического
университета, обладающем 16 Гб оперативной
памяти и процессором Intel Core i7 720. Данного объема памяти достаточно для решения системы размерностью 5 млн.
Таблица 2
Расчет цепной системы в MKL Pardiso
Размерность
Погрешность, %
Время расчета, с
1,0E+05
0
0,964
1,0E+06
1,0E–04
9,46
3,0E+06
0,3
29,27
5,0E+06
6,01
51,006
Предложенный метод расчета имеет более
высокую скорость расчета (по сравнению со
стандартными библиотеками), обладает более
высокой точностью и требует меньшего количества памяти. Данный метод может быть
обобщен на случай любой полносвязной структуры тела, если описывающий его граф не имеет колец (в таком случае определитель матрицы
будет равен нулю, и система не будет иметь
однозначного решения). В настоящий момент
реализован расчетный модуль для решения любой системы с одной степенью свободы; в ближайшее время планируется его обобщить на
случай с любым числом степеней свободы.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Писсанецки, С. Технология разреженных матриц :
пер. с англ. / С. Писсанецки. – М.: Мир, 1988. – 411 c.
2. Библиотека PARDISO [Электронный ресурс]. – Режим доступа : http://www.pardiso-project.org. – 2011.
3. Горобцов, А. С. The Methods of the Transform of
Multibody Systems with Redundant Constraints / А. С. Горобцов // EUROMECH Colloquium 495. Advanced in simulation of multibody system dynamics, 18–21 February 2008,
Брянск (Россия): book of Abstracts : тез. докл. / Брянский
гос. техн. ун-т [и др.]. – Брянск, 2008. – C. 36. – Англ.
4. Банах, Л. Я. Условия разбиения системы дифференциально-алгебраических уравнений на слабосвязанные
подсистемы / Л. Я. Банах, А. С. Горобцов, О. К. Чесноков //
Журнал вычислительной математики и математической
физики. – 2006. – № 12. – C. 2223–2227.
5. Андреев, А. Е. Система для расчета тепловых технологических процессов машиностроения / А. Е. Андреев,
Е. Г. Громов, М. В. Резников, О. В. Шаповалов // Известия
Волгоградского государственного технического университета : межвуз. сб. науч. ст. № 12(60) / ВолгГТУ. – Волгоград, 2009. – 128 с. (Сер. Актуальные проблемы управления, вычислительной техники и информатики в технических системах. Вып. 7).
1/--страниц
Пожаловаться на содержимое документа