У математици, диференцна једначина је једначина која рекурзивно дефинише низ или мултидимензионални ред вредности, једном када је један или више почетних услова дато: сваки следећи члан низа или реда је дефинисина као функција претходних услова.
Термин диференцна једначина се понекад (као што је случај у овом чланку) односи на специфичан тип рекурзивне релације. Међутим, "диференцна једначина" се често односи на све типове рекурзивних релација.
Примери
Логистичка мапа Пример рекурзивне релације је логистичка мапа:
са датом константом r; датим почетним условом x0 сваки члан подниза је одређен овом релацијом.
Неке једноставно дефинисане рекурзивне релације могу имати веома комплексне (теорија хаоса) особине, и они припадају пољу математике који је познат под називом нелинеарна анализа.
Решавање рекурзивне релације значи постизање решења затвореног типа: нерекурзивна функција по n.
Фибоначијев низ Фибоначијев низ је прототип линеарне, хомогене рекурзивне релације са костантним коефицијентима (видети испод). Они су дефинисани помоћу линеарне рекурзивне релације.
са почетним условима:
Експлицитно, рекурзија даје једначине:
итд.
Добијамо низ Фибоначијевих бројева, који почиње: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Он се може решити помоћу метода које су описане у наставку, добијањем израза затвореног типа, који укључује степене два решења карактеристичног полинома t2 = t + 1; генеративна функција низа је рационална функција:
Биномни коефицијенти Једноставан пример мултидимензионалне рекурзивне релације је дат помоћу биномног коефицијента , који рачуна број начина селектовања k из сета од n елемената. Они се могу израчунати помоћу рекурзивне релације
где су почетни услови . Коришћење ове формуле за израчунавање вредности свих биномних коефицјената, ствара бесконачан ред који је назван Паскалов троугао. Те вредности се такође могу израчунати и директно помоћу формуле која није рекурзивна, али то захтева множење а не само сабирање:
Структуре
Линеарне хомогене рекурзивне релације са константним коефицијентима Низ d линеарне хомогене рекурзивне релације са константним коефицијентима је једначина форме
где су d и коефицијенти ci (за свако i) константе.
Прецизније, ово је бесконачна листа сличних линеарних једначина, једна за свако n>d−1. Низ који задовољава релацију овог облика се зове линеарни рекурзивни низ или ЛРС. ЛРС има d степена слободе, као почетне вредности се могу узети било које вредности али онда линеарна рекурзија одређује низ јединствено.
Исти коефицијенти дају карактеристични полином (такође "помоћни полином")
чија d решења играју битну улогу у налажењу и разумевању низа који задовољава рекурзију. Ако су сва решења r1, r2, ... посебна, онда је решење рекурзије облика
где је коефицијент ki одређен тако да одговара почетним условима рекурзије. Када се исти корени појаве већи број пута, чланови формуле који одговарају другом и наредним појавама истог корена се множе тако да им степенови буду n. На пример, ако карактеристични полином може бити факторисан као (x−r)3, са истим кореном r који се појављује три пута, онда ће решење бити облика Greene, Daniel H.; Knuth, Donald E. (1982), "2.1.1 Constant coefficients – A) Homogeneous equations", Mathematics for the Analysis of Algorithms (2nd ed. Као и Фибоначијев низ, и остали низови настали линеарном хомогеном рекурзијом укључујући Лукасове бројеве и Лукасов низ, Јакобсталове бројеве, Пелове бројеве као и решење Пелове једначине.
Рационална генеративна функција Линеарни рекурзивни низови су прецизније низови чија је генеративна функција, рационална: именилац је полином добијен од помоћног полинома мењањем редоследа коефицијената, и бројилац је одређен почетним вредностима низа.
Најједноставнији случајеви су периодични низови, , чији је низ и генеративна функција збир геометријских серија:
Уопштеније, дата рекурзивна релација:
са генеративном фукнцијом
серија је прекунита за ad и изнад полиномом:
Тако, множењем генеративне функције полиномом се добија
што представља коефицијент уз , и нестаје (рекурзивном релацијом) за n ≥ d. Тако
да дељење даје
представљајући генеративну функцију као рационалну.
Именилац је трансформација помоћног полинома (еквивалентно, променом редоследа коефицјената); могао је да се узме и било који чинилац, али овај стандард је изабран због једноставне везе са помоћним полиномом, тако да је .
Однос са уско дефинисаним диференцним једначинама Дати поредак низа реалних бројева: прва диференца је дефинисана са . Друга диференца је дефнисана са , која се може упростити на . Уопштено: kта диференца низа an , написана као је дефинисана рекурзивно као . (Низ и његове диференце су повезани преко биномне трансформације.) Рестриктивнија дефиниција диференцне једначине је једначина састављена од an и њених kти диференци. (широко распрострањена дефиниција третира "диференцне једначине" као синоним за "рекурзивну релацију". Видети на пример рационалну диференцну једначину и матричну диференцну једначину.)
Заправо, лако се види да је Тако, диференцна једначина може бити дефинисана као једначина које укључује an, an-1, an-2 итд. (или евентуално an, an+1, an+2 итд.)
Како су диференцне једначине врло препознатљив облик рекурзије, неки аутори користе ова два израза наизменично. На пример, диференцна једначина
је еквивалентна рекурзивној релацији
Тако да се многе рекурзивне релације могу решити превођењем у диференцне једначине, а онда аналогно решавању диференцних једначина, се могу решити обичне диференцијалне једначине. Међутим, Акерманова функција је пример рекурзивне релације која се не пресликава у диференцијалну једначину.
Видети рачун на временској скали везан за уједињење теорије о диференцним једначинама са диференцијалним једначинама.
Дискретне интегралне једначине су везане за диференцне једначине као што су интегралне једначине везане за диференцијалне једначине.
Од низова до мрежа Једно-променљиве или једно-димензионалне рекурзивне релације су везане та низове (тј. функције дефинисане на једно-димензионалним мрежама). Више-променљиве или н-димензионалне рекурзивне релације су везане за н-димензионалне мреже. Функције дефинисане на н-мрежама се такође могу изучавати у оквиру парцијалних диференцних једначина.
Решавање
Уопштене методе За низ 1, рекурзија
има решење an = rn са a0 = 1 а најуопштеније решење је an = krn са a0 = k. Карактетистични полином изједначен са нулом је (карактеристична једначина) t − r = 0.
Решења овакве рекурзивне релације вишег реда се налазе систематски, често се користи чињеница да је an = rn решење рекурзије тачно када је t = r корен карактеристичног полинома. Овоме се може приступити директно или преко генеративних функција (формални степени ред) или матрица.
Размотримо, на пример, рекурзивну релацију облика
Када има решење облика an = rn? Заменом ове претпоставке (анзац) у рекурзивној релацији, налазимо да
мора бити тачно за свако n > 1.
Дељењем са rn−2, добијамо да се све једначине своде на исту ствар:
што је карактеристика једначине рекурзивне релације. Решавањем r добијамо два корена λ1, λ2: ови корени су познати као карактеристични корени (решења) или јединствена решења карактеристичне једначине. Другачија решења се добијају у зависности од природе корена: Ако су ови корени посебни, имамо уопштено решење
док, ако су они једнаки (када је A2 + 4B = 0), имамо
Ово је најуопштеније решење; две константе C и D се могу изабрати на основу почетних услова a0 и a1 како би се добило специфично решење.
У случају комплексних јединствених решења (што такође даје комплексне вредности за решења параметара C и D), коришћење комплексних бројева може бити елиминисано писањем решења у тригонометријском облику. У том случају можемо написати јединствена решења као Затим се може показати да
може бити написано каоChiang, Alpha C., Fundamental Methods of Mathematical Economics, third edition, McGraw-Hill, 1984.:576–585
где
Овде су E и F (еквивалентно, G и δ) реалне константе које зависе од почетних услова. Коришћењем
се може поједноставити решење дато итнад као
где су a1 и a2 почетни услови и
У овом случају нема потребе решавати λ1 и λ2.
У сваком случају за реална јединствена решења, реална дупла јединствена решења, и конјуговано комплексна јединствена решења—једначина је стабилна (тако је, променљива a претворена у фиксирану вредност (посебно, нула)); ако и само ако су обе јединствене вредности мање од једне апсолутне вредности. У том случају, овај услов за јединствене вредности може бити приказан тако да буде еквивалентанPapanicolaou, Vassilis, , February 1996, 34–43. са |A| < 1 − B < 2, што је еквивалентно |B| < 1 и |A| < 1 − B.
Једначина у претходном примеру је била хомогена, у којој није било константог члана. Ако полази са не-хомогеном рекурзијом
са константим чланом K, она може бити претворена у хомогени облик као: Стабилно стање је постигнуто постављањем bn = bn−1 = bn−2 = b* како би се добило
Онда не-хомогена рекурзија може бити написана у хомогеном облику као
која се може решити преко формуле изнад.
Стабилан услов који је претходно наведен за јединствене вредности у случај другог-реда остаје могућ за уопштен случај nтог-реда: једначина је стабилна ако и само ако су све јединствене вредности карактеристичних једначина мање од једне апслутне вредности.
Решавање преко линеране алгебре Линеаран рекурзиван низ у реда n
је идентичан са
Проширен са n-1 идентитетима типа овакав n-ти ред једначина је преведен у систем првих n низова линеарних једначина,
Треба уочити да се вектор може израчунати преко n уношења придружених матрица, C, на првобитан вектор, . Тиме је, n-ти унос траженог низа y, компонента .
Јединствено разлагање на једниствене вредности, , и јединствене векторе, , се користи да би се израчунао Захваљујући битној чињеници да систем C замењује сваки једниствен вектор, e, једноставним додавањем његових компонената λ пута,
то јест, замењена верзија једниственог вектора,e, има компоненте λ пута веће, а компоненте једниственог вектора су степени од λ, а, такође, решење рекурзивне линеарне хомогене једначине је комбинација експоненцијалих функција, . Компоненте могу бити одређене преко почетних услова:
Решавање за коефицијенте,
Ово такође ради са произвољним граничним условима , и нису неопходни почетни услови,
Овакав опис се заиста не разликује од уопштених методе горе наведених, међутим много је сажетији. Он такође ради у ситуацијама типа
када има неколико повезаних рекурзија.Maurer, Stephen B.; Ralston, Anthony (1998), Discrete Algorithmic Mathematics (2nd ed.
Решавање помоћу Z-трансформација Извесне диференцне једначине - посебно, линеарне са константним коефицијентима - се могу решити помоћу Z-трансформација. Z-трансформације су део интегралних трансформација које пружају знатно корисније алгебарске манипулације и много једноставнија решења. Постоје случајеви у којима би директно тражење решења било немогуће, а са друге стране решавање таквих проблема помоћу посебних интегралних трансформација би било врло једнставно.
Теорема Дата је линеарно хомогена рекурзивна релација са константним коефицијентима реда d, нека је p(t) карактеристични полином (такође и "помоћни полином")
такав да сваки ci одговара сваком ci у оригиналном рекурзивном дносу (видети уопштен услов изнад). Претпоставимо да је λ корен од p(t) који има разноврсност r. Тада (t−λ)r дели p(t). Наредна два својства садрже: Сваки r низ задовољава рекурзивну релацију. Било који низ који задовољава рекурзивну релацију може бити написан као линеарна комбинација решења конструисаних у првом делу као λ зависи од свих јединствених решења p(t). Као резултат ове теоремем, линеарна хомогена рекурзивна релација са константним коефицијентима се може решити преко: Налажења карактеристичног полинома p(t). Налажења корена p(t) преко множења.