2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Вычисление без компьютера
Сообщение12.03.2006, 22:45 
Заслуженный участник


09/02/06
4382
Москва
Линейные рекурентные уравнения, как и линейные дифференциальные уравнения легко решается. Предлагаю вычислить:
$a_i=i,i\le k, a_n=(a_{n-1}+a_{n-2}+\dots+a_{n-k})/k,n>k$.
Вычислить $a_{2000000}$ при k=1000 с точностью до 1000 знаков после запятой.

 Профиль  
                  
 
 
Сообщение20.03.2006, 22:56 
Заслуженный участник


09/02/06
4382
Москва
Вообще то меня разочаровало, что народ не решает даже линейные уравнения.
Приведу решение и этой задачи с аналогией дифференциальных уравнений.
Рассмотрим вначале общее рекурентное уравнение:
$x_n=\sum_{i=1}^k b_I x_{n-i}$.
Оно решается аналогично дифференциальному уравнению:
$y^{(k)}=\sum_{i=1}^k b_i y^{(k-i)}$.
Решение первого ищется в виде комбинаций степеней, второго в виде комбинаций экспонент:
$x_n=\sum_i C_i s_i^{n-1}, y(t)=\sum_i C_i exp(s_i t).$
Характеристические числа и в том и в этом случае находятся как корни уравнения:
$f(s)=s^n-\sum_{i=1}^k b_i s^{k-i} =0$.
Здесь мы рассматриваем только случай отсутствия кратных корней (чему соответствует исходное уравнение). Сами коэффициенты перед степенями находятся так же, как и в случае дифференциального уравнения из соотношений:
$\sum_i C_is_i^j=x(j+1) \ (y^{(j)}(0) \ for \  diff. \ equat. \ ), j=0,1,\dots, k-1$.
Сложим все уравнения умножив j -ое уравнение на c(i,j) и получим:
$C_i f_i(s_i)=\sum_{j=0}^{k-1} c(i,j)x(j+1),f_i(s)=\frac{f(s)}{s-s_i}=\sum_{j=0}^kc(i,j)s^j$
Остается эти выкладки применить к исходной задаче. В этом случае характеристический многочлен получается:
$f(s)=ks^k-\frac{s^k-1}{s-1},s_0=1,f_0(s)=ks^{k-1}+(k-1)s^{k-2}+\dots+1$.
Это дает коэффициент перед постоянной 1:
$C_0=\frac{\sum_{j=1}^k j^2 }{\sum_{j=1}^k j}=\frac{2k+1}{3}.$
Остаётся оценить остальные члены. Они при больших k находятся по приближённой формуле:
$s_j=r_jexp(iq_j),r_j~exp(-t_j/k),q_j~2\pi j/(k-1),exp(2t_j)=(t_j+1)^2+4\pi ^2j^2,j=1,2,...,k-1$
При этом коэффициенты перед комплексными корнями получаются ограниченными и учитывая, что за k шагов оставшиеся добавки убывают более 8 раз, соответственно за 2k шагов заведомо больше 10 раз, можно их отбросить сохраняя точность в 1000 знаков при 2000k итерациях. Следовательно
$a_{2000k}=\frac{2k+1}{3}=667 \ (k=1000)$
с точностью до 1000 знаков.

 Профиль  
                  
 
 
Сообщение21.03.2006, 05:43 
Модератор
Аватара пользователя


11/01/06
5660
Так уже обсуждали.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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