Асимптотический анализ

[ELVY]

$$\forall \varepsilon > 0, \exists n_0 = n_0(\varepsilon) : n \geqslant n_0 \Rightarrow |f(n) - 1| < \varepsilon$$

Если взять $\varepsilon = 1$, то найдется $n_0 : \forall n \geqslant n_0 \Rightarrow |f(n) - 1| < 1$. Отсюда получается $c_2 = 1$ или же

$$(n + a)^b \leqslant n^b \text{ для всех } n \geqslant 0$$

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

-- 01.08.2019, 17:29 --

Otta
Не совсем понимаю о чем вы. В задаче предпологается, что $n$ может быть любым натуральным числом

[thething]

ELVY в сообщении #1408245 писал(а):

как найти границу снизу?

В последней части определения

ELVY в сообщении #1408245 писал(а):

$$ |f(n) - 1| < \varepsilon$$

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

[ELVY]

У меня получилось так:

$$|(1 + a/n)^b - 1| < \varepsilon$$

$$1 - \varepsilon < (1 + a/n)^b < 1 + \varepsilon$$

К примеру $\varepsilon = 0.5$, тогда $c_1 = 0.5$, а $c_2 = 1.5$. Тогда в конечном счете получится:

$$ \frac{1}{2}n^b \leqslant (n + a)^b \leqslant \frac{3}{2}n^b$$

Правильно ли я сделал?

[thething]

Правильно. Только надо указывать, что эти оценки верны, начиная с некоторого номера. А в асимптотических равенствах обязательно надо указывать базу, в данном случае $n\to+\infty$ (о чём и говорила Otta). При другой базе (например, при стремлении $n$ к нулю), то же самое асимптотическое равенство неверно.

[ELVY]

thething
Вы же писали, что $n_0$ явно выражать не следует. Достаточно того, что оно существует. Или я что-то не так понял?

[thething]

А я и не говорил, что его надо явно выразить, просто указать, что оценки верны, начиная с некоторого номера. У Вас же они написаны так, как будто верны вообще для всех номеров. Особенно с учётом этого

ELVY в сообщении #1408245 писал(а):

$$(n + a)^b \leqslant n^b \text{ для всех } n \geqslant 0$$

из предыдущего сообщения.

[ELVY]

thething
Хорошо, я Вас понял. Спасибо большое за помощь.

[ELVY]

Еще возник вопрос, когда посмотрел авторское решение:

Заметим, что

$$n + a \leqslant n + |a| \leqslant 2n \text{, когда }|a| \leqslant n\text{, (1)}$$

и

$$a + n \geqslant n - |a| \geqslant \frac{1}{2}n\text{, когда }|a| \leqslant \frac{1}{2}n\text{, (2)}$$

Таким образом

$$n \geqslant 2|a|\text{,}\text{ (3)}$$

$$0 \leqslant \frac{1}{2}n \leqslant n + a \leqslant 2|n|\text{, (4)}$$

Так как $b > 0$ возведем все в степень:

$$0 \leqslant (\frac{1}{2}n)^b \leqslant (n + a)^b \leqslant (2n)^b\text{, (5)}$$

$$0 \leqslant (\frac{1}{2})^bn^b \leqslant (n + a)^b \leqslant 2^bn^b\text{. (6)}$$

Таким образом: $c_1 = (\frac{1}{2})^b$, $c_2 = 2^b$, $n_0 = 2|a|$

Не совсем понятно как они пришли к этому решению, а имнно не понятны пункты $(1) - (3)$.

[nnosipov]

ELVY в сообщении #1408262 писал(а):

а имнно не понятны пункты $(1) - (3)$.

Там у Вас (или у них опечатки). А доказывается следующее утверждение: если $n \geqslant 2|a|$, то $n/2 \leqslant n+a \leqslant 2n$. Обычно это называют "оценки по модулю", и при определенном навыке они становятся более-менее очевидными.

[ELVY]

nnosipov
Я действительно неправильно переписал (уже исправил).
Не понятно откуда они получиили, что $|a| \leqslant n$ в первом увравнении и $|a| \leqslant \frac{1}{2}n$ во втором.

[nnosipov]

ELVY в сообщении #1408265 писал(а):

уже исправил

Не до конца. Вместо знаков равенства должны быть соответствующие неравенства.

[ELVY]

nnosipov
Да, пропустил. Исправил.

[nnosipov]

ELVY в сообщении #1408265 писал(а):

Не понятно откуда они получиили, что $|a| \leqslant n$ в первом увравнении и $|a| \leqslant \frac{1}{2}n$ во втором.

Понимаете, нам хочется получить пару неравенств типа $n/2 \leqslant n+a \leqslant 2n$. Но это невозможно сделать, если мы не будем как-то ограничивать $n$, причем это ограничение должно как-то зависеть от $a$. Как? Вот мы анализируем оба неравенства и обнаруживаем те самые ограничения на $n$ (которые Вам непонятны), ибо они-то и гарантируют нам то, что мы хотим.

[ELVY]

nnosipov
Правильно ли я понимаю, что сначало мы пишем это неравенство $n/2 \leqslant n + a \leqslant 2n$, а только потом ищем ограничения на $n$, чтобы неравенство выполнялось? То есть по сути я могу написать любое неравенство, например, $n/5 \leqslant n + a \leqslant 7n$ и начать искать на него ограничения?

$$n + a \leqslant n + |a| \leqslant 7n\text{, когда } |a| \leqslant 6n$$

$$n + a \geqslant n - |a| \geqslant n/5\text{, когда }|a| \leqslant \frac{4}{5}n\text{.}$$

В таком случае получаем $c_1 = (\frac{1}{5})^b$ и $c_2 = 7^b$, $n_0 = \frac{5}{4}|a|$

[nnosipov]

ELVY Да, совершенно верно.