1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 62
Текст из файла (страница 62)
Численные методы линейной алгебрыспуска, так как тогда его вторая производная по τk , равная hAr(k) , r(k) i,положительна. В целом, псевдокод метода наискорейшего градиентного спуска для решения системы линейных алгебраических уравненийAx = b представлен в Табл. 3.8.Таблица 3.8.
Псевдокод метода наискорейшего спускадля решения систем линейных уравненийk ← 0;выбираем начальное приближение x(0) ;DO WHILE ( метод не сошёлся )r(k) ← Ax(k) − b ;τk ←k r(k) k22;hAr(k) , r(k) ix(k+1) ← x(k) − τk r(k) ;k ← k +1;END DOТеорема 3.10.2 Если A — симметричная положительно определённая матрица, то последовательность {x(k) }, порождаемая методомнаискорейшего спуска, сходится к решению x⋆ системы уравненийAx = b из любого начального приближения x(0) , и быстрота этойсходимости оценивается неравенствомk x(k) − x⋆ kA ≤M −µM +µkk x(0) − x⋆ kA ,k = 0, 1, 2, .
. . , (3.119)где µ, M — нижняя и верхняя границы спектра матрицы A.Доказательство оценки (3.119) и теоремы в целом будет полученопутём сравнения метода наискорейшего спуска с методом градиентногоспуска с постоянным оптимальным шагом.3.10. Нестационарные итерационные методы379Пусть в результате выполнения (k−1)-го шага метода наискорейшего спуска получено приближение x(k) , и мы делаем k-ый шаг, которыйдаёт x(k+1) . Обозначима также через x̃ результат выполнения с x(k)одного шага метода простой итерации, так чтоx̃ = x(k) − τ Ax(k) − b .Из развитой в предшествующей части параграфа теории вытекает, чтопри любом выборе параметра τΨ (x(k+1) ) ≤ Ψ (x̃).Далее, из равенства (3.117)Ψ (x) =12 kx− x⋆ k2A − 12 hAx⋆ , x⋆ iс постоянным вычитаемым 21 hAx⋆ , x⋆ i следует, что(k+1)12 kx− x⋆ k2A ≤12 kx̃− x⋆ k2A ,т.
е.k x(k+1) − x⋆ kA ≤ kx̃ − x⋆ kA .(3.120)Иными словами, метод, обеспечивающий лучшее убывание значенияфункционала энергии одновременно обеспечивает лучшее приближение к решению в энергетической норме.В методе градиентного спуска с постоянным шагом — совпадающемс методом простой итерации (3.104) или (3.115) — имеемx̃ − x⋆ = (I − τ A)(x(k) − x⋆ ),k = 0, 1, 2, . . . .Матрица (I −τ A) является многочленом первой степени от матрицы A,и потому можем применить неравенство (3.29) из Предложения 3.3.8(стр.
257):k x̃ − x⋆ kA ≤ kI − τ Ak2 k x(k) − x⋆ kA .При этом у метода наискорейшего спуска оценка заведомо не хужеэтой оценки, в которой взято значение параметра шага τ = 2/(M + µ),оптимальное для спуска с постоянным шагом. Тогда в соответствии с(3.120) и с оценкой (3.106) для метода простой итерации получаемM −µ(k+1)⋆k x(k) − x⋆ kA ,k = 0, 1, 2, . . .
,kx− x kA ≤M +µ3803. Численные методы линейной алгебрыx⋆x(0)Рис. 3.23. Иллюстрация работы метода наискорейшего спуска.откуда следует доказываемая оценка (3.119).Интересно и поучительно рассмотреть геометрическую иллюстрацию работы метода наискорейшего спуска.Градиент функционала энергии нормален к его поверхностям уровня, и именно по этим направлениям осуществляется «спуск» — движение в сторону решения. Шаг в методе наискорейшего спуска идётна максимально возможную величину — до пересечения с касательным эллипсоидом. Поэтому траектория метода наискорейшего спускаявляется ломаной, звенья которой перпендикулярны друг другу (см.Рис.
3.23).Хотя доказательство Теоремы 3.10.2 основано на мажоризации наискорейшего спуска методом простой итерации и может показаться довольно грубым, оценка (3.119) в действительности весьма точно передаёт особенности поведения метода, а именно, замедление сходимостипри M ≫ µ.
Тот факт, что в случае плохой обусловленности матрицысистемы движение к решению в методе наискорейшего спуска весьмадалеко от оптимального, подтверждается вычислительной практикой иможет быть понято на основе геометрической интерпретации. Искомоерешение находится при этом на дне глубокого и вытянутого оврага, аметод «рыскает» от одного склона оврага к другому вместо того, чтобыидти напрямую к глубочайшей точке — решению.3813.10. Нестационарные итерационные методы3.10вМетод минимальных невязокДругой популярный подход к выбору итерационных параметров τkв нестационарном итерационном процессе (3.116)k = 0, 1, 2, .
. . ,x(k+1) ← x(k) − τk Ax(k) − b ,был предложен С.Г. Крейном и М.А. Красносельским в работе [24] иназван ими методом минимальных невязок. Его псевдокод приведёнв Табл. 3.9. Каждый шаг этого метода минимизирует kAx − bk2 или,что равносильно, kAx − bk22 в направлении невязки k-го приближения,равной r(k) = Ax(k) − b. Оказывается, что это эквивалентно наибольшему возможному уменьшению A⊤A-нормы погрешности приближённогорешения системы. В самом деле, если x⋆ — точное решение системыуравнений, то Ax⋆ = b, и потомуkAx − bk22 = hAx − b, Ax − bi = hAx − Ax⋆ , Ax − Ax⋆ i= hA(x − x⋆ ), A(x − x⋆ )i = A⊤A(x − x⋆ ), x − x⋆= k x − x⋆ k2A⊤A .(3.121)Если уже найдено x(k) , и мы желаем выбрать параметр τ так, чтобы на следующем приближении x(k) − τ r(k) минимизировать 2-нормуневязки решения, то необходимо найти минимум по τ для выраженияA(x(k) − τ r(k) ) − b2 = A(x(k) − τ r(k) ) − b, A(x(k) − τ r(k) ) − b2= τ 2 hAr(k) , Ar(k) i − 2τ hAx(k) , Ar(k) i − hb, Ar(k) i+ hAx(k) , Ax(k) i + hb, bi.Дифференцируя его по τ и приравнивая производную нулю, получим2τ hAr(k) , Ar(k) i − 2 hAx(k) , Ar(k) i − hb, Ar(k) i = 0,что с учётом равенства Ax(k) − b = r(k) даётτ hAr(k) , Ar(k) i − hr(k) , Ar(k) i = 0.Окончательноτ =hAr(k) , r(k) ihAr(k) , r(k) i=.hAr(k) , Ar(k) ikAr(k) k223823.
Численные методы линейной алгебрыТаблица 3.9. Псевдокод метода минимальных невязокдля решения систем линейных уравненийk ← 0;выбираем начальное приближение x(0) ;DO WHILE ( метод не сошёлся )r(k) ← Ax(k) − b ;τk ←hAr(k) , r(k) i;kAr(k) k22x(k+1) ← x(k) − τk r(k) ;k ← k +1;END DOТеорема 3.10.3 Если A — симметричная положительно определённая матрица, то последовательность {x(k) }, порождаемая методомминимальных невязок, сходится к решению x⋆ системы уравненийAx = b из любого начального приближения x(0) , и быстрота этойсходимости оценивается неравенством µ 2 k/2k x(k) − x⋆ kA⊤A ≤ 1 −k x(0) − x⋆ kA⊤A ,(3.122)Mk = 0, 1, 2, .
. . , где µ, M — нижняя и верхняя границы спектра матрицы A.Доказательство теоремы можно найти, к примеру, в книге [56], гдедля невязок r(k) = Ax(k) − b доказывается оценка 2 1/2 (k+1) r(k) ,r ≤ 1− µk = 0, 1, 2, . . . .22MС учётом выкладок (3.121) этот результат совершенно равносилен неравенству (3.122).Для систем линейных уравнений с несимметричными матрицами, которые положительно определены, метод минимальных невязок также3.10. Нестационарные итерационные методы383сходится. Но если матрица системы не является положительно определённой метод может не сходиться к решению.Пример 3.10.1 В системе линейных алгебраических уравнений2 21 0x= 21матрица не является ни симметричной, ни положительно определённой (её собственные значения приблизительно равны 2.732 и −0.7321).В применении к этой системе метод минимальных невязок с нулевымначальным приближением вскоре после начала работы устанавливается на векторе (0.7530088, 0.2469912)⊤, тогда как настоящее решение —это вектор (1, 0)⊤ .
Из других начальных приближений метод будет сходится к другим векторам, которые также не совпадают с этим точнымрешением.Практически важной особенностью метода минимальных невязокявляется быстрая сходимость к решению на первых шагах, котораязатем замедляется и выходит на асимптотическую скорость, описываемую Теоремой 3.10.3.Если сходимость методов наискорейшего спуска и минимальныхневязок принципиально не лучше сходимости метода простой итерации, то имеют ли они какое-либо практическое значение? Ответ наэтот вопрос положителен. Вспомним, что наша оптимизация методапростой итерации основывалась на знании границ спектра симметричной положительно определённой матрицы СЛАУ.
Для работы методовнаискорейшего спуска и минимальных невязок этой информации нетребуется.Метод минимальных невязок в представленной выше версии не отличается большой эффективностью. Но он послужил основой для создания многих популярных современных методов решения СЛАУ. Вчастности, большое распространение на практике получила модификация метода минимальных невязок, известная под англоязычной аббревиатурой GMRES — Generalized Minimal RESidulas — обобщённыйметод минимальных невязок, предложенная Ю. Саадом [56] (см. также[43, 59]).3843.10г3.
Численные методы линейной алгебрыМетод сопряжённых градиентовМетодами сопряжённых направлений для решения систем линейных алгебраических уравнений вида Ax = b называют методы, в которых решение ищется в виде линейной комбинации векторов, ортогональных в скалярном произведении, которое порождено матрицейсистемы или же какой-либо матрицей, связанной с матрицей системы.Таким образом, при этомx = x(0) +nXci s(i) ,i=1где x(0) — начальное приближение, s(i) , i = 1, 2, . . . , n, — векторы «сопряжённых направлений», ci — коэффициенты разложения решения поним.
Термин «сопряжённые направления» имеет происхождение в аналитической геометрии, где направления, задаваемые векторами u и v,называются сопряжёнными относительно поверхности второго порядка, задаваемой уравнением hRx, xi = const c симметричной матрицейR, если hRu, vi = 0. В методах сопряжённых направлений последовательно строится базис из векторов s(i) и одновременно находятся коэффициенты ci , i = 1, 2, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
