|
| |
|
Слаботочка Книги Решение системы (1-3). (1-4) описаршыми выше методами требует 0(N) арифметических операций; если при решении этой систейШ! обратиться непосредственно к стандартной программе метода Гаусса, то число операций будет порядка 0{N); это количество операций состоит из 0{N) содержательных операций метода прогонки и 0{N) несодержательных операций умножения (деления) нуля па некоторое число, и сложения (вычитания) двух нулей. Такий! образом, хотя содержательные операции при решении этой системы методом прогонки и по стандартной программе метода Гаусса одни и те же. использование стандартной программы приводит к существенному увеличению затрат на решение задачи. Текст программы метода Гаусса ьюжет быть преобразован в текст программы метода прогонки, если в преобразованиях над строкайп! и столбцами матрицы изменить начало и конец циклов так, чтобы исключить несодержательные операции. Рассмотрим теперь случай, когда при ж = О имеем граничное условие у{0) - ау(0) = а. В § 1 при его аппроксимации возникло уравнение, связывающее значения уо и уц это уравнение может быть записано в виде Уо = Cqiji + ipQ-. (14) ?У1 - Уо например, простейшую аппроксимацию -j--ауо = а можно перепи- 1 ah сать в таком виде при Со = -Г; =-- Далее вычисляем 1 -Ь an 1 -f- ah Сп, (рп по формулам (11) при п = 1,..., N - 1 и при обратном ходе прогонки ум-1,---,Уо по формулам (10). Если при х = Х имеем граничное условие у{Х) + Ру{Х) = Ь, то аналогично (14) имеем уравнение ум = Смум-1 + Фм- (15) Осуществляя прямой ход прогонки, получим равенство ум-1 = См-1Ум + vn; (16) решая систему (15), (16), находим у, yu-i и затем последовательно вычисляем ул-2, , Уо по формулам (10). При аппроксимации краевых задач для уравнений высших порядков или для систем дифференциальных уравнений появляются системы уравнений Ау = с с (/, s)-диагональными матрицами А; матрицу А = [atj] называют (/, з)-дагональной, если atj = О при j <г - I и при j > г -Ь s. Для решения таких уравнений также довольно часто бывает целесообразно применять метод Гаусса, алгоритм которого может быть записан аналогично методу прогонки в виде совокупности рекуррентных формул. Если I > S, то для уменьшения числа арифметических операций целесообразно переобозначить неизвестные и уравнения в обратном порядке, Чтобы получить систему с (s, /)-диагональной матрицей. Задача 2. Подсчитать число операций при решении методом Гаусса системы с 5)-диагональной матрицей при I > s, I = s, I < s. В ряде случаев (I, 5)-диагональная матрица системы уравнений записывается естественным образом в виде (р, д)-диагональной матрицы клсчочного вида, т. е. Л = [Aij], Aij - некоторые матрицы тшие, что = О, если j < г - р или j > г + q. Рассмотрим случай системы уравнений y -p{x)y = t{x), (17) где у, f-векторы размерности т. р- матрица размерности т х гп, и простейшую аппроксимацию У +1-2у -Ьу -. Матрица системы естественным способом записьгоается в виде (17) с р = q = 1; Aij - матрицы размерности m х т. В то же самое время эта матрица является (2т - 1, 2т - 1)-диагональной или, что то же самое, (4т - 1)-диагональной. Для решения этой системы может быть применен метод исключения Гаусса в клеточной форме, который аналогично скалярному случаю может быть записан в виде совокупности рекуррентных матричных соотношений типа формул метода прогонки. Задача 3. Подсчитать число арифметических операций для метода Гаусса в клеточной форме и для обгцей процедуры метода Гаусса с исключением несодержательных операций в применении к системе уравнений (18). При решении ряда задач возникают системы уравнений с матрицей А, отличающейся по структуре от (1, 5)-диагональной матрицы наличием ненулевых элементов при п, т.е. вблизи левого нижнего и правого верхнего углов матрицы. Для решения таких систем также целесообразно применять метод Гаусса с исключением несодержательных операций. В случае отыскания периодического решения сеточного уравнения (3) этот вариант метода Гаусса называют методом циклической прогонки. Рассмотрим пример задачи, сводящейся к системе уравнений такого вида. При сглаживании функций методом регуляризации в § 5.3 возникла следующая задача. Дана периодическая функция целочисленного аргумента q; период равен N. Требуется найти периодическую с тем же периодом функцию Uq, удовлетворяющую системе соотношений -j + {->)Щ = и при всех q. Выпишем эти соотношения при q = 1,..., N. Вследствие условия периодичности заменим значения Uq при q о и при q > N, входящие в эти соотношения, соответственно на щ+n и u-n- В результате этого получится система Л уравнений относительно N неизвестных 1,..., Utv : Аи - f. Элементы матрицы А = [uij] этой системы определяются соотношениями а- = о (г - где а(0) = (-1) (С? Л.-2 + А2 ), Г (-l) -=q77!-2 при 0<А;п, О при п< к N - п, ( l)fc+n-Nfc+ -.v,-2 pjj N-nk<N; а (1) ... а (п) О ... О а (N-n) ... а {N-l)\ а{к) = а (0) о(1) а(п) О a{N - п) V a(iV -1) Матрица А симметричная и положительно определенная. Задача 4. Выписать расчетные формулы этого метода при п = 1. Показать, что решение этой системы методом Гаусса с исключением несодержательных операций требует 0{п?М) арифметических операций. Задача 5. Выписать расчетные формулы метода квадратного корня в конкретном случае решения этой системы при п = 1. Пoдcштaть необходимое число арифметических операций. Выше, когда при рассмотрении метода прогонки выписывались расчетные формулы и подсчитывалось число арифметических действий, был оставлен в стороне вопрос о возможности переполнения процессора ЭВМ, в частности, вследствие деления на нуль. Кроме того, отсутствие переполнения само по себе не гарантирует избавления от большого влияния вычислительной погрешности. На модельном примере р{х) = р = const рассмотрим поведение прого-ночных коэффициентов С при различном знаке р. Соотношения которым удовлетворяют коэффициенты Сп метода прогонки, совпадают с итерационными формулами решения уравнения 2-fp/)2-C 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 |