|
| |
|
Слаботочка Книги при х /X. Вследствие (3) имеем равенство г + = -В Сг , где г = - X. Соотношение (6) можно переписать в виде . , (АБ-Сг , В-Сх) при г ф 0. На сфере г 2 = 1 величина (р(г ) непрерывна, поэтому она достигает своего наибольшего значения сро- Так как А > О, то всегда (р(г ) > О и поэтому (/Ро > 0. Положим = Л. Вследствие (7) имеем < 1. Очевидно, (р(сг ) = <р(г ) при любом с ф поэтому <р(г ) = (р(г /г 2) при любом г . Отсюда получаем неравенство Fo(x +i)/Fo(x ) Х\ и, таким образом, Fo(x ) x Fo{xP). Из (3.8), (3.9) следуют неравенства min у - Х2 < Fo(y) < max Цу-ХЩ. Отсюда получаем оценку скорости сходимости 1К-Х2 ,/Щ<А min А min А < А max А* min А fx -X2. (9) Теорема доказана. Из рис. 6.7.5 можно усмотреть, что метод Зейделя сходится быстрее, если направление осей эллипсоидов близко к направлению координатных осей, т.е. матри11,а А близка к диагональной. В случае, изображенном на рис. 6.7.4, последовательные приближения смещаются все время монотонно влево и вниз. Такая картина монотонное смещение отдельных компонент все время в одном и том же направлении - характерна для ряда классов матриц. При этом довольно часто монотонное смещение наблюдается именно у компонент решения, скорость сходимости которых наиболее плохая. В этих случаях для ускорения сходимости прибегают к методу релаксации, который заключается в следующем. После уточнения каждой координаты по методу Зейделя производится смещение в том же направлении на р-ю часть этого смещения. Таким обра- 10-903  Рис. 6.7.5 (10) D - диагональная матрица с элементами пц по диагонали. Как показала практика вычислений, при А > О целесообразно брать показатель релаксации р в пределах -1<р<1: в случае О < р < 1 метод релаксации обычно называют методом сверхрелаксации (или методом верхней релаксации). На рис. 6.7.4 изображены символами о приближения метода Зейделя, * -метода верхней релаксации при р= 1/4. Например, для уменьшения погрешности в раз при решении системы (6.28) методом Зейделя требуется порядка c/i~ln(e ) итераций. Если применить метод верхней релаксации при р = I -- u)h, со > О, то потребуется порядка с{ш)Н~ 1п(е~) итераций. Подбор параметра и) в этой задаче требует детального рассмотрения. В частности, во многих случаях оптимальное значение параметра релаксации р определяется экспериментально. Иногда параметр релаксации р выбирают зависяш;им от п и г. Для случая А > О егце раз обратимся к геометрической картине (см. рис. 6.7.4). После уточнения компоненты Xi по методу релаксации при -1 < р < 1 мы попадаем в точку, лежащую внутри или на гранипе эллипсоида F(x) = F(x). Рассуждая так же, как при обосновании сходимости метода Зейделя, заключаем, что при -1 <р < 1 всегда Fo(x +) < Fo(x ), если х 7 X. Задача 2. Доказать, что при условии р q < 1 метод релаксации сходится со скоростью геометрической прогрессии. § 8. Метод наискорейшего градиентного спуска Распространенным методом минимизации функций большого числа переменных является метод градиентного спуска. Последующее приближение получается из предыдущего смещением в направлении, противоположном градиенту функции F(x). Каждое следующее приближение ищется в виде х +1 = x-<5 gradF(x ). (1) Приведенное описание не определяет алгоритм однозначно, поскольку ничего не сказано о выборе параметра 6п- Например, его можно определять из условия минимума величины F(x -<5 gradF(x )). (2) В этом случае рассматриваемый метод называют методом наискорейшего градиентного спуска или просто методом наискорейшего спуска. зом, приближения отыскиваются из соотношения Для функции F{x.) = {Ах, х) - 2(Ь, х), соответствующей системе линейных уравнений с матрицей А = > О, задача нахождения минимума решается в явном виде. В этом конкретном случае gradF = 2(Ax-b) х + = х 2<5. (Лх -Ь). Обозначим 2бп через Л , т.е. положим х + =х -Л (Лх -Ь). (3) Пусть tp{A,i) = F(x +). Вспоминая, что А = А, вычислим (/р(Л ). Имеем ip{An) = F(x ) - 2Л (Ах - Ъ, Ах -Ъ) + (А(Ах - Ъ), Ах - Ь)Л -- (Ах - Ъ, Ах - Ъ)) = О, откуда (Ах - Ь, Ах - Ъ) Ап = (А(Ах -Ь), Ах -Ь) На рис. 6.8.1 изображены последовательные приближения метода наискорейшего спуска и линии уровня функции F. Итерационный процесс (3), (4) называют методом наискорейшего спуска решения рассматриваемой системы линейных уравнений. Пусть собственные значения матрицы А расположены на [/i, М], т. е. Sa с [/i, М]. Теорема. Приближения метода наи-скорейш,его спуска удовлетворяют со-отнош,ению  Рис. 6.8.1 М-/л\ М + р. Fo(x°), Fo(x) = (А(х - X), X - X). Доказательство. При у = х произведем одну итерацию оптимального одношагового итерационного процесса у +1 = у M-b/i (Ay -b). Погрешности итераций г = у - X связаны соотношением г +1 =(е~ -а\ г . V м + /1 ) 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 |