Оценка погрешности (рекуррентное неравенство)

[romanz]

Помогите, пожалуйста, по заданной оценке
$|x_n-x_{n-1}|<a|x_{n-1}-x_{n-2}|+b|x_{n-2}-x_{n-3}|$ перейти к оценке $|x_n-x_{n-1}|<c|x_{1}-x_{0}|$

[ewert]

Во-первых, перепишите в более внятной форме: $r_n\leqslant ar_{n-1}+br_{n-2}\ \Rightarrow\ r_n\leqslant cr_1$. Во-вторых, всё равно ничего не выйдет: у Вас разностное неравенство второго порядка, и для оценки понадобятся не одно, а два начальных условия.

Откуда вопрос-то?...

[Gortaur]

Ну, тут наверное можно по-разному. Например, так. Обозначим Ваше неравенство как

$$ D_n\leq aD_{n-1}+bD_{n-2}. $$

Применим это неравенство к $D_{n-1}$ и подставим ($D_{n-2}$ не трогаем), получим

$$ D_n\leq (a^2+b)D_{n-2}+abD_{n-3}. $$

После этого применям первое неравенство к $D_{n-2}$ и так далее. Степень многочленов будет увеличиваться каждый раз на 1. Плюс этого метода в том, что Вы оцениваете через все те же 2 соседних члена. Получается, что если

$$ D_n\leq p_k(a,b)D_{n-k}+q_k(a,b)D_{n-k-1}, $$

то

$$ p_{k+1} = ap_k+q_k, \quad q_{k+1} = bp_k. $$

И меня уже опередили - Вам и правда нужна оценка через первые две разности.

[romanz]

Я ищу оценку погрешности алгоритма Фюрстенау (трехмерное обобщение цепных дробей).
Пусть $\delta_n=\frac{P_n}{P_{n-1}},$ где $P_n=qP_{n-1}+pP_{n-2}+rP_{n-3},\,P_{0}=1,P_{<0}=0$, причем $q,p,r\geqslant 0$
$|\delta_n-\delta_{n-1}|=|q+\frac{p}{\delta_{n-1}}+\frac{r}{\delta_{n-1}\delta_{n-2}}-q-\frac{p}{\delta_{n-2}}-\frac{r}{\delta_{n-2}\delta_{n-3}}|\leqslant \frac{p}{|\delta_{n-1}\delta_{n-2}|}|\delta_{n-1}-\delta_{n-2}|+\frac{r}{|\delta_{n-1}\delta_{n-2}\delta_{n-3}|}|\delta_{n-1}-\delta_{n-3}|\leqslant a|\delta_{n-1}-\delta_{n-2}|+b|\delta_{n-1}-\delta_{n-2}+\delta_{n-2}-\delta_{n-3}|\leqslant (a+b)|\delta_{n-1}-\delta_{n-2}|+b|\delta_{n-2}-\delta_{n-3}|$

Мне нужна оценка
$|\delta_n-\delta_{n-1}|\leqslant \alpha^{n-3}|\delta_3-\delta_2|$ Как ее получить?

[ИСН]

У, круто! А чё за алгоритм-то?
(Оценку Вы, в сущности, уже получили. Там эта рекуррентность свернётся аналогично формуле Бинэ для чисел Фибоначчи, и всё будет.)

[romanz]

Достаточные условия сходимости алгоритма (Furshtenau E. Uber Kettenbruche hohere Ordnung // Jahrbuch uber die Fortschritte der Mathematik. --- 1876. --- S. 133--135.) нашел Круковский. Я хочу исследовать скорость его сходимости и сравнить с другими алгоритмами, например, Бруно или Вороного.

Но $\alpha$ я не нашел. Как его найти?

[ИСН]

Как наибольший по модулю корень уравнения $q^2=aq+b$

[romanz]

Разве $\alpha$ равно наибольшему корню приведенного Вами уравнения? С теорией линейных рекуррентных уравнений с постоянными коэффициентами я знаком. Находим общее решение, а потом...?

[ИСН]

Да в общем-то и всё. Я ничего более хитрого не подразумевал.

[romanz]

Спасибо, ИСН
за всегдашнюю помощь.