Дополнительные вопросы алгебры. Рекуррентные последовательности icon

Дополнительные вопросы алгебры. Рекуррентные последовательности



НазваниеДополнительные вопросы алгебры. Рекуррентные последовательности
Дата конвертации09.10.2012
Размер0.6 Mb.
ТипУчебно-методическое пособие

Пензенский государственный педагогический

университет им. В. Г. Белинского


А. Я. Султанов

  1. Дополнительные вопросы алгебры.

  2. Рекуррентные последовательности

  3. Учебно-методическое пособие




  1. Пенза – 2011

  2. Печатается по решению редакционно-издательского совета Пензенского государственного педагогического университета имени В. Г. Белинского




  • УДК 512.8(075)




  1. Султанов А. Я. Дополнительные вопросы алгебры. Рекуррентные последовательности: Учебно-методическое пособие. – Пенза, 2011. – 48 с.




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

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


Научный редактор: кандидат физ.-мат. наук, доцент Монахова О. А.


Содержание


Введение…………………………….……………………………..…....………..4

  1. 1. Понятие рекуррентной последовательности…………..……….….…..…..5

  2. 2. Решение однородных рекуррентных уравнений.…………….…..….…...10

  3. 3. Решение линейных однородных рекуррентных уравнений в случае различных простых корней характеристического уравнения……………...……..12

  4. 4. Дифференциальные операторы специального типа в алгебре

многочленов ………………..…………………..……...…....…..……………….......15

  1. 5. Решение линейных однородных рекуррентных уравнений в случае различных кратных корней характеристического уравнения……………...……..19

  2. 6. Решение неоднородных рекуррентных уравнений…………………..…..23

  3. 7. Рекуррентные уравнения над полем действительных чисел……………30

  4. 8. Производящие функции рекуррентных последовательностей………….35

  5. 9. Многочлены, определяемые рекуррентными соотношениями…………41

Библиография…………………….……………………………..…....………..46


Введение


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

Настоящее учебно-методическое пособие имеет целью описать основные методы решения рекуррентных уравнений с постоянными коэффициентами над различными полями. В пособии рассмотрены примеры и приведены задачи для самостоятельного решения.


§1.
Понятие рекуррентной последовательности



Последовательностью элементов заданного множества называют закон, по которому каждому натуральному числу сопоставляется элемент множества . Например, на множестве натуральных чисел последовательность квадратов натуральных чисел задается простым правилом, каждому сопоставляется . Под натуральными числами мы будем понимать числа 0, 1, 2, 3, ….

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

Для членов последовательности , где можно составить следующее соотношение: . Отсюда следует, что для любого натурального числа . Увеличив в последнем равенстве на 1, получим . Тогда из двух последних равенств следует . Повторив эти рассуждения, мы придем еще к одному соотношению , у которого правая часть равна нулю. Таким образом, последовательность квадратов натуральных чисел удовлетворяет следующим соотношениям:

,

,

.

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

Введем в общем виде понятие рекуррентной последовательности и рекуррентного соотношения. При этом будем предполагать, что последовательности рассматриваются над некоторым полем .

Определение 1.1. Последовательность , , …, , … ( ) называется рекуррентной (возвратной) последовательностью порядка k, если ее члены при каждом удовлетворяют равенству (рекуррентному соотношению):

, (1.1)

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

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

Пусть – переменные, принимающие значение из поля .

Определение 1.2. Система равенств при фиксированном натуральном и произвольных

, (1.2)

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

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

Пусть ,  произвольная последовательность. В равенствах вместо переменных подставим члены этой последовательности с соответствующими номерами. Тогда получим систему

.

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

Основной задачей теории рекуррентных уравнений является задача отыскания всех его решений.

Если в уравнении (1.2) правая часть равна нулю, то уравнение называется однородным, в противном случае – неоднородным.

Определение 1.3. Многочлен

[x],

где – элементы поля , входящие в (1.2), называется характеристическим многочленом рекуррентного уравнения (1.2). Многочлен называется двойственным характеристическим многочленом.

Заметим, что и связаны между собой соотношением .

Задачи

  1. Установите, однородны или неоднородны арифметическая и геометрическая прогрессии. Каковы их порядки?

  2. Задача Фибоначчи.

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

  1. Определите порядок рекуррентности данных соотношений:

а)

б)

в)

  1. Найдите однородное рекуррентное соотношение второго порядка, задающее арифметическую прогрессию.

Решение. Рассмотрим арифметическую прогрессию , члены которой удовлетворяют соотношению:

,

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

.

Вычтем из получившегося соотношения исходное

,

Отсюда получим

.

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

  1. Составьте рекуррентное соотношение, определяющее последовательность кубов натуральных чисел.

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

  3. , , , .

  4. , , , .

  5. , .

  6. , .

  7. , , .

  8. .

  9. .

  10. .

  11. .

  12. .

  13. .

  14. .

  15. .

  16. , где .

  17. , где .


§2. Решение однородных рекуррентных уравнений


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

(2.1)

порядка k.

Отметим некоторые свойства решений рекуррентного уравнения (2.1).

Предложение 2.1. Последовательности и , являющиеся решениями уравнения (2.1) совпадают тогда и только тогда, когда совпадают первые k членов этих последовательностей.

Доказательство. Необходимость очевидна.

Докажем достаточность. Пусть , решения уравнения (2.1), и пусть для всех номеров i от 1 до k. Методом математической индукции докажем, что для всех . Для имеем

,

Предположим, что утверждение верно для . Докажем, что утверждение верно для :

.

Таким образом, .

Предложение 2.2. Множество всех решений рекуррентного уравнения (2.1) относительно операции сложения решений и операции умножения решений на скаляры из поля , образует векторное пространство.

Доказательство. Пусть , любые два решения уравнения (2.1), тогда для любых выполняются следующие равенства

,

.

Сложим эти равенства. Тогда получим:

.

для любого . Значит, последовательность с общим членом является решением уравнения (2.1).

Аналогично доказывается, что произведение произвольной последовательности, являющейся решением (2.1), на произвольный скаляр поля  является решением (2.1). Действительно, если  решение уравнения (2.1), то для всех истинны равенства:

.

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



для всех . Значит, последовательность является решением уравнения (2.1).

Таким образом, множество решений уравнения (2.1) замкнуто относительно операций сложения последовательностей и умножения последовательностей на скаляры поля . Отсюда следует справедливость утверждения.

Определение 2.1. Система последовательностей называется линейно независимой, если из равенств



при всех следует, что .


§3. Решение линейных однородных рекуррентных уравнений

в случае различных простых корней характеристического уравнения


Рассмотрим линейное рекуррентное уравнение порядка k с постоянными коэффициентами над полем .

, (3.1)

причем . Пусть – корень характеристического многочлена этого уравнения

.

Тогда

, (3.2)

при этом . Имеет место

Предложение 3.1. Если – корень характеристического многочлена , то последовательность является решением рекуррентного уравнения (3.1).

Доказательство. Подставим в уравнение (3.1). Тогда



для любых в силу (3.2). Предложение доказано.

В дальнейшем уравнение



будем называть характеристическим уравнением рекуррентного уравнения (3.1).

При решении характеристического уравнения может оказаться так, что число всех корней этого уравнения в поле  меньше, чем k, считая их кратности. Тогда уравнение (3.1) будем решать в поле разложения   над  характеристического многочлена . Здесь – различные корни многочлена .

Теорема 3.1. Пусть – попарно различные корни характеристического многочлена . Последовательность будет решением рекуррентного уравнения (3.1) тогда и только тогда, когда существуют скаляры    такие, что

. (3.3)

Доказательство. Необходимость. В силу предложения 3.1 и свойств решений однородного рекуррентного уравнения заключаем, что для любых скаляров из поля разложения над  многочлена последовательность , где определяется формулой (3.3), является решением уравнения (3.1).

Достаточность. Размерность пространства решений уравнения (3.1) равна . Поэтому достаточно доказать, что система решений

(3.4)

линейно независима.

Пусть при любом

,

а неизвестные принимают значения из поля разложения   . Тогда в силу произвольности , придав этой переменной значения 0, 1, 2, …, k–1, получим:

,

,

, (3.5)

,

Определителем этой системы является определитель Вандермонда:

,

В силу того, что при , заключаем, что . Отсюда следует, что система (3.5) имеет единственное нулевое решение. Значит, система решений (3.4) линейно независима и содержит ровно k решений. Таким образом, система (3.4) является базисом пространства решений линейного однородного уравнения (3.1).

Для любого решения найдутся скаляры (определенные однозначно) такие, что будет иметь место равенство (3.3).

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

Примеры. 1. Решить уравнение над полем рациональных чисел.

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

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

, .

2. Решить уравнение над полем .

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

,

будет являться решением данного рекуррентного уравнения.

3. Решить уравнение над полем 2= .

Характеристический многочлен неприводим над полем 2. Обозначим через один из корней многочлена . Тогда в поле 2( ) вторым корнем будет элемент . Действительно, . Таким образом, , и поэтому всякая последовательность , где

, 2( )

является решением уравнения (3.1).

Задачи

Решите следующие рекуррентные уравнения

  1. .

  2. .

  3. .

  4. .

  5. .

  6. .

  7. .


§4. Дифференциальные операторы специального типа

в алгебре многочленов


При решении рекуррентных уравнений полезным является дифференциальные операторы специального вида.

В алгебре многочленов определим операцию  по правилу

.

Операция -линейна. Действительно, для произвольных и , имеем

,

.

Кроме того, является дифференцированием алгебры многочленов  :



Предложение 4.1. Дифференцирование удовлетворяет равенствам:

(а)

(б)

Доказательство. (а). Так как , то . Отсюда следует (а).

(б). Из определения следует, что

.

Утверждение доказано.

Определим по индукции операции  :

,

.

Предложение 4.2. Имеет место тождество:

Доказательство проведем методом математической индукции по

1. При имеем

.

2. Пусть утверждение верно для фиксированного :

.

3. Проверим справедливость равенства для :

.

Утверждение доказано.

Предложение 4.3. -линейный оператор на  .

Доказательство проведем методом математической индукции.

1. При оператор – -линейный.

2. Пусть – -линейный оператор.

3. Докажем, что оператор -линейный. Для произвольных и   имеем:





Следствием предложений 4.1 – 4.3 является

Предложение 4.4. Для произвольного многочлена имеют место равенства:

(при ).

Предложение 4.5. Для произвольного натурального числа и произвольного многочлена выполняются равенства:



где некоторые элементы поля , а – произвольные многочлены .

Доказательство.

1. При равенство выполняется по определению оператора :

.

2. Предположим, что утверждение верно при , для произвольного фиксированного : где – некоторые скаляры из .

3. Докажем справедливость утверждения при . Из определения оператора и предложения 1 получим:





, .

Утверждение доказано.

Предложение 4.6. Пусть , . Если , то и .

Доказательство. 1. Проверим, что утверждение верно при . Пусть . Тогда и . То есть утверждение верно при .

2. Предположим, что утверждение верно при .

3. Докажем истинность утверждения при . Пусть для . В силу индуктивного предположения имеем и . Но , поэтому . На основании предложения 4.5 можно записать следующее равенство:

.

Отсюда следует, что . Предложение 4.6 доказано.

Предложение 4.7. Пусть  – поле нулевой характеристики. Следующие условия для  , логически эквивалентны:

(1) -кратный корень многочлена   ;

(2) и .

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

и .

Тогда . Из предложения 4.5 при получим:

и .

Истинность импликации доказана.

Пусть выполняется условие (2). Тогда из предложения 4.5 получаем, что

и .

Отсюда следует, что -кратный корень многочлена   . Истинность импликации доказана.


§5. Решение линейных однородных рекуррентных уравнений

в случае различных кратных корней характеристического уравнения


В этом параграфе будем исследовать решения линейного однородного уравнения (3.1) в случае, когда среди корней есть кратные корни. Будем считать, что характеристика поля  равна нулю.

Теорема 5.1. Если -кратный корень характеристического многочлена рекуррентного уравнения (3.1), то последовательность является решением уравнения (3.1).

Доказательство. При утверждение следует из предложения 3.1.

При запишем результат подстановки последовательности в левую часть уравнения (3.1):

. (5.0)

По формуле бинома Ньютона

,

при равенство (5.0) перепишем следующим образом:















.

Так как для , то полученное выражение тождественно равно нулю. Теорема 5.1 доказана.

Теорема 5.2. Пусть попарно различные корни характеристического многочлена рекуррентного уравнения (3.1) и пусть кратности этих корней равны , соответственно. Тогда система решений



линейно независима.

Доказательство. Составим линейную комбинацию этих решений и приравняем нулю. Тогда получим тождество относительно :

(5.1)



Придадим переменной значения 0, 1, 2, …, k–1. Тогда из тождества (5.1) получим систему:

(*),

Матрица этой системы будет следующей:



Докажем, что . Доказательство проведем от противного. Предположим, что . Тогда система строк этой матрицы линейно зависима. Значит, существуют скаляры , не равные нулю одновременно, такие, что

,

где – строки вещественной матрицы .

Значит,





(5.2)







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

Из равенства (5.2) следует аналогичные равенств для соответствующих координат векторов системы .

Выпишем равенства для блока, соответствующего корню





(5.3)



.

Рассмотрим многочлен

.

Равенства (5.3) в силу предложения 4.4 примут вид:



Отсюда замечаем, что кратность корня многочлена не меньше, чем : . Напомним, что -кратность корня характеристического многочлена.

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

Поэтому . С другой стороны, – степень характеристического многочлена.

Следовательно, число корней многочлена равно .

Степень многочлена не превосходит , поэтому имеет не более, чем корней. Это значит, . Отсюда . Получили противоречие. Следовательно, система строк имеет ранг, равный . Поэтому система (*) имеет единственное нулевое решение. Значит,

, .

Теорема доказана.

Из доказанных теоремы 5.1 и теоремы 5.2 следует

Теорема 5.3. Если различные корни характеристического многочлена однородного рекуррентного уравнения (3.1), кратности корней равны , соответственно, то каждое решение уравнения (3.1) можно представить в виде

,

где , – многочлен степени не больше, чем , коэффициенты которого однозначно определяется начальными условиями и принадлежат полю разложения характеристического многочлена над .

Замечание. Теорема 5.3 имеет место и в случае, когда поле  имеет конечную характеристику , при условии, что кратности корней характеристического уравнения меньше, чем .

Задачи

Решить следующие рекуррентные уравнения

  1. .

  2. .

  3. .

  4. .


§6. Решение неоднородных рекуррентных уравнений


1. Свойства решений неоднородных рекуррентных уравнений

Рассмотрим над полем  нулевой характеристики неоднородное рекуррентное уравнение.

, (6.1)

где некоторая функция натурального аргумента, со значениями в  и не равная нулю.

Определение 6.1. Всякое решение уравнения (6.1) называется неоднородной рекуррентной последовательностью порядка .

Наряду с уравнением (6.1) рассмотрим однородное рекуррентное уравнение

, (6.2)

которое называется соответствующим уравнению (6.1) однородным рекуррентным уравнением.

Отметим свойства решений уравнения (6.1).

Предложение 6.1. Разность любых двух частных решений рекуррентного уравнения (6.1) является решением однородного рекуррентного уравнения (6.2), соответствующего данному неоднородному уравнению.

Предложение 6.2. Если – решение однородного уравнения (6.2), – частное решение уравнения (6.1), то последовательность с общим членом вида является решением рекуррентного соотношения (6.1).

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

Предложение 6.3. Пусть правая часть уравнения (6.1) является суммой двух функций: . Тогда сумма решений уравнений вида (6.1) с правыми частями и является решением уравнения (6.1).

Доказательство. Предположим, что и – решения уравнений вида (6.1) с правыми частями и . Тогда равенства:

,



выполняются для всех . Сложив эти тождества, получим, что последовательность является решением уравнения (6.1).

Пример. Найти последовательность над полем , члены которой удовлетворяют соотношению и .

Решение. Составим однородное рекуррентное уравнение, соответствующее данному неоднородному соотношению, . Его характеристическое уравнение имеет вид: . Корнем этого уравнения является 3, его кратность равна 2. Общее решение однородного соотношения, соответствующее данному, запишется в виде: .

По виду правой части неоднородного уравнения частное решение исходного соотношения будем искать в виде многочлена нулевой степени: . Подставим частное решение в неоднородное соотношение и найдем .

Окончательно, общее решение данного неоднородного рекуррентного соотношения имеет вид: .

Для нахождения решения, удовлетворяющего начальным условиям, составим систему:

,



Решив ее относительно и , получим .

^ 2. Решение неоднородных рекуррентных уравнений путем сведения к однородным

Для нахождения решений уравнения (6.1) перепишем данное уравнение, заменив на

.

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

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

Решение. Запишем соотношение для номера Получим: Вычтем из получившегося соотношения исходное, получим однородное рекуррентное соотношение: Его общее решение:

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



После преобразования левой части, мы придем к равенству



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

^ 3. Решение неоднородных рекуррентных уравнений по виду правой части

В некоторых частных случаях частное решение можно найти по виду правой части уравнения (6.1).

3.1. Пусть правая часть является многочленом степени m над полем . Тогда, если 1 не является корнем характеристического уравнения, то частное решение будем искать, положив причем коэффициенты найдем, подставив в уравнение (6.1).

Если 1 является корнем характеристического многочлена и кратность равна s, то частное решение будем искать исходя из условия .

3.2. Предположим, что , , а – многочлен степени . Если не является корнем характеристического многочлена , то частное решение будем искать, положив, где – многочлен степени не выше, чем .

Если – корень кратности s характеристического многочлена , то частное решение будем искать в виде последовательности , где , где – многочлен над  степени не выше, чем .

3.3. К случаям 3.1 и 3.2 можно прийти на основании предложения 6.3.

Примеры.

1. Найдите общее решение уравнения

и , .

Решение. Составим однородное рекуррентное уравнение, соответствующее данному: Его характеристическое уравнение имеет корни , .

Общее решение однородного уравнения запишем в следующем виде: , где .

По виду правой части частное решение исходного уравнения будем искать в виде многочлена первой степени: так как 1 не является корнем характеристического уравнения.

Подставим частное решение в исходное уравнение и найдем и :



отсюда, в силу того, что это равенство должно выполняться при любом находим , .

Окончательно общее решение данного неоднородного уравнения имеет вид:



2. Найдите общее решение рекуррентного уравнения над полем :



Решение. Общим решением однородного уравнения, соответствующего данному,



является последовательность где поскольку корнями характеристического многочлена являются числа 1, 2, и 3.

Так как 1 является корнем кратности 1, то общий член частного решения будем искать в виде многочлена:

.

Тогда



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



Раскрыв скобки и сгруппировав подобные слагаемые, получим систему уравнений относительно коэффициентов , , .





Отсюда общее решение определяется условием:



3. Найти общее решение рекуррентного уравнения над полем :



Решение. Характеристический многочлен соответствующего однородного уравнения имеет вид Корнями этого многочлена являются числа 2 и –4, поэтому общее решение определяется условием



Составим два неоднородных рекуррентных уравнения

(*)

(**)

Поскольку 1 не является корнем характеристического уравнения , то частное решение уравнения (*) будем искать, исходя из условия Тогда, подставив в (*), получим

Отсюда найдем



Решив эту систему, получим . Значит, .

Число 2 является простым корнем характеристического многочлена , поэтому частное решение уравнения (**) будем искать, исходя из условия

Подставив в (**), получим

.

Отсюда, .

Тогда общее решение исходного уравнения будет иметь вид:

.

Задачи

Решить следующие линейные неоднородные рекуррентные уравнения

  1. .

  2. .

  3. .

  4. .

  5. .

  6. .


§ 7. Рекуррентные уравнения над полем действительных чисел


Поле действительных чисел имеет нулевую характеристику, поэтому все теоремы о линейных рекуррентных уравнениях и их решениях будут иметь место и для уравнений над полем действительных чисел. Любой многочлен из можно разложить на линейные множители над полем комплексных чисел. Это значит, что поле комплексных чисел является полем разложения любого многочлена с действительными коэффициентами. Следовательно, любое линейное рекуррентное уравнение с действительными коэффициентами имеет решение над полем комплексных чисел.

Как известно, если – комплексный корень многочлена с действительными коэффициентами, то сопряженное число также является корнем этого многочлена. Если имеет кратность , то также будет иметь кратность . На основании этих свойств можно по каждой паре комплексно-сопряженных корней построить линейно независимую систему из вещественных решений. Опишем процесс построения общего решения однородного линейного рекуррентного уравнения над полем действительных чисел в случае, когда среди корней характеристического уравнения есть мнимые корни.

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

, (7.1)

заданного над полем , имеет комплексные корни и вещественные корни , кратности которых соответственно. Тогда . По теореме 5.2 система решений

(7.2)

( ; ),

образует базис пространства решений рекуррентного уравнения (7.1) над полем . Используя конечную цепочку элементарных преобразований из системы (7.2) перейдем к следующей системе решений уравнения (7.1):



(6.3)

( ; ),

Система (7.3) –линейно независима, следовательно, она и – линейно независима.

Представим комплексные числа в тригонометрической форме: . Тогда и , , поэтому

.

Отсюда следует, что (7.3) представляет собой следующую –линейно независимую систему решений уравнения (7.1):



.

Число этих решений равно , поэтому они образуют базис пространства решений уравнения (7.1) над полем действительных чисел.

Общее решение уравнения (7.1) над полем действительных чисел является последовательностью, содержащей произвольные вещественные постоянные



и задается общим числом

.

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

,

где , , .

Пример. Решить над полем рекуррентное уравнение

.

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

.

Путем испытаний находим, что целые числа 0, 1, 2 не являются корнями характеристического уравнения. При помощи схемы Горнера устанавливаем, что –2 является корнем характеристического уравнения:

1–208–128–21–48–840Остальные корни характеристического уравнения являются корнями многочлена .

Так как , то остальные корни находим как корни уравнения .

Отсюда . Значит , – корни характеристического уравнения, кратности которых равны 2. – простой корень характеристического многочлена. Для нахождения вещественных решений рекуррентного уравнения корни и представляем в тригонометрической форме:

.

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

.

Общее решение представляет собой последовательность , где

.

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



над полем действительных чисел, и правая часть имеет вид

,

где и – многочлены над .

Как найти частное решение данного рекуррентного уравнения в этом случае?

Чтобы найти вещественное решение этого уравнения, составим комплексное число (по правой части уравнения):

.

Если число не является корнем характеристического многочлена , то частное решение будем искать в виде последовательности , где



где и – многочлены то , степени которых не превышают .

Если число является корнем характеристического многочлена и – кратность этого корня, то частное решение ищется в виде последовательности , где

,

где и – многочлены, удовлетворяющие условиям, приведенным выше.

Задачи

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

  1. .

  2. .

  3. .

  4. .

  5. .

  6. .

  7. .

  8. .

  9. .

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

  1. .

  2. .

  3. .

  4. .

  5. .

  6. .

  7. .

  8. .

  9. .

  10. .

  11. .

  12. .

Найти частное решение неоднородного уравнения, удовлетворяющее указанным начальным условиям

  1. , , .

  2. , , .

  3. , , .

  4. , , .


§ 8. Производящие функции рекуррентных последовательностей


^ 1. Алгебра формальных рядов

Определение 8.1. Формальным рядом назовем степенной ряд

,

где  элементы поля .

Два формальных ряда называются равными, если равны их коэффициенты при одинаковых степенях .

Сумма формальных рядов и определяется следующим образом: .

Операция умножения формального ряда на скаляр из поля  определяется соотношением: .

Введенные таким образом операции задают на множестве  формальных рядов структуру бесконечномерного векторного пространства.

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

.

Коэффициент при вычисляется по формуле:

.

Векторное пространство формальных степенных рядов с введенной операцией умножения рядов становится линейной алгеброй над полем , которая называется алгеброй формальных рядов. Заметим, что эта алгебра ассоциативна, коммутативна и обладает единицей. Единица имеет вид: , где 1  единица поля .

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

Предложение 8.1. Формальный ряд обратим тогда и только тогда, когда .

Доказательство. 1. Пусть – обратный ряд. Тогда существует , причем

. (8.1)

Левую часть можно представить в виде формального ряда , где

, (8.2)

причем при , , а .

При получаем

. (8.3)

Из равенства формальных рядов следует, что , поэтому . Следовательно, .

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

Предположим . Вычислим . По формуле (8.2) найдем :

.

Отсюда, учитывая, что , найдем :

.

Таким образом, формальный ряд , удовлетворяющий условию (8.1), существует.

^ 2. Определение производящей функции рекуррентной последовательности

Рассмотрим рекуррентную последовательность над полем , удовлетворяющую соотношению , . Первые членов последовательности будем считать фиксированными.

Определение 8.3. Формальный ряд называется производящей функцией рекуррентной последовательности .

Пример.  производящая функция последовательности чисел Фибоначчи.

^ 3. Нахождение производящей функции рекуррентной последовательности

Пусть – рекуррентная последовательность, удовлетворяющая соотношению



и пусть через производящая функция этой последовательности. Поставим задачу получения способа построения . Из определения производящей функции имеем

. (8.4)

Умножим равенство (8.4) последовательно на 1, , , …, , и затем полученные равенства сложим. Коэффициенты при имеют вид



поэтому все они равны нулю. Следовательно, после сложения рассматриваемых равенств, получим следующее равенство:

,

где – многочлен степени , коэффициенты которого вычисляются по формулам:

,

,

, (8.5)



.

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

.

Многочлен называется производящим многочленом рекуррентной последовательности. Полученный результат сформулируем в виде теоремы.

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

, (8.6)

где вычисляются по формулам (8.5).

Верно и обратное утверждение: если – многочлен степени , задается равенством , то формальный степенной ряд , задаваемый равенством (8.6), является производящей функцией некоторой однородной рекуррентной линейной последовательности, характеристический многочлен которой определяется условием .

Формулам (8.4) можно придать другой вид. Для этого введем матрицу

,

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

.

Пример. 1. Найдем производящую функцию для последовательности чисел Фибоначчи.

Члены последовательности Фибоначчи удовлетворяют соотношению .

Составим характеристический многочлен . Двойственным для него будет многочлен .

Коэффициенты многочлена найдем по формуле , где , .

.

Следовательно, . Получим производящую функцию :

_ 1 1  хх2

1  хх2 1 + х + 2х2 + 3х3 + …

_ х + х2

хх2х3

_2х2 + х3

2х2  2х3 2х4

_3х3 + 2х4

3х3  3х4 3х5

5х4 3х5



.

Задачи

1. Пусть ,  формальные ряды над полем . Найдите произведение этих рядов над данным полем.

2. Найдите ряд, обратный над полем .

3. Найдите производящую функцию рекуррентной последовательности, удовлетворяющей соотношению , , над полем .

4. Найдите производящую функцию для последовательности, удовлетворяющей рекуррентному соотношению , , , над полем . Определите период этой последовательности.

^ 5. Найдите производящую функцию для рекуррентной последовательности , , над полем .

Указание. Повысив порядок рекуррентности, перейдите к однородному соотношению.

^ 6. Найдите производящую функцию последовательности, удовлетворяющей соотношению , , , .

7. Найдите производящую функцию для рекуррентной последовательности , , над полем .

8. Докажите, что каждая линейная рекуррентная последовательность порядка k над полем  характеристики q является периодической. При этом ее минимальный период r (наименьший из всех возможных периодов) удовлетворяет условию:

а) , если последовательность неоднородная;

б) , если последовательность однородная.

9. Разложить в степенной ряд по возрастающим степеням дробь

.

10. Найти однородное линейное рекуррентное уравнение, которому удовлетворяют коэффициенты разложения дроби задачи 9.


§ 9. Многочлены, определяемые рекуррентными соотношениями


Рассмотрим последовательность многочленов над полем действительных чисел, которые удовлетворяют рекуррентному соотношению

, (9.1)

с начальными условиями , , где – вещественные функции натурального аргумента . Предположим, что и не обращаются в нуль при каждом значении аргумента .

Введем обозначения: , , .

Соотношению (9.1) поставим в соответствие матрицу (сопровождающую матрицу)



Построенная матрица называется матрицей Якоби.

Предложение 9.1. Корни многочлена являются собственными числами матрицы .

Доказательство. Пусть – корень многочлена . Тогда и . Подставим в (9.1), тогда

, (9.2)

где . Из (9.1) получим следующую систему линейных однородных соотношений



Так как , то определитель этой системы равен нулю: . Отсюда следует, что – собственное число матрицы .

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

К числу многочленов, определяемых соотношениями вида (8.1), относятся многочлены, возникающие в математической физике. Отметим некоторые из них.

9.1. Многочлены Лагерра .

Эти многочлены определяются рекуррентными соотношениями вида (9.1) при условиях

, , , .

, :

. (9.3)

9.2. Многочлены Лежандра .

Многочлены Лежандра определяются соотношениями

, , (9.4)

, .

Сопровождающая матрица рекуррентного соотношения (9.4) имеет вид

,

а ее определитель вычисляется по формуле

(9.5)

9.3. Многочлены Эрмита .

Многочлены Эрмита определяются соотношениями

, ,

, .

Эти соотношения получаются из (8.1) при , , , , .

Задачи

  1. Докажите следующие утверждения.

  2. Если , то все характеристические числа матрицы вещественны.

  3. Если , то все корни многочлена вещественны.

  4. Для того, чтобы все характеристические числа матрицы были вещественны необходимо и достаточно, чтобы для всех .

  5. Если , то:

  6. удовлетворяет уравнению .

  7. .

  8. .

  9. Пусть . Используя результаты задачи г), докажите, что произведение корней многочлена равно , при и равно нулю .

  10. Если при всех и , то характеристические числа матрицы (а значит, и все корни ) являются чисто мнимыми.

  11. Составить матрицу , соответствующую соотношению (9.3).

  12. Докажите, что все корни многочлена вещественны.

  13. Докажите, что все корни многочлена неотрицательны.

  14. Найдите сумму корней многочлена .

  15. Найдите рекуррентное соотношение, которому удовлетворяет определитель сопровождающей матрицы .

  16. Используя результаты задачи 6, найдите значение определителя сопровождающей матрицы .

  17. Найдите многочлены Лагерра , , .

  18. Докажите, что все корни многочлена Лежандра вещественны.

  19. Сумма корней многочлена Лежандра равны нулю.

  20. Докажите, что произведение корней многочлена Лежандра равны .

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

  22. Докажите равенство (8.5).

  23. Найдите многочлены Лежандра , , , .

  24. Составьте сопровождающую матрицу рекуррентного соотношения, определяющего многочлены Эрмита.

  25. Докажите, что все корни многочлена вещественны.

  26. Докажите, что сумма всех корней многочлена равны нулю.

  27. Найдите рекуррентное соотношение, которому удовлетворяет последовательность определителей сопровождающей матрицы

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


Библиография


  1. Гельфонд А. О. Исчисление конечных разностей.  М.: Наука, 1967, 375 с.

  2. Лидл Р., Нидеррайтер Г. Конечные поля. Т 2.  М.: Мир, 1988. 822 с.

  3. Маркушевич А. И. Возвратные последовательности.  М.: Наука, 1975. 47 с.

  4. Математическая энциклопедия. Т 4.  М.: Советская энциклопедия, 1984. С. 506  507.

  5. Моденов П. С. Сборник задач по специальному курсу элементарной математики. М.: Высшая школа, 1960. С. 120  128.



ДЛЯ ЗАМЕТОК

  1. Пензенский государственный педагогический университет

  2. имени В. Г. Белинского




Адгам Яхиевич Султанов

  1. Дополнительные вопросы алгебры.

  2. Рекуррентные последовательности

  3. Учебно-методическое пособие





Похожие:

Дополнительные вопросы алгебры. Рекуррентные последовательности iconВ. Г. Белинского Султанов А. Я. Дополнительные вопросы алгебры. Оператор конечной разности Учебно-методическое пособие
Султанов, А. Я. Дополнительные вопросы алгебры. Оператор конечной разности: Учебно-методическое пособие / А. Я. Султанов. Пенза,...
Дополнительные вопросы алгебры. Рекуррентные последовательности iconДополнительные вопросы на экзамене. Ответы на следующие вопросы можно найти, изучив полную версию лекций. Из лекции «Термодинамика»
Понятие «время» для характеристики процесса использует а термодинамика б кинетика ? Выберите правильный ответ
Дополнительные вопросы алгебры. Рекуррентные последовательности iconКритерии оценки достижений в области регулятивных ууд. Фамилия, имя учащегося
Планирование – определение последовательности промежуточных целей с учетом конечного результата; составление плана и последовательности...
Дополнительные вопросы алгебры. Рекуррентные последовательности iconОсобенность этих циклов заключается в том, что тело цикла с предсловием выполняет многократно одни и те же действия в зависимости от условия
Найти Сумму Последовательности Неравных Нулю Чисел, Завершающейся Нулем. Нуль Играет Роль Признака Конца Последовательности
Дополнительные вопросы алгебры. Рекуррентные последовательности iconПримерные задачи с решениями к районной олимпиаде по информатике. Задача 1 : Вводится натуральное число n и два вещественных числа А1 и найти значение n –ого элемента последовательности {Aк},
Ак равен среднему арифметическому всех предшествующих элементов последовательности с нечетными номерами. Оценка 20 баллов
Дополнительные вопросы алгебры. Рекуррентные последовательности iconЭкзаменационные вопросы по курсу математического анализа Существование точной верхней грани у ограниченного сверху множества. Первый замечательный предел. Определение суммы двух действительных чисел и свойства
Монотонные последовательности. Сходимость ограниченных монотонных последовательностей
Дополнительные вопросы алгебры. Рекуррентные последовательности iconМатематика
Примерная программа не задает последовательности изучения материала и распределения его по классам. Авторы рабочих программ и учебников...
Дополнительные вопросы алгебры. Рекуррентные последовательности iconМатематика Статус примерной учебной программы
Примерная программа не задает последовательности изучения материала и распределения его по классам. Авторы рабочих программ и учебников...
Дополнительные вопросы алгебры. Рекуррентные последовательности iconКомментарии к вопросам муниципального уровня 8 кл по географии
Большинство вопросов данного уровня рассчитано на умение учащихся интегрировать знания для определения природных объектов. Например,...
Дополнительные вопросы алгебры. Рекуррентные последовательности iconГаражные вопросы
Гаражный вопрос давно актуален не меньше квартирного. Однако наличие гаража это не только гарантия сохранности автомобиля, но и дополнительные...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib.podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов