|
| |
|
Слаботочка Книги Обозначим Qn{A) - {Е - тА) .. .{Е - т\А). Таким образом, оператор (матрица) <5п() связывает погрешности приближения на нулевом и гг-м шагах итерационного процесса. Из (4) имеем г 2 ЩЛА)\\г \\Л\1. (5) (Всюду далее па протяжении этого параграфа под знаком нормы Ц Ц будем иметь в виду норму jj J2.) Рассмотрим следующую оптимизационную задачу. Найти такие итерационные параметры го , Ъг-и чтобы норма jj(5n() была минимальной. Так как матрица А является симметричной, то матрица Qn{.A) также будет симметричной. Отсюда следует, что если Л является собственным значением Л, то (Эп(А) является собственным значением Qn{A)- Таким образом, (ЗЛ>1)11=тахд,(Л,), (6) где Aj - собственные значения А. Предположим, что Aj g [р, М], р > 0. Поскольку собственные значения в (6) неизвестны, а известен только интервал, которому они принадлежат, то задачу нахождения нормы оператора (5п(Л) заменим задачей оценки нормы этого оператора при условии, что мы знаем отрезок, которому принадлежит спектр Л, т.е. (((5г1(Л) = шах (Эп(А)(. Заметим, что многочлен Qn{) имеет вид Qni) = 1 + Введем класс Кп многочленов степени не выше п, равных единице в точке 0. Таким образом, мы можем переформулировать исходную задачу оптимизации следующим образом. На классе требуется найти многочлен Qi) такой, что QliA) = arg min ША)\\ - arg min max Q (A)i; (7) QnEKn Qn&Kn OXM здесь arg, как обычно, означает аргумент, т.е. мы ищем многочлен g Кп, для которого имеет место равенство ийп (5п(Л) = <Эи()- На самом деле, вводя класс К, мы расширили класс многочленов, поскольку в исходной постановке задачи предполагалось, что па [/л, М] искомый многочлен должен иметь п корней. Тем не менее, как мы увидим далее, данное расширение класса не изменяет результат решения оптимизационной задачи. Лемма. Справедливо равенство где Тп - многочлен Чебышева степени п, а = Тп (ж) Доказательство. Предположим, что утверждение леммы неверно, т.е. что существует многочлен Qn & Кп с нормой, меньшей, чем у Q. Ткк Г (а;) = (А + А5)/2, Аг,2 = х±\/х-\. М + fj, При X = -- имеем М - f.1 ,уг = ±МУ-1= iV . (10) Введем обозначение Ао = {у/М + у/т)/(у/Ш - у/т). Из (10) имеем Ai = 0, 2 = Xq. Так как Аг < 1, то при больших п как \Тп\ 1 на [-1, 1], то по предположению имеет место строгое неравенство шах \QniX)\< max <5°(Л)=*-Ч (9) Рассмотрим многочлен (Л) = Qi) - QnW- Пусть М + т М - т TTJ =-2---2-°7Г Из равенства Т (а;) = cos(n arccos ж) имеем №) = (-1)Чт- Поскольку G [р, М]. то, согласно (9), \Qn{x)\<t-\ Отсюда следует, что signSn(A) = siguQ{X). Точки Л ,..., A** расположены монотонно на отрезке [р, М]. Поскольку S (A) меняет знак при переходе от каждой из этих точек к следую-ш,ей, то Sn{X) имеет п корней на [р, М]. Кроме того, 5п(0) = Q(0) - Q (0) = 1 - 1 - 0. Мы получили многочлен степени п, который имеет п + 1 нуль; следовательно, SniX) = О, QniX) = QliX), maxQ (A)=i- [fi,M] Мы пришли к противоречию с (9). Лемма доказана. Заметим, что данный многочлен решает также исходную оптимизационную задачу, так как по построению он имеет на отрезке [р, М] п нулей. Оценим скорость сходимости полученного метода. Воспользуемся явным представлением многочленов Чебышева Поскольку Л и одного знака, то Л172 = Л(;/2. (И) На основе приведенных построений можно предложить несколько типов итерационных процессов. В одном случае задаются последовательностью значений пг, = О < пу < П2 , приближения х определяют но рекуррентной формуле х .:+1 = х - Р, г(Л)(Лх- - ь), (12) где qi = n,+i - ni и F .a(A) = X~4QJX) - l). Имеем г -+=д°ДЛ)г , r +=2..-r Ml2, где Oq - IQil, и в итоге r -2,o---.,-Jr°2- Рассмотрим случай qi = к, т.е. 4\i = ik. Тогда, обозначив х = у% можно записать итерационный процесс (12) в виде /+=у рО (Л)(Лу-ь). Соответствующая оценка погрешности имеет вид у-х2(а,)уО-х2. Такой итерационный процесс называют оптимальным (по числу итераций) линейным к-шаговым итерационным процессом. В частном случае А; = 1, согласно (5), выполняются соотношения РПА) = 1-Лд (Л) = = 1-Л М+и М + п Таким образом, оптимал.ьпый линейный одношаговый итерационный процесс имеет вид а погрепшость оценивается следуюгцим образом: 11у-х2()!у -х2 (13) (этот метод мы уже построили выше в этом параграфе). 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 |