Методы программирования и прикладные алгоритмы. Учебное пособие СанктПетербург 2007
 Скачать 2.32 Mb.
|
|
i = 1 n 3 = 13, n 2 = 4, n 1 = 1, n 0 = 0 (0,1,2,3,4) : (5,6,7,8,9) 0,10,11,12,13 i = 2 = (0,10) : (11,12) = 0,13 (0,10) : (11,12) = (0) : (13) = 0 13 Т 13 Л < > < ( 10) Л ( 11,12) Т ((11)Т) : ((12)Т) = 10 Л 12 Т 11 Т < > > ( 10) Т ( 11,12) Л ((11)Л) : ((12)Л) = 10 Т 11 Л 12 Л < > i = 3 (1,2,3,4) Л ( 5,6,7,8,9) Т < ((1)Л,(5,6)Т) : ((2)Л,(7,8)Т) ( 3,4) Л ( 9) Т 9 Т ((3)Л) : ((4)Л) 3 Л 4 Л = < > = ( 1) Л ( 7,8) Т < ((7)Т) : ((8)Т) 1 Л 8 Т 7 Т = < > ( 5,6) Т ( 2) Л > ((5)Т) : ((6)Т) 2 Л 6 Т 5 Т = < > (1,2,3,4) Т ( 5,6,7,8,9) Л < ((1)Т,(5,6)Л) : ((2)Т,(7,8)Л) ( 3,4) Т ( 9) Л 9 Л ((3)Т) : ((4)Т) 4 Т 3 Т = < > = ( 2) Т ( 5,6) Л < ((5)Л ) : ((6)Л) 2 Т 5 Л 6 Л = < > ( 7,8) Л ( 1) Т > ((7)Л) : ((8)Л) 1 Т 7 Л 8 Л = < > Рис. 3.5. Решение задачи о фальшивой монете для 27 монет при наличии эталонной 78 3.2. Решение рекуррентных уравнений Основные понятия В предыдущих главах рассматривались уравнения, решения- ми которых является не число, а последовательность и где очеред- ной элемент последовательности выражается аналитически через какое-то количество ее предыдущих элементов. Такие уравнения часто возникают при анализе сложности того или иного алгорит- ма и нужно уметь их решать, т.е. находить аналитическое выра- жение, позволяющее вычислить любой элемент последовательно- сти, не находя предыдущие. В этом подразделе рассмотрим неко- торые такие уравнения и методы их решения [7]. Определение 3.1 Рекуррентным уравнением называется зависимость, выража- ющая n-й элемент некоторой последовательности через элементы F (n − 1), F (n − 2), . . .. Рекуррентное уравнение имеет порядок k, если оно позволяет выразить член последовательности F (n + k) через F (n), F (n + 1), F (n + 2), . . ., F (n + k − 1). Если задано рекуррентное уравнение k-го порядка, то ему удовлетворяет бесконечно много последова- тельностей. Но если первые k элементов заданы, то все осталь- ные определяются однозначно — элемент F (k + 1) выражается через элементы F (1), . . . , F (k), элемент F (k + 2) — через элемен- ты F (2), . . . , F (k + 1) и т.д. Пример 3.1 Приведем несколько примеров рекуррентных уравнений. Так F (n + 2) = F (n)F (n + 1) − 3F 2 (n + 1) + 1 задает рекуррентное уравнение второго порядка, которому удо- влетворяет, например последовательность 1, 1, −1, −3, −23, −1517, −6868975, . . . , если положить начальные два члена равными F (1) = 1, F (2) = 1. 79 Уравнение F (n + 3) = 6F (n)F (n + 2) + F (n + 1) является рекуррентным уравнением третьего порядка, ему соот- ветствует последовательность 0, 2, 1, 2, 25, 152, 1849, . . . , если F (1) = 0, F (2) = 2, F (3) = 1. Пользуясь рекуррентным уравнением и начальными членами, можно один за другим выписывать члены последовательности, причем рано или поздно получим любой ее член. Однако при этом придется выписать и все предыдущие члены. Но во многих случа- ях удобнее иметь явную формулу для n-го члена последователь- ности. Определение 3.2 Некоторая последовательность является решением данного рекуррентного уравнения, если при подстановке этой последова- тельности уравнение обращается в тождество. Пример 3.2 Последовательность 2, 4, 8, . . . , 2 n , . . . является одним из решений рекуррентного уравнения F (n + 2) = 3F (n + 1) − 2F (n). В самом деле общий член этой последовательности имеет вид F (n) = 2 n . Значит, F (n + 2) = 2 n+2 , F (n + 1) = 2 n+1 . Но при любом n имеет место тождество 2 n+2 = 3 · 2 n+1 − 2 · 2 n . Поэтому 2 n является решением уравнения. Определение 3.3 Решение рекуррентного уравнения k-го порядка называется общим, если оно зависит от k произвольных постоянных C 1 , . . ., C k , и путем подбора этих постоянных можно получить любое ре- шение данного уравнения. 80 Пример 3.3 Для уравнения F (n + 2) = 5F (n + 1) − 6F (n) (3.4) общим решением будет F (n) = C 1 2 n + C 2 3 n (3.5) Легко проверить, что последовательность (3.5) обращает уравне- ние (3.4) в тождество. Действительно, 5F (n + 1) − 6F (n) = 5(C 1 2 n+1 + C 2 3 n+1 ) − 6(C 1 2 n + C 2 3 n ) = = 2C 1 2 n+1 + 3C 2 3 n+1 = = C 1 2 n+2 + C 2 3 n+2 = = F (n + 2). Поэтому достаточно показать, что любое решение уравнения (3.4) можно представить в виде (3.5). Но любое решение уравне- ния (3.4) однозначно определяется значениями F (1) и F (2). По- этому надо доказать, что для любых чисел a и b найдутся такие значения C 1 и C 2 , что 2C 1 + 3C 2 = a, 2 2 C 1 + 3 2 C 2 = b. (3.6) При любых значениях a и b система уравнений (3.6) имеет реше- ние. Поэтому (3.5) действительно является решением уравнения (3.4). Линейные однородные рекуррентные уравнения Для решения рекуррентных уравнений, вообще говоря, общих правил не существует. Однако есть весьма часто встречающийся класс уравнений, решаемый единообразным методом. Это — ре- куррентные уравнения, в которых элементы последовательности F (n), . . ., F (n + k − 1), F (n + k) связаны линейной зависимостью. 81 Определение 3.4 Рекуррентные уравнения вида F (n + k) = a k−1 F (n + k − 1)+ + a k−2 F (n + k − 2) + . . . + a 0 F (n) + f (n), (3.7) где a 0 , a 1 , . . ., a k−1 — некоторые числа (постоянные коэффициен- ты), а f (n) — некоторая функция от n, называются линейными. Если при этом функция f (n) = 0, то уравнения такого вида называются однородными, или однородными уравнениями с по- стоянными коэффициентами. Если же функция f (n) = 0, то со- ответствующие уравнения называются неоднородными. Определение 3.5 Линейные однородные рекуррентные уравнения с постоянны- ми коэффициентами имеют вид F (n+k) = a k−1 F (n+k −1)+a k−2 F (n+k −2)+. . .+a 0 F (n), (3.8) где a 0 , a 1 , . . ., a k−1 — некоторые числа. Очевидно, что последовательность 0, 0, 0, . . . всегда будет ре- шением любого однородного уравнения. Такое решение называет- ся тривиальным решением. Сначала рассмотрим, как решаются такие уравнения при k = 2, т.е. изучим уравнения вида F (n + 2) = a 1 F (n + 1) + a 0 F (n). (3.9) Решение этих уравнений основывается на следующих двух утвер- ждениях. Т е о р е м а 3.2 Если F 1 (n) и F 2 (n) являются решениями рекуррентного урав- нения (3.9), то их линейная комбинация также является реше- нием уравнения (3.9), т.е. при любых числах A и B последова- тельность F 3 (n) = AF 1 (n) + BF 2 (n) является решением этого уравнения. 82 Доказательство. Действительно, по условию F 1 (n + 2) = a 1 F 1 (n + 1) + a 0 F 1 (n), F 2 (n + 2) = a 1 F 2 (n + 1) + a 0 F 2 (n). Умножим эти равенства на A и B, соответственно, и сложим по- лученные тождества. В результате получим F 3 (n) = AF 1 (n + 2) + BF 2 (n + 2) = = a 1 [AF 1 (n + 1) + BF 2 (n + 1)] + a 0 [AF 1 (n) + BF 2 (n)]. А это и означает, что F 3 (n) является решением уравнения (3.9). Т е о р е м а 3.3 Если число r 1 является корнем уравнения r 2 = a 1 r + a 0 , то последовательность 1, r 1 , r 2 1 , . . . , r n 1 , . . . является решением рекуррентного уравнения F (n + 2) = a 1 F (n + 1) + a 0 F (n). Доказательство. Пусть F (n) = r n 1 , тогда имеем F (n + 1) = r n+1 1 и F (n+2) = r n+2 1 . Подставляя эти значения в (3.9), получаем равенство r n+2 1 = a 1 r n+1 1 + a 0 r n 1 или r n 1 (r 2 1 − (a 1 r 1 + a 0 )) = 0. Оно справедливо, так как по условию r 2 1 = a 1 r 1 + a 0 . При r 1 = 0 имеем тривиальное решение. Заметим, что наряду с последова- тельностью {r n 1 }, любая последовательность вида F (n) = r n+m 1 , где m = 1, 2, . . ., также является решением уравнения (3.9). Для доказательства достаточно использовать теорему 3.2, положив в ней A = r m 1 , B = 0. 83 Определение 3.6 Квадратное уравнение r 2 = a 1 t + a 0 (3.10) называется характеристическим уравнением рекуррентного урав- нения (3.9). Из теорем 3.2 и 3.3 вытекает следующее правило решения ли- нейных однородных рекуррентных уравнений второго порядка. Т е о р е м а 3.4 Пусть дано рекуррентное уравнение (3.9): F (n + 2) = a 1 F (n + 1) + a 0 F (n). Если соответствующее характеристическое уравнение имеет два различных корня r 1 и r 2 , то общее решение уравнения (3.9) име- ет вид F (n) = C 1 r n 1 + C 2 r n 2 Доказательство. Заметим сначала, что согласно теореме 3.3 последовательности F 1 (n) = r n 1 и F 2 (n) = r n 2 являются решени- ями данного рекуррентного уравнения. Тогда по теореме 3.2 и C 1 r n 1 + C 2 r n 2 является его решением. Надо только показать, что любое решение уравнения (3.9) можно записать в этом виде. Но любое решение уравнения второго порядка определяется значе- ниями F (0) и F (1). Поэтому достаточно показать, что система уравнений C 1 + C 2 = a, C 1 r 1 + C 2 r 2 = b (3.11) имеет решения при любых a и b. Очевидно, что этими решениями являются C 1 = b − ar 2 r 1 − r 2 , C 2 = ar 1 − b r 1 − r 2 84 Пример 3.4 (числа Фибоначчи) Известную последовательность чисел Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13, . . . можно получить с помощью рекуррентного уравнения F (n + 2) = F (n + 1) + F (n). (3.12) Для него характеристическое уравнение имеет вид r 2 = r + 1. Корнями этого квадратного уравнения являются числа r 1 = 1 + √ 5 2 , r 2 = 1 − √ 5 2 Поэтому общее решение уравнения Фибоначчи имеет вид F (n) = C 1 1 + √ 5 2 n + C 2 1 − √ 5 2 n (3.13) Начальными условиями являются значения F (0) = 0, F (1) = 1. В соответствии с этими начальными условиями получаем для C 1 и C 2 систему уравнений C 1 + C 2 = 0, √ 5 2 (C 1 − C 2 ) = 1. Решая эту систему уравнений, находим, что C 1 = −C 2 = 1 √ 5 , и потому F (n) = 1 √ 5 1 + √ 5 2 n − 1 − √ 5 2 n (3.14) Таким образом, это выражение при всех натуральных значе- ниях n принимает целые значения. Рассмотрим случай, когда корни характеристического уравне- ния совпадают: r 1 = r 2 . В этом случае выражение C 1 r n 1 +C 2 r n 2 уже 85 не будет являться общим решением. Ведь из-за того, что r 1 = r 2 , это решение можно записать в виде F (n) = (C 1 + C 2 )r n 1 = Cr n 1 В результате система (3.11) обращается в систему из двух уравне- ний с одним неизвестным. Если эта система окажется несовмест- ной, то выбрать константу C так, чтобы она удовлетворяла двум начальным условиям a и b, становится невозможно. Следовательно, необходимо найти какое-нибудь другое реше- ние, отличное от F 1 (n) = r n 1 . Таким решением является F 2 (n) = nr n 1 . В самом деле, если квадратное уравнение r 2 = a 1 r + a 0 имеет два совпадающих корня r 1 = r 2 , то по теореме Виета a 1 = 2r 1 , a 0 = −r 2 1 . Поэтому уравнение записывается следующим образом: r 2 = 2r 1 r − r 2 1 А тогда рекуррентное уравнение имеет вид F (n + 2) = 2r 1 F (n + 1) − r 2 1 F (n). (3.15) Проверим, что F 2 (n) = nr n 1 действительно является его решением. Подставляя значения F 2 (n + 2) = (n + 2)r n+2 1 и F 2 (n + 1) = (n + 1)r n+1 1 в уравнение (3.15), получим очевидное тождество (n + 2)r n+2 1 = 2r 1 (n + 1)r n+1 1 − r 2 1 nr n 1 Значит, nr n 1 — решение нашего рекуррентного уравнения. Таким образом, известно уже два решения данного рекуррент- ного уравнения: F 1 (n) = r n 1 и F 2 (n) = nr n 1 . Тогда общее решение можно записать следующим образом: F (n) = C 1 r n 1 + C 2 nr n 1 = r n 1 (C 1 + C 2 n). Теперь путем нахождения коэффициентов C 1 и C 2 можно най- ти решение при любых начальных условиях, пользуясь системой уравнений C 1 = a, C 2 = b r 1 − a. 86 Линейные рекуррентные уравнения, порядок которых больше двух, решаются таким же способом. Пусть уравнение имеет вид F (n+k) = a k−1 F (n+k−1)+a k−2 F (n+k−2)+. . .+a 0 F (n). (3.16) Составим характеристическое уравнение r k = a k−1 r k−1 + a k−2 r k−2 + . . . + a 0 Если все корни r 1 , . . . , r k этого алгебраического уравнения k-й сте- пени различны, то общее решение уравнения (3.16) имеет вид F (n) = C 1 r n 1 + C 2 r n 2 + . . . + C k r n k Если же, например r 1 = r 2 = . . . = r m , то этому корню соот- ветствуют решения F 1 (n) = r n 1 , F 2 (n) = nr n 1 , F 3 (n) = n 2 r n 1 , . . ., F m (n) = n m−1 r n 1 рекуррентного уравнения (3.16). В общем реше- нии этому корню соответствует часть r n 1 (C 1 + C 2 n + . . . + C m n m−1 ). Составляя такие выражения для всех корней и складывая их, по- лучаем общее решение уравнения (3.16) F (n) = r n i (C i1 + C i2 n + . . . + C im n m−1 ). Поиск корней характеристического многочлена При отыскании корней характеристического уравнения доволь- но часто приходится решать уравнения степени, большей 2. Для решения этой задачи можно использовать метод подбора, т.е. брать наугад число и проверять, является ли оно корнем данного мно- гочлена. При этом можно довольно быстро натолкнуться на ко- рень, а можно и никогда его не найти, так как вариантов выбора бесконечно много. Другое дело, если бы нам удалось сузить об- ласть поиска, например знать, что искомые корни находятся сре- ди тридцати указанных чисел, для которых можно сделать пря- мую проверку. В связи с этим важным представляется следующее утверждение. 87 Т е о р е м а 3.5 Если несократимая дробь l/m (l, m — целые числа) являет- ся корнем многочлена F (x) с целыми коэффициентами, то стар- ший коэффициент этого многочлена делится на m, а свободный член — на l. Доказательство. В самом деле, пусть F (x) = a n x n +a n−1 x n−1 + . . . + a 1 x + a 0 , a n = 0, где a n , a n−1 , . . ., a 1 , a 0 — целые числа и F (l/m) = 0, т.е. a n (l/m) n + a n−1 (l/m) n−1 + . . . + a 1 (l/m) + a 0 = 0. Умножим обе части этого равенства на m n . Получим a n l n + a n−1 l n−1 m + . . . + a 1 lm n−1 + a 0 m n = 0. Отсюда следует a n l n = m(−a n−1 l n−1 − . . . − a 1 lm n−2 + a 0 m n−1 ). Полученное выражение означает, что целое число a n l n делится на m. Но l/m — несократимая дробь, т.е. числа l и m взаимно про- сты, а тогда числа l n и m тоже взаимно просты, и следовательно, a n делится на m. Аналогично доказывается, что a 0 делится на l. Доказанная теорема позволяет значительно сузить область по- иска рациональных корней многочлена с целыми коэффициента- ми. Прежде чем рассмотреть пример, докажем еще два утвержде- ния. Л е м м а 3.1 Если a(x) — многочлен с целыми коэффициентами, и k — целое число, то при делении a(x) на многочлен x − k с остатком справедливо равенство a(x) = (x − k)b(x) + a(k), где b(x) — многочлен с целыми коэффициентами; a(k) — целое число. 88 Доказательство. Пусть многочлен a(x) имеет степень n. Оче- видно, при делении a(x) на (x − k) получим частное b(x) — много- член степени n−1, и остаток c(x) — многочлен степени 0. Другими словами, можно принять c(x) константой a(x) = (x − k)b(x) + C. (3.17) Пусть a(x) = a n x n + a n−1 x n−1 + a n−2 x n−2 + . . . + a 1 x + a 0 , b(x) = b n−1 x n−1 + b n−2 x n−2 + . . . + b 1 x + b 0 . Прямой проверкой можно убедиться, что при делении на (x − 1) многочлена a(x) b n−1 = a n , b n−2 = ka n + a n−1 , b n−3 = k 2 a n + ka n−1 + a n−2 , b i = n j=i+1 k j−i−1 a j , (3.18) b 0 = n j=1 k j−1 a j (3.19) Из (3.18) очевидно, что все b i являются целыми числами. Обо- значим произведение (x−k)b(x) через z(x) и пусть z 0 — свободный член многочлена z(x), z 0 = −kb 0 . Тогда, с учетом (3.19) C = a 0 − z 0 = a 0 + k n j=1 k j−1 a j = = a 0 + n j=1 k j a j = n j=0 k j a j = a(k), (3.20) что и требовалось доказать. Заметим, что утверждение (3.20) также легко можно получить из (3.17), приняв x = k. 89 Т е о р е м а 3.6 Если несократимая дробь l/m является корнем многочлена F (x) с целыми коэффициентами, то F (k) делится на l − km для любого целого числа k при условии, что l − km = 0. Доказательство. Для доказательства этой теоремы разделим F (x) на x − k с остатком. Из леммы 3.1 имеем F (x) = (x − k)b(x) + F (k), где b(x) — многочлен с целыми коэффициентами, а F (k) — целое число. Пусть b(x) = b n−1 x n−1 + b n−2 x n−2 + . . . + b 1 x + b 0 Тогда F (x) − F (k) = (x − k)(b n−1 x n−1 + b n−2 x n−2 + . . . + b 1 x + b 0 ). Положим в этом равенстве x = l/m. Учитывая, что F (l/m) = 0, получаем −F (k) = l m − k b n−1 l m n−1 + . . . + b 1 l m + b 0 Умножим обе части последнего равенства на m n −m n F (k) = (l−km)(b n−1 l n−1 +b n−2 l n−2 m+. . .+b 1 lm n−2 +b 0 m n−1 ). Отсюда следует, что целое число m n F (k) делится на l − km. Но так как l и m взаимно просты, то m n и l − km тоже взаимно просты, а значит F (k) делится на l − km. Теорема доказана. Пример 3.5 Найдем рациональные корни многочлена F (x) = 6x 4 + 13x 3 − 24x 2 − 8x + 8. Согласно теореме 3.5, рациональные корни этого многочлена находятся среди несократимых дробей вида l/m, где l — делитель свободного члена a 0 = 8, а m — делитель старшего коэффициен- та a 4 = 6. При этом если дробь l/m — отрицательная, то знак «−» будем относить к ее числителю. Например, − 1 3 = −1 3 . Значит, можно сказать, что l — делитель числа 8, а m — положительный делитель числа 6. Так как делители числа 8 — это 1, 2, 4, 8, а 90 положительными делителями числа 6 будут 1, 2, 3, 6, то раци- ональные корни рассматриваемого многочлена находятся среди чисел ±{1, 1/2, 1/3, 1/6, 2, 2/3, 4, 4/3, 8, 8/3}. Напомним, что выписали лишь несократимые дроби. Таким образом, имеем двадцать чисел-кандидатов в корни. Осталось только проверить каждое из них и отобрать те, кото- рые действительно являются корнями. Воспользовавшись теоре- мой 3.6, еще больше сузим круг поиска рациональных корней. Применим теорему для значений k = 1 и k = −1, т.е. если несо- кратимая дробь l/m является корнем многочлена F (x), то F (1) делится на (l − m), a F (−1) делится на (l + m). Очевидно, в на- шем случае F (1) = −5, а F (−1) = −15. Заметим, что заодно ис- ключили из рассмотрения 1. Итак, рациональные корни нашего многочлена следует искать среди чисел ±{1/2, 1/3, 1/6, 2, 2/3, 4, 4/3, 8, 8/3}. Рассмотрим l/m = 1/2. Тогда l − m = −1 и F (1) = −5 делится на это число. Далее l + m = 3 и F (−1) = −15 также делится на 3. Значит, дробь 1/2 остается в числе кандидатов в корни. Пусть теперь l/m = −1/2. В этом случае l − m = −3 и F (1) = −5 не делится на −3. Значит дробь −1/2 не может быть корнем данного многочлена. Выполнив проверку для каждой из выписанных вы- ше дробей, получим, что искомые корни находятся среди чисел 1/2, 2/3, 2, −4. Таким образом, с помощью довольно простого приема уда- лось значительно сузить область поиска рациональных корней рассматриваемого многочлена. Проверив оставшиеся кандидаты, убедимся, что многочлен F (x) = 6x 4 + 13x 3 − 24x 2 − 8x + 8 имеет два рациональных корня, 1/2 и −2/3. Описанный выше метод позволяет находить лишь рациональ- ные корни многочлена с целыми коэффициентами. Между тем многочлен может иметь и иррациональные корни. Так, напри- мер, рассмотренный в примере многочлен имеет еще два корня: −1 ± √ 5 (это корни многочлена x 2 + 2x − 4). Заметим, что при испытании кандидатов в корни с помощью последней теоремы, обычно рассматривают случай k = ±1. Дру- 91 гими словами, если l/m — кандидат в корни, то проверяют, де- лятся ли F (1) и F (−1) на l − m и l + m соответственно. Но может случиться так, что, например F (1) = 0, т.е. 1 — корень, а то- гда F (1) делится на любое число, и наша проверка теряет смысл. В этом случае следует разделить F (x) на x − 1, т.е. получить F (x) = (x − 1)s(x) и проводить испытания для многочлена s(x). При этом не следует забывать, что один корень многочлена F (x), x 1 = 1, уже найден. В некоторых случаях, когда характеристическое уравнение от- носится к уравнениям специального вида, его корни могут быть найдены с помощью подстановки. К таким уравнениям относятся, например симметрические и возвратные уравнения. Определение 3.7 Уравнения вида ax n + bx n−1 + cx n−2 + . . . . . . + px n/2+2 + qx n/2+1 + rx n/2 + kqx n/2−1 + k 2 px n/2−2 + . . . . . . + ck n/2−2 x 2 + bk n/2−1 x + ak n/2 = 0, где k — некоторый коэффициент, называются возвратными. Определение 3.8 Симметрическим называется уравнение степени n (n — чет- ное) вида ax n + bx n−1 + cx n−2 + . . . + cx 2 + bx + a = 0. Симметрические уравнения являются частным случаем воз- вратных при k = 1. Рассмотрим решение возвратных уравнений четвертой степе- ни. Пусть дано уравнение ax 4 + bx 3 + cx 2 + bkx + ak 2 = 0. (3.21) Его решение может быть получено с помощью подстановки t = x + k x (3.22) 92 Понизим степень уравнения, поделив обе части на x 2 . Для полу- чившегося уравнения ax 2 + bx + c + bk x + ak 2 x 2 = 0, (3.23) воспользуемся подстановкой (3.22). Тогда уравнение (3.23) можно переписать в виде at 2 + bt + (c − 2ak) = 0. (3.24) Решим уравнение (3.24), как обычное квадратное уравнение, и получим два корня t 1 и t 2 . Теперь, подставляя поочередно корни t 1 и t 2 в уравнение (3.22), получим два квадратных уравнения x 2 − t 1 x + k = 0, x 2 − t 2 x + k = 0. (3.25) Решив систему уравнений (3.25), получим четыре корня исходного уравнения (3.21). Таким образом, решение возвратного уравнения четвертой степени сводится к решению трех квадратных уравне- ний. Решение симметрических уравнений полностью аналогично, если положить k = 1. Линейные неоднородные рекуррентные уравнения Определение 3.9 Линейное рекуррентное уравнение называется неоднородным, если его можно представить в следующем виде: a k F (n + k) + a k−1 F (n + k − 1) + . . . . . . + a 1 F (n + 1) + a 0 F (n) = f (n), (3.26) где f (n) — некоторая функция от n, a k = 1. Введем однородное линейное рекуррентное уравнение (ОЛРУ), соответствующее неоднородному линейному рекуррентному урав- нению (НЛРУ) (3.26) a k F (n+k)+a k−1 F (n+k −1)+. . .+a 1 F (n+1)+a 0 F (n) = 0, (3.27) 93 а его общее решение обозначим через F o (n). Вначале пренебре- жем начальными условиями и предположим, что одно решение уравнения (3.26) уже найдено. Назовем это решение частным и обозначим через F p (n). Т е о р е м а 3.7 Общее решение НЛРУ находится в виде суммы его частного решения и общего решения соответствующего ему ОЛРУ F (n) = F o (n) + F p (n). (3.28) Доказательство. Покажем, что (3.28) действительно являет- ся решением НЛРУ (3.26). Подставим (3.28) в (3.26) a k (F o (n + k) + F p (n + k))+ + a k−1 (F o (n + k − 1) + F p (n + k − 1)) + . . . . . . + a 1 (F o (n + 1) + F p (n + 1))+ + a 0 (F o (n) + F p (n)) = f (n) ⇐⇒ a k F o (n + k) + a k−1 F o (n + k − 1) + . . . + a 0 F o (n) = 0, a k F p (n + k) + a k−1 F p (n + k − 1) + . . . + a 0 F p (n) = f (n). Таким образом, первое уравнение в системе есть общее решение ОЛРУ, а второе — частное НЛРУ. Решение НЛРУ при функции-константе Пусть НЛРУ имеет вид a k F (n+k)+a k−1 F (n+k −1)+. . .+a 1 F (n+1)+a 0 F (n) = b, (3.29) где b — целое число (константа). Будем искать частное решение уравнения (3.29) в виде кон- станты F p (n) = c, (3.30) 94 где c — также целое число. Подставим (3.30) в (3.29), тогда a k c + a k−1 c + . . . + a 0 c = b и c = b k i=0 a i (3.31) Константа c и будет частным решением уравнения (3.29) при условии неравенства нулю знаменателя формулы (3.31). Введем характеристическое уравнение для НЛРУ (3.29) h(x) = a k x k + a k−1 x k−1 + . . . + a 1 x + a 0 Если h(1) = 0, то уравнение (3.29) имеет частное решение F p (n) = b h(1) Очевидно, указанное решение не может быть использовано в слу- чае, если характеристический многочлен имеет корень, равный 1. В этом случае для нахождения частного решения нужно будет принять во внимание кратность корня 1. Обозначим формальную производную характеристического мно- гочлена h(x) через h (x). Тогда h (x) = a k kx k−1 + a k−1 (k − 1)x k−2 + . . . + a 1 , (3.32) h (1) = k i=0 ia i (3.33) Пусть h(1) = 0, но h (1) = 0. Будем искать решение (3.29) в виде F p (n) = cn. (3.34) Подставляя (3.34) в (3.29), имеем a k c(n + k) + a k−1 c(n + k − 1) + . . . + a 0 cn = b, c k i=0 (n + i)a i = b, c(nh(1) + h (1)) = b, 95 но h(1) = 0, а h (1) = 0, и c = b h (1) Итак, если h (1) = 0, то уравнение (3.29) имеет частное решение F p (n) = bn h (1) Обобщая приведенные рассуждения, обозначим m-ю произ- водную многочлена h(x) через h (m) (x). По определению будем считать h (0) (x) = h(x). Известно, что если число α является m- кратным корнем многочлена h(x), то h (m) (α) = 0. Теперь частное решение (3.29) можно записать в виде F p (n) = bn m h (m) (1) , (3.35) где m — кратность корня x = 1 характеристического многочлена h(x). Пример 3.6 Решить уравнение F (n + 2) − 2F (n + l) + F (n) = 5, F (1) = 3, 5, F (0) = 0. 1. Составляем ОЛРУ F (n + 2) − 2F (n + 1) + F (n) = 0. 2. Составляем характеристическое уравнение h(x) = x 2 − 2x + 1. 3. Решаем характеристическое уравнение, находим его корни x 1 = 1, x 2 = 1. 96 4. Записываем общее решение ОЛРУ F o (n) = C 1 1 n + C 2 n1 n = C 1 + nC 2 5. Находим частное решение НЛРУ F p (n) = 5n 2 h (2) (1) = 2, 5n 2 , так как h (2) (x) = (2x − 2) = 2. 6. Записываем общее решение НЛРУ F (n) = F o (n) + F p (n) = C 1 + nC 2 + 2, 5n 2 7. С учетом начальных условий находим коэффициенты в ре- шении НЛРУ F (0) = C 1 + 0 · C 2 + 2, 5 · 0 = 0 F (1) = C 1 + 1 · C 2 + 2, 5 · 1 2 = 3, 5 =⇒ C 1 = 0, C 2 = 1. 8. Записываем решение НЛРУ F (n) = n + 2, 5n 2 Итак, получили явную формулу для вычисления n-го чле- на последовательности. В заключение вычислим саму последо- вательность 0; 3, 5; 12; 25, 5, . . .. Решение НЛРУ при функции-многочлене Будем искать частное решение НЛРУ a k F (n + k) + a k−1 F (n + k − 1) + . . . . . . + a 1 F (n + 1) + a 0 F (n) = l i=0 b i n i (3.36) 97 в виде многочлена той же степени l, что и в правой части (3.36) F p (n) = l i=0 c i n i (3.37) Подставляя (3.37) в (3.36), получим правило вычисления ко- эффициентов многочлена (3.37) k i=0 a i l j=0 c j (n + i) j = l i=0 b i n i (3.38) Приравнивая коэффициенты левой и правой части при n l , имеем k i=0 a i c l = b l , отсюда c l = b l h(1) при h(1) = 0. Остальные коэффициенты c i находятся аналогично путем при- равнивания членов при n i , i ∈ [0, l − 1] в (3.38). Если 1 является корнем характеристического уравнения h(x) кратности m, то частное решение НЛРУ следует искать в виде F p (n) = l i=0 c i n i+m (3.39) Решение НЛРУ при функции-экспоненте Будем искать частное решение НЛРУ a k F (n+k)+a k−1 F (n+k−1)+. . .+a 1 F (n+1)+a 0 F (n) = bα n (3.40) в виде F p (n) = cα n (3.41) 98 Подставляя (3.41) в (3.40), имеем k i=0 a i cα n+i = bα n , отсюда cα n h(α) = bα n , т.е. F p (n) = bα n h(α) , если α не является корнем характеристического уравнения h(x). Если α является корнем кратности m характеристического урав- нения h(x), то частное решение (3.40) следует искать в виде F p (n) = dα n n (m) , (3.42) где d — некоторая константа, а n (m) — обобщенная степень, n (i) = n(n − 1) · . . . · (n − i + 1), n (0) = 1. (3.43) Пример 3.7 При решении одной задачи теории кодирования установлена рекуррентная зависимость числа умножений M от числа итера- ций n при построении проверочной матрицы кода M (n + 1) − 2M (n) = 4 · 2 n − 3, M (2) = 7. Запишем ОЛРУ M (n + 1) − 2M (n) = 0. Тогда имеем характеристическое уравнение h(x) = x − 2 99 и общее решение ОЛРУ M o (n) = C · 2 n Будем искать частное решение в виде M p (n) = d · 2 n + e. Подставляя его в исходное уравнение, имеем −e = 4 · 2 n − 3. Левая часть уравнения не содержит d и, следовательно, предпола- гаемое частное решение определено неверно (так как 2 — корень характеристического уравнения). Теперь изменим вид частного решения на M p (n) = dn · 2 n + e. Подставляя его в исходное уравнение, имеем e = 3, d = 2. Таким образом, M (n) = C2 n + 2n2 n + 3 и, учитывая начальные условия, C = −3. Итак, решение исходного уравнения M (n) = 2 n (2n − 3) + 3. Рекуррентные уравнения общего вида Рекуррентные уравнения, отличные от линейных рекуррент- ных уравнений с постоянными коэффициентами, не имеют обще- го метода решения. Они могут решаться, например методом проб и ошибок. 100 Пример 3.8 Решим уравнение F (n) = n−1 i=0 a i F (i) + b. (3.44) Заметим, что уравнение не является линейным, а его порядок за- висит от n. Преобразуем (3.44) в ОЛРУ. Подставив n − 1 в (3.44), получим F (n − 1) = n−2 i=0 a i F (i) + b. (3.45) Вычитая (3.45) из (3.44), имеем F (n) − F (n − 1) = a n−1 F (n − 1), т.е. ОЛРУ первого порядка F (n) = (a n−1 + 1)F (n − 1), которое имеет решение F (n) = C(a n−1 + 1) n Пример 3.9 Рассмотрим другое нелинейное уравнение, F (n) = aF n m + bn, F (1) = b. (3.46) Вычислим значение F (n) при подстановке в (3.46) некоторых кон- стант. F (m) = aF (1) + bm = b(m + a) = bm 1 + a m при n = m, F (m 2 ) = aF (m) + bm 2 = b(m 2 + am + a 2 ) = = bm 2 1 + a m + a m 2 при n = m 2 , F (m 3 ) = aF (m 2 ) + bm 3 = b(m 3 + am 2 + a 2 m + a 3 ) = = bm 3 1 + a m + a m 2 + a m 3 при n = m 3 101 Теперь можно предположить, что решением уравнения (3.46) является F (n) = bn log m n i=0 a m i (3.47) Подставляя (3.47) в (3.46) и введя обозначение r = a m , имеем F (n) = aF n m + bn = a b n m log m n m i=0 r i + bn = = rbn log m n−1 i=0 r i + bn = bn log m n−1 i=0 r i+1 + 1 = = bn log m n j=1 r j + r 0 = bn log m n i=0 r i Таким образом, (3.47) действительно является решением урав- нения (3.46). Рассмотрим еще один метод решения характеристических урав- нений. Если не удалось найти корни многочлена, то можно попро- бовать разложить его на несколько многочленов меньшей степени. При этом коэффициенты многочленов меньшей степени можно получить, решив систему из нескольких уравнений. В общем слу- чае эта система не будет линейной. Однако высказав некоторые предположения относительно коэффициентов многочленов мень- шей степени, можно свести полученную систему к системе линей- ных уравнений. Пример 3.10 Решить уравнение 13F (n + 4) + 34F (n + 3) − F (n + 2) − 2F (n + 1) + F (n) = 3 · 2 n 1. Составляем ОЛРУ 13F (n + 4) + 34F (n + 3) − F (n + 2) − 2F (n + 1) + F (n) = 0. 102 2. Составляем характеристическое уравнение h(x) = 13x 4 + 34x 3 − x 2 − 2x + 1 = 0. (3.48) 3. Решаем характеристическое уравнение. Применяя известные нам ранее методы нахождения корней уравнения, решить это уравнение нельзя. Попробуем пред- ставить характеристический многочлен из уравнения (3.48) в виде произведения двух многочленов второй степени с не- определенными коэффициентами a, b, c, d, e, f : (ax 2 + bx + c)(dx 2 + ex + f ) = =13x 4 + 34x 3 − x 2 − 2x + 1 = 0. (3.49) Раскрыв скобки в левой части уравнения (3.49) и приведя подобные слагаемые, получим систему из 5 уравнений: cd + be + af = −1, ce + bf = −2, bd + ae = 34, ad = 13, cf = 1. Данная система содержит 5 уравнений и 6 неизвестных, а кроме того, уравнения — нелинейные. Чтобы решить эту систему, попробуем высказать некоторые предположения от- носительно неизвестных, входящих в нее. Положим коэффи- циенты c и f , равными 1, и заыпишем новую систему, d + be + a = −1, bd + ae = 34, e + b = −2, ad = 13. В последней системе 4 уравнения и 4 неизвестных, но урав- нения по-прежнему остаются нелинейными. Чтобы избавить- ся от нелинейности, попробуем высказать еще некоторые 103 предположения. Положим a = 13 и d = 1. Теперь система примет вид 1 + be + 13 = −1, b + 13e = 34, e + b = −2. Эта система из трех уравнений с 2 неизвестными, причем 2 уравнения являются линейными. Составим систему из ли- нейных уравнений b + 13e = 34, e + b = −2. Решив эту линейную систему, получим значения коэффи- циентов b = −5 и e = 3. Подставив найденные значения коэффициентов в избыточное уравнение 1 + be + 13 = −1, получим тождество. Таким образом, высказанные нами ра- нее предположения относительно коэффициентов c, f , a, d оказались верными, а исходное характеристическое уравне- ние (3.48) можно представить в следующем виде: 13x 4 + 34x 3 − x 2 − 2x + 1 = (13x 2 − 5x + 1)(x 2 + 3x + 1) = 0. Теперь, чтобы найти корни характеристического уравнения (3.48), достаточно решить два квадратных уравнения 13x 2 − 5x + 1 = 0 и x 2 + 3x + 1 = 0. Очевидно, что далеко не во всех случаях высказанные пред- положения могут оказаться верными. Однако иногда только этот метод может позволить решить исходное характеристи- ческое уравнение. 104 Итак, корнями характеристического уравнения являются x 1 = 5 + i3 √ 3 26 , x 2 = 5 − i3 √ 3 26 , x 3 = −3 + √ 5 2 , x 4 = −3 − √ 5 2 4. Записываем общее решение ОЛРУ F o (n) = C 1 x n 1 + C 2 x n 2 + C 3 x n 3 + C 4 x n 4 5. Находим частное решение НЛРУ F p (n) = 3 · 2 n h(2) = 3 473 · 2 n 6. Записываем общее решение НЛРУ F (n) = F o (n) + F p (n) = = C 1 5 + i3 √ 3 26 n + C 2 5 − i3 √ 3 26 n + + C 3 −3 + √ 5 2 n + C 4 −3 − √ 5 2 n + + 3 473 · 2 n Производящие функции как метод решения рекуррентных уравнений Определение 3.10 Пусть A = (α 1 , α 2 , . . . , α n , . . .) — последовательность чисел. Тогда многочлен a(x) A(x) = ∞ i=0 α i x i называется производящей функцией последовательности A. 105 |