86277 (Вивчення поняття "символ О")

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

Зміст

Введення

Розділ 1. Символ О

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

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

1.3 Рішення задач

Розділ 2. Додаток символу О

2.1 Асимптотичне рішення трансцендентних рівнянь дійсного змінного

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

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

Література

Введення

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

Які мають прямі 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 Основні визначення, приклади

Визначення 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³),

тому що

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

_n = О(n²), тому що

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

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

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

Приклад 2:

,

де х – речовинне число.

Тут уже не можна сказати, що S(x) = O(x³), тому що відношення необмежено росте при х0. Не можна також сказати, що S(x) = O(x), тому що відношення необмежено росте, коли х прагне до нескінченності. Виходить, ми не можемо використовувати символ "О" для оцінки S(x).

Ця дилема дозволяється завдяки тому, що на змінні, використовувані із О, звичайно накладаються які-небудь обмеження. Якщо, наприклад, ми поставимо умову, що , або що , де - довільна позитивна константа, або що х – ціле число, то ми зможемо записати S(x) = O(x³). Якщо ж накладена умова або , де з – довільна позитивна константа, то в цьому випадку S(x) = O(x). "О велике" залежить від контексту, від обмежень на використовувані змінні.

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

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

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

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

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

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

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

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

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

Якщо говорити строго формально, то запис 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: "Рівняння" означає, що S₁ S₂, де S₁ є множину всіх функцій виду , для яких найдеться константа З₁, така, що , а S₂ є множина всіх функцій , для яких найдеться константа З₂, така, що .

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

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

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

Приклад 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) справедливо.

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)

Доказ:

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