FN_Alg04 (Лекции 2009)

Московский государственный технический университетимени Н.Э. БауманаÌÃÒÓФакультет «Фундаментальные науки»Кафедра «Математическое моделирование»ÌÃÒÓÀ.Í. ÊàíàòíèêîâÈÇÁÐÀÍÍÛÅ ËÅÊÖÈÈÏÎ ÀËÃÅÁÐÅÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12Äëÿ ñòóäåíòîâ ôàêóëüòåòà ÔÍÌÃÒÓÊîíñïåêò ëåêöèéÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12Москва2009ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓРассмотрим систему Ax = b с матрицей A типа m × n. Здесь x и b обозначают матрицыстолбцы, которые мы будем рассматривать как элементы арифметических пространств Rn иRm соответственно. Мы будем полагать, что в этих линейных пространствах задано стандартное скалярное произведение (сумма попарных произведений компонент), так что мы имеем делос евлидовыми пространствами.

Длину вектора x в евклидовом пространстве будем обозначатьчерез |x| (т.е./ как абсолютную величину числа). Матричное произведение Ax мы, как правило, будем интерпретировать как матричную запись линейной комбинации столбцов a1 , . . . ,an матрицы A, коэффициентами которой являются компоненты вектор-столбца x, т.е.Ax = x1 a1 + x2 a2 + . . . + xn an .f (x1 , . . . , xn ) =nX2bi − (ai1 x1 + . . . + ain xn )i=11ÔÍ-12h∈HH.

Геометрически (в V2 ) вектор h, обеспечивающий минимум |b − h|, определяется основаниемперпендикуляра, опущенного из точки на плоскость или прямую, т.е. |b − h|2 имеет наименьшеезначение, когда b − h ⊥ H. Покажем, что это условие выполняется в общем случае. Разложимвектор b на ортогональную проекцию b0 на H и ортогональную b⊥ , т.е. представим в видеÌÃÒÓпринимает наименьшее значение. Такую задачу можно решать общими методами исследованияфункций многих переменных на экстремум. В данном случае, однако, решение можно получитьчисто геометрическими методами.Рассмотрим подпространство H = span(a1 , . . . , an ) ⊂ Rm — линейную оболочку столбцовматрицы A.

Это подпространство представляет собой множество всевозможных линейных комбинаций Ax столбцов матрицы A с вектором коэффициентов x. Решение системы Ax = b пометоду наименьших квадратов означает выбор вектора h ∈ H, для которого величина |b − h|принимает наименьшее значение, а также разложение этого вектора по системе столбцов a1 , . .

. ,an . Если система имеет решение, то b ∈ H. Иначе b ∈/ H.Величина min |b − h| называется расстоянием от вектора b до подпространстваÔÍ-12Выбрав вектор x, мы для выражения b − Ax получим значение, которое равно нулю, есливыбранный вектор есть решение системы. В общем случае величина |b − Ax| характеризует,насколько вектор неизвестных x близок к решению системы. Компоненты вектора b − Ax называют невязками уравнений системы.

Сам вектор мы будем называть вектором невязок,а его длину — нормой невязки.Если система несовместна, то в качестве решения можно выбрать такой вектор x, что величина |b − Ax|2 примет наименьшее значение. Квадрат нормы в данном случае выбран потому,что он без радикала выражается через скалярное произведение. Описанныq подход к решениюсистемы линейных уравнений называют методом наименьших квадратов.Задача поиска решения несовместной системы по методу наименьших квадратов по своемуклассу относится к задачам оптимизации: речь идет о поиске таких значений неизвестных xi ,при которых функцияÌÃÒÓÔÍ-12ÌÃÒÓ4.1. Метод наименьших квадратовÔÍ-12ÔÍ-124. ПСЕВДОРЕШЕНИЯИ ПСЕВДООБРАТНАЯ МАТРИЦАÌÃÒÓÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓ2b = b0 + b⊥ , где b0 ∈ H, b⊥ ∈ H ⊥ .

Тогда по теореме Пифагора|b − h|2 = |b0 + b⊥ − h|2 = |(b0 − h) + b⊥ |2 = |b0 − h|2 + |b⊥ |2 .ÌÃÒÓОтсюда следует, что |b−h|2 принимает минимальное значение тогда, когда b0 −h = 0, т.е. векторh совпадает с проекцией вектора b на подпространство H. В этом случае b − h = b⊥ ⊥ H. Самоминимальное значение совпадает с длиной ортогональной составляющей вектора b.ÌÃÒÓТеорема 4.1. Следующие условия эквивалентны:1) величина |b − Ax| минимальна для данного вектора x ∈ Rm ;2) вектор x является решением системы Ax = прH b;тт3) вектор x является решением системы A Ax = A b.J Согласно проведенным рассуждениям величина |b − Ax| минимальна тогда и только тогда,когда вектор h = Ax является проекцией прH b вектора b на H. Это будет в том случае, когдавектор x ∈ Rm является решением системы Ax = прH b.

Тем самым доказана эквивалентностьпервых двух из трех условий.Условие Ax = прH b означает, что вектор b − Ax принадлежит H ⊥ . Это равносильно ортогональности вектора b − Ax каждому вектору aj , j = 1, n. Записав в матричном виде условияттолртогональности, получим aj (b − Ax) = 0, j = 1, n, или A (b − Ax) = 0. Последнеее равенствотÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-124. ПСЕВДОРЕШЕНИЯИ ПСЕВДООБРАТНАЯÌÃÒÓМАТРИЦАттИз доказанной теоремы вытекает ряд следствий:т1. Системы Ax = 0 и A Ax = 0 имеют одно и то же множество решений.т2.

rang A A = rang A.т3. Матрица A A невырождена тогда и только тогда, когда столбцы матрицы A линейнонезависимы.4. Система векторов a1 , a2 , . . . , ak в евклидовом пространстве L линейно независима тогдаи только тогда, когда матрица Грама этой системы невырождена.тт5. Система A Ax = A b всегда совместна; она является определенной тогда и только тогда,когда столбцы матрицы A линейно независимы.Первое из сформулированных утверждений вытекает из того, что системы Ax = прH b итA Ax = A b имеют одно и то же множество решений (следовательно, и соответствующие однородные ситстемы имеют одно и то же множество решений). Впрочем, это можно доказать инепосредственно (доказательство, представленное в учебнике). Третье следствие представляетсобой частный случай второго следствия, когда системы имеют единственное решение.

Однородная система имеет единственное решение в том и только в том случае, когда ранг матрицысистемы совпадает с количеством неизвестных (количеством столбцов матрицы). Для квадраттной матрицы A A это равносильно невырожденности. Ну, и вообще равенство ранга матрицыколичеству ее столбцов равносильно тому, что ее столбцы линейно независимы. Из третьегоследствия вытекает пятое.Чтобы обосновать четвертое следствие, достаточно записать координаты векторов в некотором ортонормированном базисе и составить из них матрицу A. Линейная независимостьсистемы векторов равносильна линейной независимости столбцов матрицы A, что в силу следтствия 3 равносильно невырожденности матрицы A A.

Но эта матрица и есть матрица Грамасистемы векторов.ÔÍ-12ÔÍ-12тЗамечание. Матрица A A представляет собой матрицу скалярных произведений ai ajстолбцов aj , j = 1, n, матрицы A, называемую матрицей Грама системы векторов a1 , . . . , an .ÌÃÒÓÌÃÒÓэквивалентно равенству A b = A Ax, т.е. третьему условию в формулировке теоремы. IÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓтÌÃÒÓТеорема 4.3. Пусть xj — псевдорешения СЛАУ Ax = bj , j = 1, l. Тогда псевдорешениемСЛАУ Ax = b, где b = λ1 b1 + . . . + λl bl , является вектор x = λ1 x1 + . . . + λl xl .ÔÍ-12Этот путь приведет к решению, но не всегда самый короткий. Можно указать другие способырешения.Для псевдорешений сохраняются некоторые свойства обычных решений СЛАУ.ÌÃÒÓКак найти нормальное псевдорешение? Можно поступить таким образом: записать норттмальную СЛАУ A Ax = A b и добавить условие x ∈ K ⊥ , означающее, что (x, fj ) = 0, j = 1, k,где система векторов {fj } — фундаментальная система решений (ФСР) однородной СЛАУтAx = 0.

Последнее условие представляет собой систему линейных уравнений F x = 0, гдеF — матрица, составленная из вектор-столбцов fj , j = 1, k. В результате получим системууравнений(! т тттA Ax = A b,A AA bилиx=.тт0F x = 0,FÔÍ-12J Множество псевдорешений СЛАУ Ax = b — это множество решений нормальной СЛАУттA Ax = A b, которое можно представить в виде x = xч + x0 , где xч — частное решение нортмальной СЛАУ, а x0 — общее решение однородной СЛАУ A Ax = 0, совпадающее с общимрешением СЛАУ Ax = 0. Нормальное псевдорешение определяется таким вектором x0 , прикотором норма |xч + x0 | имеет минимальное значение. Из метода наименьших квадратов вытекает, что наименьшее значение норма |xч + x0 | принимает, когда вектор xч + x0 ортогоналенподпространству K ⊂ Rm решений СЛАУ Ax = 0. Значит, единственный вектор вида xч + x0 ,x0 ∈ K, имеющий минимальную норму, является ортогональной составляющей x∗ вектора xчпри его проектировании на K.

Это доказывает, что нормальное псевдорешение существует иединственно, причем x∗ ∈ K ⊥ может быть получен как ортогональная проекция на K ⊥ любогопсевдорешения системы Ax = b.Систему Ax = 0 можно интерпретировать как систему (si , x) = 0, i = 1, m, означающую,что K есть ортогональное дополнение к линейной оболочке системы {si }. Но тогда K ⊥ =span(si ), а вектор x∗ ∈ K ⊥ представим в виде линейной комбинации векторов si — столбцовтматрицы A . IÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Теорема 4.2. Любая СЛАУ имеет нормальное псевдорешение, и притом единственное.

Нормальное псевдорешение СЛАУ Ax = b есть решение нормальной СЛАУ, являющееся линейнойткомбинацией столбцов матрицы A .ÌÃÒÓÌÃÒÓЛюбой столбец x, обеспечивающий минимальное значение нормы |b − Ax| вектора невязки,называется псевдорешением системы Ax = b. Если система совместна, то минимальноезначение нормы вектора невязки достигается на любом решении и равно нулю.

В этом случаепсевдорешения системы представляют собой решения системы.Чтобы найти псевдорешения системы Ax = b, необходимо, согласно теореме 4.1 составитьттсистему A Ax = A b, называемую нормальной системой, и найти все ее решения. Отметим, что система Ax = b имеет единственное псевдорешение тогда и только тогда, когда уматрицы A столбцы линейно независимы или, иначе, ранг матрицы A равен количеству екестолбцов.Если система Ax = b имеет много псевдорешений, среди них выделяют то, которое имеетминимальную норму. Такое решение единственно и называется нормальным псевдорешением.