Anderson-et-al-1 (1185923), страница 28
Текст из файла (страница 28)
Метод позволяет явным образом учесть разреженность матрицы коэффициентов. Приведем сначала пример, показывающий простоту рассматриваемого метода, а потом уже сформулируем достаточные условия его сходимости. В тех случаях, когда этот метод можно использовать, решение системы уравнений определяется следующим образом: (. Задается начальное приближение (при этом, как будет видно из приведенного ниже примера, значение одной из неизвестных можно не задавать). 2.
Из каждого уравнения определяют неизвестную, коэффициент перед которой имеет наибольшую абсолютную величину, при этом используются заданные начальные значения и уже вычисленные значения других неизвестных. 3. Процесс решения уравнений повторяется итерационно до тех пор, пока значения неизвестных на двух последовательных итерациях не будут отличаться на достаточно малую величину, при этом надо не забывать подставлять в правую часть каждого уравнения уже вычисленное значение неизвестной. В качестве примера рассмотрим систему уравнений 4х, — х, + ха = 4, х1+ бхе+ ха= — 9, — х, + 2х, + бхв = 2. 5 4.3 Уранненпе Лапласа 159 Сначала приведем ее к виду х/ — — '/4(4+ ха — ха), ха = //а(9 — х, — 2ха) ха = '/а(2+ х/ — 2ха) и зададим начальное приближение для х, и ха (начальное приближение для х/ задавать не надо).
После этого в ходе описанного выше итерационного процесса будем последовательно вычислять хь хк ха. (4. 120) то метод Гаусса — Зайделя сходится. Это достаточное условие сходимости, т. е. в ряде случаев метод может сходиться и тогда, когда указанные выше условия' не выполнены. Можно установить и необходимое условие, но пользоваться ими на практике не имеет смысла. Можно предложить и словесную формулировку достаточного условия сходимости метода Гаусса — Зайделя: метод сходится, если в каждом уравнении абсолютная величина коэффициента, расположенного на главной диагонали, больше или равна сумме абсолютных значений остальных коэффициентов уравнения и хотя бы в одном уравнении выполняется строгое условие больше (при решении физических задач обычно в уравнении, записанном для точки, расположенной вблизи границы). Воспользуемся теперь приведенными выше условиями сходимости итерационного процесса для анализа системы уравнений (4.113), которая была раньше получена при дискретизации уравнения Лапласа.
Прежде всего заметим, что наибольшим по абсолютной величине является коэффициент при неизвестной иь ь Так как уравнение (4.113) записывается в каждой точке, Достаточное условие сходимости метода Гаусса — Зайделя. Для упрощения записи перепишем систему уравнений так, чтобы по возможности максимальный по абсолютной величине коэффициент в каждой строке был расположен на главной диагонали. Тогда если система уравнений несводима (т. е. не может быть преобразована так, чтобы часть неизвестных определялась из решения системы с меньшим чем п числом уравнений) и если а !ап!> Х (ап! / ! / аа! для всех / и, кроме того, хотя бы для одного / !ап!> ~ !ап!, (4.
121) / 1 / а-"/ ИЮ Гл. 4. Метод конечных разностей для модельных уравнений в которой величина иь ~ неизвестна, то легко расположить все уравнения рассматриваемой системы так, что наибольшие по величине коэффициенты будут расположены на главной диагонали. При некотором опыте и соответствующем выборе конечноразностного аналога уравнений такое диагональное преобладание можно обычно обеспечить при решении любых уравнений эллиптического типа. Если разностное уравнение для и линейно, то можно ожидать, что метод Гаусса — Зайделя сходится в том случае, когда в тех узлах (з',/), в которых значения ид; неизвестны, разностные уравнения имеют такой вид, что коэффициент при неизвестной и;,; по абсолютной величине больше нлй равен сумме абсолютных величин коэффициентов при остальных неизвестных.
Строгое условие больше должно выполняться хотя бы для одного уравнения. Мы не будем приводить доказательство этого достаточного условия сходимости метода Гаусса — Зайделя, а просто попробуем на простом примере пояснить, почему оно должно выполняться. Вернемся к нашему примеру решения системы трех линейных уравнений итерационным методом Гаусса — Зайделя.
В каждой точке промежуточное значение х, получаемое в ходе итераций, является суммой точного значения и некоторой погрешности в, т. е. х1 =(х1)еласе+ в1 и т. д. Условие диагонального преобладания гарантирует убывание в от итерации к итерации. Действительно, в рассматриваемом примере после одной итерации имеем ! ~! ('/а1в~1+'/! а1 ) в3 ) ( 1/а 1 ва, ( + '/а ) в' ~ ( еа ~ ( '/а ~ в', ) + я/в ) ея (. Если е,' и е,' вначале равнялись 10, то (ее)(5, а (ез~(1.446. Верхние индексы используются здесь для обозначения номера итерации. В заключение отметим, что для выполнения одной итерации может потребоваться до аа операций, однако для сильно разреженных матриц объем вычислений существенно сокращается. Метод последовательной верхней релаксации.
Метод последовательной верхней релаксации может быть использован для ускорения сходимости любого итерационного процесса, однако мы рассмотрим его в основном как метод, используемый для улучшения метода Гаусса — Зайделя. Про возникновение этого метода рассказывают одну любопытную (хотя, возможно, и вымышленную) историю о том, как один охотник обнаружил, что 5 !.3.
Уравнение Лапласа !6! (4.122) называется верхней релаксацией, или последовательной верхней релаксацией. Здесь й — номер итерации, и,"+/' — последнее значение неизвестной и; /, вычисленное по методу Гаусса — Зайделя, (и~ )' — значение й/ / на предыдущей итерации, возможно уже скорректированное по предлагаемой формуле, если метод верхней релаксации применяется последовательно (на каждой итерации), а (ий+/')' — новое или «подправленное» значение и, / на (и+ 1)-й итерации.
Применяя этот метод, мы предполагаем, что (и~+/')' будет ближе к точному значению неизвестной, чем значение иь/+/', полученное методом Гаусса — Зайделя. Формула (4.122) применяется непосредственно в каждой точке на каждой итерации, а во все последующие расчеты входит величина (и1н')', а не иьн'. Коэффициент а называется параметром релаксации. Если 1 а ( 2, то говорят, что используется метод верхней релаксации. Верхняя релаксация в каком-то смысле аналогична линейной экстраполяции, проводимой по значениям (иь )' и ил+'. /,/) /,/ ' При решении некоторых задач применяют метод нижней релаксации (О ( а - 1). Обычно его используют в тех случаях, когда сходимость решения в точке носит осциллирующий характер, причем в ходе итераций оно стремится как бы «превы- 6 Д Андерсон н нр.
Том ! если он целится не в утку, а перед ней, то чаще попадает в цель. Утка — движущаяся мишень, и, предвосхитив ее движение, мы с большей вероятностью попадем в нее. Охотник рассказал о своем открытии соседу — специалисту в области вычислительной математики. Так, если верить этой истории, был создан метод последовательной верхней релаксации. При решении системы алгебраических уравнений методом Гаусса — Зайделя д/(я достижения требуемой точности приходится совершать несколько последовательных расчетов или итераций. Предположим, что мы наблюдаем за изменением значения неизвестной в некоторой точке на двух последовательных итерациях: тогда, определив направление и скорость ее изменения, можно предположить, что они сохранятся и на следующей итерации.
Если пойти дальше, то можно задуматься: а не увеличится ли скорость сходимости итераций при коррекции в соответствии с этой тенденцией неизвестных до проведения следующей итерации? Коррекция неизвестных в любом итерационном методе (в этом разделе мы ведем речь о методе Гаусса— Зайделя лишь потому, что в данный момент изучаем именно этот метод) по формуле (и/+')' =(ин )'+ а(ил+' — (и/ь )') 162 !'л. Л.
Метод конечных разностея для модельных уравненнй сить» точное значение. В методе нижней релаксации «подправленное» значение (иа+')' лежит между (иа,.)' и иа+,.'. Метод последовательной верхней релаксации обычно дает хорошие результаты при численном решении задачи Дирихле для уравнения Лапласа. Метод нижней релаксации обычно используют при решении эллиптических уравнений лишь в том случае, когда. уравнения нелинейные. Иногда при решении нелинейных уравнений сходимость численного метода обеспечивается лишь при использовании нижней релаксации.
Мы наложили на параметр релаксации условие 0 < го < 2. Введение такого ограничения на то связано с тем, что по определению итерационный процесс сходится тогда, когда отличие и от точного решения убывает от итерации к итерации. При «о ) 2 это отличие будет либо не убывать, либо возрастать, т.е. такой итерационный процесс не может сходиться. Пока еще мы не ответили на два очень важных вопроса: как выбрать хорошее и даже лучшее значение параметра оу и на сколько при этом ускорится сходимость итерационного процессар Общих ответов на эти вопросы не существует, но можно привести некоторые полезные соображения.
Если уравнение Лапласа решается (по схеме (4.113)) в прямоугольной области на квадратной сетке (Лх = Ау = Ь), а на границе заданы условия Дирихле, то оптимальное значение параметра ео (здесь и далее будем обозначать его через го,р~) можно определить теоретически согласно работам [Уонип, 1954; Ггап)те1, 1950]. Это оптимальное значение ео равно меньшему корню уравнения 1аеоа — 16ат + 16 = О, где 1 = соз(п/р) + соз(те/д), а р и д — число отрезков, на которые сетка разбивает каждую из сторон прямоугольника.
Приведем один пример. Если р = д = = 45, то го ве = 1 87. Однако в общем случае при решении более сложных эллиптических задач найти ео,р~ заранее не удается. В такой ситуации полезными для определения подходящих значений ы могут оказаться численные эксперименты. Теория и численные эксперименты показывают, что обычно лучше задать более высокое, чем оу,рь а не более низкое значение параметра го. Вопросы определения параметра оу,в~ рассмотрены в работах 1гогзу(Ье, 0/азочт, 1960; Магда, 1962; Агпез, 1977].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
