Анотация: Разположения без повторение. Пренареждания. Комбинации. Рекурентни отношения. Друг метод за доказване. Процесът на последователни дялове. Задача: „Трудност за майордомото“.
Поставяния без повторения
Има различни предмети. Колко от тях могат да бъдат подредени? В този случай две подредби се считат за различни, ако се различават една от друга поне в един елемент или се състоят от едни и същи елементи, но подредени в различен ред. Такива договорености се наричат поставяния без повторения, а броят им е означен с . Когато съставяме разположения без повторение на елементи, трябва да направим избор. На първата стъпка можете да изберете всеки от наличните елементи. Ако този избор вече е направен, тогава във втората стъпка трябва да изберете от останалите елементи. На -та стъпка от обекти. Следователно, съгласно правилото за произведение, намираме, че броят на -разположенията без повторение на обекти се изразява, както следва:
Пренареждания
При съставянето на аранжименти без повторения от елементи получихме аранжименти, които се различават един от друг както по състава, така и по реда на елементите. Но ако вземем подредби, които включват всички елементи, тогава те могат да се различават един от друг само по реда на елементите, включени в тях. Такива договорености се наричат пермутации на n елемента, или накратко, пермутации.
Комбинации
В случаите, когато не се интересуваме от реда на елементите в комбинация, а се интересуваме само от нейния състав, говорим за комбинации. И така, комбинациите от елементи са всякакви подредби, съставени от тези елементи и различаващи се един от друг по състав, но не и по реда на елементите. Броят на -комбинациите, които могат да бъдат съставени от елементи, се означава с .
Формулата за броя на комбинациите се получава от формулата за броя на разположенията. Всъщност, нека първо съставим всичко - комбинации от елементи и след това да пренаредим елементите, включени във всяка комбинация, по всички възможни начини. В този случай се оказва, че всички са разположения на елементи, всяко само веднъж. Но можете да правите комбинации от всяко! пермутации, а броят на тези комбинации е равен на . Така че формулата е правилна
От тази формула намираме това
Рекурентни отношения
При решаването на много комбинаторни задачи те използват метода за редуциране на даден проблем до проблем, включващ по-малък брой обекти. Извиква се методът за свеждане до подобен проблем за по-малък брой обекти метод на рекурентните отношения(от латинското "recurrere" - "да се върна").
Ние илюстрираме концепцията за рекурентни отношения с класически проблем, който беше поставен около 1202 г. от Леонардо от Пиза, известен като Фибоначи. Значението на числата на Фибоначи за анализа на комбинаторни алгоритми прави този пример доста подходящ.
Фибоначи постави проблема под формата на история за темпа на растеж на популацията на зайци при следните допускания. Всичко започва с една двойка зайци. Всяка двойка става плодородна след месец, след което всяка двойка ражда нова двойка зайци всеки месец. Зайците никога не умират и размножаването им никога не спира.
Нека е броят на двойките зайци в популацията след месеци и нека тази популация се състои от двойки потомци и „стари“ двойки, т.е. Така през следващия месец ще се случат следните събития: . Старото население в даден момент ще се увеличи с броя на ражданията в даден момент. 
. Всяка възрастна двойка в определен момент произвежда двойка потомство в даден момент. Този модел се повтаря през следващия месец:
Комбинирайки тези равенства, получаваме следната рекурентна връзка:
| (7.1) |
Изборът на началните условия за числовата редица на Фибоначи не е важен; Основното свойство на тази последователност се определя от рекурентната връзка. Ще приемем (понякога 
).
Нека погледнем този проблем малко по-различно.
Една двойка зайци ражда котило от две зайчета (женско и мъжко) веднъж месечно, а новородените зайчета вече носят потомство два месеца след раждането. Колко зайци ще се появят за една година, ако в началото на годината е имало една двойка зайци?
От условията на задачата следва, че след месец ще има две двойки зайци. След два месеца само първата двойка зайци ще роди, а ще бъдат 3 двойки. А след още един месец и оригиналната двойка зайчета, и появилата се преди два месеца двойка зайчета ще родят. Следователно ще има общо 5 чифта зайци. Нека означим с брой двойки зайци по месеци от началото на годината. Ясно е, че след няколко месеца ще има тези двойки и още толкова новородени двойки зайци, колкото е имало в края на месеца, тоест повече двойки зайци. С други думи, има връзка на повторение
| (7.2) |
Тъй като, по условие, и , Ние последователно намираме
В частност, 
.
Извикват се номерата Числата на Фибоначи. Те имат редица прекрасни свойства. Сега нека изведем израза за тези числа чрез . За да направим това, ще установим връзка между числата на Фибоначи и следната комбинаторна задача.
Намерете броя на последователностите, състоящи се от нули и единици, в които няма две последователни единици.
За да установим тази връзка, нека вземем всяка такава последователност и сравним чифт зайци с нея съгласно следното правило: единиците съответстват на месеците на раждане на една от двойките „предци“ на тази двойка (включително оригиналния) и нулите съответстват на всички останали месеци. Например последователността 010010100010 установява следната „генеалогия“: самата двойка се появява в края на 11-ия месец, нейните родители в края на 7-ия месец, „дядото“ в края на 5-ия месец и „великият -дядо” в края на втория месец. След това оригиналната двойка зайци се криптира с последователността 000000000000.
Ясно е, че в този случай две единици подред не могат да се появят в каквато и да е последователност - двойка, която току-що се е появила, не може, според условието, да роди потомство за един месец. Освен това, с определеното правило, различните двойки зайци съответстват на различни последователности и обратното, две различни двойки зайци винаги имат различна „генеалогия“, тъй като според условието женският заек ражда потомство, състоящо се само от един чифт зайци.
Установената връзка показва, че броят на -последователностите, притежаващи посоченото свойство, е равен на .
Нека сега докажем това
| (7.3) |
Къде , ако е нечетно и , ако е четно. С други думи, - цялата част от числото (в бъдеще ще означаваме цялата част от числото с ; по този начин, 
).
Всъщност това е броят на всички последователности от 0 и 1, в които няма две 1 съседни. Броят на такива последователности, които съдържат точно единици и нули, е равен на . Тъй като това трябва да се направи
Числата на Фибоначи.
При решаването на много комбинаторни задачи те използват метода за редуциране на дадена задача до задача, включваща по-малък брой елементи. Например, можете да извлечете формула за броя на пермутациите:
Това показва, че винаги може да се редуцира до факториел на по-малко число.
Добра илюстрация на изграждането на рекурентни отношения е проблемът на Фибоначи. В своята книга през 1202 г. италианският математик Фибоначи представя следния проблем. Една двойка зайци раждат две млади зайчета (женско и мъжко) веднъж месечно, а самите новородени зайчета раждат потомство два месеца след раждането. Колко зайци ще се появят за една година, ако в началото е имало една двойка зайци.
От условията на задачата следва, че след месец ще има две двойки зайци, след два месеца само първата двойка зайци, появила се преди два месеца, ще даде потомство, така че ще има общо 3 двойки зайци. След месец вече ще има 5 чифта. И така нататък.
Нека означим с брой двойки зайци по месеци от началото на годината. Тогава след един месец броят на двойките зайци може да се намери по формулата:
Тази зависимост се нарича рекурентна връзка . Думата „рекурсия“ означава връщане назад (в нашия случай връщане към предишни резултати).
По условие и , след това по отношение имаме: , , и т.н., .
Определение 1:Извикват се номерата Числата на Фибоначи . Това е добре известна поредица от числа в математиката:
1, 1, 2, 3, 5, 8, 13, 21, ...
В тази последователност всяко следващо число е сбор от двете предходни числа. И във връзката на повторение следващият член също се намира като сбор от двата предходни члена.
Нека установим връзка между числата на Фибоначи и комбинаторния проблем. Да кажем, че трябва да намерим редица последователности, състоящи се от нули и единици, в които няма две единици подред.
Нека вземем всяка такава последователност и съпоставим чифт зайци с нея съгласно следното правило: единиците съответстват на месеците на раждане на една от двойките „предци“ на тази двойка (включително оригиналния), а нулите съответстват на всички останали месеца. Например последователността установява такова „генеалогия“ – самата двойка се появява в края на 11-ия месец, родителите й в края на 7-ия месец, „дядото“ в края на 5-ия месец и „великият -дядо” в края на 2-рия месец. Първоначалната двойка е криптирана с последователността. В нито една последователност не могат да стоят две единици в един ред - двойка, която току-що се появи, не може да роди потомство след месец. Очевидно различни последователности съответстват на различни двойки и обратно.
По този начин броят на последователностите с посочените свойства е равен на .
Теорема 1:Числото се намира като сбор от биномни коефициенти:. Ако – странно, тогава . Ако – дори, тогава . В противен случай: – цяла част от числото .
Доказателство:Действително, е броят на всички поредици от 0 и 1, в които няма две 1-ци, съседни. Броят на такива последователности, съдържащи точно единици и нули, е равен на , след което варира от 0 до . Прилагайки правилото за сумата, получаваме тази сума.
Това равенство може да се докаже по различен начин. Да обозначим:
От равенството следва, че . Освен това е ясно, че. Тъй като и двете последователности и отговарят на рекурентната връзка, тогава , и .
Определение 2:Рекурентната връзка има поръчка , ако позволява изчисление чрез предишни членове на редицата: .
Например, е рекурентна връзка от втори ред и рекурентна връзка от 3-ти ред. Коефициентът на Фибоначи е връзка от втори ред.
Определение 3: Чрез решениерекурентна връзка е последователност, която удовлетворява тази връзка.
Ако е дадена рекурентна връзка от ред, тогава тя се удовлетворява от безкрайно много последователности, тъй като първите елементи могат да бъдат зададени произволно. Но ако първите елементи са дадени, тогава останалите членове се определят еднозначно.
Например, в допълнение към последователността 1, 1, 2, 3, 5, 8, 13, 21, ... обсъдена по-горе, съотношението на Фибоначи може да бъде удовлетворено и от други последователности. Например последователността 2, 2, 4, 8, 12,... е изградена по същия принцип. Но ако посочите началните членове (има 2 от тях в редицата на Фибоначи), тогава решението е еднозначно определено. Взети са толкова начални термини, колкото и редът на връзката.
Използвайки известни рекурентни отношения и начални членове, можем да изпишем членовете на редицата един след друг и по този начин да получим всеки от нейните членове. Но в много случаи нямаме нужда от всички предишни членове, а само от един конкретен член. В този случай е по-удобно да имате формула за тия член на редицата.
Ще кажем, че определена последователност е решение на дадена рекурентна релация, ако при заместване на тази последователност връзката е идентично изпълнена.
Например последователността е едно от решенията на релацията: . Това е лесно да се провери с просто заместване.
Определение 4:Решението на рекурентна връзка от ‑ти ред се нарича общ , ако зависи от произволни константи, променяйки които, може да се получи всяко решение на тази връзка.
Например за релацията общото решение ще бъде .
Всъщност е лесно да се провери, че това ще бъде решение на нашата връзка. Нека покажем, че всяко решение може да бъде получено в тази форма. Нека бъдат произволни.
Тогава ще има и такива, които
Очевидно за всяко , системата от уравнения има единствено решение.
Определение 5:Рекурентната връзка се нарича линеен , ако е написано във формата:
където са числените коефициенти.
Най-общо казано, няма общи правила за решаване на произволни рекурентни отношения. Съществуват обаче общи правила за решаване на линейни рекурентни отношения.
Нека първо разгледаме връзката от 2-ри ред.
Решението на тази връзка се основава на следните твърдения.
Теорема 2:Ако и - са решение на дадена рекурентна връзка от 2-ри ред, тогава за всякакви числа и последователността също е решение на тази връзка.
Теорема 3:Ако числото е корен на квадратно уравнение, тогава последователността е решение на рекурентната връзка.
От теореми 2, 3 следва следното правило за решаване на линейни рекурентни отношения от 2-ри ред.
Нека е дадена рекурентна връзка.
1) Да съставим квадратно уравнение, което се нарича Характеристика за дадено съотношение. Да намерим всичкокорени на това уравнение (дори многократни и сложни).
2) Нека създадем общо решение на рекурентната връзка. Структурата му зависи от вида на корените (те са еднакви или различни).
а) Ако тази връзка има две различни корении , тогава общото решение на връзката има формата .
Наистина, от теоремите 2, 3 следва, че - решение и система от уравнения
Има едно единствено решение, т.к като се има предвид, че .
Например за числата на Фибоначи имаме . Характеристичното уравнение има формата: . Решавайки последното уравнение, получаваме корените:, .
Ако всички корени на характеристичното уравнение са различни, тогава общото решение има формата: .
Ако, например, този корен съответства на решенията:
на тази рекурентна връзка. В общото решение този корен съответства на частта .
Например, решаване на рекурентната връзка:
Съставяме характеристично уравнение от вида: .
Корените му са... Следователно има общо решение.
Комбинаторни изчисления върху крайни множества
Въведение в комбинаториката
Предметът на теорията на комбинаторните алгоритми, често наричан комбинаторно изчисление, е изчислението върху дискретни математически структури. В тази теория се обръща много внимание на алгоритмичния подход за решаване на дискретни математически проблеми, оптимизиране на избора на опции и намаляване на броя на разглежданите решения.
Областта на комбинаторните алгоритми включва проблеми, които изискват преброяване (оценяване) на броя на елементите в крайно множество или изброяване на тези елементи в специален ред (Приложение Б). В този случай процедурата за избор на елементи с връщане и нейните варианти се използват широко.
Има два вида проблеми с броенето. В простия случай е посочен конкретен набор и той е необходим определете точно броя на елементитев него. В общия случай има семейство от множества, определени от някакъв параметър, а мощността на множеството се определя като функция на параметъра. В същото време често се случва достатъчна оценка на реда на функция, а понякога се нуждаете само от оценка на скоростта му на растеж. Например, ако силата на набора, който трябва да се разглежда, нараства експоненциално по някакъв параметър, тогава това може да е достатъчно, за да се откаже от предложения подход за изучаване на проблема, без да се занимава с различни подробности. Процедурите на асимптотични разширения, рекурентни отношения и генериращи функции се прилагат към този по-общ тип задачи.
Асимптотика
Асимптотата е специална линия (най-често права линия), която е границата на разглежданата крива.
Асимптотиката е изкуството да се оценяват и сравняват темповете на растеж на функциите. Казват, че когато х®¥ функция "се държи като х“, или „се увеличава със същата скорост като х", и когато х®0 "се държи като 1/ х". Казват, че "дневник хпри х®0 и всяко e>0 се държи като х e , и какво при н®¥ расте не по-бързо от ндневник н„Такива неточни, но интуитивни твърдения са толкова полезни при сравняване на функции, колкото и съотношенията<, £ и = при сравнивании чисел.
Нека дефинираме три основни асимптотични отношения.
Определение 1.функция f(х) е еквивалентен ж(х) при х® х 0, ако и само ако =1.
В този случай се казва, че функцията е f(х) е асимптотично равно на функцията ж(х) или какво f(х) нараства със същата скорост като ж(х).
Определение 2. f(х)=o( ж(х)) при х® х 0, ако и само ако =0.
Казват, че когато х® x 0 f(х) расте по-бавно от ж(х), или какво f(х) "има малко" от ж(х).
Определение 3 . f(х)=O( ж(х)) при х® х 0, ако и само ако има константа C, такава че sup = C.
В този случай те казват това f(х) расте не по-бързо от ж(х), или какво х® x 0 f(х) "има голямо О" от ж(х).
Съотношение f(х)=ж(х)+о(ч(х)) при х®¥ означава това f(x)-g(х)=о(ч(х)). По същия начин f(х)=ж(х)+ОТНОСНО(ч(х)) означава, че f(х)-g(х)=О(ч(х)).
Изразите O(·) и o(·) също могат да се използват в неравенства. Например неравенството х+о(х)£2 хпри х®0 означава, че за всяка функция f(х) така че f(х)=о(х), при х®¥ връзката е в сила x+f(х)£2 хза всички достатъчно големи стойности х.
Нека представим някои полезни асимптотични равенства.
Полиномът е асимптотично равен на своя водещ член:
при х®¥; (4.1)
при х®¥; (4.2)
при х®¥ и a k#0. (4.3)
Сумите от степени на цели числа удовлетворяват отношението:
при н®¥. (4.4)
Следователно, по-специално, имаме за н®¥
В по-общ случай, когато н®¥ и за всяко цяло число к³0
; (4.6)
. (4.7)
Рекурентни отношения
Ние илюстрираме концепцията за рекурентни отношения, като използваме класически проблем, поставен и изследван от Фибоначи около 1200 г.
Фибоначи поставя проблема си под формата на история за скоростта на нарастване на популация от зайци при следните предположения. Всичко започва с една двойка зайци. Всяка двойка зайци става плодородна след месец, след което всяка двойка ражда нова двойка зайци всеки месец. Зайците никога не умират и размножаването им никога не спира. Позволявам Fn- броят на двойките зайци в популацията след нмесеца и нека това население се състои от Nnдвойки потомци и На„стари“ двойки, т.е. Fn = Nn + На. Така през следващия месец ще се случат следните събития:
Старото население в ( н+1)-ият момент ще се увеличи с броя на ражданията в момента н, т.е. O n+1 = На + Nn= Fn;
Всеки стар в един момент ндвойката произвежда по време ( н+1) двойка потомство, т.е. Nn+1= Cn.
Този модел се повтаря през следващия месец:
О n+2 = O n+1+ Nn+1= Fn+1,
Nn+2=O n+1;
Комбинирайки тези равенства, получаваме рекурентната връзка на Фибоначи:
О n+2 + Nn+2=Fn+1 + O n+1,
Fn+2 = Fn+1 + Fn. (4.8)
Изборът на началните условия за числовата редица на Фибоначи не е важен; основните свойства на тази последователност се определят от рекурентната връзка (4.8). Обикновено се вярва F 0=0, F 1=1 (понякога се приема F 0=F 1=1).
Рекурентната връзка (4.8) е частен случай на хомогенни линейни рекурентни връзки с постоянни коефициенти:
x n = a 1 x n-1 + a 2 x n-2 +…a k x n-k, (4.9)
къде са коефициентите a iне зависят от нИ х 1, х 2, …, x kсе считат за дадени.
Има общ метод за решаване (т.е. намиране x nкато функции н) линейни рекурентни отношения с постоянни коефициенти. Нека разгледаме този метод, като използваме отношение (4.8) като пример. Нека намерим решение във формата
Fn=cr n (4.10)
с постоянна сИ r. Замествайки този израз в (4.8), получаваме
cr n + 2 = cr n+ 1 + cr n,
cr n(r n -r-1)=0. (4.11)
Означава, че Fn=cr nе решение, ако едно от двете с=0, или r= 0 (и следователно F n =0 за всички н), а също (и това е по-интересен случай) if r 2 - r -1=0 и константа спроизволен. Тогава от (4.11) следва
r= или r = . (4.12)
Числото “1.618” е известно като “златното” съотношение, тъй като от древни времена се смята, че триъгълник (правоъгълник) със страни 1 има най-приятните за окото пропорции.
Сумата от две решения на хомогенна линейна рекурентна връзка очевидно също е решение и всъщност може да се покаже, че общото решение на редицата на Фибоначи е
Fn= 
, (4.13)
къде са константите сИ с'се определят от началните условия. Като поставим F 0 =0 и F 1 =1, получаваме следната система от линейни уравнения:
, (4.14)
чието решение дава
° С = -° С" = . (4.15)
ПОВТОРЯЩИ СЕ ВРЪЗКИ
ПОВТОРЯЩИ СЕ ВРЪЗКИ
(от лат. recur-rens, gen. case recurrentis - връщане) - ф-лизи от същия тип, които свързват определени последователности, които следват една след друга (това може да бъде последователност от числа, функции и др.). В зависимост от естеството на обектите, свързани със системата, тези отношения могат да бъдат алгебрични, функционални, диференциални, интегрални и др.
Наиб. добре известният клас на R.s са рекурентни функции за специални функции.Да, за цилиндрични функции Z m (x)P. с. изглежда като
Позволяват според функцията Z m0 (x)намерете функции Zm(x)при T= T 0 b 1, T 0 б 2и т.н. или например чрез стойности на функция 
в определен момент х 0 . 0 намерете (при числени изчисления) стойността на която и да е от функциите
В същата точка (тук м 0 - всяко реално число).
д-р важен клас на R. s. дават множество методи за последователни приближения (вж. итерационен метод);Методите също са включени тук. теория на смущенията.
В квантовата механика има друг тип динамична система, която свързва вектори в Хилбертовото пространство на състоянията. Например стационарните хармонични осцилатори са параметризирани с неотрицателни цели числа. Съответните вектори, означени с , където н- цели, с разн нмогат да бъдат получени един от друг чрез действие на оператори за създаване а +и унищожение А:
Тези връзки могат да бъдат разрешени чрез изразяване на всеки вектор по отношение на (най-ниското енергийно състояние, h = 0):
Обобщение на тази конструкция е репрезентацията вторично квантуванев квантовата статистика механика и квантова теория на полето (вж Фокапространство).
Типичен пример за Р. с. в статистиката механика - уравнения за частични функции на разпределение, които образуват веригата на Боголюбов (вж. уравнения на Боголюбов);познаването на такива функции ви позволява да намерите всички термодинамични. характеристики на системата.
В квантовата теория на полето, динамично съдържащи се например в Функции на Грийн.За да ги изчислите, използвайте различни. приближения, най-често - изчисления по теория на смущенията. Алтернативен подход се основава на интегро-диференциал уравнения на Дайсън,които са R. системи: уравнението за двуточковата функция на Грийн съдържа четириточкова функция и т.н. Подобно на уравнението на Боголюбов, тази система може да бъде решена само чрез „разкъсване“ на веригата (мястото на „разкъсването“ обикновено се избира от физически съображения и определя какво се получава).
Друг вид R. s. в квантовата теория на полето - Ордата има идентичностив теориите габаритни полета.Тези идентичности също представляват верига от интегро-диференциални отношения, свързващи функциите на Грийн с различни. брой външни линии, p са следствие от калибровъчната инвариантност на теорията. Те играят решаваща роля при проверката на симетрията на габарита по време на процедурата. пренормиране.
И накрая, самата процедура също е повтаряща се процедура: на всяка стъпка (във всеки следващ цикъл) контрачленове,получени от изчисляване на диаграми с по-малко цикли (за повече подробности вижте R-операция).А. М. Малокостов.
Физическа енциклопедия. В 5 тома. - М.: Съветска енциклопедия. Главен редактор А. М. Прохоров. 1988 .
Вижте какво представляват „Повтарящите се връзки“ в други речници:
рекурентни отношения- - [L.G.Sumenko. Английско-руски речник по информационни технологии. M .: Държавно предприятие TsNIIS, 2003.] Теми информационни технологии като цяло EN повтарящи се отношения ... Ръководство за технически преводач
- (функции на Вебер) общо име за специални функции, които са решения на диференциални уравнения, получени чрез прилагане на метода на разделяне на променливи за уравнения на математическата физика, като уравнението на Лаплас, уравнението ... ... Wikipedia
Или римата за броене на Йосиф Флавий, известен математически проблем с исторически нюанси. Задачата се основава на легендата, че отрядът на Йосиф Флавий, защитаващ град Йодфат, не искал да се предаде на превъзхождащите сили на римляните, които блокирали пещерата.... ... Wikipedia
Пафнутий Лвович Чебишев В математиката поредица от ортогонални полиноми е безкрайна поредица от реални полиноми... Wikipedia
Тази статия се предлага за изтриване. Обяснение на причините и съответната дискусия можете да намерите на страницата на Уикипедия: За изтриване / 22 ноември 2012 г. Докато процесът на дискусия е ... Уикипедия
Последователността на Падован е цяло число P(n) с начални стойности и линейна рекурентна връзка. Първите стойности на P(n) са 1, 1, 1, 2, 2, 3, 4, 5, 7. , 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265 ... Wikipedia
Полиномите на Ермит от определен тип са последователност от полиноми на една реална променлива. Полиномите на Ермит възникват в теорията на вероятностите, комбинаториката и физиката. Тези полиноми са кръстени на Чарлз Ермит. Съдържание 1... ...Уикипедия
- (функции на Бесел) решения Zv(z) Уравнение на Бесел, където параметър (индекс) v е произволно реално или комплексно число. В приложенията по-често се среща уравнение, зависещо от четири параметъра: чиито решения са изразени чрез C... Физическа енциклопедия
Метод за решаване на система от линейни алгебрични системи. уравнения A x = b с ермитова неизродена матрица A. Сред директните методи той е най-ефективен, когато се реализира на компютър. Изчислителната схема на метода обикновено се основава на ермитова факторизация... ... Математическа енциклопедия
Модифицираните функции на Бесел са функции на Бесел на чисто въображаем аргумент. Ако диференциалното уравнение на Бесел се замени с, то ще приеме формата Това уравнение се нарича модифицирано уравнение на Бесел ... Wikipedia
С голям обем данни от наблюдения хкрайните методи за решаване на уравнението на вероятността водят до значителни изчислителни трудности, свързани с необходимостта да се запомнят голям брой първоначални данни и междинни резултати от изчисленията. В това отношение от особен интерес са повтарящите се методи, при които оценката на максималната вероятност се изчислява на стъпки с постепенно нарастваща точност, като всяка стъпка е свързана с получаване на нови данни от наблюдението, а повтарящата се процедура е конструирана по такъв начин, че да съхранява в паметта възможно най-малкото количество данни от предишните стъпки. Допълнително и много значимо от практическа гледна точка предимство на рекурентните методи е тяхната готовност да дадат резултат на всяка междинна стъпка.
Това прави препоръчително използването на рекурентни методи дори в случаите, когато е възможно да се получи точно решение на уравнението на максималната вероятност чрез крайния метод и ги прави още по-ценни, когато е невъзможно да се намери точен аналитичен израз за оценка на максимума вероятност.
Нека наборът от данни за наблюдение е последователност, за да опишем, която въвеждаме вектор. (Както винаги, всеки негов компонент от своя страна може да бъде вектор, сегмент от случаен процес и т.н.). Нека е функцията на вероятността и
неговият логаритъм. Последният винаги може да бъде представен във формата
Логаритъмът на функцията на вероятността за съвкупност от данни от наблюдение без последната стойност и
Логаритъм от условната плътност на вероятността на стойността за дадени стойности на и .
Представянето (7.5.16) за логаритъма на функцията на вероятността е основата за получаване на повтаряща се процедура за изчисляване на оценката на максималната вероятност. Нека разгледаме редовния случай. В този случай оценката на максималната вероятност може да бъде намерена като решение на уравнението
което се различава от (7.1.6) само с въвеждането на индекса p yлогаритъм на функцията на вероятността.
Нека обозначим решението на това уравнение, като подчертаем, че тази оценка е получена от набор от данни от наблюдения. По същия начин, нека обозначим с решението на уравнението оценката на максималната вероятност, получена от съвкупността от данни.
Уравнение (7.5.19) може да бъде пренаписано, като се вземе предвид (7.5.16) в следната форма:
Нека разширим лявата страна на (7.5.20) в серия на Тейлър в околност на точката . При което
(7.5.22)
Градиентният вектор на функцията в точката ; членът става нула поради факта, че , е решение на уравнението на вероятността за предишното (P - 1ва стъпка:
Симетрична матрица на вторите производни на логаритъма на функцията на вероятността в точката , взета с противоположен знак, неписаните членове на разширението имат квадратичен и по-висок порядък на малкост спрямо разликата . Пренебрегвайки последните, получаваме следното приблизително решение на уравнението на максималната вероятност:
където е обратната матрица.
Това решение е представено под формата на рекурентна връзка, която определя следващата стойност на оценката чрез оценката на предишната стъпка и корекцията , в зависимост от наличните данни от наблюдение директно и чрез предишна оценка. Корекцията се формира като произведение на градиента на логаритъма на условната плътност на вероятността на новополучената стойност х n в точка, равна на предишната оценка, към тегловната матрица . Последният се определя от израза (7.5.23) и също зависи от оценката на предходната стъпка, а зависимостта му от нови данни от наблюдение се определя изцяло от формата на логаритъма на условната плътност на вероятността.
Формата на връзката (7.5.24) е много подобна на (7.5.8), която прилага итеративен метод за изчисляване на оценката на максималната вероятност, използвайки метода на Нютон. В действителност обаче те са значително различни един от друг. В (7.5.8) корекцията към предишната прогнозна стойност се определя от градиента на логаритъма на цялата функция на вероятността, която винаги зависи от всички налични данни от наблюдение, което изисква запаметяване на целия този набор. В съответствие с (7.5.24), корекцията към се определя от големината на градиента, който, поради свойствата на условната плътност на вероятността, всъщност зависи само от тези стойности (), които са в силна статистическа връзка с хн. Тази разлика е следствие от специалния избор на предишното приближение като оценка на максималната вероятност, намерена от набор от данни за наблюдение, намалени с една стойност, и е особено изразена за независими стойности на (). В този последен случай
поради което зависи само от и х n , а градиентът е само от предишната стойност на оценката и новополучените на П- mstep от данните за наблюдение. Следователно, с независими стойности, за да се формира вектор, не е необходимо да се помни никаква друга информация от предишната стъпка, освен стойността за оценка.
По същия начин, в случай на последователност на Марков от данни за наблюдение, т.е
векторът зависи само от текущата и една предишна стойност. В този случай, за изчислението, е необходимо да запомните от предишната стъпка, в допълнение към стойността, само стойността, но не целия набор от данни за наблюдение, както при итеративната процедура. Като цяло изчислението може да изисква съхраняване на по-голям брой предишни стойности (), но поради необходимостта да се вземат предвид само онези стойности, които са статистически зависими, този брой почти винаги е по-малък от общия обем от данните от наблюдението. По този начин, ако векторът описва времева последователност, тогава броят на членовете на тази последователност, които трябва да бъдат запомнени, се определя от нейното време на корелация и техният относителен дял намалява обратно пропорционално н, както в случая на независими ценности.
Нека сега разгледаме структурата на тегловната матрица, включена в рекурентната връзка (7.5.24). Според дефиницията (7.5.23), поради наличието на член, той, най-общо казано, зависи от всички стойности дори и с независими стойности на , което лишава рекурентната връзка (7.5.24) от предимствата свързани с възможно намаляване на количеството данни, съхранени от предишната стъпка. Има няколко начина за приблизително изчисление на матрицата , които отстраняват този недостатък.
Първият от тях се основава на по-последователно използване на основното предположение за малка разлика между двете следващи стойности на оценката и , което е основата за получаване на рекурентната връзка (7.5.24). Това ни позволява да получим подобна рекурентна връзка за матрицата на теглото. Наистина, използвайки малкостта от (7.5.23), имаме
Чрез въвеждане на обозначението
от (7.5.24) и (7.5.25) получаваме система от рекурентни отношения за векторната и тегловната матрица
Тази система, заедно с първоначалните стойности, напълно определя стойността на оценката на всяка стъпка, като изисква на всяка от тях да се изчисли само градиентът и матрицата на вторите производни на логаритъма на условната плътност на вероятността за текущата наблюдавана стойност. Първоначалните стойности се избират, като се вземат предвид наличните априорни данни за възможните стойности и диапазон на изменение на параметрите, а при пълна липса на тези данни те се приемат като нула (,).
За независими стойности системата от рекурентни отношения (7.5.27) очевидно описва многомерен (размерен) случаен процес на Марков, чийто компонент се сближава с истинската стойност на параметъра , а компонентът се сближава с информационната матрица на Фишер (7.3. 8), където е истинската стойност на оценения параметър и се увеличава неограничено с растежа П.Системата (7.5.27) има подобни свойства на конвергенция при по-общи условия, ако последователността е ергодична.
Вторият от споменатите методи се основава на замяна на матрицата на вторите производни на логаритъма на функцията на вероятността с нейното математическо очакване - информационната матрица на Фишер, която, като се вземе предвид (7.5.16), може да бъде записана като:
където е подобно на (7.5.26)
Заменяйки матрицата в (7.5.24) с матрицата , получаваме рекурентната връзка
за приблизителното изчисляване на оценките на максималната вероятност, предложени от Sakrison (в оригинала за независими еднакво разпределени , когато и . Тази рекурентна връзка е по-проста от системата (7.5.27), тъй като оптималната матрица на теглото е заменена от нейната математическа очакване и съществуващите данни от наблюдение не са необходими за намирането му, с изключение на тези, които са концентрирани в стойността на оценката. В същото време е очевидно, че такава замяна означава необходимост от изпълнение на допълнително изискване в сравнение с (. 7.5.27), че матрицата на вторите производни е близка до нейното математическо очакване.
Ако функцията за плътност на вероятността и матрицата се променят от стъпка на стъпка, директното намиране на всяка стъпка може да изисква твърде много изчисления. В този случай, поради допълнително намаляване на точността на резултатите, определено от неравенството на малки разлики до нула, може да се пристъпи към периодично изчисляване на приблизителната стойност на матрицата. Връщайки се към предишното обозначение за тази приблизителна стойност, получаваме друга система от рекурентни отношения
Очакваната стойност на матрицата (информационна матрица на Фишер за едно наблюдение), взета в точка . Тази система се различава от (7.5.27) по това, че второто от рекурентните отношения (7.5.31) не включва директно данни от наблюдение.
Всяка от системите на рекурентни отношения, разгледани по-горе, е напълно точна, ако функцията зависи квадратично от , и освен това матрицата на вторите производни не зависи от . Всъщност това съответства на случай на независими нормално разпределени (не непременно идентични) стойности с неизвестно математическо очакване, което представлява оценения параметър.
Системата от рекурентни отношения (7.5.24) дава точно решение на уравнението на максималната вероятност при много по-широки условия с единственото изискване функцията да зависи квадратично от . Освен това зависимостта от е произволна, което съответства на широк клас от разпределения на вероятността на популацията с независими и зависими стойности.
Наред с разглежданите общи методи, съществуват редица методи за избор на матрица от тегловни коефициенти в рекурентната връзка (7.5.24), адаптирани към определени специфични ограничения. Най-простият от тях е изборът под формата на диагонална матрица, така че , ( аз- единична матрица), където е намаляваща последователност от числени коефициенти, избрани независимо от свойствата на функцията на вероятността по същия начин, както в процедурата за стохастична апроксимация на Робинс-Монро, която ще бъде обсъдена в следващите глави.
Струва си да се отбележи, че всички итеративни или повтарящи се процедури за намиране на оценки на максималната вероятност обикновено са приблизителни. Следователно, най-общо казано, за оценките, получени в резултат на прилагането на тези процедури, последователността, асимптотичната ефективност и асимптотичната нормалност трябва да бъдат доказани наново. За итеративните процедури необходимите свойства на оценките са гарантирани от факта, че по принцип такива процедури, с подходящия брой повторения, осигуряват решение на уравнението на вероятността с произволна предварително определена точност. Има специални доказателства за повтарящи се процедури като (7.5.27), (7.5.30), (7.5.31) и други. В същото време, в допълнение към изискването за редовност, се налагат някои допълнителни изисквания:
Относно поведението на функция (7.2.2) за различни стойности на ||, за постигане, използвайки повтаряща се процедура, глобален максимум на тази функция в точката, съответстваща на истинската стойност на параметъра;
По реда на нарастване на вторите моменти на производните на логаритъма на правдоподобната функция за големи абсолютни стойности. Тези изисквания са следствие от по-общи условия за сходимост към точка на всички или част от компонентите на марковски случаен процес, до който води една или друга повтаряща се процедура.
В заключение също така отбелязваме, че в случай, че има точно решение на уравнението на максималната вероятност, то почти винаги може да бъде представено в повтаряща се форма. Нека дадем два прости и различни примера. По този начин, елементарна оценка на неизвестното математическо очакване на нормална случайна променлива в популацията ннеговите примерни стойности под формата на средноаритметично
е оценка на максималната вероятност и може да бъде представена в повтаряща се форма:
което е най-простият частен случай (7.5.30) с
Друг пример е нередовната оценка на максималната вероятност за параметъра - ширината на правоъгълното разпределение - от (7.4.2), която също може да бъде определена чрез рекурентната връзка
с началното състояние. Тази рекурентна връзка е от различен тип: нейната дясна страна не може да бъде представена като сбор от предишната оценка и малка корекция, което е следствие от неправилността на този пример; той обаче има всички предимства на повтарящия се подход: той изисква запаметяване само на едно число от предишната стъпка - оценката - и рязко намалява търсенето до едно сравнение, вместо да сравнява всички стойности.
Дадените примери илюстрират предимствата на рекурентните методи дори в случаите, когато уравнението на максималната вероятност позволява точно решение, тъй като простотата на аналитичното представяне на резултата не е идентична с изчислителната простота на получаването му.
7.5.3. Преход към непрекъснато време. Диференциални уравнения за оценители на максимална вероятност
Нека сега разгледаме специалния случай, когато наличните данни от наблюдение хне са описани от набор от примерни точки , a представлява сегмент от изпълнението на някакъв процес , в зависимост от зададените параметри на интервала , и дължината на този интервал може да се увеличи по време на наблюдение (времева точка Tе променлива).
За статистическо описание на данните от наблюдението в този случай се въвежда функционал на съотношението на вероятността, което е границата при , max на съотношението на разпределението на плътността на вероятността на набор от стойности при произволно зададена стойност към подобна вероятност плътност при определена фиксирана стойност и в някои случаи, когато позволява представянето на , където е случаен процес , независим от , до плътността на вероятността на набор от стойности, при условие че . Използването на функционала на съотношението на вероятността ни позволява да елиминираме формалните трудности при определяне на плътността на вероятността, които възникват при преминаване към непрекъснато време.
Логаритъмът на функционала на отношението на вероятността може да бъде представен като
където е някакъв функционал на процеса на интервала. В някои случаи функционалът се изражда във функция, която зависи само от стойността на . Така че, ако
където е известна функция на времето и параметрите и е делта-корелиран случаен процес („бял“ шум) със спектрална плътност н o , след което избираме като знаменател съотношението на вероятността на разпределението на вероятностите хв , ще имаме
Нека е оценката на максималната вероятност на параметъра, конструирана от изпълнението на процеса на интервала, т.е. решението на уравнението на максималната вероятност
Диференцирайки лявата страна на това уравнение по отношение на времето, получаваме
Въвеждане на обозначения
и решавайки уравнение (7.5.42) за , получаваме диференциално уравнение за оценка на максималната вероятност
Матрицата от своя страна съгласно (7.5.37) се определя от диференциалното уравнение
Точно както в дискретния случай, матрицата в (7.5.45), (7.5.47) може да бъде заменена с нейното математическо очакване - информационната матрица на Фишер при стойността на , и диференциалното уравнение (7.5.46) за теглото матрица - по уравнението
където подобно на дискретния случай
Математическо очакване на матрицата на вторите производни.
Наборът от диференциални уравнения (7.5.45), (7.5.46) или (7.5.45), (7.5.48), заедно с началните условия, по отношение на избора на които всичко казано за дискретния случай остава в сила, напълно определя оценката на максималната вероятност за всеки момент от времето. Този набор може да бъде моделиран с помощта на подходящи, най-общо казано, нелинейни аналогови устройства или, с подходяща времева дискретизация, решен с помощта на компютър. В заключение, нека отбележим една от модификациите на тези уравнения, която ни позволява да избегнем необходимостта от обръщане на матрицата.
Представяне на обозначението
, Където аз
и разграничаване по отношение на времето на връзката , Където азе матрицата на идентичност, като използваме (7.5.46) получаваме диференциално уравнение, което директно определя матрицата:
(и по подобен начин, когато се замени с), което заедно с уравнение (7.5.45)
определя оценката , без да се изисква инверсия на матрицата. В този случай има преход от най-простото линейно диференциално уравнение (7.5.46) към нелинейно относително диференциално уравнение (7.5.51) от типа на Рикати.