Главная > Математика > Введение в прикладную комбинаторику
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 7. z-преобразование

Производящую функцию

часто называют «преобразованием в или -првобразованием.

Некоторые авторы предпочитают ей следующую функцию:

называемую отрицательным -преобразованием. Кроме того, как мы видели в § 5, используется также функция

называемая экспоненциальным -преобразованием.

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

Рис. 6

Рис. 7

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

Пример 1 (рис. 6). Пусть

Тогда

Итак, -преобразованием для (7.4) будет

Пример 2 (рис. 7). Пусть

Тогда

(кликните для просмотра скана)

(кликните для просмотра скана)

(см. скан)

Формулы (7.45) — (7.48) останутся справедливыми, если заменить тригонометрические функции соответствующими гиперболическими.

Обратное преобразование. Коэффициенты разложения в ряд Тейлора образуют исходную последовательность

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

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

— рациональная дробь, причем полиномы не имеют общих корней. Предположим, что степень полинома меньше степени полинома (в противном случае достаточно заменить на и что корни полинома по модулю больше или равны 1, т. е. что Известно, что такую рациональную дробь можно разложить на простые дроби, а именно

где кратность корня

Учитывая (7.10), (7.11) и (7.30), из (7.50) получаем обратное преобразование:

где

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

Далее, если положим

то, сравнивая (7.49) и (7.50), имеем

обозначает производную от по

Замечание. z-преобразование приводит, в сущности, к некоторому «символическому исчислению» или «операционному исчислению», аналогичному тому, которое получается с помощью

преобразования Лапласа (или Карсона — Лапласа, если угодно) для функций, непрерывных на отрезках, хотя -преобразование и применяется к последовательностям Как уже отмечалось, -преобразование — это не что иное, как особое представление производящей функции, в наибольшей степени используемое в теории вероятностей Как -преобразование, так и само преобразование Лапласа восходят к Эйлеру и Лапласу.

Некоторые свойства преобразования Лапласа:

легко переносятся на -преобразование:

при замене на 1—2.

Заметим также, что преобразованию Карсона — Лапласа

можно сопоставить видоизмененное -преобразование

при этом некоторые формулы упрощаются.

Пример применения z-преобразования к уравнениям в конечных разностях. Рассмотрим уравнение в конечных разностях

с

Применяя (7.13) к » а затем к , имеем

или

откуда

Представляя в виде

имеем

Используя (7.27), получаем

Другие важные соотношения. Пусть

Тогда

откуда

Вообще, исходя из (7.19), имеем

Если рассмотрим три последовательности, связанные между собой соотношением (7 71), то задание двух из этих последовательностей определяет третью. По внутреннему закону композиции,

определяемому формулой (7.71), можно указать некоторый обратный внутренний закон. Относительно первого последовательности образуют группу, а относительно второго не образуют группы

или

Экспоненциальное z-преобразование. Можно показать, что это преобразование обладает свойствами, подобными свойствам, которые были установлены для обычного -преобразования. Вот некоторые из них:

Основные свойства преобразований f*(z) и fe(z). Найдем -преобразование для

Из (7.83) следует, что

Если -преобразование для -преобразование для то

Итак,

Этот результат можно обобщить. Положим

Легко получить

Это как раз -преобразование для последовательности, получаемой суммированием порядка из эту последовательность можно получить индукцией:

Оператор примененный к функции -преобразованию дает (см. (7.72) и (7.73))

Имеет место другая основная формула:

Рассматривают также оператор (полином относительно

Приведем теперь несколько основных свойств экспоненциального -преобразования,

По определению (см. (7.33))

Полагаем символически

где означает, что член справа заменяется на члены слева. Тогда разложение (7.93) запишется символически так (полагаем

Исходя из (7.95), можно построить символическое исчисление, приводящее к интересным упрощениям.

Например, если

то, полагая

имеем

и

Можно определить произведение экспоненциальных разложений

Это символическое разложение обобщается на любое число функций:

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

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

Это символическое экспоненциальное исчисление может быть использовано для вычисления по последовательности такой последовательности что

Чтобы получить исходя из (7.104), можно, очевидно, воспользоваться экспоненциальным -преобразованием, отыскивая последовательность, соответствующую но можно также использовать символическое разложение:

добавляя условие

Это дает

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление