1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 65
Текст из файла (страница 65)
Численные методы линейной алгебрыПусть задан сходящийся стационарный одношаговый итерационныйметодx(k+1) ← Cx(k) + d,k = 0, 1, 2, . . . ,в котором kCk < 1 для некоторой матричной нормы. Ясно, что ввидурезультатов §3.9б о связи спектрального радиуса и матричных нормпоследнее допущение не ограничивает общности нашего рассмотрения.Как оценить отклонение по норме очередного приближения x(k) от предела x⋆ := limk→∞ x(k) , не зная самого этого предела и наблюдая лишьза итерационной последовательностью x(0) , x(1) , . .
. , x(k) , . . . ?Как и прежде, имеемx(k) = Cx(k−1) + d,x⋆ = Cx⋆ + d.Вычитание второго равенства из первого даётx(k) − x⋆ = C x(k−1) − x⋆ .(3.137)Перенесём x(k) в правую часть этого соотношения, а затем добавим кобеим частям по x(k−1) :x(k−1) − x⋆ = x(k−1) − x(k) + C x(k−1) − x⋆ .Возьмём теперь от обеих частей полученного равенства векторную норму, которая согласована с используемой матричной нормой для C. Применяя затем неравенство треугольника, приходим к оценке (k−1)x− x⋆ ≤ x(k) − x(k−1) + kCk · x(k−1) − x⋆ ,Перенесение в левую часть второго слагаемого из правой части и последующее деление обеих частей неравенства на положительную величину(1 − kCk) даёт (k−1)x− x⋆ ≤ (k)1x − x(k−1) .1 − kCkС другой стороны, вспомним, что из (3.137) следует (k)x − x⋆ ≤ kCk · x(k−1) − x⋆ .(3.138)3.14. Оценка погрешности приближённого решения399Подставляя сюда вместо kx(k−1) − x⋆ k оценку сверху (3.138), получаемокончательно (k)kCk x − x⋆ ≤x(k) − x(k−1) .(3.139)1 − kCkВыведенная оценка может быть использована на практике как дляоценки погрешности какого-то приближения из итерационной последовательности, так и для определения момента окончания итераций, т.
е.того, достигнута ли желаемая точность приближения к решению илинет.Пример 3.14.1 Рассмотрим систему линейных алгебраических уравнений 02 1,x=53 4точное решение которой равно (−1, 2)⊤ . Пусть для решения этой системы организован итерационный метод Гаусса-Зейделя с начальнымприближением x(0) = (0, 0)⊤ .
Через сколько итераций компоненты очередного приближения к решению станут отличаться от точного решения не более, чем на 10−3 ?Исследуемый нами вопрос требует чебышёвской нормы k·k∞ для измерения отклонения векторов друг от друга, и соответствующая подчинённая матричная норма задаётся выражением из Предложения 3.3.6.Матрица оператора перехода итерационного метода Гаусса-Зейделя согласно (3.109) есть −1 0 −0.50 12 0,=−0 0.3750 03 4так что её ∞-норма равна 0.5.
Следовательно, в оценке (3.139) имеемkCk0.5== 1,1 − kCk1 − 0.5и потому должно быть справедливым неравенство (k)x − x⋆ ≤ x(k) − x(k−1) .∞∞(3.140)Оно показывает, что компоненты очередного приближения отличаютсяот компонент точного решения не более, чем компоненты приближенийдруг от друга.4003. Численные методы линейной алгебрыЗапустив итерации Гаусса-Зейделя, мы можем видеть, чтоx(0) = (0, 0)⊤ ,x(1) = (0, 1.25)⊤ ,x(2) = (−0.625, 1.71875)⊤,······x(8) = (−0.998957, 1.999218)⊤,x(9) = (−0.999609, 1.999707)⊤,т. е. 9-я итерация отличается от предыдущей 8-й меньше чем на 10−3 , ипотому согласно оценке (3.140) на этой итерации мы получаем требуемую погрешность. То, что она действительно такова, можно убедитьсяиз сравнения x(9) с известным нам точным решением (−1, 2)⊤ .Как хорошо видно из примера, практическая реализация методики оценки погрешности итерационного решения может столкнуться сдвумя трудностями.
Во-первых, непростым является определение матрицы C (которая может и не задаваться в явном виде). Во-вторых,выбор нормы k · k, в которой kCk < 1, также может быть неочевидным.Теоретически такая норма должна существовать, если итерационныйпроцесс сходится из любого начального приближения, но её конкретный выбор в общем случае непрост.3.15Линейная задачанаименьших квадратовДля заданных m × n-матрицы A и m-вектора b линейной задачейнаименьших квадратов называют задачу отыскания такого вектора x,который доставляет минимум квадратичной форме hAx − b, Ax − b i,или, что равносильно, квадрату евклидовой нормы невязки kAx − bk22 .Ясно, что для матриц A полного ранга в случае m ≤ n, когда число строк матрицы не превосходит числа столбцов, искомый минимум,как правило, равен нулю. Для квадратной матрицы A линейная задачао наименьших квадратах, фактически, равносильна решению системылинейных алгебраических уравнений Ax = b и несёт особую специфику лишь когда A имеет неполный ранг, т.
е. особенна. Теоретически ипрактически наиболее важный случай линейной задачи о наименьших3.15. Линейная задача наименьших квадратов401квадратах соответствует m ≥ n. Он находит многочисленные и разнообразные применения при обработке данных.Рассмотрим в качестве примера задачу идентификации параметров системы, называемую также задачей восстановления зависимостей.Предположим, что имеется объект, на вход которому подаются воздействия, описываемые вектором a = (a1 , a2 , . .
. , an ) ∈ Rn , а на выходеимеем величину b ∈ R. Зависимость «вход-выход» является линейной,имеющей видb = a1 x1 + a2 x2 + . . . + an xn(3.141)с некоторыми постоянными вещественными коэффициентами x1 , x2 ,. . . , xn . Задача идентификации (называемая также задачей восстановления зависимостей) — это задача определения (оценивания) значенийxk на основе данных о входе и выходе объекта, т. е. по ряду соответствующих друг другу значений (a1 , a2 , . .
. , an ) и b.Каждое наблюдение (измерение) входов и выходов объекта порождает соотношение, которое связывает искомые xk . Если серия наблюдений входа-выхода объекта является «достаточно представительной»,то можно попытаться решить получающуюся систему уравнений относительно неизвестных xk и найти их значения. Восстанавливаемуюфункциональную зависимость (3.141) обычно называют регрессией величины b по величинам a1 , a2 , . .
. , an , а её график — регрессионнойлинией b по a1 , a2 , . . . , an .Для удобства выкладок условимся обозначать результат i-го измерения входов такого объекта через ( ai1 , ai2 , . . . , ain ), а выхода — черезbi , i = 1, 2, . . . , m. Тогда решение задачи идентификации — это вектор x = ( x1 , x2 , . . . , xn )⊤ , который удовлетворяет всем соотношениямвида (3.141), получающимся в результате отдельных наблюдений. Иными словами, результат идентификации x = ( x1 , x2 , . .
. , xn )⊤ являетсярешением системы уравненийa11 x1 + a12 x2 + . . . + a1n xn = b1 , a21 x1 + a22 x2 + . . . + a2n xn = b2 ,(3.142)...............am1 x1 + am2 x2 + . . . + amn xn = bm ,где m — общее количество измерений (наблюдений).На практике описанная выше ясная и стройная схема почти не работает, так как система уравнений (3.142), как правило, решений не4023.
Численные методы линейной алгебрыимеет. Это вызвано тем, что данные измерений (наблюдений) содержатслучайные ошибки, которые делают невозможными точные равенства(3.141). Дополнительно неразрешимости системы (3.142) обычно способствует её переопределённость: измерений стремятся получить какможно больше, и уж заведомо не меньше количества неизвестных параметров, подлежащих определению. Кроме того, назначая избранныйвид зависимости между входными и выходными переменными, мы также можем совершать идеализацию, желая, к примеру, выявить только«главную часть» функциональной зависимости, которая связывает b иa1 , a2 , . .
. , an . Как следствие, для системы (3.142) мы должны искатьрешение в каком-то обобщённом смысле. Чаще всего в качестве такого решения ищут точку (или точки), минимизирующие норму невязкисистемы (3.142), т. е. разности между её правой и левой частями. В случае, когда рассматривается евклидова норма невязки, мы приходим клинейной задаче наименьших квадратов.Пусть e — вектор единичной длины, kek2 = 1. Найдём производнуюфункции Φ(x) = kAx−bk22 в точке x по направлению e.
По определению∂ Φ(x)hA(x + te) − b, A(x + te) − b i − hAx − b, Ax − b i= limt→0∂et= limt→0hA(te), Ax − b i + hAx − b, A(te) i + hA(te), A(te) it2t hA⊤ (Ax − b), e i + t2 hAe, Aeit→0t= limt2 hAe, Aei2t hA⊤ (Ax − b), e i+ limt→0t→0tt= lim= 2 hA⊤Ax − A⊤ b, e i.В точке минимума производная функции по любому направлению равна нулю, так что hA⊤Ax − A⊤ b, e i = 0 для любого вектора e единичной длины. Как следствие, приходим к выводу, что должно бытьA⊤Ax = A⊤ b.Система линейных алгебраических уравненийA⊤A x = A⊤ b(3.143)называется нормальной системой уравнений для линейной задачи о3.16. Проблема собственных значений403наименьших квадратах с матрицей A и вектором b.29 Её решение и доставляет искомый минимум выражению Φ(x) = kAx − bk22 , что следуетиз проведённых выше выкладок и того факта, что гессианом функцииΦ является положительно полуопределённая матрица A⊤A.Решение системы линейных алгебраических уравнений по методунаименьших квадратов обычно называют псевдорешением, а псевдорешение наименьшей длины выделяется термином нормальное псевдорешение.На практике применяется несколько подходов к решению линейнойзадачи о наименьших квадратах.
Прежде всего — это прямое решение нормальной системы уравнений (3.143). Недостаток этого способасостоит в том, что обусловленность нормальной системы (3.143) существенно хуже, чем исходной. Тем не менее, при небольших размерахзадачи этим невыгодным обстоятельством можно пренебречь. Так какматрица A⊤A симметрична и положительно полуопределена, для решения нормальной системы (3.143) можно использовать метод Холесского.Другие подходы к решению линейной задачи наименьших квадратов основаны на использовании QR-разложения матрицы A или её сингулярного разложения.3.16Проблема собственных значений3.16аОбсуждение постановки задачиНенулевой вектор v называется собственным вектором квадратнойматрицы A, если в результате умножения на эту матрицу он переходитв коллинеарный себе, т.
е. отличающийся от исходного только некоторым скалярным множителем:Av = λv.(3.144)Сам скаляр λ, который является коэффициентом пропорциональности исходного вектора и его образа при действии матрицы, называютсобственным значением или собственным числом матрицы. Соответственно, проблемой собственных значений называется задача определения собственных значений и собственных векторов матриц: для за29 Переход от исходной системы уравнений Ax = b к нормальной системе (3.143)иногда называют первой трансформацией Гаусса.4043. Численные методы линейной алгебрыданной n × n-матрицы A найти числа λ и n-векторы v 6= 0, удовлетворяющие условию (3.144).Система уравнений (3.144) кажется недоопределённой, так как содержит n + 1 неизвестных, которые нужно найти из n уравнений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
