|
| |
|
Слаботочка Книги Пусть ei,...-ортонормированная система собственных векторов матрицы А: Ai = Лгвг, (вг, е ,) = Поскольку fj. Xi М, то при всех i выполняются соотношения M-/i М + р М + ц и, таким образом, М + ц М-р М + р Пусть г = CiGi. Справедливы соотношения г-. = Е.е., где (Лг. , 5:Л.6 = 5:л< (l - С учетом (7) получаем (Аг , г ). Поскольку Fo(y ) = (Ar , г ), то это означает, что Приближение у * можно записать в виде (1) у +1 = х - gradF(x ), а={М + р)-\ Так как на х + достигается минимум F{x) среди всех приближений вида (1), то F(x +) F(y +). Отсюда следует оценка а поэтому и справедливость утверждения теоремы. Аналогично (7.9) можно получить неравенство Их - ХЬ M-pY /м о -х -ХЬ. Хотя на каждом шаге метода наискорейшего спуска уменьшение величины Fo(x) заведомо не меньше, чем у итерационного процесса (6), МЫ получили примерно одинаковые оценки скорости сходимости. Однако есть принципиальное различие в этих методах. Для написания итерационного процесса (6) требуется информация о границах спектра р, М. В случае метода (3), (4), такой информации не требуется. Отметим также то важное обстоятельство, что метод наискорейшего спуска является нелинейным итерационным методом; параметры метода на каждом шаге выбираются в зависимости от полученного приближения. У метода наискорейшего спуска (3), (4), однако, есть следующий недостаток по сравнению с простейшим процессом (6). При нахождении каждого след\тощего приближения он требует не одной, а двух трудоемких операций умножения матрицы на вектор. Двукратного умножения матрицы на вектор при каждой итерации можно избежать следующим образом. Обозначим w = Ах - Ь и перепишем (3) в виде =:х - A w . (8) Вектор w называется вект,ором невязки. Умножая (8) слева на А и вычитая Ь, получим w +i = w - A Aw . (9) Формулу (4) Д.ПЯ определения Д можно записать в виде (Aw , w ) В процессе итерации запоминаются векторы х\ w и на каждом шаге последовательно вычисляются Aw , Д , х * , w +. В исходном методе наискорейшего спуска (3), (4) погрешность на шаге итерации равносильна возмущению начального приближения и, поскольку процесс сходящийся, ее влияние должно иметь тенденцию к затуханию. В итерационном процессе (8)-(10) накопление вычислительной погрешности носит более сложный характер. Задача 1. Получить оценку скорости сходимости метода наискорейшего спуска х -Х2(1-/х/М) х*-Х,. Реальный выбор итерационного процесса должен производиться с учетом имеюш;ейся информации о границе спектра, объеме и структуре памяти ЭВМ. Например, при решении сеточных уравнений, аппроксимирующих дифференциальные уравнения в частных производных, иногда идут но следующему пути. Рассматривая задачу на более крупной сетке, проводят вспомогательную работу по возможно более точному определению значений ц и М, соответствуюгцих более мелкой сетке, а затем применяют оптимЕшьный линейный итерационный процесс. § 9. Метод сопряженных градиентов Метод сопряженных градиентов предназначен для решения систем линейных алгебраических уравнений Ах = b (1) с симметричной положительно определенной матрицей А. Предположим, что мы имеем некоторое начальное приближение х*. Обозначим через г* = А{х - X) невязку начального приближения; здесь X - точное решение системы (1). Поставим следующую задачу - построить многочлен Рп(А) степени п, удовлетворяюгций условию (0) = 1, такой, что значение функционала F(x ) = (Ах , х ) - 2(Ь, х ), где х находится из соотношения г =Р (А)г , (2) будет минимальным. Так как F{y) = (Ay, у) - 2(b, у) = у - Х2 - llXlli = Ау - b\\U - Xi, то данная задача может быть переюрмулирована следующим образом. Требуется найти Рп(А), рп{0) = 1 такой, что норма невязки ((г ((а-1 будет минимальной. Обратим внимание на интересное обстоятельство. Из геометрической картины итераций метода Зейделя видно, что скорость сходимости метода не меняется при умножении уравнений системы на множители и изменении масштабов по координатным осям, равносильном замене Xi = кгу. Иначе обстоит дело в случае метода наискорейшего спуска. Пусть, например, А = Е - единичная матрица. Тогда т т, F(x) = (Ах, х) - 2(Ь, х) = xf - 22ЬгХг г=1 г=1 и метод наискорейшего спуска сходится за одну итерацию (доказать!). Произведем замену масштабов Xi = kjyj, к > 0. Матрица системы А в данном случае будет диагональной с элементами на диагонали, равными ki- Тогда минимизируется функционал т, т Пу) = (Ау, у) - 2(Ь, у) = Yiyf - 2j2bm- г=1 i=l При большом разбросе k-i линиями уровня функции F будут сильно вытянутые эллипсоиды и скорость сходимости метода наискорейшего спуска будет очень медленной. 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 |