Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (1185350), страница 25

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 25)

В случаенекоторой симметрической положительно определеннойматрицы D будемpпользоваться обобщенной нормой вектора kykD = (Dy, y) .Теорема 8.3 ( [12]). Пусть A и B — симметрические положительноопределенные матрицы, для которых справедливы неравенстваγ1 B ≤ A ≤ γ2 B ,(8.21)где γ1, γ2 — положительные константы и γ1 < γ2. При τ = 2/(γ1 + γ2) итерационный метод (8.20) сходится, и для погрешности справедливы оценки:гдеkxn − xkA ≤ ρn kx0 − xkA ,n = 0, 1, .

. . ,kxn − xkB ≤ ρn kx0 − xkB ,n = 0, 1, . . . ,ρ=1−ξ,1+ξξ=γ1.γ2(8.22)ПустьAµ = λBµ .(8.23)Тогдаиγ1(Bµ, µ) ≤ (Aµ, µ) = λ(Bµ, µ) ≤ γ2 (Bµ, µ)γ1 ≤ λmin (B −1A) ,γ2 ≥ λmax (B −1A) ,(8.24)где λmin (B −1A) и λmax (B −1A) — минимальное и максимальное по абсолютному значению собственные числа в обобщенной задаче (8.23) на собственные значения.Таким образом, наиболее точными константами, с которыми выполняются неравенства (8.21), являются константыγ1 = λmin (B −1A) ,γ2 = λmax (B −1A) .В этом случае параметрτ=1482λmin (B −1A) + λmax (B −1A)(8.25)8.9 Скорость сходимости итерационных методовназывается оптимальным итерационным параметром, минимизирующимρ=1−ξ,1+ξξ=γ1γ2на множестве всех положительных γ1 , γ2, удовлетворяющих условиям (8.24).В случае метода простой итерации (B = I) получаем два следствия.Следствие 8.4.Если AT = A > 0, то для метода простой итерацииxn+1 − xn+ Axn = fτприτ = τ0 =2λmin (A) + λmax (A)справедлива оценкагде [12]kxn − xk ≤ ρn0 kx0 − xk ,ρ0 =1−ξ,1+ξξ=λmin (A).λmax (A)Следствие 8.5.

Для симметрической матрицы A и τ0 = 2/(λmin(A) ++ λmax (A)) справедливо равенствоkI − τ0 Ak = ρ0 ,где [12]ρ0 =1−ξ,1+ξξ=λmin (A).λmax (A)В приложениях часто встречаются задачи с плохо обусловленной матрицей A, когда соотношение λmax (A)/λmin(A) велико. В этом случае число ρ0близко к единице, и метод простой итерации сходится медленно. Число итераций n0 (ε), которое требуется в случае малых ξ для достижения заданнойточности ε, т. е. для достижения оценкиkxn − xk ≤ εkx0 − xk ,получается из условия ρn0 < ε в виде n ≥ n0(ε), гдеn0(ε) =ln(1/ε).ln(1/ρ0)1498 Итерационные методыОтсюда при малых ξ имеемln(1/ε)n0 (ε) ≈=O2ξ 1.ξЭто свидетельствует о том, что метод простой итерации в случае малых ξявляется медленно сходящимся методом. Ускорить сходимость можно двумяспособами: применяя неявный итерационный метод и/или делая τ = τn+1зависящим от номера итерации.8.10Итерационные методы вариационного типаНайти минимальное и максимальное по абсолютному значению собственные числа в обобщенной задаче (8.23) на собственные значения бываетсложно, а без них невозможно задать наилучшее значение итерационногопараметра (8.25).

В таких случаях можно использовать другой класс итерационных методов — методы вариационного типа. Здесь на каждой итерацииxk+1 − xk+ Axk = f ,(8.26)Bτk+1для параметра τk+1 выбирают то значение, которое минимизирует предопределенный критерий качества, связанный с погрешностью kxk+1 − xkD ,при условии, что предыдущая итерация уже состоялась с погрешностьюkxk − xkD . В зависимости от выбора матриц D и B получают различныеметоды этого типа.Метод минимальных невязокРассмотрим уравнение Ax = f с A = AT > 0. Разностьrk = Axk − f ,(8.27)которая получается при подстановке приближенного значения xk в это уравнение, называют невязкой.

Погрешность zk = xk − x и невязка rk связаныравенством Azk = rk . Представим явный итерационный методxk+1 − xk+ Axk = fτk+1(8.28)xk+1 = xk − τk+1rk .(8.29)в виде1508.10 Итерационные методы вариационного типаМетод минимальных невязок есть метод (8.28), в котором параметр τk+1минимизирует krk+1k при заданной норме krk k невязки текущего шага. Найдем это значение. Из (8.29) получаем:Axk+1 = Axk − τk+1Ark ,rk+1 = rk − τk+1Ark .(8.30)Возводя обе части уравнения (8.30) скалярно в квадрат, получим2krk+1k2 = krk k2 − 2τk+1(rk , Ark ) + τk+1kArk k2.Отсюда видно, что krk+1k достигает минимума приτk+1 =(Ark , rk ).kArk k2(8.31)Таким образом, в методе минимальных невязок переход от k-й итерациик (k + 1)-й осуществляется по следующему алгоритму:по найденному значению xk вычисляют вектор невязки rk = Axk − f ,по формуле (8.31) находят параметр τk+1,по формуле (8.29) определяют вектор xk+1.Теорема 8.4 ( [12]).

Пусть A — симметрическая положительно определенная матрица. Для погрешности метода минимальных невязок справедлива оценкаkA(xn − x)k ≤ ρn0 kA(x0 − x)k ,n = 0, 1, . . . ,гдеλmin (A)1−ξ,ξ=.1+ξλmax (A)Иными словами, метод минимальных невязок сходится с той же скоростью, что и метод простой итерации с оптимальным параметром τ .ρ=Метод минимальных поправокЗапишем неявный итерационный метод (8.26) в видеxk+1 = xk − τ B −1rk ,где rk = Axk − f — невязка.

Вектор ωk = B −1rk называют поправкой итерационного метода на (k +1)-й итерации. Поправка ωk удовлетворяет тому жеуравнению, что и погрешность zk = xk − x неявного метода, т. е. уравнениюωk+1 − ωk+ Aωk = 0 .(8.32)Bτk+11518 Итерационные методыПусть B — симметрическая положительно определенная матрица. Тогдаметод минимальных поправок — это метод (8.26), в котором параметр τk+1минимизирует норму kωk+1kB = (Bωk+1, ωk+1)1/2 при ранее полученном векторе ω k . В случае B = I метод минимальных поправок совпадает с методомминимальных невязок.Перепишем (8.32) в видеωk+1 = ωk − τk+1B −1Aωkи вычислим2kωk+1k2B = kωk k2B − 2τk+1(Aωk , ωk ) + τk+1(B −1Aωk , Aωk ) .Мининум kωk+1k2B достигается, если и только еслиτk+1 =(Aωk , ωk ).(B −1Aωk , Aωk )(8.33)Для реализации метода минимальных поправок требуется на каждойитерации решать систему уравнений Bωk = rk относительно поправки ωkи затем решать систему уравнений Bvk = Aωk , откуда находят векторvk = B −1Aωk , необходимый для вычисления параметра τk+1.Теорема 8.5 ( [12]).

Пусть A и B — симметрические положительноопределенные матрицы и λmin (B −1A), λmax(B −1A) — наименьшее и наибольшее собственные значения в задаче Ax = λBx. Для погрешности методаминимальных поправок справедлива оценкаkA(xn − x)kB −1 ≤ ρn0 kA(x0 − x)kB −1 ,где1−ξρ0 =,1+ξn = 0, 1, . .

. ,λmin (B −1A)ξ=.λmax (B −1A)Метод скорейшего спускаВозьмем явный метод (8.13) и выберем итерационный параметр τk+1 изусловия минимума kzk+1kA при заданном векторе zk , где zk+1 = xk+1 − x.Поскольку погрешность zk удовлетворяет уравнениюzk+1 = zk − τk+1Azk ,имеем2kzk+1k2A = kzk k2A − 2τk+1(Azk , Azk ) + τk+1(A2zk , Azk ) .1528.10 Итерационные методы вариационного типа(Azk , Azk ).(A2zk , Azk )Величина zk = xk − x неизвестна, но Azk = rk = Axk − f . Поэтомувычисление τk+1 проводят по формулеМинимум нормы kzk+1k2A достигается при τk+1 =τk+1 =Теорема 8.6 ( [12]).спуска справедлива оценка(rk , rk ).(Ark , rk )Для погрешности явного метода скорейшегоkxn − xkA ≤ ρn0 kx0 − xkA ,n = 0, 1, .

. . ,гдеρ0 =1−ξ,1+ξξ=λmin (A).λmax (A)Если вместо (8.13) взять неявный метод (8.26) и параметр τk+1 выбиратьиз условия минимума kzk+1 kA , то получим неявный метод наискорейшегоспуска. Для него2kzk+1k2A = kzk k2A − 2τk+1(Azk , B −1Azk ) + τk+1(AB −1Azk , B −1Azk ) ,или2kzk+1k2A = kzk k2A − 2τk+1(rk , ωk ) + τk+1(Aωk , ωk ) .Следовательно, норма kzk+1 k2A будет минимальной приτk+1 =Теорема 8.7 ( [12]).ведлива оценка(rk , ωk ).(Aωk , ωk )Для неявного метода скорейшего спуска спра-kxn − xkA ≤ ρn0 kx0 − xkA ,n = 0, 1, . .

. ,где1−ξρ0 =,1+ξλmin (B −1A)ξ=.λmax (B −1A)1538 Итерационные методыМетод сопряженных градиентовЭтот метод исходит из задачи минимизации функции1J(x) = (Ax, x) − (b, x) ,2(8.34)решение которой совпадает с решением системыAx = f ,A = AT > 0 .(8.35)Полный вывод метода сопряженных градиентов можно найти в [12]. Опуская детали, приведем окончательный результат.Метод сопряженных градиентов для решения системы Ax = f состоит ввычислениях по следующим формулам:rk = b − Axk , k = 0, 1, .

. . ,k+1kk10p= r + βk+1 p , k = 1, 2, . . . , p = r ,k+1kk+10(8.36)x= x + αk+1 p, k = 0, 1, . . . , x = 0 ,αk+1 = (rk , pk+1)/(pk+1, Apk+1) , k = 0, 1, . . . , k kk kβk+1 = −(Ap , r )/(Ap , p ) , k = 1, 2, . . . .Теорема 8.8 ( [12]). Для метода сопряженных градиентов (8.36) справедливоhikppkkx − xkA ≤ 2 (1 − λmin /λmax )/(1 + λmin /λmax) kxkA ,где λmin и λmax — минимальное и максимальное собственные значения матрицы A.Следуя [12], преобразуем соотношения (8.36).

В этих соотношениях наиболее трудоемкими являются две операции: вычисление векторов Axk и Apk .Однако операцию вычисления вектора Axk можно исключить. Посколькуэтот вектор нужен только для вычислении невязки rk , то можно заменитьпервую из формул (8.36) наrk = rk−1 − αk Apk ,k = 1, 2, . . . ,r0 = b .(8.37)Преобразуем формулы для вычисления параметров αk+1 и βk+1 .

Подставляявторое из соотношений (8.36) в четвертое, найдемαk+1 = (rk , rk )/(pk+1, αpk+1) ,154k = 0, 1, . . . .(8.38)8.11 Другие методыЗаменяя здесь k + 1 на k и подставляя полученное выражение для (pk , Apk )в последнее из соотношений (8.36), получимβk+1(Apk , rk )= −αk k−1 k−1 .(r , r )Теперь подставим сюда вместо Apk его выражение из (8.37).Теорема 8.9 ( [12]). После k шагов метода сопряженных градиентовневязки r0 , r1, ..., rk взаимно ортогональны.Принимая это во внимание, найдемβk+1 =(rk , rk ),(rk−1, rk−1)k = 1, 2, . .

. .(8.39)С учетом (8.37)–(8.39) формулы метода сопряженных градиентов (8.36)преобразуются к видуrk = rk−1 − αk Apk , k = 1, 2, . . . , r0 = b , k+1kk10p= r + βk+1pk = 1, 2, . . . , p = r ,k+1kk+10(8.40)x= x + αk+1 p , k = 0, 1, . . . , x = 0 ,αk+1 = krk k2 /(pk+1, Apk+1) , k = 0, 1, . . . ,k 2k−1 2βk+1 = kr k /kr k , k = 1, 2, . . . .Легко проверить, что эти вычисления проводят в следующем порядке:r0 = b ,r1 , β2 ,8.11p1 = r0 , Ap1 , α1 , x1 ,p2 , Ap2 , α2 , x2 , . . .Другие методыОбласть итерационных методов решения систем линейных алгебраических уравнений обширна. Она включает гораздо большее количество методов, чем то, что приведено выше.В итерационных методах нашли применение полиномы Чебышёва, благодаря которым можно решать задачу оптимального выбора итерационныхпараметров как для явных ИМ, так и для неявных ИМ [12].Стационарные методы, широко применявшиеся в 1950–1980 годах, сейчасчаще применяются [126] как средство сглаживания в многосеточных алгоритмах [102, 118, 144] или для предобусловливания в алгоритмах Крылова[139].1558 Итерационные методыИдея сопряженных градиентов [136] оказалась очень плодотворной, и наиболее широкое воплощение она нашла при опоре на метод подпространствКрылова, который является одним из методов решения проблемы собственных значений и собственных векторов для очень больших разреженныхматриц [143].

Переход к методу подпространств Крылова в этой проблемевызван тем, что преобразования подобия, лежащие в основе ее решениядля небольших матриц, выполнять для очень больших матриц практически невозможно. В то же время достаточно легко выполнять однотипныеоперации умножения матрицы на вектор: взять вектор x и затем, умножаяслева на A, построить последовательность Крылова x, Ax, A2x, A3x, . . . и,соответственно, получить пространства КрыловаKj (A, x) = span x, Ax, A2x, A3x, .

Характеристики

Список файлов книги