Рішення рекурентних співвідношень. Рекурентні методи Розміщення без повторень

Анотація: Розміщення без повторень. Перестановки. Поєднання. Рекурентні співвідношення. Інший спосіб підтвердження. Процес послідовного розбиття. Завдання: "Утруднення мажордома".

Розміщення без повторень

Є різні предмети. Скільки з них можна скласти розстановок? При цьому дві розстановки вважаються різними, якщо вони або відрізняються один від одного хоча б одним елементом, або складаються з тих самих елементів, але розташованих в різному порядку. Такі розстановки називають розміщення без повторень, які число позначають . При складанні -розміщень без повторень із предметів нам треба зробити вибори. На першому кроці можна вибрати будь-який із наявних предметів. Якщо цей вибір вже зроблено, то на другому кроці доводиться вибирати з предметів, що залишилися. На - м кроку предметів. Тому за правилом твору отримуємо, що число -розміщень без повторення з предметів виражається так:

Перестановки

При складанні розміщень без повторень з елементів ми отримали розстановки, що відрізняються один від одного і складом, і порядком елементів. Але якщо брати розстановки, в які входять всі елементи, то вони можуть відрізнятися один від одного лише порядком елементів, що входять в них. Такі розстановки називають перестановками з n елементів, або, коротше, – перестановками.

Поєднання

У тих випадках, коли нас не цікавить порядок елементів у комбінації, а цікавить лише її склад, говорять про поєднання. Отже, поєднаннями з елементів називають всілякі розстановки, складені з цих елементів і відрізняються один від одного складом, але не порядком елементів. Число поєднань, яке можна скласти з елементів, позначають через .

Формула для числа поєднань виходить із формули для числа розміщень. Справді, складемо спочатку все - поєднання з елементів, а потім переставимо елементи, що входять у кожне поєднання, всіма можливими способами. При цьому виходить, що всі розміщення з елементів, причому кожне тільки по одному разу. Але з кожного - поєднання можна зробити! перестановок, а кількість цих поєднань дорівнює . Значить, справедлива формула

З цієї формули знаходимо, що

Рекурентні співвідношення

При вирішенні багатьох комбінаторних завдань користуються методом зведення даної задачі до завдання, що стосується меншої кількості предметів. Метод зведення до аналогічного завдання для меншого числа предметів називається методом рекурентних співвідношень(Від латинського "recurrere" - "повертатися").

Поняття рекурентних співвідношень проілюструємо класичною проблемою, яка була поставлена ​​близько 1202 Леонардо з Пізи, відомим як Фібоначчі. Важливість чисел Фібоначчі для аналізу комбінаторних алгоритмів робить цей приклад дуже сприятливим.

Фібоначчі поставив завдання у формі розповіді про швидкість зростання популяції кроликів за таких припущень. Все починається з однієї пари кролів. Кожна пара стає фертильною через місяць, після чого кожна пара народжує нову пару кроликів щомісяця. Кролики ніколи не вмирають, і їхнє відтворення ніколи не припиняється.

Нехай - кількість пар кроликів у популяції після місяців, і нехай ця популяція складається з пар приплоду і "старих" пар, тобто . Отже, черговий місяць відбудуться такі события: . Стара популяція в-й момент збільшиться на кількість народжених на момент часу. . Кожна стара пара в момент часу виробляє пару приплоду в момент часу. Наступного місяця ця картина повторюється:

Поєднуючи ці рівності, отримаємо наступне рекурентне співвідношення:

Вибір початкових умов для послідовності чисел Фібоначчі не є важливим; Значна властивість цієї послідовності визначається рекурентним співвідношенням. Будемо припускати (іноді ).

Розглянемо це завдання трохи інакше.

Пара кроликів приносить раз на місяць приплід із двох кроленят (самки і самця), причому новонароджені кроленята через два місяці після народження вже приносять приплід. Скільки кроликів з'явиться за рік, якщо на початку року була одна пара кроликів?

З умови завдання випливає, що за місяць буде дві пари кроликів. Через два місяці приплід дасть лише перша пара кроликів, і вийде 3 пари. А ще через місяць приплід дадуть і вихідна пара кролів, і пара кролів, що з'явилася два місяці тому. Тому всього буде 5 пар кролів. Позначимо через кількість пар кроликів після місяців з початку року. Зрозуміло, що через місяці будуть ці пари і ще стільки новонароджених пар кроликів, скільки було в кінці місяця, тобто ще пар кроликів. Іншими словами, має місце рекурентне співвідношення

Оскільки, за умовою, і , то послідовно знаходимо

Зокрема, .

Числа називаються числами Фібоначчі. Вони мають цілу низку чудових властивостей. Тепер виведемо вираз цих чисел через . Для цього встановимо зв'язок між числами Фібоначчі та наступним комбінаторним завданням.

Знайти число послідовностей, що складаються з нулів та одиниць, у яких жодні дві одиниці не йдуть поспіль.

Щоб встановити цей зв'язок, візьмемо будь-яку таку послідовність і зіставимо їй пару кроликів за таким правилом: одиницям відповідають місяці появи на світ однієї з пар "предків" цієї пари (включаючи і вихідну), а нулями - всі інші місяці. Наприклад, послідовність 010010100010 встановлює таку "генеалогію": сама пара з'явилася наприкінці 11-го місяця, її батьки - наприкінці 7-го місяця, "дід" - наприкінці 5-го місяця та "прадід" - наприкінці другого місяця. Вихідна пара кролів тоді зашифровується послідовністю 000000000000.

Ясно, що при цьому в жодній послідовності не можуть стояти дві одиниці поспіль - пара, що тільки-но з'явилася, не може, за умовою, принести приплід через місяць. Крім того, при зазначеному правилі різним послідовностям відповідають різні пари кроликів, і назад дві різні пари кроликів завжди мають різну "генеалогію", так як, за умовою, кролиця дає приплід, що складається тільки з однієї пари кроликів.

Встановлений зв'язок показує, що число-послідовностей, що мають зазначену властивість, дорівнює .

Доведемо тепер, що

Де , якщо непарно, і , якщо парно. Іншими словами, - ціла частина числа (надалі будемо позначати цілу частину числа через ; таким чином, ).

Насправді - це число всіх - послідовностей з 0 і 1, в яких ніякі дві одиниці не стоять поруч. Число таких послідовностей, в які входить рівно одиниць і нулів, дорівнює . Бо при цьому має виконуватись

Транскрипт

1 МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ Костромської державний університетімені М. А. Некрасова Т. Н. Матицина ДИСКРЕТНА МАТЕМАТИКА

2 ББК я73-5 М348 Друкується за рішенням редакційно-видавничої ради КМУ ім. Н. А. Некрасова Рецензент А. В. Череднікова, кандидат фізико-математичних наук, доцент М348 Матицина Т. Н. Дискретна математика. Вирішення рекурентних співвідношень: практикум [Текст] / Т. Н. Матицина. Кострома: КДУ ім. Н. А. Некрасова, с. Практикум містить індивідуальні завдання для студентів та призначений для забезпечення самостійної роботи з освоєння першої частини курсу «Дискретна математика». Для студентів 2-3 курси фізико-математичного факультету, які навчаються за спеціальностями «Математика» з додатковою спеціальністю «Інформатика», «Інформатика» з додатковою спеціальністю «Математика». ББК я73-5 Т. Н. Матицина, 2010 КМУ ім. Н. А. Некрасова,

3 ЗМІСТ Вступ Методичні рекомендаціїза рішенням лінійних рекурентних співвідношень Основні поняття та визначення рекурентних (поворотних) послідовностей Алгоритми рішення ЛОРС і ЛРС самостійного рішенняЗавдання для вирішення ЛОРС та ЛРС Відповіді Висновок Бібліографічний список

4 ВСТУП Перша частина курсу «Дискретна математика», що вивчається студентами 2 3 курсів фізико-математичного факультету, які навчаються за спеціальностями «Інформатика» з додатковою спеціальністю «Математика» (IV семестр) та «Математика» з додатковою спеціальністю «Інформатика» (V , передбачає рішення рекурентних співвідношень В даний видання включені завдання на обчислення однорідних та неоднорідних лінійних рекурентних співвідношень. Приводом для написання практикуму стала та обставина, що студенти практично не мають навичок вирішення завдань з даного курсу. Однією із причин є відсутність доступного підручника чи збірника завдань. Завдання із запропонованого практикуму допоможуть кожному зі студентів (індивідуально) розібратися з основними методами та прийомами вирішення завдань. З метою легшого освоєння матеріалу на початку посібника розглянуто всі типи завдань, що пропонуються для самостійного вирішення. Наприкінці розміщено список рекомендованої літератури, яка допоможе глибше вивчити цей предмет. Тема «Рекурентні співвідношення» близька до шкільного курсу (арифметичні та геометричні прогресії, послідовність квадратів і кубів натуральних чисел тощо), тому не вимагає від студентів попереднього вивчення будь-яких інших дисциплін. Основи теорії рекурентних співвідношень (поворотних послідовностей) були розроблені та опубліковані в 20-х роках. XVIII ст. французьким математиком А. Муавром та одним із перших за часом членів Петербурзької Академії наук швейцарським математиком Д. Бернуллі. Розгорнуту теорію дав найбільший математик XVIII ст. 4

5 петербурзький академік Л. Ейлер. З пізніших робіт слід виділити виклад теорії зворотних послідовностей у курсах обчислення кінцевих різниць, читаних знаменитими російськими математиками академіками П. Л. Чебишевим та А. А. Марковим. Рекурентні співвідношення (від латинського слова recurrere повертатися) відіграють велику роль дискретної математики, будучи сутнісно у певному сенсі дискретним аналогом диференціальних рівнянь. Крім того, вони дозволяють зводити це завдання від параметрів до задачі від 1 параметрів, потім до завдання від 2 параметрів і т. д. Послідовно зменшуючи число параметрів, можна дійти до завдання, яке вже легко вирішити. Поняття рекурентного співвідношення (поворотної послідовності) є широким узагальненням поняття арифметичної чи геометричної прогресії. Як окремі випадки воно охоплює також послідовності квадратів або кубів натуральних чисел, послідовності цифр десяткового розкладання раціонального числа (і взагалі будь-які періодичні послідовності), послідовності коефіцієнтів приватного від поділу двох багаточленів, розташованих за зростаючими ступенями х, і т.д.

6 1. МЕТОДИЧНІ РЕКОМЕНДАЦІЇ З РІШЕННЯ ЛІНІЙНИХ РЕКУРРЕНТНИХ СПІВВІДНОШЕНЬ 1.1. Основні поняття та визначення рекурентних (поворотних) послідовностей Записуватимемо послідовності у вигляді a 1, a 2, a 3, a, (1) або, коротко, (a ). Якщо існує натуральне число k та числа α 1, α 2, α k (дійсні або уявні), такі, що, починаючи з деякого номера та для всіх наступних номерів, a +k = α 1 a +k 1 + α 2 a + k α k a, (k 1), (2) то послідовність (1) називається рекурентною (поворотною) послідовністю порядку k, а співвідношення (2) рекурентним (поворотним) рівнянням порядку k. Таким чином, рекурентна послідовність характеризується тим, що кожен її член (починаючи з деякого з них) виражається через те саме кількість k безпосередньо попередніх йому членів за формулою (2). Сама назва "рекурентна" (а також зворотна) вживається саме тому, що тут для обчислення наступного члена повертаються до попередніх членів. Наведемо кілька прикладів рекурентних послідовностей. Приклад 1. Геометрична прогресія. Нехай маємо геометричну прогресію: a 1 = α, a 2 = α q, a 3 = α q 2, a = α q 1, ; (3) для неї рівняння (2) набуває вигляду: a +1 = q a. (4) 6

7 Тут k = 1 та α 1 = q. Таким чином, геометрична прогресія є рекурентною послідовністю першого порядку. Приклад 2. Арифметична прогресія. В разі арифметичної прогресії a 1 = α, a 2 = α + d, a 3 = α + 2d, a = α + (1)d, маємо a +1 = a + d співвідношення, яке не має виду рівняння (2). Однак якщо ми розглянемо два співвідношення, написані для двох сусідніх значень: a +2 = a +1 + d і a +1 = a + d, то отримаємо їх шляхом почленного віднімання a +2 a +1 = a +1 a, або a +2 = 2a +1 a рівняння виду (2). Тут k = 2, α 1 = 2, α 2 = 1. Отже, арифметична прогресія є рекурентною послідовністю другого порядку. Приклад 3. Розглянемо старовинне завдання Фібоначчі 1 про кількість кроликів. У ній потрібно визначити кількість пар зрілих кроликів, що утворилися від однієї пари протягом року, якщо відомо, що кожна зріла пара кроликів щомісяця народжує нову пару, причому новонароджені досягають повної зрілості протягом місяця. У цьому завдання цікавий аж ніяк не результат, отримати який зовсім неважко, але послідовність, члени якої виражають загальну кількість зрілих пар кроликів у початковий момент (a 1) через місяць (a 2), через два місяці (a 3) і, взагалі, через місяців (a+1). Очевидно, що a 1 = 1. Через місяць додасться пара новонароджених, але кількість зрілих пар буде колишня: a 2 = 1. Через два місяці кроленята досягнуть зрілості і загальна кількість зрілих пар дорівнюватиме двом: a 3 = 2. Нехай ми вирахували вже кількість 1 Фібоначчі, або Леонардо Пізанський, італійський середньовічний математик (близько 1200 р.) залишив після себе книгу «Про абак», що містить великі арифметичні та алгебраїчні відомості, запозичені у народів Середньої Азії та візантійців та творчо ним переробка. 7

8 зрілих пар через 1 місяць a і через місяць a +1. Так як до цього часу раніше зрілих пар дадуть ще a пар приплоду, то через + 1 місяців загальна кількість зрілих пар буде: a +2 = a +1 + a. (6) Звідси a 4 = a 3 + a 2 = 3, a 5 = a 4 + a 3 = 5, a 6 = a 5 + a 4 = 8, a 7 = a 6 + a 5 = 13,. Ми отримали таким чином послідовність a 1 = 1, a 2 = 1, a 3 = 2, a 4 = 3, a 5 = 5, a 6 = 8, a 7 = 13, a 13 = 233, (7) у якій кожен наступний член дорівнює сумі двох попередніх. Послідовність ця називається послідовністю Фібоначчі, а члени її числами Фібоначчі. Рівняння (6) показує, що послідовність Фібоначчі є рекурентною послідовністю другого порядку. Приклад 4. Як такий приклад розглянемо послідовність квадратів натуральних чисел: a 1 = 1 2, a 2 = 2 2, a 3 = 3 2, a = 2,. (8) Тут a +1 = (+ 1) 2 = і, отже, a +1 = a (9) Збільшуючи на одиницю, отримаємо: a +2 = a (10) І, отже (віднімаючи почленно (9) з (10)), a +2 a +1 = a +1 a + 2, або a +2 = 2a +1 a + 2. (11) Збільшуючи у рівності (11) на одиницю, матимемо: a +3 = 2a +2 a; (12) звідки (віднімаючи почленно (11) з (12)) a +3 a +2 = 2a +2 3a +1 + a, 8

9 або a+3 = 3a +2 3a +1 + a. (13) Ми отримали рекурентне рівняння третього порядку. Отже, послідовність (8) є рекурентною послідовністю третього порядку. Приклад 5. Розглянемо послідовність кубів натуральних чисел: a 1 = 1 3, a 2 = 2 3, a 3 = 3 3, a = 3,. (14) Так само, як у прикладі 4, можна переконатися, що послідовність кубів натуральних чисел є рекурентна послідовність четвертого порядку. Члени її задовольняють рівняння a +4 = 4a +3 6a a +1 a. (15) У разі найпростіших рекурентних послідовностей, наприклад, арифметичної та геометричної прогресій, послідовності квадратів або кубів натуральних чисел, ми можемо знаходити будь-який член послідовності, не вдаючись до обчислення попередніх членів. У разі ж послідовності чисел Фібоначчі ми, на перший погляд, не маємо можливості для цього і, щоб обчислити тринадцяте число Фібоначчі a 13, знаходимо попередньо один за одним усі попередні члени (користуючись рівнянням a +2 = a +1 + a ( 6)): a 1 = 1, a 2 = 1, a 3 = 2, a 4 = 3, a 5 = 5, a 6 = 8, a 7 = 13, a 8 = 21, a 9 = 34, a 10 = 55, a 11 = 89, a 12 = 144, a 13 = 233. У ході детального дослідження структури членів рекурентної послідовності можна отримати формули, що дозволяють обчислити в загальному випадку будь-який член рекурентної послідовності, не вдаючись до обчислення попередніх членів. Інакше кажучи, наступне завдання у тому, щоб знайти формулу -го члена послідовності, залежить тільки від номера. 9

10 Рекурентне співвідношення у загальному випадку може бути записане у вигляді a + k = F(, a + k 1, a + k 2, a), де F функція від k + 1 змінної, а число k називають порядком співвідношення. Рішенням рекурентного співвідношення називається числова послідовність b 1, b 2, b 3, b, для якої виконується рівність: b + k = F(, b + k 1, b + k 2, b) при будь-якому = 0, 1, 2, . Взагалі кажучи, довільне рекурентне співвідношення має безліч рішень. Наприклад, якщо розглянути рекурентне співвідношення другого порядку a +2 = a +1 + a, то йому, крім послідовності Фібоначчі: 1, 1, 2, 3, 5, 8, 13, 21, 34,..., що характеризується тим, що тут a 1 = a 2 = 1, задовольняє ще безліч інших послідовностей, що виходять при різному виборі значень a 1 і a 2. Так, наприклад, при a 1 = 3 і a 2 = 1 отримуємо послідовність: 3, 1, 2 , 1, 3, 4, 7, 11, 18, 29,. Щоб однозначно визначити рішення рекурентного співвідношення, необхідно задати початкові умови (початкових умов має бути рівно стільки, який порядок рекурентного співвідношення). Вирішити рекурентне співвідношення означає знайти формулу -го члена послідовності. На жаль, немає загального методу вирішення довільних рекурентних співвідношень. Винятком є ​​клас про лінійних рекурентних співвідношень з постійними коефіцієнтами. Рекурентне співвідношення виду a + k = α 1 a + k 1 + α 2 a + k α k a, де і деякі числа, i = 1, 2, k, називається лінійним однорідним рекурентним співвідношенням (ЛОРС) з постійними коефіцієнтами порядку k. 10

11 Рекурентне співвідношення виду a + k = α 1 a + k 1 + α 2 a + k α k a + f(), де a i деякі числа, i = 1, 2, k, f() 0 функція від, називається лінійним рекурентним співвідношенням (ЛРС) з постійними коефіцієнтами порядку k Алгоритми рішення ЛРС і ЛРС Алгоритм рішення ЛРС. Маємо ЛОРС: a + k = a 1 a + k 1 + a 2 a + k a k a. 1 крок. Кожному ЛОРС порядку k відповідає рівняння алгебри ступеня k з тими ж коефіцієнтами, і воно називається характеристичним рівнянням ЛОРС. Складаємо характеристичне рівняння x k = α 1 x k 1 + α 2 x k α k x 0 і знаходимо його коріння xi, де i = 1, k. 2 крок. Якщо x i коріння кратності 1 (тобто всі різні між собою), то загальне рішенняЛОРС має вигляд: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) + + c k (x k) = c i x i Якщо x i коріння кратності r i, то загальне рішення ЛОРС має вигляд k a = i= 1 (c 1 2 ri 1 i1 + ci2 + ci cir) (наприклад, якщо корінь x кратності 2, то a = (c 1 + c 2) x). i x i k i = 1 3 крок. Коефіцієнти i знаходяться за допомогою початкових умов. 11

12 Алгоритм рішення ЛРС. Маємо ЛРС: a + k = a 1 a + k 1 + a 2 a + k a + f (). Функцію f() можна подати у вигляді R m () λ, де R m () багаточлен ступеня m від змінної. Справді, наприклад: f() = 10 3= (10 3)1 = R 1 () 1, або f() = = (2 + 3) 3 = R 2 () 3. Перепишемо ЛРС у вигляді a + k α 1 a +k 1 α 2 a +k 2 α k a = R m () λ. 1 крок. Виписуємо відповідний ЛОРС: a + k α 1 a + k 1 α 2 a + k 2 α k a = 0 і знаходимо його загальне рішення. Для цього складаємо характеристичне рівняння x k α 1 x k 1 α 2 x k 2 α k x 0 = 0 і знаходимо його коріння x i, де i = 1, k. Нехай, наприклад, x i різне коріння, тоді загальне рішення відповідного ЛОРС має вигляд: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) + c k (x k). 2 крок. Знаходимо a приватне рішення ЛРС: а) якщо λ не корінь характеристичного рівняння x k α 1 x k 1 α 2 x k 2 α k = 0, то a = Q m () λ, де Q m () багаточлен ступеня m від змінної; б) якщо λ корінь характеристичного рівняння x k α 1 x k 1 α 2 x k 2 α k = 0 кратності r, то a = r Q m () λ, де Q m () багаточлен ступеня m від змінної. Далі, підставляємо a у вихідне ЛРС і знаходимо коефіцієнти в многочлен Q m (). 12

13 3 крок. Знаходимо загальне рішення ЛРС, воно є сумою загального рішення відповідного ЛОРС a і ​​приватного рішення ЛРС a, тобто a = a + a. Коефіцієнти c i знаходяться за допомогою початкових умов Приклади рішення ЛОРС та ЛРС Користуючись наведеним алгоритмом знаходження рішення ЛОРС та ЛРС, розберемо декілька завдань. Завдання 1. Знайти рішення лінійного однорідного рекурентного співвідношення другого порядку: a +2 = 6 a +1 8 a, a 0 = 3, a 1 = Складаємо характеристичне рівняння x 2 = 6 x 8 x 0 і знаходимо його коріння. x 2 6x + 8 = 0; x 1 = 2, x 2 = 4 коріння різні, отже, їх кратність дорівнює Знаходимо загальне рішення ЛОРС: a = c 1 (x 1) + c 2 (x 2) = c c Оскільки задані початкові умови, то коефіцієнти c 1 і з 2 визначаються однозначно. a 0 = c c = c 1 + c 2 = 3; a 1 = c c = 2c 1 + 4c 2 = 4. Отримали систему: c1 + c2 = 3, 2c1 + 4c2 = 4. Вирішуючи її, знайдемо коефіцієнти: c 1 = 8, c 2 = 5. Таким чином, рішення ЛОРС має вид a = Завдання 2. Знайти рішення лінійного однорідного рекурентного співвідношення: 13

14 a +2 = 6 a +1 9 a, a 0 = 5, a 1 = Складаємо характеристичне рівняння x 2 = 6x 9 і знаходимо його коріння. x 2 6x + 9 = 0; (x3) 2 = 0; x 1 = x 2 = 3 два корені, при цьому x 1 і x 2 збіглися, отже, кратність кореня дорівнює Знаходимо загальне рішення ЛОРС: a = (c 1 + c 2) (x 1) = (c 1 + c 2) За допомогою початкових умов визначаємо коефіцієнти c1 та c2: a 0 = (c 1 + c 2 0) 3 0 = c 1 = 5; a 1 = (c 1 + c 2 1) 3 1 = (c 1 + c 2) 3 = 6. Отримали систему c1 = 5, c1 + c2 = 2. Вирішуючи її, знайдемо коефіцієнти c 1 = 5, c 2 = 3. Отже, рішення ЛОРС має вигляд: a = (5 3) 3. Зауваження. Як відомо, корінням квадратного рівняння можуть бути раціональні, ірраціональні, комплексні числа і т. п. Метод вирішення лінійних рекурентних співвідношень з таким корінням вирішується аналогічно. Завдання 3. Знайти рішення лінійного однорідного рекурентного співвідношення третього порядку: a +3 = 3 a a +1 8 a, a 0 = 9, a 1 = 9, a 2 = Складаємо характеристичне рівняння x 3 = 3 x x 8 і знаходимо його коріння. x 3 3x 2 6x + 8 = 0; (x 1) (x + 2) (x 4) = 0; x 1 = 1, x 2 = 2, x 3 = 4 коріння різні, отже, їх кратність дорівнює Знаходимо загальне рішення ЛОРС: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) = c c 2 (2) + c

15 3. За допомогою початкових умов знаходимо коефіцієнти c 1 , c 2 і c 3. a 0 = c c 2 (2) 0 + c = c 1 + c 2 + c 3 = 9; a 1 = c c 2 (2) 1 + c = c 1 2c 2 + 4c 3 = 9; a 2 = c c 2 (2) 2 + c = c 1 + 4c c 3 = 9. c1 + c2 + ñ3 = 9, Вирішуючи систему c1 2c2 + 4c3 = 9, отримаємо c 1 = 7, c 2 = 4, c 3 = 2. Таким c1 + 4c2 + 16c3 = 9, таким чином, рішення ЛОРС має вигляд: a = (2) 2 4. Завдання 4. Знайти рішення лінійного однорідного рекурентного співвідношення третього порядку: a +3 = a a +1 3 a, a 0 = 6, a 1 = 15, a 2 = становимо характеристичне рівняння x 3 = x 2 + 5x 3 і знаходимо його коріння. x 3 + x 2 5x + 3 = 0; (x 1) 2 (x + 3) = 0; x 1 = x 2 = 1 корінь кратності 2; x 3 = 3 корінь кратності Знаходимо загальне рішення ЛОРС: a = (c 1 + c 2) (x 1) + c 3 (x 3) = (c 1 + c 2) 1 + c 3 (3). 3. За допомогою початкових умов знаходимо коефіцієнти c1, c2 та c3. a 0 = (c 1 + c 2 0) c 3 (3) 0 = c 1 + c 3 = 6; a 1 = (c 1 + c 2 1) c 3 (3) 1 = c 1 + c 2 3c 3 = 15; a 2 = (c 1 + c 2 2) c 3 (3) 2 = c 1 + 2c 2 + 9c 3 = 8. c1 + ñ3 = 6, Розв'язуючи систему c1 + c2 3c3 = 15, отримаємо c 1 = 8, c 2 = 1 і c 3 = 2. Таким c1 + 2c2 + 9c3 = 8, таким чином, рішення ЛОРС має вигляд: a = (8 +) 1 2 (3). 15

16 Завдання 5. Знайти рішення лінійного рекурентного співвідношення другого порядку: Перепишемо ЛРС як a +2 = 18 a a + 128, a 0 = 5, a 1 = 2. a a a = () 1. Виписуємо відповідний ЛОРС: a a a = 0. характеристичне рівняння та знаходимо його коріння. x 2 18x + 81 = 0; (x9) 2 = 0; x 1 = x 2 = 9 коріння характеристичного рівняння збіглося, отже, їх кратність дорівнює 2. Тоді загальне рішення a = (c 1 + c 2) (x 1) = (c 1 + c 2) Знаходимо a приватне рішення ЛРС. За умовою f() = R m () λ = = = R 0 () λ, де R 0 () = 128 багаточлен нульового ступеня від змінної, а λ = 1 не корінь характеристичного рівняння відповідного ЛОРС. Отже, a = Q m () λ = Q 0 () 1 де Q 0 () багаточлен нульового ступеня від змінної, в загальному вигляді Q 0 () = с. Таким чином, a = с 1. Далі, підставляємо a у вихідне ЛРС () і знаходимо коефіцієнт з багаточлен Q 0 (): с з с 1 = ; з 18с + 81с = 128; 64с = 128; с = 2. Отже, отримали a = с 1 = 2 1 = 2. 16

17 3. Знаходимо загальне рішення ЛРС, воно є сумою загального рішення відповідного ЛОРС a і ​​приватного рішення ЛРС a, тобто a = a + a = (c 1 + c 2) Залишилося за допомогою початкових умов знайти коефіцієнти c 1 і c 2. a 0 = (c 1 + c 2 0) = c = 5; a 1 = (c 1 + c 2 1) = 9c 1 + 9c = 2; Вирішуючи систему c1 + 2 = 5, 9c1 + 9c2 + 2 = 2, отримаємо c 1 = 3, c 2 = 3. Таким чином, рішення ЛРС має вигляд: a = (3 3) Завдання 6. Знайти рішення лінійного рекурентного співвідношення: a +2 = 10 a a , a 0 = 7, a 1 = 50. Перепишемо ЛРС у вигляді a a a = Виписуємо відповідний ЛОРС: a a a = 0; складаємо характеристичне рівняння та знаходимо його коріння. x 2 10 x + 25 = 0; (x5) 2 = 0; x 1 = x 2 = 5 корінь кратності 2. Тоді загальне рішення ЛОРС має вигляд: a = (c 1 + c 2) (x 1) = (c 1 + c 2) Знаходимо a приватне рішення ЛРС. За умовою f() = R m () λ = 50 5 = R 0 () λ, де R 0 () = 50 багаточлен нульового ступеня від змінної, а λ = 5 збігається з коренем x 1 кратності 2 характеристичного рівняння відповідного ЛОРС. Отже, a = r Q m () λ = = 2 Q 0 () 5, де Q 0 () = з багаточленом нульового ступеня від змінної. Таким чином, a = 2 з 5. Далі, підставляємо a у вихідне ЛРС і знаходимо коефіцієнт з: 17

18 с (+ 2) з (+ 1) з 2 5 = 50 5 (розділимо на 5 0); 25с (+2) 2 50с (+1) з 2 = 50; с() 2с() + с 2 = 2; с = 1. Отже, a = 2 з 5 = Виписуємо загальне рішення ЛРС: a = a + a = (c 1 + c 2) За допомогою початкових умов знаходимо коефіцієнти c 1 і c 2: a 0 = (c 1 + c 2 0) = c 1 = 7; a 1 = (c 1 + c 2 1) = 5c 1 + 5c = 50; Вирішуючи систему c1 = 7, c1 + c2 + 1 = 10, отримаємо c 1 = 7, c 2 = 2. Таким чином, рішення ЛРС має вигляд: a = (7 + 2) = () 5. Завдання 7. Знайти рішення лінійного рекурентного співвідношення: a +2 = 6 a +1 8 a , a 0 = 0, a 1 = 11. Перепишемо ЛРС у вигляді a +2 6 a a = Виписуємо відповідний ЛОРС: a +2 6 a a = 0; складаємо характеристичне рівняння та знаходимо його коріння. x 2 6x + 8 = 0; x 1 = 2, x 2 = 4 коріння кратності рівної 1. Тоді загальне рішення ЛОРС має вигляд a = c 1 (x 1) + c 2 (x 2) = c c Знаходимо a приватне рішення ЛРС. За умовою f() = R m () λ = = (3 + 2) 1 = R 1 () λ, де R 1 () = багаточлен першого ступеня від змінної, а λ = 1 не корінь характеристичного рівняння відповідного ЛОРС. Отже, a = Q m () λ = Q 1 () 1, де Q 1 () багаточлен першого ступеня від змінної, у загальному вигляді Q 1 () = = a + b. Таким чином, a = (a + b) 1. 18

19 a та b: Далі, підставляємо a у вихідне ЛРС і знаходимо коефіцієнти (a (+ 2) + b) (a (+ 1) + b) (a + b) 1 = 3 + 2; 25с (+2) 2 50с (+1) з 2 = 3 + 2; 3a + (3b 4a) = Таким чином, отримали, що два багаточлени рівні, а тоді рівні відповідні коефіцієнти: 3a = 3, a = 1, 3b 4a = 2 b = 2. Отже, a = (a + b) 1 = Виписуємо загальне рішення ЛРС: a = a + a = c c (+2). За допомогою початкових умов знаходимо коефіцієнти c 1 і c 2: a 0 = c c (0 + 2) = 0; a 1 = c c (1 + 2) = 11; Вирішуючи систему c1 + c2 = 2, 2c1 + 4c2 = 14, отримаємо c 1 = 3, c 2 = 5. Таким чином, рішення ЛРС має вигляд: a = Завдання 8. Знайти рішення лінійного рекурентного співвідношення: a +2 = 5 a +1 6 a + (10 4) 2, a 0 = 5, a 1 = 12. Перепишемо ЛРС у вигляді a +2 5 a a = (10 4) Виписуємо відповідний ЛОРС: a +2 5 a a = 0; складаємо характеристичне рівняння та знаходимо його коріння. x 2 5x + 6 = 0; x 1 = 3, x 2 = 2 коріння різних кратностей 1. Тоді загальне рішення ЛОРС має вигляд: a = c 1 (x 1) + c 2 (x 2) = c c

20 2. Знаходимо приватне рішення ЛРС. За умовою маємо, що f() = = R m () λ = (10 4) 2 = R 1 () λ, де R 1 () = (10 4) багаточлен першого ступеня від змінної, а λ = 2, то тобто збігається з коренем характеристичного рівняння відповідного ЛОРС. Отже, a = r Q m () λ = 1 Q 1 () 2, де Q 1 () багаточлен першого ступеня від змінної, у загальному вигляді Q 1 () = a + b. Таким чином, отримуємо a = = (a + b) 2. Далі, підставляємо a у вихідне співвідношення та знаходимо коефіцієнти a та b. (+ 2)(a (+ 2) + b) (+ 1) (a (+ 1) + b) (a + b) 2 = = (10 4) 2. Розділимо це рівняння на 2 0: 4(+ 2) (a (+ 2) + b) 10 (+ 1) (a (+ 1) + b) + 6 (a + b) = 10 4; 4a + (6a 2b) = Таким чином, отримали, що два багаточлени рівні, а тоді рівні відповідні коефіцієнти: 4a = 4, a = 1, 6a 2b = 10 b = 2. Отже, a = (a + b) 2 = (2) Виписуємо загальне рішення ЛРС, тобто a = a + a = c c (2) 2. За допомогою початкових умов знаходимо коефіцієнти c 1 і c 2. a 0 = c c (0 2) 2 0 = 5; a 1 = c c (1 2) 2 1 = 12. Вирішуючи систему c1 + c2 = 5, 3c1 + 2c2 = 14, отримаємо c 1 = 4, c 2 = 1. Таким чином, рішення ЛРС має вигляд: a = (2 ) 2 = () 2. 20

21 Завдання 9. Знайти рішення лінійного рекурентного співвідношення: a +2 = 8 a a , a 0 = 1, a 1 = 7. Перепишемо ЛРС у вигляді a +2 8 a a = () Виписуємо відповідний ЛОРС: a +2 8 a a = 0 ; складаємо характеристичне рівняння та знаходимо його коріння. x 2 8 x + 16 = 0; x 1 = x 2 = 4 коріння збіглося, отже, кратність кореня дорівнює 2. Тоді загальне рішення ЛОРС має вигляд: a = (c 1 + c 2) (x 1) = (c 1 + c 2) Знаходимо a приватне рішення ЛРС . За умовою f() = R m () λ = = () 1 = R 2 () λ, де R 2 () = багаточлен другого ступеня від змінної, а λ = 1 не збігається з коренем характеристичного рівняння відповідного ЛОРС. Отже, a = Q m () λ = Q 2 () 1, де Q 2 () багаточлен другого ступеня від змінної, у загальному вигляді Q 2 () = a 2 + b + c. Таким чином, a = = (a 2 + b + c) 1. Далі, підставляємо a у вихідне співвідношення і знаходимо коефіцієнти a, b та c. (a (+ 2) 2 + b (+ 2) + c) (a (+ 1) 2 + b (+ 1) + c) (a b + c) 1 = () 1; a(+ 2) 2 + b(+ 2)+ c 8a(+ 1) 2 8b(+ 1) 8c + 16a b + 16c = = ; 9a 2 12a + 9b 4a 6b + 9c = Таким чином, отримали, що два багаточлени рівні, а тоді рівні відповідні коефіцієнти: 9a = 9, 12a + 9b = 6, 4a 6b + 9c = 2 a = 1, b = 2, c = 2. 21

22 Отже, a = (a 2 + b + c) 1 = Виписуємо загальне рішення ЛРС, тобто a = a + a = (c 1 + c 2) (). За допомогою початкових умов знаходимо коефіцієнти c 1 і c 2. a 0 = (c 1 + c 2 0) () = 1; a 1 = (c 1 + c 2 1) () = 7. Вирішуючи систему c1 + 2 = 1, 4c1 + 4c2 + 5 = 7, отримаємо c 1 = 1, c 2 = 2. Таким чином, рішення ЛРС має вигляд : a = (1 2)

23 2. ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО РІШЕННЯ 2.1. Завдання для вирішення ЛОРС та ЛРС Лінійні однорідні рекурентні співвідношення другого порядку 1. a +2 = 9 a a, a 0 = 2, a 1 = a +2 = 3,5 a +1 2,5 a, a 0 = 3,5 , a 1 = a +2 = 8 a a, a 0 = 4, a 1 = a +2 = 2 a a, a 0 = 3, a 1 = i. 5. a +2 = 10 a a, a 0 = 3, a 1 = a +2 = 6 a a, a 0 = 0, a 1 = 2i a +2 = 8 a a, a 0 = 2, a 1 = a + 2 = 4 a a, a 0 = 7, a 1 = a +2 = a +1 + a, a 0 = 2, a 1 = a +2 = 8 a a, a 0 = 8, a 1 = a +2 = () a a, a 0 = 7, a 1 = a +2 = 5 a +1 4 a, a 0 = 0, a 1 = a +2 = 2 a +1 5 a, a 0 = 5, a 1 = 6i a +2 = 3 a a, a 0 = 7, a 1 = a +2 = 6 a +1 9 a, a 0 = 8, a 1 = a +2 = 6 a a, a 0 = 3, a 1 = 9 2i. 17. a +2 = a a, a 0 = 4, a 1 = a +2 = 14 a a, a 0 = 5, a 1 = a +2 = 8 a a, a 0 = 2, a 1 = a +2 = 7 a a, a 0 = 5, a 1 = a +2 = 2 a +1 + a, a 0 = 2, a 1 =

24 1 22. a +2 = a +1 a, a 0 = 4, a 1 = a +2 = 4 a +1 a, a 0 = 12, a 1 = a +2 = a a, a 0 = 2, a 1 = a +2 = 2 a a, a 0 = 8, a 1 = a +2 = 6 a +1 9 a, a 0 = 12, a 1 = a +2 = 4 a +1 5 a, a 0 = 5, a 1 = 10 i a +2 = 3 a +1 a, a 0 = 8, a 1 = a +2 = 14 a a, a 0 = 5, a 1 = a +2 = 4 a a, a 0 = 2, a 1 = a +2 = 4 a +1 5 a, a 0 = 3, a 1 = 6 7i. 32. a +2 = a a, a 0 = 5, a 1 = a +2 = 16 a a, a 0 = 7, a 1 = a +2 = 5 a +1 6 a, a 0 = 2, a 1 = a +2 = 10 a a, a 0 = 2, a 1 = 10 4i a +2 = 6 a +1 5 a, a 0 = 11, a 1 = a +2 = 2 a a, a 0 = 11, a 1 = a +2 = 6 a a; a 0 = 3, a 1 = 0. Лінійні однорідні рекурентні співвідношення третього порядку 39. a +3 = 7 a a a, a 0 = 1, a 1 = 3, a 2 = a +3 = 4 a +2 a +1 6 a, a 0 = 4, a 1 = 5, a 2 = a +3 = 6 a a a, a 0 = 5, a 1 = 8, a 2 = a +3 = 8 a a a, a 0 = 4, a 1 = 31, a 2 = a +3 = 5 a +2 3 a +1 9 a, a 0 = 1, a 1 = 3, a 2 = a +3 = 15 a a a, a 0 = 8, a 1 = 40, a 2 =

25 45. a +3 = 27 a a, a 0 = 6, a 1 = 3, a 2 = a +3 = 6 a a a, a 0 = 15, a 1 = 32, a 2 = a +3 = 15 a a a, a 0 = 1, a 1 = 20, a 2 = a +3 = 9 a a a, a 0 = 0, a 1 = 4, a 2 = a +3 = 2 a a +1 6 a, a 0 = 4, a 1 = 5, a 2 = a +3 = 4 a +2 5 a a, a 0 = 2, a 1 = 6, a 2 = a +3 = 6 a +2 5 a a, a 0 = 4, a 1 = 2, a 2 = a +3 = 3 a a a, a 0 = 2, a 1 = 17, a 2 = a +3 = 9 a a a, a 0 = 1, a 1 = 3, a 2 = a +3 = 6 a a +1 6 a, a 0 = 13, a 1 = 31, a 2 = a +3 = 5 a +2 3 a +1 9 a, a 0 = 3, a 1 = 14, a 2 = a +3 = a a +1 4 a, a 0 = 2, a 1 = 1, a 2 = a +3 = 3 a a a, a 0 = 2, a 1 = 3, a 2 = a +3 = 12 a a a, a 0 = 2, a 1 = 16, a 2 = a +3 = 4 a a a, a 0 = 0,2, a 1 = 6, a 2 = a +3 = 8 a a a, a 0 = 3, a 1 = 13, a 2 = a +3 = 4 a a a, a 0 = 3, a 1 = 29, a 2 = a +3 = 5 a +2 7 a a, a 0 = 11, a 1 = 34, a 2 = a +3 = 11 a a a, a 0 = 27, a 1 = 17, a 2 = a +3 = 12 a a a, a 0 = 1, a 1 = 37, a 2 = a +3 = 3 a a a, a 0 = 11, a 1 = 23, a 2 = a +3 = 7 a a a, a 0 = 3, a 1 = 6, a 2 = a +3 = 4 a a a, a 0 = 4, a 1 = 1, a 2 = 4; 68. a +3 = 7 a a a, a 0 = 1, a 1 = 0, a 2 = a +3 = 5 a a a, a 0 = 6, a 1 = 0, a 2 = a +3 = 5 a +2 3 a a, a 0 = 10, a 1 = 1, a 2 = a +3 = 3 a +2 3 a +1 + a, a 0 = 2, a 1 = 4, a 2 = a +3 = 3 a a a , a 0 = 6, a 1 = 5, a 2 =

26 73. a +3 = 10 a a a, a 0 = 0, a 1 = 1, a 2 = a +3 = 8 a a a, a 0 = 8, a 1 = 23, a 2 = a +3 = 5 a + 2 8 a +1 4 a, a 0 = 11, a 1 = 15, a 2 = a +3 = a a a, a 0 = 6, a 1 = 5, a 2 = a +3 = 10 a a a, a 0 = 1, a 1 = 2, a 2 = a +3 = a a a, a 0 = 1, a 1 = 14, a 2 = a +3 = 2 a +2 + a a, a 0 = 10, a 1 = 1, a 2 = a +3 = 5 a +2 8 a a, a 0 = 9, a 1 = 9, a 2 = a +3 = 8i a a +1 10i a, a 0 = 8; = 38. Лінійні рекурентні співвідношення першого порядку 82. a +1 = 4 a + 6, a 0 = a +1 = a + + 1, a 0 = a +1 = 5 a , a 0 = a +1 = 3 a + 5 2, a 0 = a +1 = 3 a + (4) 5 1, a 0 = a +1 = 4 a + 8 4, a 0 = a +1 = 3 a , a 0 = 14. Лінійні рекурентні співвідношення другого порядку 89. a +2 = 7 a a + 10, a 0 = 4, a 1 = a +2 = 10 a a + 32, a 0 = 1, a 1 = a +2 = 6 a +1 9 a 2 3, a 0 = 0, a 1 = a +2 = 7 a a , a 0 = 3, a 1 = a +2 = 9 a a + (18 20) 2, a 0 = 6, a 1 = a +2 = 8 a +1 7 a , a 0 = 9, a 1 = a +2 = 4 a +1 9 a , a 0 = 15, a 1 = 27 i a +2 = 12 a a , a 0 = 13, a 1 = 6. 26

Благовіщенський державний педагогічний університет кафедра алгебри, геометрії та МПМ 16 квітня 2011 р. 1 Рішення рекурентних співвідношень Визначення Рекурентним співвідношенням називається співвідношення

Лекція 3. Послідовності, що визначаються рекурентними співвідношеннями. Однорідні та неоднорідні лінійні рекурентні рівняння (ЛОРУ та ЛНРУ). Загальні рішення ЛОРУ та ЛНРУ. Лектор – доцент Селезньова Світлана

Лекція: Послідовності. Однорідні та неоднорідні лінійні рекурентні рівняння. Загальні рішення лінійних рекурентних однорідних та неоднорідних рівнянь. Лектор – доцент Селезньова Світлана Миколаївна

лекція. Функції натурального аргументу (послідовності). Однорідні та неоднорідні лінійні рекурентні рівняння (ЛОРУ та ЛНРУ). Загальні рішення ЛОРУ та ЛНРУ. Приклади Лектор – доцент Селезньова Світлана

РІШЕННЯ РЕКУРРЕНТНИХ РІВНЯНЬ Позначимо через значення деякого виразу при підстановці в нього цілого числа Тоді залежність члена послідовності від членів послідовності F F зі значеннями

Пензенський державний педагогічний університет ім У Г Бєлінського О А Монахова, Н А Восьминіна Рекурентні послідовності Алгебра формальних рядів Методичні рекомендації для студентів спеціальностей

Лекція 3. Послідовності, що визначаються рекурентними співвідношеннями. Однорідні та неоднорідні лінійні рекурентні рівняння (ЛОРУ та ЛНРУ). Загальні рішення ЛОРУ та ЛНРУ. Приклади Лектор – доцент Селезньова

Міністерство освіти та науки Російської ФедераціїФедеральне державне бюджетне освітня установавищої професійної освіти "Сибірський державний індустріальний університет"

Міністерство транспорту Російської Федерації ФЕДЕРАЛЬНА ДЕРЖАВНА БЮДЖЕТНА ОСВІТАЛЬНА УСТАНОВА ВИЩОЇ ОСВІТИ «РОСІЙСЬКИЙ УНІВЕРСИТЕТ ТРАНСПОРТУ (МІІТ)» Кафедра « Математичний аналіз»

Лекції з Математики Вип ТММ-Ю У Чебраков ТЕОРІЯ МАГІЧНИХ МАТРИЦЬ Санкт-Петербург, 00 УДК 5+5 ББК Ч35 Рецензенти: Доктор фізико-математичних наук, професор С-Петерб техн ун- Саль Кандидат

А А КИРСАНОВ КОМПЛЕКСНІ ЧИСЛА ПСКІВ ББК 57 К45 Друкується за рішенням кафедри алгебри та геометрії та редакційно-видавничої ради ПДПІ ім СМ Кірова Рецензент: Медведєва ІН, кандидат фіз мат наук, доцент

Михайлова Інна Анатоліївна Інститут математики та природничих наук. Кафедра алгебри та фундаментальної інформатики. 30 вересня 2018 р. Приклади Числа Фібоначчі Числа Фібоначчі 1, 1, 2, 3, 5, 8, 13, 21,...

Уральський федеральний університет, Інститут математики та комп'ютерних наук, кафедра алгебри та дискретної математики Поняття багаточлена Визначення Багаточленом від однієї змінної називається вираз виду

Глава 0 НАСЛІДНОСТІ Алгоритми А- Завдання числових послідовностей А-Арифметична прогресія А-Геометрична прогресія А-Підсумування А-5 Безкінечно спадна геометрична прогресія

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СПЕЦИАЛИЗИРОВАННЫЙ УЧЕБНО-НАУЧНЫЙ ЦЕНТР Математика 0 класс МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ И БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ

Федеральне агентство з освіти Державна освітня установа вищої професійної освіти Ухтинський державний технічний університет (УДТУ) МЕЖ ФУНКЦІЇ Методичні

ЧИСЛОВІ НАСЛІДНОСТІ. ГЕОМЕТРИЧНА ПРОГРЕСІЯ Геометричною прогресією називається числова послідовність b, перший член якої відмінний від нуля, а кожен наступний член, починаючи з другого,

ФЕДЕРАЛЬНА АГЕНЦІЯ З ОСВІТИ Державна загальноосвітня установа вищої професійної освіти «Тверський державний університет» Математичний факультет Кафедра алгебри

Розділ 0 ТЕСТОВІ ЗАВДАННЯ ТА ДИКТАНТИ Т-00 Обчислення членів послідовності за рекурентною формулою Т-00 Складання рекурентної формули Т-00 Формула загального члена Т-004 Складання арифметичної прогресії

6-7 уч рік 6, кл Математика Комплексні числа 4 Квадратні рівняння Алгебраїчні рівняння У шкільному курсі алгебри розглядалися квадратні рівняння ax bx c =, a, () з дійсними коефіцієнтами

МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ Державна освітня установа вищої професійної освіти МОСКІВСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ МАШИНОБУДУВАННЯ ІІ Поспєлов,

Лекція Розділ Множини та операції над ними Поняття множини Поняття множина відноситься до найбільш первинних понять математики не визначених через простіші Під множиною розуміють сукупність

Лекції з математики. Вип. ТММ-1 Ю. В. Чебраков ТЕОРІЯ МАГІЧНИХ МАТРИЦЬ Санкт-Петербург, 010 УДК 511+51 ББК Ч345 Рецензенти: Доктор фізико-математичних наук, професор С.-Петерб. техн. ун-ту

Прогресії Послідовність функція натурального аргументу. Завдання послідовності формулою загального члена: a n = f(n), n N, наприклад, a n = n + n + 4, а = 43, а = 47, а 3 = 3,. Завдання послідовності

ДИФЕРЕНЦІЙНЕ РІВНЯННЯ Загальні поняттяДиференціальні рівняння мають численні та найрізноманітніші додатки у механіці фізики астрономії техніці та інших розділах вищої математики (наприклад

Зміст Вступ. Основні поняття.... 4 1. Інтегральні рівняння Вольтерри... 5 Варіанти домашніх завдань.... 8 2. Резольвента інтегрального рівняння Вольтерри. 10 Варіанти домашніх завдань.... 11

МІНІСТЕРСТВО ЗАГАЛЬНОЇ ТА ПРОФЕСІЙНОЇ ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ НИЖЕМІСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ім. Н. І. ЛОБАЧЕВСЬКОГО Факультет обчислювальної математики та кібернетики Кафедра математичної

лекція. Завдання про кроликів. Числа Фібоначчі, послідовність Фібоначчі, рекурентна формула 3. Властивості чисел Фібоначчі (a) Лінійність (b) Теоретико-числові властивості (c) Суми: F + F +... + F n, непарних

ЛІНІЙНА АЛГЕБРА Видавництво ТДТУ Міністерство освіти і науки Російської Федерації ГОУ ВПО "Тамбовський державний технічний університет" ЛІНІЙНА АЛГЕБРА Методичні вказівки для студентів

Тишин В І Основні методи вирішення тригонометричних рівнянь г Тишин В І Математика для вчителів та учнів Матеріал підготовлений вчителем математики Тишиним Володимиром Івановичем року Тишин В І Основні

Диференціальні рівняння вищого ладу. Конєв В.В. Малюнки лекцій. 1. Основні поняття 1 2. Рівняння, що допускають зниження порядку 2 3. Лінійні диференціальні рівняння вищого порядку

лекція.7. Розширення поняття числа. Комплексні числа, дії з них Анотація: У лекції вказується необхідність узагальнення поняття числа від натурального до комплексного. Вводяться алгебраїчна,

МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ федеральна державна бюджетна освітня установа вищої професійної освіти «УЛЬЯНІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ»

Лекція 3 Ряди Тейлора і Маклорена Застосування статечних рядів Розкладання функцій у статечні ряди Ряди Тейлора і Маклорена Для додатків важливо вміти цю функцію розкладати в статечний ряд, ті функцію

Уральський федеральний університет, Інститут математики та комп'ютерних наук, кафедра алгебри та дискретної математики Вступні зауваження У цій лекції ми приступаємо до вивчення лінійної алгебри як такої,

Тема 2-11: Власні вектори та власні значення А. Я. Овсянніков Уральський федеральний університет Інститут математики та комп'ютерних наук кафедра алгебри та дискретної математики алгебра та геометрія

НОВОСИБІРСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ Заочна школа Математичне відділення МЕТОД МАТЕМАТИЧНОЇ ІНДУКЦІЇ ТА БЕЗКІНЕЧНІ ЧИСЛОВІ НАСЛІДНОСТІ 0-й клас, завдання ПРАВИЛА ОФОРМЛЕННЯ

ЗАВДАННЯ ДО КОНТРОЛЬНОЇ РОБОТИ За дисципліною: «Алгебра» Спеціальність: «Математика» заочна форма навчання 6 семестр Упорядник: зав кафедрою Трофімук АА Багаточлени від кількох змінних алгебраїчні результати

Вказівки, рішення, відповіді РІВНЯННЯ В ЦІЛІХ ЧИСЛАХ. Рівняння з однією невідомою. Рішення. Підставимо в рівняння. Отримаємо рівність (4a b 4) (a b 8) 0. Рівність A B 0 де А і В цілі, виконується,

ВСТУП В МАТЕМАТИЧНИЙ АНАЛІЗ Лекція. Поняття множини. Визначення функції основних властивостей. Основні елементарні функції ЗМІСТ: Елементи теорії множин Безліч дійсних чисел Числова

Робоча програма з алгебри для учнів 8-9 класів розроблена з урахуванням вимог до результатів освоєння основний освітньої програми основного загальної освіти. Робоча програма розрахована

Уральський федеральний університет, Інститут математики та комп'ютерних наук, кафедра алгебри та дискретної математики Вступні зауваження При вирішенні багатьох завдань виникає необхідність мати числові

ЗВИЧАЙНІ ДИФЕРЕНЦІЙНІ РІВНЯННЯ ПЕРШОГО ПОРЯДКУ.. Основні поняття Диференціальним рівнянням називається рівняння, до якого невідома функція входить під знаком похідної чи диференціала.

СИСТЕМИ ЛІНІЙНИХ ДИФЕРЕНЦІЙНИХ РІВНЯНЬ З ПОСТОЯННИМИ КОЕФІЦІЄНТАМИ Приведення до одного рівняння -го порядку З практичної точки зору дуже важливі лінійні системи з постійними коефіцієнтами

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ Нижегородський державний університет ім. НІ Лобачевського Національний дослідний університет АВ Леонтьєва

АГЕНЦІЯ ОСВІТИ АДМІНІСТРАЦІЇ КРАСНОЯРСЬКОГО КРАЮ КРАСНОЯРСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ЗАТІВНА природничо-наукова школа при красзі ДОДАТКОВІ ГЛАВИ МАТЕМАТИКИ

Міністерство освіти Російської Федерації Російський державний університет нафти та газу імені ІМ Губкіна ВІ Іванов Методичні вказівки до вивчення теми «ДИФЕРЕНЦІЙНІ РІВНЯННЯ» (для студентів

СТУПЕНЬ З ДРОБНИМ ПОКАЗНИКОМ Якщо показник t ступеня числа є дробовим, ті t, N, то для невід'ємних значень (0) за визначенням вважають def негативних чисел (0) < операция возведения

Міністерство сільського господарстваРосійської Федерації Федеральна державна бюджетна освітня установа вищої освіти«Пермська державна сільськогосподарська академія імені

РАЦІОНАЛЬНІ ЧИСЛА Звичайні дробиВизначення Дроби виду називаються звичайними дробами Визначення Дроби, правильні, якщо< при, где Z, N Z, N Z,

лекція. 5. ОПИС І АНАЛІЗ ДИСКРЕТНИХ ЛІНІЙНИХ СИСТЕМ ЗА ДОПОМОГОЮ РІЗНИЧНИХ РІВНЯНЬ 5.. ОДНОМІРНІ СИСТЕМИ ПРИ ДЕТЕРМІНОВАНИХ ВПЛИВАХ 5... Опис сигналів і систем. Опис сигналів. Сигнали

На закінчення цього пункту зауважимо, що говорять також про власні вектори матриці порядку, маючи при цьому через власні вектори оператора -мірного простору, який має своєю матрицею в деякому базисі.

ПРАКТИЧНЕ ЗАНЯТТЯ Інтегрування раціональних дробів Раціональним дробом називається дріб виду P Q, де P і Q багаточлени Раціональний дріб називається правильним, якщо ступінь многочлена P нижче ступеня

Тема 14 «Алгебраїчні рівняння та системи нелінійних рівнянь» Багаточлен ступеня n називається многочлен виду P n () a 0 n + a 1 n-1 + + a n-1 + a n, де a 0, a 1, a n-1, a n задані числа, a 0,

Тема: Загальна теорія систем лінійних рівнянь А. Я. Овсянніков Уральський федеральний університет Інститут математики та комп'ютерних наук кафедра алгебри та дискретної математики алгебра та геометрія для

МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ Московський державний університет геодезії та картографії (МІІГАіК) Факультет дистанційних формнавчання Заочне відділення `` МЕТОДИЧНІ ВКАЗІВКИ,

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРОМЫШЛЕННЫХ

Вирішити диференціальне рівняння Рішення: складемо і вирішимо характеристичне рівняння:, Отримано два різних дійсних кореня Все, що залишилося зробити записати відповідь, керуючись формулою

КОМПЛЕКСНІ ЧИСЛА РОЗКЛАДАННЯ МНОГОЧЛЕНІВ НА МНОЖИКИ Числові множини Множина комплексних чисел Багаточлени з речовими коефіцієнтами Розкладання на множники ЧИСЛОВІ МНОЖИНИ

Даний метод полягає в тому, що розв'язання комбінаторної задачі з n предметами виражається через розв'язання аналогічної задачі з меншим числом предметів за допомогою деякого співвідношення, що називається рекурентним. Говорять, що послідовність елементів u0, u1, … un, … над полем комплексних чисел C задовольняє рекурентному співвідношенню порядку k, якщо

де a1 , … , ak - Коефіцієнти з C. Співвідношення такого типу природним чином виникають при вирішенні комбінаторних завдань.

приклад. Нехай є послідовність позицій, занумерованих числами 1, 2, ..., n, ... і в початковий момент предмет знаходиться в першій позиції. За один хід предмет просувається вперед на 1 та 2 позиції. Визначити кількість методів потрапляння в n-ю позицію.

♦ Нехай un - цікаве для нас число. Зрозуміло, що u2 = 1, u3 = 2. Далі, розіб'ємо всі способи попадання в позицію з номером n на два класи: ті, при яких на останньому кроці предмет пересувається на 1 крок і ті, за яких він пересувається на 2 кроки. Зрозуміло, що у першому випадку маємо un-1 варіантів, у другому un-2 варіантів. Отже, маємо

Багаточлен P(x) називається характеристичнимдля лінійного рекурентного співвідношення (2). Зауважимо, що будь-яка рекурентна послідовність k-го порядку однозначно визначається завданням її перших членів.

Нехай - корінь характеристичного многочлена P(x).

Теорема 1. Послідовність u0, u1, … un, …, де un = c n, c - довільна константа з C, задовольняє лінійному рекурентному співвідношенню (2).

♦ Підставляючи дані значення un , n = 0, 1, … у (2), маємо

cλ n - a1 cλ n-1 - a2 cλ n-2 - … - ak c n-k = c n-k (λ k - a1 λ k-1 - … - ak ) ≡ 0. ♦

Теорема 2. Нехай послідовності un, vn, n = 0, 1, … задовольняють лінійному рекурентному співвідношенню (2). Тоді цією властивістю володіє послідовник-

ність rn , n = 0, 1, … , де rn = un + β vn , n , α, β - довільні константи з C.

♦ Доказ очевидний. ♦

Теорема 3. Нехай ?

Тоді загальне рішення даного рекурентного співвідношення має вигляд

де c1, …, ck - відповідні константи з C.

♦ Згідно з попереднім зауважуємо, що послідовність un , n = 0, 1, … є рішення співвідношення (2). Щоб довести, що будь-яке рішення має вигляд (5), достатньо показати, що для довільної послідовності vn , n = 0, 1, … , що задовольняє

(2), існують константи c1, …, ck, такі, що un = vn, n. Для цього достатньо, щоб виконувалося v0 = u0, v1 = u1, …, vk-1 = uk-1. Розглянемо ці умови

щодо c1, c2, …, ck. Визначником цієї системи є визначник Вандермонда і згідно (7, стор. 118).

згідно з припущенням про коріння λ 1, …, λ k. Звідси й випливає твердження. ♦ Як приклад розглянемо рекурентне співвідношення (3). Маємо характеристичний багаточлен

P(x) = x2 - x -1

Його коріння дорівнює λ 1 = 1 + 2 5 , λ 2 = 1 − 2 5 , Загальне рішення має вигляд

u n = c 1 1+ 2 5 n + c 2 1− 2 5 n

Система рівнянь для констант c1, c2: c1 1 + 2 5 + c2 1 − 2 5 = 1

Нехай тепер - корінь кратності r характеристичного многочлена P(x). Аналогічно попередньому доводиться

Теорема 4. Послідовності c1 λ n , c2 nλ n ,K , cr n r − 1 λ n , n = 0, 1, … для про-

довільних констант c1, …, cr із C задовольняють співвідношенню (2).

Теорема 5. Нехай характеристичний багаточлен P(x) має коріння λ 1 , … , λ s кратностей r1 , … , rs (r1 + … + rs = k). Тоді загальне рішення рекурентного співвідношення

Вкажемо ще одне корисна властивістьлінійних рекурентних співвідношень. Теорема 6. Нехай маємо співвідношення

un = a1 un-1 + … + ak un-k

з початковими умовами u1, …, uk. Тоді справедливе співвідношення за всіх n ≥ k

♦ Доказ індукцією за n. За n = k рівність (8) справедлива. Нехай воно правильно при n. При n+1 маємо

У більшості випадків, однак, при вивченні перелічувальних завдань виникають нелінійні рекурентні співвідношення, для вирішення яких використовуються специфічні прийоми. Деякі з них будуть розглянуті надалі. Наведемо важливий приклад нелінійного рекурентного співвідношення.

Теорема 7. Нехай C(n, k) - число підстановок n-елементної множини, що мають точно циклів. Тоді справедливо

♦ Розіб'ємо множину підстановок множини X = (1, 2, … n,) що мають точно k циклів, на два класи - підстановки, в яких елемент n міститься в одиничному циклі, та підстановки, в яких елемент n знаходиться в циклі довжини l, l > 1. У разі число підстановок збігається з числом підстановок множини X′ = (1, 2, …, n - 1), мають k - 1 циклів, тобто. C(n – 1, k – 1). У другому випадку, видаляючи елемент n, напів-

чаєм підстановку множини X′ = (1, 2, …, n - 1) з k циклами, число яких дорівнює C(n - 1, k). З'ясуємо тепер, яким числом способів підстановку ступеня n - 1 з k циклами можна додати елемент n. Якщо є цикл довжини i, це можна зробити i способами. Загальна кількість способів дорівнює i1 + … + ik, де i1, …, ik – довжини циклів підстановки. Однак i1 + … + ik = n – 1. Значить число підстановок другого класу дорівнює

(n - 1) C(n - 1, k). Звідси й одержуємо (9). ♦

Отримані числа C(n, k) пов'язані з відомими числами Стірлінга першого роду sn,k, які визначаються так:

sn,k = (- 1)n+k C(n, k)

Наведемо таблицю кількох перших значень чисел sn, k.

Табл. Числа Стірлінга першого роду

При великому обсязі сукупності даних спостереження хкінцеві методи вирішення рівняння правдоподібності призводять до значних обчислювальних труднощів, пов'язаних із необхідністю запам'ятовування великої кількостівихідних даних та проміжних результатів обчислень. У зв'язку з цим особливий інтерес представляють рекурентні методи, в яких оцінка максимальної правдоподібності обчислюється по кроках з точністю, що поступово збільшується, причому кожен крок пов'язаний з отриманням нових даних спостереження, а рекурентна процедура будується так, щоб зберігати в пам'яті по можливості найменшу кількість даних від попередніх кроків. Додатковим і дуже суттєвим з практичної точки зору перевагою рекурентних методів є готовність до видачі результату на будь-якому проміжному кроці.

Це обумовлює доцільність застосування рекурентних методів навіть у тих випадках, якщо вдається отримати точне рішення рівняння максимальної правдоподібності кінцевим методом, і робить їх ще більш цінними, коли неможливо знайти точне аналітичне вираження для оцінки максимальної правдоподібності.

Нехай сукупність даних спостереження є послідовністю для опису якої введемо вектор . (Як завжди, кожна його компонента, у свою чергу, може бути вектором, відрізком випадкового процесу тощо). Нехай – функція правдоподібності, а

її логарифм. Останній завжди можна уявити у вигляді

Логарифм функції правдоподібності для сукупності даних спостереження без останнього значення, а

Логарифм умовної густини ймовірності значення при заданих значеннях і .

Подання (7,5.16) для логарифму функції правдоподібності є основою отримання рекурентної процедури обчислення оцінки максимальної правдоподібності. Розглянемо регулярний випадок. При цьому оцінка максимальної правдоподібності може бути знайдена як рішення рівняння

яке відрізняється від (7.1.6) лише запровадженням індексу п улогарифма функції правдоподібності

Позначимо рішення цього рівняння через підкресливши тим, що ця оцінка отримана за сукупністю даних спостереження. Аналогічно позначимо через рішення рівняння-оцінку максимальної правдоподібності, отриману за сукупністю даних.

Рівняння (7.5.19) можна переписати з урахуванням (7.5.16) у такому вигляді:

Розкладемо ліву частину (7.5.20) до ряду Тейлора на околиці точки . При цьому

(7.5.22)

Вектор градієнта функції в точці; доданок звертається в нуль завдяки тому, що , є рішенням рівняння правдоподібності для попереднього (п - 1)-го кроку:

Симетрична матриця других похідних логарифму функції правдоподібності в точці , взята зі зворотним знаком, аненаписані члени розкладання мають квадратичний і вищий порядок дещиці щодо різниці . Нехтуючи цими останніми, отримуємо наступне наближене рішення рівняння максимальної правдоподібності:

де - матриця, зворотна.

Це рішення представлено у формі рекурентного співвідношення, що визначає чергове значення оцінки через оцінку на попередньому кроці та поправку , залежить від наявних даних спостереження безпосередньо і через попередню оцінку. Виправлення формується як добуток градієнта логарифму умовної щільності ймовірності новоствореного значення х n у точці , що дорівнює попередньої оцінки, на вагову матрицю . Остання визначається виразом (7.5.23) і також залежить від оцінки на попередньому кроці, а її залежність від нових даних спостереження цілком визначається видом логарифму умовної густини ймовірності.

Формою співвідношення (7.5.24) дуже схоже на (7.5.8), що реалізує ітеративний спосіб обчислення оцінки максимальної правдоподібності за методом Ньютона. Однак насправді вони суттєво відрізняються один від одного. В (7.5.8) поправка до попереднього значення оцінки визначається величиною градієнта логарифму всієї функції правдоподібності, який завжди залежить від усіх наявних даних спостереження, що вимагає запам'ятовування всієї цієї сукупності. Відповідно до (7.5.24) поправка визначається величиною градієнта , який завдяки властивостям умовної щільності ймовірностіфактично залежить тільки від тих значень (), які знаходяться в сильному статистичному зв'язку з х n. Ця відмінність є наслідком спеціального вибору попереднього наближення як оцінки максимальної правдоподібності, знайденої за зменшеною на одне значення сукупності даних спостереження і особливо яскраво проявляється при незалежних значеннях (). У цьому останньому випадку

завдяки чому залежить тільки від і х n , а градієнт - тільки від попереднього значення оцінки та знову отриманих на п-кроці даних спостереження. Тому при незалежних значеннях для формування вектора не потрібно запам'ятовувати з попереднього кроку жодної іншої інформації, крім оцінки.

Аналогічно, у разі марківської послідовності даних спостереження, тобто при

вектор залежить тільки від , поточного та одного попереднього значення .У цьому випадку для обчислення потрібно запам'ятати з попереднього кроку, крім значення , ще тільки значення , але не всю сукупність даних спостереження, як в ітеративної процедури. У загальному випадку для обчислення може знадобитися запам'ятовування більшого числапопередніх значень (), однак через необхідність обліку тільки тих значень, які статистично залежні з , це число практично завжди менше повного обсягу сукупності даних спостереження. Так, якщо вектор описує тимчасову послідовність, то кількість членів цієї послідовності, що підлягають запам'ятовуванням, визначається часом її кореляції, а відносна їх частка убуває назад пропорційно nяк і у разі незалежних значень.

Розглянемо тепер структуру вагової матриці , що входить у рекурентне співвідношення (7.5.24). Згідно з визначенням (7.5.23), через наявність доданку вона, взагалі кажучи, залежить від усіх значень навіть при незалежних значеннях, що позбавляє рекурентне співвідношення (7.5.24) переваг, пов'язаних з можливим скороченням кількості даних, що запам'ятовуються з попереднього кроку. Існує кілька способів наближеного обчислення матриці , які усувають цей недолік.

Перший з них заснований на більш послідовному використанні основного припущення про малу відмінність двох чергових значень оцінки та , яке є основою для отримання рекурентного співвідношення (7.5.24). Це дозволяє отримати аналогічне рекурентне співвідношення для вагової матриці .Дійсно, використовуючи трохи з (7.5.23)

Ввівши позначення

з (7.5.24) та (7.5.25) отримаємо систему рекурентних співвідношень для вектора та вагової матриці

Ця система спільно з початковими значеннями і повністю визначає значення оцінки на будь-якому кроці, вимагаючи на кожному з них обчислення тільки градієнта та матриці других похідних від логарифму умовної густини ймовірності для поточного значення. Початкові значення вибираються з урахуванням наявних апріорних даних про можливі значення та діапазон зміни параметрів , а за повної відсутності цих даних приймаються нульовими (,).

При незалежних значеннях система рекурентних співвідношень (7.5.27), очевидно, описує багатовимірний (розмірності) марківський випадковий процес, компонента якого сходить до справжнього значення параметра, а компонента сходить до інформаційної матриці Фішера (7.3.8), де - справжнє значення параметра, що оцінюється , і необмежено збільшується зі зростанням п.Аналогічні властивості збіжності система (7.5.27) має і за більш загальних умов, якщо послідовність є ергодичною.

Другий зі згаданих способів заснований на заміні матриці других похідних від логарифму функції правдоподібності її математичним очікуванням - інформаційною матрицею Фішера, яка з урахуванням (7.5.16) може бути записана у вигляді:

де аналогічно (7.5.26)

Замінюючи в (7.5.24) матрицю , отримуємо рекурентне співвідношення

для наближеного обчислення оцінок максимальної правдоподібності, запропоноване Сакрісоном (в оригіналі для незалежних однаково розподілених коли і . Це рекурентне співвідношення простіше системи(7.5.27), оскільки оптимальна вагова матриця замінена її математичним очікуванням, і для її знаходження не потрібні наявні дані спостереження, крім тих, що сконцентровані у значенні оцінки. У той самий час очевидно, що така заміна означає необхідність виконання додаткового порівняно з (7.5.27) вимоги близькості матриці других похідних до математичного очікування.

Якщо щільність розподілу ймовірності та матриця змінюються від кроку до кроку, пряме перебування на кожному кроці може вимагати надто великої кількості обчислень. При цьому за рахунок додаткового зменшення точності результатів, що визначається нерівністю нулю малих різниць можна перейти до рекурентного обчислення наближеного значення матриці . Повертаючись до попереднього позначення для цього наближеного значення, отримуємо ще одну систему рекурентних співвідношень

Математичне очікування матриці (інформаційна матриця Фішера одного спостереження ), взяте у точці . Ця система відрізняється від (7.5.27) тим, що у другому з рекурентних співвідношень (7.5.31) не беруть безпосередньо дані спостереження.

Будь-яка з розглянутих вище систем рекурентних співвідношень є абсолютно точною, якщо функція квадратично залежить від , додатково матриця других похідних не залежить від . Фактично це відповідає нагоди незалежних нормально розподілених (не обов'язково однаково) значень з невідомим математичним очікуванням, яке і є оцінюваним параметром.

Система рекурентних співвідношень (7.5.24) дає точне рішення рівняння максимальної правдоподібності в набагато ширших умовах за єдиної вимоги, щоб функція квадратично залежала від . У цьому залежність від довільна, що він відповідає широкому класу розподілів ймовірності сукупності як із незалежними, і із залежними значеннями.

Поряд із розглянутими загальними способами існує ще ряд методів вибору матриці вагових коефіцієнтів у рекурентному співвідношенні (7.5.24), пристосованих до тих чи інших конкретних обмежень. Найпростішим з них є вибір у вигляді діагональної матриці, так що , ( I- одинична матриця), де - спадна послідовність числових коефіцієнтів, що вибирається незалежно від властивостей функції правдоподібності так само, як у процедурі стохастичної апроксимації Робінса - Монро, яка буде розглянута в наступних розділах.

Варто зазначити, що будь-які ітераційні чи рекурентні процедури знаходження оцінок максимальної правдоподібності у загальному випадку є наближеними. Тому, взагалі кажучи, для оцінок, що виходять внаслідок застосування цих процедур, спроможність, асимптотичну ефективність та асимптотичну нормальність треба доводити наново. Для ітеративних процедур необхідні властивості оцінок гарантуються тим, що в принципі такі процедури за відповідної кількості ітерацій дають рішення рівняння правдоподібності з будь-якою заданою точністю. Для рекурентних процедур типу (7.5.27), (7.5.30), (7.5.31) та інших є спеціальні докази. При цьому, крім вимог регулярності, пред'являються деякі Додаткові вимоги:

На поведінку функції (7.2.2) при різних значеннях||, задля досягнення з допомогою рекурентної процедури глобального максимуму цієї функції у точці , що відповідає істинному значенню параметра;

На порядок зростання других моментів похідних логарифму функції правдоподібності при великих за модулем значеннях. Ці вимоги є наслідком більш загальних умов збіжності в точку всіх або частини компонентів марковського випадкового процесу, до якого приводить та чи інша процедура рекурентної.

На закінчення відзначимо також, що в тому випадку, коли існує точне рішення рівняння максимальної правдоподібності, воно практично завжди може бути представлене в рекурентному вигляді. Наведемо два простих різнорідних прикладів. Так, елементарна оцінка невідомого математичного очікування нормальною випадкової величиниза сукупністю nїї вибіркових значень у вигляді арифметичного середнього

є оцінкою максимальної правдоподібності і може бути представлена ​​в рекурентному вигляді:

що є найпростішим окремим випадком (7.5.30) при

Інший приклад - це нерегулярна оцінка максимальної правдоподібності для параметра - ширини прямокутного розподілу - (7.4.2), яка також може бути визначена рекурентним співвідношенням

з початковою умовою. Це рекурентне співвідношення вже іншого типу: його праву частину не можна подати у вигляді суми попередньої оцінки та малої поправки, що є наслідком нерегулярності цього прикладу; проте воно має всі переваги рекурентного підходу: вимагає запам'ятовування з попереднього кроку всього одного числа - оцінки - і різко скорочує перебір до одного порівняння замість порівняння всіх значень.

Наведені приклади ілюструють переваги рекурентних методів навіть у тому випадку, коли рівняння максимальної правдоподібності допускає точне рішення, бо простота аналітичного подання результату не є тотожною обчислювальній простоті його отримання.

7.5.3. Перехід до безперервного часу. Диференціальні рівняння для оцінок максимальної правдоподібності

Розглянемо тепер спеціальний випадок, коли наявні дані спостереження хописуються не сукупністю вибіркових точок , а є відрізок реалізації деякого процесу , залежить від параметрів, заданий на інтервалі , причому довжина цього інтервалу може збільшуватись при спостереженні (момент часу tє змінним).

Для статистичного опису даних спостереження в цьому випадку вводиться функціонал відносини правдоподібності, що представляє собою межу при , maxвідношення щільності розподілу ймовірності сукупності значень при довільно заданому значенні до аналогічної щільності ймовірності при деякому фіксованому значенні , а в деяких випадках, коли допускає уявлення , де - випадковий , який залежить від , до щільності ймовірності сукупності значень за умови, що . Використання функціоналу відносини правдоподібності дозволяє виключити формальні труднощі визначення густини ймовірності, що виникають при переході до безперервного часу.

Логарифм функціоналу відношення правдоподібності може бути представлений у вигляді

де - деякий функціонал процесу на інтервалі. У деяких випадках функціонал вироджується у функцію, яка залежить тільки від значення . Так, якщо

де - відома функція часу та параметрів , а - дельта-корельований випадковий процес («білий» шум) із спектральною щільністю N o ,то, вибираючи як знаменник відносини правдоподібності розподілу ймовірності хпри , будемо мати

Нехай - оцінка максимальної правдоподібності параметра, побудована за реалізацією процесу на інтервалі, тобто рішення рівняння максимальної правдоподібності

Диференціюючи ліву частину цього рівняння за часом, отримуємо

Вводячи позначення

і вирішуючи рівняння (7.5.42) щодо , отримуємо диференціальне рівняння для оцінки максимальної правдоподібності

Матриця , своєю чергою, відповідно (7.5.37) визначається диференціальним рівнянням

Так само, як у дискретному випадку, матриця (7.5.45), (7.5.47) може бути замінена своїм математичним очікуванням - інформаційною матрицею Фішера при значенні , а диференціальне рівняння (7.5.46) для вагової матриці - рівнянням

де аналогічно дискретному випадку

Математичне очікування матриці других похідних.

Сукупність диференціальних рівнянь (7.5.45), (7.5.46) або (7.5.45), (7.5.48) спільно з початковими умовами, щодо вибору яких залишається чинним все сказане для дискретного випадку, повністю визначає оцінку максимальної правдоподібності для будь-якого моменту часу. Ця сукупність може бути змодельована за допомогою відповідних, взагалі кажучи, нелінійних аналогових пристроїв або за відповідної дискретизації за часом вирішена за допомогою ЕОМ. Зазначимо на закінчення одну з модифікацій цих рівнянь, що дозволяє уникнути необхідності обігу матриці.

Вводячи позначення

, де I

та диференціюючи за часом співвідношення , де I- одинична матриця, отримуємо за допомогою (7.5.46) диференціальне рівняння, що визначає безпосередньо матрицю:

(і аналогічно при заміні на ), яке спільно з рівнянням (7.5.45)

визначає оцінку , не вимагаючи звернення матриць. При цьому має місце перехід від найпростішого лінійного диференціального рівняння (7.5.46) до нелінійного щодо диференціального рівняння (7.5.51) типу Ріккаті.

Лінійні рекурентні співвідношення із постійними коефіцієнтами. Основні визначення та приклади рекурентних співвідношень Часто рішення однієї комбінаторної задачі вдається звести до вирішення аналогічних завдань меншої розмірності за допомогою деякого співвідношення званого рекурентним від латинського слова recurrere Повертатися. Тим самим розв'язання складної задачі можна отримати послідовно знаходячи рішення легших задач і далі перераховуючи по рекурентним співвідношенням знаходити розв'язання важкої задачі. Рекурентним співвідношенням го...

Якщо ця робота Вам не підійшла внизу сторінки, є список схожих робіт. Також Ви можете скористатися кнопкою пошук

аранів Віктор Павлович. Дискретна математика. Розділ 2. Елементи комбінаторики.

Лекція 5. Метод рекурентних співвідношень

Лекції 5. МЕТОД РЕКУРРЕНТНИХ СПІВВІДНОШЕНЬ

План лекції:

1. Основні визначення та приклади рекурентних співвідношень.
2. Лінійні рекурентні співвідношення із постійними коефіцієнтами. Формула

Біне.

1. Основні визначення та приклади рекурентних співвідношень

Часто розв'язання однієї комбінаторної задачі вдається звести до розв'язання аналогічних задач меншої розмірності за допомогою деякого співвідношення, що називається річкар рентним (від латинського слова recurrere Повертатися). Тим самим вирішення складної задачі можна отримати, послідовно знаходячи рішення легших завдань, і далі, пе розраховуючи за рекурентними співвідношеннями, знаходити розв'язання важкого завдання.

Рекурентним співвідношенням -го порядкуміж елементами послідовності чисел називається формула виду

(1)

Приватним рішеннямрекурентного співвідношення є будь-яка послідовникь ність, що звертає співвідношення (1) у тотожність. Співвідношення (1) іме ет нескінченно багато приватних рішень, так як перші елементи послідовніо сти можна задати довільно. Наприклад, послідовність є ре шенням рекурентного соотно ня, оскільки має місце тотожність.

Рішення рекурентного співвідношення -го порядку називаєтьсязагальним, якщо воно за висить від довільних постійних, і шляхом підбору цих постійних мож але отримати будь-яке рішення цього співвідношення. Наприклад, для співвідношеньня

(2)

загальним рішенням буде

. (3)

Справді, легко перевірити, що послідовність (3) перетворює співвідношення (2) у тотожність. Тому треба тільки показати, що будь-яке рішення співвідношення (2) мож але у вигляді (3). Але будь-яке рішення цього співвідношення однозначно визначаєт ся значеннями і. Тому треба довести, що для будь-яких чисел і знайдутьсяа значення і, що

Так як ця система має рішення за будь-яких значень і, то рішення (3) дійсно є загальним рішенням співвідношення (2).

приклад 1 . Числа Фібоначчі.У 1202 р. знаменитим італійським математиком Лео нардо Пізанським, який відомий більше на своє прізвисько Фібоначчі ( Fib o nacci | скорочене filius Bonacci , тобто син Боначчі), була написана книга « Liber abacci» («Кн і га про абака»). До нас ця книга дійшла у другому своєму варіанті, що відноситься до 1228 р. Розглянемо одну з безлічі наведених у цій книзі завдань.

Пара кроликів приносить раз на місяць приплід з двох кроленят (самки і самця), іні ніж новонароджені кроленята через два місяці після народження вже приносять приплід. Скільки кроликів з'явитьсяе рез рік, якщо на початку року була одна пара кроликів?

З умови завдання випливає, що за місяць буде дві пари кроликів. Через два місяція ця приплід дасть тільки перша пара кроликів, і вийде 3 пари. A ще через місяць приплід дадуть і вихідна пара кролів, і пара кролів, що з'явилася два місяці тому. Тому всього буде 5 пар кролів і т.д.

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

. (4)

Так, то послідовно знаходимо: і т. д. Ці числа становлять послідовність

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…,

яку називаютьпоруч Фібоначчі, а його члени числами Фібоначчі. Вони мають цілу низку чудових властивостей. Числа Фібоначчі пов'язані з наступною комбінацієюа торним завданням.

Знайти число двійкових слів довжини, в яких жодні дві одиниці не йдуть под ряд.

Зватимемо такі словаправильними і позначимо їхнє число через. Розіб'ємо велику кількість цих правильних слів на два класи: слова, що закінчуються на нуль, і слова, що закінчуються на одиницю. Позначимо кількість слів у цих класах і соот ветственно. За правилом складання

(5)

Очевидно, що слово, що закінчується на нуль, перші символи утворюють правильне слово довжини, або іншими словами, є біекція між безліччю правильних слів довжини, що закінчуються на нуль, і безліччю правильних слів довжини, тобто.

Якщо правильне слово довжини закінчується на одиницю, попередній символ цього слова має бути нулем, а перші символи повинні утворювати правильне слово довжини. Як і в попередньому випадку, знову маємо бієкцію між безліччю правильних слів довжини, що закінчуються на одиницю, і множиною правильних слів довжини. Отже. . З формули (5) отримуємо рекурентне соотнпро шення

. (6)

Для використання рекурентного співвідношення необхідні для цього вичіз лення всіх попередніх значень. Наприклад, якщо нам потрібно знати кількість правиль них слів з 10 символів, то його можна знайти, послідовно заповнюючи наступну таб особі:

Таблиця 1

Перші два значення знаходяться безпосередньо (? слова 0 і 1; ? слова 000, 010, 101), а решта за формулою (6).

приклад 2. Завдання про розміщення дужок у виразі з неасоціативною біноюрної операцією. Нехай позначає деяку бінарну операцію. Розглянемо вы ураження, в якому символ позначає деяку бінарну неасоціаціюа тивну операцію. Скільки є різних способів розміщення дужок у цьомувиразі?

Як приклад неасоціативної операції можна навести векторне твір. Інший приклад - звичайне додавання і множення, що виконується на комп'ютері. У сі тому, що подання кожного числа в пам'яті комп'ютера обмежене визначеннян ною кількістю розрядів, при виконанні кожної операції виникає похибка та сум марний результат цих похибок залежить від розміщення дужок. Нехай |машинний нуль . Це означає, що. Тоді, в той час, як.

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

Назвемо операцію умовно твором. Для довільного розіб'ємо всі способи розміщення дужок на класи, включивши в -ий клас способи, при якиха чала обчислюється добуток перших і останніх операндів з якоюсь відстаннюа новинок дужок, а потім обчислюється їх твір:

(7)

де.

За визначенням кількість способів розміщення дужок для обчислення перших операндів дорівнює, останніх. За правилом твору кількість розстановок ско бік для виразу (4) одно. За правилом складання

, (8)

Наприклад, .

1. Лінійні рекурентні співвідношення з постійними коефіцієнтами

Нехай функція у співвідношенні (1) є лінієюй ний

, (9)

де деякі частини. Такі співвідношення називаютьлінійними соотно шення-го порядку з постійними коефіцієнтами.

Спочатку досліджуємо докладно співвідношення другого порядку, а потім перейдемо доб щему випадку. При формулі (9) отримаємо

, . (10)

Рішення цих співвідношень засноване на наступних тверджень, що легко доводяться.нях.

Лемма 1. Нехай рішення співвідношення (10), а будь-яке число. Тоді послідовність також вирішеноі ним цього співвідношення.

Лемма 2. Нехай і рішення соотно шення (10). Тоді послідовність також явля ється рішенням цього співвідношення.

З цих двох простих лем можна зробити такий важливий висновок. Совокп ність всіляких послідовностей з операціями спокійр динатного складання та множення на скаляр утворює векторний простір. Совокп ність послідовностей, що є рішеннями співвідношення (10), представляєо бій підпростір цього простору. Об'ємний простір всіляких по слідств нескінченномірно, але підпростір рішень лінійного рекуррент ного співвідношення має кінцеву розмірність, рівну порядку рівняня.

Лемма 3. Розмірність простору рішень рекурентного співвідношення (10) дорівнює двом.

З леми 3 випливає, що для визначення всіх розв'язків рівняння (12) необхідно відшукати два лінійно незалежні рішення. Будь-яке інше рішення буде представлятиь ся лінійною комбінацією цих базисних рішень.

Розглянемо рекурентне співвідношення першого порядку

, (11)

де - константа.

Якщо, то з (11) маємо

, (12)

тобто рішенням рекурентного рівняння першого порядку є геометрична прогресія.

Шукатимемо рішення рекурентного співвідношення другого порядку також у вигляді (12). Тоді, підставляючи (12) до (9), отримаємо

. (13)

При =0 маємо нульове рішення, яке представляє інтересу. Вважаючи, поділимо останнє співвідношення на:

(14)

Таким чином, геометрична прогресія (12) є рішенням рекурентного співвідношення (10), якщо знаменник прогресії є коренем квадратного рівня.е ня (14). Це рівняння називаєтьсяхарактеристичним рівняннямдля рекурентного соот носіння (9).

Побудова базисних рішень залежить від коріння та характеристичного рівняння (14).

1. (). У цьому випадку маємо два рішення і які лі нейно незав і сими. Щоб переконатися в цьому, покажемо, що із формули

(15)

шляхом відповідного вибору констант можна отримати рішення співвідношення (10). Розглянемо довільне рішення. Виберемо константи і так, щоб при:

(16)

Визначник лінійної системи (16)

отже, система має єдине рішення, а значить формула (15) загальне ре шення співвідношення (10).

1. . У разі кратного коріння характеристичне рівняння (13) має вигляд або. Тоді, а для співвідношення (10) по лучим рівняння, що дає два базисних рішення и. Загальне рішення подається у вигляді

. (17)

У разі співвідношення порядку (9) мають місце затвердження, аналогічні тим, які були розглянуті для рівнянь 2-го порядку.

1. Сукупність всіх рішень рівняння (9) є підпростором у про подорожі всіх послідовностей.
2. Розмірність цього простору дорівнює, тобто кожне рішення однозначно визначається своїми першими значеннями.
3. Для визначення базису підпростору рішень складається характеристикае ське рівняння

. (18)

Багаточлен

(19)

називається характеристичним багаточленомрекурентного співвідношення (9).

1. Якщо характеристичне рівняння має різного коріння, то загальне рішення рекурентного співвідношення (9) має вигляд

. (20)

При заданих початкових значеннях рішення, константи на ходять із системи

1. Якщо корінь характеристичного рівняння кратності, то співвідношення (9) має такі рішення

Нехай характеристичне рівняння (18) має коріння: ,…, кратності зо відповідально, ..., причому. Тоді характеристичний багатоо член та загальне рішення співвідношення (9) представляться у вигляді

Приклад 3 . Формула Біне . Поставимо завдання отримати формулу у явному вигляді для годі сіл Фібоначчі. Для цього знайдемо рішення рекурентного співвідношення (4) за умови, що. Складемо характеристичне рівняння, знайдемо його коріння та отримаємо загальне рішення. Константи та опреде лім із початкових умов: . Тоді чи

, (21)

де золотий переріз. Формула (21) називаєтьсяформулою Біне . При цьому. З формули Біне випливає, що.