Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 86
Текст из файла (страница 86)
а„= а„| + Зп — 2. РАЗДЕЛ 1бэ. Конечные разности 469 ) 21 + 22 + 23 + 24 + + 2о. Используйте соотношение а„= а„1 + 2". 6. Найдите приведенные ниже суммы, 1з + 2з + 3з +... + из Используйте соотношение а„= а„1+И . з в) 1 2о+2 21+3 22+,, +и,21 -11 Используйте соотношение а„= а„1+ и 21" г) 1 2+2 3+3 4+ ° +и (и+1); Используйте соотношение а„= а„1 + и (и + 1). используя рекуррентные отношения: б) 12 2+22 3+32 4+ +иг (и+1); Используйте соотношение а„= а„1+ и (и+ 1).
11.3. КОНЕЧНЫЕ РАЗНОСТИ ь 11х) = 1 1х + 1) — Дх) . Вторая разность, или разность второго аорядка функции г", обозначаемая Ьг 1', определена следующим образом Ь Г"(х) = 4~(ЬДх)). Поэтому, Ь г(х) = Ьшх + 1) — г" 1х)) = = Щх + 2) — г" (х + 1) ) — ( г 1х + 1) — Дх) ) = = Дх + 2) — 2Дх + 1) + Дх). В общем случае и-ая разность функции ~, обозначаемая сз" г", индуктивно определена выражением сз",Г" 1х) = Ь(Ь" ',Г" 1х)). Для студентов, прослушавших курс математического анализа, многие результаты, изложенные в данном разделе, покажутся хорошо известными.
Фактически, конечные разности можно рассматривать как бесконечно малые без предельных переходов. Аналогично исчислению бесконечно малых, теория конечных разностей имеет широкое применение в таких разнообразных областях, как информатика, актуарная математика, экономика, психология и социология. Сфера их использования включает обнаружение случайных погрешностей, построение полиномов, аппроксимирующих функциональную зависимость по результатам измерений, экстраполирование и интерполирование функций, суммирование функций, дифференцирование комбинаторных функций, аппроксимацию плошадей и многое другое.
Конечные разности — одно из базовых средств численного анализа. Следует, однако, подчеркнуть, что изучение данного раздела не требует знания математического анализа. В этом разделе мы только вводим понятие о конечных разностях и показываем некоторые их элементарные свойства. Первая разность, или разность первого иорядка функции г", обозначаемая Ьг", определена следующим образом 470 ГЛАВА т1. Некоторые специальные вопросы теории рекурсии Далее приводится формула, выражаюшая Ы(х) через 1(х). Приведенная ниже таблица иллюстрирует разностную функцию: Заметим, что в данном случае Г(х) = хз и 1ь41(х) = 0 для всех значений х. Оператором называется функция, которая отображает функции в функции.
Следовательно, 11 является оператором. Определим также другой оператор Е согласно выражению Е(1(х)) = 1(х+ 1). Таким образом, Ь|(х) = ЕЩх)) — 1(х) = (Š— 1)Щх)), где использовано обозначение (Г+С)(и) = Г(и)+С(и). Оператор 1 представляет собой тождественный оператор. Поэтому 11 = (Š— 1) и Е = 1+ 11. Используя запись сЪ = (Š— 1) и полагая Ео = 1, получаем 11" (1(х)) = (Š— 1)п(г(х)) = Е" (1(х)) — и Е" '(1(х)) + .. ,..+( 1)ь ", Еп- Щх)), ... +( 1)~ЕО(г(х)) = 1(х+ п) — п ('(и — 1) + + ( — 1)" (Дх+ и — Й)) + + ( — 1)" 1(х). й/ ПРИМЕР 11.22.
11з(1'(х)) = 1(х + 3) — 31(х + 2) + 3 г'(х + 1) — 1(х) . ТЕОРЕМА 11.23. Операторы сь и Е обладают следуюшими свойствами. Для действительного числа а и функций 1 и д а) 1ь(1 +д) = сь(1) + 11(д); Е(1 +д) = ЕЦ) + Е(д); б) 11(а1') = ась(1); Е(а1) = аЕЦ); в) Есз = ЬЕ; г) 11(а) = 0; Е(а) = а. ДОКАЗАТЕЛЬСТВО.
Докажем пункт (а). сз((1 + д)(х)) = ЙЩх) + д(х)) = = 1(х + 1) + д(х + 1) — Щх) + д(х)) = = 1(х + 1) — 1(х) + д(х + 1) — д(х) = = Ь 1(х) + Ьд(х) = = (11У + 11д)(х) РКЗДЕЛ 11.3. Конечные разности 471 Ь((а()(х)) = сз(аУ(х)) = = аг" (х + 1) + аг" (х) = = а®х+ 1) — )(х)) = = аЛу(х). Доказательство пунктов (б) и (в) предоставляется читателю. ПРИМЕР 11.24. Ь(Зх + 2хз+ 5х+ 4) = Л(Зх ) + Л(2х ) + й(5х) + й(4) = = ЗЛ(х~) + 2Л(хз) + 5Ь(х) П Теперь необходимо найти л (х"). К сожалению, здесь все не так просто. Имеем Й(х) = (х + 1) — х = 1 ~1(хз) = (х+1) — х = х +2х+1 — х = 2х+1.
В общем случае имеем Ь(х") = (х+1)" — х" = х" + пх" '+. + ("„)х" +. +1 — х" = =их" +.. +(„)х . +1. Теперь введем два свойства оператора сз, которые знакомы студентам, прослушавшим курс математического анализа. Они называются соответственно правило произведения и правило частного. ТЕОРЕМА 11.26. Для функций ~ и д ~(И) = У . Ь(д) + Е(д) . ~1(У) ~Г~ д г~У) — У (~1(д)) ~д/ д. (Е(д)) ДОКАЗАТЕЛЬСТВО. ~Од( )) = ~(Пх) .д(х)) = = Дх + 1) д(х + 1) — )'(х) д(х) = = Дх+ 1) . д(х+ 1) — ~(х) д(х+ 1) + ('(х) д(х+ 1) — г"(х) д(х) = Ях + 1) — )'(х)) .
д(х + 1) + г(х) . (д(х + 1) — .д(х)) = = ЬУ(х) Е(д(х)) + г"(х) Ьд(х) = 1'(х) . Лд(х) + Ед(х) . ЬДх) = = У Лд+ Ед ЛУИх). Доказательство второй части предоставляется читателю. 472 ГЛАВА 11. Некоторые специальные вопросы теории рекурсии ПРИМЕР 11.26. й((х + 6х) (2хг + 5) = (хг + бх) г1(2х + 5) + Е(2х + 5) й(х~ + 6х) = = (хг + бх)(2Ь(хг) + г1(5)) + Е(2хг + 5)(л,(хг) + бган(х)) = = (хг + бх) (4х + 2) + Е(2х + 5) (2х + 1 + 6) = = (х + бх)(4х + 2) + (2((х + 1) + 5)(2х + 7) = = (хг + бх) (4х + 2) + (2хг + 4х + 7) (2х + 7). ПРИМЕР 11.27. с + 2 1 (2хг + 6т+ 5) гз(хг + 2) (ха + 2) гг(2хг+ бх+ 5) 2хг + бх + 5) (2хг + бх + 5) Е(2х + бх + 5) (2хг+бх+ 5) (Ь(хг) + Е~(2)) — (хг+ 2) (2Г~(хг) + 6Ь(х) + й(5)) (2хг+ 6х+5) (2(х+ 1)г+ 6(х+ 1) + 5) (2хг + бх + 5) (2х + 1) — (хг + 2) (2(2х + 1) + 6) (2хг + бх + 5) (2(хг + 2х + 1) + бх + 11) (2хг+бх+5) (2х+1) — (ха+2) .
(4х+8) (2хг+ бх+ 5) . (2хг+ 10х+ 13) если сг(х + Зх+ 4+ 2 + 4*) = сг(х~) + Зсг(х) + сг(4) + сг(2*) + гг(4*) = = 2х+ 1+ 3+ 2*+ 3. 4* = = 2х + 4 + 2* + 3 . 4*. Как показывает приведенная ниже теорема, находить сг|(х) для 7"(х) гораздо легче. ТЕОРЕМА 11.28. Если г"(х) = а*, то Ь7(х) = а*(а — 1). В частности, г"(х) = 2*, то ЬДх) = 2*. ДОКАЗАТЕЛЬСТВО. г1(а*) = а*+1 — а* = а (а — 1).
ПРИМЕР 11.29. ° УПРАЖНЕНИЯ 1. Найдите глк(х ), вычисленное при х = 1. 2. Найдите газ(2*), вычисленное при х = 1. 3. Найдите ььгЕг(х4), вычисленное при х = 4. 4. Найдите ЬгЕ(пй), вычисленное при п = 1. 5. Найдите г1((Зх+ 2)(х — 3)). 6. Найдите гз((4х — 2)(х+ 5)). /х — 6 т 7. Найдите г1 ( ~,Зх+4)' /2х+ З~ 8. Найдите г11 — ). 1 4х+1)' 9. Покажите, что А(х.') = х х! РАЗг1ЕЛ11.4. Факториальные многочлены 473 10.
Докажите части (б), (в) и (г) теоремы 11.23 для действительного числа а и функций 1 и д а) Ь(а1) = аЬ(1); б) Е(а1) = аЕЯ; в) ЕЬ. = ЬЕ; г) сз(а) = 0; д) Е(а) = а. 11. Докажите вторую часть теоремы 11.25. (У~ д 110) — У. (Ф(д)) 1 д,/ д. (Е(д)) 11.4. ФАКТОРИАЛЬНЫЕ МНОГОЧЛЕНЫ Ранее была возможность убедиться в том, что нахождение конечных разностей функции х" довольно запутанно. Это — неблагоприятный момент, поскольку полиномиальные функции весьма распространены. Для решения данной проблемы рассмотрим факториальную задачу. Пусть при х > и > 0 ОО 1х(х — 1)(х — 2) (х — п+ 1), если п > 0; х" если п = О. К счастью, Й(хбй) = (х + 1) (х)(х — 1) ..
(х — п + 2) — х(х — 1)(х — 2) .. (х — п + 1) = = (х)(х — 1)(х — 2) ..(х — и + 2)((х + 1) — (х — п + 1) = = (х)(х — 1)(х — 2) . (х — п + 2)(п) = = п(х)(х — 1)(х — 2) (х — (п — 1) + 1) = пх~" так что теперь имеется функция с очень хорошими разностями. В действительности те, кто изучал математический анализ, возможно, надеялись на такой хороший результат для х<"1. Заметим также, что хОО = х.
Таким образом, если ~(х) = бх14) + бхОΠ— Зхбй + 2хГО + 7, то 1з 1" (х) = (5 4)х~~) + (6. 3)хбб — 3. 2хы)+ 2 = 20хрн + 18хбб — бхОО + 2. Если 1(х) = а„хбб+а„1х1" '1+ ..азхбй +а1х+ао для некоторого п, то У называется факториальны.м многочленом. Очевидно, что вычислять разности факториального многочлена очень просто. Задача состоит в том, чтобы обычный многочлен записать в виде факториального. Ниже будет дан алгоритм решения этой задачи. Читатель может заметить, что здесь используется техника, подобная одной из тех, которые применялись в разделе 5.6 для перехода от представления числа на основе 10 к представлению числа на основе п.
Начнем с примера. Предположим, что обычный многочлен Зхк — 19хз + 34хз — 21х + 5 474 ГЛКВА 11. Некоторые специальные вопросы теории рекурсии необходимо записать в виде факториального многочлена аехби + азх~~~ + агх~~~ + азх + ао Напомним, что оба многочлена задают одну и ту же функцию. Они являются только ее разными представлениями. Если разделить Зх4 19хз + 34хг — 21х — 5 на х, то получим частное Зхз — 19хг + 34х — 21 с остатком — 5.
Если разделить акх1 1+ азх~ 1+ агх~г1+ агх + ар на х, то получим а4(х — 1)(х — 2)(х — 3) + аз(х — 1)(х — 2) + аг(х — 1) + аг с остатком ао. Следовательно, ао = -5 и Зхз — 19хг + 34х — 21 = = а4(х — 1)(х — 2)(х — 3) + аз(х — 1)(х — 2) + аг(х — 1) + аг. Если Зхз — 19хг + 34х — 21 разделить на х — 1, то получим частное Зхг — 16х + 18 с остатком -3. Если ак(х — 1)(х — 2)(х — 3) + аз(х — 1)(х — 2) + аг(х — 1) + аг разделить на х — 1, получим частное а4(х — 2)(х — 3) + аз(х — 2) + аг с остатком аг. Поэтому аг = — 3 и Зх — 16х+ 18 = ак(х — 2)(х — 3) + аз(х — 2) + аг.
Если разделить Зхг — 16х + 18 на х — 2, то получим частное Зх — 10 с остатком — 2. Если разделить а4(х — 2)(х — 3) + аз(х — 2) + аг на х — 2, то получим частное а4(х — 3) + аз и остаток аг. Следовательно, аг = — 2 Зх — 10 = а4(х — 3) + аз. РЯЗДЕЛ 11.4. Фвкториальныв многочлены 475 Разделив Зх — 10 на х — 3, получаем 3 и остаток -1. Разделив а4(х — 3) + аз на х — 3, получаем аа и остаток аз. Поэтому и аз= — 1. Итак, искомый факториальный многочлен имеет вид 3х(4) х(з) 2х(з) 3х + Окончательно для нахождения коэффициента ао факториального многочлена делим на х и берем остаток. Для нахождения коэффициента а) факториального многочлена делим частное на х — 1 и берем остаток.
Продолжаем процесс деления полученного каждый раз частного на х — 2, х — 3 и х — 4 для нахождения остатков аз, аз и аг соответственно. Теперь представим алгоритм нахождения факториального многочлена а„х(")+ а„гх(" ') + + азх(з) + а)х(1) + аох. Алгоритм Факторнальный многочлен: Шаг 1. Для заданного многочлена 1(х) степени п положить и = О. Шаг 2. Разделить 7"(х) на х — )г, получив остаток г и частное д(х). Шаг 3. Положить аь = г и 1(х) = д(х). Шаг 4. Если )г = п, то процесс завершен.
В противном случае положить и = й+ 1 и вернуться к шагу 2. Простейший способ реализовать этот процесс — использовать сокращенное деление. Проиллюстрируем его на примере, положив 1(х) = х4 — 8хз+21хз — бх+3. Это дает факториальный многочлен х(4) — 2х(з) + 4х(з) + 8х + 3. Существуют несколько способов перехода от факториального многочлена к обычному. Один из них — просто раскрыть каждое слагаемое и собрать члены с одинаковыми степенями х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
