Fletcher-1-rus (1185917), страница 45
Текст из файла (страница 45)
6.8.4. Методы ускорения сходимости Различные методы итераций, описываемые в п. 6.3.1 — 6.3.3, являются эффективными, но прн решении некоторых задач обнаруживают довольно медленную сходимость после того, как невязка 1! испытает быстрое начальное уменьшение. Если ошибку итерационного решения е = !Да~ — Ч' разложить в ряд Фурье, то быстрое начальное уменьшение невязка соответствует уменьшению амплитуды коротковолновых мод ряда Фурье. Последующее уменьшение амплитуды длинноволновых мод зачастую протекает со значительно меньшей скоростью.
Имеется, однако, возможность модифицировать уже рассмотренные нами итерационные методы для ускорения сходимостн. Два наиболее эффективных для этого метода — это метод ускорения по Чебышеву н метод ускорения с сопряженными градиентами (Надешап, Уоппд, 19811. Здесь мы дадим описание важнейших особенностей метода ускорения с сопряженн ым и градиентами. Первоначально будет предполагаться, что матрица А в уравнении (6.2) является симметричной н положительно определенной. Иначе говоря, прн любом выборе х будет хтАх ) О. й 6.3. Итерационные методы да< (6.75) имела минимум в направлении Р("> при Ч<"+'>.
Дискретизация уравнения Лапласа с центрированными конечно-разностными выражениями приводит к линейной системе уравнений, для которой матрица А симметричная и положительно определенная. Последовательность шагов при применении традиционного метода сопряженных градиентов (Нез(епез, 5!!е!е!, 19521 можно описать в следующем виде: Ч(н+ и Ч(н> ~„>„(н>Р(н> 2) Р(н+» = $~(н> — >>("><>("> 3) р("+и — (!>( +(>) 61("+о (не» 4) а(н+и = р р(н> 5) Р<"+'>= ат("">+ а("+иР("> (6.73) 6) 11(н+(> АР(н+>> (и.(-(> й( >— (р(а+и)г О(н+» Данный алгоритм оказывается сравнительно экономичным, так как он требует только одного матрично-векторного умножения на этапе (6).
Можно отметить, что невязка В(н+» вычисляется рекурсивно по результатам шага (2), а не из соотношения В("+» =  — АЧ'"+'>. За параметром р("+'> ведется наблюдение с целью уловить приближение сходимостн. В отличие от схемы ПВР (и. 6.3.!) метод сопряженных градиентов ие содержит эмпирически подбираемых параметров. В формулах (6.73) вектор Р'"> определяет направление поиска, которое в начале итерационного процесса задается равенством Р<о> = В(а>.
Выбор параметра а(н+» в формулах (6.73) гарантирует, что направления поиска Р('> будут взаимно сопряженными (ортогональными) в смысле выполнения условия Р<'> гАР<(> = О при ( ~ !'. (6,74) Кроме того, данный алгоритм обеспечивает, что К(огй((>=О при < Ф!'. Все эти особенности делают алгорйтм весьма эффективным и в отсутствие ошибок округления он мог бы способствовать построению решения системы из У линейных алгебраических уравнений (6.2) ие более чем за (Ч итераций. Параметр й<>о в формулах (6.73) выбирается так, чтобы эквивалентная квадратичная функция Р(Ч) О 5ЧтАЧ ЧтВ Гл. 6. Стацаоаарниа задачи Если невязка К разлагается в ряд по собственным функциям матрицы А, то можно установить, что каждый шаг метода сопряженных градиентов воздействует таким образом, что как бы приближенно исключает вклады от каждого из собственных векторов по очереди [Лепп1пдз, 1977Ь).
Следовательно, если некоторые из собственных значений А собраны в единую группу, то сходимость достигается менее чем за )Ч итераций. Если, кроме того, оказывается возможным произвести предварительное умножение отдельных членов уравнения (6.2) так, чтобы собственные значения полученной в результате матрицы были сгруппированы более тесно, чем для матрицы А, а разброс собственных значений ()! ), ) „) был несколько уменьшен, то последующее применение метода сопряженных градиентов к «предварительно подготовленной» системе обеспечивает более быструю сходимость.
Наилучший вариант выбова кондиционирующего множителя состоит в умножении на А-, так как после этого решение будет тривиальным. Хорошим вариантом является множитель 1з)-), фигурирующий в формуле (6.51), соответствующей итерационному методу решения стационарных задач общего вида. На этом основании вместо (6.2) запишем Я 'АЧ=))1 'В. (6.76) Чтобы можно было применять вышеописанный вариант метода сопряженных градиентов, необходимо комплекс М-)А сделать симметричным. Этого можно добиться, формируя комбинацию %Ь(-)А%-), где матрица % обычно выбирается так, чтобы получить %т% = Ь).
В результате вместо (6.76) получим АЧ=В, (6.77) где В=%Я 'В. А=%Ь) 'А% ', Ч =%Ч, Применение метода сопряженных градиентов к решению уравнения (6.77) называют методом сопряженных градиентов с предварительным кондиционированием. При хорошем выборе К этот вариант приводит к более быстрой сходимости, чем непосредственное применение метода к уравнению (6.2). На практике уравнение (6.77) не формируется явным образом. Вместо шагов, соответствующих формулам (6.73), делается следующее: Ч)л+!) Ч)л! 1 ! )л)р)л) 2) Ь! ч!) = Ь)л) — )))л)ц)л) р)л+!) =%Ь)л+!) =%$Ч )1т)л+!) 3) р'«+и= ф!"+!)) )с!"+!), $6.3.
Итерационные методы 4) а<а+ П = р(не П/р(л( 5) Р"+в= Ь<л+((+а(л+ПР(л' Р'"+П=%Р(л~" 11(л+П Ь -(АР(л~-П е((лео 1((<11(л+(( (а+ и 7 т(л+и р (р(л "( П)г () (л+(( (6.78) (6.79) где (л. <( (ХАЬ<л()г ри( (лАР(())Г р(п Ь(л Х 'Кл( Ф Л(л( = (ХАД(л))Г Р(л) (ядр(л))г р(л) Х=($Ч 'А) . Если сохранить все члены под знаком суммирования в выРажении для Р(л>, то реализация метода потребует значитель- В приводимой выше последовательности формул величины Ь и К играют роль псевдоневязок, а значение величины р<"+(> служит критерием близости к сходимости. Различные варианты выбора Х, а следовательно, и % соответствуют различным итерационным схемам, рассмотренным в п.
6.3.1. Таким образом, метод, основанный на применении формул (6.78), может интерпретироваться как основная схема с ускорением по методу сопряженных градиентов. Альтернативный, но очень эффективный вариант предварительного коидиционирования можно построить путем приближенной факторизации матрицы А и расщепления ее на нижнетреугольную и верхнетреугольную матрицы 1. и (1 [Ласкзоп, КоЬ(пзоп, 1985). Для случая конечно-разностной дискретизации стационарного уравнения переноса, не содержащего производной по времени (уравнение (9.81) ), результирующая система уравнений, эквивалентная (6.2), не будет симметричной вследствие влияния дискретизированных членов с первыми производными идТ/дх и идТ/ду.
Метод сопряженных градиентов может быть применен и к этому случаю при надлежащей модификации [Ахе!эзоп, Опз1а(эзоп, 1979]. Одна из таких схем под названием ОКТНОМ1Х, построенная в работе [Ч)изоте, 1976), описывается нами здесь. В принятых автором обозначениях формулы (6.78) заменяются следующими выражениями: Ч(л+и Ч(л( 1 т(л(Р<л( л-( Р<л(= Ь<л(+,), а(л (>Р«>, 264 Гл.
6. Стационарные задачи ного объема памяти и будет весьма неэкономичиной. На практике схема хорошо работает при ( = О, ..., 4. В работе [Маг!4Ьаш, 1984] проводится сравнение различных вариантов метода сопряженных градиентов с предварительным кондиционированием для несимметричных систем уравнений. Схема ОВТНОМ1Х является эффективной, однако Маркхэм находит, что метод дважды сопряженных градиентов [г!е(сЬег, 1976], а также модификации этого метода обладают большей эффективностью.
Тем не менее в работе [Ласкзоп, ВоЬ!пзоп, 1985] утверждается, что методы минимальной невязки оказываются эффективнее, чем метод дважды сопряженных градиентов, если решаемая задача обладает значительной степенью несимметричности. Таким образом, если матрица А имеет произвольную форму, то нельзя указать универсально предпочтительного метода сопряженных градиентов.
Имеется возможность симметризовать общую форму матричного уравнения (6.2), заменяя последнее на (6.80) АГАЧ = АГВ. В общем случае данный подход не может быть рекомендован, так как если матрица А в какой-то степени плохо обусловлена, то к матрице АгА это будет относиться в еще большей степени при вытекающей отсюда потере точности в процессе решения (6.80) относительно Ч. Однако в работе [КЬоз!а, ЯпЬ(п, 1981] уравнения, описывающие поток несжимаемой вязкой, жидкости вокруг кругового цилиндра при Ве = 100, были решены путем такой симметризации определяющих уравнений, как в (6.80), и применения схемы СНП (п. 6.3.3) в| сочетании с методом сопряженных градиентов при предварительном конднционировании.
Метод СНП как таковой требует приблизительно 240 итераций для достижения сходимости на сетке 61 Х 24, тогда как метод СНП с вышеуказанным дополнением требует для достижения сходимости всего около 40 итераций. б.3.5. Многосеточные методы Описываемые здесь методы применимы как к линейным системам (6.2), так и к нелинейным системам (6.1). Типичный вариант метода будет описан первоначально в применении к линейным системам, а в дальнейшем будет описано и его распространение на случай нелинейных систем. Многосеточиые методы имеют дело с последовательностью сеток, гп = 1, ..., М, при отношении размеров ячеек сетки Ь +з/б =0.5.
Линейная система, решение которой нужно по- й 6.3. Итерационные методы строить на наиболее мелкой сетке, записывается в виде АмЧм=Вм (6.81) Приближенное представление Чм соответствует решению на сетке, ближайшей в последовательности по степени грубости, т. е. Чм '. Подобным же образом решение Ч, построенное на сетке промежуточного размера, является хорошим приближением к решению на более мелкой сетке, ближайшей в последовательности к данной, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
