Методы решения некорректно поставленных задач
(3;2,4)
Пусть i — собственные значения матрицы А. Известно, что они непрерывно зависят от А в норме (3; 2,4). Следовательно, собственные значения r+1 , r+2, …,n могут быть сколь угодно малыми при достаточно малом h.
Если они не равны нулю, то
zi*=
.
Таким образом, найдутся возмущения системы в пределах любой достаточно малой погрешности А и и, для которых некоторые zi* будут принимать любые наперед заданные значения. Это означает, что задача нахождения нормального решения системы (3; 2,2) является неустойчивой.
Ниже дается описание метода нахождения нормального решения системы (3; 2,2), устойчивого к малым (в норме (3; 2,4)) возмущениям правой части и , основанного на методе регуляризации.
3.3. Метод регуляризации нахождения нормального решения
3.3.1. Пусть z° есть нормальное решение системы
Аz = и. (3; 3,1)
Для простоты будем полагать, что приближенной может быть лишь правая часть, а оператор (матрица) А — точный.
Итак, пусть вместо и мы имеем вектор и, || и — и || <=; т. е. вместо системы (3;3,1) имеем систему
(3; 3,2)
Аz = u.
Требуется найти приближение z к нормальному решению системы (3;3,1), т. е. к вектору z° такое, что z z° при 0. Отметим, что векторы u и u (один из них или оба) могут не удовлетворять классическому условию разрешимости.
Поскольку система (3; 3,1) может быть неразрешимой, то inf ||Az-u|| = >=0, где inf берется по всем векторам z Rn.
Естественно искать приближения z в классе Q векторов z, сопоставимых по точности с исходными данными, т. е. таких, что || Az – u ||<=+. Но поскольку вместо вектора u мы имеем вектор u, то мы можем найти лишь
=inf || Az – u ||.
z Rn
Отметим, что из очевидных неравенств
||Az – u ||<=||Az – u || + || u – u || ,
||Az – u ||<= || Az – u || + ||u – u ||
следуют оценки <=+, <=+, приводящие к неравенству | — | <=. Поэтому будем искать приближение z к нормальному решению z° в классе Q векторов z, для которых || Аz — и || <= +2. Отметим, что если имеется информация о разрешимости системы (3;3,1), то = 0 и в качестве класса Q можно брать класс векторов z, для которых || Аz — и|| <= . Класс Q есть класс формально возможных приближенных решений.
Но нельзя в качестве z брать произвольный вектор из класса Q, так как такое «приближение» будет неустойчивым к малым изменениям правой части уравнения (3;3,2). Необходим принцип отбора. Он естественным образом вытекает из постановки задачи. В самом деле согласно определению нормального решения искомое решение z° должно быть псевдорешением с минимальной нормой. Поэтому в качестве приближения к z° естественно брать вектор z из Q, минимизирующий функционал
[ z ] = ||z||2 на множестве Q .
Таким образом, задача сводится к минимизации функционала [ z ] = ||z||2 на множестве Q векторов z, для которых выполняется условие || Аz — u || <= +2.
3.3.2. Пусть z — вектор из Q, на котором функционал ||z||2 достигает минимума на множестве Q. Его можно рассматривать как результат применения к правой части u уравнения (3; 3,2) некоторого оператора R1(u,), зависящего от параметра . Справедлива
Теорема 1. Оператор R1(u,) обладает следующими свойствами:
1) он определен для всякого uRm и любого > 0;
2) при 0 z== R1(u,) стремится к нормальному решению z° уравнения Аz=u, т. е. он является регуляризирующим для уравнения Аz=u .
3.3.3. Пусть z — вектор, на котором функционал [ z ] = ||z||2 достигает минимума на множестве Q. Легко видеть из наглядных геометрических представлений, что вектор z лежит на границе множества Q, т.е. ||Az - u ||= +2 =1.
Это следует непосредственно также из того, что функционал [ z ] = ||z||2 является сстабилизирующим и квазимонотонным. Стабилизирующий функционал [ z ] называется квазимонотонным , если каков бы ни был элемент z из F1 , не принадлежащий множеству M0 , в любой его окрестности найдется элемент z1 из F1, для которого [ z1 ]<[ z ], т.е. если функционал не имеет локальных минимумов на множестве F1 M0.
Задачу нахождения вектора z можно поставить так: среди векторов z, удовлетворяющих условию ||Az – u ||= +2 , найти вектор z с минимальной нормой, т. е. минимизирующий функционал [ z ]=||z||2.
Последнюю задачу можно решать методом Лагранжа, т. е. в качестве z брать вектор z, минимизирующий функционал
М [z, u] = ||Az - u ||2+||z||2, >0,
с параметром , определяемым по невязке, т. е. из условия ||Аz— u||=1. При этом параметр определяется однозначно .
3.3.4. Поскольку М [z, u] — квадратичный функционал, то для любых uRm и > 0 существует лишь один минимизирующий его вектор z. В самом деле, допустим,
что существуют два вектора z и z, минимизирующие его. Рассмотрим векторы z, расположенные на прямой (пространства Rn), соединяющей z и z:
z = z + (z - z).
Функционал М [z, u] на элементах этой прямой есть неотрицательная квадратичная функция от . Следовательно, она не может достигать наименьшего значения при двух различных значениях : = 0 (z = z) и =1 (z = z).
Компоненты zj вектора z являются решением системы линейных алгебраических уравнений

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

Здесь

Компоненты zj могут быть определены и с помощью какого-нибудь другого алгоритма минимизации функционала М [z, u].
Вектор z можно рассматривать как результат применения к u некоторого оператора z=R(u, ), зависящего от параметра .
Покажем, что оператор R0(u, ) является регуляризирующим для системы (3;3,1), т. е. обладает свойствами 1) и 2) определения 2 (см. 3.1.2.). В п. 3.3.2. было сказано, что он определен для всяких uRm и > О и, следовательно, обладает свойством 1). Теперь покажем справедливость свойства 2), т. е. существование таких функций = , что векторы z = R0(u, ) сходятся к нормальному решению z° системы (3; 3,1) при 0. Это непосредственно следует из приводимой ниже теоремы 2.
Теорема 2( Тихонова). Пусть z° есть нормальное решение системы Az= u и вместо вектора u мы имеем вектор u такой, что ||u—u||<=. Пусть, далее, и — какие-либо непрерывные на [0, 2] и положительные на (02] функции, монотонно стремящиеся к нулю при 0 и такие, что

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

векторы z = R0(u, ) сходятся к нормальному решению z0 системы Az = u при 0, т. е.

Примечание. Доказательства теорем в данном разделе опущены, т.к. основной теоретической частью работы является раздел «Метод Подбора. Квазирешения». Метод Тихонова описан из-за использования его в численном эксперименте.
ЗАКЛЮЧЕНИЕ
Для реализации численного примера был выбран метод Тихонова решения плохо обусловленных СЛАУ. В качестве исходной была взята СЛАУ Az=u, имеющая в матричной записи вид:

Определитель матрицы коэффициентов этой системы близок к нулю – он равен 0.000125. Попробуем решить эту систему с помощью обратной матрицы:
z=A-1u
Получим z1=316
z2=-990
z3=832
Теперь предположим, что правая часть нам известна приближенно, с погрешностью 0.1 Изменим, к примеру, третий элемент вектора-столбца с 1 на 1.1 :

Попробуем решить новую систему также с помощью обратного оператора. Мы получаем другой результат:
z1=348
z2=-1090
z3=916.
Мы видим, что малому изменению правой части данной системы отвечают весьма значительные изменения решения. Очевидно, эта система – плохо обусловленная, и здесь не может идти речи о нахождении решения близкого к точному с помощью обратного оператора.
Будем искать решение методом Тихонова. В теоретической части было показано, что целесообразно использовать регуляризирующий оператор следующего вида: (E + ATA)z=ATu , где E – единичная матрица, zприближенное нормальное решение, AT – транспонированная исходная матрица, параметр регуляризации,
u -- правая часть, заданная неточно. Эту задачу можно решать стандартными методами, задав предварительно функцию удовлетворяющую условиям теоремы Тихонова. В моем примере это функция =/4Далее будем решать регуляризованную задачу с точностью .001 ,последовательно изменяя значения .
В качестве контр-примера можно подставить в программу любую функцию , не удовлетворяющую условиям теоремы Тихонова. Любая положительная функция монотонно возрастающая, не обладающая свойством 0 при 0, не будет минимизировать невязку.
Текст программы приведен в приложении 1. Полная распечатка результатов приведена в приложении 2. Здесь же представлены окончательные значения на выходе из программы.
Приближение к нормальному решению
Z(1)= 3.47834819174013E+0002
Z(2)=-1.08948394975175E+0003
Z(3)= 9.15566443137791E+0002
Значение правой части при подстановке прибл. решения
U1(1)= 9.99997717012495E-0001
U1(2)= 1.00000741970775E+0000
U1(3)= 1.09948402394883E+0000
Значение параметра регуляризации:
2.61934474110603E-0010
ПРИЛОЖЕНИЯ
Приложение 1.
Текст программы для реализации метода Тихонова на языке PASCAL
Uses CRT;
type
real=extended;
const
matrixA: array[1..3,1..3] of real = ((-19/20,1/5, 3/5),
(-1 ,0.1, 0.5),
(-0.01 ,0 ,1/200));
One: array [1..3,1..3] of real = ((1,0,0),
(0,1,0),
(0,0,1));
U:array[1..3] of real = (1,1,1.1);
var
i,j,k,q:byte;
A,At,A1,A2,Ar,One1:array[1..3,1..3] of real;
delta,Det,S,alpha:real;
B,Z,U1:array[1..3] of real;
f:text;
Procedure TransA;
begin
for i:=1 to 3 do
for j:=1 to 3 do
At[i,j]:=A[j,i]
end;
Function Koef(par1,par2:byte):real;
var
Sum:byte;
Tmp:real;
begin
Sum:=par1+par2;
Tmp:=1;
for k:=1 to sum do
Tmp:=Tmp*(-1);
Koef:=Tmp;
end;
Function AlAdd(par1,par2:byte):real;
type
element=record
value:real;
flag:boolean;
end;
var
BB:array[1..2,1..2] of real;
AA:array[1..3,1..3] of element;
k,v,w:byte;
N:array[1..4] of real;
P1:real;
begin
for v:=1 to 3 do
for w:=1 to 3 do begin
AA[v,w].value:=A2[v,w];
AA[v,w].flag:=true
end;
for v:=1 to 3 do AA[par1,v].flag:=false;
for v:=1 to 3 do AA[v,par2].flag:=false;
{ for v:=1 to 3 do begin
for w:=1 to 3 do write(AA[i,j].value:2:3,' ');
writeln
end; }
k:=1;
for v:=1 to 3 do
for w:=1 to 3 do
begin
if AA[v,w].flag then
begin
N[k]:=AA[v,w].value;
{ writeln(N[k]);}
k:=k+1
end;
end;
BB[1,1]:=N[1]; BB[1,2]:=N[2];
BB[2,1]:=N[3]; BB[2,2]:=N[4];
{ writeln('alg dop',par1,par2,' ',BB[1,1]*BB[2,2]-BB[1,2]*BB[2,1]);}
AlAdd:=BB[1,1]*BB[2,2]-BB[1,2]*BB[2,1];
end;
Function DetCount:real;
var
S1:real;
z:byte;
begin
S1:=0;
for z:=1 to 3 do S1:=S1+A2[1,z]*Koef(1,z)*AlAdd(1,z);
DetCount:=S1;
end;
Procedure RevMatr;
begin
for i:=1 to 3 do
for j:=1 to 3 do
Ar[j,i]:=Koef(i,j)*AlAdd(i,j)/DetCount;
{ for i:=1 to 3 do begin
for j:=1 to 3 do write(Ar[i,j],' ');
writeln;
end;}
end;
Function AllRight:boolean;
begin
writeln(f,'Ґўп§Є Ї® 1-¬г н«-вг',(abs(U[1]-U1[1])));
writeln(f,'Ґўп§Є Ї® 2-¬г н«-вг',(abs(U[2]-U1[2])));
writeln(f,'Ґўп§Є Ї® 3-¬г н«-вг',(abs(U[3]-U1[3])));
writeln(F);
if (abs(U[1]-U1[1])<0.001) and (abs(U[2]-U1[2])<0.001) and
(abs(U[3]-U1[3])<0.001) then AllRight:=true
else AllRight:=false
end;
Function Pow(par1:real;par2:byte):real;
var
S2:real;
z:byte;
begin
S2:=1;
if par2=0 then begin
Pow:=1;
exit
end
else
for z:=1 to par2 do S2:=S2*par1;
Pow:=S2;
end;
BEGIN
clrscr;
Assign(f,'c:tikh.txt');
Rewrite(f);
for i:=1 to 3 do
for j:=1 to 3 do
A[i,j]:=matrixA[i,j];
TransA;
Det:=0.000125;
{----------------------------}