2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Решение рекуррентного соотношения
Сообщение18.01.2018, 11:36 


02/05/17
34
Здравствуйте! При анализе алгоритма с рекурсией получилось следующее рекуррентное соотношение
{C_N} = {C_{N - 1}} + s \cdot {C_{N - k}} где k < N,s < N
Для начала рассматриваю его в предположении что N кратно k. Предварительно вывел из комбинаторных соображений формулу для вычисления количества выполнений рекурсивной процедуры при длине данных N.
k \cdot \left( {{{\left( {\frac{N}{k} - 1} \right)}^s} + {{\left( {\frac{N}{k} - 2} \right)}^s} +  \cdots  + {2^s} + 1} \right) + s + 1
Потом решил пойти более строгим путем и вывести замкнутое выражение для решения данной рекуррентности через производящие функции. Выполнил стандартную процедуру из четырех этапов и на четвертом этапе получил следующее соотношение для производящей функции:
$G(z) = \frac{{s \cdot z + s \cdot {z^{k - 1}}}}{{1 - z - s \cdot {z^k}}}$
Согласно методу производящих функций для решения рекуррентных соотношений данную замкнутую форму производящей функции необходимо разложить в степенной ряд. Но знаменатель не раскладывается в общем случае на простые множители. Если же представлять данную функцию рядом Тэйлора то при длине данных например 100 или 200 придется брать производную от производящей функции соответствующего порядка что малореально.Подскажите пожалуйста, есть ли какой то иной способ представить данное соотношение G(z) в виде степенного ряда или нужно было использовать какой - либо другой вид производящей функции с самого начала ?

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение18.01.2018, 11:47 
Заслуженный участник
Аватара пользователя


27/12/17
1411
Антарктика
SergeiSX
Подстановку ряда в ряд пробовали? Имею ввиду $\frac{1}{1-f(z)}=1+f(z)+f^2(z)+...$ при условии, что $\left\lvert{f(z)}\right\rvert<1$?

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение18.01.2018, 11:53 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
А через корни уравнения
$x^k-x^{k-1}-s=0$ не получится?

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение18.01.2018, 16:25 


02/05/17
34
Евгений Машеров, спасибо! Вы имеете в виду деление всего соотношения для производящей функции на $z^k$ и дальнейшую подстановку $x=\frac{1}{z}$? Вопрос в том как дальше искать корни знаменателя. Это возможно сделать в общем виде или необходимо конкретизировать $k$ и $s$? Спасибо я попробую!
thething, спасибо! Вы предлагаете представить производящую функцию в виде соотношения ${\left( s \cdot z + s \cdot z^{k-1} \right)} \cdot \frac{1}{1-\left(z-s \cdot z^k \right)}$ и, затем, представить $\frac{1}{1-\left(z-s \cdot z^k \right)}$ в виде предлагаемого Вами разложения в ряд? Спасибо, надо попробовать!

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение18.01.2018, 16:29 
Заслуженный участник
Аватара пользователя


27/12/17
1411
Антарктика
SergeiSX в сообщении #1285413 писал(а):
Вы предлагаете представить производящую функцию в виде соотношения ${\left( s \cdot z + s \cdot z^{k-1} \right)} \cdot \frac{1}{1-\left(z-s \cdot z^k \right)}$

Да, только у Вас опечатка, в скобке в знаменателе надо поставить знак "$+$"

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение18.01.2018, 16:33 


02/05/17
34
thething в сообщении #1285415 писал(а):
Да, только у Вас опечатка, в скобке в знаменателе надо поставить знак "$+$"

Спасибо! Действительно поспешил! Я попробую обязательно!

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение19.01.2018, 01:10 
Заслуженный участник


10/01/16
2315
thething в сообщении #1285321 писал(а):
Подстановку ряда в ряд пробовали?

Не, это ровно нас и вернет к исходному рек. уравнению.
И вааще, от характеристического уравнения для исходной задачи - его написал Евгений Машеров
- никуда нам не деться.... Единственно пользу может принести производяшая функция - это получить асимптотику (через радиус сходимости ее разложения в ряд Тейлора, который, как все знают, равен расстоянию от нуля до ближайшего полюса). Но ту же информацию можно извлечь и из хар. многочлена. Дохлый номер, мне кажицца...
SergeiSX
А это, случаем, не случайное блуждание с неравными шагами? Что то - в свое время - ничего путного у меня с этим не вышло :x

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение19.01.2018, 12:21 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Ну, в общем, для таких уравнений есть достаточно простая теория, схожая с теорией линейных дифуравнений. Решение выражается через корни характеристического уравнения. Вот простого выражения для корней мне как-то в голову не приходит...

 Профиль  
                  
 
 Из https://dxdy.ru/topic124290.html
Сообщение19.01.2018, 12:35 


02/05/17
34
DeBill в сообщении #1285547 писал(а):
А это, случаем, не случайное блуждание с неравными шагами? Что то - в свое время - ничего путного у меня с этим не вышло :x

Здравствуйте! Это задача выбора оптимальной топологии разбиения скажем так связного множества квадратиков(связного в смысле наличия пути от каждого квадратика к каждому с помощью только горизонтальных и вертикальных перемещений) в квадратной области на фигуры определенной формы. Оптимальным считается то разбиение которое минимизирует общее количество получившихся фигур(оставшиеся необъединенными квадратики тоже считаются фигурами). Задача решается рекурсивным перебором. Если я правильно понимаю это и есть частный случай блуждания с неравными шагами или я ошибаюсь ?

Евгений Машеров в сообщении #1285650 писал(а):
Ну, в общем, для таких уравнений есть достаточно простая теория, схожая с теорией линейных дифуравнений. Решение выражается через корни характеристического уравнения. Вот простого выражения для корней мне как-то в голову не приходит...

Добрый день! То есть если я правильно понимаю нужно конкретизировать параметры $k$ и $s$ и решать для каждого конкретного случая отдельно ?

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение19.01.2018, 14:27 
Заслуженный участник


10/01/16
2315
Евгений Машеров в сообщении #1285650 писал(а):
Решение выражается через корни характеристического уравнения. Вот простого выражения для корней мне как-то в голову не приходит.

Ага. Да они плохие, видимо. И искать их придется приближенно.
Но есть эффективный алгоритм нахождения комплексных корней (точнее - максимального по модулю).
Такой (это - смешно): состряпать линейное рекуррентное уравнение именно с таким хар. многочленом. Для - случайного набора начальных значений, считать члены последовательности. Отношение соседних членов довольно быстро сходится к максимальному корню :D Блин....

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение19.01.2018, 15:25 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Теорию разностных уравнений можно найти во многих местах. Есть книги Гельфанда, Романко и др. Решение выражается через степени корней характеристического уравнения с коэффициентами, зависящими от начальных условий. Кратность корней имеет значение.
Красивого решения приведенного уравнения я не вижу, что не означает, что его нет. Подозреваю, что ввиду специального вида тут будет что-то тригонометрическое. Но если нет - надо решать численно, находя все k комплексных корней.

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение19.01.2018, 17:47 


02/05/17
34
Если комплексные корни будут найдены, то, если я правильно понимаю, дальнейший ряд тоже будет содержать комплексные коэффициенты и, соответственно, результат решения рекуррентного соотношения для некоторого номера $n$ тоже будет комплексный ?

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение19.01.2018, 18:02 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Нет. У нас ведь коэффициенты характеристического уравнения действительны, так что комплексные корни парами ходят, комплексно сопряжёнными. И мнимые части взаимопогашаются. Соответственно, при нахождении коэффициентов при степенях корней, исходя из начальных условий (которые, смею думать, действительны) имеем дело лишь с действительными числами, так что и результат будет действителен.

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение19.01.2018, 18:37 


02/05/17
34
Спасибо, Евгений Машеров! Начальные параметры действительны. И решать, насколько я понимаю, в общем виде не получится, необходимо конкретизировать $s$ и $k$? Затем решать численно ? А если не численно, какой метод лучше применить ?

 i  Lia: не искажайте ники. А чтобы это было проще сделать, вместо ручного набора кликните мышью на никнейм над аватаром нужного пользователя.

 Профиль  
                  
 
 Re: Решение рекуррентного соотношения
Сообщение22.01.2018, 11:33 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Ну, в общем мне красивого трюка для получения решения уравнения в общем виде придумать не удалось. Доказательство ли это моей глупости, лени или же сложности проблемы - не вем. Возможно, больше посвятив этой задаче, а также глубже изучив задачи такого рода, смог бы что-то придумать, но не уверен. Досужих размышлений на выходных не хватило для решения...
Поскольку с ростом N значение $C_N$ будет определяться максимаьным(и) по модулю корнем(-ями) характеристического уравнения, то можно попытаться поискать лишь его. Почему-то кажется, что тут Греффе-Лобачевский поможет. Или нет...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Евгений Машеров


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group