Символ "О" - асимптотический анализ

Дипломная работа - Педагогика

Другие дипломы по предмету Педагогика

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Пожалуйста введите слова с картинки:

2. И нажмите на эту кнопку.
закрыть



сть является подмножеством правой части.

В левой части функции имеют вид a(n), такие, что существуют константы С, n0, что

.

По определению символа О мы получаем верное равенство (1.2.7). Соотношение 7 доказано.

Соотношение 8: O(f(n)2)= O(f(n))2.(1.2.8)

Доказательство:

O(f(n)2)=O(f(n) f(n))= (по 1.2.7) = f(n) O(f(n)) = (по 1.2.3) = О(f(n)) O(f(n)) = O(f(n))2

Соотношение доказано.

Соотношение 9: еO(f(n))= 1 + O(f(n)), если f(n) = О(1)(1.2.9)

Доказательство:

еO(f(n))= еg(n), где . Т.к. f(n) = О(1), т.е. , то.

. Значит еO(f(n))= 1 + O(f(n)).

Соотношение доказано.

Соотношение 10: Если сумма сходится абсолютно для некоторого комплексного числа z=z0, то

.

Доказательство:

Данное соотношение очевидно, поскольку

.

Соотношение доказано.

Замечание 4: В частности, S(z)=O(1) при z0 и S(1/n)=O(1) при n при том только условии, что S(z) сходится хотя бы для одного ненулевого значения z. Мы можем использовать этот принцип для того, чтобы, отбросив хвост степенного ряда, начиная с любого удобного места, оценить этот хвост через О. Так, например, не только S(z)=O(1), но и

S(z)=a0+O(z), S(z)=a0+a1z+O(z2),

и т.д., поскольку

,

а последняя сумма, как и сама S(z), абсолютно сходится при z=z0 и есть О(1).

В таблице №1 приведены самые полезные асимптотические формулы [2], половина из которых получена просто путем отбрасывания членов степенного ряда в соответствии с этим правилом.

Таблица №1

Асимптотические аппроксимации, справедливые при n и z0

(1.2.10) (1.2.11) (1.2.12) (1.2.13) (1.2.14)(1.2.15)

Асимптотические формулы для Hn, n! не являются начальными отрезками сходящихся рядов; если неограниченно продолжить эти формулы, то полученные ряды будут расходиться при всех n.

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

.

Абсолютная погрешность этой аппроксимации есть O(nn-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) положительны для всех nN.

Решение:

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

Пусть f(n)=n2, а g(n)=1. Найдем такую функцию (n), которая бы принадлежала левому множеству, но не принадлежала бы правому множеству, т.е. (С1) (n) [(n) C1(n2 + 1)] и (С2) (nn0) [(n) > n2 + C2].

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

1). Пусть С1 = 3, тогда (nn0) 2n2 3(n2 + 1). Значит функция (n) принадлежит левому множеству.

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

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

Решение:

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

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

Решение:

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

.

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

= (по 1.2.4)

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

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

Решение:

(по 1.2.6)

(по 1.2.3)

(по 1.2.4)

(по 1.2.2)

Задача 6. Вычислите (n + 2 + O(n-1))n с относительной погрешностью
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. Докажите, что , при nN, n.

Решение:

Покажем, что .(*)

По определению - функция аn такая, что . Получаем, что , значит .

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

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

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

1. Асимптотическое решение трансцендентны

s