Институт вычислительной математики и математической геофизики СОРАН

Всероссийская конференция по вычислительной математике КВМ-2009

23-25 июня 2009 г. Академгородок, Новосибирск, Россия

Тезисы докладов

Вычислительная алгебра

Локальные оценивающие процедуры для интервальных линейных систем уравнений

Шарый С.П.

Институт вычислительных технологий СО РАН (Новосибирск)

ЛОКАЛЬНЫЕ ОЦЕНИВАЮЩИЕ ПРОЦЕДУРЫ
ДЛЯ ИНТЕРВАЛЬНЫХ ЛИНЕЙНЫХ СИСТЕМ УРАВНЕНИЙ

С.П. Шарый
Институт вычислительных технологий СО РАН, г. Новосибирск

В работе рассматриваются интервальные системы линейных алгебраических уравнений (ИСЛАУ) вида

a₁₁ x₁ + a₁₂ x₂ + … + a_1n x_n = b₁,
a₂₁ x₁ + a₂₂ x₂ + … + a_2n x_n = b₂,
… … … … …
a_n1 x₁ + a_n2 x₂ + … + a_nn x_n = b_n

с интервальными коэффициентами a_ij и интервальными правыми частями b_i, i, j = 1, 2, …, n, или, кратко,

Ax = b,

где A = (a_ij) – интервальная n×n-матрица и b = (b_i) – интервальный n-вектор. Выписанные интервальные системы мы понимаем как семейства точечных линейных систем Ax = b той же структуры с матрицами A из A и векторами b из b.

Множеством решений интервальной линейной системы уравнений будем называть множество

Ξ(A,b) = { x є Rⁿ | (существует A є A) (существует b є b) ( Ax = b ) },

образованное всевозможными решениями точечных систем Ax = b c A из A и b из b (см., к примеру, [1,2,3,4]). Часто его называют также объединённым множеством решений, поскольку для интервальных уравнений существуют другие множества решений, более адекватные тем или иным конкретным практическим ситуациям.

Известно, что множество решений Ξ(A,b) является многогранным (полиэдральным) множеством, в общем случае невыпуклым, но его пересечение с каждым из ортантов пространства Rⁿ выпукло. Точное и полное описание множества решений практически невозможно в силу его огромной трудоёмкости, а с другой стороны и не нужно в большинстве реальных постановок задач. Чаще достаточно знать приближённое описание, или оценку множества решений более простыми множествами, имеющими меньшую конструктивную сложность. В нашей работе мы занимаемся его внешним интервальным оцениванием, стараясь найти (по-возможности, меньший) брус U в Rⁿ со сторонами, параллельными координатным осям, содержащий множество решений Ξ(A,b) интервальной системы уравнений Ax = b.

Локальными оценивающими процедурами для интервальных линейных систем алгебраических уравнений мы будем называть любые процедуры для локального оценивания множеств решений ИСЛАУ, т.е. не всего множества решений целиком, а лишь той его части, которая лежит в некотором заданном брусе. Более строго, интервальнозначное отображение LocSol(A,b,z) : IR^m×n × IRⁿ × IRⁿ → IRⁿ называется локальной оценивающей процедурой для интервальных систем линейных алгебраических уравнений, если для любых интервальных матриц A и любых интервальных векторов b, z, z' выполнены следующие условия:

LocSol (A,b,z) содержит пересечение множества решений Ξ(A, b) интервальной линейной системы Ax = b с брусом z,
LocSol (A,b,z) содержится в LocSol (A,b,z'), если z содержится в z'.

Зачем нужны локальные оценивающие процедуры?

С одной стороны, практика нередко предъявляет к решению задачи, в самой постановке которых присутствуют двусторонние ограничения на возможные значения неизвестных переменных, вытекающие, например, из физических, экономических и т.п. соображений. Это сразу же суживает область поиска решений, и естественно было бы попытаться учесть подобные ограничения с самого начала процесса их поиска.

С другой стороны, локальные оценивающие процедуры (особенно для ИСЛАУ) оказываются полезными как вспомогательное средство при решении более сложных задач, приводящих к необходимости измельчения области решений и отдельного исследования задачи на подобластях меньшего размера, где погрешности интеральных методов меньше и есть надежда на более успешное применение различных интервальных тестов. Такова, к примеру, ситуация с решением систем нелинейных уравнений.

В представляемой работе рассмотрены общие способы построения локальных оценивающих процедур на основе известных методов глобального решения ИСЛАУ, обсуждаются их применения и влияние на конструирование интервальных алгоритмов.

Литература

[1] Калмыков С.А., Шокин Ю.И., Юлдашев З.Х. Методы интервального анализа. – Новосибирск: Наука, 1986.

[2] Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. – Москва: Мир, 1987.

[3] Шарый С.П. Конечномерный интервальный анализ. – Электронная книга, доступная на http://www.nsc.ru/interval.

[4] Neumaier A. Interval methods for systems of equations. – Cambridge: Cambridge University Press, 1990.

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

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]