FN_Alg04 (1172022)
Текст из файла
Московский государственный технический университетимени Н.Э. БауманаÌÃÒÓФакультет «Фундаментальные науки»Кафедра «Математическое моделирование»ÌÃÒÓÀ.Í. ÊàíàòíèêîâÈÇÁÐÀÍÍÛÅ ËÅÊÖÈÈÏÎ ÀËÃÅÁÐÅÔÍ-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 имеет много псевдорешений, среди них выделяют то, которое имеетминимальную норму. Такое решение единственно и называется нормальным псевдорешением.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
