Если г1 и 8 вначале равнялись 10, то JBjS, а 8 1.446.

Верхние индексы используются здесь для обозначения номера итерации.

В заключение отметим, что для выполнения одной итерации может потребоваться до операций, однако для сильно разреженных матриц объем вычислений существенно сокращается.

Метод последовательной верхней релаксации. Метод последовательной верхней релаксации может быть использован для ускорения сходимости любого итерационного процесса, однако мы рассмотрим его в основном как метод, используемый для улучшения метода Гаусса - Зайделя. Про возникновение этого метода рассказывают одну любопытную (хотя, возможно, и вымышленную) историю о том, как один охотник обнаружил, что

В которой величина ui, / неизвестна, то легко расположить все уравнения рассматриваемой системы так, что наибольшие по величине коэффициенты будут расположены на главной диагонали. При некотором опыте и соответствующем выборе конечно-разностного аналога уравнений такое диагональное преобладание можно обычно обеспечить при решении любых уравнений эллиптического типа. Если разностное уравнение для и линейно, то можно ожидать, что метод Гаусса - Зайделя сходится в том случае, когда в тех узлах (/,/), в которых значения uij неизвестны, разностные уравнения имеют такой вид, что коэффициент при неизвестной / по абсолютной величине больше или равен сумме абсолютных величин коэффициентов при остальных неизвестных. Строгое условие больше должно выполняться хотя бы для одного уравнения.

Мы не будем приводить доказательство этого достаточного условия сходимости метода Гаусса - Зайделя, а просто попробуем на простом примере пояснить, почему оно должно выполняться. Вернемся к нашему примеру решения системы трех линейных уравнений итерационным методом Гаусса - Зайделя. В каждой точке промежуточное значение х, получаемое в ходе итераций, является суммой точного значения и некоторой погрешности 8, т. е. Xi = (xi)exact + 81 И Т. Д. Условис диагональ-ного преобладания гарантирует убывание е от итерации к итерации. Действительно, в рассматриваемом примере после одной итерации имеем

e?<V4e+V4B

И2<7бв? + 7зв

если он целится не в утку, а перед ней, то чаще попадает в цель. Утка - движущаяся мишень, и, предвосхитив ее движение, мы с большей вероятностью попадем в нее. Охотник рассказал о своем открытии соседу - специалисту в области вычислительной математики. Так, если верить этой истории, был создан метод последовательной верхней релаксации.

При решении системы алгебраических уравнений методом Гаусса - Зайделя для достижения требуемой точности приходится совершать несколько последовательных расчетов или итераций. Предположим, что мы наблюдаем за изменением значения неизвестной в некоторой точке на двух последовательных итерациях: тогда, определив направление и скорость ее изменения, можно предположить, что они сохранятся и на следующей итерации. Если пойти дальше, то можно задуматься: а не увеличится ли скорость сходимости итераций при коррекции в соответствии с этой тенденцией неизвестных до проведения следующей итерации? Коррекция неизвестных в любом итерационном методе (в этом разделе мы ведем речь о методе Гаусса - Зайделя лишь потому, что в данный момент изучаем именно этот метод) по формуле

KV) = к /) + «> («f.V - («?. /У) (4.122)

называется верхней релаксацией, или последовательной верхней релаксацией. Здесь k - номер итерации, - последнее значение неизвестной Uif, вычисленное по методу Гаусса - Зайделя, (uf - значение на предыдущей итерации, возможно уже скорректированное по предлагаемой формуле, если метод верхней релаксации применяется последовательно (на каждой итерации), а (wfY) - новое или «подправленное» значение Uij на {k -\- 1)-й итерации. Применяя этот метод, мы предполагаем, что (м+У будет ближе к точному значению неизвестной, чем значение wy, полученное методом Гаусса - Зайделя. Формула (4.122) применяется непосредственно в каждой точке на каждой итерации, а во все последующие расчеты входит величина (мУ), а не му. Коэффициент w называется параметром релаксации. Если 1 << 0) < 2, то говорят, что используется метод верхней релаксации. Верхняя релаксация в каком-то смысле аналогична линейной экстраполяции, проводимой по значениям

При решении некоторых задач применяют метод нижней релаксации (О < 0 < 1). Обычно его используют в тех случаях, когда сходимость решения в точке носит осциллирующий характер, причем в ходе итераций оно стремится как бы «превы-

сить» точное значение. В методе нижней релаксации «подправленное» значение (иу лежит между (wf и Метод последовательной верхней релаксации обычно дает хорошие результаты при численном решении задачи Дирихле для уравнения Лапласа. Метод нижней релаксации обычно используют при решении эллиптических уравнений лишь в том случае, когда уравнения нелинейные. Иногда при решении нелинейных уравнений сходимость численного метода обеспечивается лишь при использовании нижней релаксации.

Мы наложили на параметр релаксации условие О < 0 << 2. Введение такого ограничения на <о связано с тем, что по определению итерационный процесс сходится тогда, когда отличие и от точного решения убывает от итерации к итерации. При 02 это отличие будет либо не убывать, либо возрастать, т. е. такой итерационный процесс не может сходиться.

Пока еще мы не ответили на два очень важных вопроса: как выбрать хорошее и даже лучшее значение параметра о) и на сколько при этом ускорится сходимость итерационного процесса? Общих ответов на эти вопросы не существует, но можно привести некоторые полезные соображения.

Если уравнение Лапласа решается (по схеме (4.113)) в прямоугольной области на квадратной сетке (Ах = Ау = А), а на границе заданы условия Дирихле, то оптимальное значение параметра 0) (здесь и далее будем обозначать его через o)opt) можно определить теоретически согласно работам [Young, 1954; Frankel, 1950]. Это оптимальное значение 0 равно меньшему корню уравнения 20-16о)+ 16 = 0, где t = cos{n/p) + cos{n/q), а р и -число отрезков, на которые сетка разбивает каждую из сторон прямоугольника. Приведем один пример. Если р = q = = 45, то 0opt= 1.87. Однако в общем случае при решении более сложных эллиптических задач найти 0opt заранее не удается. В такой ситуации полезными для определения подходящих значений 0 могут оказаться численные эксперименты. Теория и численные эксперименты показывают, что обычно лучше задать более высокое, чем 0opt, а не более низкое значение параметра 0. Вопросы определения параметра 0opt рассмотрены в работах [Forsythe, Wasow, 1960; Varga, 1962; Ames, 1977].

Стоит ли тратить время и силы на поиск подходящих значений 0? Конечно, да, так как в ряде случаев время расчета удается сократить почти в 30 раз, а это существенно! Разумеется, в некоторых случаях метод последовательной верхней релаксации не дает сколь-нибудь заметного ускорения сходимости, но все равно его стоит попробовать применить, так как не следует игнорировать потенциальную возможность значительного уменьшения времени расчета.