Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 64
Текст из файла (страница 64)
Кроме того, прн этом предположении можно показать, что спектральный радиус матрицы В меньше единицы, так что итерации (8.4.28) будут сходиться при любом начальном приближении ие. Скорость сходи- мости зависит от параметра а. На самом деле оказывается, что скорость сходимости может быть значительно увеличена, если использовать несколько различных значений параметра а,,..., а„„повторяя их циклически. При правильном выборе значений а; (описание того, как это делается, выходит за рамки настоящей книги) итерации Писмэна — Рэчфорда сходятся очень быстро.
Метод Писмэна — Рэчфорда применим и к эллиптическим задачам более общего вида, чем мы здесь рассматривали.Для сходнмостн итераций (8.4.28) достаточно положительной определенности матриц Н и Р" и выполнения ус- где А — трехдиагональная матрица (7.2.14) с элементами 2 и — 1; матри- ца 1' получается из Н перестановкой строк н столбцов, причем ее действие на вектор и приводит к вычислению разности по индексу1, как это указа- но в (8.4.24).
В вектор Ь входят переменные и~;нз (8-4.24), значения-кото- рых известны из граничных условий, и если мы имеем дело с уравнением Пуассона, то также значениями~;. Обратите внимание, что уравнение (а1 + Н) и = (а1 — У) и + Ь, или, после взаимного уничтожения членов а1и в левой н правой частях, (Н+ $') и = Ь, точно совпадает с уравнением (8.2.10) . Действительно, если матрицу коэф- фициентов в (8.2.10) обозначить через А, то А = Н+ г, где матрица 1" име- ет отличными от нуля только главную диагональ, все элементы которой равны 2, и две параллельные диагонали с элементами — 1 (см.
(8.2.10)) . Аналогичным образом (8.4.25) можно переписать в виде ловия а ) О. Однако возможность выбора последовательности значений параметра, которая обеспечивает быструю сходимость, тесно связана с предположением о прямоугольной форме области и о том, что само уравнение м~!ет вид и„„+ и + ои ='О. Мы закончим этот раздел кратким описанием одного метода, играющего все более важную-роль, который по существу является прямым (т.е.
реше.ние линейной системы находится за конечное число операций), но на практике используется как итерационный. Мы имеем в виду метод солряхгенных градиентов. Мы сначала опишем сам метод, а затем обсудим идеи, на которых он основан. Предположим, что матрица А коэффициентов линейной системы является симметричной и положительно определенной, и пусть (х, у) =— х у означает евклидово скалярное произведение векторов х и у. Тогда алгоритм метода сопряженных градиентов можно сформулировать следующим образом. 1. а) Выбрать начальное приближение.Р; б) вычислить г = Ь вЂ” Ахо; в) положитьро =г и1е =О.
2. а) Вычислить а„= (г", р")/(р~, Ар"); б) вычислить х»+ =х + а»р»; в) вычислить|~+1 =г" — а»Ар»; г) проверить сходимость: ~~ г "+' 1~ < в? Если нет, то продолжить алгоритм. 3. а) Вычислить |3» = (г"+', Ар")1(р"„Ар~); б) вычислитьр ' =т " — д»р»; в) увеличить 1 на 1 и вернуться к шагу 2.а).
Мы теперь сделаем несколько замечаний по поводу этого метода. Во-первых, этот метод наиболее естественно рассматривать как метод миними- Рнс, 8.19. Минимизация квадратичной формы в направлении р » зации. Так как матрица А положительно определена, то квадратичная форма — хАх — хЬ т т (8.4.30) 2 имеет минимум, и вектор х', на котором этот минимум достигается, является решением системы Ах = Ь. Если мы имеем текущее приближение х" и задающий направление вектор р, то следующее приближение х»+' находится в результате минимизации квадратичной формы (8.4.30) вдоль направления р, исходящего из точки х" (рис. 8.19).
Но это просто одномерная задача минимизации: »» т Мш — (х" +ар ) А (х +ар ) — (х" +ар") Ь. о 2 (8.4.31) 272 Если раскрыть здесь скобки и сгруппировать члены при одинаковых степенях о, то легко видеть, что квадратичная форма в (8.4.31) представляет собой квадратичный полипом относительно а. Значение а, которое минимизирует этот полинам, вычисляется по явной формуле, приведенной в шаге 2.а) алгоритма.
Теперь мы должны вычислить вектор невязки г»" = Ь вЂ” Ах"". Это можно было бы сделать непосредственно, но так как Ь вЂ” Ах~+ =Ь вЂ” А (х + а»р") =㻠— а»Ар~, а вектор Ар" нам уже известен, невязку можно определить, не формируя вектор Ах"+'. Далее мы проверяем условие сходимости, сравнивая ~~ г "11 с некоторым заданным допуском е.
(Отметим здесь, что в качестве условия сходимости мы могли бы использовать и целый ряд других критериев.) Если условие сходимости не выполняется, то мы на шаге З.б) определяем новое направление р"+' и возвращаемся к шагу 2.а) для вычисления следующего приближения. Центральной частью алгоритма является определение направлений р». Эти направления должны удовлетворять условиям (р',Ар')=О, 1Ф/, !',/=0,1,...,п — 1. (8.4.32) Действительно, так как (р, Ар") =(г~+~ Д»р~ Ар») (г»+1 Ар») ф (р» А1э») мы видим, что значение 1э» выбирается из условия (р ", Ар") = О.
Чтобы показать, что соотношение (8.4.32) выполняется и при других значениях 1 и 1', необходимо проделать некоторые преобразования и воспользоваться методом индукции (см. упражнение 8.4.10) . Направления ~ р» ~, которые удовлетворяют (8.4.32), называют сопряженными относительно матрицы А.
Можно показать, что если соответствующие приближения х~+' вычисляются по формулам шагов 2.а) и 2.б) алгоритма, то не более чем за и таких шагов мы получим точное решение линейной системы Ах = Ь. Именно благодаря этому свойству метод сопряженных градиентов относится к прямым методам решения линейных систем. Имеются, однако, два обстоятельства, которые при практических расчетах не позволяют воспользоваться этим свойством. Во-первых, иэ-за ошибок округления полученное за и шагов приближенное решение может значительно отличаться от точного и нам придется продолжить выполнение алгоритма.
С другой стороны, если мы заложим в алгоритм условие остановки через и шагов, то в случае очень больших матриц, скажем и = 10000, он не сможет выдержать конкуренции с другими итерационными методами, дающими приемлемое приближенное решение за значительно меньшее число итераций. Практическое использование метода соппяженных градиентов тем не менее показало, что во многих реальных задачах сходимость достигается гораздо быстрее, чем за я итераций, так что этот метод и его многочисленные варианты составляют привлекательную альтернативу другим итерационным методам, описанным в настояшем разделе. В этом разделе мы познакомились с некоторыми простейшими итерационными методами решения больших разреженных систем линейных урав- ! 8.
дж. Ортега пений, особенно систем, которые возникают при применении раэностных методов к эллиптическим уравнениям в частных производных. Имеется и целый ряд других итерапнонных методов (некоторые из них упоминаются в дополнительных замечаниях), так что вопрос о том, какой метод испольэовать при решении данной конкретной задачи, обычно вызывает определенные затруднения. Кроме того, в последнее время выяснилось, что описанные в предыдущем разделе прямые методы работают на больших разреженных матрицах более эффективно, чем можно было предположить заранее. В настоящее время, по-видимому, можно сказать, что для двумерных эллиптических уравнений следует предпочесть прямые методы, а для, решения трехмерных задач лучше воспользоваться итерационными методами. Дополнительные замечания и ссылки 8.4 Итерации Якоби н Гаусса — Зейделя являются классическими методами, восходящими к прошлому столетию.
Метод последовательной верхней релаксации возник из эвристических релаксационных методов, доведенных до высокой степени савершвясша Саусвеллом н ега сотрудниками ва время второй мировой войны. Основы теории зтога метода разработали в конце 1940-х гадов Франкел н Янг. Подробное рассмотрение методов Якоби и Гаусса — Зсйделя, метода последовательной верхней релаксации, неявных методов переменных направлений, а также многочисленных разновидностей этих методов имеется в книгах [7,89,109]. С помощью пошпия неразложимой матрицы теорема 8.4.2 мажет быть обобщена таким образом, что она становится применимой к уравнениям вида (8.4,9). Матрица А называется рэзаожцмой, если существует такая матрица перестановок Р, что *) РАР= ~ ] В противном случае матрица называется неразложимой.
Теорема 8 4 2 теперь обобщааэ ся следующим образом. Предположим, что матрица А является неразложимой и диагонально доминирующей, причем хотя бы адно из соотношений ]ли ] > Ц;ь1]ат7 ] (1 = 1, ..., л) вьпюлняется как строгое неравенство, Тогда система уравнений Ах = Ь имеет единственное решение х' и как итерации Якоби, так и итерации Гаусса — Зейдсля сходятся к х' при любом 'начальном приближении х'. Можно показать, что матрица коэффициентов уравнений (8.4.9) неразложима и что к ней применима только что сформулированная теорема. Метод сопряженных градиентов бьш разработан в начале 1950-х годов [95], прнчем в последние несколько лет интерес к этому методу как итерационному алгоритму решения больших разреженных систем уравнений сильно возрос.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
