Знайти рекурентне співвідношення онлайн. Виробляючі функції - туди і назад

Рекурентним співвідношенням, рекурентним рівняннямабо рекурентною формулоюназивається співвідношення виду, яке дозволяє обчислювати всі члени послідовності
якщо задані її перші kчленів.

1. Формула
задає арифметичну прогресію.

2. Формула
визначає геометричну прогресію.

3. Формула
задає послідовність чисел Фібоначчі.⁫

У разі, коли рекурентне співвідношення лінійне та однорідне, тобто виконується співвідношення виду

(p= Const), послідовність
називається зворотної. Багаточлен

називається характеристичнимдля зворотної послідовності
. Коріння багаточлена
називаються характеристичними.

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

Опис загального рівняння співвідношення (1) має аналоги з описом рішення звичайного диференціального рівняння постійними коефіцієнтами.

Теорема 1. 1. Нехай- Корінь характеристичного багаточлена (2). Тоді послідовність
, деc- Довільна константа, задовольняє співвідношенню (1).

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

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

Знаючи загальне рішення рекурентного рівняння (1), за початковими умовами,
можна знайти невизначені постійні і тим самим отримати рішення рівняння (1) з цими початковими умовами.

Приклад 2. Знайти послідовність
, що задовольняє рекурентне співвідношення
та початковим умовам
.

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

вирішуючи яку, знаходимо
і
. Таким чином,
.⁫

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

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

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

Таким чином, в силу теореми 1. Завдання знаходження загального рішення рекурентного рівняння (3) зводиться до знаходження деякого приватного рішення.

В окремих випадках є загальні рецепти знаходження загального рішення.

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

Нехай
- багаточлен ступеня rвід змінної n, і число 1 не є характерним коренем. Тоді і приватне рішення слід шукати у вигляді
. Підставляючи багаточлени у формулу (3), отримуємо

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

приклад. Знайти рішення рівняння

(4)

з початковою умовою
.

Розглянемо характеристичний багаточлен
. Так як
та права частина
рівняння (3) дорівнює n+1, то приватне рішення шукатимемо у вигляді
. Підставляючи рівняння (4), отримуємо . Прирівнюючи коефіцієнти у лівій та правій частинах останньої рівності, отримуємо систему

звідки знаходимо
. Таким чином, приватне рішення рівняння (4) має вигляд
. По теоремі 3.1. загальне рішення однорідного рівняння
задається формулою
, та за теоремою 3.2. отримуємо загальне рішення рівняння (4):
. З початкової умови
знаходимо
, тобто. . Таким чином,
.

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

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

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

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

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

Поєднання

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

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

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

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

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

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

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

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

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

(7.1)

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

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

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

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

(7.2)

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

Зокрема, .

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

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

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

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

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

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

(7.3)

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

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

Розмір: px

Починати показ зі сторінки:

Транскрипт

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 параметрів і т. д. Послідовно зменшуючи кількість параметрів, можна дійти задачі, яку вже легко розв'язати. Поняття рекурентного співвідношення (поворотної послідовності) є широким узагальненням поняття арифметичної або геометричній прогресії. Як окремі випадки воно охоплює також послідовності квадратів або кубів натуральних чисел, послідовності цифр десяткового розкладання раціонального числа(і взагалі будь-які періодичні послідовності), послідовності коефіцієнтів приватного від поділу двох багаточленів, розташованих за зростаючими ступенями х, і т. д. 5

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) х). 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

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

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

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

Міністерство освіти та науки Російської ФедераціїМосковський фізико-технічний інститут (державний університет) Заочна фізико-технічна школа МАТЕМАТИКА Тотожні перетворення. Рішення

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

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

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

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

03 Математика у вищій освіті УДК 54; 5799 ЗМІСТ І ТЕХНОЛОГІЇ МАТЕМАТИЧНОЇ ОСВІТИ У ВНЗ ДЕЯКІ МЕТОДИ СУМУВАННЯ ЧИСЛОВИХ НАСЛІДОК А В Ласунський Новгородський державний

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

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

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

А. І. Козко В. Г. Чирський Завдання з параметром та інші складні завданняМосква Видавництво МЦНМО 2007 УДК 512 ББК 22.141 К59 К59 Козко А. І. Чирський В. Г. Завдання з параметром та інші складні завдання. М.:

ЛЕКЦІЯ N Диференціальні рівняння вищих порядків, методи вирішення Завдання Коші Лінійні диференціальні рівняння вищих порядків Однорідні лінійні рівняння Диференціальні рівняння вищих порядків,

КАЗАНСЬКИЙ ФЕДЕРАЛЬНИЙ УНІВЕРСИТЕТ ІНСТИТУТ МАТЕМАТИКИ ТА МЕХАНІКИ ІМ. Н.І.ЛОБАЧЕВСЬКОГО Кафедра теорії та технологій викладання математики та інформатики Фалілєєва М.В. Перші кроки у вирішенні рівнянь та

Вісник КДУ ім НА Некрасова 6 Скибицький ЕГ Шкабура ОВ Стиль мислення як стратегія розв'язання задач з використанням комп'ютера // Інформатика та освіта З 7 Яковлєва ПЗ Теоретико-методологічні засади

УДК 373:512 ББК 22.14я721 М52 М52 Мерзляк, А.Г. Математика: Новий повний довідникдля підготовки до ОДЕ/А.Г. Мерзляк, В.Б. Полонський, М.С. Якір. Москва: АСТ, 2017. 447, с.: іл. ISBN 978-5-17-096816-9

Освітній програміна 2016-2017 навчальний рік(7-11 класи), затвердженої наказом МБОУ «Середня загальноосвітня школа 21» м. Калуги 145/01-08 від 26.08.2016 РОБОЧА ПРОГРАМА Предмета АЛГЕБРА

Тема 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,

Лекція ІНТЕГРУВАННЯ РАЦІОНАЛЬНИХ ДРОБІВ Раціональні дроби Інтегрування найпростіших раціональних дробів Розкладання раціонального дробу на найпростіші дроби Інтегрування раціональних дробів Раціональні

10 клас, базовий рівень Завдання 1 Варіант 0 (демонстраційний, з рішеннями) Заочна математична школа 009/010 навчальний рік 1 Подайте вираз у вигляді багаточлена стандартного виглядуі знайдіть його

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

Муніципальне казенне загальноосвітня установасередня загальноосвітня школа 3 міста Пудожа Розглянуто на засіданні МО математики та інформатики Протокол 1 від 29.08.2016 Керівник МО Купцова

57 Розглянемо інтегрування найпростішого раціонального дробу четвертого типу (M N) d () p q p Зробимо заміну змінної, поклавши d. де p q. Тоді Інтеграл M N d p p p q q a, M p N Mp q d M (p q) p

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

Лекції -6 Розділ Звичайні диференціальні рівняння Основні поняття Різні завдання техніки природознавства економіки призводять до вирішення рівнянь, в яких невідомою є функція однієї або

Заняття. Ступінь із довільним дійсним показником, її властивості. Ступінна функція, її властивості, графіки.. Згадати властивості ступеня з раціональним показником. a a a a a для натурального разів

Муніципальна бюджетна загальноосвітня установа середня загальноосвітня школа 4 м. Балтійська Робоча програма навчального предмета«Алгебра» 8 клас, базовий рівень Балтійськ 2017 1 1. Пояснювальна

ЕЛЕМЕНТИ ОПЕРАЦІЙНОГО ЗЛІЧЕННЯ ВИДАВНИЦТВО ТДТУ МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ ГОУ ВПО «Тамбівський державний технічний університет» ЕЛЕМЕНТИ ОПЕРАЦІЙНОГО

Розглянемо перший спосіб розв'язання СЛУ за правилом Крамера для системи трьох рівнянь із трьома невідомими: Відповідь розраховується за формулами Крамера: D, D1, D2, D3 це визначники третього

Алгебраїчні багаточлени. 1 Алгебраїчні багаточлени ступеня n над полем K Визначення 1.1 Багаточлен ступеня n, n N (0), від змінної z над числовим полем K називається вираз виду: fz = a n z n

Модуль Тема Функціональні послідовності та ряди Властивості рівномірної збіжності послідовностей та рядів Ступінні рядиЛекція Визначення функціональних послідовностей та рядів Рівномірно

ГАОУ ВПО ДАГЕСТАНСЬКИЙ ДЕРЖАВНИЙ ІНСТИТУТ НАРОДНОГО ГОСПОДАРСТВА Бабичева ТА Кафедра вищої математики НАВЧАЛЬНИЙ ПОСІБНИК З ДИСЦИПЛІНИ ДИФЕРЕНЦІЙНІ РІВНЯННЯ Махачкала УДК 5(5) Навчальний посібник

Теореми «піфагорових трійок» Мурсєєв Михайло Петрович Існує різні методивизначення варіантів « піфагорових трикутників» Іноді їх називають «піфагорові трійки» або «єгипетські трикутники».

1. Вимоги до рівня підготовки учнів. Учень, який закінчує 9 клас, має вміти: виконувати арифметичні дії, поєднуючи усні та письмові прийоми; знаходити значення кореня натурального ступеня,

Федеральне агентство з освіти Томський державний університет систем управління та радіоелектроніки Кафедра вищої математики (ВМ) Приходовський М.А. ЛІНІЙНІ ОПЕРАТОРИ ТА КВАДРАТИЧНІ ФОРМИ

МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ НОВОСИБІРСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ СПЕЦІАЛІЗОВАНИЙ НАВЧАЛЬНО-НАУКОВИЙ ЦЕНТР Математика 9 клас СУМУВАННЯ

Міністерство освіти і науки Російської Федерації ФДБОУ ВО «Тверський державний університет» ЗАТВЕРДЖУЮ Керівник ООП Цвєтков ВП 2015г Робоча програма дисципліни (з інструкцією) Теорія чисел

ВИРОБНИЧА, ЇЇ ГЕОМЕТРИЧНИЙ І ФІЗИЧНИЙ ДУМКА Приростом функції = f() називається різниця f f, де - приріст аргументу З рис видно, що g () Рис Похідної функції = f() у точці називається кінцевий

Лекція 2. Властивості біноміальних коефіцієнтів. Підрахунок сум та метод виробляючих функцій (кінцевий випадок). Поліноміальні коефіцієнти. Оцінки біномних та поліноміальних коефіцієнтів. Оцінки сум

1. Пояснювальна записка. Робоча програма з предмету «Алгебра» для глухих учнів 8, 9, 10, 11 класів розроблена на основі програми загальноосвітніх закладів «Алгебра» 7-9 класи / автори

ББК 74.262.21 Б94 Б94 Буцко О.В. Алгебра: 7 клас: методичний посібник/Є.В. Буцько, О.Г. Мерзляк, В.Б. Полонський та ін. М.: Вентана-Граф, 2017. 104 с. : іл. ISBN 978-5-360-08673-4 Посібник містить

Анотація до робочої програми з алгебри Клас: 7 Рівень вивчення навчального матеріалу: базовий УМК, підручник Робоча програма з алгебри для 7 класу складена на основі програми «Алгебра» (Ю.М. Макарічев,

I варіант 8В клас, 4 жовтня 007 1 Вставте пропущені слова: Визначення 1 Арифметичним квадратним коренемчисло, якого дорівнює a з числа a (a 0) позначається так: виразом Дія знаходження

Міністерство освіти і науки Російської Федерації Федеральне агентство з освіти Пензенський державний університет Руденко АК, Руденко МН, Семерич ЮС ЗБІРНИК ЗАВДАННЯ З РІШЕННЯМИ ДЛЯ ПІДГОТОВКИ

ББК.4я7т+.4я7.6 М5 Підручник включено до федерального списку Мерзляк А.Г. М5 Алгебра: 9 клас: підручник для учнів загальноосвітніх організацій/ А.Г. Мерзляк, В.М. Поляків. М.: Вентана-Граф, 07. 368

Математичний аналізРозділ: диференціальні рівняння Тема: Лінійні однорідні системи дистанційного керування з постійними коефіцієнтами Лектор Пахомова ЕГ 0 г 4 Системи лінійних однорідних диференціальних рівнянь

Í. Â. Áîãîìîëîâ ÌÀÒÅÌÀÒÈÊÀ ÇÀÄÀ È Ñ ÐÅØÅÍÈßÌÈ àñòü 1 УЧЕБНОЕ ПОСОБИЕ ДЛЯ СПО 2-е издание, исправленное и дополненное Ðåêîìåíäîâàíî Ó åáíî-ìåòîäè åñêèì îòäåëîì ñðåäíåãî ïðîôåññèîíàëüíîãî îáðàçîâàíèÿ â êà

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

Розділ 2 Теорія меж Тема Числові послідовностіВизначення числової послідовності 2 Обмежені та необмежені послідовності 3 Монотонні послідовності 4 Нескінченно малі та

Московський державний технічний університет імені Н.Е. Баумана Факультет « Фундаментальні науки" Кафедра " Математичне моделювання» À.Í. Êàíàòíèêîâ,

Ірраціональні рівняння та нерівності Зміст Ірраціональні рівняння Метод зведення обох частин рівняння в один і той же ступінь Завдання Завдання Завдання Заміна ірраціонального рівняннязмішаної

Про одне узагальнення чисел Стірлінга Устинов А. В. Мого вчителя, М. М. Коробову, до його 85 річчя У роботі вводяться узагальнені числа Стірлінга. Для них доводяться властивості, аналогічні властивостям звичайних.

А. Н. РУРУКІН ПОВРОЧНІ РОЗРОБКИ З АЛГЕБРІ до підручника Ю.М. Макарічева та ін. (М.: Просвітництво) НОВЕ ВИДАННЯ 8 клас МОСКВА «ВАКО» 015 УДК 7:167.1:51 ББК 74.6.1 Р87 Р87 Рурукін О.М. Поурочні розробки

Математичний аналіз Розділ: Невизначений інтегралТема: Інтегрування раціональних дробів Лектор Пахомова Є.Г. 0 р. 5. Інтегрування раціональних дробів ВИЗНАЧЕННЯ. Раціональним дробом називається

Пояснювальна записка Робоча програма навчального предмета Алгебра. 8-9 клас» складена на основі: 1. Федерального компонента державного стандартуосновного загального та середнього (повного) загальної освіти

Лекція Диференціальні рівняння -го порядку (ДК-) Загальний вигляддиференціального рівняння порядку n запишеться: (n) F, = 0 () Рівняння -го порядку (n =) набуде вигляду F(,) = 0 Подібні рівняння

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

МЕТОДИЧНІ ВКАЗІВКИ ДО РОЗРАХУНКОВИХ ЗАВДАНЬ ПО КУРСУ ВИЩОЇ МАТЕМАТИКИ «ЗВИЧАЙНІ ДИФЕРЕНЦІЙНІ РІВНЯННЯ РЯДИ КРАТНІ ІНТЕГРАНІЇ РОЗДІЛІ ТЕМА ОБИКНІВ

Федеральне агентство з освіти Архангельський державний технічний університет будівельний факультет РЯДИ Методичні вказівки до виконання завдання для самостійної роботи Архангельськ

Муніципальна бюджетна загальноосвітня установа «Ліцей ім. академіка Б.М. Петрова» міста Смоленська «ПОГОДЖЕНО» Заступник директора Казанцева Т.В. «29» «08» 206 р. «Прийнято» педагогічною радою

9., 9. клас Модуль 5 «Послідовності. Ступені та коріння» У тесті перевіряються теоретична та практична частини. Послідовності Числові послідовності. Способи завдання числових послідовностей.

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

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

Приклад 1¢.Послідовність a n=a 0 +nd a n=a n - 1 +d. Це – формула загального члена арифметичної прогресії з різницею dі з початковим членом прогресії a 0 .

Приклад 2¢.Послідовність b n=b 0 × q nє загальним рішенням співвідношення b n=b n - 1 ×q. Це формула загального члена геометричної прогресії зі знаменником q¹0 і з початковим членом прогресії b 0 .

Приклад 3¢.Так звана формула Біне j n=є приватним рішенням співвідношення j n=j n- 2 +j n- 1 за j 0 =j 1 =1.

3. Лінійні рекурентні співвідношення.Співвідношення виду

a n + k+p 1 a n + k - 1 +…+p k a n=h(n) (2)

де h(n) - функція від числа, а , називається лінійним рекурентним співвідношенням.

Лінійне рекурентне співвідношення називають однорідним, якщо f(n)=0:

a n + k+p 1 a n + k - 1 +…+p k a n=0. (3)

Багаточлен x k+p 1 x k - 1 +…+p k - 1 x+p kназивається характеристичнимдля співвідношення (2).

простимякщо ділиться на , але не ділиться на .

Корінь a багаточлена називається кратним, якщо ділиться на , але не ділиться на .

При цьому число називається кратністюкореня.

Основна теорема алгебри: багаточлен ступеня з комплексними коефіцієнтами має комплексне коріння з урахуванням їх кратності.

Теорема 1 n простих коренів a 1 , …, a n

, (4)

де c 1 ,…,c kÎ C.

Доведення. Легко перевірити такі два твердження.

(a) Послідовність cx n, де cÎ Cє рішенням рекурентного співвідношення (3).

(b) Якщо послідовності a nі b nє рішеннями співвідношення (3), то послідовність a n+b nтакож є рішенням співвідношення (3).

З ( a) та ( b) Випливає, що будь-яка послідовність виду (4) є рішенням співвідношення (3).

Назад, будь-яке рішення співвідношення (3) має вигляд (4).

При n=0,1,…,k-1, з рівності (4) ми отримаємо систему лінійних рівнянь щодо c 1 ,…,c k:

(5)

Визначник системи (5) є відомий в алгебрі визначник Вандермонда:

Оскільки просте коріння x 1 ,…,x kпопарно різні, то D10. Отже, система (5) має (єдине) рішення.

Завдання 1.Знайти спільний член геометричної прогресії за формулою (4).

Рішення b n=qb n- 1 має вигляд. Тому.

Завдання 2.Знайти загальне рішення співвідношення Фібоначчі a n + 2 =a n+a n + 1 .

Рішення. Характеристичний багаточлен рекурентного співвідношення a n + 2 =a n+a n+ 1 має вигляд. Тому .

Наведемо без підтвердження наступне узагальнення теореми 1.

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

Завдання 3.Знайти загальне рішення співвідношення.

Рішення.Характеристичний багаточлен має корінь 2 кратності 3. Тому .

Зауваження. Загальне рішення неоднорідного лінійного співвідношення (2) можна визначити як суму загального рішення однорідного лінійного співвідношення (3) і окремого рішення неоднорідного лінійного співвідношення (2).

4. Виробляючі функції.Формальний ряд a 0 +a 1 x+a 2 x 2 +…+a k x k+ ... називається виконує функцією послідовності a 0 ,a 1 ,a 2 ,…,a k,…

Функція, що виробляє, є або схожим рядом, або розбіжним рядом. Два розбіжних ряду можуть дорівнювати як функції, але бути функціями різних послідовностей. Наприклад, ряди 1+2 x+2 2 x 2 +…+2k x k+… та 1+3 x+3 2 x 2 +…+3k x k+… визначають ту саму функцію (рівну 1 у точці x=1, невизначену в точках x>1), але є функціями різних послідовностей.

Властивості послідовностей, що виробляють функцій:

сума (різниця) функцій послідовностей, що виробляють a nі b nдорівнює виконує функції сумі (різниці) послідовностей a n+b n;

добуток функцій послідовностей, що виробляють a nі b nє функцією, що виробляє згортки послідовностей a nі b n:

c n=a 0 b n+a 1 b n - 1 +…+a n - 1 b 1 +a n b 0 .

приклад 1.Функція є виробляє для послідовності

приклад 2.Функція є виробляє для послідовності 1, 1, 1, …

Транскрипт

1 РІШЕННЯ РЕКУРРЕНТНИХ РІВНЯНЬ Позначимо через значення деякого виразу при підстановці в нього цілого числа Тоді залежність члена послідовності від членів послідовності F F зі значеннями аргументу меншими називається рекурентним рівнянням Прикладом може служити вирівнювання членів F F Таким чином рівняння має порядок а рівняння F 3 6 має порядок 3 Якщо встановлено рекурентне рівняння -го порядку то йому задовольняє нескінченно багато послідовностей Але якщо перші елементів задані то всі інші визначаються однозначно А саме елемент виражається через елемент F через елементи F і тд Алгоритм Рішення рекурентного рівняння наведено на Рис. початковими членамиі заданим рівняннямми обчислюємо черговий член послідовності Діючи таким чином ми рано чи пізно отримаємо будь-який член послідовності Однак при цьому нам доведеться обчислювати і всі попередні члени. У багатьох випадках зручніше мати явну формулу для -го члена послідовності. її в рівняння останнє звертається в тотожність Наприклад послідовність 4 8 є одним з рішень рекурентного рівняння 3 Дійсно загальний член цієї послідовності має вигляд Але при будь-якому має місце тотожність Значить 3 Таким чином є рішенням рекурентного рівняння Рішення рекурентного рівняння називається загальним якщо воно залежить від C C та шляхом підбору цих постійних можна отримати будь-яке рішення даного рівнянняНаприклад для рівняння 5 6 загальним рішенням буде F C C 3 3 Легко перевірити що послідовність 3 звертає в тотожність Тому достатньо показати що будь-яке рішення можна подати у вигляді 3 Але будь-яке

2 рішення однозначно визначається значеннями і Тому треба показати що для будь-яких чисел і знайдуться такі і що F C C 3C C 3 C Визначник системи дорівнює При будь-яких і система має рішення Тому 3 дійсно є рішенням F; F; I: FFF; FF; FF; F Рис Алгоритм формування послідовності чисел Фібоначчі

3 ЛІНІЙНІ РЕКУРРЕНТНІ РІВНЯННЯ Для вирішення довільних рекурентних рівнянь загальних правилне існує Проте є клас рівнянь, що дуже часто зустрічається, розв'язуваний одноманітним методом Це рекурентні рівняння виду f 4 де постійні коефіцієнтиа f - деяка функція Такі рівняння називаються лінійними тому що елементи послідовності F пов'язані лінійною залежністюЯкщо при цьому функція f то рівняння такого виду називаються однорідними або однорідними рівняннями з постійними коефіцієнтами В іншому випадку рівняння називаються неоднорідними Рівняння Таке рішення називається тривіальним рішенням Спочатку розглянемо як вирішуються такі рівняння при вивчимо рівняння виду F 6 Рішення цих рівнянь ґрунтується на наступних двох твердженнях: Якщо F і F є рішеннями рекурентного рівняння 6 то при будь-яких числах A і B послідовність F AF є рішенням цього рівняння Дійсно за умовою F F F F Помножимо ці рівності на тотожності У результаті отримаємо: A і F F B відповідно і складемо отримані [ AF BF ] [ AF BF ] AF BF А це означає, що F AF BF є рішенням рівняння 6 Якщо число є ється коренем рівняння

4 то послідовність є рішенням рекурентного рівняння F Доведемо це твердження Нехай то і Підставляючи ці значення в 6 отримуємо рівність або Воно справедливо так як за умовою При маємо тривіальне рішення будь-яка послідовність виду де Зауважимо що поряд з послідовністю ( ) також є рішенням рівняння 6 Для доказу цього факту досить використовувати твердження поклавши в ньому A B З тверджень і випливає наступне правило рішення лінійних однорідних рекурентних рівнянь другого порядку Нехай дано рекурентне рівняння 6 F Складемо квадратне рівняння 7 яке називається характеристичним рівнянням даного рекурентного рівняння рівняння 6 має вигляд C C Доведемо це твердження Зауважимо спочатку що згідно з затвердженням послідовності і є рішеннями даного рекурентного F F рівняння А тоді затвердженням і C C є його рішенням Треба тільки показати що будь-яке вирішено ие рівняння 6 можна записати в цьому виді Але будь-яке рішення рівняння другого порядку визначається значеннями і Тому достатньо показати що система рівнянь C C C C має рішення за будь-яких і Очевидно що цими рішеннями є При C F C система завжди має рішення Розглянемо приклад Як уже було сказано послідовність чисел Фібоначчі 3583 можна отримати за допомогою рекурентного рівняння F 8 Для нього характеристичне рівняння має вигляд Корінням цього квадратного рівняння є числа

5 5 5 і Тому загальне рішення рівняння Фібоначчі має вигляд 5 5 C C 9 Початковими умовами є значення F F Відповідно до цих початкових умов отримуємо для і C систему рівнянь C C C 5 C C Вирішуючи цю систему рівнянь знаходимо що C C і тому F 5 Таким чином цей вираз при всіх натуральних значеннях приймає цілі значення ВИПАДКУ РІВНИХ КОРНІВ ХАРАКТЕРИСТИЧНОГО РІВНЯННЯ Розглянемо випадок коли коріння характеристичного рівняння збігаються: У цьому випадку вираз CC вже не буде загальним рішенням Адже через те, що це рішення можна записати у вигляді CC C і вибрати її так щоб рівняння задовольняло двом початковим умовам і взагалі кажучи неможливо Отже необхідно знайти якесь інше рішення відмінне від Таким рішенням є Якщо квадратне F рівняння має два збігаються кореня то за теоремою Вієта а Тому рівняння записується наступним чином: А тоді рекурентне рівняння ення має вигляд Перевіримо, що F тотожність F F дійсно є його рішенням Підставляючи значення F в рівняння отримаємо очевидне Значить - це рішення нашого рекурентного рівняння Таким чином нам відомо вже два рішення даного рекурентного рівняння: і Тоді загальне рішення можна записати наступним чином: F F C C C C Тепер коефіцієнти Cі C можна підібрати так щоб виконувались будь-які дві початкові умови для F

6 C C C C Лінійні рекурентні рівняння порядок яких більше двох вирішуються таким же способом Нехай рівняння має вигляд F Складемо характеристичне рівняння Якщо всі коріння цього рівня алгебри різного то загальне рішення рівняння має вигляд F C C C Якщо ж наприклад то цьому кореню відповідають рішення F F F рівняння У загальному рішенні цьому кореню відповідає частина C C C Складаючи такі вирази для всіх коренів і складаючи їх отримуємо загальне рішення рівняння s P де - кратність кореня s - число різних коренів P - поліном ступеня щодо Приклад Розглянемо рівняння F 4 Складемо характеристичне рівняння Загальне рішення рекурентного рівняння має вигляд C C C C Складаємо систему рівнянь для знаходження та C: C C C C 4 Вирішуючи систему отримуємо що C і C Таким чином рішення рекурентного рівняння має вигляд

7 ПОШУК КОРНІВ МНОГОЧЛЕНА При відшуканні коренів характеристичного рівняння досить часто доводиться вирішувати рівняння ступеня більше Для вирішення цього завдання можна використовувати метод підбору ті брати навмання число і перевіряти чи є воно коренем даного многочлена При цьому можна досить швидко натрапити на корінь а можна і ніколи його не адже перевірити всі числа неможливо так як їх нескінченно багато Інша справа якщо б нам вдалося звузити область пошуку наприклад знати що шукані корені знаходяться наприклад серед тридцяти вказаних чисел А для тридцяти чисел можна зробити перевірку А у зв'язку з цим важливим є твердження Теорема Якщо нескоротний дріб / цілі числа є коренем багаточлена F x з цілими коефіцієнтами то старший коефіцієнт цього многочлена ділиться на а вільний член насправді якщо x x x x де - цілі числа і / є його коренем то F / ті / / / Помножимо обидві частини рівності на отримаємо Звідси Очевидно, що ціле число ділиться на Але / - нескоротний дріб ті числа і взаємно прості тоді як відомо з теорії ділимості цілих чисел числа і теж взаємно прості Отже ділиться на і взаємно просто з значить ділиться на Аналогічно доводиться що ділиться на цілими коефіцієнтами Продемонструємо це на конкретному прикладіЗнайдемо раціональне коріння багаточлена 4 3 F x 6x 3x 4x 8x 8 Згідно з доведеною теоремою раціональне коріння цього багаточлена знаходиться серед нескоротних дробів виду / де - дільник вільного члена 8 а - дільник старшого коефіцієнта 6 4 При цьому якщо дріб негативний то знак - відноситимемо до її чисельнику Наприклад Значить можна сказати, що дільник числа 8 а - позитивний дільник числа 6 Так як дільники числа 8 це ± 48 а позитивними дільниками числа 6 будуть 36 то раціональні коріння розглянутого багаточлена знаходяться серед чисел ± / / 3/ 6 / 344 / 388/ 3 Нагадаємо, що ми виписали тільки нескоротні дроби. Таким чином ми маємо двадцять чисел-«кандидатів» у корені.

8 Теорема Якщо нескоротний дріб / є коренем багаточлена F x з цілими коефіцієнтами, то F ділиться на для будь-якого цілого числа за умови, що Для доказу цієї теореми розділимо F x на x з залишком. є і s x а - ціле число Нехай s x b x b x b x b Тоді x x b x b x b x b Покладемо в цій рівності x / Враховуючи що F / отримуємо / b b b b Помножимо обидві частини останньої рівності на: b b b b Звідси випливає що ціле число ділиться на Але так як і взаємно прості те і теж а значить F ділиться на Теорема доведена Повернімося тепер до нашого прикладу і скориставшись даною теоремою ще більше звузимо коло пошуку раціональних коренів Застосуємо теорему для значень і ті якщо нескоротний дріб є коренем многочлена x то ділиться на а F ділиться на Очевидно що в нашому випадку F 5 а 5 Зауважимо що заразом ми виключили з розгляду одиницю Отже раціональні коріння нашого багаточлена слід шукати ді чисел // 3 / 6 // 3 8 8/3 Розглянемо // Тоді і F 5 ділиться на це число Далі 3 і 5 також ділиться на 3 Значить дріб / залишається в числі кандидатів у корені Нехай тепер // У цьому випадку 3 і F 5 не ділиться на -3 Значить дріб / не може бути коренем даного багаточлена Виконавши перевірку для кожного з виписаних вище дробів отримаємо що коріння знаходяться серед чисел // 3 4 Таким чином за допомогою досить простого прийомувдалося значно звузити область пошуку раціональних коренів розглянутого багаточлена Перевіривши 4 3 кандидати, що залишилися, переконаємося що багаточлен x 6x 3x 4x 8x 8 має два раціональні корені / і / 3 Описаний вище метод дозволяє знаходити лише раціональні корені багаточлена з цілими коефіцієнтами ірраціональне корінняТак наприклад розглянутий у прикладі багаточлен має ще два корені: ± 5 це коріння багаточлена x x 4 Зауважимо що при випробуванні кандидатів у корені за допомогою останньої теореми зазвичай розглядають випадок ± Іншими словами якщо / - кандидат у корені то перевіряють чи діляться і F на і відповідно Але може статися так що наприклад ті одиниця - корінь а тоді ділиться на будь-яке число і наша перевірка втрачає сенс. У цьому випадку слід розділити x на x ті отримати x x s x і проводити випробування для многочлена sx знайдений

9 У деяких випадках коли характеристичне рівняння відноситься до рівнянь спеціального видуйого корені можуть бути знайдені за допомогою підстановки. До таких рівнянь відносяться наприклад симетричні і поворотні рівняння. - деякий коефіцієнт Розглянемо, наприклад, рішення симетричних і поворотних рівнянь четвертого ступеня. враховуючи що t x / x вираз 4 можна записати як t bt c 6 Розв'язавши рівняння 6 як звичайне квадратне рівняння отримаємо два корені t і t Тепер підставляючи по черзі коріння t і t в рівняння 5 отримаємо два квадратні рівняння усі чотири корені вихідного рівняння 3 Таким чином рішення симетричного рівняння четвертого ступеня зводи ся до рішення трьох квадратних рівняньАналогічно вирішуються і поворотні рівняння Якщо рівняння четвертого ступеня можна подати у вигляді 4 x 3 bx cx bx 8 то його рішення може бути отримане за допомогою підстановки t x / x 9 Так само як і в попередньому випадку знизимо ступінь рівняння поділивши обидві частини на x Для рівняння, що вийшло x bx c b / x / x скористаємося підстановкою 9 Тоді рівняння можна переписати у вигляді t bt c Так само як і в попередньому прикладі розв'яжемо рівняння і отримаємо два корені t і t Тепер підставляючи по черзі коріння t і t в рівняння 9 отримаємо два квадратні рівняння x tx x t x Розв'язавши систему рівнянь отримаємо чотири корені вихідного рівняння 8 Таким чином рішення зворотного рівняння четвертого ступеня також зводиться до розв'язання трьох квадратних рівнянь

10 РІШЕННЯ НЕОДНОРОДНИХ ЛІНІЙНИХ РЕКУРРЕНТНИХ РІВНЯНЬ Лінійне рекурентне рівняння називається неоднорідним якщо його можна представити в наступному вигляді: f 3 де f - деяка функція від Введемо однорідне лінійне рекурентне рівняння ОЛРУ відповідне неоднорідному лінійному рекурентному рівнянню НЛРУ 3 F 4 а його загальне рішення позначимо через FO За аналогією з методами рішення диференціальних рівнянь знайдено Назвемо це рішення приватним і позначимо його через Будемо шукати загальне рішення НЛРУ у вигляді суми F його приватного рішення та загального рішення відповідного йому ОЛРУ F 5 3 O Покажемо що 5 дійсно є рішенням НЛРУ 3 оскільки FO FO F O F F F F f де перше рівняння в системі є загальне рішення ОЛРУ а друге приватне рішення НЛРУ Нехай НЛРУ має вигляд тобто c - також ціле число Підставимо 7 в 6 c c c b b c 8 Константа буде т приватним рішенням рівняння 6 за умови нерівності нулю знаменника формули 8 Введемо характеристичний поліном для НЛРУ 6 Якщо h h то очевидно, що рівняння 6 має приватне рішення

11 b F h Позначимо формальну похідну характеристичного полінома Тоді h h через h 9 h 3 Нехай h але h Будемо шукати рішення 6 у вигляді F c 3 Підставляючи 3 в 6 маємо c c c c b c h h b h а h і b c h Отже якщо h то рівняння 6 має приватне рішення b F h Позначимо похідну h через h За визначенням будемо вважати h h З курсу алгебри відомо що якщо число α є -кратним коренем багаточлена h то h α Тепер приватне рішення 6 можна записати у вигляді b F 3 h де - кратність кореня характеристичного многочлена h Приклад Вирішити рівняння 5 при F 35 Складаємо ОЛРУ F Складаємо характеристичне рівняння h 3 Вирішуємо характеристичне рівняння 4 Записуємо загальне рішення ОЛРУ F C C C C 5 Знаходимо приватне рішення НЛРУ 5 F 5 h так як h 6 Записуємо загальне рішення НЛ коефіцієнти у рішенні НЛРУ

12 C C 5 C C 5 35 отримуємо C C 8 Записуємо рішення НЛРУ F 5 Отже ми отримали явну формулу для обчислення -го члена послідовності На закінчення обчислимо саму послідовність: Будемо шукати приватне рішення НЛРУ РІШЕННЯ НЛРУ ПРИ ФУНКЦІЇ-МНОГОЧЛЕ ступеня що і в правій частині F c 34 Підставляючи 34 в 33 отримаємо правило обчислення коефіцієнтів многочлена j c j b 35 j Прирівнюючи коефіцієнти в лівій і правій частині при членах, що містять отримуємо Інші коефіцієнти c c b b c при h h знаходяться аналогічно шляхом прирівнювання коефіцієнтів при в 35 h кратності то приватне рішення НЛРУ слід шукати у вигляді F c РІШЕННЯ НЛРУ ПРИ ФУНКЦІЇ-ЕКСПОНЕНТІ Будемо шукати приватне рішення НЛРУ F bα 37 у вигляді 36 Підставляючи 38 у 37 маємо Тобто F cα cα bα 38

13 bα F h α якщо α не є коренем характеристичного рівняння h Якщо ж α є коренем характеристичного рівняння кратності, то приватне рішення 37 слід шукати у вигляді F dα де d - деяка константа Приклад При вирішенні одного завдання теорії кодування встановлено рекурентну залежність числа множень M від числа ітерацій при побудові перевірочної матриці коду M M 4 3 при M 7 Запишемо ОЛРУ M M Тоді маємо характеристичне рівняння h та загальне рішення ОЛРУ M C Будемо шукати приватне рішення у вигляді M d e Підставляючи його у вихідне рівняння маємо e 4 3 Ліва частина рівняння не містить отже пропоноване приватне рішення визначено неправильно так як корінь характеристичного рівняння Тепер змінимо вид приватного рішення на M d e Підставляючи його у вихідне рівняння маємо e 3 d Таким чином M C 3 і враховуючи початкові умови C 3 Отже рішення вихідного рівняння M 3 3 РЕКУРРЕНТИ рівняння відмінні від лінійних рекурентних рівнянь з постійними коефіцієнтами немає загального методу решения Вони можуть вирішуватися наприклад методом спроб і помилок Розглянемо нелінійне рівняння F F b при F b 39 Обчислимо значення при підстановці в 39 деяких констант F b b b при; F F b b b при;

14 b b b F F при 3 Тепер можна припустити, що рішенням рівняння 39 є 4 og b F де Підставляючи 4 в 39 маємо og og og b b b b b F F og og j j b b Таким чином 4 дійсно є рішенням рівняння 39

Тема 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 запишеться: (n) F, = 0 () Рівняння -го порядку (n =) набуде вигляду F(,) = 0 Подібні рівняння

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

Заняття. Ступінь із довільним дійсним показником, її властивості. Ступінна функція, її властивості, графіки. Згадати властивості ступеня з раціональним показником. a a a a a для натурального разів

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

Тема 7 Ранг матриці Базисний мінорТеорема про ранг матриці та її наслідки Системи m лінійних рівнянь з невідомими Теорема Кронекера-КапелліФундаментальна система рішень однорідної системилінійних

ДОВІДНИК З МАТЕМАТИКИ 5 9 класи МОСКВА «ВАКО» 201 УДК 32.851 ББК 4.262.22 С4 6+ Видання допущено до використання у освітньому процесівиходячи з наказу Міністерства освіти і науки РФ

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

ПРИКЛАДНА АЛГЕБРА. Частина I: Кінцеві поля чи поля Галуа. II 1 / 78 Частина I Кінцеві поля чи поля Галуа. II ПРИКЛАДНА АЛГЕБРА. Частина I: Кінцеві поля чи поля Галуа. II 2 / 78 Поля відрахувань за модулем

ПРИКЛАДНА АЛГЕБРА. Частина І: Кінцеві поля (поля Галуа). II 1/78 Частина I Кінцеві поля (поля Галуа). II ПРИКЛАДНА АЛГЕБРА. Частина І: Кінцеві поля (поля Галуа). II 2 / 78 Поля відрахувань за модулем простого

Лекція 7 2 Рівняння Фредгольма 2го роду з виродженими ядрами Цей випадок відрізняється тим, що рішення інтегрального рівняння зводиться до лінійного рішення. алгебраїчної системиі може бути легко отримано

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

лекція. Елементи теорії багаточленів. Багаточлен (деякі відомості довідкового характеру) Функція виду: 1 P (x) a0x a1x... a 1x a = + + + + (1) де натуральне число a i (i = 01...) постійні коефіцієнти

Заняття 4 Інтегрування раціональних функцій (продовження) Раціональною функцією(або, по-простому, дробом) називається відношення двох багаточленів, тобто функція виду R() = f() g() = a 0 m + a m +...+

Міністерство освіти і науки Російської Федерації Санкт-Петербурзький державний архітектурно-будівельний університет

Федеральне агентство з освіти ГОУ ВПО «Уральський державний технічний університет УПІ» НМ Кравченко Диференціальні рівняння та лави Навчально-методичний посібник Науковий редактордоц, канд

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

I варіант 8В клас, 4 жовтня 007 1 Вставте пропущені слова: Визначення 1 Арифметичним квадратним коренем з числа, якого дорівнює a з числа a (a 0) позначається так: Виразом Дія знаходження

Теореми «піфагорових трійок» Існує різні методи визначення варіантів «піфагорових трикутників» Іноді їх називають «піфагорові трійки» або «єгипетські трикутники»

Тема Невизначений інтеграл Основні методи інтегрування Інтегрування частинами Нехай u і v дві функції, що диференціюються одного і того ж аргументу Відомо, що d(u v) udv vdu (77) Візьмемо від обох

Тема 4. Чисельне рішення нелінійних рівнянь -1- Тема 4. Чисельне рішення нелінійних рівнянь 4.0. Постановка задачі Завдання знаходження коріння нелінійного рівняннявиду y=f() часто зустрічається в наукових

Науково-дослідна робота Тема роботи «Розкладання багаточлена п'ятого ступеня на квадратичні множники за допомогою інтерполяційного багаточлена Лагранжа» Виконав: Шабуневич Едуард Олегович учень

~ ~ Диференціальні рівняння Загальні відомостідиференційних рівнянь Завдання на складання диференціальних рівнянь Визначення: диференціальним рівнянням називається таке рівняння, яке

Розділ Невизначений інтеграл Безпосереднє інтегруванняФункцію F() називають первісною для функції f(), якщо виконується рівність F"() f() Сукупність всіх первісних цієї функції f()

МІНІСТЕРСТВО НАУКИ ТА ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ РІЗАНСЬКА ДЕРЖАВНА РАДІОТЕХНІЧНА АКАДЕМІЯ ГС ЛУК'ЯНОВА АІНОВІКІВ РАЦІОНАЛЬНІ ТА ІРРАЦІОНАЛЬНІ

Лекція 9 Лінеаризація диференційних рівнянь Лінійні диференціальні рівняння вищих порядків Однорідні рівняннявластивості їх рішень Властивості рішень неоднорідних рівняньВизначення 9 Лінійним

Лекція 3 Екстремум функції кількох змінних Нехай функція кількох змінних u = f (x, x) визначена в області D, і точка x (x, x) = належить даній області Функція u = f (x, x) має

Розв'язання задач шостої студентської олімпіади з алгебри Завдання 1 Доведіть, що якщо всі елементи дійсної квадратної матриціпорядку більше двох відмінні від нуля, їх можна помножити на позитивні

Тема 1 Справжні числата дії над ними 4 години 11 Розвиток поняття про число 1 Спочатку під числами розуміли лише натуральні числа, яких достатньо для рахунку окремих предметівБезліч

95 Білінійні та квадратичні функціїБілінійна функція Визначення Білінійною функцією (білінійною формою) на лінійному просторі L називається функція від двох векторів з L лінійна по кожному зі своїх

Федеральна державна бюджетна освітня установа вищої професійної освіти «Новосибірський національний дослідницький державний університет» СИСТЕМИ ЛІНІЙНИХ ДИФЕРЕНЦІЙНИХ

ДОВІДНИК Деякі ознаки ділимості натуральних чисел Натуральні числа це числа, що використовуються для рахунку:, Натуральні числа утворюють безліч, зване безліччю натуральних чисел Безліч

1 УДК 517 96 1. Рішення рівняння Ріккаті та його застосування до лінійних рівнянь другого порядку Чочієв Тимофій Захарович, кандидат фізико-математичних наук, старший науковий співробітник Південний Математичний

Системи диференціальних рівнянь Введення Так само як і звичайні диференціальні рівняння системи диференціальних рівнянь застосовуються для опису багатьох процесів реальної дійсності

Московський державний технічний університет імені Н.Е. Баумана Факультет «Фундаментальні науки» Кафедра «Математичне моделювання» À.Í. Êàíàòíèêîâ,

Міністерство загальної та професійної освіти Російської Федерації РОСТІВСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ Є. Я. Файн МЕТОДИЧНИЙ ПОСІБНИК з курсу ЕЛЕМЕНТАРНА МАТЕМАТИКА для студентів першого курсу

ЛЕКЦІЯ 2 СИСТЕМИ ЛІНІЙНИХ РІВНЯНЬ ВИЗНАЧНИКИ МАЛИХ ПОРЯДКІВ 1 ЕКВІВАЛЕНТНІСТЬ ЛІНІЙНИХ СИСТЕМ Нехай нам дана ще одна лінійна систематого ж розміру a 11x 1 + a 12x 2 + + a 1nx n = b 1, a 21x 1

{ загальні поняття- теорема Коші - лінійний диференціальний оператор - основні теореми - лінійна незалежністьрішень - визначник Вронського - вронскіан однорідного лінійного диференціального рівняння

Математичний аналіз Розділ: Невизначений інтеграл Тема: Інтегрування раціональних дробів Лектор Пахомова Є.Г. 0 р. 5. Інтегрування раціональних дробів ВИЗНАЧЕННЯ. Раціональним дробом називається

Глава ДИФЕРЕНЦІАЛЬНІ РІВНЯННЯ Основні поняття та визначення Диференціальним рівнянням називається рівняння, що зв'язує незалежну змінну х шукану функцію (у f (х і похідні шуканої функції)

Метод поділу змінних (метод Фур'є) Загальні принципиМетод поділу змінних Для найпростішого рівняння з приватними похідними поділ змінних це пошуки рішень виду тільки від t. u (x, t

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

ПРО РІШЕННЯ У НАТУРАЛЬНИХ ЧИСЛАХ РІВНЯНЬ ВИДУ У діофантовому аналізі рівняння виду ставляться до важко розв'язних. В даний час невідомий загальний метод повного рішеннянавіть найпростіших рівнянь цього

Алгебра: 7 клас. Урок 2. Числові вирази. Вирази зі змінними Доброго дня, хлопці! Минулого уроку ми повторили теми, вивчені у 6 класі. Згадали, як виконувати дії зі звичайними та

РОЗДІЛ 2 ВЕКТОРНІ ПРОСТІР 9 Векторний простірнад полем 91 Аксіоматика Нехай задано поле P, елементи якого називатимемо скалярами і деяку множину V, елементи якого називатимемо

Ланцюгові дроби Кінцеві ланцюгові дроби Визначення Вираз виду a 0 + a + a + + a m де a 0 Z a a m N a m N/() називається ланцюговим дробом a m - довжиною ланцюгового дробу a 0 a a m називатимемо коефіцієнтами ланцюгового

Елементарна теорія похибок. Рішення СЛАУ. 4. Норми в кінцевомірних просторах... 4. Обумовленість СЛАУ............ 5.3 Ітераційні методирішення лінійних систем......................

Міністерство освіти і науки РФ Уральський державний економічний університетЮ. Б. Мельников Поле. Розширення полів Розділ електронного підручникадля супроводу лекції Вид. 4-те, испр. та дод.

Міністерство освіти і науки Російської Федерації НАЦІОНАЛЬНИЙ ДОСЛІДНИЙ МОСКІВСЬКИЙ ДЕРЖАВНИЙ БУДІВЕЛЬНИЙ УНІВЕРСИТЕТ Кафедра прикладної механіки та математики ЗВИЧАЙНІ ДИФЕРЕНЦІЙНІ

Розділ 7 Поняття про асимптотичні методи Лекція Регулярно та сингулярно обурені завдання При побудові математичних моделей фізичних об'єктів, що характеризуються різними масштабамипо простору,