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

Автор(ы): Панюков А. В., Голодов В. А.

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

Выпуск: 43

Рубрика: Математическая теория управления

Год: 2013

Библиография: Панюков А. В., Голодов В. А. Программная реализация алгоритма решения системы линейных алгебраических уравнений с интервальной неопределенностью в исходных данных / Управление большими системами. Выпуск 43. М.: ИПУ РАН, 2013. С.78-94.

Дата опубликования: 31.05.2013

Ключевые слова: интервальная СЛАУ, псевдорешение интервальной системы, линейное программирование, точные вычисления

Аннотация: Рассмативается система линейных алгебаических уравнений Ax=b, с интервальными матрицами A и b. За множество решений принимается tol(A,b)={x:Ax2b}. усть ol(A,b(z))= {x:Ax=(1 z)b)}, z =inf{z: tol(A,b(z))6=;}. элементы множества tol(A,b(z )) названы псевдорешениями. Доказано существование псевдорешения для бых интервальных СЛАУ, предложен способ поиска псевдорешения как решения соответствущей задачи линейного прогаммиования. В силу вырожденности полученной задачи необходимо использовать вычисления с точностью, намного превышающей возможности стандартных типов данных языков прогаммирования. Симплекс-метод в сочетании с безошибочными дробнорациональными вычислениями дает решение задачи. Для реализации используется крупнозенистый параллелизм (технология MPI), безошибочные дробнорациональные вычисления реализованы на GPU (технология CUDA C).

Author(s): Panyukov A., Golodov V.

Article title: Software implementation of algorithm for solving a set of linear equations under interval uncertainty

Issue: 43

Year: 2013

Keywords: interval linear equation set, pseudo-solution of interval equation set, Linear programming, exact computations

Abstract: We consider a set of linear equations Ax=b with
interval matrices A, b. Solutions are items of tol(A,b)={x: A?x2
? b}. Let
tol(A,b(z))={x: Ax=(1+z)b)}, z

=
inf{z:
tol(A,b(z))6=
;
}
be.
Items of the set tol(A,b(z )) are referred to as pseudosolutions.
We prove existence of a pseudosolution for all sets of interval
algebraic linear equations, suggest a technique to search for the
pseudosolution via solving the corresponding linear programming
problem. The obtained problem is singular, thus computations demand
accuracy exceeding that of standard data types of programming
languages. Simplex method coupled with errorless rational-fractional
computations gives an efficient solution of the problem. Coarsegrained
parallelism for distributed computer systems with MPI gives
a software implementation tool. CUDA C software is suggested for
errorless rational-fractional calculations.

в формате PDF
Обсудить статью в Интернет-конференции по проблемам управления

Просмотров: 4394; загрузок: 1560, за месяц: 16.

Назад