Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow Линейная алгебра: теория и прикладные аспекты

Решение систем линейных уравнений методом наименьших квадратов

Пусть дана действительная или комплексная система линейных уравнений

в матричной форме имеющая вид

Если система (8.70) описывает реальный физический процесс, но оказывается несовместной, то естественно ввести коррективы в математическую модель и, в частности, изменить трактовку понятия "решение". Например, часто возникает задача найти такие значения неизвестных ад, Х2, ..., хп, при которых функция

где х = (ад, ад,..., хп)т, принимает наименьшее значение. Этот подход к понятию решения линейной системы составляет суть метода наименьших квадратов. При этом найденный набор значений х = (ад, ад, ??.,хп)Т называют псевдорешением или обобщенным решением системы. Очевидно, что если система Ах = b совместна, то ее псевдорешение представляет собой обычное решение, а любое решение системы можно искать как ее псевдорешение.

Описанный подход к понятию решения линейной системы объясняется следующими соображениями. Пусть некоторый процесс описывается некоторым набором величин од, <22, ..., ап, Ь, причем из эмпирических исследование известно, что параметр Ъ является линейной функцией от величин ад, ад, ..., хп, т.е.

Стремясь определить коэффициенты ад, Х2, • .., хп этой зависимости, исследователи проводят ряд экспериментов, в результате которых измеряют в разных ситуациях значения величин од, ад, ..., ап, 6, а затем составляют следующую таблицу наблюдений (табл. 8.1).

Таблица 8.1

Номер

эксперимента

Результаты измерений

а 1

«2

«п

6

  • 1
  • 2

т

«п

«21

«ml

«12

«22

«m2

«1п

«2п

«тп

^2

От

Подставив данные каждого наблюдения в рассматриваемую линейную функцию, заключаем, что неизвестные коэффициенты ад, ад,

..., хп являются решением системы линейных уравнений

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

С аналогичной проблемой встречаемся при отыскании коэффициентов функции

аппроксимирующей функцию /(?), заданную таблично, а также при приближении функции на отрезке тригонометрическими многочленами и полиномами Лежандра.

Система может иметь неединственное псевдорешение. Среди всех псевдорешений системы нормальным псевдорешением называют то, которое имеет наименьшую длину. На таком псевдорешении функция

принимает наименьшее значение. Этим свойством нормального псевдорешения обычно пользуются при его выделении из общего псевдорешения системы Ах = Ь. Другой способ выделения нормального псевдорешения системы Ах = Ь из общего псевдорешения основан на его свойстве ортогональности (см. следствие 8.10) к каждому решению однородной системы Ах = 0, в частности, к каждому решению, входящему в ФСР этой однородной системы.

Исходя из определения псевдорешений, укажем способ их нахождения. Для этого замечаем, что левая часть г-го уравнения системы (8.70) при любом наборе значений Х2, ..., хп отличается от его правой части на некоторую невязку. Поэтому вместо системы (8.70) будем рассматривать систему

в матричной записи имеющую вид А х + z = Ъ.

Для того чтобы функция F(x) = Ах Ь2 имела наименьшее значение, длина вектора z должна быть минимальной. Это возможно, лишь когда в равенстве Ах + z = Ъ вектор Ах = А х + А^ Х2 +...+ пхп является ортогональной проекцией (см. разд. 8.5) вектора b на пространство Ь(А) столбцов А, А2, ..., Ап матрицы А, а вектор z — ортогональной составляющей вектора Ъ. Поэтому вектор 2 должен быть ортогональным к каждому вектору-столбцу Aj матрицы А. Следовательно, (2, А,) = 0, j = 1, 2,..., п. В матричной форме это означает, что A* z = 0. Отсюда, умножив равенство А х + z = b слева на матрицу А*, получим систему

В действительном (вещественном) случае к системе (8.73) можно прийти также используя методы математического анализа, а именно, приравняв к нулю дифференциал

функции

или, что то же самое, приравняв к нулю первые частные производные ПО Х, Х2, ..., хп функции F{x).

Примечание. При вычислении дифференциала dF(x) использовано то обстоятельство, что вещественное выражение (Axb)* A dx, являясь матрицей первого порядка, не меняется при транспонировании и комплексном сопряжении и потому совпадает с выражением dx* А* хЬ).

Систему А* Ах = А* b называют системой нормальных уравнений. Ее матрица А* А квадратная п-го порядка. Это матрица Грама системы столбцов матрицы А.

Теорема 8.40. Система А* Ах = А* b всегда совместна, причем ее решения, и только они, являются псевдорешениями системы Ах = Ь.

О Сначала убедимся в совместности системы нормальных уравнений. Для этого докажем, что вектор .то = А+ Ъ, где А+ — псев- дообратная к А матрица, является решением этой системы. С этой целью возьмем какое-нибудь скелетное разложение А = В С матрицы А. Тогда А* = С* В*, Л+ = С* (СС*)-1 (В* Б)"1 В* и

Следовательно, Хо = А+ b — решение системы нормальных уравнений, а эта система совместная.

В совместности системы нормальных уравнений можно убедиться и следующим образом. Представим столбец b в виде Ь = Ь{] + /Д, где

А-, — столбцы матрицы А, Ь1- — ортогональная составляющая вектора Ъ. Тогда

Таким образом, система нормальных уравнений равносильна системе А* Ах = А* Ьо, а последняя всегда совместная, поскольку при х = (ki,k2, ...,kn)T

Перейдем к доказательству второй части утверждения теоремы. Пусть х — решение системы нормальных уравнений А* Ах = А* Ь. Эта система равносильна системе А* (А х — Ь) = 0, означающей, что каждый столбец матрицы А ортогонален столбцу г = Ах—b. Следовательно, столбец А х является проекцией вектора b на подпространство Ь(А), порожденное столбцами матрицы А, а вектор х есть псевдорешение системы Ах = Ь.

Эти рассуждения можно провести и в обратном порядке (см. вывод системы нормальных уравнений). Тогда придем к заключению, что псевдорешения системы Ах = b являются решениями системы нормальных уравнений. ?

Следствис8.6. Общее псевдорешение системы Ах = b представимо в виде

где .то — какое-либо частное решение системы А* Ах — А* 6, т.е. какое- либо частное псевдорешение системы А х = 6, а т0бЩ — общее решение однородной системы А* А х = 0.

Следствие 8.7. Система А* Ах = А* b имеет единственное решение, если столбцы матрицы А линейно независимы, и бесконечное множество решений, если столбцы матрицы А линейно зависимы.

О Определитель системы А* Ах = А* b есть определитель матрицы Грама системы столбцов матрицы А. Этот определитель отличен от нуля тогда и только тогда, когда столбцы матрицы А линейно независимы. В то же время это условие означает, что система А* Ах = А* b имеет единственное решение. ?

Еще и еще раз подчеркнем, что решения х системы А* Ах = А* b нормальных уравнений, и только они, являются псевдорешениями системы Ах = Ь. Причем, при таких х, и только при них, вектор Ах = Ах 1 + А2Х2 + ... + Апхп является (см. раздел 8.5) ортогональной проекцией вектора b на подпространство Ь(А), порожденное столбцами А, А2, ..., Ап матрицы А, а вектор z = Ах — b — ортогональной составляющей вектора Ъ.

Итак, чтобы решить систему Ах = b методом наименьших квадратов, нужно найти общее решение системы А* Ах = А* b и, если требуется, из множества решений выделить нормальное решение, т.е. то, которое имеет наименьшую длину.

Пример 8.36. Для системы

найти общее и нормальное псевдорешения.

Решение. Составим систему А* Ах — А* Ъ нормальных уравнений, которая в данном случае имеет вид:

Решив эту систему, найдем общее псевдорешение Теперь составим функцию

Из равенства нулю ее производной по Х найдем ж 4 = 1, при котором из общего псевдорешения х получается нормальное псевдорешение х° = (3, —5, 3,1)т.

Если для выделения нормального псевдорешения применить второй способ, то сначала нужно построить какую-либо ФСР однородной системы Ах = 0. В данном случае ФСР состоят из одного решения. Одна из этих ФСР состоит из решения X = ( — 1, —1, —1,1)т. Далее из соотношения ортогональности

векторов X и х найдем значение Х4 = 1, при котором из общего псевдорешения х выделяется нормальное псевдорешение х° = (3, —5,3,

i)T ?

Пример 8.37. Найти многочлен p(t) = х + X2t--x^t2, с наименьшей квадратичной погрешностью приближающий функцию /(?), которая задана таблицей

t

-2

-1

1

2

m

-5,5

0,5

3,5

3,0

Решение. Подставляя в p(t) данные из таблицы, придем к системе

Записанная система несовместная. Поэтому будем решать ее методом наименьших квадратов. Система А* Ах = А* Ь нормальных уравнений в данном случае имеет вид:

Решив систему, получим

Поэтому искомый многочлен p(t) имеет вид:

Пример 8.38. Найти нормальное псевдорешение системы Ах = 6, если

Решение. Следуя общему правилу, составим систему А* Ах = = А* Ъ нормальных уравнений, которая в данном случае имеет вид:

Решив эту систему, получим общее псевдорешение

данной системы Ах = Ь. Чтобы из него выделить нормальное псевдорешение ж° первым способом, представим Жз в виде Жз = а + Ы. Тогда х0бщ и ж*бщ будут иметь вид

Поэтому функция Ф(жобщ) имеет выражение

Из равенств нулю производных

найдем а = 12/9, 6 = 2/9. Следовательно, х3 = а + 6 г = 12 g г.

При таком значении х3 из общего псевдорешения выделяется нормальное псевдорешение

Если для выделения нормального псевдорешения х° из общего псевдорешения т0бщ применить второй способ, то сначала нужно построить какую-либо ФСР однородной системы Ах = 0. В данном случае ФСР состоят из одного решения. Одной их них является ФСР, состоящая из решения х = ( —1, — 1,1)т. Далее из соотношения ортогональности

векторов х0бщ и х найдем значение х3 = 12+, при котором из .т0бщ выделяется х°. ?

Лемма 8.5. Однородные системы Ах = 0 и А* Ах = 0 эквивалентны.

> Если А х = 0, то А* А х = А* ? 0 = 0, т.е. все решения системы Ах = 0 являются и решениями системы А* Ах = 0. Предположим, что столбец х является решением системы А* Ах = 0. Тогда х* А* А х = х* ? 0 = 0. Но

Таким образом, из равенства А* Ах = 0 вытекает, что столбец Ах имеет нулевую длину, а значит, он равен нулю, т.е. Ах = 0. ?

Следствие 8.8. Общее псевдорешение системы Ах = b представимо в виде

где xq — какое-либо частное псевдорешение системы Ах = Ь, т0бщ — общее решение однородной системы Ах = 0.

О Это утверждение непосредственно вытекает из теоремы 8.40, следствия 8.С и леммы 8.5. ?

В последнее время в теории и практике решения систем линейных уравнений методом наименьших квадратов широкое применение находят псевдообратные матрицы. Обсудим это положение подробнее.

Лемма 8.6. Общее решение однородной системы Ах = 0 с (т х п) -матрицей А представило в виде

где Е — единичная матрица п-го порядка, с = (ci,C2,..., сп)Т — вектор произвольных постоянных.

> При любом векторе с столбец А+ А) с является решением системы А х = 0, поскольку

В то же время любое решение то системы Ах = 0 можно представить в виде .то = (Е — А+ А) то, так как

Это значит, что формула (8.75) содержит все решения системы Ах — = 0. ?

Следствие 8.9. Общее решение системы А* Ах = 0 представимо в виде (8.75).

Теорема 8.41Общее псевдорешение системы Ах = b с (тх п)-матрицей А представимо в виде

где с = (ci,c2,...,cn)Tвектор произвольных постоянных.

> Для доказательства этой теоремы замечаем, что в формуле (8.74) за .то можно взять столбец А+ Ъ, поскольку он является одним из частных псевдорешений системы Ах = b (см. доказательство теоремы 8.40), а за т0бщ — выражение из формулы (8.75). ?

Теорема 8.42. Нормальное псевдорешение системы Ах = b представимо в виде

О Известно (см. доказательство теоремы 8.40), что х° = А+ b является псевдорешением системы Ах = Ь. Пусть т — произвольное псевдорешение этой системы. В силу соотношения (8.74) это псевдорешение можно представить в виде т = х° + 2, где т° = А+ buz — произвольное решение системы Ах = 0. Тогда

Поскольку столбец 2 является решением системы Ах = 0, а псевдо- обратная матрица А+ представима в виде А+ = А* V, то

При этом и Значит

и наименьшее значение модуля псевдорешения х = х° + г достигается при 2 = 0, т.е. х° = А+ b и есть нормальное псевдорешение системы Ах = Ь. ?

Следствие 8.10. Нормальное псевдорешение системы Ах = Ъ ортогонально к каждому решению системы Ах = 0.

О Это утверждение следует из полученного в ходе доказательства теоремы 8.42 равенства z* х° = {x°,z) = 0 при любом решении 2 системы Ах = 0. ?

Формула (8.77) является естественным обобщением формула х = = Л-1 6, представляющей решение системы Ах = b с квадратной невырожденной матрицей А.

Пример 8.39. Вернемся к системе из примера 8.36. Для матрицы

этой системы в примере 8.33 найдена псевдообратная матрица

По формуле (8.77) находим нормальное псевдорешение

Вычислив

затем по формуле (8.76) получаем общее псевдорешение

Видно, что в найденном представлении общего псевдорешения произвольные постоянные связаны друг с другом. Положив 7 = Х4 = = 1 — (ci + С2 + сз — С4), придем к представлению общего псевдорешения, как и в примере 8.3С, в виде

Псевдообратная матрица А+ к матрице А позволяет найти нормальное псевдорешение системы Ах = Ь по формуле х° = А+ Ъ. В то же время имеет место следующее утверждение.

Псевдообратная матрица А+ к (тХп)-матрице А является нормальным псевдорешением матричного уравнения А X = Е, где Еединичная матрица т-го порядка.

> Отыскание нормального псевдорешения Х° матричного уравнения АХ = Е равносильно нахождению нормальных псевдорешений XI, Х%, ..., Х°п систем

где Xj — j-й столбец матрицы X, Ej — j-й столбец единичной матрицы Е т-го порядка.

Для каждой из этих систем по формуле (8.77) соответственно получаем

Эти соотношения равносильны формуле

которое доказывает рассматриваемое утверждение. ?

Пользуясь доказанным утверждением, найдем псевдообратную матрицу А+ к матрице

Для этого следует найти нормальные псевдорешения систем А Х = = Ei, АХ2 = Е‘2, АХз = Е3, АХ4 = Е4, где Х4, Х2, Х3, Х4 столбцы искомой матрицы А+, Е, Е2, Е3, Е4 — столбцы единичной матрицы Е четвертого порядка.

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

выпишем системы нормальных уравнений А* АХ = А* Е, А* АХ-2 = = А* Е2, А* А Х3 = А* Е3, А* А Х4 = А* Е4, т.е. системы

найдем их общие решения и выделим из них нормальные решения. Общее решение первой из этих систем

Чтобы из него выделить нормальное решение Xf, составим функцию

найдем ее производную по х3 и приравняем ее к нулю. Тогда придем к уравнению

из которого находим х3 = 1/3. При таком значении жз из общего решения Х выделяется нормальное решение

Таким же способом находим нормальные решения

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

Формулу х° = Л+ b с помощью сингулярного разложения А = = QT, Р* матрицы Лис учетом теоремы 8.38 можно преобразовать следующим образом:

где ei, б2, еп — столбцы матрицы Р, /1, /2, /ш — столбцы матрицы Q, а, 2, аг — ненулевые сингулярные числа матрицы А.

Поскольку из соотношений (8.51) при г = 1, 2, г вытекают соотношения

то

где

Аналогично, вследствие того, что из соотношений (8.52) при i = = 1, 2, ..., г вытекают соотношения

то

где

Поэтому из разложения (8.78) получаем представления

где

и

где

Столбцы er_|_i, ег+2, •••? еп матрицы Р в сингулярном разлоэюении А = QSP*, соответствующие нулевым сингулярным числам матрицы А, составляют фундаментальную систему решений системы уравнений Ах — 0.

Действительно, эти столбцы линейно независимы, а их количество равно п — г, где г — ранг матрицы А, равный общему числу ненулевых сингулярных чисел. Кроме того, каждый из этих столбцов является решением системы А х = 0, поскольку при j = r+1, г+2,..., п

Поэтому общее псевдорешение системы Ах = Ъ молено записать в виде

или

где первые г коэффициентов имеют фиксированные значения, определенные формулами (8.80), а остальные принимают произвольные значения.

Формула (8.82) удобна для получения проекций псевдорешений па подпространства, порожденные правыми сингулярными векторами е, е-2- ..., еп матрицы А. Проекции на подпространство, порожденное векторами е, в2, ..., ед, при к ^ г можно также получить из соотношения (8.79) или, что то же самое, из системы

Пример 8.40. Найти проекции х^к к = 1, 2, 3, 4, псевдорешений системы

на подпространства, порожденные правыми сингулярными векторами матрицы системы.

Решени е. Для матрицы данной системы в примере 8.2С найдены сингулярные числа оу = 2, ад = яд = 1, (74 = 0 и правые сингулярные векторы

В соответствии с формулами (8.80) находим

a CI4 — произвольное постоянное. Далее, по формуле (8.82) получаем:

Эти результаты можно получить с помощью формулы (8.83), используя найденное в примере 8.26 сингулярное разложение:

Отыскание нормального решения произвольной системы моэюно свести к решению одной или двух систем с невы- роснсденными матрицами. Действительно, если дана совместная или несовместная система В х = b с х п)-матрицей В ранга г = п, то, домножая ее на матрицу В* слева, придем к системе В* В х = В* b с невырожденной матрицей В* В ранга п. Решая эту систему, получим: х = (В* В)-1 В* b = В+ Ь = х°.

Если дана система С х = b с х п)-матрицей С ранга г = га, то х будем искать в виде х = С* z. Тогда придем к системе С С* z = = b с невырожденной матрицей С С* ранга га. Поэтому х = С* z = = С* (СС*)-1Ь = С+Ь = .х°.

Пусть, наконец, дана совместная или несовместная система Ах = = 6 с х п)-матрицей А ранга г ^ min(m, п). Матрицу А представим скелетным разложением А = В С с х п)-матрицей В ранга г и (г х п)-матрицсй С ранга г. Тогда система Ах = b примет вид В Сх = = Ь. Полагая у = Сх, придем к системе By — b, которая по только что рассмотренному первому случаю дает у = С х = В+ Ъ. Отсюда по второму случаю получаем

Из приведенных рассуждений видно, что этот способ равносилен применению формулы х° = А+ b для отыскания нормального решения системы. Кроме того, отсюда становится понятной формула (8.С7).

Пример 8.41. Найти нормальное решение системы

путем сведения ее к решению систем с невырожденными матрицами.

Решение. В примере 4.5 для матрицы А рассматриваемой системы было найдено скелетное разложение

Используя это разложение, данную систему перепишем в виде Полагая

где у = {yi,yi)T, придем к системе

Здесь имеем первый из рассмотренных выше случаев. Поэтому полученную систему домножаем слева на матрицу

В результате придем к системе

Эта система имеет невырожденную матрицу’, а, следовательно, единственное решение. Находим это решение:

Теперь найденный столбец у = (1, 1)т подставим в систему Сх = у. Получим систему

Здесь имеем второй из рассмотренных выше случаев. Поэтому будем искать столбец X = (яд, яд, х%)т в виде

В результате придем к системе

или, после перемножения матриц в левой части, — к системе

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

Поэтому

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы