|
| |
|
Слаботочка Книги 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 § 8- Методы решения сеточных эллиптических уравнений в этом параграфе будут рассмотрены методы решения систем сеточных эллиптических уравнений. Рассмотрим простейший пример (см. § 6). Пусть IJm+l,n Щпп Ь т-1,п m,n+l Umn Ь m,n-\ Го 72 - Vmm hi h (1) UmO - UmN = 0, Mo,n = UM,n = 0; m = 1, , . . , M - 1; П = 1. . . . , W - 1, система сеточных уравнений относителыю неизвестных Umn, О тп Л/, О п N, попучаюгцаяся в результате аппроксимации краевой задачи Дирих-пе дпя уравненпя Пуассона в квадрате О = {а; = (xi, Ж2), О Xi 1}. Будем дпя простоты считать, что hi = /12 = h = l/N. Для решения системы уравнений (1) можно предложить большое число методов. Поэтому дпя того, чтобы их сравнивать, необходимо выбрать один или нескопько критериев, по которым будет проводиться сравнение. Условимся критерием качества метода считать количество арифметических операций, которые необходимы .либо для получения точного решения, либо для по.пучения решения с некоторой заданной точностью. Так как часто не удается вычислить точное число арифметических операций либо этот подсчет достаточно громоздок, оценивают .пишь порядок числа арифметических операций по отношению к числу уз.пов сетки. Прежде всего отметим особенности рассматриваемых систем уравнений. Во-первых, это большая размерность (большое число неизвестных в системе). Это связано с желанием получить решение исходной дифференциальной задачи с нужной точностью, что требует достаточно малого шага сетки. Во-вторых, в каждой строке матрицы лишь конечное число элементов отлично от пуля. В частности, в (1) ко;шчество ненупевых элементов в строке не превосходит пяти. Все это застав.пяет разрабатывать специальные эффективные методы, учитывающие особенности систем уравнений такого типа. Рассмотрим прежде всего, что же дает применение к.пассического метода Гаусса к решению системы (1). Предположим, что граничные узлы исключены из системы уравнений. Тогда вектор неизвестных, которыми являются значения функции во внутренних узлах, имеет размерность (Л -1). Поэтому прямое применение метода Гаусса к решению системы (1) требует 2/3{N - l)* + 0{N) арифметических операций. Кроме этого, потребуется хранить в памяти матрицу системы, т. е. потребуется OiN) слов ЭВМ для хранения элементов матрицы. Заметим, однако, что большая часть арифметических операций является несодержательной - это операции над нулевыми элементами ма- трицы. Выясним, какое потребуется количество арифметических операций, если вычисления проводить только над ненулевыми элементами. Напомним, что матрица А системы уравнений (1) при естественной нумерации компонент вектора неизвестных (и, 12) - - , uin-i, U21, , un-1,N-i) имеет вид (с точностью до множителя h~) ( А\\ Ai2 А21 А22 А23 V о о \ An~2,N-1 Ац - /4 - 1 О -14-10 О ...... V О ...... О \ 4 -1 -1 4 / а Лг,г±1 - диагональные матрицы с элементами на диагонали, равными - 1. Матрицы Ац имеют размерность {N - 1) х (iV - 1). Таким образом, матрица А оказывается блочно-трехдиагональной и в каждой строке матрицы не более пяти элементов отличны от нуля; кроме этого, матрица А является ленточной с шириной jkhtbi равной (2iV-1): все элементы =0 при г -i N. Задача решения системы (1) является частным случаем решения системы m уравнений с m неизвестными Лх - b (2) с (2s + 1)-диагональной матрицей. Для решения такой системы могут быть применены, например, методы Гаусса, квадратного корня, отражений и враш;епий с исключением несодержательных операций во всех случаях. Под исключением несодержательных операций имеется в виду следуюгцее. Поскольку = О при г -j > S, то не надо проводить операций по обнулению этих элементов. Поэтому производятся операции лишь по обнулению 0{ms) элементов. Кроме того, при реализации каждого шага обнуления все элементы Gij = О при \г - j\ > S остаются равными нулю и поэтому каждый шаг требует 0{s) арифметических операций. Таким образом, общее число операций при решении системы уравнений (2) оказывается величиной порядка 0{ms-). В данном случае т = [N - 1), s = N - 1 и поэтому общее число арифметических операций 0{N). Матрица А симметричная и положительно определенная. Как отмечалось ранее, в случае Л > О при реализации этих методов не возникает операции деления на нуль. Еще один возможный метод решения этой системы - это метод прогонки в блочной форме. Исходную систему уравнений записываем в виде Апи1 + Аг2П2 =fi, 2iUi + A22U2 + A23U3 = f2, AN-2,N-:i4N-S + An2,N-~24N-~2 + Лу-2, jV-lU/V-1 = f/v-2, Aj\-1N-2UN-2 + jV i A 1UjV- i = fjV-1, где Ufc -вектор с компопенталш 11,1, щ,2-, kN-i- Далее последовательно исключаем векторы неизвестных ui,U2,..., ujv 2 и получаем рекуррентные формулы, аналогичные формулам метода прогонки. При реализации этих формул придется произвести порядка cN операций умножения и обращения матриц размерности Л - 1, что потребует всего порядка 2cN арифметических операций. Дополнительно требуется произвести порядка 0{N) операций умножения матрихщ! на вектор и сложения векторов, для этого потребуется 0(N) арифметихе-ских операций. Общие вычислительные затраты, таким образом, составят порядка 2cN арифметических операций. Описанные выше методы непосредственно применимы в случае эллиптического уравнения или системы атшиптических уравнений с произвольными, в частности, переменными коэффициентами и во всех этих случаях требуют 0{N) арифметических операций. В конкретном случае системы (2) при N = 2 можно предложить метод, требующий 0{N\nN) арифметических операций. Для этого следует применять метод Гаусса в векторной форме при следующем порядке исключения неизвестных: сначала исключаются векторы ui, U3, U5,..., т.е. все векторы U2fc+i, затем векторы 112, Uf ию,..., т.е. все векторы U2(2fc+i), затем векторы U4, U12, U20,.-., т.е. все векторы U4(2fc+i) и т.д. Оказывается, что при таком способе исключения многократно умножаются и обращаютя одни и те же матрицы. Если вместо этого запомнить произведения соответствующих матриц, то общее число операций окажется O(AlogA). Описанные методы требуют в общем случае для запоминания ленты матрицы 0{N) слов памяти ЭВМ. Задача 1. Показать, что при нумерации неизвестных Uii, U12, U21,..., Ui,N-l, U2,N-2,---, UN-1,1,---, iV-l.iV-l количество арифметических -операций в методе Гаусса по порядку также равно 0{N). Задача 2. Для случая разностной аппроксимации уравнения Лапласа в произвольной двумерной области указать порядок исключения неизвестных, при котором решение системы получается за 0(М/2) арифметических операций; здесь М - общее число узлов. 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 |