|
| |
|
Слаботочка Книги Наименьший из этих корней, равный обозначим через Итерационный процесс (25). (26) называют оптимальным (по количеству итераций) лии,ейным. итерацгюнным процессом.. При реализации процесса (25), (26) после любых к применений матрицы А мы получаем оптимальный результат в смысл< (6). Из сказанного видно, что по скорости сходимости итерационный процесс (25), (26) предпочтительнее, чем (12). Однако иногда от него отказываются в пользу (12) из-за соображений экономии памяти ЭВМ. Получим более наглядную оценку скорости сходимости построенных итерационных процессов. Согласно (27) и (И) для оптимального итерационного процесса выполняется оценка К-ХЬ2Ао- х -Х2. Норма погрешности г уменьшится по крайней мере в раз, если 2Л е. Отсюда получаем оценку числа итерапцй, обеспечиваюгп,их получение решения с точностью е: п т = logj2/e) = (1пЛо)- 1п(2/е). Для многих задач число М/р оказывается очень большим. Поэтому при M/fx оо имеем Ао = 1 + 2y/Ji/M + 0{ц/М). Таким образом, InAo ~ 2 М, П1 ~0,5v/M /ln(2/e). Для сравнения рассмотрим оптимальный линейный одношаговый процесс, имеющий, согласно (13), оценку погрешности 1х -Х2() хО-Х2; отсюда получаем оценку числа итераций При M i со имеем , М + 11 2/1 1М , 1 М - ц М 2 /1 е имеет два положительных корня fj, = min Ai = 8P sin ~ 2, M = max Ai = 8/ cos ~ 8, т.е. \jMlii ~ 211 IK. Например, при шаге I = 30 выигрыш в числе итераций примерно в 20 раз. Таким образом, в этом сравнении оптимальный итерационный процесс дает выигрыш в числе итераций примерно в /мJJ раз. Задача 2. Рассматривается итерационный процесс X* = х-1 - Ti i(Ax-i - b), г = 1, 2,... . Пусть р нечетное и при всех к совокупности то,...,Трк-1 совпадают с совокупностями 7i i = 2 M + p-(M-p)cos , = Проверить, что при всех г = р/ приближения х* совпадают с приближениями, получаемыми по оптимальному линейному итерационному процессу. Задача 3. Пусть то = 2/(М + ), п = 1/М, тг = 1/р и совокупности т2л+1,..., Tgfc+i при каждом А; > 1 совпадают с совокупностями величин 7i = 2(M + p-(M-p)cos) \ i = l,...,2 Показать, что для такого итерационного процесса при всех п - 2+ справедлива оценка - - (лг-лЛл.-л.-) - - 1х -Х2 = 0(Ао- )х -Х2. Рассмотрим типичную задачу математической физики, сводящуюся к решению системы уравнений с большим отношением М х. Пусть в квадрате О Xi,X2 1 решается уравнение Пуассона - Аи = / при нулевых условиях на границе. Зададимся сеткой с шагами /), = 1/Z и напишем систему уравнений, аппроксимирующих дифференциальную задачу: Un\-\-\,n 2л1пгп т- ------= ( при О < ?п, п < I; гягп = О, если т{1 - гп){1 - п)п = 0. Матрица этой системы является положительно определенной, и для нее Таким образом, при больших п итерационная формула (25) б.пизка к формуле z +i = z + w2(z - z -) - Т7(1 + w)(Az - b). (29) Ad + fi Если нри n > 1 итерации будут произвсдиться по этой формуле, то при условии z° = х°, z = у этот итерационный процесс требует примерно столько же итераций, сколько итерационный процесс (25). Задача 4. Для итерационного процесса (29) получить оценку погрешности 1к +М2 . 2+(п-1)(1-Ло) Указание. Представить погрешность в виде г = Efc {е} -пол- пая ортогональная система собственных векторов матрицы А. Подстановкой в (29) получить разностное уравнение, связывающее z~, z, z * . Получить явное выражение для z и с его помощью получить требуемую оценку (30). Задача 5. Показать, что оценка (30) не может быть улучшена на множестве матриц, удовлетворяющих условию S(A) С [/л, М]. § 7. Метод Зейделя Пусть решается система уравнений Ах = Ъ, все диагональные элементы которой ненулевые. В итерационном методе Зейделя последовательно уточняются компоненты решения, причем к-я компонента находится из fc-ro уравнения. Именно, если х = (ж,..., ж), то следующее прибли- В начале этого параграфа было упомянуто, что при симметризации системы ее свойства могут ухудшаться. Действительно, пусть этот процесс применяется к уже симметричной матрице А, т.е. переходим от системы Ах = b к системе Ах = АЬ. Если у старой системы отношение максимального и минимального собственных значений равнялось М/р, то у новой оно будет (M i) и скорость сходимости итерационных процессов будет меньше. Примечание. При п -> оо имеем т (1±И\ -у LO - 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 |