Задачка, простенькая, но лень сейчас, в полпервого ночи, решать
Некто записывает в каждый из 7 дней число, целое и положительное, в таблицу.
На 8-день он записывает в таблицу среднее из предыдущих 7.
На девятый день - среднее из предыдущих семи, т.е. дней 2-8 ("скользящее среднее").
Так он продолжает. Надо доказать, что последовательность значений для N-ного дня сходится.
На 8-день он записывает в таблицу среднее из предыдущих 7.
На девятый день - среднее из предыдущих семи, т.е. дней 2-8 ("скользящее среднее").
Так он продолжает. Надо доказать, что последовательность значений для N-ного дня сходится.
Comments 19
Доказательство «в лоб» такое: для любых начальных значений в первые 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, и получим противоречие.
Reply
Reply
Давайте так: правило «скользящего среднего» - всего лишь частный случай линейной рекурсии глубины N (в вашем примере N=7), когда любое число x_n, стоящее на n-ном месте в генерируемой последовательности, где n>N, получается как линейная комбинация предыдущих N членов с фиксированными коэффициентами. Попробуем найти такое число z, что последовательность x_n = z^n удовлетворяет условию рекурсии: подставим в формулу рекурсии и получим уравнение для z в виде многочлена. Таким образом, для любого корня z этого многочлена последовательность z^n удовлетворяет условию рекурсии (но не начальным условиям)
Reply
Условие рекурсии линейно, поэтому любая линейная комбинация выполняющих его последовательностей тоже его выполняет. Чтобы удовлетворить N начальных условий, нужно иметь N (независимых) последовательностей. Если у многочлена все корни z_i различны, то это будут N последовательностей z_i^n. (Если есть кратные корни, то нужно делать дополнительные телодвижения, но в нашем частном случае «скользящего среднего» у нас все в порядке и без этого). Отсюда формула.
Reply
Reply
И если да, то как в случае "Х с половиной"?
Reply
Reply
Смок подошел к столу ( ... )
Reply
Leave a comment