Основні співвідношення

1.2 Основні співвідношення

Співвідношення 1: якщо .(1.2.1)

Доказ:

Нехай , тоді  по властивості ступеня й модуля. , де З = 1. А по визначенню (1.1.2) символи Об це й означає, що при . Співвідношення 1 доведене.

Співвідношення 2: .(1.2.2)

Доказ:

Покажемо строго відповідно до теоретико-множинного визначення символу О, що ліва частина є підмножиною правої частини.

Будь-яка функція з лівої частини має вигляд a(n) + b(n), і існують константи m₀, B, n₀, C, такі, що

и.

Отже, функція в лівій частині

А, виходить, по визначенню символу О ліва частина належить правій частині. Співвідношення 2 доведене.

Співвідношення 3: f(n) = O(f(n));(1.2.3)

Доказ:

Для будь-якої функції f(n) вірна нерівність . , де З = 1. По визначенню символу О (1.1.2) це й означає, що f(n) = O(f(n)). Співвідношення 3 доведене.

Співвідношення 4: O(f(n))O(g(n)) = O(f(n)g(n));(1.2.4)

Доказ:

Покажемо відповідно до теоретико-множинного визначення символу О, що ліва частина є підмножиною правої частини.

У лівій частині функції мають вигляд 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: е^(f(n)) = 1 + O(f(n)), якщо f(n) = О(1)(1.2.9)

Доказ:

е^(f(n)) = е^g(n), де .

Так як. f(n) = О(1), тобто

, те .

. Значить е^(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

(1.2.10)

(1.2.11)

(1.2.12)

(1.2.13)

(1.2.14)

(1.2.15)

Асимптотичні формули для 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). Абсолютна погрішність співвідноситься із числом вірних десяткових цифр праворуч від десяткової крапки, які зберігаються після відкидання члена О; відносна погрішність пов'язана із числом вірних "значущих цифр".