Подход к решению систем линейных алгебраических уравнений с интервальной неопределенностью в исходных данных

Рассматривается система линейных алгебраических уравнений с интервальной матрицей коэффициентов и интервальной правой частью. Для данных систем вводится понятие псевдорешения. Доказано существование псевдорешения для любых интервальных систем линейных уравнений, предложен способ поиска псевдорешения с помощью решения соответствующей задачи линейного программирования. Вследствие вырожденности полученной задачи для ее решения необходимо использовать вычисления, обеспечивающие точность, намного превышающую возможности стандартных типов данных языков программирования. Симплекс-метод в сочетании с безошибочными дробно-рациональными вычислениями дает решение задачи. Для реализации используется крупнозернистый параллелизм в распределенных системах на основе MPI. Для реализации безошибочных дробно-рациональных вычислений на GPU используется CUDA C.

Ключевые слова

интервальная система линейных уравнений, псевдорешение интервальной системы, линейное программирование, точные вычисления.

Литература

1. 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.
2. Neumaier, A. Interval Methods for Systems of Equations / A. Neumaier. - Cambridge: Cambridge University Press, 1990.
3. Shary, S.P. Solving the Linear Interval Tolerance Problem / S.P. Shary // Mathematics and Computers in Simulation. - 1996. - V. 39. - P. 53-85.
4. 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.
5. Шарый, С.П. Решение интервальной линейной задачи о допусках / С.П. Шарый // Автоматика и телемеханика. - 2004. - № 10. - С. 147-162.
6. 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.
7. Lakeyev, A.V. NP-Hard Classes of Linear Algebraic Systems with Uncertainties / A.V. Lakeyev, V. Kreinovich // Reliable Computing - 1997. - № 3. - P. 51-81.
8. Rohn, J. Inner Solutions of Linear Interval Systems / J. Rohn // Interval Mathematics. - 1985. - P. 157-158.
9. Стецюк, П.И. Субградиентные методы с преобразованием пространства для минимизации овражных выпуклых функций / Стецюк П.И. // Современные проблемы прикладной математики и механики: теория, эксперимент и практика: конф., посвящ. 90-летию со дня рождения академика Н.Н. Яненко, Новосибирск. 30 мая - 4 июня, 2011. - http://conf.nsc.ru/niknik-90/ru/reportview/37828 (дата обращения: 11 февраля 2013).
10. Интервальный анализ и его приложения. - URL: http://www.nsc.ru/interval (дата обращения: 11 февраля 2013).
11. Иванов, В.К. О линейных некорректных задачах / В.К. Иванов // ДАН СССР. - 1962. - Т. 145, № 2. - С. 270-272.
12. Тихонов, А.Н. Методы решения некорректных задач / А.Н. Тихонов, В.Я. Арсенин. - М.: Наука, 1979. - 285 с.
13. Панюков, А.В. Техника программной реализации алгоритма решения системы линейных алгебраических уравнений с интервальной неопределенностью в исходных данных / А.В. Панюков, В.А. Голодов // "Параллельные вычисления и задачи управления", PACO'2012. - Шестая междунар. конф., Москва, 24-26 окт. 2012 г.: тр. в 3 т. - М., 2012. - Т. 2. - С. 155-166.
14. Панюков, А.В. Библиотека классов "Exact Computation" / Свидетельство о государственной регистрации программы для ЭВМ № 2009612777 от 29 мая 2009 г. / А.В. Панюков, М.И. Германенко, В.В. Горбик // Программы для ЭВМ, базы данных, топологии интегральных микросхем: офиц. бюл. Рос. агентства по патентам и товарным знакам. - 2009. - № 3. - С. 251.
15. The GNU MP Bignum Library. - URL: http://gmplib.org/ (дата обращения: 11 февраля 2013).
16. Панюков, А.В. Применение массивно-параллельных вычислений для решения задач линейного программирования с абсолютной точностью / А.В. Панюков, В.В. Горбик // Автоматика и телемеханика. - 2012. - №2. - C. 73-88.
17. Схрейвер, А. Теория линейного и целочисленного программирования: в 2-х т. / пер. с англ. - М.: Мир, 1991. - Т. 1. - 360 с.
18. Голодов, В.А. Распределенные символьные дробно-рациональные вычисления на процессорах x86 и x64 / В.А. Голодов // Параллельные вычислительные технологии (ПаВТ'2012)[ Электронный ресурс]: тр. междунар. науч. конф. (Новосибирск, 26 марта - 30 марта 2012 г.). - Челябинск: Издательский центр ЮУрГУ, 2012. - С. 719.
19. Панюков, А.В. Параллельные реализации симплекс-метода для безошибочного решения задач линейного программирования / Панюков А.В., В.В. Горбик // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - № 25 (242), вып. 9. - 2011. - С. 107-118.