Символ "О" - асимптотический анализ (стр. 3 из 5)

Говорят, что асимптотическая аппроксимация имеет абсолютную погрешность O(g(n)), если она имеет вид f(n) + O(g(n)), где f(n) не включает О. Аппроксимация вида f(n)(1 + O(g(n))) имеет относительную погрешность O(g(n)), если f(n) не включает О. Например, аппроксимация H_n в таблице №1 имеет абсолютную погрешность O(n^-6); аппроксимация n! - относительную погрешность O(n^-4). (Правая часть (1.2.11) не такая, как требуется, - f(n)(1 + O(n^-4)), но ее можно переписать как

.

Абсолютная погрешность этой аппроксимации есть O(n^n-3.5e^-n). Абсолютная погрешность соотносится с числом верных десятичных цифр справа от десятичной точки, которые сохраняются после отбрасывания члена О; относительная погрешность связана с числом верных «значащих цифр».

§3. Решение задач

Задача 1. Что неверно в следующих рассуждениях? Поскольку n = O(n) и 2n = O(n) и так далее, то заключаем, что

?

Решение:

Замена kn на O(n) подразумевает различные С для различных k; а нужно, чтобы все О имели общую константу. В действительности, в данном случае требуется, чтобы О обозначало множество функций двух переменных, k и n. Правильно будет записать

.

Задача 2. Докажите или опровергните: О(f(n) + g(n)) = f(n) + O(g(n)), если f(n) и g(n) положительны для всех nÎN.

Решение:

Утверждение ложно.

Пусть f(n) = n², а g(n) = 1. Найдем такую функцию j(n), которая бы принадлежала левому множеству, но не принадлежала бы правому множеству, т.е. ($С₁) ("n) [j(n) £C₁(n² + 1)] и ("С₂) ($n³n₀) [j(n) > n² + C₂].

Возьмем j(n) = 2n².

1). Пусть С₁ = 3, тогда ("n³n₀) 2n²£ 3(n² + 1). Значит функция j(n) принадлежит левому множеству.

2). ("С₂) ($n>

) 2n² > n² + C₂. Значит функция j(n) не принадлежит правому множеству.

Задача 3. Докажите или опровергните: cos O(x) = 1 + O(x²) для всех вещественных х.

Решение:

Если функция g(x) принадлежит левой части так, что g(x) = cos y для некоторого y, причем

для некоторой константы С, то
g(x) = cos y = 1 - 2sin² (y/2) £ 1 = 1 + 0 ×х². Значит существует такая константа В, что g(x) £ 1 + В×х². Следовательно, множество из левой части содержится в правой части, и формула верна.

Задача 4. Докажите, что

.

Решение:

Преобразуем левую часть следующим образом:

.

Заметим, что

, тогда , где С – константа, тогда можно записать по определению символа О, что . Используя это для преобразованного равенства, получаем, что

= (по 1.2.4)

Что и требовалось доказать.

Задача 5. Вычислите

при nÎN.

Решение:

(по 1.2.6)

(по 1.2.3)

(по 1.2.4)

(по 1.2.2)

Задача 6. Вычислите (n + 2 + O(n^-1))ⁿ с относительной погрешностью
O(n^-1), при n®¥.

Решение:

(по 1.2.3 и 1.2.4)

Приn®¥k = (2n^-1 + O(n^-2))®0, тогдаln (1 + k)®0. Тогда при n®¥
ln (1 + k) = k.

(по 1.2.9)

.

Задача 7. Докажите, что

, при nÎN, n®¥.

Решение:

Покажем, что

. (*)

По определению

- функция а_n такая, что . Получаем, что , значит .

Теперь докажем, что

:

= (по 1.2.4 и 1.2.6) = = (по (*))
= (по 1.2.6) = (по 1.2.9)
= (по 1.2.6) = .

Глава 2. Приложения символа О.

§1. Асимптотическое решение трансцендентных уравнений: действительного переменного

Пример 1.

Рассмотрим уравнение

x +th x = u,

где u - действительный параметр,

- гиперболический тангенс [6], , х и thx– непрерывные, строго возрастающие функции на всей числовой прямой.

Найдем асимптотические приближения для корня:

1). Функция u(x) = x +thx непрерывна и строго монотонна на R. По теореме о непрерывности обратной функции, существует обратная к ней функция х(и), непрерывная и строго монотонная на Е_и = R.

Так как при х®¥и(х)®¥, то при и®¥х(и)®¥.

Пусть и®¥, тогда х®¥ и

.

Значит, х(и) ~ и, при и®¥. Это первое асимптотическое приближение для корня.

2). Приведем уравнение к виду:

x = и - thx.

+С, где С – некоторая константа. По определению символа Оthx = 1+O(1).

x = и – 1 + О(1) - это второе асимптотическое приближение корня.

3). Докажем, что е^-2х = О(е^-2и): (2.1.1)

подставим второе асимптотическое приближение корня

е^-2х = е^{-2(и – 1 + О(1))} = е^-2и × е²× е^О(1) = (по 1.2.3 и 1.2.9) = е²О(е^-2и)(1 + О(1))×=

(по 1.2.3) = е²О(е^-2и)(2О(1)) = (по 1.2.6 и 1.2.4) = О(е^-2и).

Разложим thx в ряд [6], удобный при больших х:

thx = 1 – 2е^-2х + 2е^-4х – 2е^-6х +… (х > 0)