Курсовая работа: Вивчення поняття "символ О"

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

1.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. Доведіть, що .

Рішення:

Перетворимо ліву частину в такий спосіб:

.