Курсоваробота: Вивчення поняття «символ О»
Зміст
Введення
Розділ 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= О(n3),
тому що
/>
для всіх цілих n. Можнаодержати більше точну формулу
n = />О(n2), тому що
/>
для всіх цілих n. Можнатакож недбало відкинути частина інформації й записати n= О(n10).
Визначення О не змушує насдавати найкращу оцінку.
Розглянемо приклад, колизмінна n – не целочисленна.
Приклад 2:
/>,
де х – речовинне число.
Тут уже не можна сказати, щоS(x) = O(x3), тому що відношення /> необмежено росте при х®0. Не можна також сказати, що S(x) = O(x), тому щовідношення /> необмежено росте, коли хпрагне до нескінченності. Виходить, ми не можемо використовувати символ «О»для оцінки S(x).
Ця дилема дозволяєтьсязавдяки тому, що на змінні, використовувані із О, звичайно накладаютьсяякі-небудь обмеження. Якщо, наприклад, ми поставимо умову, що />, або що />, де e — довільна позитивна константа, або що х – цілечисло, то ми зможемо записати S(x) = O(x3). Якщо ж накладена умова /> або />, де з – довільна позитивнаконстанта, то в цьому випадку S(x) = O(x). «О велике» залежить відконтексту, від обмежень на використовувані змінні.
Ці обмеження часто задаютьсяу вигляді граничних співвідношень.
Визначення 2: співвідношення f(n) = O(g(n)) при n®¥ означає, що існують дві константи С и n0,такі, що
/>при всіх n ³ n0.(1.1.3)
Зауваження 1: Значення С и n0можуть бути різними для різних О, але вони не залежать від n.
Визначення 3: запис f(х) = O(g(х)) при х®0 означає, що існують дві константи С и e, такі, що
/>, якщо тільки />.(1.1.4)
Тепер О представляє невизначену функцію й одну абодві невизначені константи, що залежать від контексту.
Зауваження 2: запис /> коректний, але в ційрівності не можна міняти місцями праву й ліву частини. У противному випадку миможемо прийти до безглуздих висновків, на зразок n = n2, виходячи звірних тотожностей n = О(n2) і n2 = О(n2).
Працюючи із символом «О»ми маємо справу з однобічними рівностями. Права частина рівняння містить небільше інформації, чим ліва, і фактично може містити менше інформації; правачастина є «огрубінням» лівої.
Якщо говорити строгоформально, то запис 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! не є початковими відрізками збіжних рядів; якщо необмежено продовжити ціформули, те отримані ряди будуть розходитися при всіх n.
Говорять, що асимптотична апроксимаціямає абсолютну погрішність O(g(n)), якщо вона має вигляд f(n) + O(g(n)), де f(n)не включає О. Апроксимація виду f(n)(1 + O(g(n))) має відносну погрішністьO(g(n)), якщо f(n) не включає О. Наприклад, апроксимація Hn утаблиці №1 має абсолютну погрішність O(n-6); апроксимація n! — відносну погрішність O(n-4). (Права частина (1.2.11) не така, якпотрібно, — f(n)(1 + O(n-4)), але її можна переписати як
/>.
Абсолютна погрішність цієї апроксимаціїє O(nn-3.5e-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) = n2, а g(n) = 1. Знайдемо такуфункцію j(n), яка б належала лівій множині, але не належала б правій множині,тобто ($З1) («n) [j(n) £ C1(n2 + 1)] і (»З2)($n³n0) [j(n) > n2 + C2].
Візьмемо j(n) = 2n2.
1). Нехай З1 = 3, тоді («n³n0)2n2 £ 3(n2 + 1). Значить функція j(n) належитьлівій множині.
2). (»З2) ($n>/> ) 2n2 > n2+ C2. Значить функція j(n) не належить правій множині.
Задача 3. Доведіть або спростуйте: cos O(x) = 1 + O(x2)для всіх речовинних х.
Рішення:
Якщо функція g(x) належитьлівій частині так, що g(x) = cos y для деякого y, причому /> для деякої константи З, то g(x) = cos y = 1 — 2sin2 (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 = (2n-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. Додаток символу О
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і× е2× еО(1) = (по 1.2.3 і 1.2.9) = е2О(е-2і)(1 + О(1))×=
(по 1.2.3) = е2 О(е-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 ~ np при(n → ¥).
Якщо x > 1, то [6]
/>
1). По теоремі (2.1.2)
/>.
/>.
2). />
По теоремі (2.1.2)
/>.Тоді />.
/>.
3). />
По теоремі (2.1.2)
/>.Тоді />.
/>.
І так далі.
2.2 Асимптотичне рішення інтегралів
Приклад 1. Обчислити /> при х > 1.
Розкладемо в ряд [6]:
/>
По теоремі (2.1.2)
/>,тобто />.
/>
Приклад 2. Обчислити /> при e®+0, />, А(х) — східчаста функція:А(х) = 0 при х .
Скористаємося асимптотичною формулою [4]
/>,
де g — постійна Ейлера />. Уведемо функцію Ã(х)= lnx + g.
/>
/>.
Останній інтеграл має порядок О(e ln e) приe®+0, апередостанній – дорівнює -g/2, так що
/>.
S(e) = I + J, де
/>.
Оцінимо інтеграл J. Нехай />, тоді "k ³ 1
/>.
Ологарифмуємо />, одержимо />.
Значить />
Отже,
/>.
Одержуємо, що
/>.
2.3 Асимптотичне обчислення суми ряду
При знаходженні суми ряду нерідко використовуєтьсяформула підсумовування Ейлера [2]:
/>
де />
Вk – числа Бернуллі, Вm({x}) –багаточлен Бернуллі.
Вk = (-1)k b2k. [6]
/>.Коефіцієнти bk обчислюються, використовуючи теорему Оодиничність розкладання функції в статечної ряд:
/>
шляхом дорівнюючи коефіцієнтів:
коефіцієнт при х: b0= 1,
коефіцієнт при хk:
/>
/>
Приклад 1. Знайти />.
По 1.2.10 Нk = ln k + O(1). Тоді
/>.
/>
Застосуємо формулу підсумовування Ейлера:
/>
/>
/>
/>
/>.
Приклад 2. Знайти />
Застосуємо формулу підсумовування Ейлера:
/>
/>
/>
Приклад 3. Знайти асимптотикупри n ® ¥ суми />
Члени цієї суми швидко ростуть із ростом номера, такщо головний член асимптотики дорівнює останньому члену суми: S(n) ~ n!, n ® ¥.Дійсно,
/>
Отже,
/>
Література
1.Брейн, Н.Г. Асимптотичні методи в аналізі. – К., 2006
2.Грехем, Р. Конкретна математика. Основи інформатики. – К.,2004
3.Олвер, Ф. Введення в асимптотичні методи й спеціальні функції. – К., 2004
4.Панченков, О.М. Асимптотичні методи в екстремальних задачах механіки. – К.,2004
5.Федорюк, М.В. Асимптотика: інтеграли й ряди. – К., 2005
6.Фихтенгольц, Г.М. Курс диференціального й інтегрального вирахування. – К., 2000