2014 dxdy logo

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

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




 
 Нелинейная рекуррентная последовательность
Сообщение24.09.2019, 18:59 
Последовательность $(a_k)$ определена следующим образом:$$a_{k+1}=a_k+a_k^{\log_n a_k},$$ здесь натуральное $n>1$, начальное значение $a_1$ вещественное и $1\leqslant a_1<n$.

Задача -- при $k\to\infty$ оценить асимптотику $a_k$. Более конкретно нужно следующее:
1) Пусть $n\to\infty$, $a_1=n^\alpha$ $(\alpha>0)$. Оценить при каком наименьшем $s$ верно $a_s>n^\beta$ $(\beta>\alpha)$
2) При $\alpha=0, \beta=1$ проблема эквивалентна задаче о кузнечике, который прыгает из единички и дальность прыжка увеличивается с каждым прыжком, вопрос -- сколько потребуется прыжков, чтобы допрыгать до $n\to\infty.$

Пункт (2) я изучил с помощью компьютера, получается, что число прыжков $O(n^{1/4}\log n)$. Вот только хотелось бы научиться получать такие оценки аналитически, не используя аппроксимацию численных результатов. Должно быть существуют умные методы, которые мне неизвестны. Уж больно неудобная рекуррентная формула, не знаю как подойти к решению.

 
 
 
 Re: Нелинейная рекуррентная последовательность
Сообщение28.09.2019, 11:55 
Можно показать, что при $\alpha >1, s=O(1).$ Поэтому задача сводится к случаю $1>\beta >\alpha >0$

 
 
 
 Re: Нелинейная рекуррентная последовательность
Сообщение28.09.2019, 16:11 
mihiv в сообщении #1417890 писал(а):
Можно показать, что при $\alpha >1, s=O(1).$
Да, спасибо. Действительно, если воспользоваться $\log_n a_{k+1}> (\log_n a_{k+1})^2$, то для $s$ легко получить оценку сверху $s\leqslant \left\lceil \log_2 \log_{\alpha}\beta\right\rceil$ (кузнечик прыгает неудержимо).
mihiv в сообщении #1417890 писал(а):
Поэтому задача сводится к случаю $1>\beta >\alpha >0$
У этой задачи есть небольшая предыстория. Последовательность $(a_k)$ связана с алгоритмом факторизации $n$. Если выполнить проверки некоторых условий в точках, значения которых равны целым частям элементов последовательности, то либо найдутся делители $n$, либо докажем, что на интервале $[n^\alpha,n^\beta]$ делителей нет. Таким образом интересен случай $1/2\geq\beta>\alpha\geq 0$.

Ещё отмечу такой интересный момент -- для факторизации числа $n$ можно проверять интервал $[1,n^{1/2}]$ на предмет делителей или интервал $[n^{1/2}, n]$. Так вот наш кузнечик пропрыгивает оба этих интервала за удивительно равное количество прыжков, тем самым как бы смеясь над нами и говоря: "не ребята, сложность лучше чем $O(n^{1/4}\log n)$, вы это бросьте."

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group