Таким образом, мы убедились в том, что способ выбора многочле-
нов Q
ny
Р
ту
при котором величина? (/) — Qn
1
(t) Р
т
(t) была бы до-
статочно мала [а это гарантирует быструю сходимость КР
Х
(^-ме-
тода],
оказался связанным с задачей о выборе квадратуры S
t
[от S
t
-
квадратуры зависит вид функции г (*)], а от выбора S
t
зависит по-
грешность метода сеток. Очевидна
Лемма 11.19.1. При
т
= n—l,7(t) = Р
п
_
г
(t)/Q
n
(t) и f
x
(х) =
= F (х) для
периодической
задачи имеет место равенство w = S
t
и>
где
сеточные
функции
и>
w являются
соответственно
периодическими
решениями систем разностных уравнений (11.19.1), (11.19.5).
Лемма 11.19.1 следует из того, что в указанных условиях
7 (t) [1 - cr (t)]'
1
= [Q
n
(t) - Р
п
.
г
(t) с]'
1
Р
п
_г (/), т. е. формулы
(9.11.15) для S
t
uYL (11.19.7) для w совпадают при f
x
= F.
Из леммы 11.19.1 вытекает [119]
Следствие 11.19.1. Существует прямой алгоритм 51 решения пе-
риодической задачи, для которого Ц (51) —
общее
число приведенных
арифметических
действий
—есть величина порядка
О
(MN)
f
а Э(51) —
двоичный логарифм числа ячеек памяти ЭВМ, необходимых для pea-
лизации алгоритма
51,
есть
величина log
2
N + О (/).
В самом деле, решение периодической задачи сведется в условиях
леммы 11.19.1 к решению периодической задачи для сильноэллип-
тического обыкновенного дифференциального уравнения 2Af-ro
порядка с постоянными коэффициентами, а последняя задача сводится
к последовательному М-кратному интегрированию периодических
задач для уравнений 2-го порядка, правые части которых, заданные в N
точках, зависят только от результата предыдущего интегрирования
[см.
формулы (11.10.17), (11.10.18)]. А так как каждая из периодиче-
ских задач для уравнения 2-го порядка решается методом прогонки
с затратой О (N) действий и запоминанием О (N) чисел, всего потре-
буется О (MN) действий с запоминанием только О (N) чисел.
В условиях леммы 11.19.1 имеет место равенство М = п. Это
накладывает ограничения на вид операции Р. Поэтому рассмотрим
другой способ выбора Р
т
и Q
n
. Пусть P
n
_i, Q
n
выбраны согласно
лемме
11.10.1;
они являются соответственно числителем и знамег
нателем подходящей для г (t) дроби порядка 2п. Пусть п < М, а
многочлены См-\ (f)
y
Вм (t), определяющие квадратуру S
t
(см. § 9.11),
являются также соответственно числителем и знаменателем подхо-
дящей для г (t) дроби порядка 2М. Тогда, учитывая неравенства
(11.10.6), получаем 0<^"(/, Q
n
, Р
п
_
ъ
с) = {С
М
-\1В
М
— P
n
-i/Qn)X
X (1 - cPnJQnT
1
< (г (t)-P
n
JQ
n
) (l-cP
n
JQ
n
)~\ т. е. по лемме
11.10.1 имеем
||-ф||
(Q
n
, Р
п
_
ъ
с) = О
(я"
1
).
Таким образом, скорость
сходимости KPi(n) -метода оказалась асимптотически равна
— In сп'
1
. На каждую операцию К затрачивается О (NM) действий
и требуется
О
(N) ячеек памяти ЭВМ, а на операцию Р
г
(п) затрачи-
вается 0 (nN) Действий и требуется О (N) ячеек памяти. Пусть при
N, М ->оо цена операции /С, которая обозначена Ц (К), с точностью
до членов О (N), О (М) равна aMN, а Ц (Р (п)) — цена операции
Pi (п) — с точностью до членов о (N), О (п) равна dn N, где a, d —
386