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

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

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

А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.

Итак, рассмотрим произвольную систему линейных алгебраических уравнений (короче — СЛАУ) А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,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.

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

zi*=.

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

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