Задачка, простенькая, но лень сейчас, в полпервого ночи, решать

[rezoner]

Некто записывает в каждый из 7 дней число, целое и положительное, в таблицу.

На 8-день он записывает в таблицу среднее из предыдущих 7.

На девятый день - среднее из предыдущих семи, т.е. дней 2-8 ("скользящее среднее").

Так он продолжает. Надо доказать, что последовательность значений для N-ного дня сходится.

Comments

[brevi.livejournal.com]

Доказательство «в лоб» такое: для любых начальных значений в первые 7 дней, значение в день n даётся суммой 7 членов вида a_i * z_i^n, где i=1,…,7, в которой z_i это 7 (возможно, комплексных) корней уравнения 1 + z + z^2 + … + z^6 = 7 * z^7, а коэффициенты a_i подбираются так, чтобы получить 7 заданных начальных значений. Для доказательства утверждения задачи достаточно доказать, что все корни этого многочлена, кроме очевидного корня z=1, удовлетворяют условию |z| < 1. Это проще всего доказывается от противного: предположим, что есть корень с |z| >= 1, не равный 1, и получим противоречие.

[rezoner.livejournal.com]

Не очень понятно, попробую разобраться.

[brevi.livejournal.com]

Давайте так: правило «скользящего среднего» — всего лишь частный случай линейной рекурсии глубины N (в вашем примере N=7), когда любое число x_n, стоящее на n-ном месте в генерируемой последовательности, где n>N, получается как линейная комбинация предыдущих N членов с фиксированными коэффициентами. Попробуем найти такое число z, что последовательность x_n = z^n удовлетворяет условию рекурсии: подставим в формулу рекурсии и получим уравнение для z в виде многочлена. Таким образом, для любого корня z этого многочлена последовательность z^n удовлетворяет условию рекурсии (но не начальным условиям)

[brevi.livejournal.com]

Условие рекурсии линейно, поэтому любая линейная комбинация выполняющих его последовательностей тоже его выполняет. Чтобы удовлетворить N начальных условий, нужно иметь N (независимых) последовательностей. Если у многочлена все корни z_i различны, то это будут N последовательностей z_i^n. (Если есть кратные корни, то нужно делать дополнительные телодвижения, но в нашем частном случае «скользящего среднего» у нас все в порядке и без этого). Отсюда формула.

[rezoner.livejournal.com]

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

[brevi.livejournal.com]

Многочлен степени 7 нужен для того, чтобы удовлетворить условие рекурсии глубины 7: если z - это любой (комплексный?) корень многочлена, то последовательность z^n выполняет условия рекурсии. Но такая последовательность не выполняет, в общем случае, начальные условия — поэтому мы рассматриваем всевозможные линейные комбинации таких степенных последовательностей, в надежде, что какая-то линейная комбинация подойдет. Начальных условий 7, поэтому у нас будет система из 7 уравнений для ещё неизвестных коэффициентов линейных комбинаций — поэтому таких коэффициентов тоже должно быть не меньше семи, иначе их подогнать в общем случае нельзя. Получается, что нам нужно никак не менее 7 базисных последовательностей. К счастью, их у нас как раз ровно 7, так как у нашего многочлена 7-й степени ровно 7 различных корней. (А если бы были кратные корни, то пришлось бы базисные последовательности конструировать чуть-чуть иначе)

[clovis3.livejournal.com]

Ух ты! Я дожил до седых ..., но не осознавал, что линейная рекурсия -- это чистая линейная алгебра!

Давайте, объясню с подробностями.

Ваша рекурсия -- это линейное преобразование n-мерного пространства (у Вас n=7) колонок высоты n. Это преобразование описывается матрицей А размера n x n, и вопрос состоит в том, есть ли предел у A^N, когда N стремится к бесконечности. Главный приём при ответе на этот вопрос -- это матрицу надо диагонализовать (или привести к жордановой нормальной форме), и тогда её степень легко посчитать. Если матрица диагонализуется, то её степень -- это просто надо возвести в эту степень диагональные элементы, они же собственные значения. Если все собственные значения, за исключением одного, пусть даже комплексные, но по модулю меньше 1, а оставшееся равно единице, до понятно, что в пределе мы получим матрицу, где всюду нули, кроме одной единицы на диагонали. Это значит, что A^N в пределе будет проектором на собственный вектор с собственным значением 1, причём проекция будет осуществляться вдоль остальных собственных векторов.

Матрицу A нетрудно посчитать: её i-ая колонка -- это то, что получится с колонкой, где все нули, кроме единицы в i-ой строке, если применить одну рекурсию. То есть, в этой матрице всюду нули за исключением первой "наддиагонали", где единицы, и последней строки, заполненной числами 1/n. Такая матрица с общими числами в нижней строке (точнее, её транспозиция) очень хорошо известна в узких кругах. Эта матрица "регулярна", что означает, среди прочего, что если хоть одно из чисел в нижней строке не равно нулю, то A диагонализуема.

Теперь найдём собственные вектора и собственные значения. Ввиду специального вида A, легко видеть, что собственный вектор с собственным значением z должен иметь вид [1, z, z^2, ... , z^{n-1}], причём поскольку рекурсия заменяет z^{n-1} на

( 1 + z + ... + z^{n-1} )/n = (z^n - 1)/(z-1)*n

то получаем условие

( 1 + z + ... + z^{n-1} )/n = z^n,

то есть, z` должен быть корнем многочлена

p(z) = n z^n - (z^{n-1} + ... + z + 1)

У этого многочлена есть один корень 1 (его собственный вектор имеет вид v = [1,...,1]). Осталось доказать, что остальные корни по модулю меньше единицы. Для этого достаточно заметить, что

|1 + z + ... + z^{n-1}| < or = n |z| ^{n-1},

а если ещё и |z|>1, то

|1 + z + ... + z^{n-1}| < or = n |z| ^{n-1} < n |z|^n.

Следовательно, корни могут быть только с |z| <= 1. Oднако если z не есть положительное вещественное число, то имеем строгое неравенство

|1 + z + ... + z^{n-1}| < n |z| ^{n-1},

и следовательно, если |z|=1, то z=1. Теперь надо доказать, что z=1 имеет кратность 1. Вообще-то это следует из регулярности матрицы A, но можно и явно убедиться, взяв производную от p(z) и убедившись, что z=1 не есть её корень, что вытекает из неравенства

n^2 > n(n-1)/2

В общем, в итоге мы доказали, что A^N сходится к проектору на [1, 1, ... , 1], то есть, рекурсивная последовательность сойдётся.

Чтобы найти предел по начальным данным, надо знать остальные корни, но как их найдёшь для n>3?

[ichthuss]

Предел в данном случае легко находится, т.к. среднеарифметическое значений на каждом шаге сохраняется.

[clovis3.livejournal.com]

В том-то и дело, что не сохраняется! Возьмите крайний пример: 0, 0, ... ,0 , 1 превратится в 0, 0, ... , 0, 1, 1/n. Сразу видно, что среднее увеличилось.

[ichthuss]

Да, туплю.

[brevi.livejournal.com]

Если вам нравится использовать линейную алгебру — вот вам ещё идея: по теореме Гамильтона-Кэли, характеристический многочлен квадратной матрицы A, примененный к ней самой, обращается в ноль. Перенеся высшую степень матрицы в этом многочлене в одну сторону, а все остальные члены в другую, получаем выражение вида A^n = (Tr A) A^(n-1) + … - (-1)^n (det A) I, которое можно рассматривать как формулу рекурсии: n-ная степень матрицы, A^n, есть линейная комбинация, с явно заданными коэффициентами, предыдущих степеней матрицы A^0=I, A^1=A, …, и так далее до A^(n-1) включительно. Используя эту формулу рекурсивно, можно разложить любую степень матрицы А^N с N >= n как линейную комбинацию первых n степеней I, A, …, A^(n-1), с коэффициентами, зависящими от N. Проверьте, что получается с матрицей рекурсии «скользящего среднего» при таком подходе.

[clovis3.livejournal.com]

Спасибо! Я не осознавал, что теорема Гамильтона-Кэли означает рекурсивное соотношение между степенями матрицы с коэффициентами из характеристического многочлена. Применительно к данной задаче этот факт соответствует тому, что в матрице вышеописанного вида (всюду нули, кроме единиц на первой "над-диагонали" и произвольных чисел в нижней строке) числа из нижней строки -- это, с одной стороны, коэффициенты рекурсии, а с другой, как известно любителям данной формы регулярной матрицы, они же суть коэффициенты характеристического многочлена. Поскольку я в данный момент очень люблю некоторое обобщение понятия регурлярных матриц, то непременно приму всё это во внимание.

[brevi.livejournal.com]

Ага. Например, для матрицы 2x2, применяя формулу из теоремы Гамильтона-Кэли рекурсивно для А^n при всех возможных n и не пользуясь ничем другим, можно посчитать явное выражение для экспоненты от матрицы exp(A). Очень полезно.

[rezoner.livejournal.com]

Это всё совершенно потрясающе. Я думать не думал, что в такой простенькой на вид задаче кроются такие бездны. Спасибо вам и остальным участникам!

[ichthuss]

Это стандартный подход для цифровых линейных фильтров. Выполним частотное разложение исходного сигнала (7 начальных значений). Если мы покажем, что любая исходная частота, кроме 0 Гц, в отфильтрованном сигнале затухает, то этим мы докажем, что при любых исходных значениях результат экспоненциально сойдется к одному значению.

В комплексном виде каждая частотная компонента имеет вид e^iωn, где ω принадлежит [0, 0.5). Если обозначить z=e^iω, то воздействие любого линейного фильтра будет сводиться к умножению на функцию от z.

Для рекурсивных фильтров эта функция будет дробно-рациональной, в частности, для таких фильтров, как в условии — в числителе будет 1, в знаменателе — полином от z степени N, где N — глубина рекурсии, причем коэффициентами этого полинома буду коэффициенты из рекурсивного выражения.

Для того, чтобы сигнал после этого фильтра сходился к нулю, необходимо, чтобы все корни полинома были по модулю меньше 1 (это эквивалентно требованию, чтобы все частотные компоненты на выходе затухали). Чтобы конечный сигнал на выходе сходился к постоянному значению, нужно, чтобы все корни, кроме z=1, были по модулю меньше 1 (это эквивалентно требованию, чтобы затухали все частоты, кроме 0).

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

[old-radist.livejournal.com]

А вычисляемые средние тоже округляются до целых?

[jak40.livejournal.com]

И если да, то как в случае "Х с половиной"?

[rezoner.livejournal.com]

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

[d-white1967.livejournal.com]

А ты хитрый, эк какую задачу задал. Но всё проще, всё проще...

Смок подошел к столу.
- Прошу внимания, джентльмены! У меня не совсем обыкновенная система.
Вряд ли это можно назвать системой. Но у нее то преимущество, что она дает
практические результаты. У меня, собственно, есть свои догадки, однако я
не стану о них сейчас распространяться. Следите за мной. Крупье,
приготовьте шарик. Я хочу выиграть на номер двадцать шесть. Допустим, я
ставлю на него. Пускайте шарик, крупье!
Шарик забегал по кругу.
- Заметьте, - сказал Смок, - что номер девять был как раз напротив!
Шарик остановился как раз напротив двадцати шести.
Большой Бэрк выругался. Все ждали.
- Для того, чтобы выиграть на ноль, нужно, чтобы напротив стояло
одиннадцать. Попробуйте сами, если не верите.
- Но где же система? - нетерпеливо спросил Моран. - Мы знаем, что вы
умеете выбирать выигрышные номера. Но как вы их узнали?
- Я внимательно следил за выигрышами. Случайно я дважды отметил, где
остановился шарик, когда вначале против него был номер девять. Оба раза
выиграл двадцать шестой. Тогда я стал изучать и другие случаи. Если
напротив находится двойной ноль - выигрывает тридцать второй. А для того
чтобы выиграть на двойной ноль, необходимо, чтобы напротив было
одиннадцать. Это случается не всегда, но обычно. Как я уже сказал, у меня
есть свои догадки, о которых я предпочитаю не распространяться.
Большой Бэрк, пораженный какой-то мыслью, внезапно вскочил, остановил
рулетку и стал внимательно осматривать колесо. Все девять остальных
владельцев рулеток тоже склонили головы над колесом. Затем Большой Бэрк
выпрямился и посмотрел на печку.
- Черт возьми! - сказал он. - Никакой системы не было. Стол стоит
слишком близко к огню, и проклятое колесо рассохлось, покоробилось. Мы
остались в дураках. Не удивительно, что он играл только за этим столом. За
другим столом он не выиграл бы и кислого яблока.