Курсовая работа на тему «Рекуррентные последовательности»

ВВЕДЕНИЕ
1 Рекуррентные последовательности: определения и теоремы
1.1 Понятие и примеры рекуррентной последовательности
1.2 Решение линейного однородного рекуррентного уравнения
1.3 Решение линейного неоднородного рекуррентного уравнения
2 Практическая часть: решение задач
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

ВВЕДЕНИЕ

 

Одним из основных понятий математики является понятие последовательности элементов  заданного множества А. Последовательность можно считать заданной на А, если указан закон, по которому каждому натуральному числу n сопоставляется элемент u_n множества А. Того или иного рода последовательности встречаются в различных разделах математики и с их помощью описываются многие свойства изучаемых объектов, потому исследуемая тема остается высокоактуальной. Например, в терминах сходящихся последовательностей точек какого-либо топологического пространства удобно описывать существование предела отображения, его непрерывность.

Последовательность Фибоначчи, о которой в том числе будет идти речь в работе, возникшая в средневековье, оказалась пригодной в качестве системы счисления, которая более помехоустойчива, чем двоичная система, в компьютерных приложениях [3].

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

Объект исследования – рекуррентные последовательности.

Предмет исследования – методика проведения исследования рекуррентных последовательностей.

Целью работы описать основные методы решения рекуррентных уравнений с постоянными коэффициентами.

Для достижения цели работы необходимо решить следующие задачи:

• определить понятие и привести примеры рекуррентных последовательностей;
• рассмотреть методику решения линейного однородного рекуррентного уравнения;
• привести алгоритм решения неоднородного рекуррентного уравнения;
• рассмотреть примеры заданий, содержащих рекуррентные последовательности, уравнения и др.

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

 

1 Рекуррентные последовательности: определения и теоремы

1.1 Понятие и примеры рекуррентной последовательности

 

Рекуррентная последовательность: пусть известно k чисел a₁, …, а_k. Эти числа являются первыми числами числовой последовательности. Следующие элементы данной последовательности вычисляются так [10]:

Здесь F— функция от k аргументов.

Рекуррентным соотношением (уравнением, рекуррентной формулой) называется соотношение вида [8]

,

которое позволяет вычислить все члены последовательности a₀,a_1,a₂,.., если заданы её первые k членов.

k – порядок рекуррентного уравнения.

Примеры.

1) a_n+1 = a_n + d — арифметическая прогрессия.

2) a_n+1 = q ∙ a_n — геометрическая прогрессия.

3) a_n+2 = a_n + a_n+1 — последовательность чисел Фибоначчи.

Последняя числовая последовательность известна в математике под названием чисел Фибоначчи [1]:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

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

А теперь рассмотрим ситуацию с другой стороны. Будем обозначать буквами V, V^/ и V^// соответственно последовательности

v_1, v₂ , v₃ , …

v₁^/ , v₂^/ , v₃^/ , …

v₁^// , v₂^// , v₃^// , …

Есть две простые леммы:

1) Если V есть решение уравнения (1), и с — произвольное число, то последовательность c V есть также решение данного уравнения.

2) Если последовательности V и V» являются решениями уравнения (1), то и их сумма также является решением данного уравнения.

Пусть теперь V^/ и V^// два непропорциональных решения уравнения (1), т. е. такие, что при любом постоянном С найдётся такой номер n, что

Покажем, что всякую последовательность V можно представить в виде:

C₁V^/ + C₂V^// (2), где C₁ и C₂ — некоторые постоянные.

Т. к. последовательности V^/ и V^// непропорциональны, то непропорциональны и её соответствующие члены (это утверждение можно доказать методом от противного, применив индукцию).

Теперь найдём последовательность V, она будет определена, если заданы её два начальных члена.

Чтобы V = C₁V^/ + C₂V^// , найдём такие с₁ и с₂, чтобы имела место система:

c₁v₁^/ +c₂v₁^// = v₁,

c₁v₂^/ + c₂v₂^// = v₂.

Тогда на основании двух лемм, указанных ранее, C₁V^/ + C₂V^// даст нам последовательность V.

В силу непропорциональности последовательностей, эта система будет разрешима относительно c₁ и c₂, каковы бы ни были при этом числа v_{1 ,} v₂.

 

Знаменатель этих дробей не может быть равен нулю. а подставив полученные значения в C₁V^/ + C₂V^// мы и получим требуемое представление последовательности V. Для получения всех решений уравнения V = C₁V^/ + C₂V^// , нам достаточно найти два его какие-нибудь непропорциональные решения. Будем искать эти решения среди геометрических прогрессий. В соответствии с леммой №1, мы имеем право выбрать только такие прогрессии, первый член которых равен 1.

Итак, возьмём прогрессию: 1; q ; q² ; …

Чтобы она являлась решением уравнения V = C₁V^/ + C₂V^// , необходимо. чтобы для любого n выполнялось q^{n — 2} + q^{n — 1} = qⁿ или 1 + q = q² .

Корни этого квадратного уравнения  и .

с₁ + с₂ = 1 и

с₁ + с₂  =1

Решив эту систему, получим:

с₁ = , с₂ =  ,

откуда V =  .

Эта формула называется формулой Бине (по имени получившего её математика). Полученная формула и есть аналитическое задание последовательности Фибоначчи F(n) [15].

Введение представления о рекуррентных последовательностях позволяет по-новому взглянуть на некоторые уже известные нам задачи. Например, факториал целого числа n! можно рассматривать как значение n-го элемента следующего ряда чисел [13]:

Рекуррентное описание такой последовательности выглядит следующим образом:

 

1.2 Решение линейного однородного рекуррентного уравнения

 

В случае, когда рекуррентное уравнение линейно и однородно, то есть выполняется соотношение вида [6]

Последовательность a₀, a_1, a₂,.., удовлетворяющая данному уравнению называется возвратной.

называется характеристическим многочленом для возвратной последовательности .

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

Общее решение однородного линейного рекуррентного уравнения имеет аналогию с решением линейного дифференциального уравнения. А именно, справедливы теоремы.

Теорема 1.

Пусть  — корень характеристического многочлена (2), тогда последовательность , где c – производная константа, удовлетворяет уравнению (1).

Теорема 2.

Если  — простые корни характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид:

где c₁,c₂,..,c_k – произвольные константы.

Теорема 3.

Если  — корень кратности  (i = 1,2,..,s) характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид:

где c_ij – произвольные константы.

Зная общее решение рекуррентного уравнения (1), по начальным условиям a₀, a₁,.., a_k-1, можно найти неопределенные постоянные c_ij, и тем самым получить частное уравнении (1) с данными условиями.

 

1.3 Решение линейного неоднородного рекуррентного уравнения

 

Рассмотрим линейное неоднородное рекуррентное уравнение [6]

a_n+k + p₁a_n+k-1 + … + p_ka_n = f(n), (n = 0, 1, 2,…)         (3)

Пусть {b_n} – общее решение однородного уравнения (1).

{c_n} – частное (конкретное) решение неоднородного уравнения (3).

Тогда последовательность {b_n + c_n} образует общее решение уравнения (3). Таким образом, справедлива теорема.

Теорема 4.

Общее решение линейного неоднородного рекуррентного уравнения представляется в виде суммы общего решения соответствующего линейного однородного рекуррентного уравнения и некоторого частного решении неоднородного уравнения.

В результате, задача нахождения общего  решения неоднородного уравнения (3) сводится к нахождению его частного решения. В отдельных случаях имеются рецепты нахождении частного решения.

1) Если f(n) = βⁿ,  (где β не является корнем характеристического уравнения), то частное решение следует искать в виде c_n = Cβⁿ . Тогда, подставляя его в (3), получаем:

Отсюда

В результате, частное решение задаётся формулой

2) Пусть f(n)–многочлен степени r от переменной n, и число 1 не является характеристическим корнем. Тогда  и частное решение следует искать в виде

Подставляя c_n  в (3) вместо a_n, получаем

Сравнивая коэффициенты левой и правой частей полученного равенства, найдём соотношения для чисел d_i, позволяющие эти числа определить.

 

2 Практическая часть: решение задач

 

Пример 1.

Найти последовательность {a_n}, удовлетворяющую рекуррентному уравнению

Решение.

Характеристический многочлен

Пример 2.

Для заданного вещественного х и малой величины ε (например, ε = 0,000001) вычислить сумму ряда

 

включив в нее только слагаемые, превышающие ε.

Решение.

Известно, что сумма такого бесконечного ряда имеет конечное значение, равное е^x, где е = 2,71828… — основание натурального логарифма. Поскольку элементы этого ряда представляют собой убывающую последовательность чисел, стремящуюся к нулю, то суммирование нужно производить до первого слагаемого, по абсолютной величине не превышающего ε.

Если слагаемые в этом выражении обозначить следующим образом:

то обобщенная формула для i-го элемента будет следующей:

Нетрудно увидеть, что между элементами данной последовательности имеется рекуррентная зависимость. Ее можно найти интуитивно, но можно и вывести формально. Правда, для этого нужно догадаться, что рекурсия — одношаговая, и что каждый следующий элемент получается путем умножения предыдущего на некоторый множитель, т.е.

Используя обобщенную формулу, имеем:

Отсюда:

Действительно:

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

Пример 3.

Для заданного натурального N и вещественного х (х > 0) вычислить значение выражения:

Решение.

В этом примере не очевидно то, что представленное выражение рекуррентно. Попробуем найти ее методом индукции. Будем считать, что искомое выражение есть n-й элемент последовательности следующего вида:

Отсюда видна связь:

Ответ:

Пример 4.

Построить линейное однородное разностное уравнение (минимально возможного порядка) с постоянными действительными коэффициентами, частными решениями которого являются функции

Решение.

Так как характеристическое уравнение имеет действительные коэффициенты, его корни  действительные или комплексно-сопряженные.

Функция  показывает, что -3 является корнем

Функции  показывает, что 5 является корнем кратности не менее 2

Функция

-показывает, что комплексно-сопряженные числа

являются корнями характеристического уравнения.

Значит, в характеристическое уравнение входят сомножители

По характеристическому уравнению строим линейное однородное разностное уравнение

Ответ:

Пример 5.

Предположим, что  — национальный доход в момент времени . Потребление  запаздывает относительно  в соответствии с законом . Предприниматель  осуществляет инвестиции в том случае, если приращение национального дохода устойчиво, т.е. . Равновесное состояние достигается при условии:

Найти функцию национального дохода в условиях равновесия в момент времени .

Решение.

В уравнение

подставим  вместо

Сложим с данным уравнением

Найдем одно частное решение полученного неоднородного уравнения в виде

и обозначим для краткости

Подставим в уравнение

Так как функции  и  линейно независимы, для выполнения тождества по  нужно, чтобы коэффициенты при них в левой и правой части должны быть равны. При :

Заменяем  и  с точностью 4 знака, получаем линейную систему:

Решаем систему по правилу Крамера:

Значит, функция  является решением неоднородного уравнения.

К ней надо прибавить общее решение однородного уравнения

Его характеристическое уравнение

Корень  имеет кратность 2, общее решение

Общее решение неоднородного уравнения можно записать как сумму найденного частного решения неоднородного уравнения и общего решения однородного уравнения:

где константы .

Ответ:

Пример 6. В ходе лечебного голодания масса пациента за 30 дней снизилась с 96 до 70 кг. Было установлено, что ежедневные потери массы пропорциональны массе тела. Вычислить, чему была равна масса пациента через k дней после начала голодания для k = 1, 2, …, 29.

Решение.

Обозначим массу пациента в i-й день через р_i (i = 0, 1, 2, …, 30). Из условия задачи известно, что р₀ = 96 кг, p₃₀ = 70 кг.

Пусть К – коэффициент пропорциональности убывания массы за один день. Тогда

Получаем последовательность, описываемую следующей рекуррентной формулой:

Однако нам неизвестен коэффициент К, его можно найти, если используем условие p₃₀ = 70.

Для этого будем делать обратные подстановки:

Пример 7.

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

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

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

Решение.

Находим из уравнений модели:

Получаем в ответе вектор валового выпуска

Ответ:

Пример 8.

Решите однородное рекуррентное уравнение с начальными условиями

Решение.

Это однородное уравнение порядка 3.

Составим характеристическое уравнение

Один его корень t=-1 подбирается сразу: -1=2-7+4

Делим многочлен  на (t+1)

Многочлен  опять имеет корень -1, тогда по теореме Виета другой его корень равен 4.

Корень -1 имеет кратность 2, корень 4 – кратность 1.

Поэтому общее решение рекуррентного уравнения имеет вид

Коэффициенты А, В, С найдем из начальных условий

A=-1, C=2, B=0

Ответ:

Пример 9.

Решите неоднородное рекуррентное уравнение с начальным условием

Решение.

Для всех n = 0, 1, 2, . . . положим x_n = y_n + γ, где пока неизвестная постоянная γ.

Подставим эти выражения в исходное уравнение:

Уравнение станет однородным для

Это геометрическая прогрессия

Ответ:

Пример 10.

Найти решение рекуррентного уравнения

с начальным условием  .

Решение.

Рассмотрим характеристический многочлен данного рекуррентного уравнения

Его корень . Тогда по теореме 1 общее решение соответствующего однородного рекуррентного уравнения
задаётся формулой , где  – произвольная константа.

Так как  , т.е. единица не является корнем характеристического многочлена, а правая часть  есть многочлен первой степени, то частное решение неоднородного уравнения ищется в виде полинома первой степени с неопределёнными коэффициентами , где  и  – неизвестные коэффициенты. Подставив  вместо  в исходное уравнение, получим  или . Приравнивая коэффициенты левой и правой части последнего равенства, получаем систему уравнений для определения неизвестных  и :

Отсюда, находим:  и . Таким образом, частное решение исходного уравнения имеет вид . По теореме 4 получаем общее решение неоднородного рекуррентного уравнения . Из начального условия . В результате, окончательно имеем: .

Ответ:

ЗАКЛЮЧЕНИЕ

 

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

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

Все поставленные перед началом исследования цели были достигнуты:

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

Тема рекуррентные последовательности не является изолированной, Она близка к школьному курсу математики (арифметическая и геометрическая прогрессии, последовательности квадратов и кубов натуральных чисел и т.д.), используется в высшей алгебре, геометрии, математическом анализе и других математических дисциплинах. Теория возвратных последовательностей составляет особую главу математической дисциплины, называемой исчислением конечных разностей; представляет собой частную главу о последовательностях.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

1. Воробьев Н. Н. Числа Фибоначчи. 4-е издание. — М.: Наука, 1978.
2. Галушкина Ю. И. , Марьямов А. Н.: Конспект лекций по дискретной математике — 2-е изд., испр. — М.: Айрис-пресс, 2008.
3. Глухов М. М. ,Елизаров В. П., Нечаев А. А. Глава XXV. Линейные рекуррентные последовательности // Алгебра. — Учебник. В 2-x томах. — М.: Гелиос АРВ, 2003. — Т. 2.
4. Грехем, Р. Конкретная математика. Основание информатики. / Р. Грехем, Д. Кнут, О. Паташник. Пер. с англ. – М.: Мир, 1998. – С. 17−37.
5. Лидл Р., Нидеррайтер Г. Конечные поля. Т 2. – М.: Мир, 1988, – 822 с.
6. Султанов А. Я. Дополнительные вопросы алгебры. Рекуррентные последовательности: Учебно-методическое пособие. – Пенза, 2011. – 48 с.
7. Маркушевич А. И. Возвратные последовательности. — М.: Наука, 1975. 47 с.
8. Математическая энциклопедия. Т 4. — М.: Советская энциклопедия, 1984. — С. 506 — 507.
9. Моденов П. С. Сборник задач по специальному курсу элементарной математики. – М.: Высшая школа, 1960. С. 120 – 128.
10. Монахова О. А., Осьминина Н. А. Рекуррентные последовательности. Алгебра формальных рядов: Методические рекомендации для студентов специальностей «математика-физика», «математика-информатика». – Пенза, 2007. – 32 с.
11. Олейник В. Л. Рекуррентные соотношения и разностные уравнения// Соросовский образовательный журнал. Т 7, № 3, 2001, с. 114-120.
12. Стахов А. П. Алгоритмическая теория измерения. – М.: Знание, 1979.
13. Шклярский Д. О., Ченцев Н. Н., Яглом И. Н. Избранные задачи и теорем элементарной математики (арифметика и алгебра). – М.: Наука, 1976.
14. Яглом И. М. Итальянский купец Леонардо Фибоначчи и его кролики // Квант. – 1971. – №11. – с.31.