1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n J
Изтегляне 5.91 Mb.
|
Твърдение: Ако е изображение на интервала [a, b] в себе си, то при произволно начално приближение x0 [a, b], всички точки от редицата { xn} принадлежат също на [a, b]. Доказателство: Тривиална индукция по n. При n = 0, x0 [a, b]. Ако xn [a, b], то xn+1 = (xn) [a, b].
[a, b] на . Следващото просто условие върху гарантира поне една неподвижна точка. Твърдение: Ако е непрекъснато изображение на интервала [a, b] в себе си, то има поне една неподвижна точка. Доказателство: Ако (a) = a или (b) = b, то има неподвижна точка. Нека сега (a) a и (b) b. Тъй като : [a, b] [a, b], имаме a < (a) и (b) < b. Разглеждаме функцията r (x) = x - (x). Очевидно тя е дефинирана и непрекъсната в [a, b]. Имаме r (a) = a - (a) < 0 и r (b) = b - (b) > 0. От теоремата на Болцано-Коши съществува точка (a, b), такава че r () = 0 = (), т.е. е неподвижна точка на . Остава да видим какви условия за ще гарантират сходимост на редицата { xn} към неподвижната точка . Казваме, че функцията g удоволетворява условието на Липшиц с константа q в интервала [a, b], ако |g (x) – g (y)| q.|x – y| за всеки x, y [a, b]. Теорема: Нека е непрекъснато изображение на [a, b] в себе си, което удоволетворява условието на Липшиц с константа q < 1. Тогава уравнението x = (x) има единствен корен в [a, b] и редицата { xn} (x0 [a, b] е произволно, xn+1 = (xn), n = 0, 1, …) клони към при n . При това, |xn - | (b – a).qn за всяко n = 0, 1, …. Доказателство: От предното твърдение, има поне една неподвижна точка в [a, b]. Да допуснем, че 1 и 2 са две различни неподвижни точки на в [a, b], т.е. 1 = (1), 2 = (2) и 1, 2 [a, b], 1 2. Имаме |1 - 2| = | (1) - (2)| q.|1 - 2| < < |1 - 2| - противоречие. Използвали сме, че удоволетворява условието на Липшиц с константата q < 1 и, че 1 2. Така има единствена неподвижна точка в [a, b]. С индукция по n ще покажем горната оценка. При n = 0, |x0 - | (b – a).q0 = b – a, тъй като x0 [a, b] и [a, b]. Нека |xn - | (b – a).qn. Тогава |xn+1 - | = | (xn) - ()| q.|xn - | q.(b – a).qn = (b – a).qn+1. Така |xn - | (b – a).qn за всяко n = 0, 1, … xn при n . Изображение , което удоволетворява условието на Липшиц с константа q < 1 се нарича свиващо изображение. При него разстоянието между образите (x) и (y) е строго по-малко от разстоянието между праобразите x и y, т.е. “свива” разстоянията. Твърдение: Нека е диференцируема функция в [a, b] и нека | (x)| q < 1 за всяко x [a, b]. Тогава е свиващо изображение. Доказателство: Нека x, y [a, b]. Тогава от теоремата за крайните нараствания на Лагранж, (x) - (y) = ().(x – y), [a, b] | (x) - (y)| = | ()|.|x – y| q.|x – y| и q < 1. Нека уравнението x = (x) има корен в интервала [a, b]. Казваме, че итерационният процес, породен от е сходящ в [a, b], ако за всяко начално приближение x0 [a, b], редицата { xn}, построена по формулата xn+1 = (xn), n = 0, 1, …е сходяща към корена . Горната теорема, показва сходимостта на итерационните процеси, породени от свиващи изображения. Сега ще приведем една по-слаба форма на теоремата. Следствие: Нека е корен на уравнението x = (x). Да предположим, че има непрекъсната производна в околност U на и | ()| < 1. Тогава при достатъчно добро начално приближение x0, итерационният процес, породен от , е сходящ. Нещо повече, съществуват константи C > 0 и 0 < q < 1, такива че |xn - | C.qn за всяко n = 0, 1, …. Доказателство: Тъй като (x) е непрекъсната функция в U и | ()| < 1, то съществуват q < 1 и > 0, такива че | (x)| q за всяко x [ - , + ]. Освен това, за всяко x [ - , + ] имаме | (x) - | = | (x) - ()| = | ()|.|x - | q. < , е между x и , така че (x) [ - , + ]. Следователно, е свиващо изображение на интервала [ - , + ] в себе си и всички твърдения на следствието следват от теоремата. Ето и геометрична илюстрация на итерационният процес, породен от свиващо изображение . 
Скоростта на сходимост в разгледания итерационен процес се определя от общия член qn на една геометрична прогресия. Затова казваме, че итерационният процес е сходящ със скоростта на геометрична прогресия. Има и по-бързо сходящи итерационни процеси. За да характеризираме тяхната скорост въвеждаме понятието ред на сходимост. Казваме, че итерационният процес { xn} има ред на сходимост p, ако съществуват константи C > 0 и 0 < q < 1, такива че |xn - | C. Ще посочим без доказателство една теорема, която ни позволява да определяме реда на сходимост на итерационен процес, породен от изображението .
() = () = …= (p-1)() = 0, (p)() 0. Тогава при достатъчно добро начално приближение x0, итерационният процес, породен от има ред на сходимост p.
f е функция, която удоволетворява следните условия: 1. f е дефинирана в интервала [a, b]. 2. f притежава непрекъсната втора производна в [a, b]. 3. f (a).f (b) < 0. 4. f (x) 0 за всяко x [a, b]. 5. f (x) 0 за всяко x [a, b]. Тези условия гарантират съществуването на единствен корен на уравнението f (x) = 0 в интервала [a, b]. Действително, условието 2. осигурява непрекъснатост на f, условието 3. показва, че f приема противоположни знаци в краищата на интервала [a, b] f има поне един корен. От условие 4. следва, че първата производна на f има постоянен знак f е строго монотонна функция графиката на f може да пресича най-много един път оста Ox, т.е. f (x) = 0 може да има най-много едно решение. Също, от условие 5. и непрекъснатостта на f f има постоянен знак в [a, b] f е или изпъкнала (при f (x) > 0 за всяко x [a, b]) или вдлъбната (при f (x) < 0 за всяко x [a, b]). Методът на хордите е итерационен метод, при който се построява редица от последователни приближения x0, x1, …, xn, … на корена на уравнението f (x) = 0 по следния начин: избираме x0 = a или x0 = b, така че да имаме f (x0).f (x0) < 0. Нека за определеност сме избрали x0 = a. Тогава за n = 0, 1, …, ако сме избрали xn, то xn+1 избираме по следния начин: прекарваме права през (xn, f (xn)) и (b, f (b)) (през (xn, f (xn)) и (a, f (a)), ако x0 = b) и xn+1 е пресечната точка на тази права с оста Ox. За по-голяма нагледност привеждаме геометрична илюстрация: 
Тя отговаря на случая x0 = a, f (a) < 0 и f (x) > 0 за всяко x [a, b]. Сега ще изведем формула за xn+1 чрез xn. Правата през (xn, f (xn)) и (b, f (b)) има уравнение y = f (xn) + (x – xn).f [xn; b], така че xn+1 е решението на уравнението 0 = f (xn) + (x – xn).f [xn; b], т.е. xn+1 = xn f (a) < 0 и f е изпъкнала в [a, b] (или f (a) > 0 и f е вдлъбната в [a, b]) може да се покаже, че редицата { xn} е монотонно растяща и ограничена отгоре { xn} е сходяща. Нека xn при n . В равенството xn+1 = xn (x) = x За целта изчисляваме (). Имаме () = 1 = 1 Сега използваме формулата на Тейлър: съществуват 1, 2 [a, b], такива че f (b) = f () + f ().(b - ) + f (b) = f () + f (2).(b - ). Така () = Нека M = Тогава | ()| x0 = a или x0 = b, така че да имаме f (x0).f (x0) > 0. След това избираме точка x1 x0, x1 [a, b], такава че f (x1).f (x1) > 0. По-нататък, ако за n = 1, 2, … сме избрали xn-1 и xn, то xn+1 избираме по следния начин: прекарваме права през (xn-1, f (xn-1)) и (xn, f (xn)) и xn+1 е пресечната точка на тази права с оста Ox. За по-голяма нагледност привеждаме геометрична илюстрация:
Тя отговаря на случая x0 = b, f (b) > 0 и f (x) > 0 за всяко x [a, b]. Сега ще изведем формула за xn+1 чрез xn и xn-1. Правата през (xn, f (xn)) и (xn-1, f (xn-1)) има уравнение y = f (xn) + (x – xn).f [xn-1; xn], така xn+1 е решението на уравнението 0 = f (xn) + (x – xn).f [xn-1; xn], т.е. xn+1 = xn Може да се покаже, че ако интервалът [a, b] е достатъчно малък, методът на секущите е сходящ и има ред на сходимост x0 = a или x0 = b, така че да имаме f (x0).f (x0) > 0. Тогава за n = 0, 1, …, ако сме избрали xn, то xn+1 избираме по следния начин: прекарваме допирателната към графиката на f в точката (xn, f (xn)) и xn+1 е пресечната точка на тази допирателна с оста Ox. За по-голяма яснота привежда геометрична илюстрация:
Тя отговаря на случая x0 = b, f (b) > 0 и f (x) > 0 за всяко x [a, b]. Сега ще изведем формула за xn+1 чрез xn. Допирателната към графиката на f в точката (xn, f (xn)) има уравнение y = f (xn) + f (xn).(x – xn), така xn+1 е решението на уравнението 0 = f (xn) + f (xn).(x – xn), т.е. xn+1 = xn Ако елементарното събитие w Î W се сбъдне и w Î A W, ще казваме че се е сбъднало събитието A. Тъй като за всяко w имаме w Î W, то W се сбъдва при всеки експеримент. Тъй като за всяко w имаме w Ï Æ, то събитието Æ не може да се сбъдне при никой експеримент. Нека A е фамилия от подмножества на W, т.е. A е множество от събития. Ще казваме, че A e булова алгебра, ако са в сила следните свойства:
Ще казваме, че буловата алгебра A е булова s-алгебра, ако тя е затворена относно изброимите сечения и обединения, т.е. Ai Î A, i = 1, 2, … Þ За краткост буловите -алгебри ще наричаме просто -алгебри.
Нека (W, A) e измеримо пространство. Вероятност P в измеримото пространство наричаме всяка реална функция, дефинирана върху случайните събитията от A, която удоволетворява следните аксиоми:
 = Æ, имаме  = 0. (непрекъснатост в Æ)
При това положение тройката (W, A, P) наричаме вероятностно пространство. От аксиомите получаваме следните свойства:
P (  ) =  . (крайна адитивност)
7. За всеки An Î A, n = 1, 2, …, такива че Ai Aj = Æ при i ¹ j и  Î A имаме P () =  . (s-адитивност)
Теорема (Каратеодори): Всяка вероятност, дефинирана върху буловата алгебра A може да се продължи по единствен начин върху най-малката s-алгебра, която съдържа A. По-точно теоремата казва, че ако (W, A, P) е вероятностно пространство, където A е булова алгебра, то може да се построи по единствен начин вероятностно пространство (W, A, P¢), където A е най-малката s-алгебра, която съдържа A, така че P (A) = P¢ (A) за всяко A Î A. Така оттук нататък можем да считаме, че във всяко вероятностно пространство (W, A, P) имаме, че A е s-алгебра. Нека (W, A, P) е вероятностно пространство. Ще казваме, че функцията x : W à е случайна величина, ако за всяко x Î имаме, че Lx (x) = { w | x (w) < x } е случайно събитие, т.е. Lx (x) Î A. За всяка случайна величина x, дефинираме функцията
С други думи Fx (x) е вероятността случайната величина x да приеме стойност по-малка от x. Бележим още Fx (x) = P (x < x). По-нататък ще изпускаме индекса x и ще считаме, че той се подразбира. Свойства на функцията на разпределение:
Не е задължително, функцията на разпределение F (x) да бъде непрекъсната, въпреки че тя е непрекъсната отляво. В общия случай, F (x) има точки на прекъсване със скок. Лесно се вижда, че те са не повече от изброимо много. На всяка случайна величина се съпоставя функция на разпределение. Лесно се вижда, че това съпоставяне не е еднозначно. В теорията на вероятностите, обаче, често случайните величини с еднакви разпределения се считат за неразличими, т.е. пренебрегват се вероятностните пространства, в които случайните величини са реализирани. Казваме, че случайните величини x и h са независими, ако за всеки x, y Î имаме P (x < x Ç h < y) = P (x < x).P (h < y), бележим x ^ h. Казваме, че случайните величини x1, x2, …, xn са независими в съвкупност, ако за всеки x1, x2, …, xn Î имаме, че P (x1 < x1 Ç x2 < x2 Ç …Ç xn < xn) = = P (x1 < x1). P (x2 < x2). …. P (xn < xn). Ако x1, x2, …, xn са независими в съвкупност, то xi ^ xj при i j, т.е. те са независими по двойки. Обратното не е вярно, както лесно се показва с пример.
събития от A. Лесно се проверява, че дефиницията е коректна, т.е. дефинирата по този начин функция действително е случайна величина. Нека P (x = xi) = pi, i = 1, 2, …. Естествено, pi ³ 0 и За функцията на разпределение получаваме F (x) = P (x < x) = P (  ) =  =  .
В случая когато x1 < x2 < …< xn < … за x Î (xm, xm+1] имаме Каталог: fmi fmi -> Софтуерни технологии fmi -> Лекции и семинарни занятия по аналитична геометрия fmi -> 3d-алгоритъм на Chaikin fmi -> Лекции по увод в програмирането fmi -> Лекции и семинарни занятия по линейна алгебра fmi -> Конкурентно Програмиране fmi -> Лекции по компютърни мрежи и комуникации fmi -> Ще предпочетеш да наблюдаваш света отстрани или ще се присъединиш към най-голяма студентска организация? fmi -> Лекции по обектно-ориентирано програмиране Изтегляне 5.91 Mb. Сподели с приятели:
|
за всяко n = 0, 1, ….
= xn
. Като се използва, че
f () = 0 = и сходимостта на редицата { xn} към е доказана. Ясно е, че при методът на хордите итерационният процес е породен от следната функция :
. Уравнението f (x) = 0 е еквивалентно на уравнението x = (x). Ще приложим следствието от по-горе за дадем оценка за сходимостта на итерационния процес. 
=
= 
. Използвали сме, че f () = 0.
.(b - )2 и
.
, m = 
, m > 0. 
.(b - ). Така стига интервалът [a, b] да е достатъчно малък, | ()| може да стане по-малко от произволно отнапред избрано q < 1. Оттук по следствието от по-горе получаваме, че при достатъчно малък интервал, съдържащ корена, методът на хордите е сходящ със скоростта на геометрична прогресия.
= xn
.
.
. Ясно е, че при методът на допирателните, итерационният процес е породен от следната функция : (x) = x 
. Уравнението f (x) = 0 е еквивалентно на уравнението x = (x). Лесно се вижда, че () = 0. Също може да се покаже, че в общия случай () 0. Така от теоремата по-горе, ако интервалът [a, b] е достатъчно малък, методът на допирателните е сходящ и има ред на сходимост 2.
Î A;
Î A и Ai Î A, i = 1, 2, … Þ 
Î A.
.
= 1.