Интервальные системы линейных алгебраических уравнений

Статья «ИСПОЛЬЗОВАНИЕ МЕТОДОВ ИНТЕРВАЛЬНОГО АНАЛИЗА ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ МЕТОДОМ КРАМЕРА»

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

«Актуальность создания школьных служб примирения/медиации в образовательных организациях»

Свидетельство и скидка на обучение каждому участнику

ИСПОЛЬЗОВАНИЕ МЕТОДОВ ИНТЕРВАЛЬНОГО АНАЛИЗА

ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ

УРАВНЕНИЙ МЕТОДОМ КРАМЕРА

МБОУ г. Абакана «Лицей»

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

Ключевые слова: вещественный интервал, интервальный анализ, обобщенная интервальная арифметика, метод Крамера, системы линейных алгебраических уравнений.

THE USE OF METHODS OF INTERVAL ANALYSIS FOR THE SOLUTION OF SYSTEMS OF LINEAR ALGEBRAIC EQUATIONS BY THE METHOD OF KRAMER

Abstract . This paper considers the solution of systems of linear algebraic equations by using methods of interval analysis. As the coefficients and variables of these systems use real intervals. An example of solving systems using generalized interval arithmetic.

Keywords : real interval, interval analysis, generalized interval arithmetic, the method of Cramer system of linear algebraic equations.

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

Основная идея интервального анализа состоит в замене арифметических операций и вещественных функций над вещественными числами интервальными операциями и функциями, преобразующими интервалы, содержащие эти числа. Интервальный анализ представляет собой относительно молодое и интенсивно развивающееся направление математики. Первоначально интервальные алгоритмы строились как непосредственные обобщения вещественных алгоритмов. Затем все чаще стали появляться специфические алгоритмы и дополнительные операции (такие, как пересечение). К настоящему времени имеются разработанные приемы интервальных вычислений и несколько пакетов прикладных программ и алгоритмических макроязыков, реализующих элементы интервального анализа на машинном уровне для нескольких типов ЭВМ.

Вещественным интервалом , или просто интервалом, называется замкнутое и ограниченное подмножество множества вещественных чисел такое, что . Интервал обозначается также через [1].

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

Рассмотрим метод Крамера для системы линейных уравнений Ax = b с n×n-матрицей A = ( a _ij ) и n-вектором правых частей b = (b _i ).

Метод Крамера предназначен для решения тех систем линейных алгебраических уравнений (СЛАУ), у которых определитель матрицы системы отличен от нуля. Решение системы уравнений методом Крамера проходит за три шага простого алгоритма:

Составить определитель матрицы системы (его называют также определителем системы), и убедиться, что он не равен нулю, т. е. Δ≠0.

Для каждой переменной x _i ( i =) необходимо составить определитель Δ x _i , полученный из определителя Δ заменой i -го столбца столбцом свободных членов заданной СЛАУ.

Найти значения неизвестных по формуле x _i = Δ x _i /Δ ( i =).

Пусть задана интервальная n × n -система линейных уравнений A x = b . Заменим в алгоритме все величины на интервальные, а арифметические операции – на операции интервальной арифметики. Получающийся при этом алгоритм, являющийся естественным интервальным расширением точечного метода Крамера, называется интервальным методом Крамера. На рисунке 1 представлен пример решения СЛАУ методом Крамера с использованием объектно-ориентированной системы программирования Delphi 10.

Рис. 1 – Решение СЛАУ c интервальными коэффициентами методом Крамера

В вещественной интервальной арифметике правило деления на нуль исключается. Чтобы освободиться от этого ограничения была определена обобщенная интервальная арифметика [1]. Для этого была расширена система вещественных чисел с помощью добавления к ней двух идеальных точек – положительной и отрицательной бесконечности:

Затем допустили, чтобы инфимумы и супремумы вещественных интервалов были идеальными точками. Тогда множество обобщенных вещественных интервалов имеет вид:

Иными словами, IR* представляет собой множество вещественных интервалов, дополненное такими интервалами, у которых нижняя и/или верхняя границы являются идеальными точками.

Для конечных интервалов при обобщенное интервальное деление определяется формулой (2):

Далее рассмотрим применение обобщенного интервального деления для решения систем линейных алгебраических уравнений (СЛАУ) интервальным методом Крамера [2]. Метод Крамера предназначен для решения тех СЛАУ, у которых определитель матрицы системы отличен от нуля. Обобщенное интервальное деление применяется здесь, когда главный определитель (интервал) содержит нуль.

Пример: Пусть имеется следующая СЛАУ [3] с интервальными коэффициентами: .

E ё главный определитель Δ равен [–12; 40], т. е. получили интервал, содержащий нуль. Следовательно, для решения данной СЛАУ необходимо использовать обобщенное деление интервальной арифметики.

Сначала вычислим остальные определители: Δ ₁ = [–102; –8], Δ ₂ = [–9; 39], Δ ₃ = [–34; 24]. Далее имеем:

Обобщенное арифметическое деление нередко сочетается с последующим пересечением результата с некоторым конечным интервалом. Результат пересечения может быть пустым множеством, конечным интервалом или объединением двух конечных интервалов. В этом смысле обобщенная арифметика служит средством порождения и оперирования бесконечными интервалами в ходе расчетов, в окончательный ответ которых входят только конечные интервалы.

Достоверные вычисления. Базовые численные методы: книга / У. Кулиш и др. Пер. с англ. – Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2005. – 496 с.

Кабаева Е. В. Решение системы линейных алгебраических уравнений с интервальными коэффициентами методом Крамера // Инновационные направления в науке, технике, образовании. Сборник научных трудов по материалам Международной научно-практической конференции 30 июня 2016 г. В 2-х частях. Часть 2. Смоленск. С. 86-88.

Кабаева Е. В. Применение обобщенной интервальной арифметики для решения систем линейных алгебраических уравнений // Фундаментальные и прикладные вопросы науки и образования. Сборник научных трудов по материалам Международной научно-практической конференции 30 сентября 2016 г. В 2-х частях. Часть 2. Смоленск. С. 29-30.

Интервальный подход к регуляризации неточно заданных систем линейных уравнений Голодов Валентин Александрович

480 руб. | 150 грн. | 7,5 долл. ‘, MOUSEOFF, FGCOLOR, ‘#FFFFCC’,BGCOLOR, ‘#393939’);» onMouseOut=»return nd();»> Диссертация — 480 руб., доставка 10 минут , круглосуточно, без выходных и праздников

Автореферат — бесплатно , доставка 10 минут , круглосуточно, без выходных и праздников

Голодов Валентин Александрович. Интервальный подход к регуляризации неточно заданных систем линейных уравнений: диссертация . кандидата физико-математических наук: 05.13.17 / Голодов Валентин Александрович;[Место защиты: Вычислительный центр им.академика А.А.Дородницына РАН].- Москва, 2014.- 107 с.

Содержание к диссертации

1 Интервальная неопределённость в математическом моделировании 15

1.1 Источники интервальной неопределенности 15

1.2 Некорректные задачи 18

1.3 Интервальные системы линейных алгебраических уравнений . 21

1.4 Линейная задача о допусках для ИСЛАУ 22

1.4.1 Исследование пустоты допускового множества 25

1.4.2 Коррекция правой части системы 28

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

1.5.1 Линейное уравнение межотраслевого баланса 29

1.5.2 Определение компонентов бинарных смесей методом Фи-рордта 30

1.5.3 Доказательные вычисления и интервалы 32

1.6 Основные выводы 35

2 Псевдорешение интервальной системы. Существование. Алгоритм поиска 36

2.1 Новизна предлагаемого подхода 36

2.2 Предпосылки рассматриваемого подхода 37

2.3 Понятие псевдорешения ИСЛАУ 37

2.4 Вопрос единственности псевдорешения 38

2.5 Наилучшее возможное псевдорешение 40

2.5.1 Поиск наилучшего псевдорешения 41

3 Программный комплекс вычисления псевдорешения интервальной системы 46

3.1 Параллельный алгоритм нахождения псевдорешения интервальной системы 46

3.2 Точные вычисления в существующих программных пакетах . 47

3.3 Описание разработанного программного комплекса поддержки дробно-рациональных вычислений 48

3.3.1 Особенности гетерогенных систем с GPU 51

3.3.2 Дробно-рациональные вычисления в гетерогенных системах 53

3.3.3 Параллельные алгоритмы для базовых арифметических операций. Реализация на GPU nVidia 56

3.4 Схема работы с программным комплексом для вычисления псевдорешения 67

3.4.1 Входные данные 67

3.4.2 Выходные данные 68

3.4.3 Запуск приложения и параметры 69

4 Численные эксперименты 71

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

4.1.1 Производительность сравнения 71

4.1.2 Производительность сложения (вычитания) 71

4.1.3 Производительность умножения 73

4.2 Примеры решения ИСЛАУ небольшой размерности 73

4.3 Линейное уравнение межотраслевого экономического баланса . 74

4.4 Определение компонентов бинарных и тернарных смесей методом Фирордта 78

4.5 Результаты нагрузочного тестирования 82

Основные обозначения 87

Список рисунков 88

Список таблиц 89

Интервальные системы линейных алгебраических уравнений

Работать с приближёнными числами, границами ошибок и интервалами значений приходится во многих случаях, ниже приводятся некоторые их них.

Представление чисел. При вычислениях, как правило, мы можем эффективно оперировать лишь объектами, которые имеют конечное описание (с конечной конструктивной сложностью). Например,

Если для дробно-рациональных чисел возможны точные машинные представления [13,16,32,52], то, например, вещественные числа точных аналогов в современных ЭВМ не имеют.

Тем самым уже в постановке вычислительной задачи допускается некоторая неизбежная ошибка представления из-за приближенного характера данных. Кроме того, теряется информация о характере ошибки приближения, какое именно приближение выбрано, с недостатком или с избытком.

Более правильно указывать границы этой ошибки, к примеру, путём уточнения, что все выписанные знаки верны и, таким образом, ошибка не превосходит половины единицы последнего разряда. Предпочтительный способ представления ошибки, состоит в том, чтобы дать наиболее узкие границы — нижнюю и верхнюю — для интересующей нас величины:

Частным случаем ошибок представления являются ошибки машинного представления чисел в формате с плавающей точкой ІЕЕЕ-754-1985/754-2008 [55]. Многие десятичные числа (к примеру, 0.1) не имеют точного конечного представления в формате с плавающей точкой одинарной и двойной точности [55], с которыми оперируют современные цифровые ЭВМ. При вводе подобных чисел в ЭВМ они неизбежно заменяются их некоторыми приближением.

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

Физические константы и результаты измерений. Чаще всего они известны неточно. К примеру, современные значения атомных весов некоторых химических элементов рекомендуется принимать интервальнозначными, например, для кислорода установлен интервал [15.99903; 159977] [68]. Для некоторых физических констант серьезные источники указывают стандартное (среднеквадратичное) отклонение, например, для гравитационной постоянной G.

Замечание. Здесь интервальная неопределённость носит существенный характер, поскольку заложена в саму математическую модель реального процесса, её учет позволяет создать более тонкий инструмент исследования.

Допуски. Допуски (техн.) — допускаемые отклонения (т.е. интервал, прим. автора) числовой характеристики какого-либо параметра, например, размеров деталей машин и механизмов, физико-химические свойства материалов) от его номинального расчетного значения в соответствии с заданным классом точности [42].

Наиболее широко понятие допуска распространено в машиностроении, где допуски устанавливают для обеспечения необходимого качества и взаимозаменяемости изделий.

Замечание. Интервалы в такой математической модели являются существенной ее частью, переход к точечной постановке приводит к искажению модели. Неопределённость в физических законах и явлениях. Ограниченные по величине неопределённости и неоднозначности естественно возникают при математическом моделировании многих механических, физических, химических и пр. явлений. Интересным примером является сила сухого трения, играющая важнейшую роль в технике. Хорошо известно, что её максимальная величина Ттах пропорциональна силе, с которой прижаты соприкасающиеся поверхности. Но, вообще говоря, если движение одной поверхности по другой не наступило, то абсолютная величина силы трения покоя может принимать любое значение из интервала [0,Ттаж]. Аналогично коэффициент силы трения покоя может задаваться некоторым интервалом [43].

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

Неопределённости в технических, экономических и пр. системах. Здесь имеются в виду величины, точные значения которых неизвестны или же могут изменяться. На протяжении нескольких столетий вплоть до второй половины XX века для их описания преимущественно использовалась теория вероятностей. Основоположником исследования ограниченных неопределённостей, для которых известны лишь границы изменения, является Л.В.Канторович, впервые сформулировавший идею их использования в работе [25] и наметивший основы математического аппарата для их обработки.

Показательный пример даёт понятие управления. Управление по смыслу подразумевает неоднозначность параметров объекта, которые можно выбирать из некоторого множества значений для достижения тех или иных желаемых целей управления. С другой стороны, даже цели управления и параметры функционирования объекта могут быть определены неточно. Эти соображения приводят к задаче так называемого робастного управления [49].

Замечание. Здесь интервальных характер входных данных и результата существенен, поэтому исследование имеет смысл проводить интервальными методами.

Замечание. Учет интервальной неопределённости позволяет провести численное исследование математической модели в виде доказательного эксперимента и повысить её качество.

Понятие псевдорешения ИСЛАУ

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

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

Применение проверенного временем и детально исследованного симплекс-метода, достаточно простого в реализации и доказавшего свою эффективность [53,61], упрощает кодирование и оптимизацию программного обеспечения воплощающего данную разработку. 2.2 Предпосылки рассматриваемого подхода

Во многих практических задачах система неравенств (2.1) оказывается плохо обусловленной или вообще несовместной. В этом случае по аналогии с псевдорешением СЛАУ М.М. Лаврентьева, работами [24,45] разумным представляется введение понятия псевдорешения интервальных систем линейных алгебраических уравнений.

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

Понятие псевдорешения ИСЛАУ Определение 2.3.1 (= 1.2.1). Псевдорешениями интервальной системы линейных уравнений Ах = b назовем точки допускового множества системы Ах = b(z) с расширенной правой частью b(z) = [b — zp,b + zq], где р, q — константные положительные векторы, определяющие характер расширения исходя из содержательного смысла задачи, z 0 — параметр, отвечающий за величину расширения.

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

Покажем влияние выбора параметров р, q, отвечающих за вид расширения интервалов правой части системы, на получаемое точечное решение. В случае на Рисунок [2.2] р» = q,h = 1, г = 1. ш, то есть расширение всех интервалов одинаковое и равно 1. ,m. x Система

Легко заметить, что решение уц = у % = 0, і = l,2. m является допустимым решением задачи (2.10) — (2.14). Таким образом, показано существование решений прямой (2.6) — (2.9), и двойственной (2.10) — (2.14)) задач линейного программирования. Из теоремы двойственности в линейном программировании следует существование у этих задач оптимальных решений [44].

Пусть х+\ х \ z оптимальное решение задачи (2.6) — (2.9). Из теоремы Рона следует, что х = х+ — х является допустимым решением системы Ах = b(z ). Из оптимальности z следует, что х является наилучшим возможным псевдорешением интервальной системы линейных уравнений Ах = Ь. Теорема доказана.

Таким образом, введенное понятие — псевдорешение интервальной системы линейных уравнений является вполне конструктивным и позволяет получать результаты решении любых интервальных систем в том числе несовместных, когда допусковое множество решений Etoi(A b) пусто. Покажем, что для точечных невырожденных систем наилучшее возможное псевдорешение интервальной системы совпадает с обычным решением системы.

Утверждение 2.5.1. Если точечная система Ах = Ъ невырождена, то ее решение и псевдорешение интервальной системы Ах = Ъ, где А = [А, А], Ъ = [Ь, Ъ] совпадают.

Сделав замену tj = хЛ—х t = 1. ,п получим обычную точечную систему At = 6, решение которой t существует и единственно. Возвращаясь обратно к переменным ж+,ж получим единственное псевдорешение интервальной системы Ах = Ь, с А = [A, A], b = [6,6]. Утверждение доказано.

В том случае когда Etoi(A,b(z )) неограниченно, см. критерий [1.4.3] является конечным пересечением гиперполос отличным от точки (ответом на задачу линейного программирования является грань или ребро симплекса), имеет смысл ставить дополнительную оптимизационную задачу, которая может обеспечить единственность выбора оптимального псевдорешения интервальной системы. Для решения совместной задачи о допусках имеет смысл применять методы интервального анализа, дающие оценку Sto/(A,6).

Полученная задача линейного программирования (2.6)-(2.9) и двойственная (2.10) — (2.14)) потенциально имеют высокую степень вырожденности, что будет приводить, при использовании приближенных вычислений, к зацикливанию симплекс-метода и погрешностям при применении других методов решения задачи линейного программирования.

Выходом является использование рациональных вычислений без округления [52,59], подобные разработки были предложены в совместной работе А.В. Панюкова, М.И. Германенко, В.В. Горбика библиотеке классов — «Exact Computation» 2009 года. В работах А.В. Панюкова и В.В. Горбиком доказывается что количество требуемых на каждой итерации бит памяти полиномиально зависит от числа бит, достаточных для представления элемента матрицы исходных данных. Симплекс допускает эффективное распараллеливание, при этом эффективность (т.е. отношение ускорения к числу процессоров) в асимптотике близка к 100% [36].

Описание разработанного программного комплекса поддержки дробно-рациональных вычислений

В данной главе построена полная технологическая цепочка реализации эффективного программного комплекса вычисления псевдорешения интервальной системы линейных уравнений. Описаны особенности построения эффективных приложений в гетерогенной вычислительной среде. Описана уникальная архитектура программного комплекса поддержки рациональных вычислений в гетерогенной вычислительной среде. Описаны и обоснованы разработанные параллельные алгоритмы базовых арифметических операций для устройств с массовым параллелизмом на примере GPU. Описана схема работы с программным комплексом вычисления псевдорешения интервальной системы, формат входного и выходного файлов, параметры запуска. Все описанные разработки реализованы в виде программных комплексов и зарегистрированы в Федеральной службе по интеллектуальной собственности в виде самодостаточных программных комплексов.

В следующей главе приводятся результаты тестирования программных комплексов поддержки рациональных вычислений и комплекса вычисления псевдорешения интервальной системы линейных уравнений. Приводятся результаты применения концепции псевдорешения интервальной системы в математическом моделировании. ГЛАВА 4

Вычислительный эксперимент проводился на компьютере с процессором Intel Core 17-950 3.06 ГГц, 6 Гб ОЗУ, GPU Nvidia 460(1гб GDDR5) GPU Nvidia 660ТІ, под управлением ОС Win 7 х64, в качестве компилятора был выбран 64-разрядный Visual C++ 2011.

Операция сравнения реализована с помощью алгоритма описанного в главе 3, алгоритм обеспечивает минимальное теоретически достижимое количество шагов для параллельного алгоритма результат которого зависит от всех входных данных, отчет о тестировании представлен в Таблица 4.1.

Производительность сложения случайных чисел, когда длина переноса в среднем не превосходит двух разрядов, на первый план выходит масштабируемость операции. В том случае когда длина переносов велика важным фактором является частота ядер графического процессора, которая отвечает за скорость последовательного исполнения инструкций. Отчет о тестировании представлен в Таблица 4.2.

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

Оптимальный размер блока зависит от типа задачи, а также архитектуры ускорителя. Операции сравнения, сложения-вычитания являются операциями, требующими интенсивной работы с памятью. Для ускорителей архитектуры FerminpH решении задач таких задач лучшим выбором является размер блока равный 512 или 1024 Таблица 4.3.

Операция умножения существенно зависит от объема быстрой (устанавливаемой непосредственно на чипе процессора) памяти ускорителя. Время выполнения умножения двух операндов в зависимости от их длины указаны в Таблица 4.5.

Рассмотрим насколько хорошо предложенный метод решения интервальной системы линейных алгебраических уравнений справляется с задачами разной степени сложности, нижеследующие примеры взяты из книги [49].

Рассмотрим простой пример. Экономика представлена двумя отраслями производства: промышленностью и сельским хозяйством. За отчетный период получены следующие данные о межотраслевых поставках Х и векторе объемов конечного использования Уо.

Данные о межотраслевых поставках за отчетный период, вектор объемов конечного использования Уо и конечного продукта Yn

Отрасли Отрасли потребители Y0 у1 п 2 1 62 42 102 152

Для численного эксперимента с реальными данными были использованы данные реального предприятия, представленные в диссертации на соискание ученой степени доктора физико-математических наук А.В. Келлер. Использованы данные модели построенной для предприятия МУП «Производственное объединение водоснабжения и водоотведения» по данным за 2007 год: А- матрица удельных прямых затрат, Ь — вектор конечного продукта или спроса. интервальная матрица удельных прямых затрат, b — интервальный вектор конечного продукта или спроса. Сначала рассматривалась точечная постановка задачи, когда А = А = А и Ъ = Ъ = Ъ, затем в матрицу коэффициентов была внесена интервальная неопределенность. Матрица удельных прямых затрат имеет размер 24 х 24 элемента, она доступна в указанном источнике, приведем лишь известный годовой выпуск продукции предшествующего периода Х0 и вектор конечного продукта или спроса Ъ (см. первый и второй столбцы таблицы [4.8]). Псевдорешение интервальной системы для точечной постановки(Л = А = А) системы и отклонение от выпуска прошлого года указаны в таблице (см. соответствующие столбцы таблицы [4.8]).

Данные экспериментов, а именно псевдорешение, соответствующее минимальному расширению правой части, а также характер расширения интервалов приведены в таблице [4.9], поскольку расширение интервалов в правой части в отрицательную часть действительной оси для данной математической модели не имеет смысла, то параметры р, q, отвечающие за вид расширения были выбраны как pi = 0.00000001, = 1,г = 1. т. Вектор псевдорешения xps, оптимальное значение параметра z = z , расширенные интервалы в правой части и интервал подстановки Ах для определения минимально необходимого расширения по каждому компоненту приведены в таблице [4.9]. Фрагмент файла ответа, выданного программным комплексом приведен в приложении [Г].

Производительность сравнения

Рассмотренные примеры задач математического моделирования показали жизнеспособность подхода как в случае неустойчивых задач, так и в случае сильно вырожденных систем.

Дальнейшая работа направлена на получение более эффективных реализаций программных комплексов за счет оптимизации параллельных версии программ, расширение списка поддерживаемых библиотекой «Exact Computation 2.0» архитектур, реализацию графического пользовательского интерфейса и разработку проблемно-ориентированных программных решений применяющих разработанных подход к регуляризации неточно заданных систем к задачам математического моделирования из различных прикладных областей. Заключение

Учет интервальной неопределённости повышает адекватность математических моделей. Подход позволяет единообразно решать как задачи с изначально интервальным характером данных, так и те практические задачи, в которых правая часть Ь и элементы матрицы А, т. е. коэффициенты системы Ах = Ь, известны приближенно. В этих случаях вместо системы мы имеем дело с некоторой другой системой Ах = Ь такой, что \А — А\\ h \\b — b\\ 5, где смысл норм обычно определяется характером задачи [45].

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

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

Предложен стратегический путь для эффективной реализации подхода, а именно использование ресурса параллелизма современных гетерогенных вычислительных систем.

В работе построена полная технологическая цепочка реализации эффективного программного комплекса вычисления псевдорешения интервальной системы линейных уравнений. Описаны особенности построения эффективных приложений в гетерогенной вычислительной среде. Описана уникальная архитектура разработанного программного комплекса поддержки рациональных вычислений в гетерогенной вычислительной среде. Описаны и обоснованы разработанные параллельные алгоритмы базовых арифметических операций для устройств с массовым параллелизмом на примере GPU. Описана схема работы с программным комплексом вычисления псевдорешения интервальной системы, формат входного и выходного файлов, параметры запуска.

Проведенные вычислительные эксперименты показывают, что комплекс поддержки дробно-рациональных вычислений позволяет получить в гетеро 85 генных вычислительных средах существенный прирост производительности приложений для больших чисел. В случае вычислений на процессорах архитектуры х_86 программный комплекс вычисления псевдорешения интервальной системы позволяет получать прирост производительности за счет использования крупнозернистого параллелизма.

Классы overlong и rational обеспечивают необходимую точность вычислений и, тем самым, позволяют избежать зацикливания симплекс-метода в случае сильной вырожденности задачи линейного программирования, что важно для разработанного подхода к регуляризации неточно заданных систем.

Рассмотрены примеры задач математического моделирования: межотраслевая модель Леонтьева и анализ смеси веществ методом Фирордта. Предлагаемый в работе подход показал свою жизнеспособность. Метод погружения неточно заданных систем в интервальные СЛАУ позволил получить устойчивые к колебаниям входных данных решения. Решения хорошо согласуются с известными методами.

Все описанные разработки реализованы в виде программных комплексов и зарегистрированы в Федеральной службе по интеллектуальной собственности в виде самодостаточных программных комплексов.

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

Предложен новый подход к регуляризации СЛАУ за счет погружения в ИСЛАУ и перехода к поиску точки из допускового множества решений ИСЛАУ.

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

Разработан и протестирован масштабируемый параллельный алгоритм для нахождения псевдорешения интервальной системы линейных алгебраических уравнений в распределённых гетерогенных вычислительных системах с применением точных дробно-рациональных типов данных. Эффективность реализованного численного метода достигнута за счет применения технологии крупно-зернистого параллелизма и библиотеки MPI. Разработан и протестирован комплекс программ для безошибочных дробно-рациональных вычислений. Выполнена реализация последовательных алгоритмов для базовых арифметических операций и их параллельных версий для распределённых вычислительных систем с GPU. Применение технологии GPGPU позволяет на порядок увеличить эффективность данного ПО по сравнению с последовательной версией. Разработан и реализован программный комплекс для численного решения задач математического моделирования.

Дальнейшая работа направлена на получение более эффективных реализаций программных комплексов за счет оптимизации параллельных версии программ, расширение списка поддерживаемых библиотекой «Exact Computation 2.0» архитектур, реализацию графического пользовательского интерфейса и разработку проблемно-ориентированных программных решений применяющих разработанных подход к регуляризации неточно заданных систем к задачам математического моделирования из различных прикладных областей.

Некоторые вопросы решения интервальных систем линейных алгебраических уравнений тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ С,’/! УНИВЕРСИТЕТ

На правах рукописи

ЛЯШКО Марина Александровна

НЕКОТОРЫЕ ВОПРОСЫ РЕШЕНИЯ ИНТЕРВАЛЬНЫХ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Работа выполнена на кафедре математической физики и вычислительной математики Саратовского государственного университета имени Н.Г.Чернышевского.

Научный руководитель: кандидат физико-математических

ЗЮЗИН Владимир Сергеевич

Официальные оппоненты: доктор технических наук,

Заслуженный деятель науки и техники РФ, профессор МЕНЬШИКОВ Григорий Григорьевич,

кандидат физико-математических наук, доцент

НЕСТЕРОВ Вячеслав Михайлович

Ведущая организация: Институт Проблем Точной

Механики и Управления РАН

Защита диссертации состоится » />£/10 1998 г. в » » часов на заседании диссертационного совета К 063.57.16 по защитам диссертаций на соискание ученой степени кандидата физико-метематических наук в Санкт-Петербургском государственном университете по адресу: 199004, Санкт-Петербург, 10-я линия В.О., д.ЗЗ, ауд.88.

С диссертацией можно ознакомиться в научной библиотеке им.М.Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская набережная, 7/9.

Автореферат разослан » 1998 г.

диссертационного совета К 063.57.16 В.Ф.Горьковой

Общая характеристика работы

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

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

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

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

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

ния. Доказательство проведено двумя способами, один из которых использует развиваемый в диссертации подход перенесения итерационного процесса из пространства IIR» в хорошо изученное пространство Ш,2″.

Апробация работы. Результаты диссертации докладывались на Межвузовской конференции молодых ученых «Развитие фундаментальных и прикладных исследований» (Ленинград, 1985 год), на Всесоюзном совещании по интервальной математике (ВЦ СО АН СССР, Красноярск, 1987 год), в Ленинградском отделении математического института им. В. А. Стеклова на семинаре Ю.В. Ма-тиясевича (1987 год), на коференции «Актуальные проблемы прикладной математики» (Саратов, 1991 год), на Межреспубликанском совещании по интервальной математике (Новосибирск, 1996 год).

Структура и объем работы. Структурно работа состоит из введения, указателя основных обозначений, двух глав, списка литературы из 68 наименований и приложения. Объем диссертации — 161 страница, 22 страницы из них — приложение.

Публикации. По теме диссертации опубликовано 10 работ [1]-[10].

Краткое содержание работы

Во введении формулируются цели исследования, обсуждаются известные методы и результаты, необходимые в дальнейшем изложении. Там же приводится краткая аннотация глав работы.

В указателе основных обозначений приводится перечень используемых понятий и вводятся соглашения относительно обозначений. Интервалы и интервальные величины обозначаются жирным шрифтом: А, В. ,х,у. а для других объектов будем использовать обозначения: .

IIR — множество вещественных интервалов;

х,х — левый и правый конец интервала х соответственно, так что х := [х,х], х,х е Н, х 0, i,j — 1,п) и неразложимой матрицей |А|.

В §1.2 предложен подход к нахождению точного значения ат, основанный на изучении итерационного процесса в достаточно малой окрестности решения х% который может быть распространен на другие интервальные итерационные методы, что и продемонстрировано в дальнейшем в §1.8 на примере метода Гаусса-Зейделя (короткошагового метода) ив §1.9 на примере метода релаксации для короткошагового случая. Данный подход позволяет проводить сравнение факторов сходимости различных методов.

Пусть а,х 6 ГО,. В случае, когда min (ах, ах,ах, ах) — ах и max (ах, ах, ах, ах) = ах достигаются лишь для одного из четырех зпачений ах,ах,ах,ах, или в случае, когда только один из концов интервала а равен нулю и ни один из концов интервала х не равен нулю, или в случае, когда оба конца интервала а равны нулю, произведение интервалов ах можно представить однозначно в виде:

\ аху \ Я21 а22 J \x j Элементы 2х2-матрицы а^ £ <0, а, ä>, i,j = 1,2, причем один из элеметов каждой строки обязательно равен нулю.

и компонент вектора х= однозначно представляются в виде

(6) при i,j = 1,п. Далее, пусть в уравнении (5) х* £ W(A). От интервальной га-матрицы А и интервальных re-векторов Ь и х* с помощью отображения

er: HR» —► Ш,2″, Ж=а(х)-(х1,х1,х2,х2. хп,х„)т (7)

можно перейти к точечным 2пх2п-матрице А(х*) и 2п-векторам Ь=ст(Ь) и х*=а(х*). Коэффициенты ay, i,j — 1,2п, матрицы Л(х*) определяются с помощью равенства

Поэтому А(х*) удовлетворяет соотношению Х*—А(Х.*)’Х* + b (что по существу является другой записью равенства (5)).

Заметим, что при отображении а компоненты х* и Ъ, стоящие на т-ом и к-ом месте (1 0, г,= 1 ,п, их* 6 Т7(А). Тогда ат = р<В) для некоторой В £ В<А).

Обозначим теперь через В(А) множество всех матриц из К»*» таких, что ровно к = «+»^»> min

Теорема 1.3.2 Пусть матрица А в сходящемся полношаговом методе (3) такова, что Жу G В(А), А P(F),

где F G 1ГХ», Д- = mm<|ay|, |äy|>, i,j = TJi.

В §1.5 доказываются легко вычисляемые оценки снизу ат для знакопостоянных матриц А в методе (3): для неотрицательных матриц выполняется оценка

a-r > max а,-,- — max la.,1, — 1 тах ■ а„- и ат > Ч/^ • а1|П • а2 ^ ■ а2>„_1 •. • а„д • а„д.

1 />(Л(Ь)). Если к тому же х* £ И^(А), то аТ = р(Л(Ь)).

Заметим, что х* £ почти всегда, а если Ь € И^А) и П(Ь)

существует, то х* = с(х*) может быть найдено как алгебраическое решение точечной системы х = Л(Ь)х 4- + Ъ, к = 0,1. (10)

где А = Ь + Ю + и, Ъ — строго нижняя треугольная матрица, Ю -диагональная матрица, и — строго верхняя треугольная матрица. Асимптотический фактор сходимости этого метода обозначается а$ и оценивается сверху следующим образом1:

а5 12, -D21, U21 — неположительные матрицы.

Утверждение 1.8.1 Если в сходящемся короткошаговом методе (10) х* € ЩА), moas = p ((/ — Ь)-\0 + U)).

Пусть L,D,U 6 Ж»*», и L — строго нижняя треугольная матрица, такая что /у = min |а,, |>, i > j, i,j = 1 ,п, D — диагональная матрица, такая что dy = min <1, jstfj-1>, i — j, i, j = 1, n, U — строго верхняя треугольная матрица, такая что йу = min <|a;j|, |ау |>, i р ((/ — Ь)

Далее в этом же параграфе доказываются аналоги оценок из §1.5 и результатов из §1.6. Предложенная методика позволяет сравнивать скорости сходимости различных методов.

Теорема 1.8.5 Если для системы (2) /э(]А|) 0 — релаксационный параметр, а матрицы Ь, и — те же, что и в методе (10). Известно1, что необходимое и достаточное условие сходимости метода (12) таково:

р ((/ — ИЧГ1 (|1 — ш\1++ |и|))) (|А|)), то метод (12) тоже сходится к неподвижной точке х*, для которой

Если 0 1, то х* С х*.

Для асимптотического фактора сходимости ая релаксационного метода (12) получены верхняя и нижняя оценки: при условии (13)

^ р((1- «¿Г1 ((1 — ш)1 + ыф + й))) , а также доказано утверждение о его точном значении: Утверждение 1.9.1 Если в сходящемся методе (12) х* 6 то

Здесь L,D,U, L,D,Ü — матрицы, описанные в §1.8.

Во второй главе рассматривается вопрос совпадения интервальной оболочки объединенного множества решений и неподвижной точки сжимающего интервального отображения.

В §2.1 приводятся необходимые факты, формулируется основная задача главы, а также освещаются известные результаты.

Рассмотрим интервальную систему линейных алгебраических уравнений:

Аз; = ь, Аетпхл, belli» (15)

Одной из важных задач, связанных с системой (15), является задача нахождения объединенного множества решений (ОМР):

Интервальной оболочкой этого множества называется минимальный интервальный вектор Xя = (xf,хя. ,хя)Т, содержащий Е:

xf = [xf,хя] , xf = min , xf = max ,

Нахождение Xя требует решения порядка 2″—2″2 точечных систем, а в случаях системы (15) с вещественной матрицей или монотонной интервальной матрицей А, вектор Xя может быть найден как решение двух неинтервальных систем или как результат умножения вещественной^ обратной матрицы на интервальный вектор 6 7. В общем случае при обращении только одной вещественной матрицы 8 не гарантируется получение минимального по ширине ограничения множества S.

Если систему (15) можно привести к равносильной (в смысле совпадения объединенных множеств решений Е i Б’ соответственно) системе

6Beeck Н. Zur scharfen Außenabschätzung der Lösungsmenge bei linearen Intervallgleichungssystemen. ZAMM 54 (1974), 208-209.

7Beeck H. Bemerkungen zu Komponentenweisen Abschätzungen bei linearen Gleichungssystemen mit fehlerhaften Daten. ZAMM 57 (1977), 265-266.’

8Rohn J. Cheap and tight bounds: the recent result by E. Hansen can be made more efficient. Interval Computations 4 (1993), 13-21.

так, чтобы отображение Mi+r было сжимающим, то неподвижная точка х* этого отображения (алгебраическое решение уравнения (16) 9) всегда содержит интервальную оболочку Xя: Xя С х*. Таким образом, множество Е может быть ограничено каким-либо итерационным методом, а основная задача, рассматривающаяся во второй главе состоит в следующем:

при каких условиях алгебраическое решение х* системы х — Мж + г совпадает с интервальной оболочкой Xй объединенного множества решений равносильной системы А.х = Ъ?

Совпадение Xя и х* доказано1 для интервальных систем (16) с неотрицательной матрицей М. Достаточные условия совпадения Xя и х* доказаны Г.Майером5 для итерационных методов, основывающихся на подходящем М-расщеплении А = М — N М-матрицы А системы (15).

Тякжб в §2.1 для одного из способов приведения системы (15) к равносильному виду (16) доказывается выполнение неравенства />(|М|) ■ Л2″, заданного по формуле (9). Если матрица М(х*) путем перестановок рядов i ui + n (i £ <1,2. ,п>) приводится к блочно диагональному виду с пхп-блоками, то Xя совпадает с х*.

Далее показано, что возможность приведения матрицы М(х*) к блочно диагональному виду с блоками одинаковой размерности не является в общем случае необходимым условием совпадениия Xя

В приложении приведены алгоритмы и программы, осуществляющие для некоторых теорем главы 1 проверку их условий.

Автор выражает глубокую признательность В.С.Зюзину, Т.Э.Каминскому, Л.В.Куприяновой, Г.Г.Меньшикову, В.М.Нестерову и С.П.Шарому.

Список работ по теме диссертации

[1] Кузнецова М.А. К вопросу об итерационном ограничении множества решений интервальной системы линейных алгебраических уравнений. JL, 1987. Деп. в ВИНИТИ, №1389-В87, 14с.

[2] Кузнецова М.А. Об одной частичной системе интервальной арифметики. Л., 1987. Деп. в ВИНИТИ, №2182-В87, 6с.

[3] Кузнецова М.А. Достаточное условие совпадения интервальной оболочки множества решений интервальной системы линейных алгебраических уравнений с ее итерационным решением. Л., 1987. Деп. в ВИНИТИ, №7836-В87, 8с.

[4] Кузнецова М.А. Нахождение интервальной оболочки множества решений интервальной системы линейных алгебраических уравнений (ИСЛАУ) итерационными методами. Препринт ВЦ СО АН СССР №, Красноярск, 1987.

[5] Ляшко М.А. Одна итерационная схема решения ИСЛАУ. Материалы Всесоюзной конференции «Актуальные проблемы прикладной математики». Саратов, 1991.

[6] Ляшко М.А. О совпадении интервальной оболочки объединенного множества решений ИСЛАУ с итерационным решением. Балашов, 1996. Деп. в ВИНИТИ, №429-В96, 16с.

[7] Ляшко М.А. О скорости сходимости полношагового итерационного метода для интервальных СЛАУ. Балашов, 1996. Деп. в ВИНИТИ, №430-В96, 22с.

[8] Lyashko М.А. On the speed of convergence of the total step iterative method for a class of interval linear algebraic systems. Reliable Computing 2 (4) 1996, 351-356.

[9] Ляшко М.А. Один способ нахождения асимптотического фактора сходимости полношагового итерационного метода для интервальных СЛАУ. Вычислительные технологии, 2, №1, 1997, 37-44.

[10] Ляшко М.А. Скорость сходимости интервальных итерационных методов. Балашов, 1997. Деп. в ВИНИТИ, №2692