emigrant90 Mar 20 2017 at 14:10

Метод наборов

3 min

6.9K

Читая книгу «Конкретная математика», одновременно набираясь знаний и осознавая свою некомпетентность в вопросе, ещё в самой первой главе я наткнулся на метод наборов, который авторы используют для решения Задачи Иосифа Флавия. Метод они не объясняют, сочтя его слишком элементарным, так что пришлось искать информацию о нём самому. В рускоязычном сегменте интернетов достаточно подробного описания не нашел, поэтому воспользовался ответом с math.stackexchange.com, который позже перевёл, и теперь представляю его вам, дабы те, кто тоже не понял метод инстинктивно, смогли проникнуться.
Далее — перевод от первого лица.

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

Метод повторений (базовые понятия)

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

$\begin{align*} {x_0} &= {a_0} \\ {x_n} &= {a_n} + {x_{n-1}}, \quad n>0 \end{align*}$

и у нас есть вторая рекуррентность для $inline$

$\begin{align*} {y_0} &= {b_0} \\ {y_n} &= {b_n} + {y_{n-1}}, \quad n>0 \end{align*}$

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

${\alpha a_n} + {\beta b_n}$

будет иметь результат

${\alpha x_n} + {\beta y_n}$

Чтобы показать это наглядно, допустим ${a_n} = 3$ и ${b_n} = {5n^2} + {1}$ . Допуская, что мы знаем результаты ${x_n}$ и ${y_n}$ рекуррентностей

$\begin{align*} {x_0} &= {3} & {y_0} &= {1} \\ {x_n} &= {3} + {x_{n-1}},\quad n>0 & {y_n} &= {5n^2} + {1} + {y_{n-1}},\quad n>0 \end{align*}$

мы так же знаем по линейности, что результат рекуррентности

$\begin{align*} {z_0} &= {7} \\ {z_n} &= {2n^2} + {7} + {z_{n-1}} \end{align*}$

равен

$\begin{align*} {z_n} = \frac{11}{5}{x_n} + \frac{2}{5}{y_n} \end{align*}$

Видно, что в этом случае мы имеем набор двух решений ${x_n}$ и ${y_n}$ , которые мы можем линейно объединить для нахождения требуемого решения ${z_n}$ .

НО: мы обычно начинаем с рекуррентности ${z_n}$ не имея в наличии подходящих кандидатов.И это является вторым ингредиентом. Мы должны построить набор.

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

$\begin{align*} {z_0} &= {7} \\ {z_n} &= {2n^2} + {7} + {z_{n-1}}, \quad {n} > 0 \tag{1} \end{align*}$

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

$\begin{align*} {\mathcal{Z}_0} &= {a_0} \\ {\mathcal{Z}_n} &= {a_n} + {\mathcal{Z}_{n-1}}, \quad {n} > 0 \end{align*}$

Самое время для некоторых творческий идей, что обычно является самой сложной частью в использовании этого метода. Мы хотим найти набор, состоящий из двух членов. Один из них с ${a_n} = const$ , а другой с ${a_n}$ равным квадрату от $inline$ . Для этого мы должны подобрать несколько подходящих кандидатов для ${\mathcal{Z}_n}$ , слагаемым которого является искомое ${a_n}$ .

Давайте подберём первого кадидата. Это довольно просто (в этом случае), т.к. равенство ${\mathcal{Z}_n} = n$ даёт

$\begin{align*} {a_0} &= {0} \\ {n} &= {a_n} + n - 1, \quad {n} > 0 \end{align*}$

и мы находим: ${a_0} = {0}$ и ${a_n} = 1, \quad {n} > 0$ .
Мы получили первого кандидата, допустим ${x_n}$ , такого, что

$\begin{align*} {x_0} &= {0} \\ {x_n} &= {1} + {x_{n-1}}, \quad {n} > 0 \tag{2} \end{align*}$

По схожему принципу мы можем найти подходящего второго кандидата, который обеспечит нас ${a_n} =$ квадрат от $inline$ , заметив, что сумма натуральных чисел в степени $inline$ обычно сводится к чему-то в степени $inline$ . Давайте подберём ${\mathcal{Z}_n} = {n^3}$ , который дает

$\begin{align*} {a_0} &= 0 \\ {n^3} &= {a_n} + {({n} - {1})}^3,\quad{n} > {0} \end{align*}$

и получим ${a_0} = {0}$ и ${a_n} = {3n^2} - {3n} + {1},\quad {n} > {0}$ .

Мы получили второго кандидата, допустим $inline$ , для которого справедливо

$\begin{align*} {y_0} &= {0}\\ {y_n} &= {3n^2} - {3n} + {1} + {y_{n-1}}, \quad {n} > {0}\tag{3} \end{align*}$

Мы видим, что ${y_n}$ также содержит линейное слагаемое в $inline$ , которое для нас излишне, т.к. мы ищем (следуя формуле (1)) ${a_n} = {2n^2} + {7}$ . Поэтому мы расширим наш набор третьим членом, который обеспечит нас ${a_n}$ линейным по $inline$ . Таким образом мы будем иметь возможность избавиться от линейного слагаемого $inline$ соответствующей линейной комбинацией трёх членов набора. Мы подберём такой ${\mathcal{Z}_n} = {n^2}$ , который даёт

$\begin{align*} a_0&=0\\ n^2&=a_n+(n-1)^2, \quad n>0 \end{align*}$

и найдём ${a_0} = {0}$ и ${a_n} = {2n} - {1}, \quad {n} > {0}$ .

Таким образом мы получим третьего кандидата, допустим $inline$ , для которого справедливо

$\begin{align*} u_0&=0\\ u_n&=2n-1+u_{n-1},\quad n>0\tag{4} \end{align*}$

Давайте взглянем на набор:

Обзор трёх кандидатов

$\begin{array}{rlcr} \mathcal{Z}_n&&a_n&\\ \hline\\ x_n=&n\qquad&1&\qquad\qquad\text{acc. to }(2)\\ y_n=&n^3\qquad&3n^2-3n+1&\qquad\qquad\text{acc. to }(3)\\ u_n=&n^2\qquad&2n-1&\qquad\qquad\text{acc. to }(4)\\ \end{array}$

Используя подходящую линейную комбинацию можно заметить, что

$\begin{align*} a_n&=2n^2+7\\ &=\frac{2}{3}\left(3n^2-3n+1\right)+\left(2n-1\right)+\frac{22}{3} \end{align*}$

таким образом мы придём к

$\begin{align*} z_n&=\frac{22}{3}x_n+\frac{2}{3}y_n+u_n+c_0\\ &=\frac{1}{3}n\left(2n^2+3n+22\right)+c_0 \end{align*}$

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

$z_n=\frac{1}{3}n\left(2n^2+3n+22\right)+7,\quad n\geq 0$

Подытожим.

Описание метода наборов:
Для решения рекуррентности формы

$\begin{align*} x_n=f(n)+g(x_{n-1},x_{n-2},\ldots,x_0)\tag{5} \end{align*}$

мы находим кандидатов $inline$ , ..., $inline$ формулы $inline$ таким образом, чтобы они могли быть линейно приведены к форме

$f(n)=\lambda_1 f_1(n)+\ldots+\lambda_k f_k(n)$
после чего рассматриваем обобщённое представление (5) заменяя $inline$ на $inline$

$\mathcal{Z}_n=a_n+g(\mathcal{Z}_{n-1},\mathcal{Z}_{n-2},\ldots,\mathcal{Z}_0)$
и решаем более простые рекуррентности

$x_n^{(l)}=f_l(n)+g(x_{n-1},x_{n-2},\ldots,x_0),\quad 1 \leq l \leq k$

подбирая $x_n^{(l)}$ чтобы получить $inline$ .
Решения $x_n^{(l)}$ при $inline$ формируют набор для решения $inline$ .
Определяем линейную комбинацию

$f(n)=\lambda_1 f_1(n)+\ldots+\lambda_k f_k(n)$
и выводим решение

$x_n=\lambda_1 x_n^{(1)}+\ldots+\lambda_k x_n^{(k)}+c_0$
после чего определяем $inline$ согласно начальным условиям.

Примечание: Возможны ситуации, в которых придётся определить более одного начального условия.
Примечание: Возможна ситуация, когда набор потребует дальнейшего расширения с целью избавиться от лишних слагаемых, которые появляются при расчёте $x_n^{(l)}$ .

Tags:

Hubs: