Главная > Итерационные методы решения уравнений
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
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
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

2.2. ЛИНЕЙНАЯ И СВЕРХЛИНЕЙНАЯ СХОДИМОСТЬ

В § 2.1 для решения уравнения использовалась итерационная процедура Для задач, которые мы будем рассматривать в дальнейшем, это нетипично. В общем случае нам предстоит иметь дело с уравнением вида и для него строить функционал, выполняющий роль ИФ. В § 2.1 мы показали, что если удовлетворяет сжимающему условию Липшица, то итерационная последовательность сходится к единственному решению задачи о неподвижной точке. В дальнейшем будем уделять больше внимания не поиску слабых достаточных

условий, обеспечивающих сходимость итерационной последовательности, а построению таких ИФ, для которых эта последовательность сходится быстро. При этом мы будем готовы потребовать выполнения гораздо более сильных условий, чем условие Липшица. В частности, будем предполагать, что в рассматриваемом интервале имеет нуль.

2.2.1. Линейная сходимость.

Предположим, что производная непрерывна в окрестности точки а. Если и функция непрерывна, то

Поэтому потребуем, чтобы

Отметим, что

где расположено в промежутке между Используя (2.7), получаем

Потребуем, чтобы в некоторой окрестности точки а выполнялось условие Ввиду непрерывности для этого достаточно потребовать, чтобы Тогда существует такая окрестность точки а, что для всех х из этой окрестности и Тогда

Точку а, для которой при любой начальной точке взятой из достаточно малой окрестности точки а, последовательность сходится к а, называют точкой притяжения. Мы придерживаемся терминологии Ритта (см. Ostrowski [2.2-1, р. 26], где также определяется точка отталкивания). Только что доказанный результат можно сформулировать так: если производная непрерывна в окрестности точки а, для которой то а является точкой притяжения.

Далее, пусть Тогда не обращается в нуль в некоторой окрестности точки а. Положим при этом (2.8) примет вид

Ясно, что если не обращается в нуль, то и -отлично от нуля для любого конечного номера Иными словами, итерационная последовательность не может сойтись к решению за конечное число шагов, если ее члены лежат в окрестности точки а, в которой Следовательно, Это — случай сходимости первого порядка, или линейной сходимости.

В случае же сверхлинейной сходимости можно отказаться от требования итерационная последовательность всегда сходится в некоторой окрестности точки а.

2.2.2. Сверхлинейная сходимость.

В дополнение к условию предположим теперь, что производная непрерывна. Тогда

где точка расположена в промежутке между Ясно, что имеет порядок только в том случае, если Поэтому мы предполагаем, что

В этом случае где Поскольку производная также не обращается в нуль в некоторой окрестности точки а. Но тогда алгоритм не может сойтись за конечное число шагов, если и все члены итерационной последовательности лежат в окрестности точки а, где не обращается в нуль (см. также начало . Кроме того,

Хартри основывается на условиях (2.9), давая определение порядка ИФ. Однако такое определение неприменимо к одноточечным ИФ с памятью. Поэтому для наших целей полезнее использовать условия (2.9) как часть утверждения теоремы.

Теорема 2.2. Предположим, что производная итерационной функции непрерывна в некоторой окрестности точки а. Положим а. Тогда имеет порядок в том и только том случае, если Кроме того,

Напомним, что наличие у итерационной функции некоторого положительного порядка еще не гарантирует сходимости порождаемой ею последовательности. Достаточные условия сходимости этой последовательности будут установлены ниже.

Пример 2.1. Пусть (ИФ Ньютона). Предположим, что производная непрерывна, а Непосредственное вычисление показывает, что Следовательно, ИФ Ньютона имеет второй порядок и Здесь мы вынуждены предполагать непрерывность для того, чтобы выполнялось условие теоремы 2.2 о непрерывности . В гл. 4 будет установлено, что на самом деле достаточно непрерывности

В п. 2.2.1 было показано, что последовательность, порожденная ИФ линейного порядка, может не сходиться ни в какой окрестности точки а. Теперь мы увидим, что порожденная сверхлинейной ИФ последовательность всегда сходится в некоторой окрестности точки а. Проводимые ниже рассуждения охватывают случаи как сверхлинейной, так и линейной сходимости.

Исходным моментом наших рассуждений, является соотношение

Положим (это обозначение было разъяснено в конце п. 1.2.1). Предположим, что производная непрерывна на и соотношение выполнено для всех х из

Из условия следует, что Поэтому

Предположим, что

Тогда Следовательно, Докажем по индукции, что при выполнении (2.12) для всех справедливо

В самом деле, пусть (2.13) выполнено для некоторого номера Тогда

Следовательно, (2.13) выполнено и для что завершает индукцию. Поскольку то Таким образом, доказана

Теорема 2.3. Предположим, что производная непрерывна на интервале Пусть, кроме того, и соотношение

выполняется для всех х из причем Тогда для любого

2.2.3. Преимущества итерационных функций высокого порядка.

Пусть производная непрерывна в окрестности точки а и имеет первый порядок. Сходимость к а последовательности, порожденной эквивалентна условию за исключением случая, когда какой-то из элементов оказывается в точности равным а. Существенность последнего условия

иллюстрирует пример

В рассматриваемом случае непрерывна в окрестности нуля и тем не менее итерационная последовательность сходится для любого из единичного интервала. За исключением подобных случаев, для сходимости необходимо, чтобы по модулю не превышало единицу. В то же время, если производная непрерывна в некоторой окрестности точки а при то всегда существует такая окрестность точки а, в которой итерация обязательно сходится.

Это только одно из целого ряда преимуществ сверхлинейной сходимости над линейной. Пожалуй, наиболее важное преимущество можно нестрого сформулировать так: приближение к а имеет в раз больше верных цифр по сравнению с (см. приложение С).

ИФ более высокого порядка во многих случаях требуют меньшего суммарного количества вычислений значений функции и ее производных. Напомним, что эффективность использования информации ИФ равна отношению порядка к количеству элементов новой информации, приходящихся на одну итерацию. В гл. 5 мы покажем, что существуют ИФ всех порядков с эффективностью использования информации, равной 1. Такие ИФ мы назвали оптимальными. Для простоты рассуждений предположим, что оптимальные ИФ соответственно второго и третьего порядков. Пусть получено из 0 в результате трехкратного применения получено из в результате двукратного применения В обоих случаях использовано по шесть элементов информации, однако в то время как В работе Ehrmann [2.2-3] рассматривается семейство ИФ, содержащее ИФ произвольных порядков, и выясняется, какой порядок при некоторых предположениях является «наилучшим».

Основные недостатки, проявляющиеся при использовании ИФ высокого порядка, состоят в росте сложности формул и стоимости вычислений высших производных функции В гл. 8, 9 будет показано, что у некоторых многоточечных ИФ высокого порядка эти недостатки отсутствуют.

Отметим, что если функция удовлетворяет дифференциальному уравнению, то может оказаться удобнее вычислять ее производные посредством этого дифференциального уравнения. Например, пусть задана дифференциальным уравнением второго порядка. Если вычислены, то можно получить из дифференциального уравнения. Дифференцируя его, получаем и т. д.

Может показаться, что построение ИФ высокого порядка для произвольных сопряжено с какими-то трудностями. Однако это не так: многими авторами предложены методы, позволяющие строить ИФ произвольного порядка (см., например, Bodewig [2.2-4], Ehrmann [2.2-5], Ludwig [2.2-6], Е. Schroder [2.2-7], Schwerdtfeger [2.2-8], Zajta [2.2-9]). Значительная часть этих методов связана с построением ИФ, для которых

Ниже будет предложен ряд методов построения ИФ произвольного порядка, удовлетворяющих некоторым другим критериям. Таким образом, будет показано, что для построения ИФ необязательно использовать соотношения (2.14).

Методика, развитая Стеффенсоном, Хаусхолдером и Островским, позволяет получать одну ИФ второго порядка из двух ИФ первого порядка (приложение

Во многих областях численного анализа при построении аппроксимаций предъявляют требование точности их для некоторого количества степеней х. В нашем случае ИФ, полученные прямой интерполяцией , дают за одну итерацию точное решение а для всех многочленов не выше некоторой степени. Однако это свойство не является общим для любых ИФ. Вообще говоря, использование степеней х целесообразно лишь с той точки зрения, что имеет корень кратности

Пример 2.2. Положим

имеет второй порядок и вычисляет а за одну итерацию для любой линейной функции также имеет второй порядок. Однако для итерационная функция не. дает решения за одну итерацию и вообще не сходится при

1
Оглавление
email@scask.ru