Главная > Основы компьютерной алгебры с приложениями
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
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
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
След.
Макеты страниц

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

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

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

7.3.3. Теорема Винсента: расширение и приложения

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

Мы начинаем с тщательного исследования правила о знаках Кардано-Декарта (теорема 7.2.6), утверждающего, что число положительных корней полиномиального уравнения не может превосходить числа v перемен знаков в последовательности его коэффициентов, и если четное число.

Более внимательное рассмотрение теоремы 7.2.6 показывает, что это довольно слабое предложение; оно дает точное число положительных корней полиномиального уравнения только в следующих двух частных случаях [ниже, когда мы допускаем терминологическую вольность и говорим «перемена знаков», мы имеем в виду перемены знаков в последовательности коэффициентов полинома

Если нет перемен знаков, то нет и положительных корней, . Если имеется одна перемена знаков, то имеется один положительный корень.

Как мы увидим впоследствии, эти два частных случая играют важную роль. Более того, справедливо также утверждение, обратное к i, поскольку имеет место следующая

Лемма 7.3.6 (Стодола). Если полиномиальное уравнение

с вещественными коэффициентами имеет только корни с отрицательными вещественными частями, то все его коэффициенты положительны и, следовательно, не дают перемен знаков.

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

Относительно второго частного случая теоремы 7.2.6 (случай упомянутый выше) заметим, что его обращение в общем случае неверно, в чем можно убедиться на примере полиномиального уравнения у которого имеется один положительный корень, но три перемены знаков. Однако при более ограничительных условиях обратное также верно; формально это выражается следующим образом:

Лемма 7.3.7 (Akritas-Danielopoulos, 1985). Пусть — полиномиальное уравнение степени с вещественными коэффициентами без кратных корней, имеющее один положительный корень и корней с отрицательными вещественными частями (комплексные корни появляются попарно сопряженными) и такое, что его корни могут быть выражены в виде

, где

Тогда в форме распределения по степеням содержит ровно одну перемену знаков в последовательности своих коэффициентов.

Доказательство. С точностью до постоянного множителя полином может быть записан в виде

где

— сумма, состоящая из членов Ясно, что можно переписать в виде

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

а поскольку по предположению для мы получаем

Поэтому можно написать

где и, следовательно

Затем нам нужно показать, что отношение уменьшается с увеличением к, иными словами, Однако это тривиально, поскольку, пользуясь мы получаем

и

и нам нужно теперь доказать, что

Действительно, это неравенство справедливо, поскольку, с одной стороны,

и, с другой стороны,

Таким образом, так как и отношение уменьшается с увеличением к, мы доказали теорему.

Тщательно проанализировав два частных случая теоремы 7.2.6, мы можем теперь сформулировать теорему Винсента, существенно от них зависящую [см. также историческое замечание 5, (Akritas et al., 1978; Lloyd, 1979; Poggendorff, 1863)].

Теорема 7.3.8 (Vincent, 1836). Если в полиномиальном уравнении с рациональными коэффициентами и без кратных корней сделать последовательно подстановки вида

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

в то время как в первом случае корней нет.

Доказательство. Доказательство этой теоремы можно найти в оригинальной работе Винсента, и здесь оно опускается. Вместо этого непосредственно ниже мы представляем доказательство более общей теоремы.

Очевидно, что эта теорема обрабатывает только положительные корни; отрицательные корни исследуют, заменяя на в исходном полиномиальном уравнении. Общность этой теоремы не ограничивается предположением, что не должно быть кратных корней, потому что, как и в случае теоремы Штурма, мы можем сначала применить разложение на свободные от квадратов множители. Сам Винсент говорил, что теорему 7.3.8 сформулировал в 1827 г. Фурье, но он не дал какого-либо ее доказательства (или если и дал, то оно никогда не было найдено); более того, Лагранж использовал главную идею этой теоремы гораздо раньше.

Зависимость теоремы Винсента от теоремы Бюдана легко заметить, если каждую подстановку вида заменить эквивалентной парой подстановок

Интуитивно цель ряда последовательных подстановок вида применяемых к уравнению состоит в том, чтобы один из его положительных корней оказался внутри интервала (0,1), а все остальные — в или наоборот, за исключением, конечно, случая, когда 1 — корень. В первом случае последующая подстановка даст в результате уравнение с одним только корнем в , в то время как во втором случае тот же результат достигается с помощью подстановки .

В теореме 7.3.8 естественно возникает вопрос относительно максимума числа подстановок вида необходимых, чтобы получить полиномиальное уравнение с не более чем одной переменой знаков. Ответ дается следующей теоремой (см. историческое замечание 6).

Теорема 7.3.9 (Винсент-Успенский-Акритас). Пусть — полиномиальное уравнение степени рациональными коэффициентами и без кратных корней, и пусть — наименьшее расстояние между любыми двумя из его корней. Пусть — наименьший индекс, такой, что

где есть элемент последовательности Фибоначчи и

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

эквивалентна ряду последовательных подстановок вида преобразует уравнение в уравнение которое имеет не более одной перемены знаков.

Локазательство. Чтобы доказать теорему, достаточно показать, что после последовательных подстановок вида вещественные части всех комплексных корней, также как все вещественные корни, за исключением, может быть, одного, становятся отрицательными. (Чрезвычайно важно отметить, что корни преобразованного уравнения группируются вокруг —1.)

Действительно пусть есть подходящая дробь для цепной дроби

Из разд. 2.2.3 нам известно, что для мы имеем

Так как то, следовательно, . Далее, может быть выражено в виде

откуда следует, что

Ясно, что если о — любой корень уравнения то величина определяемая формулой (V4), является соответствующим корнем преобразованного уравнения а. Предположим, что о — комплексный корень уравнения т.е. . В этом случае вещественная часть соответствующего корня равна

и обязательно отрицательна, если Если, наоборот, значение a, очевидно, содержится между двумя последовательными подходящими дробями абсолютное значение разности между которыми равно Следовательно,

откуда следует, что

Из (V5) и (V6) мы заключаем, что значение отрицательно, если Чтобы доказать, что это так в нашем случае, прежде всего заметим, что, поскольку — минимальное расстояние между любыми двумя корнями уравнения мы имеем

откуда получаем более того, мы знаем, что и, согласно (V1), что Тогда, очевидно, откуда следует, что Из последних двух неравенств мы получаем доказав, таким образом, что это

очевидным образом верно для всех комплексных корней преобразованного уравнения

b. Предположим теперь, что — вещественный корень уравнения и рассмотрим сначала случай, когда для всех вещественных корней

Из (V4) следует, что все вещественные корни преобразованного уравнения будут отрицательными; более того, по предположению все комплексные корни уравнения имеют отрицательные вещественные части. Следовательно, по лемме не имеет перемен знаков.

Предположим, теперь, что для некоторого вещественного корня о

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

из (V4) следует, что

или

где

Теперь

и, следовательно,

Из последнего выражения и второго неравенства формулы (VI) мы заключаем, что Таким образом, корни преобразованного уравнения соответствующие корням уравнения которые все отличны от имеют вид

т.е. корни преобразованного уравнения имеют отрицательные вещественные части и группируются вокруг —1. Если сделать подстановку

где

то преобразованный полином может быть записан в виде

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

Нам осталось рассмотреть теперь только случай, когда в (V7) имеет место равенство, т.е.

Если то из (V4) мы видим, что и, очевидно, у преобразованного уравнения нет перемен знаков (лемма 7.3.6). В случае мы имеем и преобразованное уравнение редуцируется к степени Поскольку снова все корни имеют отрицательные вещественные части, мы заключаем из леммы 7.3.6, что не имеет перемен знаков. Таким образом, мы полностью доказали теорему.

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

Следствие 7.3.10. В предположениях теоремы 7.3.9

Доказательство. По определению — наименьший индекс, такой, что одновременно выполняются оба неравенства (VI). Ясно, что одно из этих неравенств (а возможно, оба) не будет выполняться, если мы уменьшим на единицу; предположим, что не выполняется первое, так что

Применяя соотношение (с правой частью уравнения, округленной до ближайшего целого), где из (V9) получаем, что откуда заключаем, что

Более того, напомним, что из теоремы 7.2.12 (Mahler, 1964) мы имеем

Если мы объединим (V10) и (VII) и примем во внимание тот факт, что то следствие будет доказано. [Тот же результат получается, если предположить, что не выполнено второе неравенство

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

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

i. Подстановка цепной дроби (V3) может также быть записана как

где есть подходящая дробь для цепной дроби

и, как уже говорилось, для к мы имеем

ii. Расстояние между двумя последовательными подходящими дробями равно Ясно, что наименьшее значение встречается, когда для всех i. Тогда число Фибоначчи. Это объясняет, почему существует связь между числами Фибоначчи и расстоянием Д в теореме 7.3.9.

iii. Пусть — уравнение, полученное из после подстановки вида (V13), соответствующей ряду сдаигов и инверсий. Заметим, что (V13) отображает интервал на х-интервал, неупорядоченные концевые точки которого — последовательные подходящие дроби Если длина этого х-интервала меньше, чем , то он содержит не более одного корня уравнения а соответствующее уравнение имеет не более одного корня в интервале .

iv. Если у — этот положительный корень уравнения то соответствующий корень уравнения может легко быть получен из (V13). Мы знаем только, что находится в интервале поэтому, подставляя вместо у в (V13) один раз 0, а другой мы получаем для положительного корня изолирующий интервал, неупорядоченные концевые точки которого — это Каждому положительно-му корню соответствует своя цепная дробь; нужно вычислить не более m неполных частных для отделения любого положительного корня. (Как мы уже упоминали, отрицательные корни могут быть отделены, если мы заменим на — в исходном уравнении.)

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