|
| |
|
Слаботочка Книги { m+l,n - Vmn + Vm-l,n hi 0 в остальных случаях; 1 m M - 1, lnN -1, 0 в остальных случаях. Тогда система уравнений (1) может быть представлена в операторной форме Au = -(Ai+A2)u = ip. (3) Пусть для определенности Mhi = 1. Заметим, что этого всегда можно достичь, умножая обе части (1) на соответствущий коэффициент. Функция и как функция переменного т представима в виде дискретной суммы Фурье по переменной т. (см. § 4.3): u{mhi, n/i2) = Uj(n/i2) smJTrjmhi), j=i Uj{nh2) = 2 hiu{khi, nh2) sm{7rjkhi). k=l Аналогично представим ip в виде ip(mhi, 71/12) = <Pj(n/t2) sin(7rjm/ti), j=i <Pj{nh2) = 2 h\(p(kh\, 71/12) sin(7rjfc/ii). Рассмотрим прямой метод решения системы уравнений (1), основанный на использовании дискретного преобразования Фурье в случае прямоугольника. Здесь мы не будем предполагать, что М = N. Преобразуем вначале систему уравнений (1) к операторной форме. Пусть u{mhi, n/12)- сеточная функция, определенная при О т М, О п N, которая соответствует решению (1), т.е. u{mhi, nh2) = ип- Аналогично, (p(mhi, nh}) = ipmn, Щп = VMn = Vmo = PmN = 0 -ссточная функция, соответствующая правой части (1). Через А/- обозначим операторы Ai sm(7rjm/ii) = 4sin2 =---2-sin(7rjm/ii) = - Aj sin(7rjVn/ii). Поэтому выражение (5) может быть заменено эквивалентным EV 2uj{nh2)--Uj{{n-l)h2)-Uj{{n+l)h2)\ ... , , \jUj{nh2) + ---2------ sin(7rjm/i,) = = Е( Т/2) sm(7rjm/ii). Функции sin(7rjm/ii), j = 1,..., М - 1, являются ортогональными в скалярном произведении (tl, W) = Е hiWi. Поэтому (6) представляет собой систему независимых уравнений 2Uj(n/i2) -Uj((n - l)/i2) -uj((n-M)/i2) , . . XjU,{nh2) +----- = ipj{nh2), uj{Q) -uj{Nh2) =Q, j = 1,..., M ~1. Система уравнений (7) может быть получена из (6) также умножением обеих частей (6) скалярно на sin(7rjm/ii), j = 1,М -1. Выражение (7) при фиксированном j представляет собой систему линейных алгебраических уравнений с трехдиагональной матрицей относительно неизвестных Uj{h2), Uj(2/i2), ..., Uj{{N - l)h2), которая может быть решена, например, методом прогонки. Таким образом, алгоритм решения задачи (1) заключается в следующем: а) находим из (4 ) при каждом п, О < п < N, коэффициенты (pj{nh2), j = 1,..., М - 1; б) при j = 1,..., М - 1 решаем методом прогонки систему уравнений (7). В результате получаем функции Uj{nh2), j - 1,..., М - 1; Подставляя полученные разложения в (3), получим м-1 - (Ai + A2)u - Е {uj{nh2)Aism{7rjmhi) + sm{Trjmhi)A2Uj{nh2)) = = (/3j(n/i2)sin(7rjm/ii). Напомним, что функции sin(7rja;) являются собственными для оператора Ai: sin(7rj(m -f- - 2sin(7rjm/ii) + sin(7rj( i - можно применить, например, метод простой итерации ,..1+1 ..,1 ~-- + Аи = ур, К = V, (8) где и -вектор начального приближения. Согласно § 6.6 параметр г целесообразно выбрать из соотношения в) из формулы (4) при т = 1,...,М - 1, п = I,..., N - 1 вычисляем значения функции u{mhi, n/12). Оценим затраченное количество арифметигеских операций. Пусть М = 2. В этом случае, используя алгоритм быстрого дискретного преобразования Фурье, найдем все (pj за 0{MN lQg2M) арифметических операций. При нахождении коэффициентов Uj потребуется 0{MN) операций. Наконец, при вычислении и из (4) с использованием быстрого дискретного преобразования Фурье понадобится 0(MiVlog2M) операций. Поэтому суммарное количество арифметических операций, необходимых для нахождения решения, в данном случае по порядку равно 0{MN\og2M). В частности, при M = N получаем 0{N \0g2N). Рассмотрехшый метод даст решение намного быстрее, чем метод Гаусса. Однако этот метод применим лишь в случае, когда исходная область является прямоугольником, в то время как метод Гаусса применим и в случае областей общей формы. В случае прямоугольника существует ряд других методов решения с такой же асимптотикой числа действий. Как уже отмечалось, один из вариантов марш-алгоритма с приемлемой величиной вычислительной погрешности решает задачу за 0{N) арифметических операций при N = М = 2. Рассмотрим другие приближенные методы решения системы уравнений (1), допускающие обобщение на случай более общих, чем прямоугольник, областей. В основу этих методов положено то свойство системы уравнений (1), что результат применения матрицы системы к вектору вычисляется по простым формулам и не требует запоминания матрицы. Количество арифметических операций, затрачиваемое на вычисление результата применения матрицы к вектору, по порядку равно 0{MN), т. е. пропорционально длине вектора. Ранее мы упоминали, что матрица А системы уравнений (1) симметрична и положительно определена и в рассматриваемом случае ее собственные значения Amni 0<m<M, 0<п<Л, лежат в промежутке 4sm2 4sm2 4cos2 2[.l 4cos2 тгп - I mn I = max- Поэтому ДЛЯ решения системы уравнений Аи = (р 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 |