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



1. Введение

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

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

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

В значительной мере это вопросы риторические, так как в течение последних десятилетий накоплено достаточно много примеров плодотворного применения интервальных методов к задачам, которые до сих пор никак иначе не решались или решались неудовлетворительно. Таковы, в частности, задачи доказательной глобальной оптимизации и доказательного глобального решения уравнений и систем уравнений [1–5]. Кроме того, интервальный анализ предоставляет нам новый язык для описания задач с ограниченными неопределенностями и неоднозначностями в данных [6], язык удобный и весьма выразительный, который существенно обогащает арсенал методов математического моделирования окружающей нас действительности. В частности, система линейных алгебраических уравнений (СЛАУ) используется при математическом моделировании объектов различной природы: физических, химических и социально-экономических процессов, процессов управления.

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

, (1)

где — величина силы или момента, действующих на конструкцию,

— единичное перемещение по направлению k , — величина перемещения в направлении k -й связи. При анализе электрических цепей постоянного тока используют систему уравнений вида [8]:

, (2)

где R _kj — сопротивление смежных ветвей между k -м и j -м контурами, E _k — контурная ЭДС k -го контура, I _kk – контурный ток в k -м контуре. В общем виде эти системы представим так:

, (3)

или в матричном виде:

(4)

Системы уравнения (1), (2) и (3), (4) имеют важную особенность. Все входящие в эти системы параметры и неизвестные величины имеют реальный физический смысл и, в силу этого, их значения могут быть получены с некоторой погрешностью. В зависимости от конкретного физического смысла задачи эти погрешности могут быть заранее известными, а в некоторых случаях их определение невозможно. Таким образом, можно утверждать, что все эти величины известны с некоторой неустранимой неопределённостью. В соответствии с [9] различают неопределенность типа А, которую оценивают статистическими методами и неопределенность типа b , которую оценивают нестатистическими методами. При этом предлагается два метода оценивания неопределенностей А и b . Для неопределенности типа А это использование известных статистических оценок среднеарифметического значения и среднеквадратического отклонения, используя результаты измерений и опираясь, в основном, на нормальный закон распределения полученных величин. Для неопределенности типа b это использование априорной нестатистической информации, опираясь, в основном, на равномерный закон распределения возможных значений величин в определенных границах. Таким образом, возникает задача получения решения СЛАУ с учётом этой неопределённости.

Пусть дана система линейных алгебраических уравнений (4), где A –матрица размерности n*n , x– искомый вектор, b –известный вектор. Эта система может быть однозначно разрешимой, неразрешимой и вырожденной (иметь бесконечно много решений).

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

Метод нахождения нормального решения системы (4), устойчивого к малым возмущениям правой части b и матрицы A, основанный на методе регуляризации рассматривался в работе А. Н. Тихонова [10, 11]. Выходные данные системы задаются с некоторой погрешностью, то есть вместо b и A задаются и : причем меру точности для входных данных и решения будем определять при помощи норм [12, 13].

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

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

2. Прогноз выпуска продукции по запасам сырья

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

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

Тип сырья	Расход сырья по видам продукции, ед./изд.		Запас сырья, ед.
	П 1	П 2
С 1	1	1.4	38.2
С 2	0.99	1.386	37.818

Принятые обозначения:

А — матрица норм затрат ресурсов, В — запасы ресурсов, С — прибыль на единицу продукции.

А = ; В = ;

Решение: например, пусть выпускает в количестве x ₁ -сорочки (пальто), x ₂ -брюки (пуховики). Тогда исходя из таблицы, с расходом материала каждого вида, получаем систему:

(5)

Данная система представляет собой два линейных уравнения, с двумя неизвестными. Такая система является математической моделью. И составление такой системы является лишь первым шагом в исследовании данного процесса. Второй шаг заключается в том, чтобы найти решение, а именно совокупность данных значений неизвестных: x ₁ , x ₂ , которые давали бы верное решение всем уравнениям. Понятно, для того, что решить данную экономическую задачу необходимо разобраться с основными понятиями, которые характерны для систем линейных уравнений; необходимо изучить свойства математических объектов и потом на их основе уже выбрать метод решения.

Прогнозирования выпуска продукции по запасам сырья требуется:

1) составить экономико-математическую модель задачи;

2) определить план выпуска изделий, обеспечивающий получение максимальной прибыли;

3) найти стабильное оптимальное решение;

4) определить интервал стабильности оценки ресурса;

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

Приведем пример простой СЛАУ, являющейся вырожденной, для которой традиционные методы решения некорректных задач, таких как, например, нормальное псевдорешение по А. Н. Тихонову и М. М. Лаврентьеву имеет недостатки. Нормальное псевдорешение СЛАУ есть ( x ₁ , x ₂ )=(13,18) , однако в случае минимальных колебаний значений коэффициентов, например,

(5а)

>0, система имеет единственное точное решение ( x ₁ , x ₂ )=(0,27.285714) , и сходимости при ε → 0 к нормальному псевдорешению нет.

Если же принять изначально интервальную постановку, то есть допустить колебание элемента a ₁₁ в закрытом интервале [1,1 + ε], то вычислив решение интервальной СЛАУ, мы получим точку ( x ₁ , x ₂ )=(0,27.285714) , которая является точным решением для любой системы из семейства СЛАУ описываемых соотношениями (5а), то есть является устойчивым к колебаниям коэффициентов в рамках заданных интервалов, тем самым можно устранить влияние возможных колебаний коэффициентов правой части уравнения на результат. В данной работе предлагается способ поиска решения подобных некорректных задач исходя из следующего определения

Определение . Псевдорешениями интервальной СЛАУ (4) назовем точки допускового множества системы

с расширенной элементы матрицы A()={ [ a _kj -p, a _kj +q] } ( k,j =1,2,…,n) и правой частью b() = [︀b−p, b + q]︀, где p, q — константные положительные векторы, определяющие характер расширения исходя из содержательного смысла задачи,  ≥ 0 — параметр, отвечающий за величину расширения.

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

3. Постановка задачи

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

Рассмотрим для определенности вырожденные системы (4). В этом случае речь может идти лишь о нахождении их нормального решения.

Пусть

. (6)

Предположим, что вектор b мы знаем в какой-то степени неопределенно (то есть нам известно лишь некоторое приближение ), и мы хотим знать, как эта неопределенность сказывается на решении x .

Пусть x ^* -нормальное решение системы (4), и

другая правая часть, близкая к , и , . Требуется найти приближение к вектору такое что , при , то есть построение устойчивого алгоритма для нахождения нормальных решений задачи (4) по отношению к возмущению правой части в нормах (6). Нетрудно видеть, что нахождение нормального решения рассматриваемой задачи некорректно и алгоритм, базирующийся на определении нормального решения уравнения (4) неустойчив по отношению к .

4 . Класс возможных приближенных решений

Пусть системы уравнение (4) имеет нормальное решение

при . Если , то x ^* =x _т . Тогда приближенные решения естественно искать в классе Q _ векторов , сопоставимых по точности с исходными данными, то есть таких, что .

Класс , есть множество возможных приближенных решений. Однако нельзя брать в качестве приближенного решения уравнения (1) с приближенной правой частью произвольный вектор из Q _ , так как такое приближенное решение не будет устойчивым к малым изменениям правой части. Из постановки задачи вытекает, что для получения в качестве приближенного решения такого вектора из Q _ , который устойчив к малым изменениям правой части, необходим принцип отбора возможных решений, то есть в качестве приближенного решения берется такой элемент из Q _ , который непрерывно зависел бы от  и при стремился бы к .

Согласно [13], в качестве приближения к будем брать вектор x _т из Q _ , минимизирующий функционал

(7)

на множестве Q _ ( ). Его можно рассматривать как результат применения к правой части уравнения (4) некоторого оператора , зависящего от параметра , то есть .

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

5. Единственности нормального решения

Поскольку (7) неотрицательный функционал, то существуют его точная нижняя грань на множестве Q _

и минимизирующая последовательность векторов такая, что

.

Не ограничивая общности, можно полагать, что для всякого

.

Следовательно, для любого

.

Таким образом, элементы последовательности принадлежат множеству Q _ , для которых

,

при любых фиксированных

, то есть , где

замкнутое ограниченное множество в .

По теореме Больцано-Вейерштрасса из последовательности можно выделить сходящуюся подпоследовательность .

Пусть

.

В силу замкнутости множества , которому принадлежат последовательность , вектор также принадлежит множеству

Так как

,

то функционал (3) достигает минимума на множестве на вектор

.

Таким образом, элемент принадлежит компактному в множеству .

Пусть задана последовательность такая, что

,

где -последовательность положительных чисел, сходящаяся к нулю, то есть

, при . Тогда для каждого в силу неравенства Минковского [4] справедлива оценка

Следовательно, при , , где

.

С другой стороны, для всякого

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

, последовательности .

Пусть

.

Так как , то для всякого элемента подпоследовательности выполняется неравенство

.

Переходя в нем к пределу при

, получим

.

Следовательно,

.

В силу единственности нормального решения системы уравнений (4) с правой частью , имеем . Таким образом

.

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

Теорема 1. Вектор -реализующий минимум функционала

вида (7) на множестве обладают следующими свойствами:

1) он определен для всякого и любого ;

2) -сходятся к вектору , являющимся нормальным решением системы (1) в виде ,при , то есть для любого существует такое

, что из неравенства следует неравенство ,где ;

3) он является регуляризирующим для системы уравнения (1).

6. Основные результаты

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

, на множестве , то есть , где

.

Предположим, что для из выполняется два неравенстве:

1) ;

2)

.

В первом случае решением вариационной задачи на минимум функционала на множестве является элемент . Это решение устойчиво к малым изменениям . Рассмотрим второе неравенство. В этом случае задачу минимизации функционала на множестве можно свести к классической задаче на условный экстремум функционала .

Допустим, что достигает на элемент

из , для которого

.

По условию, , то есть . Следовательно, .

С другой стороны, если квазимонотонно, то каков бы ни был элемент из

, не принадлежащий множеству , в любой его окрестности найдется элемент из для которого

. (8)

Так как элемент принадлежит множествам и , а следовательно, и множеству , то неравенство (8) противоречит тому, что на

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

Тогда задачу нахождения вектора можно поставить так: среди векторов , удовлетворяющих условию

найти вектор минимизирующий функционал вида (3).

Эту задачу можно решить методом Лагранже, то есть в качестве брать вектор , минимизирующий функционал

(9)

с параметром α, определяемым по невязке или по отношению двух норм (см. [11]).

7. Минимизации функционал типа А. Н. Тихонова

Рассмотрим квадратичный функционал (9), где

-функционал вида (7). Нетрудно убедиться, что существует один и только один вектор , реализующий минимум при любых фиксированных и .

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

,

получающихся из условий минимума функционала :

.

Вектор можно рассматривать как результат применения к некоторого оператора , зависящего от параметра , то есть .

Если и -решение системы уравнений

, то для любого существует , что из неравенства , следует неравенство , где -вектор, реализующий минимум и .

Отсюда следует, что при любом

.

Действительно,

так как и по определению нормального решения уравнения .

Таким образом, для любого и произвольного такого, что , имеем

.

Пусть и какие-либо непрерывные функции, равен нулю при и такие, что . Тогда из последнего неравенства следует, что при любом , удовлетворяющим условиям

(10)

будем иметь

, (11)

где при .

Докажем теперь, что для любого существует такое , что если , то , где удовлетворяет условиям (6).

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

Пусть последовательность векторов, таких что , где последовательность чисел сходится к нулю при

. Этой последовательности отвечает последовательность векторов , . В силу (11), если удовлетворяют условию (10), то множество ограничено. Следовательно из нее можно выбрать сходящуюся подпоследовательность .

Пусть

.

В этом случае, для всякого , имеем

так как . Используя условие (10), то есть

,

получим

,

где , при .

Переходя в нем к пределу при , получим . Следовательно, . В силу нормального решения системы уравнений (4) с правой частью имеем .

Таким образом,

.

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

, что из неравенства , следует неравенство , где удовлетворяет условиям (10). Таким образом, доказана следующая теорема 2.

Теорема 2. Пусть — нормальное решение системы уравнений (4) и какие-либо -приближения к . Пусть далее, и какие-либо непрерывные функции, равен нулю при

и такие, что

.

Тогда для любой положительной функции , удовлетворяющей условиям (10) векторы

сходятся к нормальному решению системы (1) при , то есть для любого существует такое

, что из неравенства , следует неравенство , где ( ) –вектор, реализующий минимум вида (9) при любых фиксированных .

8. Вычислительный эксперимент

При разработке численных алгоритмов наиболее естественно использовать метод регуляризации, минимизации функционал (7) и (9), оставляя в СЛАУ конечное число уравнений и конечное число неизвестных.

Исследуем поведение решение СЛАУ с двумя уравнениями и двумя неизвестными вида (5). График решений системы уравнений с двумя уравнениям разрешенного относительно неизвестный называется его кривыми (прямыми линиями). В геометрических терминах данная система уравнений выражает следующий факт: кривая на

-плоскость является его решением в том и только том случае, когда в любой точке этой прямой линии она имеет пересечение или касательную с условиям собственное значениям соответствующих уравнениям системы. Для построения графиков функций из первого уравнения определим x ₁ как функцию зависимости от параметра x ₂ . Аналогично, из второго уравнения определим x ₂ как функцию зависимости от параметра x ₁ .

На рис. 1 (а, б) представлены решения системы уравнений (5). На рис. 1а приведены результаты вырожденной системы (5), а на рис. 1б — плохо обусловленной.

а)

б)

Рис.1. График поведения системы (5)

Из рис.1 видно, что графики системы точки пересечения не имеет, то есть прямые линии лежат параллельно. Если график системы уравнений точки пересечение не имеет, то она вырожденная.

Литература:

1. 1.Добронец Б. С. Интервальная математика: Учеб. Пособие /Б. С. Добронец // -Красноярск: Красноярский государственный университет. -2004. -216 с.
2. Shary, S. P. A new technique in systems analysis under interval uncertainty and ambiguity / S. P. Shary // Reliable Computing. — 2002. — Vol. 8, no. 5. —P. 321–418.
3. Panyukov, A. V. Computing best possible pseudo-solutions to interval linear systems of equations / A. V. Panyukov, V. A. Golodov // Reliable Computing. –2013. –Vol. 19. –P. 215–228.
4. Шарый, С. П. Конечномерный интервальный анализ / С. П. Шарый. — Новосибирск, «XYZ», 2013. —С. 285.
5. Алтунин А. Е., Семухин М. В. Модели и алгоритмы принятия решений в нечетких условиях: Монография. -Тюмень: Издательство Тюменского государственного университета, 2000. 352 с.
6. 6.Жолен Л., Кифер М., Дидри О., Вальтер Э. Прикладной интервальный анализ. -М.-Ижевск: Институт компьютерных исследований. -2005. –468 с.
7. Дарков А. В. Строительная механика / А. В. Дарков, Н. Н. Шапошников. — М.: Высш. шк., 1986. — 607 с.
8. Бессонов Л. А. Теоретические основы электротехники. Электрические цепи./ Л. А. Бессонов. — М.: Высш. шк., 1996. — 626 с.
9. Захаров И. П. Теория неопределённости в измерениях. / И. П. Захаров, В. Д. Кукуш. — Харков:Консум. –2002. — 256 с.
10. Тихонов А. Н. О некорректных задачах линейной алгебры и устойчивом методе их решения. //ДАН СССР. -1965.-Т.163, № 6.
11. Тихонов А. Н. Об устойчивости алгоритмов для решения вырожденных систем линейных алгебраических уравнений. // ЖВМ и МФ. -1965. –Т.5, № 4
12. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. –М.: Наука. -1986. — 288 с.
13. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. -М.: Наука. -1981. –
14. Джураев Х. Ш. Об одном регуляризирующих алгоритме получения приближений к нормальному решению вырожденных систем линейных алгебраических уравнений (СЛАУ) // Прикладная математика. Межвузовской сборник научных трудов. -М.: МГПИ им. В. И. Ленина,1986. -130 с.