ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 305
Скачиваний: 6
§ 3. Итерационные методы и сходимость |
177 |
ке CDG 6600. Время выполнения одной итерации на сетке 128 X X 128 составило 0,154 с. Это, вероятно, отвечает оптимальному случаю, так как в цикл не был включен логический блок для определения максимальной поправки — часть, которая обяза тельно должна содержаться в рабочей программе для того, чтобы оценить ошибку. Добавление такого логического блока приведет к дальнейшему увеличению времени работы программы, так как размер внутреннего цикла превысит размеры быстрого блока команд. Мы видели (табл. 3), что прямой метод позволяет решать раз ностные уравнения за 0,75—0,94 с в зависимости от граничных условий. Таким образом, прямой метод определяет решение раз ностных уравнений за время пяти или шести итераций метода SOR.
2. Циклический метод Чебышева
Если несколько изменить нечетно-четный процесс SOR, то можно улучшить априорную оценку скорости на много порядков. Единственное отличие заключается в том, что в этом циклическом методе Чебышева значение параметра верхней релаксации со изме няется через каждые пол-итерации по следующей схеме [22]:
со<0> = |
1, |
со( Ѵ г ) : |
(63) |
(0(«+V2) : |
, t = X/2 , 1, 3/ 2, . . ., оо. |
|
і —4- |
Первая полуитерация определяется как первая прогонка по нечетным узлам сетки, вторая — как первая прогонка по четным узлам, третья — как вторая прогонка по нечетным узлам и т. д. Можно показать, что со(°°)= (щ, следовательно, этот процесс пред ставляет собой процесс SOR с параметром верхней релаксации, изменяющимся от 1 до соь. Как в методе SOR, так и в методе Чебы шева предельная асимптотическая скорость сходимости прини мает одно и то же значение, равное сщ — 1 за итерацию.
Для сетки 128 X 128 соъ = 1,9521, и, следовательно, норма ошибки асимптотически уменьшается на 5% за итерацию. Однако априорная оценка начальной скорости сходимости гораздо лучше
в методе Чебышева, что видно из фиг. 7 для сетки 128 X |
128. |
|
Для циклического метода Чебышева имеем [22] |
|
|
\\ мт\\ = - ^ - ( \ \ р 21^ |
+ \ \ р , 4 У \ |
(64) |
где |
|
|
т ы * ъ - і ) ' » |
1+(£ _ ф . |
|
12—01236
178 |
Гл. 4. Методы расчета потенциала |
Можно показать, |
что ЦЛ/4*11| всегда убывает с увеличением t\ |
и для п = 128 асимптотическая скорость достигается после гс/4 итераций. Уменьшение ошибки до 1% обеспечивается после 108 итераций, а до 10~6 — после 295. Тем не менее даже при этой улуч шенной сходимости можно гарантировать уменьшение ошибки лишь в 0,96 раза за время, равное времени работы прямого метода.
Причину того, что для установления асимптотической скоро сти сходимости необходимо примерно п!2 итераций, можно наглядно представить себе на специальном случае одиночного заря да, помещенного в крайней правой стороне сетки. Рассматривая место на сетке, в котором происходит изменение при каждой ите рации, можно заметить, что в случае нечетно-четной последова тельности потребуется п/2 итераций, прежде чем какое бы то ни было изменение, связанное с этим отдельным зарядом, произойдет на левом краю сетки.
Факт успешного использования итерационных методов многими авторами [23, 20, 21, 24] говорит о том, что на практике обычно встречаются довольно хорошие векторы начальных ошибок. Тем не менее указанные выше наихудшие случаи могут возникнуть, и они служат предостережением против применения итерацион ных методов без соответствующего изучения скорости сходимости в рассматриваемой частной задаче. Чтобы оценить скорость схо димости, которая, по-видимому, возникает в реальных задачах, рассмотрим два варианта: случайную ошибку и ошибку, вызван
ную движением |
заряженного стержня. В последнем случае мы |
изучим влияние |
хорошего и плохого начального приближения. |
|
3. Случайная ошибка |
На фиг. 8 показано использование трех сеток при изучении случайной ошибки. Сначала создавалось случайное распределение потенциала ф* на первой сетке. На второй сетке с помощью диф
ференцирования, использующего |
разностные уравнения |
|
9 ь У = = ф г * - 1 , 1 + ф 1 и , 1 + |
Ф г * , ; - 1 + ф г * і + 1 ~ 4 ф г * j , |
( 6 5 ) |
определялось распределение заряда q, создающего потенциал ф*. Таким образом, ф* является точным решением разностного урав нения при распределении заряда q. Затем на третьей сетке исполь зовалась итерационная процедура для определения последователь ных приближений, т. е. фФ. Мы выбирали ф(0)=г 0, и, следова тельно, начальное распределение ошибок было случайным. Так как известно точное решение разностных уравнений, на каждой итерации можно вычислить среднеквадратичную норму погреш ности. На фиг. 9 показана эта норма для различных итерацион ных процедур.
§ 3. Итерационные методы и сходимость |
179 |
Сначала отметим, что в методе SOR при со = а>ь после неболь шого начального роста ошибка убывает почти с асимптотической
Сетка 1 |
Сетка Z |
Сетка '3 |
Ф и г. 8. Использование трех сеток при исследовании случайной ошибки.
Символ Vft означает конечно-разностную аппроксимацию оператора Лапласа (65).
скоростью. Однако если положить со = 1, превращая таким обра зом метод SOR в итерационной процесс Гаусса — Зайделя без
Ф и г . 9. Зависимость нормы вектора ошибок от числа итераций для слу чайной начальной ошибки на сетке 128 X 128 при применении методов SOR (1), Гаусса — Зайделя (2) и Чебышева (3).
верхней релаксации, то убывание начальной ошибки делается гораздо более быстрым: за первые шесть итераций ошибка умень-
12*
180 Гл. 4. Методы расчета потенциала
шается на порядок. Но впоследствии спадание ошибки в процессе Гаусса — Зайделя становится безнадежно медленным, прибли жаясь асимптотически к величине ц2 = cos2 (я/гг) за одну итера цию. Для сетки 128 X 128 это составит 0,9949 за итерацию, что следует сопоставить с коэффициентом спадания 0,95 за итерацию в случае со — (о&. При асимптотической скорости спадания [18] процедура Гаусса — Зайделя требует 2,3 гг2/я2 (=4000 при гг = = 128) итераций для уменьшения ошибки в 10 раз, в то время как метод SOR при со = соь требует 2,3 гг/2л (=47 при гг = 128) ите раций. Это показывает, насколько медленной может быть сходи мость при использовании мелкой сетки и насколько важно исполь зовать наилучшее значение параметра со в процессе SOR, если требуется значительное уменьшение ошибки.
Мы видели, что в отношении начальной скорости спадания ошиб
ки значение с о = 1 |
лучше, чем ( |
о = |
с |
&;о |
в отношении же асимпто |
||
тической |
скорости |
спадания с |
о = |
с |
щ |
в огромной степени пре |
|
восходит |
со = 1. Это подсказывает, |
что метод Чебышева, плавно |
|||||
изменяющий значение параметра с о |
от 1 |
до с ьо , может объединить |
|||||
в себе достоинства |
обоих значений |
с |
о |
Третья. |
кривая на фиг. 9 |
||
показывает, что для случайной ошибки метод Чебышева в самом деле превосходит метод SOR. Довольно странно, что для первых 80 итераций и метод Чебышева, и метод SOR уступают методу Гаусса — Зайделя. Возможно, это характерная особенность слу чайной ошибки. Такое преимущество метода Гаусса — Зайделя исчезает при более реалистическом распределении ошибок, рас смотренном в п. 4. Поскольку метод Чебышева, являясь незначи тельным изменением метода SOR, характеризуется лучшей ско ростью сходимости, представляется неоправданным применение непосредственно самого метода SOR.
4. Влияние хорошего начального приближения
Для численного моделирования плазмы типично перемещение некоторых зарядов на расстояние одного пространственного шага сетки за один шаг по времени. Поэтому мы в качестве простого контрольного примера взяли заряженный стержень шириной в две пространственные ячейки, который за один шаг по времени перемещается на одну ячейку в сторону. Этот пример разумно описывает и движение ветви галактики в гравитационной модели.
Выбранная сеть характеризуется индексами 0 ^ і, / < 128
с граничным условием срг, j = 0 при г, j — 0, |
128. |
Вначале еди |
|
ничные заряды помещались в узлы |
г = 63, / = |
32 |
96 и г = 64, |
і"— 32_96, что соответствовало |
расположению |
заряженного |
|
стержня немного левее центра. Затем по методу Чебышева опре делялся потенциал исходя из начального приближения ср = 0. После 500 итераций максимальная невязка уменьшалась до ІО-9,
§ 3. Итерационные методы и сходимость |
181 |
а теоретическая оценка обеспечивала уменьшение нормы ошибки по крайней мере до ІО-11. Результат рассматривался как точное решение.
После этого стержень сдвигался на одну ячейку вправо, как показано на фиг. 10, и, следовательно, занимал столбцы і — 64 и г = 65. Для этого нового распределения заряда точное решение было известно, поскольку оно совпадало с зеркальным отраже нием ранее вычисленного решения относительно центрального столбца і = 64. Проверка состояла в итерационном определении
|
|
|
65 |
|
|
96 |
|
|
|
|
|
|
9 |
• |
|
|
|
9 |
« |
|
|
|
X • |
|
|
|
|
• • |
|
|
|
|
• |
О |
— |
зг |
|
9 |
9 |
|
9 |
9 |
||
|
О - |
- --і |
64 |
т |
а .)П р ед ы д ущ и й , ш а г |
|
б)Последующий шаг |
||
Ф и г . 10. Расположение заряда до (а) и после (б) перемещения заряженного стержня на одну ячейку слева направо.
Исходное и последующее' положения зеркально симметричны относительно центрального ряда і = 64. Крестиком отмечен узел, в котором проводился контроль поля.
нового распределения потенциала, начиная или с ф = 0 («плохое» приближение), или с потенциала, вычисленного при старом рас положении стержня («хорошее» приближение). Так как было известно точное решение, можно было вычислять норму ошибки.
На фиг. 11 показано отношение нормы ошибки к норме точного решения в зависимости от числа итераций. Этот результат показы вает, что самым лучшим является метод Чебышева. Скорость схо димости в этом методе примерно одна и та же как для хорошего, так и для плохого приближения, и форма кривой близка к форме предельной кривой на фиг. 7. При хорошем начальном прибли жении шесть итераций дают уменьшение ошибки лишь до 0,78 начальной величины; для уменьшения же до 0,1 необходимо 57 ите раций, и 105 итераций снижают ошибку до 1%. Соответствующие цифры в случае плохого начального приближения составляют 0,95 за 6 итераций и 61 итерация для уменьшения ошибки до 0,1.
Хотя начальная скорость сходимости выше в случае хорошего приближения, основное различие между случаями хорошего и пло-
182 Гл. 4. Методы расчета потенциала
хого приближений заключается в том, что величина начальной ошибки для первого из них составляет лишь 1/40 от начальной
Фиг. 11. Зависимость нормы ошибки (в единицах нормы точного решения) от числа итераций на сетке 128 х 128 при перемещении заряженного стержня на одну ячейку для случаев хорошего и плохого начальных приближений.
1 — метод Гаусса — Зайделя, 2 — метод SOR, 3 — метод Чебышева.
ошибки второго. Оценим накопление ошибок, если наряду с опре деленным снижением ошибки на каждом шаге систематически вно сится дополнительная погрешность. Для этого будем рассматри вать векторы как скаляры и используем следующее грубое рас суждение.
Предположим, что каждый шаг вносит ошибку а и что умень шение ошибки за один шаг характеризуется коэффициентом А. Тогда
е <0,= а, |
е(1) = |
аА + |
а |
|
и после t шагов по времени |
|
|
|
|
е т ^ а ^ + А '^ф- . . . + А + 1] = |
(66) |
|||
__ а (1 — Ат |
) |
|
|
(67) |
1 —'А |
|
|
|
|
Следовательно, е<00) = а/(1 — |
А,), так |
как |
А < 1. |
|
§ 3. Итерационные методы и сходимость |
183 |
Если в нашем примере брать всего шесть итераций на один шаг, то Я = 0,83 и е(°°> == 6а. Таким образом, окончательная ошиб ка в системе равна шестикратной ошибке одного шага, что в нашем случае, где а = Ѵ^, составляет 15%.
Выборочной проверке подвергалось также поле в центре систе мы і = 64, і — 64. При перемещении стержня это поле должно изменить направление на противоположное, и так как оно дей ствует на элементы стержня, особенно важно вычислить его пра вильно. Относительная величина ошибки поля убывает довольно быстро как для плохого, так и для хорошего приближения. В обоих случаях относительная ошибка составляет 10-1 после 4 итераций, ІО-2 после 25 итераций и ІО“3 после 100 итераций. Однако резуль тат для «хорошего» начального приближения несколько хуже, чем для «плохого». Вызвано это, видимо, тем, что нулевое поле, заданное как «плохое» начальное приближение, ближе к истинному чем противоположное поле, взятое с предыдущего шага по вре мени и использованное в качестве «хорошего» начального прибли жения.
5. Условия сходимости
Мы видели, что не часто представляется возможность прово дить итерационный процесс с таким числом итераций, которое обес печивает значительное уменьшение ошибки. На практике обычно проводят итерации до тех пор, пока не будут выполнены некоторые условия сходимости. Поскольку точное решение неизвестно, пря мое измерение истинной ошибки невозможно и ошибку прихо дится оценивать, исходя из измеряемых величин, например из ве личины невязки или изменения в решении по сравнению с пре дыдущей итерацией. Ниже мы рассмотрим оба случая.
Предположим для простоты, что итерационный процесс уста новился таким образом, что остался один преобладающий вектор ошибок с собственным значением Я. Для метода SOR при ю = сщ все собственные значения по модулю равны соь — 1. Два из них вещественны. Пусть — результат, а гW — истинная ошибка jf-й итерации. Тогда изменение за t-ю итерацию составит
Д<*, = е(*+1>—е(І) = (Я—1) е(і).
Следовательно,
8<*> = (Я—I)“1А<г>
или
|
т |
—!Т 1 |
J |
<1 |
Для сетки 128 X 128 (Оь = 1,9521 и Я = 0,9521, поэтому
(68)
(69)
(70)
II в® II = 20||Д(0||. |
(71) |
