1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 63
Текст из файла (страница 63)
. . , n.Наиболее популярными представителями методов сопряжённых направлений являются методы сопряжённых градиентов, предложенныеМ.Р. Хестенсом и Э.Л. Штифелем в начале 50-х годов прошлого века.Их общая схема такова.Пусть требуется найти решение системы линейных алгебраическихуравненийAx = bс симметричной и положительно определённой матрицей A. Для такой матрицы имеет смысл понятие A-ортогональности, и пусть s(1) ,s(2) , . .
. , s(n) — базис Rn , составленный из A-ортогональных векторов.Решение x⋆ системы уравнений можно искать в виде разложения поэтому базису, т. е.nXxi s(i)(3.123)x⋆ =i=1с какими-то неизвестными коэффициентами xi , i = 1, 2, . . . , n. Умножая обе части этого равенства слева на матрицу A и учитывая, что3853.10. Нестационарные итерационные методыAx⋆ = b, будем иметьnXxi (As(i) ) = b.i=1Если далее умножить скалярно это равенство на s(j) , j = 1, 2, . . . , n, тополучим n штук соотношенийnXi=1xi hAs(i) , s(j) i = h b, s(j) i,j = 1, 2, .
. . , n.(3.124)Но в силу A-ортогональности системы векторов s(1) , s(2) , . . . , s(n)0, если i 6= j,(i) (j)(i) (j)hAs , s i = hs , s iA = δij =1, если i = j,так что от равенств (3.124) останется лишьxi hAs(i) , s(i) i = h b, s(i) i,i = 1, 2, . . . , n.Окончательноxi =h b, s(i) i,hAs(i) , s(i) ii = 1, 2, . . . , n,откуда из (3.123) нетрудно восстановить искомое решение СЛАУ. Нодля практического применения этого элегантного результата нужноуметь эффективно строить A-ортогональный базис s(1) , s(2) , .
. . , s(n)пространства Rn .Он определяются процессом A-ортогонализации невязок r(0) , r(1) ,. . . , r(n−1) последовательных приближений к решению x(0) , x(1) , . . . ,x(n−1) . Этот процесс ортогонализации конечен и завершается при некотором k ≤ n, для которого r(k) = 0, т. е. когда очередная невязка приближённого решения зануляется.Но на практике из-за неизбежных погрешностей вычислений методсопряжённых градиентов может не прийти к решению системы за nшагов. Тогда целесообразно повторить цикл уточнения, превратив алгоритм при необходимости в итерационный. Именно такой псевдокодметода сопряжённых градиентов приведён в Табл.
3.10. В теле циклапервая команда вычисляет длину очередного шага метода, а втораястрока даёт следующее приближение к решению. Далее вычисляется невязка вновь найденного приближённого решения, а в следующих3863. Численные методы линейной алгебрыТаблица 3.10. Псевдокод метода сопряжённых градиентовдля решения систем линейных уравненийk ← 0;выбираем начальное приближение x(0) ;r(0) ← Ax(0) − b ;s(0) ← r(0) ;DO WHILE ( метод не сошёлся )τk ←hr(k) , r(k) i;hAs(k) , s(k) ix(k+1) ← x(k) − τk s(k) ;r(k+1) ← r(k) − τk As(k) ;υk ←hr(k+1) , r(k+1) i;hr(k) , r(k) is(k+1) ← r(k+1) + υk s(k) ;k ← k +1;END DOдвух строках тела цикла (перед увеличением счётчика k) вычисляетсяновое направление движения к решению.Широко распространена также другая трактовка метода сопряжённых градиентов, представляющая его как модификацию метода наискорейшего градиентного спуска. Как мы видели в предшествующемпараграфе, направления градиентов энергетического функционала, покоторым осуществляется движение (спуск) к решению в методе наискорейшего спуска, могут сильно изменяться от шага к шагу.
По этой причине траектория метода наискорейшего спуска имеет зигзагообразныйвид, и для получения решения затрачивается много лишней работы.Естественно попытаться каким-нибудь образом сгладить «вихляния»метода наискорейшего спуска, чтобы он шёл к решению более прямымпутём. Один из возможных способов сделать это состоит в том, чтобы3873.11. Методы установленияна каждой итерации корректировать направление спуска по антиградиенту с помощью некоторой добавки. Например, исходя из геометрических соображений, её можно взять пропорциональной разности двухпоследовательных приближений, так что в целом получаем алгоритмx(k+1) ← x(k) − τk Ax(k) − b + υk x(k) − x(k−1) ,(3.125)k = 0, 1, 2, .
. . ,где τk , υk — некоторые параметры. Для их определения можно привлечь условие минимизации энергетического функционала Ψ (x) в точке x(k+1) . При этом получаются формулы для τk и υk , приведённые впсевдокоде Табл. 3.10.Итерационный процесс (3.125) — двухшаговый, так что для началаего работы требуется знать два последовательных приближения к решению. Можно положить x(−1) = x(0) , откуда однозначно определяетсяx(1) и т. д.3.11Методы установленияМетоды установления — общее название для большой группы методов, в основе которых лежит идея искать решение рассматриваемой стационарной задачи как предела по времени t → ∞ для решения связанной с ней вспомогательной нестационарной задачи.
Этотподход к решению различных задач был развит в 30-е годы XX векаА.Н. Тихоновым.Пусть требуется решить систему уравненийAx = b.Наряду с ней рассмотрим также систему уравнений∂x(t)+ Ax(t) = b,∂t(3.126)в которой вектор неизвестных переменных x зависит от времени t. Ясно, что если x(t) не зависит от переменной t, то производная ∂x/∂tзануляется и соответствующие значения x(t) являются решением исходной задачиНаиболее часто задачу (3.126) рассматривают на бесконечном интервале [t0 , ∞) и ищут её устанавливающееся решение, т. е.
такое, что3883. Численные методы линейной алгебрысуществует конечный limt→∞ x(t) = x⋆ . Тогда из свойств решения задачи (3.126) следует, что∂xlim= 0,t→∞ ∂tи потому x⋆ является искомым решением для Ax = b.При поиске значений x(t), установившихся в пределе t → ∞, значения x(t) для конечных t не слишком интересны, так что для решения системы дифференциальных уравнений (3.126) можно применитьпростейший явный метод Эйлера (метод ломаных) с постоянным временны́м шагом τ , в котором производная заменяется на разделённуюразность вперёд.
Обозначая x(k) := x(tk ), tk = t0 + τ k, k = 0, 1, 2 . . . ,получим вместо (3.126)x(k+1) − x(k)+ Ax(k) = b,τ(3.127)илиx(k+1) = x(k) − τ (Ax(k) − b),k = 0, 1, 2, . . . ,то есть известный нам метод простой итерации (3.104) для решениясистемы уравнений Ax = b. При переменном шаге по времени, когдаτ = τk , k = 0, 1, 2, . . ., получающийся метод Эйлераx(k+1) − x(k)+ Ax(k) = bτkэквивалентенx(k+1) = x(k) − τk (Ax(k) − b),k = 0, 1, 2, . .
. ,т. е. простейшему нестационарному итерационному методу Ричардсона(3.116).Представление метода простой итерации в виде (3.127), как метода решения системы дифференциальных уравнений, даёт возможностьпонять суть ограничений на параметр τ . Это не что иное, как ограничение на величину шага по времени, вызванное требованием устойчивости метода. Если шаг по времени мал, то до установления решениязадачи (3.126) нам нужно сделать большое количество таких мелкихшагов, что даёт ещё одно объяснение невысокой вычислительной эффективности метода простой итерации.Более быструю сходимость к решению можно достичь, взяв шагпо времени большим, но для этого нужно преодолеть ограничение на3893.12.
Теория А.А. Самарскогоустойчивость метода. Реализация этой идеи действительно приводитк более эффективным численным методам решения некоторых специальных систем линейных уравнений Ax = b, встречающихся при дискретизации дифференциальных уравнений с частными производными.Таковы методы переменных направлений, методы расщепления и методы дробных шагов, идейно близкие друг другу (см. [87]).Очевидно, что вместо (3.126) можно рассмотреть задачу более общего вида∂xB+ Ax(t) = b,(3.128)∂tгде B — некоторая неособенная матрица.
Смысл её введения станетболее понятен, если переписать (3.128) в равносильном виде∂x+ B −1 Ax(t) = B −1 b.∂tТогда в пределе, при занулении ∂x/∂t, имеемB −1 Ax = B −1 b,откуда видно, что матрица B выполняет роль, аналогичную роли предобуславливающей матрицы для системы Ax = b.Отметим в заключение темы, что для решения систем линейных алгебраических уравнений, возникающих при дискретизации уравненийв частных производных эллиптического типа, предельно эффективными являются многосеточные методы, предложенные Р.П.
Федоренко вначале 60-х годов XX века.3.12Теория А.А. СамарскогоМы уже отмечали, что системы линейных алгебраических уравнений, которые необходимо решать на практике, часто бывают заданынеявно, в операторном виде. При этом мы не можем оперировать итерационными формулами вида (3.97) с явно заданным оператором Tk(наподобие (3.98)). Для подобных случаев А.А. Самарским была предложена специальная каноническая форма одношагового линейного итерационного процесса, предназначеного для решения систем уравненийAx = b:Bkx(k+1) − x(k)+ Ax(k) = b,τkk = 0, 1, 2, . . . ,(3.129)3903. Численные методы линейной алгебрыгде Bk , τk — некоторые последовательности матриц и скалярных параметров соответственно, причём τk > 0. Мы будем называть её канонической формой Самарского. Если x(k) сходится к пределу, то принекоторых необременительных условиях на Bk и τk этот предел является решением системы линейных алгебраических уравнений Ax = b.Различные последовательности матриц Bk и итерационных параметров τk задают различные итерационные методы.
Выбирая начальное значение x(0) , находим затем из (3.129) последовательные приближения как решения уравненийBk x(k+1) = Bk − τk I x(k) + τk b,k = 0, 1, 2, . . . .Ясно, что для однозначной разрешимости этой системы уравнений всематрицы Bk должны быть неособенными. Итерационный метод в форме (3.129) естественно назвать явным, если Bk = I — единичная матрица и выписанная выше система сводится к явной формуле для нахождения следующего итерационного приближения x(k+1) . Иначе, еслиBk 6= I, итерации (3.129) называются неявными. Неявные итерационные методы имеет смысл применять лишь в том случае, когда решениесистемы уравнений относительно x(k+1) существенно легче, чем решение исходной системы.Выпишем представление в форме Самарского для рассмотренныхранее итерационных процессов.
Метод простой итерации из §3.9г принимает видx(k+1) − x(k)+ Ax(k) = b,τk = 0, 1, 2, . . . ,(3.130)где τ = τk = const — постоянный параметр, имеющий тот же смысл,что и в рассмотрениях §3.9г. Переменный параметр τk в (3.130) приводит к нестационарному методу Ричардсона (3.116) (см. §3.10а). ЕслиD и L̃ — диагональная и строго нижняя треугольная части матрицы Aсоответственно (см. §3.9д), то методы Якоби и Гаусса-Зейделя можнозаписать в видеx(k+1) − x(k)+ Ax(k) = b,D1иx(k+1) − x(k)(D + L̃)+ Ax(k) = b.13913.12. Теория А.А. СамарскогоНаконец, итерационный метод релаксации с релаксационным параметром ω (см. §3.9ж) в тех же обозначениях имеет форму Самарского(D + ω L̃)x(k+1) − x(k)+ Ax(k) = b,ωk = 0, 1, 2, .
. . .При исследовании сходимости итераций в форме Самарского удобнопользоваться матричными неравенствами, связанными со знакоопределённостью матриц. Условимся для вещественной n × n-матрицы Gписать G ⊲ 0, если hGx, xi > 0 для всех ненулевых n-векторов x, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
