86277 (612706), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

У лівій частині функції мають вигляд a(n), такі, що існують константи З, n₀, що

.

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

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

.

Доказ:

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

.

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

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

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

,

а остання сума, як і сама 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.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) позитивні для всіх nN.

Рішення:

Твердження невірне.

Нехай f(n) = n², а g(n) = 1. Знайдемо таку функцію (n), яка б належала лівій множині, але не належала б правій множині, тобто (З₁) (n) [(n) C₁(n² + 1)] і (З₂) (nn₀) [(n) > n² + C₂].

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

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

2). (З₂) (n> ) 2n² > n² + C₂. Значить функція (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. Доведіть, що .

Рішення:

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

.

Помітимо, що , тоді , де З – константа, тоді можна записати по визначенню символу О, що . Використовуючи це для перетвореної рівності, одержуємо, що

= (по 1.2.4)

Що й було потрібно довести.

Задача 5. Обчислите при nN.

Рішення:

(по 1.2.6)

(по 1.2.3)

(по 1.2.4)

(по 1.2.2)

Задача 6. Обчислите (n + 2 + O(n^-1))ⁿ з відносною погрішністю 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. Доведіть, що , при nN, 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і е² е^О(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 при (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. Обчислити при +0, , А(х) - східчаста функція: А(х) = 0 при х < 0, А(х) = А_k, k x < k + 1, А_k = а₁ + а₂ +…+а_k , а_k = k ^-1 . Причому .

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

,

Характеристики

Список файлов курсовой работы