Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

и

.

Тогда для любого n max(n₀, m₀,). Значит левая часть принадлежит правой части, а, следовательно, является подмножеством правой части по определению символа О. Соотношение 6 доказано.

Соотношение 5: O(O(f(n))) = O(f(n)); (1.2.5)

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

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

Функция из левой части имеет вид a(n) такой, что существуют положительные константы С, В, n₀, m₀ такие, что

Следовательно, по определению левая часть является подмножеством правой части. Соотношение 5 доказано.

Соотношение 6: С O(f(n)) = O(f(n)), если С – константа; (1.2.6)

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

Существует такая константа В, что , по определению (1.1.1) С = О(1). Тогда С O(f(n)) = О(1) O(f(n)) = (по 1.2.4) = O(f(n)).

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

Соотношение 7: O(f(n)g(n)) = f(n)O(g(n)). (1.2.7)

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

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

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

.

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

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

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

O(f(n)²) = O(f(n) · f(n)) = (по 1.2.7) = f(n) · O(f(n)) = (по 1.2.3) = О(f(n)) · O(f(n)) = O(f(n))²

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

Соотношение 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 = z₀, то

.

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

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

.

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

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

S(z) = a₀ + O(z), S(z) = a₀ + a₁z + O(z²),

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

,

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

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

Таблица №1

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

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

Говорят, что асимптотическая аппроксимация имеет абсолютную погрешность 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) положительны для всех nN.

Решение:

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

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

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

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

2). (С₂) (n> ) 2n² > n² + C₂. Значит функция (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. Вычислите при nN.

Решение:

(по 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. Докажите, что , при nN, 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], , х и th x – непрерывные, строго возрастающие функции на всей числовой прямой.

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

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

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

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

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

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

x = и - th x.

+С, где С – некоторая константа. По определению символа О 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и).

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

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

Тогда по теореме [3]: (2.1.2)

если ряд сходится при , тогда для фиксированного n в любом круге , где .

Ряд – 2е^-2х + 2е^-4х – 2е^-6х +… сходится при х > 0, т.е. и его сумма равна th x - 1. Значит, по теореме: th x - 1 = О(е^-2х), т.е.
th x=О(е^-2х)+1.

Тогда x = и - th x = и – 1 + О(е^-2х) = (по 2.1.1) = и – 1 + О(О(е^-2и)) =

(по 1.2.5) = и – 1 + О(е^-2и).

Таким образом, x = и – 1 + О(е^-2и) - этот третье асимптотическое приближение корня.

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

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

(по 1.2.9)

(по 1.2.6)

(по 1.2.3 и 1.2.4) .

Ряд 2е^-4х – 2е^-6х + 2е^-8х – 2е^-10х +… сходится при х > 0, т.е. и его сумма равна th x – 1 + 2е^-2х. Значит, по теореме: th x – 1 + 2е^-2х = О(е^-4х),
т.е. th x=О(е^-4х)+1 - 2е^-2х.

Тогда x = и - th x = и – 1 + 2е^-2х + О(е^-4х) = (по 2.1.3) =

= и – 1 + 2(е^-2и+2 + О(е^-4и)) + О(е^-4х) = (по 1.2.6) =

= и – 1 + 2е^-2и+2 + О(е^-4и) + О(е^-2х е^-2х) = (по 2.1.1) =

= и – 1 + 2е^-2и+2 + О(е^-4и) + О(О(е^-2и) О(е^-2и)) = (по 1.2.4) =

= и – 1 + 2е^-2и+2 + О(е^-4и) + О(О(е^-4и)) = (по 1.2.5) =

= и – 1 + 2е^-2и+2 + О(е^-4и) + О(е^-4и) = и – 1 + 2е^-2и+2 + 2О(е^-4и) = (по 1.2.6) =

= и – 1 + 2е^-2и+2 + О(е^-4и).

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

Продолжая этот процесс, получим последовательность приближений с ошибками, асимптотический порядок которых постоянно убывает. Сходимость этой последовательности при неограниченном возрастании числа шагов на основе проведенных рассуждений увидеть трудно, но численные возможности этого процесса можно оценить, взяв, например, и = 5:

1) х = 5;

Характеристики

Список файлов ВКР