Вивчення поняття "символ О"
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
?мволом "О" ми маємо справу з однобічними рівностями. Права частина рівняння містить не більше інформації, чим ліва, і фактично може містити менше інформації; права частина є "огрубінням" лівої.
Якщо говорити строго формально, то запис O(g(n)) позначає не якусь одну функцію f(n), а відразу множина функцій f(n), таких, що для деякої константи С. Звичайна формула g(n), що не включає символ О, позначає множину, що містить одну функцію f(n) = g(n). Якщо S і T суть множини функцій від n, то запис S + T позначає множину всіх функцій виду f(n) + g(n), де f(n)S і g(n)T; інші позначення начебто S T, ST, S/T, , е, ln S визначаються аналогічно. Тоді "рівність" між двома такими множинами функцій є теоретико-множинне включення; знак "=" у дійсності означає "(".
Приклад 3: "Рівняння" означає, що S1 S2, де S1 є множину всіх функцій виду , для яких найдеться константа З1, така, що , а S2 є множина всіх функцій , для яких найдеться константа З2, така, що .
Можна строго довести це "рівність", якщо взяти довільний елемент із лівої частини й показати, що він належить правій частині: нехай таке, що , варто довести, що існує така константа З2, що . Константа вирішує проблему, тому що для всіх цілих n.
Зауваження 3: Якщо у формулі використовується трохи змінних, то символ О представляє множину функцій від двох або більше змінних, а не тільки від однієї. В область визначення кожної функції входять всі змінні, які в даному контексті "вільні" для зміни.
Отут є деяка тонкість через те, що змінні можуть мати сенс лише в частині вираження, якщо вони звязані знайомий ( або подібним.
Приклад 4:
,
ціле n 0.(1.1.5)
Вираження k2 + O(k) у лівій частині відповідає множині всіх функцій від двох змінних виду k2 + f(k, n), для яких найдеться константа З, така, що для 0 k n. Сума таких множин функцій для 0 k n є множину всіх функцій g(n) виду
,
де f задовольняє сформульованій умові. Оскільки
те всі такі функції g(n) належать правій частині (1.1.5); отже, (1.1.5) справедливо.
1.2 Основні співвідношення
Співвідношення 1: якщо .(1.2.1)
Доказ:
Нехай , тоді по властивості ступеня й модуля. , де З = 1. А по визначенню (1.1.2) символи Об це й означає, що при . Співвідношення 1 доведене.
Співвідношення 2: .(1.2.2)
Доказ:
Покажемо строго відповідно до теоретико-множинного визначення символу О, що ліва частина є підмножиною правої частини.
Будь-яка функція з лівої частини має вигляд a(n) + b(n), і існують константи m0, B, n0, 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), такі, що існують константи В, З, n0, m0, що
і
.
Тоді для будь-якого n max(n0, m0,). Значить ліва частина належить правій частині, а, отже, є підмножиною правої частини по визначенню символу О. Співвідношення 6 доведене.
Співвідношення 5: O(O(f(n))) = O(f(n));(1.2.5)
Доказ:
Покажемо, що ліва частина є підмножиною правої частини.
Функція з лівої частини має вигляд a(n) такий, що існують позитивні константи З, В, n0, m0 такі, що
Отже, по визначенню ліва частина є підмножиною правої частини. Співвідношення 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), такі, що існують константи З, 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: е(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 = z0, те
.
Доказ:
Дане співвідношення очевидно, оскільки
.
Співвідношення доведене.
Зауваження 4: Зокрема, S(z) = O(1) при z 0 і 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 і z 0
(1.2.10) (1.2.11) (1.2.12) (1.2.13) (1.2.14)(1.2.15)
Асимптотичні формули для Hn, n! не є початковими відрі?/p>