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

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

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

Похожие работы

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

Скачать

39390

0

2

... , действующий из нормированного пространства Z в нормированное пространство U. В 1963 г. А.Н.Тихонов дал знаменитое определение регуляризирующего алгоритма (РА), которое лежит в основе современной теории некорректно поставленных задач. Определение. Регуляризирующим алгоритмом (регуляризирующим оператором)  называется оператор, обладающий двумя следующими свойствами: 1)  определен для любых δ ...

Расчет и анализ потерь активной мощности

Скачать

139305

0

14

... при решении предусмотренных задач одна из эталонных схем (рабочая) копируется в рабочие файлы. Для моделирования, анализа и хранения режимов создана база режимов (до 12 режимов). Предусмотрена возможность записи произвольного режима, являющегося результатом решения одной из задач, в базу режимов. Все расчеты, включая и формирование отображаемых на дисплеях кадров, производятся на ЭВМ ИВП. В ИВП ...

Решение обратных задач теплопроводности для элементов конструкций простой геометрической формы

Скачать

15935

0

12

... из-за дефектов производства, технологии изготовления, загрязнения поверхности, погрешности измерения и обработки экспериментальной информации. Влияние погрешностей исходной информации на решение обратной задачи теплопроводности оценивалось с помощью метода статистических испытаний Монте – Карло / 5-8 /. Анализ результата статистического моделирования решения обратной задачи позволяет установить ...

Вычислительные методы алгебры (лекции)

Скачать

26259

2

288

... и получим . ЧТД. Пример. Вычислим значение , где . Действие Содержимое НГ ВГ (1) x 2.57 2.58 (2) y 1.45 1.46 (3) z 8.33 8.34 (1)+(2) x+y 4.02 4.04 (1)-(2) x-y 1.11 1.13 9.24 9.43 2.28 2.35 §8. Математические модели и численные методы.Велика роль математики в решении задач реального мира. Физиков математика интересует не сама по ...