Плавные последовательности

30

Плавные последовательности

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

Игра «гонки» и вторые разности

Вероятно, многие из наших читателей знают игру «гонки», описанную в книге M. Гарднера. «Matематические новеллы».

Напомним правила игры. На клетчатой бумаге рисунется более-менее произвольная изогнутая область (трек), у одного края трека для каждой игрока отмещается своей точка с тарта, у другого края — линия ф и и ша. Автомобилисты по очереди делают ходы в один из узлов сетки, причем изменять скорость разрешается только на единицу: если предыдущий ход автоматически был $\overrightarrow{AB}$, то следующий ход $\overrightarrow{BC}$ либо точно такой же ($\overrightarrow{BC} = \overrightarrow{AB}$), либо заканчивается в одном из воспоминаних с $C$ узлов. Ходить можно только по отрезкам, целиком лежащим в пределах трека: тот, кто слишком «разогнался» и вылетел за границу, пропускает ход и начинает с единичной скоростью (так же проводится и старт, рис. 1).

По сравнению с другими играми на клетчатой бумаге (например, с «морским бомем») эта игра замечательна не только близостью к реальной ситу-

цин, но и разнообразием: ведь каждый новый трек — это новая игра.

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

Задача 1. На клетчатой бумаге на одной горизонтальной линии семки $l$ отмещен отрезок $A_0A_1$ длины 1 (сторона одной клетки). Нужно, начав с эмодогом отрезка, построить путь, в котором:

1. каждый следующий шаг $A_kA_{k+1}$ либо макой же, как предыдущий $\overrightarrow{A_kA_{k+1}} = \overrightarrow{A_{k-1}A_k}$, либо отличается от него на одну единицу в ее рхили в и и з (в отличие от «гонок», скорость смещения вправо всегда остается одинаковой: 1 клетка за каждой шаг);

2. последний отрезок $A_nA_{n+1}$ лежит на той же пряной, что и первой $A_0A_1$.

На какую наиболее высокую высоту, при заданном $n$, может подняться макой путь над пряной l?

Эту задачу легко, конечно, сформировать и без клетчатой бумаги. Если считать, что отрезки $A_0A_1$ и $A_nA_{n+1}$ — это отрезки [0, 1] и [$n, n+1$] оси $Ox$ (рис. 2), то путь впол-

31

не определяется последовательностью координат $y_0, y_1, y_2, \dots, y_{n-1}, y_n, y_{n+1}$ точек $A_k = (k; y_k)$, причем эта последовательность должна удовлетворять таким условиям:

a) разность разностей $y_{k+1} - y_k$ и $y_k - y_{k-1}$ соседних членов последовательности, т. е. вморая разность
$$y_{k+1} - 2y_k + y_{k-1} = (y_{k+1} - y_k) - (y_k - y_{k-1})$$
при каждой $k$, $1 \leq k \leq n$, не превыходит 1;

6. $y_0 = y_1 = y_n = y_{n+1} = 0$, а все другие $y_k$ — целые числа. В задаче спрашивается, какое наиболее значение может иметь наиболее или этой последовательности.

Путь, о котором говорится в первой формулировке, — в некотором смысле «график» последовательности $\{y_k\}$. Далее бы мы начали сразу с алгебраической формулировки, его очень полезно было бы «выдумать»: он помогает найти представить смысл условия a).

Перейдем к решению задачи.

Чтобы удовлетворить условия 1), «верхушка» ломаной $A_m A_{m+1}$ должна быть горизонтальной. Ясно, что можно рассматривать только симметричные пути: если $A_m A_{m+1}$ — самое верхнее звено, то более длинную из частей $A_1 \dots A_m$ и $A_{m+1} \dots A_n$ можно укоротить, заменив ее симметриным отражением другой части относительно серединой перпендикулара к отрезку $A_m A_{m+1}$.

Итак, достаточно рассматривать лишь участок по дыма (отведя на него более $n/2 - 1$ наклонных шагов) — с пуск к будет точного таким же.

Кстати, отсюда видно, что для четного $n$ максимальная высота подьема — обозначим ее $h_n$ — будет такой же, как и для следующего за ним нечетного числа: $h_n = h_{n+1}$.

Если подниматься и опускаться под углом $45^\circ$, то максимальная высота, как нетрудно проверить, будет $[n/2] - 1$. Но такой способ будет наиболее лишь до $n = 7$ (рис. 3, a). На рисунке 3, б показан путь для $n = 8$, который поднимается на высоту 4 (а не на $[8/2] - 1 = 3$).

Найти оптимальный путь нам еще раз помогут сообщения симметрины. Ясно, что поначалу выгодно максимальным образом наращивать скорость подьема: $1 + 2 + 3 + \dots$; но — чтобы успеть затормить — так можно поступать лишь до середины участка подьема [1; $m$] (рис. 4, 5).

Эти сообщения можно строго оформить так. Оценим разности одновременного с двух стороны участка:

$$y_1 - y_0 = 0, \quad y_{m+1} - y_m = 0, \quad y_2 - y_1 \leq 1, \quad y_m - y_{m-1} \leq 1, \quad y_3 - y_2 \leq 2, \quad y_{m-1} - y_{m-2} \leq 2, \quad y_4 - y_3 \leq 3, \quad y_{m-2} - y_{m-3} \leq 3, \dots$$

Тепер, чтобы получить оценку для наиболее высокей высоты $h_n$ подьема, т. е. величины $y_m - y_0 = y_{m+1} - y_0$, нужно сложить оценки первых разностей. Таким образом,

для $n = 4k - 2$ (например, $n = 18$, рис. 4)

Рис. 2.

Рис. 3.

32

$$h_n \leq 1 + 2 + \dots + (k - 1) + (k - 1) + \dots + 2 + 1 = k(k - 1);$$
для $n = 4k$ (например, $n = 20$, рис. 5)

$$h_n \leq 1 + 2 + \dots + (k - 1) + k + (k - 1) + \dots + 2 + 1 = k(k - 1) + k = k^2.$$

Ясно — из тех же рисунков, — что эти оценки точные, т. е. что такое высоту подьема можно реализовать. В частности, $h_{18} = 20, h_{20} = 25$.

Итак, мы нашли наиболее высокую высоту $h_n$ при любом $n$. Проверьте, что ответ можно записать в такой компактной форме: $h_n = [n/4] \times [(n + 2)/4]$, или, еще короче, $h_n = [[n/2]]^2/4$. (Напомним, что $h_{n+1} = h_n$ при четном $n$.) Значит, при любом $n$ достаточно точную оценку сверху для $h_n$ дает неравенство $h_n \leq n^2/16$.

Заметим еще, что вершины оптимальный траектории в каждой ее четвертой части лежат на одной параболе. Это происходит не случайно. Ведь если последовательность $x_0, x_1, \dots, x_m$ — арифметическая прогрессия (в частиности, отрезок натурального ряда), а у последовательности $y_0, y_1, \dots, y_m$ вторые разности $y_{k+1} - 2y_k + y_{k-1}$ равны между собой, то точки $(x_0; y_0), (x_1; y_1), \dots, (x_m; y_m)$ лежат на одной параболе*). Именно так обстоятель дело в нашем случае (рис. 4, 5): в первой и последней четвертях траектории $y_{k+1} - 2y_k + y_k-1 = 2y_k + n^2/16$.

*) Ср. «Квант», 1973, № 2, с. 28—29.

$+y_{k-1} = 1$, а в средних четвертях $y_{k+1} - 2y_k + y_{k-1} = -1$.

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

Непрерывный анализ.
Скорости и ускорения

Задача 2. Электровоззамена в моче $O$, пропуская с места, но, дав «задний ход», через $n$ секунды снова вернулся в моче $O$ и оставился в ней. На какое наиболее расстояние $h$ он может удалиться за это время от мочи $O$, если абсолитная величина его ускорения ни в какой момент не превышает а см/сек$^2$?

Эта задача — полный анализ 1, с той разницей, что вместо дискретной последовательности $y_0, y_1, \dots, y_n$ теперь решить о функции $y(t)$ непрерывно в него аргумента $t$ (здесь $t$ — время; будем считать, что $t$ пробегает отрезок от 0 до $n$). Аналогом первых разностей является скорость (первая произведение $y'(t)$ от координаты $y(t)$), аналогом вторых разностей — ускорение (вторая произведение $y''(t) = (y'(t))'$). Мы решим эту задачу, пользоваться физическими терминами; те, кто уже знаком с произvodной и интегралом, легко переведут условия задачи и ее решение на языке математического анализа.

Докажем, что ответ в этой задаче таков: $an^2/16$ (см).

33

Пусть электровоз доступа самого далего от точки $O$ положения $M$ в некоторый момент времени $m$, $0 \leqslant m \leqslant n$. Ясно, что скорость его в этот момент равна нулю. Можно считать, что $m \leqslant n/2$ (в случае $m > n/2$ мы будем следить за движением электровоза на отрезке времени от $m$ до $n$, а не от $0$ до $m$ — ведь до и после момента $m$ движение проискодит совершенно аналогично).

Оценим скорость электровоза $v(t)$ при $0 \leqslant t \leqslant m$. Поскольку $v(0) = 0$, то $v(t) \leqslant at$. С другой стороны, поскольку $v(m) = 0$, то $v(t) \leqslant a(m-t)$. Отсюда следует, что перемещение $h = |OM|$ — площадь под графиком скорости $v(t)$ на отрезке времени $[0, m]$ — не превышает площади треугольника с основанием $m$ и высотой $am/2$, т. е. $h \leqslant am^2/4 \leqslant an^2/16$. Ясно, что эта оценка — точная, причем график оптимального перемещения в каждой четверти отрезка $0 \leqslant t \leqslant n$ — парабола (рис. 6, а—в).

Мы видим, что для «непрерывного» варианта (заданц 2) ответ и решение получается более простыми, чем для «дискретного» (заданц 1).

Большинство реализации задач оптимального управления при их математическом оформлении также допускают и непрерывный, и дискретный варианты. При этом непрерывные модели обычно легче исследовать теоретически, и результаты имеют более красивую форму. Но иногда дискретность задачи дискретется существом делала или упрощает корректную постановку математической задачи; да и для расчетов на цифровых ЭВМ приходится переходить обчично к неокоторому дискретному приближению непрерывной задачи.

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

Числа на окружности.
Формулировка результата

Задание 3. На окружности расположены $n$ действительных чисел, одно из которых равно 1, а сумма всех равна 0. Доказать, что:

a) найдут два соседних числа, различующихся не менее чем на 4/n;
b) найдет число, отличное от среднего арифметического двух севих соседей не менее чем на $16/n^2$.

Далее мы очень кратко изложим решение, позволяющее получить для каждой $n$ точки в оценки в утверждениях a) и b). Эти налучшие возможности оценки таковы:

a) максимальная из разностей между соседними числами не меньше $\frac{4}{n}$, если $n$ четно, и не меньше $\frac{4n}{n^2-1}$, если $n$ нечетно (заметим, что $\frac{4n}{n^2-1} > \frac{4}{n}$);
b) максимальное отклонение числа от среднего арифметического двух севих соседей не меньше соответствующего $\frac{16}{n^2}, \frac{16n}{n^3+n-2}$, $\frac{16}{n^2+4}$ или $\frac{16n}{n^3+n+2}$, если $n$ даем при делении на 4 остаток 0,1, 2 или 3.

На рисунках 7 и 8 изображены оптимальные последовательности (при $n=30$):

34

для последовательности на рисунке 7 разность между любыми двумя соседними числами не меньше 2/15 (это — 4/n при n=30); для последовательности на рисунке 8 отклонение каждого числа от среднего арифметического двух соседей не меньше 2/113 и, как и в первой задаче, точки в каждой четверти отрезка лежат на одной параболе. Доказательство результатов a) и 6) мы проведем ниже лисы для n=30 (для других n оно примерно такое же). Тем самым мы получим решение цикла задач М398 из «Задачника «Кванта»»).

Обозначим данные числа через $y_{-14}, y_{-13}, \dots, y_{15}$ так, что $y_0=1$. Для задачи a) получить нужную оценку нетрудно: если $|y_{k+1}-y_k| \leq \alpha$ для всех $k=-14, \dots, 15$, то, суммируя оценки разностей, как и в задаче 1, получим $y_k \geq 1-|k|\alpha$. Но сумма $\Sigma y_k$ равна нулю, поэтому

$$0 = \Sigma y_k \geq 30 - 2(1+2+\dots+14)\alpha - 15\alpha = 30 - 15^2\alpha,$$

откуда $\alpha \geq 2/15$.

Перейдем к задаче 6). Заметим, что в линияна $\frac{y_{k+1}+y_{k-1}}{2}-y_k$, которое мы должны оценить, — это просто положения «второй разности» $(y_{k+1}-y_k)-(y_k-y_{k-1})$.

Нормировка и повторение. Попробуем действовать с помощью двухратного применения задачи a).

Пусть $y_{k+1}-y_k=y'_k$, $\max_k |y'_k|=\alpha^{**}$. Согласно a), $\alpha \geq 2/15$. К последовательности $z_k=y'_k/\alpha$ мы можем вновь применить a) (нетрудно убедиться, что сумма всех 30 чисел $z_k$ равна нулю и что максимальное из $z_k$ равно единице); поэтому $\max_k |z_{k+1}-z_k| \geq 2/15$, а следовательно,

$$\max_k \frac{|y_{k+1}-2y_k-y_{k-1}|}{2} = (\alpha/2) \max_k |z_k-z_{k-1}| \geq (1/15)\alpha \geq 2/225.$$

Эта оценка примерно вводе хуже требуемой (в общем случае так же получится оценка $8/n^2$ вместе $16/n^2$).

Идея более тонкой оценки проста: нужно, исходя из оценки $|y_{k+1}-2y_k+y_{k-1}| \leq 2\beta$ для вторых разностей, точнее оценить первые разности, затем оценить сами числа $y_k$ (пользовать тем, что $y_0=1$) и, наконец, из равенства $\Sigma y_k=0$ получить оценку сизу для β.

Симметризация и комбинрование оценки.. Прежде чем перейти к осуществлению нашей плана, заметим, что можно ограничиться рассмотрением лишь симметричных последовательностей: таких, для которых $y_k=y_k-1$. В самом деле, из любой последовательности $y_k$, удовлетворяющей условием $y_0=1$, $\Sigma y_k=0$, $|y_{k+1}-$

*) См. «Квант», 1976, № 8.

**) Здесь и ниже k пробегает значение $-14 \leq k \leq 15$. Для k=15 мы полагаем $y_{k+1}=y_{-14}$, — ведь соседнее с $y_{15}$ число на окружности — это $y_{-14}$.

$-2y_k+y_{k-1} \leq 2\beta$, мы можем получить симметриную последовательность $z_k = \frac{y_k+y_k-1}{2}$, удовлетворяющую, как нетрудно проверить, всем этим условиям. (В наших обозначениях $y_0=y_{-0}=y_{15}=y_{-15}=1$.)

Теперь имеем:

$$y_0-y_1=(2y_0-y_1-y_{-1})/2 \leq \beta, y_{14}-y_{15} \leq \beta, y_1-y_2 \leq 3\beta, y_{13}-y_{14} \leq 3\beta, y_2-y_3 \leq 5\beta, y_{12}-y_{13} \leq 5\beta,$$

$$y_6-y_7 \leq 13\beta, y_7-y_8 \leq 15\beta, y_8-y_9 \leq 13\beta,$$

Из первых семи неравенств находим

$$y_k \geq 1-k^2\beta$$ при $0 \leq k \leq 7$;

из остальных

$$y_k \geq 1-(7^2+8^2)\beta+(15-k)^2\beta$$ при $7 \leq k \leq 15$. Суммируя все $y_k$ (напомним, что $y_k=y_{-k}$), найдем $0 \geq 30-15(7^2+8^2)\beta$, откуда $\beta \geq 2/113$.

В заключение — несколько задач, в том или ином относительной связи с рассмотренными выше.

1. В последовательности $a_0, a_1, \dots, a_n$ числа $a_0$ и $a_n$ равны нулю, а модель разности между каждой числом и средним арифметическим двух его соседей не превыходит единиц. Доказите, что $a_k \leq k(n-k)$.

2. Известно, что $a_0, a_1, \dots, a_n$ > $a_k$, и $a_k+1=3a_k-2a_k-1$ при всех $k>1$. Доказите, что $a_{100}>2^{99}$.

3. Дан числа $a_1, \dots, a_7$. Известно, что их сумма равна нулю и что наиболее низкие из них по абсцилотной величины $a_1=2$. Оцените максимум абсцилотной величины вторых разностей.

4. Дан некоторый набор чисел $a_1, \dots, a_n$. Известно, что

$$0 \leq a_1 \leq a_2 \leq 2a_1,$$

$$0 \leq a_2 \leq a_3 \leq 2a_2,$$

и т. д. Доказите, что в сумме $S=\pm a_1 \pm a_2 \pm \dots \pm a_n$ можно было знак так, чтобы выполнялось неравенство: $0 \leq S \leq a_1$.

5. a) Пусть $x_0, x_1, \dots, x_n$ и $y_0, y_1, \dots, y_n$ — две последовательности также, что их «вторые разности» постоянны: $x_{k+1}-2x_k+x_{k-1}=a, y_{k+1}-2y_k+y_{k-1}=b(1 \leq k \leq n-1)$. Доказите, что точки $(x_0;y_0), (x_1;y_1), \dots, (x_n;y_n)$ лежат на одной параболе в плоскости $Oxy$.

6. Доказите, что точки $(x;y)$, где $x=a_1t^2+b_1t+c_1, y=a_2t^2+b_2t+c$, лежат на одной параболе.

7. Пусть функция f периодична с периодом T, имеет первый (a в задание 6) — и второй (производную, не перерывную) периодичную, кроме конечного числа точек; f непрерывна на [0, n].

8. Пусть f определяна на отрезке [0, n], $f(0)=f(n)=0$. Какого наиболее значения может достигать f, если a) $f'(x) \leq M_1$, 6) $|f''(x)| \leq M_2$? (Производные непрерывные вскрыд, кроме конечного числа точек; f непрерывна на [0, n].).

9. Пусть функция f периодична с периодом T, имеет первый (a в задание 6) — и второй (производную, не перерывную) периодичную, кроме конечного числа точек; f непрерывна на [0, n].

10. Пусть f определяна на отрезке [0, n], $f(0)=f(n)=0$. Какого наиболее значения можетxima твердость f, если a) $f'(x) \leq M_1$, 6) $|f''(x)| \leq M_2$? (Производные непрерывные вскрыд, кроме конечного числа точек; f непрерывна на [0, n].)