Численные методы. Соснин (2005) (1160462), страница 6
Текст из файла (страница 6)
Для этоговведем некоторые дополнительные понятия, связанные с погрешностью итерационного метода.Рассмотрим произведение Az k = A(xk − x) = Axk − Ax = Axk − f = rk — полученная разностьвычислима на каждом шаге итерационного процесса и называется невязкой4 .Запишем схему итерационного процессаBxk+1 − xk+ Axk = f,τk+1и выразим xk+1 :xk+1 = xk − τk+1 B −1 (Axk − f ) = xk − τk+1 B −1 rk = xk − τk+1 ω k .Число ω k = B −1 rk называется поправкой.Перепишем (1.39), используя новые определения:τk+1Dω k , z k=.hDω k , ω k i(1.40)Проще ли нам от этого стало? Да пока не очень, потому что величина z k по-прежнему неизвестна,и вычислить ее мы не можем.
. .Воспользуемся возможностью варьировать D.4 невязка(отгреч. ηεϑαςυς ) — дисбаланс.1.8. ПРИМЕРЫ ИТЕРАЦИОННЫХ МЕТОДОВ ВАРИАЦИОННОГО ТИПА1.831Примеры итерационных методов вариационного типаМетод скорейшего спускаПусть матрица A, задающая систему уравнений Ax = f, симметрична и положительно определена(A = AT > 0), и выберем матрицу D = A, тогда k k k k kAω , zω , Az kω ,rτk+1 ===kkkkhAω , ω ihAω , ω ihAω k , ω k i— теперь, так как нам известно rk на каждом шаге, то τk+1 становится вычислимым.Получим необходимое условие на матрицу B для применимости итерационных методов вариационного типа. Используя то, что11111111C = D 2 B −1 AD− 2 = {D = A =⇒ D 2 = A 2 } = A 2 B −1 AA− 2 = A 2 B −1 A 2 ,и положительную определенность матрицы C, получимD 1E DE1110 < hCx, xi = A 2 B −1 A 2 x, x = B −1 A 2 x, A 2 x .1Обозначив A 2 x = y, получим B −1 y, y > 0, или, еще раз переобозначив B −1 y = u, hu, Bui > 0,то есть матрица B должна быть положительно определена — это и есть необходимое условие применимости метода вариационного типа.Возьмем B = E : k kr ,rk+1kkx= x − τk+1 r , где τk+1 =.hArk , rk iЭтот набор (eτ ) соответствует методу скорейшего спуска.Пояснение названия метода.F (x) = hAx, xi − 2 hf, xi =Введем функцию F (x) :nXi=1(Ax)i xi − 2nXfi xi =i=1nn XXaij xj xi − 2i=1 j=1nXfi xi ,где x ∈ Rn .i=1Пусть A = AT , найдем градиент функции F (x), чтобы определить направление максимальногоубывания:T∂F∂Fgrad F (x) =, ...,,∂x1∂xnгдеn XnnnXXX∂F∂=aij(xj , xi ) − 2fl =ail xi +alj xj − 2fl .∂xl∂xli=1 j=1i=1j=1Используя симметричность матрицы A, получим:nX∂F=2ali xi − 2fl = 2((Ax)l − fl ) = 2rl .∂xli=1Таким образом, мы показали, что градиент функции F (x) равен удвоенному вектору невязки:grad F (x) = 2r.То есть, учитывая формулу xk+1 = xk − τk+1 rk , и представление для невязки, получается, что каждыйраз мы строим xk+1 от xk в направлении антиградиента функции F (x).32Глава 1.
РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙПри этом остается свободным параметр τk+1 . Будем его выбирать так, чтобы минимизироватьзначение функции F (xk+1 ) на k + 1 приближении.min F (xk+1 ) = min Axk+1 , xk+1 − 2 f, xk+1 =τk+1τk+1= min A(xk − τk+1 rk ), xk − τk+1 rk − 2 f, xk − τk+1 rk .τk+1Раскроем скобки, и, в силу свойств скалярного произведения, получим k k2Ar , r − 2 f, xk + 2τk+1 f, rk .min F (xk+1 ) = min Axk , xk − 2τk+1 rk , Axk + τk+1τk+1τk+1Чтобы найти минимум по τk+1 , возьмем производную по этой переменной от функции F (x) иприравняем ее к 0.∂F (xk+1 )= −2 rk , Axk + 2τk+1 Ark , rk + 2 f, rk = 0.∂τk+1Откуда получаем выражение для τk+1 : k k kr ,rr , Axk − rk , f=.τk+1 =kkhAr , r ihArk , rk iКак нетрудно заметить оно совпадает с записанным ранее τk+1 в определении метода скорейшегоспуска.
Таким образом, этот метод гарантирует построение итерационной последовательности, котораястроится в направлении максимального уменьшения функции F (x). Из курса вариационного исчисления известно, что минимизация функции F (x) приводит к наиболее быстрой сходимости xk к точномурешению системы.Рассмотрим скорость сходимости этого метода. Будем подбирать τk+1 так, чтобы минимизироватьz k+1 в методе скорейшего спуска.
Понятно, что при выборе τk+1 отличным от оптимального, гарантирующего минимум, будут получены величины не меньше. Таким образом, получаем оценку сверху:||z k+1 ||A 6 ||(E − τ0 B −1 A)z k ||A .В параграфе об оценке сходимости одношаговых стационарных методов была получена верхняяоценка ||z k+1 ||A 6 q||z k ||A . Очевидно, метод скорейшего спуска имеет оценку не хуже, чем ОСИМ,и, соответственно, итерационные методы вариационного типа имеют погрешность не хуже, чем соответствующие (по матрице B ) ОСИМ с оптимальным выбором параметра τ0 . Отсюда можно сделатьзаключение, что вариационные методы сходятся не медленнее стационарных методов.Кроме того, для метода вариационного типа следует обратить внимание на то, что данный результат(оценку погрешности) можно получить, практически не исследуя матрицу B −1 A.Метод минимальных невязокВ качестве матрицы D возьмем D = AT A.
Из этого следует, что D = DT > 0. Тогда, учитываяпредставление (1.40), параметр τk+1 будет считаться так:Dω k , z kτk+1 =.hDω k , ω k iПерепишем τk+1 так, чтобы его можно было вычислить. Распишем D : T k k k kA Aω k , z kAω , rAω , rτk+1 ===TkkkkhA Aω , ω ihAω , Aω i||Aω k ||21.8. ПРИМЕРЫ ИТЕРАЦИОННЫХ МЕТОДОВ ВАРИАЦИОННОГО ТИПА33— теперь параметр τk+1 вычислим, так как невязка и поправка нам известны на каждом шаге.Для сходимости итерационных методов вариационного типа мы требовали положительной определенности матрицы C. Посмотрим к чему это условие приведет в методе минимальных невязок.
Итак,найдем ограничения на исходную систему.ED 110 < hCx, xi = D 2 B −1 AD− 2 x, x =D 1E 11= {обозначим D− 2 x = y} = D 2 B −1 Ay, D 2 y = DB −1 Ay, y = AT AB −1 Ay, y .Сделаем еще две замены: Ay = u и u = Bv, тогда получимhCx, xi = AB −1 u, u = hAv, Bvi = B T Av, v .То есть, надо следить за тем, чтобы матрица B T A была положительно определена. Если в качествеB возьмем единичную матрицу, то метод минимальных невязок будет применим к системам уравненийс положительно определенными матрицами.Объяснение названия метода. Параметр τk+1 мы подбираем таким образом, чтобы минимизировать норму погрешности:qqqmin ||z k+1 ||D = min hDz k+1 , z k+1 i = min hAT Az k+1 , z k+1 i = min hrk+1 , rk+1 i = min ||rk+1 ||τk+1τk+1τk+1τk+1τk+1— таким образом, минимизируя погрешность, мы минимизируем невязки.Метод минимальных поправокВ качестве матрицы D возьмем D = AT B −1 A, и наложим ограничения на матрицу: D = DT > 0,т.е.
матрица B должна быть симметрической положительно определенной.Возьмем B = E =⇒ rk = ω k . При таком выборе матриц B и D получим следующее выражениедля параметра τk+1 : T −1 k k −1 k k k kDω k , z kA B Aω , zB Aω , rAω , ωτk+1 ====.hDω k , ω k ihAT B −1 Aω k , ω k ihB −1 Aω k , Aω k ihAω k , Aω k iИтак, формула для итерационного параметра становится реализуемой. Исходя из ограничений наложенных на матрицы C выше (C > 0 ) опишем класс систем, которые можно решать с помощьюметода минимальных поправок. Раскроем условие положительной определенности:D 1E10 < hCx, xi = D 2 B −1 AD− 2 x, x .1Как и в методе минимальных невязок, обозначим D− 2 x = y, Ay = u, B −1 u = v, тогда получим:E D 1 10 < D 2 B −1 Ay, D 2 y = DB −1 Ay, y = AT B −1 AB −1 Ay, y = = B −1 AB −1 Ay, Ay = B −1 AB −1 u, u = B −1 Av, Bv = hAv, vi— то есть, метод минимальных поправок применим для систем с положительно определенной матрицей.Объяснение названия метода.
Как и в методе минимальных невязок, будем минимизировать норму погрешности ||z k+1 ||2D = Dz k+1 , z k+1 = AT B −1 Az k+1 , z k+1 = = B −1 Az k+1 , Az k+1 = B −1 rk+1 , rk+1 = ω k+1 , Bω k+1 = ||ω k+1 ||2B .Таким образом, минимизируя норму погрешности, мы минимизируем норму поправки.34Глава 1. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙМетод минимальных погрешностейВ этом примере матрица D берется равной некоторой матрице B0 : B0 = B0T > 0, которая должнабыть к тому же легко обратимой.
Матрица B определяется так:B = (AT )−1 B0 .Как и ранее, покажем корректность формулы для τk+1 :Dω k , z kB0 B −1 rk , z kτk+1 ===hDω k , ω k ihB0 B −1 rk , ω k i k k kr , Az kB0 B0−1 AT rk , z kr ,r−1 T−1= k= {B = B0 A } = = k.−1 T kkkhr , Aω ihr , Aω k iB0 B0 A r , ω— как уже показывалось, rk (невязку) и wk (поправку) мы умеем вычислять на каждом шаге.Другим ограничением была положительная определенность матрицы C. Проверим это:D 1ED 1E111hCx, xi = D 2 B −1 AD− 2 x, x = {обозначим y = D− 2 x} = D 2 B −1 Ay, D 2 y == DB −1 Ay, y = {D = B0 , B = (AT )−1 B0 } = B0 B0−1 AT Ay, y = hAy, Ayi .Очевидно, hAx, Axi всегда больше нуля, если матрица A — невырожденная.
Таким образом, методминимальных погрешностей верен для любых невырожденных матриц A.Название метода произошло от требования минимизации погрешности ||z k+1 ||D = ||z k+1 ||B0 на(k + 1)-м шаге.Замечание. Все эти методы возникли из стратегии локальной минимизации погрешности от шагак шагу. При таких требованиях достигается высокая скорость сходимости, причем нам не требуетсядополнительная информация, к примеру, о спектре матрицы A. Однако нет предела совершенству...1.9Двухшаговые итерационные методы вариационного типаДанные методы используются при решении систем большой размерности (тысячи, десятки тысяч уравнений).
Решаем мы по-прежнему систему Ax = f. Действуя так же, как и при работе с одношаговымиитерационными методами, можно показать, что каноническая форма двухшаговых методов такова:Bxk+1 − xk + (1 − αk+1 )(xk − xk−1 )+ Axk = f,αk+1 τk+1k = 1, 2, . . .(1.41)Для того, чтобы задать итерационный процесс, мы определяем два начальных приближения: x0 иx .
Остальные вычисляются по этой формуле, где B, αk+1 , τk+1 — параметры, определяющие метод.Также неявным параметром будет матрица D. Она определяет норму ||z k+1 ||D , которую мы, как ираньше, будем минимизировать на каждой итерации. Для этого необходимо брать αk+1 и τk+1 такими:Dω k , z kτk+1 =, k = 1, 2, . . . ;hDω k , ω k iα1 = 1; !−1kkDω,zτk+11−·, k = 1, 2, . . . αk+1 =τk αk hDω k−1 , z k−1 i1— подробный вывод этих формул можно найти в [2].Как и раньше, при надлежащем выборе мы можем избавиться от z k в скалярном произведении икорректно применять эти формулы при подсчете приближений. Поясним это на примерах.1.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
