Портал | Содержание | О нас | Авторам | Новости | Первая десятка | Дискуссионный клуб | Чат Научный форум --> Первая десятка "Русского переплета" Темы дня:

Президенту Путину о создании Института Истории Русского Народа. |Нас посетило 40 млн. человек | Чем занимались русские 4000 лет назад?

| Кому давать гранты или сколько в России молодых ученых?

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

В. А. СОБОЛЕВ

Самарский государственный университет

ВВЕДЕНИЕ

Для людей, чье знакомство с математикой ограничилось школьными учебниками, название статьи выглядит по меньшей мере странным, если не абсурдным. В то же время для специалистов, связанных с обработкой массивов данных измерений, несовместные линейные алгебраические системы - это обычные объекты изучения, и интерпретация "решений" таких систем является рутинным занятием.

Для широкого круга прикладных задач (радиофизика и радиоастрономия, сейсморазведка и космонавтика и др.) типичной является следующая задача. Предполагается, что некоторая величина c есть линейная комбинация величин a1 , a2 , _, an , то есть

c = a1x1 + a2x2 + _ + anxn

с неизвестными коэффициентами x1 , x2 , _, xn . Обычно эти коэффициенты определяются экспериментальным путем. С этой целью производятся измерения величин c и a1 , a2 , _, an . Результаты k-го измерения величины c обозначим через bk , а величин a1 , a2 , _, an - через ak1 , ak2 , _, akn соответственно. Для неизвестных коэффициентов x1 , x2 , _, xn получаем систему линейных алгебраических уравнений вида

a11x1 + a12x2 + _ + a1nxn = b1 ,

a21x1 + a22x2 + _ + a2nxn = b2 ,

..............................................

am1x1 + am2x2 + _ + amnxn = bm ,

состоящую из m уравнений с n неизвестными. Здесь число уравнений определяется количеством произведенных измерений, и обычно это число не меньше, чем количество неизвестных коэффициентов, то есть m $ n. В векторной форме эта система представима следующим образом:

Ax = b,

где

Приведем хорошо известные сведения из теории линейных алгебраических систем [1].

Если n = m и det A ? 0, то рассматриваемая система имеет единственное решение. В этом случае система является совместной, то есть имеющей решение, и, более того, определенной, то есть имеющей единственное решение. В общем случае ответ на вопрос о разрешимости системы (1) дает следующая теорема Кронекера-Капелли.

Теорема. Система (1) совместна тогда и только тогда, когда ранг расширенной матрицы равен рангу матрицы A.

Напомним, что расширенной матрицей системы называется матрица вида

Совместная система может быть неопределенной, если она имеет более одного решения. Если условия теоремы Кронекера-Капелли не выполнены и система не имеет решений, то есть является несовместной, то обычно рекомендуется применять так называемый метод наименьших квадратов.

МЕТОД НАИМЕНЬШИХ КВАДРАТОВ

Если система (1) несовместна, то есть равенство Ax = b не имеет места при любых значениях вектора x, то ставится задача отыскания таких значений неизвестных x1 , x2 , _, xn , при которых левые части уравнений системы (1) были бы возможно более близки к соответствующим правым частям. В качестве меры такой близости берется так называемое квадратичное уклонение левых частей уравнений от свободных членов, то есть величина

или, что то же самое, величина квадрата нормы разности правой и левой частей системы (1): || Ax - b || 2. Для решения данной задачи удобно использовать понятия и методы теории евклидовых пространств, изложенные в работе [2].

Рассмотрим m-мерное евклидово пространство и векторы

в этом пространстве. Требование минимальности квадрата нормы разности векторов Ax и b равносильно задаче о выборе чисел x1 , x2 , _, xn так, чтобы расстояние между векторами b и c = x1e1 + x2e2 + _ + xnen было наименьшим. Предполагая векторы e1 , e2 , _, en линейно-независимыми [2], рассмотрим подпространство m-мерного евклидова пространства, состоящее из линейных комбинаций этих векторов. Тогда задача состоит в нахождении ортогональной проекции вектора b на это подпространство. Числа x1 , x2 , _, xn , дающие решение этой вспомогательной задачи (или квазирешение исходной системы), находятся из системы

(e1 , e1)x1 + (e1 , e2)x2 + _ + (e1 , en)xn = (b, e1),

(e2 , e1)x1 + (e2 , e2)x2 + _ + (e2 , en)xn = (b, e2),

.....................................................................

(en , e1)x1 + (en , e2)x2 + _ + (en , en)xn = (b, en),

где

Определитель системы (2) называется определителем Грама для векторов e1 , e2 , _, en , он неравен нулю в случае линейной независимости этих векторов. Таким образом, задача о нахождении квазирешения несовместной системы (1) заменяется решением однозначно разрешимой (определенной) системы (2).

Пример 1. Рассмотрим систему трех уравнений с одним неизвестным:

2x = 3,

3x = 4,

5x = 7.

Для этой системы запишем векторы

Система (2) сведется к одному уравнению

(e, e)x = (b, e)

или

38x = 53.

Отсюда следует, что роль квазирешения играет величина 53/38.

Пример 2. Рассмотрим систему, состоящую из трех уравнений с двумя неизвестными:

x1 - x2 = 0,

x2 = 2,

x1 + x2 = 0.

Для этого примера получаем следующие выражения соответствующих векторов:

и, следовательно,

(e1 , e1) = 2, (e1 , e2) = 0, (e2 , e2) = 3,

(b, e1) = 0, (b, e2) = 2.

Таким образом, приходим к системе уравнений вида

2x1 = 0,

3x2 = 2,

то есть

Следует отметить, что условие линейной независимости векторов e1 , e2 , _, en , которые являются столбцами матрицы A, весьма ограничительно и заведомо не выполняется, когда количество неизвестных совпадает с количеством уравнений, то есть m = n, а det A = 0. В последнем случае обычно применяют метод регуляризации [3].

РЕГУЛЯРИЗАЦИЯ

Метод регуляризации состоит в замене матрицы A матрицей A + dE (E - единичная матрица), определитель которой неравен нулю и, следовательно, преобразованная система имеет единственное решение, которое и объявляется квазирешением исходной системы. Ясно, что такое квазирешение зависит от величины d.

Пример 3. Рассмотрим следующую систему двух уравнений с двумя неизвестными:

x1 + 2x2 = 1,

x1 + 2x2 = 2.

Соответствующая регуляризованная система имеет вид

(1 + d)x1 + 2x2 = 1,

x1 + (2 + d)x2 = 2.

Решение этой системы, имеющее вид

и зависящее от d, играет роль квазирешения исходной системы.

МЕТОД ОРТОГОНАЛЬНОГО ПРОЕКТИРОВАНИЯ

Здесь предлагается рассмотреть метод приближенного решения линейных систем вида (1), суть которого заключается в последовательном проектировании точек m-мерного евклидова пространства на гиперплоскости, описываемые уравнениями этой системы. Иногда этот метод называют методом Качмажа.

Сначала изложим этот метод на примере систем трех уравнений с двумя неизвестными. Рассмотрим систему уравнений вида

a11x1 + a12x2 = b1 ,

a21x1 + a22x2 = b2 ,

a31x1 + a32x2 = b3 .

Каждое уравнение этой системы задает прямую на плоскости переменных x1 , x2 . Приближенное решение строится следующим образом. В качестве первой точки выбирается любая точка на прямой L1 , задаваемой первым уравнением. Можно, например, взять любую точку на плоскости и спроектировать ее на эту прямую. Для определенности в качестве первой точки можно выбрать точку с координатами x1 = a11b1 / D1 , x2 = a12b1 / D1 , где которая получается в результате проектирования начала координат на прямую L1 . Напомним, что проекция точки с координатами на прямую, задаваемую уравнением

a1x1 + a2x2 = d,

имеет координаты

Вторая точка получается в результате проектирования первой точки на прямую L2 , задаваемую вторым уравнением системы, а третья - как результат проектирования второй точки на прямую L3 , которая задается третьим уравнением. Четвертая точка, как и первая, принадлежит первой прямой и получается в результате проектирования третьей точки на первую прямую. Пятая точка получается проектированием четвертой на L2 и т.д. Процесс продолжается до тех пор, пока расстояние между последовательными точками на одной прямой (L1 для определенности) не станет меньше некоторого наперед заданного числа.

Описанная выше процедура очевидным образом переносится на случай системы вида (1) с любым количеством уравнений и неизвестных. Отличие заключается только в том, что в общем случае каждое уравнение системы описывает не прямую, а так называемую гиперплоскость в пространстве переменных x1 , x2 , _, xn (плоскость для n = 1) и проектирование осуществляется на эту гиперплоскость (плоскость).

Важно отметить, что метод проектирования всегда сходится. Более того, для совместных систем последовательность точек, получающихся проектированием на гиперплоскости, сходится именно к решению (одному из решений) системы. Доказательство этого факта можно провести используя принцип сжатых отображений [4].

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

Нетрудно убедиться в том, что последовательные проекции сходятся к точке (0, 0) на первой прямой, к точке (0, 2) на второй прямой и к точке (-1, 1) на третьей прямой. Если в качестве квазирешения выбирается центр тяжести полученного треугольника, то соответствующие значения неизвестных имеют вид

Интересно отметить, что в случае, когда отрезки прямых, описываемых уравнениями системы, образуют равносторонний треугольник, последовательности проекций на каждой из прямых сходятся к точкам, которые являются вершинами равностороннего треугольника меньшего размера и делят стороны большего треугольника в отношении 1 : 2.

ЛИТЕРАТУРА

1. Ильин В.А., Позняк Э.Г. Линейная алгебра. М.: Наука, 1984. 294 с.

2. Ильин В.А. Базисы в евклидовых пространствах и ряды Фурье // Соросовский Образовательный Журнал. 1998. ╧ 4. С. 95-101.

3. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1979. 286 с.

4. Баскаков А.Г. Сжимающие отображения и решение нелинейных уравнений// Соросовский Образовательный Журнал. 1997. ╧ 5. С. 118-121.

Рецензент статьи Е.И. Моисеев

* * *

Владимир Андреевич Соболев, доктор физико-математических наук, профессор, зав. кафедрой дифференциальных уравнений и теории управления Самарского государственного университета, декан факультета математики и компьютерных наук Самарского муниципального университета Наяновой, академик РАЕН. Область научных интересов - дифференциальные уравнения, теоретическая механика, математическое моделирование, теория управления. Автор более 80 научных публикаций и четырех книг.