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

3.2.1. Известно, с какими трудностями связано решение так называемых плохо обусловленных систем линей­ных алгебраических уравнений: малым изменениям пра­вых частей таких систем могут отвечать большие (выхо­дящие за допустимые пределы) изменения решения.

Рассмотрим систему уравнений

                                                       А z = u ,                                                         (3; 2,1)

где А — матрица с элементами a_ij, А ={a_ij}, z — иско­мый вектор с координатами z_j , z={z_j}, и — известный вектор с координатами и _i , u= {u_i}, i, j =1, 2, ..., п . Система (3; 2,1) называется вырожденной, если опреде­литель системы равен нулю, detA = 0. В этом случае матрица А имеет равные нулю собственные значения. У плохо обусловленных систем такого вида матрица А имеет близкие к нулю собственные значения.

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

В практических задачах часто правая часть и и эле­менты матрицы А, т. е. коэффициенты системы (3; 2,1), известны приближенно. В этих случаях вместо системы (3; 2,1) мы имеем дело с некоторой другой системой Az=и такой, что ||A-A||<=h, ||u-u||<= d, где смысл норм обычно определяется характером задачи. Имея

вместо матрицы А матрицу A, мы тем более не можем высказать определенного суждения о вырожденности или невырожденности системы (3; 2,1).

В этих случаях о точной системе А z=u, решение которой надо определить, нам известно лишь то, что для матрицы А и правой части и выполняются неравенства

||A-A||<=h, ||u-u||<= d. Но систем с такими исходными данными (А, и) бесконечно много, и в рамках извест­ного нам уровня погрешности они неразличимы. Поскольку вместо точной системы (3; 2,1) мы имеем приближенную систему А z= и, то речь может идти лишь о нахождении приближенного решения. Но приближенная система А z =и может быть неразрешимой. Возникает вопрос:

что надо понимать под приближенным решением систе­мы (3; 2,1) в описанной ситуации?

Среди «возможных точных систем» могут быть и вы­рожденные. Если они разрешимы, то имеют бесконечно много решений. О приближенном нахождении какого из них должна идти речь?

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

В основе построения таких методов лежит идея «от­бора». Отбор можно осуществлять с помощью специальных, заранее задаваемых функционалов W[ z ] , входящих в постановку задачи.

Неотрицательный функционал W[ z ] , определенный на всюду плотном в F подмножестве F₁ множества F, называется стабилизирующим функционалом, если:

а) элемент z_T принадлежит его области определения;

б) для всякого числа d>0 множество F_1,d элементов z из F₁ , для которых

W[ z ]<=d, компактно на F.

3.2.2. Итак, рассмотрим произвольную систему линейных алгебраических уравнений (короче — СЛАУ)

Аz =u,                                            (3; 2,2)

в которой z и u—векторы, z=(z₁, z₂, ...,z_n) ÎRⁿ, и=(u₁,u₂, ...,u_n) ÎR^m, А—матрица с элементами a_ij, А = {a_ij}, где j =1, 2, ..., n; i= 1, 2, ..., т, и число п не обязано быть равным числу т.

Эта система может быть однозначно разрешимой, вы­рожденной (и иметь бесконечно много решений) и не­разрешимой.

Псевдорешением системы (3; 2,2) называют вектор z, минимизирующий невязку || Az – u || на всем пространстве Rⁿ. Система (3; 2,2) может иметь не одно псевдоре­шение. Пусть F_A есть совокупность всех ее псевдореше­ний и z¹ — некоторый фиксированный вектор из Rⁿ , оп­ределяемый обычно постановкой задачи.

Нормальным относительно вектора z¹ решением си­стемы (3;2,2) будем называть псевдорешение z⁰ с ми­нимальной нормой || z – z¹ ||, т. е. такое, что

|| z⁰ – z¹ || =

Здесь  . В дальнейшем для простоты записи будем считать z¹= 0 и нормальное относительно вектора z¹=0 решение называть просто нормальным ре­шением.

Для любой системы вида (3; 2,2) нормальное решение существует и единст­венно.

Замечание 1. Нормальное решение z° системы (3;2,2) можно определить также как псевдорешение, минимизирующее заданную положительно определенную квадратичную форму относительно координат вектора z—z¹. Все излагаемые ниже результаты остаются при этом справедливыми.

Замечание 2. Пусть ранг матрицы А вырожден­ной системы (3; 2,1) равен r < n и z_r+1,z_r+2, … , z_n— базис линейного пространства N _A , состоящего из элемен­тов z, для которых А z = 0 , N_A = {z; А z = 0}. Решение z° системы (3; 2,1), удовлетворяющее n—r условиям ортогональности

                            (z⁰ – z¹, z_S)= 0,   S= r + 1, r + 2, .. ,n,                 (3; 2,3)

определяется однозначно и совпадает с нормальным ре­шением.

3.2.3. Нетрудно видеть, что задача нахождения нормаль­ного решения системы (3; 2,2) является некорректно поставленной. В самом деле, пусть А — симметричная матрица. Если она невырожденная, то ортогональным преобразованием

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)) возму­щениям правой части и , основанного на методе регуляризации.