|
| |
|
Слаботочка Книги повторного применения этой процедуры норма погрешности решения на сетке с шагом h умножится на множитель не больший 0,25. В итоге после двукратного использования алгоритма уменьшения погрешности в 4 раза на сетке с шагом 2h, осуществляя дополнительно не более C{2)N арифметических операций, мы получаем алгоритм уменьшения погрешности в 4 раза на сетке с шагом h. Обозначим число арифметических операций, достаточное для уменьшения погрешности в 4 раза на сетке с шагом hi = 2~ через Z{1). Полученный выше результат можно записать в виде неравенства Z{1) 2Z(l-l) + C{2)2. Функция W{1) = С(2) 12 удовлетворяет уравнению W{1) = 2W{l~l) + C{2)2. При 1 = 1 рассматриваемую сеточную задачу можно решить, совершив не более чем 3 арифметические операции. Поскольку С(2) > 2, то Z{1) W{1). Индукцией по I можно получить оценку Z{1) W{1) = 0{N \og2 N) при N = 2К Если требуется добиться уменьшения погрешности в М раз, то будет достаточно [l-blog4M] итераций, и, таким образом, общее число действий, требуемое для решения задачи, будет 0(A/log2 A/log2 М). Эта оценка хуже, чем оценка 0{N) числа действий методов прогонки или стрельбы. Однако в рассматриваемом методе можно уменьшить число арифметических операций. Во-первых, можно показать, что при некотором видоизменении итерационного процесса (10) при решении задачи на сетке с шагом h достаточно лишь один раз обращаться к решехшю задачи на сетке с шагом 2/г. В результате этого число операций, требуеьюе для уменьшения нормы погрешности на сетке с шагом /г в 4 раза снижается до 0(Л). Можно предложить другой вариант уменьшения нормы погрешности, например, в 4 раза на сетке с шагом h = 2~ с затратой 0{N) арифметических действий. Положим tjj = 1/(4(Z - j + l)),mj = [4(Z ~ j + 1) x (Z - j-b2)0,59]-Ы при j = l,... ,m,i. Применим описанный вьппе алгоритм последовательного сведения решения задачи на сетке с шагом hj = 2~ к решению задачи на сетке с шагом hj = 2~~\ при этом для каждого у = Z,... ,2 производим nij итераций по формуле (10) при T = Tj = hj/4:. Задачу на сетке с шагом hi = 1/2 решаем точно. Задача 11. Доказать, что при таком выборе rjj и ruj погрешность решения на сетке с шагом h = 2~ уменьшится в 4 раза, а общее число арифметических действий, затрачиваемое при этом, есть 0(N). При решении задачи суш,ественно используется то, что при всех j выполняются наравенства t]j t]j-.i + 0,59/mj. Во вторых, можно принять во внимание следуюш,ее обстоятельство. При дважды дис1)ференцируемой /(ж) решения задач на сетках с шагами 2~ и 2 отличаются иа 0(2 ). Поэтому можно поступить следующим образом. Задаемся некоторой последовательностью убывающих величин ei = const -2 . Последовательно решаем задачи на сетках с шагами h/ = 2~(~1) с погрешностью итерационного процесса порядка <5/ i, и получившиеся приближения берем в качестве исходных для итераций на сетке с шагом hi = 2~. При этом оказывается, что при каждом I требуется лишь конечное число итераций описанного выше вида. В резуньтате {решение исходной сеточной задачи будет получено с похфешпостью О {l/N) при общем числе арис}зметических операций 0{N). В рассматриваемом случае при некотором видоизменении итерациопного процесса (10) в результате одного полного цикла итерации - спуска от шага h = 2~ до niai-a h = и возвращения к шаху /( = 2 с общей затратой 0{N) арифметических операций получается точгюе решение сеточной задачи. Однако этот факт носит случайный характер и не относится к более сложным задачам. Рассмотрим случай размерности задачи я > 1. Пусть используется рассмотренный алгоритм сведения решения задачи иа сетке с шагом h к решению задачи на сетке с шагом 2h и число таких сведений при каждом шаге равно у > 1. Для весьма широкого класса задач можно доказать существование £{q) > О и m{q) < оо, удовлютворяющих следующим соотношениям. После (-кратного применения описаиной выше процедург.1, состоящей из m{q) итераций (10), перехода к задаче па сетке с шагом 2h, решения задачи на этой сетке с помощью алгоритма S и перехода на сетку с шагом h, некоторая норма погрешности решения задачи на сетке с шагом h уменьшается в \/e{q) раз. Естественно, что операторы перехода с одной сетки на другую П и 12/1 будут иными, чем выше. Обозначим число арифметических операций, достаточное для уьюнь-шения погрешности в l/e{q) раз на сетке с шагом h = 2~, через Z{1). Справедливо неравенство Z{1) qZ{l - 1) 4- Co(s,(?)2*. Отсюда при 9 < 2* можно получить неравенство Z{1) Ci(s, (?)2*. Таким образом, общее число действий, достаточное для уменьшения погрешности на сетке с шагом h в l/£{q) раз, будет порядка 0{h~), то есть порядка 0{N), где N - общее число узлов сеточной задачи. Высказанные выше утверждения относятся и к случаю аппроксимаций метода конечных элементов. Литература 1. Бахвалов Н.С. О сходимости одного релаксационного метода при естественных ограничениях на аллиптический оператор. ЖВМиМФ - 1966, т. 6, N 5, с. 861-883. 2. Березин И. С, Жидков Н. П. Методы вычислений. Т. 2. - М.: Физматгиз, 1962. 3. Воеводин В. В., Кузнецов Ю.А. Матрицы и вычисления. - М.: Наука, 1984. 4. Годунов С. К., Рябенький В. С. Введение и теорию разностных схем. - М.: Наука, 1962. 5. Годунов С.К., Рябенький B.C. Разностные схемы. -М.: Наука, 1977. 6. Годунов С. К., Забродин А. В. и др. Численное решение много.мерных задач газовой динамики. -М.: Наука, 1976. 7. Денисов A.M. Введение в теорию обратных задач -М.: Изд-во МГУ, 1994. 8. Джордж А., Лю Д. Числен1юе решение бо.льших разреженных систем уравнений.-М.: Мир, 1984. 9. Дьяконов Е.Г. Мигшмизация вычислительной работы. Асимптотически опти-ма.льные алгоритмы для эллиптических задач.- М.: Наука, 1989. 10. Зенкевич О., Морган К. Конечные элементы и аппроксимация. - М.: Мир, 1980. 11. Кобельков Г. М. Решение задачи о стационарной свободной конвекции. ДАН СССР. - 1980, 225, N 2, с. 277-282. 12. Кобельков Г. М. О методах решения уравнений Навье-Стокса. Вычислительные процессы и системы.- М.: Наука, 1991, вып.8, с. 204-236. 13. Крылов В. И., Бобков В. В., Монастырный П. И. Начала теории вычислителпных методов. Уравнения в частных производных. Минск: Наука и техника, 1982. 14. Локуциевский О. В., Гавриков М.Б. Начала численного анализа. -М.: ТОО Янус , 1995. 15. Марчук Г. И. Методы вычислительной математики. - М.: Наука, 1980. 16. Марчук Г.И., Агошков В.И. Введение в проекционно-разпостные методы.- М.: Наука, 1981. 17. Марчук Г.И., .Лебедев В.И. Численные методы в теории переноса нейтронов.- М.: Атомиздат, 1981. 18. Марчук Г. И., Шайдуров В. В. Повышение точности решений разностных схем. - М.: Наука, 1979. 19. Марчук Г. И., Яненко Н.Н. Применение метода расщепления (дробных шагов) для решения задач математической физики. - В кн.: Некоторые вопросы вычислительной и прикладной математики.- Новосибирск: Наука, 1966. 20. Рябенький В. С, Филиппов А. Ф. Об устойчивости разностных уравнений. - М.: Гостехиздат, 1956. 21. Самарский А. А. Теория разностных схем. - М.: Наука, 1982. 22. Самарский А. А., Андреев В.Б. Разностные методы для решения эллиптических уравнений. - М.: Наука, 1976. 23. Самарский А. А., Гулин А. В. Устойчивость разностных схем. -М.: Наука, 1973. 24. Самарский А. А., Николаев Е. С. Методы решения сеточньк уравнений. - М.: Наука, 1978. 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 |