|
| |
|
Слаботочка Книги С другой стороны, пусть inf#(a;i,..., Хт) достигается в точке X, вну- тренней по отношению к G, и функция Ф дифференцируема в этой точке. Тогда точка минимума является решением системы уравнений ф. = О, г = 1,..., т. Возможность сведения одной из этих задач к другой не означает, что достаточно ограничиться рассмотрением только одной из них; родство этих задач скорее подчеркивает, что они одинаково трудны. О трудности этих задач свидетельствует то, что не существует универсальных алгоритмов решения, практически пригодных уже не при очень больших тп; отсутствие таких алгоритмов вызвано существом дела. В то же время и при больших тп существуют эффективные алгоритмы решения задач, обладающих определенной внутренней структурой (в частности задач, возникаюнщх при решении краевых задач математической физики вариационными методами). При решении задач каждого типичного в приложениях класса приходится заниматься теоретической и экспериментальной доводкой методов применительно к этому классу задач. Сведение задачи минимизации функции к системе нелинейных уравнений или наоборот производится на практике с целью снижения трудоемкости решения. Например, при решении систем нелинейных уравнений иногда поступают следуюгцим образом. Строится функционал, минимум которого достигается на решении системы. Затем, задавшись начальным приближе-1шем к точке минимума, проводят итерации каким-либо из методов спуска (см. § 3) и таким путем получают удовлетворительное приближение к решению системы. Исходя из этого приближения производят уточнения при помощи какого-либо итерационного метода, специфического для задачи решения системы уравнений, например метода Ньютона (см. § 2). Поясним причины, вызываюшце такое комбинированное применение методов. Назовем областью сходимости метода множества начальных условий, при которых итерации по данному методу сходятся к решению задачи. Применение методов спуска на первоначальном этапе вызвано тем, что обычно они имеют более широкую область сходимости, чем методы, специфические для задачи решения систеьа.1 уравнений. В то же время последние методы обычно обладают лучшей скоростью сходимости при наличии достаточно хорошего начального приближения; это и обуславливает их применение на заключительном этапе итераций. На примере решения системы линейных уравнений было также видно. Что сведение этой задачи к задаче нахождения минимума функционала приводит к конструированию новых методов решения исходной задачи. здесь а - /э(х, х*), /э(х, у) -расстояние между у:и у. Доказательство. Согласно (5) имеем р(х +\ х ) = p(g(x ), g(x -l)) qp{x\ х -), поэтому /э(х ~, х ) qp{x}, х ) = qa. При I > п имеем цепочку неравенств р{х, х ) p{x, х-1) + + /э(х +\ х ) - q § 1. Метод простой итерации и смежные вопросы Так же как в случае линейных уравнений, начнем изучение итерационных методов с метода простой итерации. Этот метод состоит в следующем: система уравнений преобразуется к виду X = g(x), (1) иначе, Xi = gdxi,i = 1,..., -m, и итерации проводятся по формуле x +i=g(x ), (2) иначе, х+-5гК,...,0, г = 1,...,т. Подойдем к изучению этого метода с более общих позиций. Пусть Я -полное метрическое пространство, а оператор у = g(x) отображает Н в себя. Рассмотрим итерационный процесс x + = g(x ) (3) решения уравнения x = g(x). (4) Если при некотором q < 1 отображение у = g(x) удовлетворяет условию P(g(xi), g(x2)) < Qp(Xi, Х2) (5) при всех Xi, Х2, то такое отображете называют сжимающим. Теорема. Если отображение у = g(x) сжимаюил,ее, то уравнение х = g(x) имеет единственное решение X и p(X, х +)-Ьдо(х ,Х)2- Поскольку n произвольное, то p(X, g(X)) = 0, и, следовательно, X = g(X). Предположим, что уравнение (4) имеет два решения Xi и Х2. Тогда /5(Xi,X2) = p((7(Xi),(7(X2)) < (7p(Xi,X2) < p(Xi,X2). Мы пришли к противоречию. Теорема доказана. Замечание. При п = О из (6) следует, что р(х, х ) -. Таким образом, все приближения принадлежат области ~ 1(х\ h) : р(х, уР) h, h = а/{1 - q). При доказательстве теоремы отображение g(x) применяется лишь к элементам множества Г2(х°, К) и условие сжимаемости применяется лишь относительно пары элементов из fi(x°, /1). Поэтому в формулировке теоремы достаточно предполагать лишь, что отображение g(x) определено на элементах из Г2(х, К) и удовлетворяет усшовию (5) при xi, Х2 G Q(x°, h). Если решается одно скалярное уравнение, то метод простой итерации имеет простую геометрическую интерпретацию. Построим на плоскости (ж, у) графики у = д(х) п у - х. Точки пересеюния этих линий соответствуют искомому решешно. Ecjni на чертеже имеется точка (ж , = (ж , <7(ж )), то, проведя через нее прямую у = а; + до пе- ресечения с прямой у = X, а затем прямую х = до пересечения с кривой у = д{х), мы получим точку .т +). На рис. 7.1.1 изображе- но поведение последовательных приближений в случаях: о) О < д{х) < 1, б) -1 < д(х) < О, в) 1 < д{х), г) д(х) < -1. Монотонное поведение ж при д{х) > О и колебательное при д{х) < О нетруд1Ю усмотреть также из соотношения ж + - X = д{хП - д{Х) д{Х){х - X). В случае системы нелинейных уравнений F(x) = О аналогом метода Зейделя является итерационный процесс, где компоненты приближений определяются из соотношений Ых-,+\х,...,х) = 0, /2 Л4+\...,х-) = о, /(ж\ж+\...,ж-+1) = 0. Согласно критерию Коши последовательность х имеет некоторый предел X. Переходя к пределу в (6) при Z -> оо, получаем р(Х,х ). Справедлива цепочка соотношений р(Х, g(X)) < р(Х, х +) -Ьр(х +\ g(X)) = р(Х, х +) -bp(g(x ), g(X)) 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 |