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

Випускна кваліфікаційна робота

«Символ О»

Зміст

Введення

Слово асимптотика має грецьке походження і буквально означає «ніколи не з'єднуються». Вивчаючи конічні перетину, давньогрецькі математики розглядали, зокрема, гіперболи, такі, як графік функції ,

має прямі y = x і y = - x своїми «асимптотами». При крива наближається до асимптоти, але ніколи не стикається з ними. У наші дні слово «асимптотика» використовується у більш широкому сенсі для позначення будь наближеною величини, яка стає все більш точної в міру наближення деякого параметра до граничного значення.

Точні рішення, якщо їх вдається отримати, - це чудово: остаточну відповідь викликає почуття глибокого задоволення. Але і наближене значення іноді виявляється в ціні.

У 1894 році Пауль Бахман придумав позначення для асимптотичного аналізу. У наступні роки його популярності сприяли Едмунд Ландау та ін Ми зустрічаємо це позначення в формулах на зразок:

, (1.1)

яка говорить нам, що n-е гармонійне число дорівнює натуральному логарифму n плюс константа Ейлера плюс деяка величина, яка становить «Про велике від 1 на n». Ця остання величина точно не визначена, однак, якою б вона не була, позначення «О» дозволяє стверджувати, що вона не перевершує константу, помножену на 1 / n.

Величину О (1 / n) можна вважати пренебрежимо малої, якщо тільки нас не цікавлять величини, відмінні від 1 / n лише постійним множником.

Програми символу Про можна зустріти в різних областях математики, а також і у фізиці. Наприклад, у книзі Панченкова А.Н. «Асимптотичні методи в екстремальних задачах механіки» розглядається застосування асимптотичних методів у вирішенні завдань аеродинаміки.

Мета дипломної роботи:

вивчити поняття «Символ О» і показати його застосування.

Завдання:

1. Вивчити поняття «Символ О», дати визначення.

2. Вивчити і довести основні співвідношення.

3. Показати застосування символу Про при вирішенні завдань.

4. Знайти застосування символу О в різних областях математики.

На підставі поставлених цілей і завдань кваліфікаційна робота розбита на два розділи.

Глава 1 «Символ О» складається з трьох параграфів. У першому параграфі розглядаються основні визначення, наводяться приклади, у другому - формулюються твердження, наводяться їх докази, третій параграф присвячений вирішенню завдань.

Глава 2 «Програми символу О» висвітлює застосування символу О, а саме, при вирішенні трансцендентних рівнянь, при обчисленні інтегралів, при знаходженні суми рядів.

Глава 1. Символ О.

§ 1. Основні визначення, приклади

Визначення 1:

f (n) = O (g (n)) для всіх n Î N (1.1.1)

означає, що існує така константа С, що

для всіх n Î N; (1.1.2)

а якщо позначення O (g (n)) використано всередині формули, то воно позначає функцію f (n), що задовольняє (1.1.2). Значення функції f (n) невідомі, але ми знаємо, що вони не надто великі.

Символ «О» включає невизначену константу С, кожне входження Про може мати на увазі різні С, але кожна з цих констант не залежить від n.

Приклад 1: ми знаємо, що сума квадратів перших n натуральних чисел дорівнює

_n = .

Можна записати _n = О (n ^3),

так як для всіх цілих n. Можна одержати більш точну формулу

_n = О (n ^2), так як

для всіх цілих n. Можна також недбало відкинути частину інформації і записати _n = О (n ^10).

Визначення Про не змушує нас давати найкращу оцінку.

Розглянемо приклад, коли змінна n - не целочисленная.

Приклад 2: , Де х - дійсне число.

Тут вже не можна сказати, що S (x)   =   O (x ^3), так як відношення необмежено зростає при х ® 0. Не можна також сказати, що S (x)   =   O (x), тому ставлення необмежено зростає, коли х прямує до нескінченності. Значить, ми не можемо використовувати символ «О» для оцінки S (x).

Ця дилема дозволяється завдяки тому, що на змінні, використовувані з О, звичайно накладаються якісь обмеження. Якщо, наприклад, ми поставимо умову, що , Або що , Де e - довільна позитивна константа, або що х - ціле число, то ми зможемо записати S (x)   =   O (x ^3). Якщо ж накладено умову або , Де с - довільна позитивна константа, то в цьому випадку S (x)   =   O (x). «Про велике» залежить від контексту, від обмежень на використовувані змінні.

Ці обмеження часто задаються у вигляді граничних співвідношень.

Визначення 2: співвідношення f (n) = O (g (n)) при n ® ¥ означає, що існують дві константи С і n _0, такі, що

при всіх n ³ n _0. (1.1.3)

Зауваження 1: Значення С і n ₀ можуть бути різними для різних О, але вони не залежать від n.

Визначення 3: запис f (х) = O (g (х)) при х ® 0 означає, що існують дві константи С і e, такі, що

, Якщо тільки . (1.1.4)

Тепер Про представляє невизначену функцію і одну або дві невизначені константи, що залежать від контексту.

Зауваження 2: запис коректна, але в цій рівності не можна міняти місцями праву і ліву частини. В іншому випадку ми можемо прийти до безглуздих висновків, на зразок n   =   n ^2, виходячи з вірних тотожностей n   =   О (n ²⁾ і n ²   =   О (n ^2).

Працюючи з символом «О» ми маємо справу з односторонніми равенствами. Права частина рівняння містить не більше інформації, ніж ліва, і фактично може містити менше інформації; права частина є «огрубленням» лівою.

Якщо говорити строго формально, то запис 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, , Е ^S, ln S визначаються аналогічно. Тоді «рівність» між двома такими множинами функцій є теоретико-множинне включення; знак «=» насправді означає «Í».

Приклад 3: «Рівняння» означає, що S ₁   Í   S _2, де S ₁ є множина всіх функцій виду , Для яких знайдеться константа С _1, така, що , А S ₂ є безліч всіх функцій , Для яких знайдеться константа С _2, така, що .

Можна строго довести це «рівність», якщо взяти довільний елемент з лівої частини і показати, що він належить правої частини: нехай таке, що , Слід довести, що існує така константа С _2, що . Константа вирішує проблему, так як для всіх цілих n.

Зауваження 3: Якщо у формулі використовується декілька змінних, то символ Про представляє безліч функцій від двох або більше змінних, а не тільки від однієї. В область визначення кожної функції входять всі змінні, які в даному контексті «вільні» для зміни.

Тут є деяка тонкість огляду на те, що змінні можуть мати сенс лише в частині виразу, якщо вони пов'язані знаком S або подібним.

Приклад 4: , Ціле n   ³   0. (1.1.5)

Вираз k ²   +   O (k) в лівій частині відповідає безлічі всіх функцій від двох змінних виду k ²   +   f (k, n), для яких знайдеться константа С, така, що для 0 £ k £ n. Сума таких множин функцій для 0 £ k £ n є безліч всіх функцій g (n) виду

,

де f задовольняє сформульованим умові. Оскільки

то всі такі функції g (n) належать правій частині (1.1.5), отже, (1.1.5) справедливо.

§ 2. Основні співвідношення

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

Доказ:

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

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

Доказ:

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

Будь-яка функція з лівої частини має вигляд a (n)   + B (n), і існують константи m _0, B, n _0, 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 _0, m _0, що

і

.

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

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

Доказ:

Покажемо, що ліва частина є підмножиною правій частині.

Функція з лівої частини має вигляд a (n) такою, що існують позитивні константи С, В, n _0, 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 _0, що

.

За визначенням символу Про ми отримуємо правильне рівність (1.2.7). Співвідношенні 7 доведено.

Співвідношення 8: O (f (n) ²⁾   =   O (f (n)) ^2. (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 _0, то

.

Доказ:

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

.

Співвідношення доведено.

Зауваження 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 ^2),

і т.д., оскільки

,

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

§ 3. Рішення задач

Завдання 1. Що неправильно в наступних міркуваннях? Оскільки n   =   O (n) і 2 n   =   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 ^2, а g (n) = 1. Знайдемо таку функцію j (n), яка б належала лівому безлічі, але не належала б правому множині, тобто ($ С ₁₎ ("n) [j (n) £ C ₁ (n ² + 1)] і (" З ₂₎ ($ n ³ n ₀₎ [j (n)> n ² + C _2].

Візьмемо j (n) = 2 n ^2.

1). Нехай З ₁ = 3, тоді ("n ³ n ₀₎ 2 n ² £ 3 (n ² + 1). Значить функція j (n) належить лівому безлічі.

2). ("З ₂₎ ($ n> ) 2 n ^2> n ² + C _2. Значить функція j (n) не належить правому безлічі.

Завдання 3. Доведіть або спростуйте: cos   O (x)   =   1   +   O (x ²⁾ для всіх речових х.

Рішення:

Якщо функція g (x) належить лівій частині так, що g (x) = cos   y для деякого y, причому для деякої константи, то
g (x)   =   cos y   =   1 - 2 sin ²   (Y / 2)   £   1 = 1 + 0 × х ^2. Значить існує така константа В, що g (x)   £   1 + В × х ^2. Отже, безліч з лівої частини міститься в правій частині, і формула вірна.

Задача 4. Доведіть, що .

Рішення:

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

.

Зауважимо, що , Тоді , Де С - константа, тоді можна записати з визначення символу О, що . Використовуючи це для перетвореного рівності, отримуємо, що

= (По 1.2.4)

Що й треба було довести.

Задача 5. Обчисліть при n Î N.

Рішення:

(По 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 = (2 n ^-1 + O (n ^-2)) ® 0, тоді ln (1 + k) ® 0. Тоді при n ® ¥
ln (1 + k) = k.

(По 1.2.9)

.

Завдання 7. Доведіть, що , При n Î N, 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;

2) х = і - 1 + О (1) = 5 - 1 = 4; (не враховуємо помилку О (1))

3) x = і - 1 + О ^(е-2и) = 5 - 1 = 4; (не враховуємо помилку О ^(е-2и))

4) x = і - 1 + ^{2е-2и +2} + О ^(е-4И) = 5 - 1 + 0,000670925 ... = 4,000670925 ... (Не враховуємо помилку О ^(е-4И))

Точне значення, отримане стандартними чисельними методами, так само 4,0006698 ...

Приклад 2.

Знайдемо великі позитивні корені рівняння

x tg x = 1

Це рівняння можна звернути наступним чином:

,

де n - Ціле число, а арктангенс приймає значення в інтервалі , Знаходимо, що x ~ n p при (n → ¥).

Якщо x> 1, то [6]

1). По теоремі (2.1.2) .

.

2).

По теоремі (2.1.2) . Тоді .

.

3).

По теоремі (2.1.2) . Тоді .

.

І так далі.

§ 2. Асимптотичне рішення інтегралів

Приклад 1. Обчислити при х> 1.

Розкладемо в ряд [6]:

По теоремі (2.1.2) , Тобто .

Приклад 2. Обчислити при e ® +0, , А (х) - ступінчаста функція: А (х) = 0 при х <0, А (х) = А _k, k £ x <k + 1,
А _k = а ₁ + а ₂ + ... + а _k , А _k = K ^-1. Причому .

Скористаємося асимптотичної формулою [4]

,

де g - постійна Ейлера . Введемо функцію Ã (х) = lnx + g.

.

Останній інтеграл має порядок О (e ln e) при e ® +0, а передостанній - дорівнює - g / 2, так що

.

S (e) = I + J, де

.

Оцінимо інтеграл J. Нехай , Тоді "k ³ 1

.

Прологарифмируем , Одержимо . Значить

Отже,

.

Одержуємо, що

.

§ 3. Асимптотичне обчислення суми ряду

При знаходженні суми ряду нерідко використовується формула підсумовування Ейлера [2]:

де

В _k - числа Бернуллі, В _m ({x}) - многочлен Бернуллі.

У _k = (-1) ^k b _2k. [6]

. Коефіцієнти b _k обчислюються, використовуючи теорему про єдиність розкладання функції в степеневий ряд:

шляхом прирівнюючи коефіцієнтів:

коефіцієнт при х: b ₀ = 1,

коефіцієнт при х ^k:

Приклад 1. Знайти .

За 1.2.10 Н _k = ln k + O (1). Тоді .

Застосуємо формулу підсумовування Ейлера:

.

Приклад 2. Знайти

Застосуємо формулу підсумовування Ейлера:

Приклад 3. Знайти асимптотику при n ® ¥ суми

Члени цієї суми швидко ростуть з ростом номера, так що головний член асимптотики дорівнює останньому члену суми: S (n) ~ n!, N ® ¥. Дійсно,

Отже,

Література

1. Брейн, Н.Г. Асимптотичні методи в аналізі / Н.Г. Брейн. - М.: Іноземна література, 1961.

2. Грехем, Р. Конкретна математика. Підстава інформатики: Пер. з англ. / Р. Грехем, Д. Кнут, О. Паташнік. - М.: Мир, 1998.

3. Олвер, Ф. Введення в асимптотичні методи та спеціальні функції / Ф. Олвер. - М.: Наука, 1978.

4. Панченков, А.Н. Асимптотичні методи в екстремальних задачах механіки / О.М. Панченков. - К.: Наука, 1982.

5. Федорюк, М.В. Асимптотика: интегралы и ряды / М.В. Федорюк. – М.: Наука, 1987.

6. Фихтенгольц, Г.М. Курс дифференциального и интегрального исчисления. Том 2. / Г.М. Фихтенгольц. – М.: Наука, 1969.