|
| |
|
Слаботочка Книги f(x) = В простейшем случае m = 1 оператор р превращается в оператор умножения на производную Пусть x - решение уравнения f(x) = 0, х - некоторое приближение к x. В предположении существования производной f, согласно (2), имеем f(x) - f(x ) - f(x )(x - х ),. = о(х - х я) (3) Если величина х - х я мала, то можно написать приближенное равенство f(x ) + f(x )(x - х ) f(x). Поскольку f(x) = О, то f(x ) + f(x )(x - х ) 0. Возьмем в качестве следующего приближения х * решение уравнения f(x ) + f(x )(x + - х ) = о, если такое регпение существует. Между прочим, последнее уравнение имеет вид (1.11). В предположении, что оператор f обратим, это решение можно записать в виде = х - (f(x )) V(x ). (4) Такой итерационный процесс называют методом Ньютона. ем II-Ця и II-Цк. Линейный оператор р, действующий из пространства Н в пространство Y, назовем производной оператора f(x) в точке х, если II f(x + /;) - f(x) - Ft; Ц - = о{\Мн) (2) при 7;д -> 0. В дальнейшем будем обозначать такой оператор р через f(x). Пусть, например, X = {xu...,XmV, F={.h,...,.fmf. Если функции fi непрерывно дифференцируемы в окрестности данной точки X, то Совокупность этих соотношений можно переписать в виде (2), если за р принять оператор умножения слева на матрицу Пусть Qa = {х- х - Хн < а}. Пусть при некоторых а, oi, 02, О < а, О О], 02 < оо, выполнены условия: j(F(X))- ai при xefi ; (5) ]F(ui) - F(U2) - F(U2)(U1 - U2) . a2u2 - uill (6) при Ui, U2 € Qu- Обозначим с = 102, b - mina, Теорема (о сходимости метода Ньютона). При условиях (5), (6) иур Е итерационный процесс Ньютона (4) сходится с оценкой погрешности х -Хя<с-1(сх°-Хя) . (7) Примечание. Если в рассматривавшемся выше примере в некоторой окрестности решения функции имеют ограниченные вторые производные, то, согласно формуле Тейлора, имеем л(у) = /i(x) + J2 (у, - + о(у - xf), и, таким образом, условие (2) выполнено. Доказательство. Пусть х° G Гь. Индукцией по п докажем, что все х G fift. Пусть это утверждение доказано при некотором щ так как b а, то тогда х € fla- Подставив в (6) ui = X и U2 = х , получим F(X) - F(x ) - F(x )(X - х ) а2х - Xf,. Поскольку F(x ) = -F(x )(x + -х ), а F(X) = о, то это соотношение может быть переписано в виде F(x )(x +i-X)a2x -Xf. Воспользовавшись (5), получаем неравенство х +1-Хя<сх -Х1;. (8) Отсюда следует, что х + - Хя < сЬ = {cb)b < 6, поэтому х + также принадлежит Г. Таким образом, при х G fib все х принадлежат Пь и, следовательно, для них выполняется (8). Пусть Qn = с(х - Хн- После умножения на с неравенство (8) запишется в виде Qn+i 9. Индукцией по п докажем справедливость неравенства Яп <: 9о - При п = О оно очевидно. Предположив его верным при п = к, получаем Таким образом, qn Qo при всех тг. Это означает, что сх -Хя (сх°-Хя) . Отсюда следует (7). Согласно определению с и 6, сх° - ХЦя < с6 1, и поэтому х X. Теорема доказана. Обращение оператора F(x ) зачастую оказывается более трудоемкой операцией, чем вычисление значения F(x ). Поэтому метод Ньютона часто модифицируется следующим образом. По ходу вычислений выбирают или заранее задаются некоторой возрастающей последовательностью чисел 7Zo = О, п\, П2---- При п < П/fe+i итерации производят по формуле хП+1 = х - (f(x *)) F(x ). Увеличение числа итераций, сопровождающее такую модификацию, компенсируется большей дешевизной одного шага итерации. Выбор последовательности {rifc} нужно производить с обоюдным учетом этих факторов. Рассмотрим геометрическую интерпретацию метода Ньютона в случае решения скалярного уравнения f{x) = О, когда расчетная формула (4) приобретает вид ж +1 = ж -/(ж ) (ж ). (9) Для получения геометрически надо найти абсциссу точки пересе- чения с осью X касательной к кривой у = f{x) в точке (т , /(ж )) (рис. 7.2.1). Уже в случае, когда /(т)- многочлен третьей степени, может случиться, что последовательность {хп} не сходится к корню при плохом начальном приближении.  Х X Х Рис. 7.2.1  а Ъ X Рис. 7.2.2 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 |