Подход к решению систем линейных алгебраических уравнений с интервальной неопределенностью в исходных данных
Автор: Панюков Анатолий Васильевич, Голодов Валентин Александрович
Рубрика: Программирование
Статья в выпуске: 2 т.6, 2013 года.
Бесплатный доступ
Рассматривается система линейных алгебраических уравнений с интервальной матрицей коэффициентов и интервальной правой частью. Для данных систем вводится понятие псевдорешения. Доказано существование псевдорешения для любых интервальных систем линейных уравнений, предложен способ поиска псевдорешения с помощью решения соответствующей задачи линейного программирования. Вследствие вырожденности полученной задачи для ее решения необходимо использовать вычисления, обеспечивающие точность, намного превышающую возможности стандартных типов данных языков программирования. Симплекс-метод в сочетании с безошибочными дробно-рациональными вычислениями дает решение задачи. Для реализации используется крупнозернистый параллелизм в распределенных системах на основе MPI. Для реализации безошибочных дробно-рациональных вычислений на GPU используется CUDA C.
Интервальная система линейных уравнений, псевдорешение интервальной системы, линейное программирование, точные вычисления
Короткий адрес: https://sciup.org/147159204
IDR: 147159204
Список литературы Подход к решению систем линейных алгебраических уравнений с интервальной неопределенностью в исходных данных
- Standardized Notation in Interval Analysis/R.B. Kearfott, M.T. Nakao, A. Neumaie, S.M. Rump, S.P. Shary, P. van Hentenryck//Proc. XIII Baikal International School-seminar: Optimization methods and their applications, Irkutsk, Baikal, July 2-8, 2005. Vol. 4 Interval analysis. -Irkutsk: Institute of Energy Systems SB RAS, 2005. -P. 106-113.
- Neumaier, A. Interval Methods for Systems of Equations/A. Neumaier. -Cambridge: Cambridge University Press, 1990.
- Shary, S.P. Solving the Linear Interval Tolerance Problem/S.P. Shary//Mathematics and Computers in Simulation. -1996. -V. 39. -P. 53-85.
- Shary, S.P. A New Technique in Systems Analysis under Interval Uncertainty and Ambiguity/S.P. Shary//Reliable Computing. -2002. -V. 8, № 5. -P. 321-418.
- Шарый, С.П. Решение интервальной линейной задачи о допусках/С.П. Шарый//Автоматика и телемеханика. -2004. -№ 10. -С. 147-162.
- Lakeyev, A.V. Optimal Solution of Interval Linear Systems is Intractable (NP-Hard)/A.V. Lakeyev, V. Kreinovich//Interval Computations. -1993. -№ 1. -P. 6-14.
- Lakeyev, A.V. NP-Hard Classes of Linear Algebraic Systems with Uncertainties/A.V. Lakeyev, V. Kreinovich//Reliable Computing -1997. -№ 3. -P. 51-81.
- Rohn, J. Inner Solutions of Linear Interval Systems/J. Rohn//Interval Mathematics. -1985. -P. 157-158.
- Стецюк, П.И. Субградиентные методы с преобразованием пространства для минимизации овражных выпуклых функций/Стецюк П.И.//Современные проблемы прикладной математики и механики: теория, эксперимент и практика: конф., посвящ. 90-летию со дня рождения академика Н.Н. Яненко, Новосибирск. 30 мая -4 июня, 2011. -http://conf.nsc.ru/niknik-90/ru/reportview/37828 (дата обращения: 11 февраля 2013).
- Интервальный анализ и его приложения. -URL: http://www.nsc.ru/interval (дата обращения: 11 февраля 2013).
- Иванов, В.К. О линейных некорректных задачах/В.К. Иванов//ДАН СССР. -1962. -Т. 145, № 2. -С. 270-272.
- Тихонов, А.Н. Методы решения некорректных задач/А.Н. Тихонов, В.Я. Арсенин. -М.: Наука, 1979. -285 с.
- Панюков, А.В. Техника программной реализации алгоритма решения системы линейных алгебраических уравнений с интервальной неопределенностью в исходных данных/А.В. Панюков, В.А. Голодов//Параллельные вычисления и задачи управления PACO'2012. -Шестая междунар. конф., Москва, 24-26 окт. 2012 г.: тр. в 3 т. -М., 2012. -Т. 2. -С. 155-166.
- Панюков, А.В. Библиотека классов Exact Computation/Свидетельство о государственной регистрации программы для ЭВМ 2009612777 от 29 мая 2009 г./А.В. Панюков, М.И. Германенко, В.В. Горбик//Программы для ЭВМ, базы данных, топологии интегральных микросхем: офиц. бюл. Рос. агентства по патентам и товарным знакам. -2009. -№ 3. -С. 251.
- The GNU MP Bignum Library. -URL: http://gmplib.org/(дата обращения: 11 февраля 2013).
- Панюков, А.В. Применение массивно-параллельных вычислений для решения задач линейного программирования с абсолютной точностью/А.В. Панюков, В.В. Горбик//Автоматика и телемеханика. -2012. -№ 2. -C. 73-88.
- Схрейвер, А. Теория линейного и целочисленного программирования: в 2-х т./пер. с англ. -М.: Мир, 1991. -Т. 1. -360 с.
- Голодов, В.А. Распределенные символьные дробно-рациональные вычисления на процессорах x86 и x64/В.А. Голодов//Параллельные вычислительные технологии (ПаВТ'2012)[ Электронный ресурс]: тр. междунар. науч. конф. (Новосибирск, 26 марта -30 марта 2012 г.). -Челябинск: Издательский центр ЮУрГУ, 2012. -С. 719.
- Панюков, А.В. Параллельные реализации симплекс-метода для безошибочного решения задач линейного программирования/Панюков А.В., В.В. Горбик//Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. -2011. -№ 25 (242), вып. 9. -С. 107-118.
