занаяти

повтарящи се методи. Общи и частни решения на рекурентни отношения Изчисляване на детерминантите на порядъка n по метода на рекурентните отношения

С голямо количество данни от наблюдения хкрайните методи за решаване на уравнението на вероятността водят до значителни изчислителни трудности, свързани с необходимостта от запомняне на голям брой първоначални данни и междинни резултати от изчисленията. В тази връзка особен интерес представляват повтарящите се методи, при които оценката на максималната вероятност се изчислява на стъпки с постепенно нарастваща точност, всяка стъпка е свързана с получаване на нови данни от наблюдение, а повтарящата се процедура е конструирана по такъв начин, че да се съхранява в памет колкото е възможно по-малко данни от предишните стъпки. Допълнително и много значително предимство от практическа гледна точка на рекурсивните методи е готовността за издаване на резултат на всяка междинна стъпка.

Това прави целесъобразно използването на рекурентни методи дори в случаите, когато е възможно да се получи точно решение на уравнението за максимална вероятност чрез краен метод, и ги прави още по-ценни, когато е невъзможно да се намери точен аналитичен израз за оценка на максималното вероятност.

Нека наборът от данни за наблюдение е последователност, за чието описание въвеждаме вектора. (Както винаги, всеки негов компонент от своя страна може да бъде вектор, сегмент от произволен процес и т.н.). Нека е функцията на вероятността и

неговия логаритъм. Последният винаги може да бъде представен като

Лог-вероятността на набора от данни от наблюдение без последната стойност и

Логаритъмът на условната плътност на вероятността на стойността за дадени стойности на и .

Представянето (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 , а градиентът е само от предишната стойност на оценката и новополучената П-Стъпка на данните за наблюдение. Следователно, за независими стойности, за да се образува вектор, не е необходимо да се съхранява никаква друга информация от предишната стъпка, освен стойността на оценката.

По същия начин, в случай на марковска последователност от данни за наблюдение, т.е. кога

векторът зависи само от , текущата и една предишна стойност . В този случай за изчислението е необходимо да запомните от предишната стъпка в допълнение към стойността само стойността , но не и целия набор от данни за наблюдение, т.к. в итеративната процедура. Като цяло изчислението може да изисква съхраняване на по-голям брой предишни стойности (), но поради необходимостта да се вземат предвид само тези стойности, които са статистически зависими от , този брой почти винаги е по-малък от общия обем на набора от данни за наблюдение. Така че, ако вектор описва времева последователност, тогава броят на запомнените членове на тази последователност се определя от времето на нейната корелация и техният относителен дял намалява обратно пропорционално н, както в случая на независими стойности.

Нека сега разгледаме структурата на матрицата на теглото, включена в рекуррентното отношение (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) с матрицата , получаваме рекуррентното отношение

за приблизителното изчисляване на оценките за максимална вероятност, предложени от Сакрисън (в оригинала за независими идентично разпределени , когато и . Тази рекурентна връзка е по-проста от системата (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. Преход към непрекъснато време. Диференциални уравнения за оценки на максимална вероятност

Нека сега разгледаме един специален случай, при който наличните данни от наблюдение хне са описани от набор от примерни точки , но представляват сегмент от изпълнението на някакъв процес , в зависимост от параметрите, дадени на интервала , освен това дължината на този интервал може да се увеличи по време на наблюдение (време те променлива).

За статистическо описание на данните от наблюдението в този случай се въвежда функционалът на съотношението на вероятността, което е границата при , 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) от типа Рикати.

Комбинаторни изчисления върху крайни множества

Въведение в комбинаториката

Предмет на теорията на комбинаторните алгоритми, често наричани комбинаторни изчисления, са изчисления върху дискретни математически структури. В тази теория се отделя голямо внимание на алгоритмичния подход за решаване на задачи от дискретна математика, оптимизиране на изброяването на опциите и намаляване на броя на разглежданите решения.

Областта на комбинаторните алгоритми включва задачи, които изискват преброяване (оценяване) на броя на елементите в крайно множество или изброяване на тези елементи в специален ред (Приложение Б). В този случай процедурата за избор на елементи с връщане и нейните варианти са широко използвани.

Има два вида проблеми с броенето. В простия случай е даден специфичен набор и той е задължителен определете точния брой елементив него. В общия случай има семейство от множества, дефинирани от някакъв параметър, а мощността на множеството се дефинира като функция на параметъра. В същото време е често достатъчна оценка на реда на функциятаи понякога ти трябва само оценка на темпа му на растеж. Например, ако мощността на разглеждания набор нараства експоненциално в някакъв параметър, тогава това може да е достатъчно, за да се изостави предложения подход за изследване на проблема, без да се навлиза в различни подробности. За този по-общ тип задача се прилагат процедурите на асимптотични разложения, рекурентни отношения и генериращи функции.

Асимптотика

Асимптотата е специална линия (най-често права линия), която е границата за разглежданата крива.

Асимптотиката е изкуството да се оценяват и сравняват темповете на растеж на функциите. Казват, че при х®¥ функцията "се държи като х", или "нараства със същата скорост като х“, и при х®0 "се държи като 1/ х". Казват, че "дневник хв х®0 и всяко e>0 се държи като хд и какво н®¥ расте не по-бързо от ндневник н". Такива неточни, но интуитивно ясни твърдения са полезни при сравняване на функции по същия начин като отношенията<, £ и = при сравнивании чисел.

Нека дефинираме три основни асимптотични отношения.

Определение 1.Функция е(х) е еквивалентно на ж(х) при х® x0, ако и само ако =1.

В този случай се казва, че функцията е е(х) е асимптотично равно на функцията ж(х) или какво е(х) расте със същата скорост като ж(х).

Определение 2. е(х)=о( ж(х)) в х® x0, ако и само ако =0.

Казват, че при х® x 0 е(х) расте по-бавно от ж(х), или какво е(х) "има o-малък" от ж(х).

Определение 3 . е(х)=О( ж(х)) в х® x0, ако и само ако съществува константа C такава, че sup =C.

В този случай те казват това е(х) расте не по-бързо от ж(х), или каквото и да е х® x 0 е(х) "има голямо О" от ж(х).

Съотношение е(х)=ж(х)+о(з(х)) в х®¥ означава това е(x)-g(х)=о(з(х)). по същия начин е(х)=ж(х)+ОТНОСНО(з(х)) означава, че е(х)-ж(х)=О(з(х)).

Изразите O( ) и o( ) могат да се използват и в неравенствата. Например неравенството х+о(х)£2 хв х®0 означава, че за всяка функция е(х) такъв, че е(х)=о(х), при х®¥ x+f(х)£2 хза всички достатъчно големи стойности х.

Нека представим някои полезни асимптотични равенства.

Полиномът е асимптотично равен на най-големия му член:

в х®¥; (4.1)

в х®¥; (4.2)

в х®¥ и а к№ 0. (4.3)

Сумите от степени на цели числа удовлетворяват съотношението:

в н®¥. (4.4)

Следователно, по-специално, имаме н®¥

В по-общ случай, когато н®¥ и за всяко цяло число к³0

; (4.6)

. (4.7)

Повтарящи се отношения

Нека илюстрираме концепцията за рекурентни отношения с класическия проблем, поставен и изследван от Фибоначи около 1200 г.

Фибоначи постави своя проблем под формата на разказ за скоростта на растеж на популацията от зайци при следните допускания. Всичко започва с един чифт зайци. Всяка двойка зайци става плодородна (фертилна) след месец, след което всяка двойка ражда нова двойка зайчета всеки месец. Зайците никога не умират и тяхното размножаване никога не спира. Нека бъде F n- броят на двойките зайци в популацията след нмесеца и нека тази популация се състои от N nдвойки котило и На„стари” двойки, т.е. F n = N n + На. Така през следващия месец ще се случат следните събития:

Старо население в ( н+1)-ти момент ще се увеличи с броя на ражданията в момента н, т.е. O n+1 = На + N n= F n;

Всеки стар в даден момент ндвойката произвежда навреме ( н+1) двойка потомци, т.е. Nn+1= C n.

Следващия месец този модел се повтаря:

O n+2 = O n+1+ Nn+1= Fn+1,

Nn+2=O n+1;

комбинирайки тези равенства, получаваме рекурентното отношение на Фибоначи:

O n+2 + Nn+2=Fn+1 + O n+1,

Fn+2 = Fn+1 + F n. (4.8)

Изборът на начални условия за последователността на Фибоначи не е важен; съществените свойства на тази последователност се определят от рекурентното съотношение (4.8). Обикновено се вярва F0=0, F1=1 (понякога F0=F1=1).

Рекурентното отношение (4.8) е специален случай на хомогенни линейни рекурентни отношения с постоянни коефициенти:

x n = a 1 x n-1 + a 2 x n-2 +…a k x n-k , (4.9)

където коефициентите а ине зависи от нИ х 1, x2, …, x kсе считат за дадени.

Има общ метод за решаване (напр x nкато функция н) линейни рекуррентни отношения с постоянни коефициенти. Нека разгледаме този метод като използваме релация (4.8) като пример. Намираме решение във формата

F n=crn (4.10)

с постоянен отИ r. Замествайки този израз в (4.8), получаваме

кр + 2 = crn+ 1 + crn,

crn(rn-r-1)=0. (4.11)

Означава, че F n=crnе решение, ако едното и другото от=0, или r= 0 (и следователно F n =0 за всички н), а също (а това е по-интересен случай), ако r 2 - r -1=0, и константата отпроизволен. Тогава от (4.11) следва

r= или r = . (4.12)

Числото "1,618" е известно като "златното" съотношение, тъй като от древни времена се е смятало, че триъгълник (правоъгълник) със страни 1 има най-приятните за окото пропорции.

Сборът от две решения на хомогенна линейна повторяемост очевидно също е решение и всъщност може да се покаже, че общото решение на последователността на Фибоначи е

F n= , (4.13)

къде са константите отИ от'се определят от началните условия. Поставяйки F 0 =0 и F 1 =1, получаваме следната система от линейни уравнения:

, (4.14)

чието решение дава

° С = -° С" = . (4.15)

Линейни рекуррентни отношения с постоянни коефициенти. Основни дефиниции и примери за рекуррентни отношения Често решението на една комбинаторна задача може да бъде сведено до решаване на подобни проблеми с по-малка размерност с помощта на някаква връзка, наречена рекурренция от латинската дума recurrere - да се върна. По този начин решението на сложен проблем може да бъде получено чрез последователно намиране на решение на по-лесни проблеми и след това преизчисляване според рекурентните отношения, за да се намери решение на труден проблем. Рецидивната връзка на...

Споделяйте работата си в социалните мрежи

Ако тази работа не ви устройва, в долната част на страницата има списък с подобни произведения. Можете също да използвате бутона за търсене

Аранов Виктор Павлович Дискретна математика. Раздел 2. Елементи на комбинаториката.

Лекция 5

Лекции 5. МЕТОД НА ПОВТОРЯЩИ се се ВРЪЗКИ

План на лекцията:

Основни дефиниции и примери за повтарящи се отношения.
Линейни рекуррентни отношения с постоянни коефициенти. Формула

Бине.

Основни дефиниции и примери за рекурентни отношения

Често решението на една комбинаторна задача може да се сведе до решаването на подобни проблеми с по-ниско измерение, като се използва някаква връзка, наречена рекаР наем (от латинската думаповтарят се - връщане). По този начин решение на сложен проблем може да бъде получено чрез последователно намиране на решение на по-лесни проблеми и освен това, nд изчислявайки чрез рецидивни отношения, намерете решение на труден проблем.

Рекурентното отношение от -ти редмежду елементите на поредица от числа се нарича формула на формата

(1)

Частно решениерецидивната връзка е всеки приемникб отношение, което превръща отношението (1) в идентичност. Отношение (1) имд има безкрайно много конкретни решения, тъй като първите елементи са последователниотносно sti може да се задава произволно. Например, последователността е pд повтаряща се връзкаотносно решения, тъй като идентичността е валидна.

Извиква се решението на рекурентната връзка от -ти редобщ, ако е за a зависи от произволни константи и чрез избор на тези константи можемдобре но получи някакво решение на тази връзка. Например за съотношенията e niya

(2)

общото решение би било

. (3)

Наистина, лесно е да се провери, че последователността (3) превръща отношението (2) в тъждество. Следователно е необходимо само да се покаже, че всяко решение на отношение (2) можедобре но представят във формата (3). Но всяко решение на тази връзка е еднозначно определено.т със стойности и. Следователно трябва да докажем, че за всякакви числа и има mно кои стойности и какви

Тъй като тази система има решение за всякакви стойности на и, то решението (3) наистина е общо решение на отношение (2).

Пример 1 . Числа на Фибоначи.През 1202 г. известният италиански математик Леотносно Нардо от Пиза, който е по-известен с прякора си Фибоначи ( Fib o nacci - съкратено filius Bonacci син на Боначи), е написана книга „ Liber abacci "(" Книга и ха за сметалата"). Тази книга е достигнала до нас във втората си версия, която датира от 1228 г. Нека разгледаме един от многото проблеми, дадени в тази книга.

Двойка зайци носи веднъж месечно потомство от две зайчета (женско и мъжко) и т.н.И отколкото новородените зайци, два месеца след раждането, вече носят потомство. Колко зайци ще се появятд res година, ако в началото на годината имаше една двойка зайци?

От условието на задачата следва, че след месец ще има две двойки зайци. Два месеца по-късноаз само първата двойка зайци ще даде потомство, а вие ще получите 3 двойки.А след друг месец както оригиналната двойка зайци, така и двойката зайци, които се появиха преди два месеца, ще дадат потомство. Следователно ще има общо 5 двойки зайци и т.н.

Означете с броя на двойките зайци след месеци от началото на rотносно да. След месеци ще има тези двойки и още толкова много новородени двойки.относно лица, колко имаше в края на тия месец, тоест повече двойки. По този начин има rд текущото съотношение

. (4)

Тъй като тогава последователно намираме: и т.н. Тези числа съставляват последователността

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…,

Нареченблизо до Фибоначи и неговите членове - Числа на Фибоначи. Те имат редица прекрасни свойства. Числата на Фибоначи са свързани със следния комбинаторно трудна задача.

Намерете броя на двоичните думи с дължина, в които няма две единициг ред.

Да наречем тези думиправилно и означете техния брой с . Нека разделим набора от тези редовни думи на два класа: думи, завършващи на нула и думи, завършващи на едно. Нека да обозначим броя на думите в тези класове ит отговорен. Според правилото за събиране

(5)

Очевидно за дума, завършваща на нула, първите знаци образуват редовна дума с дължина, или с други думи, има биекция между набора от думи с регулярна дължина, завършващи на нула, и набора от думи с нормална дължина, т.е.

Ако думата с валидна дължина завършва с единица, тогава предишният знак на тази дума трябва да е нула, а първите знаци трябва да образуват дума с валидна дължина. Както и в предишния случай, ние отново имаме биекция между набора от редовни думи с дължина, завършващи на единица, и набора от редовни думи с дължина. Следователно. . От формула (5) получаваме рекурсивното отношениеотносно

. (6)

За да се използва рекурентното отношение, е необходимо за това изчислениеот промяна на всички предишни стойности. Например, ако трябва да знаем броя на правилатаб думи от 10 знака, то може да бъде намерено чрез последователно попълване на следната таблица b лице:

маса 1

Първите две стойности се намират директно (-думи 0 и 1; - думи 000, 010, 101), а останалите - по формула (6).

Пример 2 Проблемът с поставянето на скоби в израз с неасоциативен кошоперация. Нека “” означава някаква двоична операция. Помислете зас израз, в който символ означава някаква двоична неасоциацияно активна работа. Колко различни начини за подреждане на скоби има в това s raz e nii?

Пример за неасоциативна операция е векторното произведение. Друг пример е обичайното събиране и умножение, извършвано на компютър. В сИ че представянето на всяко число в паметта на компютъра е ограничено от определенон брой цифри, при извършване на всяка операция възниква грешка им Очакваният резултат от тези грешки зависи от подредбата на скобите. Позволявам -машина нула . Означава, че. След това докато.

Нека обозначим броя на възможните начини за подреждане на скоби с. Тогава

Ние наричаме операцията условно продукт. За произволно, ние разделяме всички начини за подреждане на скоби на класове, включително в -ти клас начините, по коитоно chala, произведението на първия и последния операнди се изчислява с известно разстояниено нови скоби и след това техният продукт се изчислява:

(7)

където.

По дефиниция броят на начините за подреждане на скоби за изчисляване на първите операнди е равен, а последният - . Съгласно продуктовото правило, броят на аранжировкитеотносно страна за израз (4) е равна. Според правилото за събиране

, (8)

Например, .

Линейни рекуррентни отношения с постоянни коефициенти

Нека функцията във връзка (1) е права th noah

, (9)

къде са някои числа. Такива съотношения се наричатлинейни съотношения решения от -ти ред с постоянни коефициенти.

Нека първо разгледаме отношенията от втори ред в детайли и след това да преминем към oб актуален повод. При , от формула (9) получаваме

, . (10)

Решението на тези отношения се основава на следните лесно доказуеми твърдения e niyakh.

Лема 1. Нека е решение на отношение (10) и е произволно число. Тогава последователността също е решенаИ яжте това съотношение.

Лема 2. Нека и бъде решения наотносно разтвори (10). Тогава последователността също еаз е решение на тази връзка.

Тези две прости леми водят до следното важно заключение. лъжичкаП съществуването на всички възможни последователности с операциите на почивкаР динатично събиране и умножение със скалар образува векторно пространство. лъжичкаП брой последователности, които са решения на отношение (10) представлява сотносно бори се с подпространство на това пространство. Ограждащото пространство на всички възможниотносно последователности е безкрайномерна, но подпространството на решенията на линейна рекурентнат отношението има крайна размерност, равна на реда на уравнението e niya.

Лема 3. Размерността на пространството за решение на рекуррентното отношение (10) е равна на две.

От лема 3 следва, че за определяне на всички решения на уравнение (12) е необходимо да се намерят две линейно независими решения. Всяко друго решение ще бъдеб е линейна комбинация от тези основни решения.

Помислете за рекурентната връзка от първи ред

, (11)

където е константа.

Ако, тогава от (11) имаме

, (12)

т.е. решението на рекурсивно уравнение от първи ред е геометрична прогресия.

Ще търсим решението на рекурентната връзка от втори ред също във вида (12). След това, замествайки (12) с (9), получаваме

. (13)

За =0 имаме нулево решение, което не представлява интерес. Имайки предвид, разделяме последното съотношение на:

(14)

По този начин геометричната прогресия (12) е решение на рекурентното отношение (10), ако знаменателят на прогресията е коренът на квадратното уравнениед ния (14). Това уравнение се наричахарактеристично уравнениеза повтарящо се гукане t облечен (9).

Построяването на основни решения зависи от корените и характеристичното уравнение (14).

(). В този случай имаме две решения и, което lи неизвестен sims. За да проверим това, показваме това от формулата

(15)

чрез подходящ избор на константи може да се получи всяко решение на съотношение (10). Помислете за произволно решение. Избираме константи и така, че за и:

(16)

Детерминанта на линейна система (16)

следователно системата има уникално решение, което означава, че формула (15) е общ рд съотношение (10).

. В случай на множество корени, характеристичното уравнение (13) има вида или. Тогава и за отношение (10) pотносно получаваме уравнение, което дава две основни решения и. Общото решение е представено като

. (17)

В случая на релация от ти порядък (9) се изпълняват твърдения, подобни на разглежданите за уравненията от 2-ри ред.

Множеството от всички решения на уравнение (9) е подпространство в prотносно пространството на всички последователности.
Размерът на това пространство е равен, тоест всяко решение се определя еднозначно от първите си стойности.
За да се определи основата на подпространството на решенията, характеристика e уравнение

. (18)

Полином

(19)

Наречен характеристичен полиномрекурсивна връзка (9).

Ако характеристичното уравнение има различни корени, тогава общото решение на рекуррентното отношение (9) има вида

. (20)

За дадени начални стойности на решението константите nно излизам от системата

Ако е коренът на уравнението на характеристичната множественост, то отношението (9) има следните решения

Нека характеристичното уравнение (18) има корени: ,..., кратности сотносно отговорно, ..., освен това. След това наборът от характеристикиотносно членът и общото решение на съотношение (9) са представени като

Пример 3. Формула на Бине . Нека си поставим задачата да получим формула в изричен вид за hИ седеше Фибоначи. За да направим това, намираме решение на рекурентното отношение (4) при условие, че. Съставяме характеристичното уравнение, намираме неговите корени и получаваме общо решение. Константи и дефинициид lim от началните условия: . Тогава или

, (21)

къде е златното сечение. Формула (21) се наричаФормулата на Бине . При което. От формулата на Бине следва, че.

Други свързани произведения, които може да ви заинтересуват.vshm>
3792.		Рационалност на коефициентите в актива на предприятието	113,83 КБ
	Балансът е основната форма на финансовите отчети. Той характеризира имущественото и финансовото състояние на организацията към отчетната дата. Балансът отразява салдата на всички счетоводни сметки към датата на отчета. Тези показатели са дадени в баланса в определена група.
8407.		постоянен метод	17,82 КБ
	Казва се, че методът на обекта има свойството на неизменност (постоянство), ако след неговото изпълнение състоянието на обекта не се промени. Ако не контролирате свойството на неизменност, тогава предоставянето му ще зависи изцяло от умението на програмист. Ако неизменният метод произвежда външни ефекти по време на изпълнение, тогава резултатът може да бъде най-неочакван и е много трудно да се отстранят грешки и да се поддържа такъв код.
13457.		Метод на фазова равнина	892,42 КБ
	Методът на фазовата равнина е приложен за първи път при изследването на нелинейни системи от френския учен Анри Поанкаре. Основното предимство на този метод е точността и видимостта на анализа на движенията на нелинейна система. Методът е качествен
2243.		ВЪЗМОЖНИ ПОСОКИ МЕТОД	113,98 КБ
	Идеята на метода на възможните посоки на ЯМР е, че във всяка следваща точка има посока на спускане, така че преместването на точка по тази посока за определено разстояние да не нарушава ограниченията на проблема. Посоката, определена от вектор, се нарича възможна посока в точка, ако достатъчно малко движение от тази посока не изведе точката извън допустимата площ m. Очевидно, ако е вътрешна точка на множеството, тогава всяка посока в тази точка е възможна. Възможен...
12947.		МЕТОД НА ХАРМОНИЧНА ЛИНЕАРИЗАЦИЯ	338,05 КБ
	Обръщайки се директно към разглеждането на метода на хармонична линеаризация, ще приемем, че изследваната нелинейна система е сведена до вида, показан в. Нелинеен елемент може да има всяка характеристика, стига да е интегрируем без прекъсвания от втория вид. Трансформацията на тази променлива за пример от нелинеен елемент с мъртва зона е показана на фиг.
2248.		Графичен метод за решаване на LLP	219,13 КБ
	Точките, разположени вътре и на границата на тази област, са валидни равнини. А именно всички точки от отсечката AB са оптималните планове на задачата, върху които се постига максимална стойност на линейната форма. Метод за усъвършенстване на последователен план Методът се основава на подредено изброяване на ъгловите точки на множеството проблемни планове в посока на увеличаване или намаляване на линейната форма и съдържа три съществени точки. Първо се посочва методът за изчисляване на базовата линия.
7113.		Метод на хармонична линеаризация	536,48 КБ
	Метод на хармонична линеаризация Тъй като този метод е приблизителен, получените резултати ще бъдат близки до истината само ако са изпълнени определени предположения: Една нелинейна система трябва да съдържа само една нелинейност; Линейната част на системата трябва да бъде нискочестотен филтър, който отслабва по-високите хармоници, които се появяват в граничния цикъл; Методът е приложим само за автономни системи. Изучаваме свободното движение на системата, тоест движението при ненулеви начални условия при липса на външни влияния...
10649.		Индексен метод за анализ	121,13 КБ
	отделни индекси. Общи агрегирани индекси. Средно конвертирани индекси. Индекси на променлив и постоянен състав, индекси на структурни измествания.
12914.		Метод на най-малкия квадрат	308,27 КБ
	Нека от теоретични разсъждения знаем, че. Следователно можем да кажем, че нашата задача е да начертаем права линия по най-добрия възможен начин. Ще приемем, че цялата грешка се крие в. Ще изберем желаните коефициенти от съображенията, така че произволното събиране да е най-малкото.
9514.		Счетоводен метод	1002.23 КБ
	Счетоводни рахунки, които им побудова. Vіn sladєtsya с редица elementіv golovnі z yakikh: документация; складова наличност; рахунки; подзапис; Оценяване; изчисление; баланс; здравина. Rahunki счетоводството признава за появата на наличие на активи и пасиви. Счетоводни рахунки, които им побудова.

ПОВТОРЯЩИ СЕ ВРЪЗКИ

(от лат. recur-rens, genus case recurrentis - връщащ се) - f-s от същия тип, които свързват определена последователност, следваща една друга (това може да бъде поредица от числа, f-ции и т.н. ). В зависимост от естеството на обектите, свързани с Р. с., тези отношения могат да бъдат алгебрични, функционални, диференциални, интегрални и др.

Найб. добре познат клас от R. s. са рекуррентни функции за специални функции.Да, за цилиндрични функции Z m (x)П. от изглежда като

Те позволяват по функция Z m0 (x) намиране на функции Z m (x) в т= т 0 б 1, т 0 б 2и т.н. или, например, според стойностите на функциите в някакъв момент х 0 . 0 намерете (при числени изчисления) стойността на която и да е от функциите

В същия момент (тук м 0 - всяко реално число).

д-р важен клас от R. s. дават множество методи за последователни приближения (вж. метод на итерация);ето методите смущения на теорията.

В квантовата механика има още един вид R. s., свързващи вектори в Хилбертово пространство на състоянията. Например, стационарните хармонии, осцилаторите се параметризират с неотрицателни цели числа. Съответните вектори, означени с , където н- цели, с различни нмогат да бъдат получени един от друг чрез действието на операторите за създаване а +и унищожение но:

Тези връзки могат да бъдат разрешени чрез изразяване на всеки вектор по отношение на (най-ниско енергийно състояние, h = 0):

Обобщение на тази конструкция е представянето второ квантуванев квантовата статистика. механика и квантова теория на полето (вж Фокпространство).

Типичен пример за R. s. в статистическата механика - уравнения за функции на частично разпределение, които образуват веригата на Боголюбов (вж. уравнения на Боголюбов);познаването на такива f-ции ви позволява да намерите всички термодинамични. характеристики на системата.

В квантовата теория на полето динамика. съдържащи се например в Функциите на Грийн.За тяхното изчисляване, различни приближения, най-често - изчисления на теория на смущенията. Алтернативен подход се основава на интегро-диференциалния уравнения на Дайсън,които са R. s.: уравнението за двуточковата функция на Грийн съдържа четириточкова и т. н. Подобно на уравнението на Боголюбов, тази система може да бъде решена само чрез "разкъсване" на веригата (мястото на "прекъсването" обикновено се избира от физически съображения и определя резултантното ).

Друг вид R. s. в квантовата теория на полето - Ордата от идентичностив теориите полета за калибриране.Тези идентичности също представляват верига от интегро-диференциални отношения, свързващи функциите на Грийн с дек. броят на външните линии, p са следствие от калибровичната инвариантност на теорията. Те играят решаваща роля при проверката на симетрията на калибриране по време на процедурата пренормализация.

И накрая, самата тя също е повтаряща се процедура: на всяка стъпка (във всеки следващ цикъл) контратермини,получен от изчисляването на диаграми с по-малко цикли (за повече подробности вж R операция).А. М. Малокостов.

Физическа енциклопедия. В 5 тома. - М.: Съветска енциклопедия. Главен редактор А. М. Прохоров. 1988 .

Вижте какво е "ПОВТОРЯЩИ СЕ ОТНОШЕНИЯ" в други речници:

повтарящи се отношения- - [L.G. Суменко. Английски руски речник на информационните технологии. M .: GP TsNIIS, 2003.] Теми на информационните технологии в общите EN повторяеми отношения ... Наръчник за технически преводач

- (Вебер функции) общото име за специални функции, които са решения на диференциални уравнения, получени чрез прилагане на метода за разделяне на променливи за уравнения на математическата физика, като уравнението на Лаплас, уравнението ... ... Уикипедия

Или римата на Йосиф Флавий е добре познат математически проблем с исторически оттенъци. Задачата се основава на легендата, че отрядът на Йосиф Флавий, който защитава град Йодфат, не иска да се предаде на превъзходните сили на римляните, блокирали пещерата. ... ... Wikipedia.

Пафнути Лвович Чебишев В математиката безкрайна последователност от реални полиноми се нарича последователност от ортогонални полиноми ... Wikipedia

Тази статия се предлага за изтриване. Обяснение на причините и съответната дискусия можете да намерите на страницата на Уикипедия: За изтриване / 22 ноември 2012 г. Докато процесът на обсъждане ... Wikipedia

Последователността на Падован е целочислена последователност 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 ... Уикипедия

Ермитовите полиноми с определена форма са последователност от полиноми в една реална променлива. Полиномите на Ермит възникват в теорията на вероятностите, в комбинаториката и физиката. Тези полиноми са кръстени на Чарлз Ермит. Съдържание 1 ... ... Уикипедия

- (функции на Бесел) решения Zv(z) на уравнението на Бесел, където параметърът (индекс) v е произволно реално или комплексно число. В приложенията често се среща уравнение, което зависи от четири параметъра: решенията на които са изразени чрез C... Физическа енциклопедия

Метод за решаване на система от линейна алгебрика. уравнения A x= b с ермитова несингулярна матрица A. Сред директните методи той е най-ефективен, когато се реализира на компютър. Изчислителната схема на метода обикновено се основава на ермитовата факторизация ... ... Математическа енциклопедия

Модифицираните функции на Бесел са функции на Бесел на чисто въображаем аргумент. Ако заменим с в диференциалното уравнение на Бесел, то ще приеме формата. Това уравнение се нарича модифицирано уравнение на Бесел ... Wikipedia

Рецидивната връзка има заповед к , ако позволява изразяване на f(n+k) по отношение на f(n), f(n+1), …, f(n+k-1).

Пример.

f(n+2)=f(n)f(n+1)-3f 2 (n+1)+1 е рекурентна връзка от втори ред.

f(n+3)=6f(n)f(n+2)+f(n+1) е рекурентна връзка от трети порядък.

Ако е дадена рекурентна връзка от k-тия ред, тогава безкрайно много поредици могат да я задоволят, тъй като първите k елементи от последователността могат да се задават произволно - няма връзки между тях. Но ако са дадени първите k члена, тогава всички останали елементи са еднозначно определени.

Използвайки рекурентната връзка и началните членове, може да се изпишат членовете на последователността един по един и рано или късно ще получим някой от нейните членове. Ако обаче трябва да знаете само един конкретен член на последователността, тогава не е рационално да изчислявате всички предишни. В този случай е по-удобно да имате формула за изчисляване на n-ия член.

Решението на рекурентното отношениевсяка последователност, за която даденото отношение е идентично, се нарича.

Пример. Последователността 2, 4, 8, …, 2 n е решението на отношението f(n+2)=3∙f(n+1) – 2∙f(n).

Доказателство. Общият член на последователността е f(n)=2 n . Така че f(n+2)= 2 n+2, f(n+1)= 2n+1 . За всяко n важи тъждеството 2 n+2 =3∙2 n+1 – 2∙2 n. Следователно при заместване на последователността 2 n във формулата f(n+2)=3f(n+1) – 2f(n), съотношението се изпълнява идентично. Следователно 2 n е решението на посочената връзка.

Решение на рекурентното отношение k-ти ред се нарича общ, ако зависи от k произволни константи α 1 , α 2 , … α k и чрез избор на тези константи може да се получи произволно решение на тази връзка.

Пример. Рекурентното отношение е дадено: f(n+2)=5f(n+1)-6f(n). Нека докажем, че общото му решение има вида: f(n)= α 2 n + β3 n .

1. Първо доказваме, че последователността f(n)=α 2 n + β3 n е решение на рекурентното отношение. Заменете тази последователност в релацията на повторение.

f(n)= α 2 n + β 3 n , така че f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2 , тогава

5f(n+1)-6f(n)=5∙(α 2 n+1 + β 3 n +1)-6∙(α 2 n + β 3 n)= α (5 2 n+1 –6 2 n)+ β (5 3 n +1 –6 3 n)= =α2 n ∙(10–6)+ β 3 n ∙(15 – 6)= α 2 n+2 + β 3 n +2 = f( n+2).

Следователно, рекурентната връзка е валидна, α 2 n + β 3 n е решението на тази рекурентна връзка.

2. Нека докажем, че всяко решение на отношението f(n+2)=5f(n+1)–6f(n) може да се запише като f(n)= α 2 n + β 3 n . Но всяко решение на рекурентната връзка от втори ред се определя еднозначно от стойностите на първите два члена на последователността. Следователно е достатъчно да се покаже, че за всякакви a=f(1) и b=f(2) има α и β такива, че 2 α +3 β =a и 4 α +9 β =b. Лесно е да се види, че системата от уравнения има решение за всякакви стойности на a и b.

По този начин f(n)= α 2 n + β 3 n е общото решение на рекурентната връзка f(n+2)=5f(n+1)–6f(n).

Линейни рекуррентни отношения с постоянни коефициенти

Няма общи правила за решаване на рекурентни релации, но има често срещан клас рекурентни отношения, за които е известен алгоритъм за решаването им. Това са линейни рекуррентни отношения с постоянни коефициенти, т.е. типове съотношения:

f(n+k)=c 1 f(n+k-1)+c 2 f(n+k-2)+…+c k f(n).

Нека намерим решението на общата линейна рекурентна връзка с постоянни коефициенти от първи ред.

Линейна рекурентна връзка с постоянни коефициенти от първи ред има формата: f(n+1)=c f(n).

Нека f(1)=a, тогава f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, подобно на f(4)=c 3 ∙a и така нататък, имайте предвид, че f(n)=cn -1 ∙f(1).

Нека докажем, че последователността c n -1 ∙f(1) е решение на рекурентна връзка от първи ред. f(n)=c n -1 ∙f(1), така че f(n+1)=c n f(1). Замествайки този израз в релацията, получаваме тождество c n f(1)=с∙ c n -1 ∙f(1).

Нека сега разгледаме по-подробно линейни рекурентни отношения с постоянни коефициенти от втори ред , тоест отношения на формата

f(n+2)=C 1 ∙f(n+1)+C 2 ∙f(n). (*).

Имайте предвид, че всички съображения са валидни и за отношенията от по-висок ред.

Свойства на разтвора:

1) Ако последователността x n е решение (*), тогава последователността a∙x n също е решение.

Доказателство.

x n е решение на (*), следователно x n +2 =C 1 x n +1 +C 2 x n . Умножаваме двете страни на равенството по a. Получаваме a∙x n +2 =a∙(С 1 ∙x n +1 +С 2 ∙x n)= С 1 ∙a∙x n +1 +С 2 ∙a∙x n . Това означава, че ax n е решението (*).

2) Ако последователностите x n и y n са решения (*), тогава последователността x n +y n също е решение.

Доказателство.

x n и y n са решения, така че следните тъждества са валидни:

x n +2 \u003d C 1 x n +1 + C 2 x n.

y n +2 =C 1 y n +1 +C 2 y n .

Нека добавим двете равенства член по член:

xn +2 +yn +2 =С 1 ∙xn +1 +С 2 ∙xn + С 1 ∙yn +1 +С 2 ∙yn = С 1 ∙(xn +1 + yn +1)+С 2 ∙(xn +yn). Това означава, че x n +y n е решението на (*).

3) Ако r 1 е решение на квадратното уравнение r 2 =С 1 r+С 2, тогава последователността (r 1) n е решението на отношението (*).

r 1 е решението на квадратното уравнение r 2 =C 1 r+C 2 , така че (r 1) 2 =C 1 r 1 +C 2 . Нека умножим двете страни на равенството по (r 1) n . Вземи

r 1 2 r 1 n \u003d (C 1 r 1 + C 2) r n.

r 1 n +2 \u003d C 1 r 1 n +1 + C 2 r 1 n.

Това означава, че последователността (r 1) n е решението на (*).

От тези свойства следва начин на решениелинейни рекурентни отношения с постоянни коефициенти от втори ред:

1. Съставете характеристичното (квадратично) уравнение r 2 =C 1 r+C 2 . Нека намерим нейните корени r 1, r 2. Ако корените са различни, тогава общото решение е f(n)= ar 1 n +βr 2 n .

2. Намерете коефициентите a и β. Нека f(0)=a, f(1)=b. Система от уравнения

има решение за всякакви a и b. Тези решения са

Задача . Нека намерим формула за общия член на последователността на Фибоначи.

Решение . Характеристичното уравнение има формата x 2 = x + 1 или x 2 -x-1 = 0, корените му са числа, което означава, че общото решение има формата f (n) \u003d . Както е лесно да се види, от началните условия f(0)=0, f(1)=1 следва, че a=-b=1/Ö5, и следователно общото решение на последователността на Фибоначи има вида :

Изненадващо, този израз приема цели числа за всички естествени стойности на n.