Рекуррентные соотношения математика конспект
Обновлено: 05.07.2024
В школьном курсе математики знакомство с рекуррентными соотношениями происходит на примерах арифметической и геометрической прогрессий. Рассмотрение рекуррентных соотношений другого вида (например, числа Фибоначчи) часто входят в программы факультативов, а их решения, как правило, получают методом математической индукции, что требует определенного навыка в построении правильного индуктивного предположения. В настоящей заметке предложен подход к решению этих задач на основе построения формальных степенных рядов.
Вложение | Размер |
---|---|
Арифметика последовательностей и рекуррентные соотношения | 245.5 КБ |
Предварительный просмотр:
В школьном курсе математики знакомство с рекуррентными соотношениями происходит на примерах арифметической и геометрической прогрессий. Рассмотрение рекуррентных соотношений другого вида (например, числа Фибоначчи) часто входят в программы факультативов, а их решения, как правило, получают методом математической индукции, что требует определенного навыка в построении правильного индуктивного предположения. В настоящей заметке предложен подход к решению этих задач на основе построения формальных степенных рядов. Этот подход широко применяется во многих разделах математики, а применительно к рекуррентным соотношениям позволяет заменить рекуррентное соотношение уравнением в формальных степенных рядах. В частности, рекуррентные соотношения с постоянными коэффициентами приводят к линейному уравнению в формальных степенных рядах, которое решается стандартным образом с учетом специфики арифметики формальных степенных рядов.
- Пусть - последовательность элементов множества A (A = Z, Q, R, C ). Будем записывать последовательность в виде
где t – формальная переменная. Такая форма записи последовательности называется формальным степенным рядом . Конечную последовательность будем рассматривать как бесконечную последовательность, в которой . Слагаемые вида часто будем опускать и записывать конечную последовательность в виде . Множество формальных степенных рядов с коэффициентами из будем обозначать . Если , то коэффициент называется свободным членом формального степенного ряда и будем обозначать .
- Для учеников 1-11 классов и дошкольников
- Бесплатные сертификаты учителям и участникам
В школьном курсе математики знакомство с рекуррентными соотношениями происходит на примерах арифметической и геометрической прогрессий. Рассмотрение рекуррентных соотношений другого вида (например, числа Фибоначчи) часто входят в программы факультативов, а их решения, как правило, получают методом математической индукции, что требует определенного навыка в построении правильного индуктивного предположения. В настоящей заметке предложен подход к решению этих задач на основе построения арифметических последовательностей (формальные степенные ряды). Этот подход широко применяется во многих разделах математики, а применительно к рекуррентным соотношениям позволяет заменить рекуррентное соотношение уравнением в формальных степенных рядах. В частности, рекуррентные соотношения с постоянными коэффициентами приводят к линейному уравнению в формальных степенных рядах, которое решается стандартным образом с учетом специфики арифметики формальных степенных рядов.
- Пусть - последовательность элементов множества A ( A = Z ,Q ,R ,C ). Будем записывать последовательность в виде
где t – формальная переменная. Такая форма записи последовательности называется формальным степенным рядом. Конечную последовательность будем рассматривать как бесконечную последовательность, в которой . Слагаемые вида часто будем опускать и записывать конечную последовательность в виде . Множество формальных степенных рядов с коэффициентами из будем обозначать . Если , то коэффициент называется свободным членом формального степенного ряда и будем обозначать .
В этой главе мы обсудим, как рекурсивные методы могут выводить последовательности и использоваться для решения задач подсчета. Процедура поиска членов последовательности рекурсивным способом называется рекуррентным отношением . Мы изучаем теорию линейных рекуррентных соотношений и их решения. Наконец, мы вводим производящие функции для решения рекуррентных отношений.
Определение
Рекуррентное отношение — это уравнение, которое рекурсивно определяет последовательность, в которой следующий член является функцией предыдущих членов (выражая F n как некоторую комбинацию F i с i n ).
Пример — ряд Фибоначчи — F n = F n − 1 + F n − 2 , Ханойская башня — F n = 2 F n − 1 + 1
Линейные рекуррентные отношения
Линейное рекуррентное уравнение степени k или порядка k — это рекуррентное уравнение в формате x n = A 1 x n − 1 + A 2 x n − 1 + A 3 x n − 1 + d o t s A k x n k ( A n — константа, а A k n e q 0 ) на последовательности чисел как полинома первой степени.
Вот некоторые примеры линейных рекуррентных уравнений —
Рецидив отношений | Начальные значения | Решения |
---|---|---|
F n = F n-1 + F n-2 | a 1 = a 2 = 1 | Число Фибоначчи |
F n = F n-1 + F n-2 | а 1 = 1, а 2 = 3 | Номер Лукаса |
F n = F n-2 + F n-3 | a 1 = a 2 = a 3 = 1 | Падовская последовательность |
F n = 2F n-1 + F n-2 | a 1 = 0, a 2 = 1 | Число Пелла |
Как решить линейное рекуррентное соотношение
Предположим, что два упорядоченных линейных рекуррентных соотношения имеют вид — F n = A F n − 1 + B F n − 2 , где A и B — действительные числа.
Характеристическое уравнение для вышеуказанного рекуррентного соотношения —
x 2 − A x e − B = 0
Три случая могут возникнуть при поиске корней —
Случай 1 — Если это уравнение учитывается как ( x − x 1 ) ( x − x 1 ) = 0 и оно дает два различных реальных корня x 1 и x 2 , то F n = a x n 1 + b x n 2 является решение. [Здесь a и b являются константами]
Случай 2 — Если это уравнение вычисляется как ( x − x 1 ) 2 = 0 , и оно порождает один действительный корень x 1 , то решением является F n = a x n 1 + b n x n 1 .
Случай 3 — Если уравнение дает два различных комплексных корня, x 1 и x 2 в полярной форме x 1 = r a n g l e t h e t a и x 2 = r a n g l e ( − t h e t a ) , то F n = r n ( a c o s ( n t h e t a ) + b s i n ( n t h e t a ) ) является решением.
Решите рекуррентное соотношение F n = 5 F n − 1 − 6 F n − 2 , где F 0 = 1 и F 1 = 4 .
Характеристическое уравнение рекуррентного соотношения —
Итак, ( x − 3 ) ( x − 2 ) = 0
x 1 = 3 и x 2 = 2
Корни реальны и различны. Итак, это в форме дела 1
F n = a x n 1 + b x n 2
Здесь F n = a 3 n + b 2 n ( A s x 1 = 3 a n d x 2 = 2 )
1 = F 0 = a 3 0 + b 2 0 = a + b
4 = F 1 = a 3 1 + b 2 1 = 3 a + 2 b
Решая эти два уравнения, мы получаем a = 2 и b = − 1
Следовательно, окончательное решение —
$$ F_n = 2,3 ^ n + (-1). 2 ^ n = 2,3 ^ n — 2 ^ n $$
Решите рекуррентное соотношение — F n = 10 F n − 1 − 25 F n − 2 , где F 0 = 3 и F 1 = 17 .
Характеристическое уравнение рекуррентного соотношения —
x 2 − 10 x − 25 = 0
Итак, ( x − 5 ) 2 = 0
Следовательно, существует один действительный корень x 1 = 5
Поскольку существует единый действительный корень, он имеет вид случая 2
F n = a x n 1 + b n x n 1
3 = F 0 = a .5 0 + b .0 .5 0 = a
17 = F 1 = a .5 1 + b .1 .5 1 = 5 a + 5 b
Решая эти два уравнения, мы получаем a = 3 и b = 2 / 5
Следовательно, окончательное решение — F n = 3.5 n + ( 2 / 5 ) . n .2 n
Решите рекуррентное соотношение F n = 2 F n − 1 − 2 F n − 2 , где F 0 = 1 и F 1 = 3
Тип урока: комбинированный
- компьютерный класс, соединённый локальной сетью
- компьютер учителя оборудован мультимедийным проектором
Подготовительный этап.
План урока:
- Блок-схемы
- Работа над головоломкой
- Нахождение ошибок в записи
- Определение результата выполнения алгоритма
4. Ввод понятия рекуррентных соотношений – 5 мин.
5. Выявление формул рекуррентных соотношений – 5 мин.
6. Работа с задачами по новой теме за компьютером – 10 мин.
7. Подведение итога урока – 5 мин.
1. Организационный момент
2. Фронтальная работа
По щелчку появляется слово с недостающими буквами и подсказка к нему.
– Какая из трёх представленных блок-схем соответствует циклической структуре?
– Как называются остальные?
– Сформулируйте известные русские пословицы по их блок-схемам.
- Прошёл Огонь, воду и медные трубы.
- Готовь сани летом, а телегу зимой.
- Семь раз отмерь – один раз отрежь.
3. Повторение
1. Алгоритм, в котором команды выполняются многократно, –
а) циклический
б) линейный
в) разветвлённый
г) с неполным ветвлением
2. Особенностью цикла с предусловием является то, что…
а) тело цикла может не выполниться ни разу
б) тело цикла выполняется хотя бы один раз
в) известно число повторений
г) цикл является бесконечным
3. Цикл с постусловием – это цикл,
а) в котором условие проверяется в начале тела цикла
б) в котором условие проверяется в конце тела цикла
в) с известным числом повторений
4. Особенностью цикла с параметром является то, что…
а) тело цикла может не выполниться ни разу
б) тело цикла выполняется хотя бы один раз
в) известно число повторений
г) цикл является бесконечным
5. В убывающем цикле с параметром счётчик изменяется на…
6. В цикле с предусловием счётчик изменяется…
а) на 1
б) на 2
в) на 3
г) по усмотрению программиста
7. Сколько раз будут выполнены операторы из тела цикла в следующем фрагменте программы
8. Определить значение переменной s после выполнения следующего фрагмента программы:
s : = 0; i : = 5;
while i > 2 do i : =i - l; s : = s + i * i;
1. Операторами цикла являются
а) If… then… else
б) For… to… do
в) begin… end;
г) Repeat… until;
д) While… do
2. Цикл с параметром – это цикл,
а) в котором условие проверяется в начале тела цикла
б) в котором условие проверяется в конце тела цикла
в) с известным числом повторений
3. Особенностью цикла с постусловием является то, что…
а) тело цикла может не выполниться ни разу
б) тело цикла выполняется хотя бы один раз
в) известно число повторений
г) цикл является бесконечным
4. Цикл с предусловием – это цикл,
а) в котором условие проверяется в начале тела цикла
б) в котором условие проверяется в конце тела цикла
в) с известным числом повторений
5. В возрастающем цикле с параметром счётчик изменяется на…
6. В цикле с постусловием счётчик изменяется…
а) на 1
б) на 2
в) на 3
г) по усмотрению программиста
7. Сколько раз будут выполнены операторы из тела цикла в следующем фрагменте программы
8. Определить значение переменной s после выполнения следующего фрагмента программы:
На доске записывают формулы для нахождения n-го элемента
а1 = 6, а i = а i -1 + 3 21, 24, 27, 31
а1 = 1, а i = а i -1 + 1 28, 36, 45, 55
5. Переход за компьютеры для работы над задачами со слайда 13 (составить программу для нахождения n-го элемента задачи № 1)
6. Беседа по итогам урока
7. Домашнее задание: составить блок-схемы к задачам 2) и 3)
Читайте также: