Слаботочка Книги

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 [194] 195 196 197 198 199 200 201 202 203 204 205 206 207 208

тах min \riax тгп

При h = hi = /i2 имеем X-min/max = 7r/i/4 + 0{h), поэтому

q=l- + 0{h).

Пусть e - точность, с которой необходимо найти решение системы уравнений (1). Нормы погрешностей = и - и и z~ =и-и ~ на соседних слоях связаны соотношением

Задача 3. Показать, что при т = Topt расчетные формулы (8) приобретают вид:

1+1 f I I I I А

ттт - \у-т+1,п + т~\,п + -m,n+l + то, n-1 j + топ

как в случае прямоугольника, так и в случае произвольной области.

Поэтому для выполнения неравенства достаточно вы-

брать п так, чтобы выполнялось неравенство </ е. Отсюда п1пд

In(e-i). Так как q= l2+0{h), то lnQ = \п{\-тхЧl2+0{h)) =

тх] 12 Л- O(h). При малых h имеем требование

Так как нас интересует случай малых е, т. е. когда точность решения системы достаточно высока, то второй член в правой части (9) может быть отброшен. Поэтому в данном случае количество итераций п по порядку должно быть равно 0(/i~ In(ei)).

На каждом шаге итерации матрица умножается на вектор. Отсюда может возникнуть впечатление о необходимости запоминания матрицы А. На самом деле это не так. Нам необходим лишь результат применения матриц!,! А к вектору v, который вычисляется по формулам

. . ч Vmn - Vm+l,n fm-l.n Vm,n+1 - Vm,n-1 {Av)mn =--

Поэтому матрицу A запоминать не надо.

Для вычисления значения функции (компоненты вектора) Av в одной точке требуется конечное число арифметических операций, поэтому на каждом шаге итерационного метода (8) затрачивается 0{h~) арифметических операций. Общее количество арифметических операций, необходимых для получения решения с точностью е, таким образом, равно

о(/г-1п(е-1)) = o(jV4Ine).

При этом метод (8) сходится со скоростью геометрической прогрессии и показатель скорости сходимости метода равен

В данном случае была описана схема применения метода простой итерации к решению системы сеточных эллиптических уравнений (1), аппроксимируюш,их исходную задачу в прямоугольной области; однако все рассуждения справедливы также и для случая произвольной области, если сетка выбирается равномерной, а граничные условия аппроксимируются их сносом в ближайший узел сеточной границы. Следует отметить, что при этом, вообще говоря, неизвестны точные границы A ii , Хтах спектра матрицы системы. Эти величины можно оценить, например, следующим образом. Пусть сеточный прямоугольник К со сторонами 1[ и 1. содержится в П/ а сеточный прямоугольник К со сторонами I и 1 содержит $7;,. (Узлы К являются узлами П/, и узлы $7/, являются узлами К .) Тогда имеет место соотношение

где А ; - минимальное собственное значение сеточной задачи Дирих.пе в прямоугольнике К, а А/ - максимальное собственное значение сеточной задачи Дирихле в прямоугольнике К , Выбирая г = 2/(А, + А ,.), можно приближенно находить решение системы уравнений (1) методом простой итерации с той же асимптотикой числа арифметических операций, что и в предыдущем случае.

Задача 4. Показать, что для итерациоипого процесса с чебышевским набором параметров требуемое число операций 0{N\\i\e\).

Задача 5. Получить такую же оценку числа действий для оптимального линейного итерационного процесса.

Задача 6. Получить такую же оценку числа действий для трехоюйного итерационного процесса (см. § 6.6, задача 3) с фиксированным итерационным параметром ш.

Задача 7. Показать, что средняя трудоемкость трехслойного итерационного процесса (см. § 6.6) с фиксированным параметром ш может быть снижена вдвое за счет следующего обстоятельства. При нахождении и при I четном вычисляются и запоминаются только значения в точках с четной суммой т + п, а при / нечетном - в точках с нечетной суммой т + п.

Заметим, что в случае прямоугольника в методе переменных направлений (21) (если его рассматривать как итерационный метод) можно указать последовательность переменных шагов по времени, при которой

общее число операций будет равно ОЛ lniV 1пе 1

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

dtdx dtdy dt

Задача 8. Доказать, что при определенном соотношении между шагами по i, ж, у сеточная аппроксимация этого уравнения превращается в метод сверхрелаксации для решения сеточного уравнения Au -f / = 0. В случае, когда область G есть квадрат и hi = /i2 = h, указать итерационный параметр 7, при котором число итераций для получения решения с

точностью е будет порядка -h~ ln(e~i).

Эффективными методами решения сеточных эллиптических уравнений являются интенсивно развиваемые в последнее время метод фиктивных компонент и многосеточный метод. По сути дела они также укладываются в общую схему построения итерационных методов, и проблема заключается в выборе соответствующего переобуславливателя.

В итерационном методе фиктивных компонент, предназначенном для решения сеточного уравнения Пуассона в области произвольного вида, на каждом шаге итерациопного процесса необходимо решать первую краевую задачу для уравнения Пуассона в некотором прямоугольнике, содержащем внутри себя эту область. Если для решения последней задачи применяется какой-либо из эффективных методов (например, марш-алгоритм), то при любом р для полуюния решения с точностью 0{hP) потребуется 0(/г~ ln/i) арифметических операций.

Метод Федоренко (называемый также многосеточным методом). К числу наиболее эффективных и употребляемых методов решения сеточных эллиптических задач (включая краевые задачи для систем уравнений Навье-Стокса) относится многосеточный метод, предложенный в шестидесятые годы. Сначала практическое использование этого метода носило эпизодический характер из-за неприспособленности существовавшего тогда программного обеспечения к использованию методов такого типа.

Основная идея этого метода заключается в следующем. Пусть решается сеточная краевая задача Ьи = Д. Подбирается некоторый итераци-

а трехслойные - как аппроксимацию уравнения ди ди

В случае необходимости решения более сложных стационарных задач для уравнений с частными производными часто идут по такому пути. Строят нестацпонарный процесс, сходящийся к решению задачи, а затем в качестве итерационного процесса берут дискретную аппроксимацию этого нестационарного процесса. Например, в случае уравнения Аи + / - О один из таких процессов установления описывается уравнением

ди ди ди

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 [194] 195 196 197 198 199 200 201 202 203 204 205 206 207 208