|
| |
|
Слаботочка Книги Можно проверить, что коэффициенты многочленов Р {А) быстро растут с ростом к, поэтому при больших к алгоритм вычисления х , ис-пользуюгций информацию о значениях этих коэффициентов, сильно чувствителен к вычислительной погрешности. В связи с этим для вычисления х используют метод (2). Поскольку из (4) следует, что (3fc(A) = (l-rfcA)...(l-riA) = Q.(A), то г,: являются величинами, обратными к корням многочлена Q{X). Но по доказанному выше QiX) = tkT -i т.е. корни этого мно- гочлена равны М + /Л М-р, (2,7-1)7г . , , А, = ----2~°-2 3 = 1,...,к. (14) Отсюда следует, что значения надо брать из совокупности ---J2f] 3 = 1,...,к; (15) M-b/i-(М-р)cos 2Л- зафиксировав последовательность гх = А~,..., = XJ, мы имеем алгоритм (2) для вычисления у~ по у*. При больших к и произвольном выборе Д,..., jf алгоритм вычисления по формулам (2), (15) также неустойчив к погрешностям округления. Так, например, если взять = А , то согласно (3) уравнение для погрешности имеет вид г = {E - TiA)r~. При наличии округлений оно запишется в виде = (Е - TiAy- + р-\ Последовательно выражая г* через предыдугцие, имеем равенство к к-1 г= = П(£;-г,Л)г№-ьХ; П iE-rjA)f/. г=1 г=0 i+2jk Здесь к г применяется оператор <Э(Л) с нормой ак - \t\~ < 1, в то время как операторы, применяемые к р, могут быть с очень большими нормами. При реальных вычислениях для обеспечения устойчивости алгоритма к округлениям осуществляют перемешивание чисел г . Алгоритм перемешивания в случае А; = 2 заключается в следующем. Последовательно, при j = 1,..., I строится наиболее перемешанная перестановка чисел 1,..., 2. При j = 1 она состоит из двух чисел 2, 1. Пусть уже построена перестановка (bj~,..., b7-i); следующая перестановка берется в виде {2 + 1 - ,1у[ , 2J + 1- ЬГ\ЬГ\---)- Например, при I = 4 эта перестановка имеет вид (11, 6, 14, 3, 10, 7, 15, 2, 12, 5, 13, 4, 9, 8, 16, 1). При таком алгоритме выбора Как уже отмечалось выше, /;;-таговый оптимальный процесс обладает тем недостатком, что число итераций обязательно должно быть кратным к. В случае большого значения к (а это на практике имеет место, так как при этом улучшается скорость сходимости) это ведет к дополнительным затратам при решении системы. Поставим задачу построения итерационного процесса, который при любом к дает такую же оценку для погрешности, как и й-шаговый оптимальный процесс. Исходя из такой постановки задачи, потребуем, чтобы при любом к вектор погрешности г* удовлетворял уравнению Запишем соотношение (17) последовательно для к = п - 1, к = и, к = п + 1. Получим г - 1п-1 j г , .-1 f{M + ,j,)E-2A\, г = С1;.(--:)Л (18) rr. ({M + /i)E-2A\ Многочлены Чебышева связаны рекуррентным соотношением Т.а+х{х) - 2Тп(ж) + Т х(х) = 0. (19) Умножим первое уравнение (18) на третье -на i +i, а к обеим {М\.1)Е-2А частям второго уравнения применим матрицу -2i ----. Скла- М - \1 дывая результаты, получим М - ц {М л- р)Е ~2А f{M + fj,)E-2A\} М-р Л итерационных параметров норма оператора перехода всегда не будет превосходить 1. Задаваясь к = 2, строим таблицу чисел Ь[,..., Ь., и производим итерации (2) при значениях г, = 2 Д М + р - (А/ - ,г) cos (16) 1 ~ 2 и + /in-i = о, М-р, откуда = 1 у/ (2i - u; i при п > О, ио = to/h. (26) Таким образом, можно рекуррентно вычислять величины Шп из (26) и затем векторы х из (25). Для получения совокупности векторов х,..., х потребуется произвести п умножений матрицы на вектор, 0{п) умножений векторов на числа, сложений векторов и операций с числами. При этом для всех к, вследствие (5), (9), выполняется оценка x-X2<t,-4x°-Xi2. (27) Квадратное уравнение .2 + 2-а;-Ь1 = 0 М-р Выражение в фигурных скобках в (20) равно нулю в силу (19). Таким образом, погрешности г искомого итерационного процесса должны удовлетворять трехчленному соотношению ,r- - 2< Й1±АЯг + = 0. (21) Так как г - х - X, то подставляя это выражение в (21), получим =(< -.i-2<..<tii + < i.)x. (22) Вследствие (19) и равенства i = Т Ifrjj) имеем Wi - 2 () tn + tn-i = О, (23) и соотношение (22) может быть переписано в виде Мы получили требуемое рекуррентное соотношение. Приведем его к более удобному виду. Вследствие (23) равенство (24) можно перенисать в виде i +ix +i - (Wi + *n-i)x + *.-ix - = + *.-1)(Лх - b) x +i = x + u; a; i(x - x ) - ji + tu a; -i)(Ax - b), (25) где u)n = tn/tn+i- Разделив обе части (23) на in-i-ij получим 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 |