Методы решения некорректно поставленных задач (стр. 6 из 7)

z = Vz*, u = Vu*

ее можно привести к диагональному виду и преобразованная система будет иметь вид

l_iz_i*=u_i* , i= 1, 2,. ..,п,

где l_i — собственные значения матрицы А.

Если симметричная матрица А — невырожденнаяи имеет ранг r, то n – r ее собственных значений равны нулю. Пусть

l_i¹0 для i=1, 2, ..., r;

и

l_i=0 для i=r+1,r+2, …, n.

Полагаем, что система (3; 2,2) разрешима. При этом u_i*= 0 для i =r + 1, ..., n.

Пусть «исходные данные» системы (А и и) заданы с погрешностью, т. е. вместо А и и заданы их приближения А и u:

|| A – A ||<=h, ||u – u||<=d. При этом

(3;2,4)

Пусть l_i — собственные значения матрицы А. Известно, что они непрерывно зависят от А в норме (3; 2,4). Следовательно, собственные значения l_r+1 , l_r+2, …,l_nмогут быть сколь угодно малыми при достаточно малом h.

Если они не равны нулю, то

z_i*=

.

Таким образом, найдутся возмущения системы в пределах любой достаточно малой погрешности А и и, для которых некоторые z_i* будут принимать любые наперед заданные значения. Это означает, что задача нахождения нормального решения системы (3; 2,2) является неустойчивой.

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

3.3. Метод регуляризации нахождения нормального решения

3.3.1. Пусть z° есть нормальное решение системы

Аz = и. (3; 3,1)

Для простоты будем полагать, что приближенной может быть лишь правая часть, а оператор (матрица) А — точный.

Итак, пусть вместо и мы имеем вектор и, || и — и ||<=d ;т. е. вместо системы (3;3,1) имеем систему

(3; 3,2)

Аz = u.

Требуется найти приближение z_d к нормальному решению системы (3;3,1), т. е. к вектору z° такое, что z_d-z° при d-0. Отметим, что векторы u и u (один из них или оба) могут не удовлетворять классическому условию разрешимости.

Поскольку система (3; 3,1) может быть неразрешимой, то inf ||Az-u|| = m >=0, где inf берется по всем векторам zÎ Rⁿ.

Естественно искать приближения z_d в классе Q_d векторов z, сопоставимых по точности с исходными данными, т. е. таких, что || Az – u ||<=m+d. Но поскольку вместо вектора u мы имеем вектор u, то мы можем найти лишь

m=inf || Az – u ||.

zÎ Rⁿ

Отметим, что из очевидных неравенств

||Az – u ||<=||Az – u || + || u – u || ,

||Az – u ||<= || Az – u || + ||u – u ||

следуют оценки m<=m+d, m<=m+d, приводящие к неравенству | m — m|<=d. Поэтому будем искать приближение z_d к нормальному решению z° в классе Q_d векторов z, для которых ||Аz — и|| <=m+2d. Отметим, что если имеется информация о разрешимости системы (3;3,1), то m = 0 ив качестве класса Q_d можно брать класс векторов z, для которых ||Аz — и|| <=d. Класс Q_d есть класс формально возможных приближенных решений.

Но нельзя в качестве z_d брать произвольный вектор из класса Q_d, так как такое «приближение» будет неустойчивым к малым изменениям правой части уравнения (3;3,2). Необходим принцип отбора. Он естественным образом вытекает из постановки задачи. В самом деле согласно определению нормального решения искомое решение z° должно быть псевдорешением с минимальной нормой. Поэтому в качестве приближения к z° естественно брать вектор z_d из Q_d, минимизирующий функционал

W[ z ] = ||z||² на множестве Q_d.

Таким образом, задача сводится к минимизации функционала W[ z ] = ||z||² на множестве Q_d векторов z, для которых выполняется условие || Аz — u|| <=m+2d.

3.3.2. Пусть z_d — вектор из Q_d, на котором функционал ||z||² достигает минимума на множестве Q_d. Его можно рассматривать как результат применения к правой части u уравнения (3; 3,2) некоторого оператора R₁(u, d), зависящего от параметра d. Справедлива

Теорема 1. Оператор R₁(u, d) обладает следующими свойствами:

1) он определен для всякогоuÎR^mи любогоd > 0;

2) приd-0 z_d== R₁(u, d) стремится к нормальному решениюz° уравнения Аz=u, т. е. он является регуляризирующим для уравнения Аz=u .

3.3.3. Пусть z_d — вектор, на котором функционал W[ z ] = ||z||² достигает минимума на множестве Q_d. Легко видеть из наглядных геометрических представлений, что вектор z_d лежит на границе множестваQ_d,т.е. ||Az_d- u ||=m+2d=d₁.

Это следует непосредственно также из того, что функционал W[ z ] = ||z||² является сстабилизирующим и квазимонотонным. Стабилизирующий функционал W[ z ] называется квазимонотонным , если каков бы ни был элемент z из F₁ , не принадлежащий множеству M₀ , в любой его окрестности найдется элемент z₁из F₁, для которого W[ z₁ ]< W[ z ], т.е. если функционал не имеет локальных минимумов на множестве F₁&bsol; M₀.

Задачу нахождения вектора z_d можно поставить так:среди векторов z, удовлетворяющих условию ||Az – u ||=m+2d, найти вектор z_d с минимальной нормой, т. е. минимизирующий функционал W[ z ]=||z||².

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

М^a [z, u] = ||Az - u ||²+ a||z||²,a>0,

с параметром a, определяемым по невязке, т. е. из условия ||Аz^a— u||=d1. При этом параметр aопределяется однозначно .

3.3.4. Поскольку М^a [z, u] — квадратичный функционал, то для любых u ÎR^m и a> 0 существует лишь один минимизирующий его вектор z^a. В самом деле, допустим,

что существуют два вектора z^a и z^a, минимизирующие его. Рассмотрим векторы z, расположенные на прямой (пространства Rⁿ), соединяющей z^a и z^a:

z = z^a+ b(z^a-z^a).

Функционал М^a [z, u] на элементах этой прямой есть неотрицательная квадратичная функция от b. Следовательно, она не может достигать наименьшего значения при двух различных значениях b: b = 0 (z=z^a) иb=1 (z=z^a).

Компоненты z_j^a вектора z^a являются решением системы линейных алгебраических уравнений

получающихся из условий минимума функционала М^a [z, u]:

Здесь

Компоненты z_j^a могут быть определены и с помощью какого-нибудь другого алгоритма минимизации функционалаМ^a [z, u].

Вектор z^a можно рассматривать как результат применения к u некоторого оператора z^a=R(u, a), зависящего от параметра a.

Покажем, что оператор R₀(u, a) является регуляризирующим для системы (3;3,1), т. е. обладает свойствами 1) и 2) определения 2 (см. 3.1.2.). В п. 3.3.2. было сказано, что он определен для всяких u ÎR^m и a> О и, следовательно, обладает свойством 1). Теперь покажем справедливость свойства 2), т. е. существование таких функций a=a(d) , что векторы z^a(d) = R₀(u,a(d)) сходятся к нормальному решению z° системы (3; 3,1) при d-0. Это непосредственно следует из приводимой ниже теоремы 2.

Теорема 2( Тихонова). Пусть z° есть нормальное решение системы Az=u и вместо вектора u мы имеем вектор u такой, что ||u—u||<=d. Пусть, далее,b1(d)и b2(d) — какие-либо непрерывные на [0, d2] и положительные на (0, d2] функции, монотонно стремящиеся к нулю при d- 0 и такие, что

Тогда для любой .положительной на (0, d2] функции a=a(d) , удовлетворяющей условиям

векторы z^a(d) = R₀(u,a(d)) сходятся к нормальному решению z⁰ системы Az = u при d-0, т. е.

Примечание. Доказательства теорем в данном разделе опущены, т.к. основной теоретической частью работы является раздел «Метод Подбора. Квазирешения». Метод Тихонова описан из-за использования его в численном эксперименте.

ЗАКЛЮЧЕНИЕ

Для реализации численного примера был выбран метод Тихонова решения плохо обусловленных СЛАУ. В качестве исходной была взята СЛАУ Az=u, имеющая в матричной записи вид:

Определитель матрицы коэффициентов этой системы близок к нулю – он равен 0.000125. Попробуем решить эту систему с помощью обратной матрицы:

z=A^-1u

Получим z₁=316

z₂=-990

z₃=832

Теперь предположим, что правая часть нам известна приближенно, с погрешностью 0.1 Изменим, к примеру, третий элемент вектора-столбца с 1 на 1.1 :

Попробуем решить новую систему также с помощью обратного оператора. Мы получаем другой результат:

z₁=348

z₂=-1090

z₃=916.

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

Будем искать решение методом Тихонова. В теоретической части было показано, что целесообразно использовать регуляризирующий оператор следующего вида: (aE + A^TA)z^a=A^Tu_d , где E – единичная матрица, z^a -- приближенное нормальное решение, A^T– транспонированная исходная матрица, a -- параметр регуляризации,