Lihat sumber Relasi perulangan

{{short description|Definisi setiap suku dari suatu urutan sebagai fungsi dari suku-suku sebelumnya}}
{{redirect-distinguish|Persamaan beda|persamaan diferensial}}{{Periksa terjemahan|en|Recurrence relation}}
Dalam [[matematika]], '''relasi perulangan'''<ref>{{Cite book|last=Lipschutz|first=Seymour|last2=Lipson|first2=Marc|date=2008|title=Matematika Diskret|location=Jakarta|publisher=Erlangga|translator-last=Dr. Thombi Layukallo|url-status=live}}</ref> adalah [[persamaan]] yang[[rekursi]]f mendefinisikan array nilai [[urutan]] atau multidimensi, sekali satu atau lebih istilah awal diberikan; setiap suku selanjutnya dari barisan atau [[larik]] didefinisikan sebagai [[Fungsi (matematika)|fungsi]] dari suku-suku sebelumnya.

Syarat '''[[#Hubungan persamaan perbedaan didefinisikan secara sempit|persamaan perbedaan]]''' terkadang (dan untuk tujuan artikel ini) mengacu pada jenis relasi perulangan tertentu. Namun, "persamaan perbedaan" sering digunakan untuk merujuk ke relasi perulangan dengan '' apa saja ''.

== Definisi ==
''Relasi perulangan'' adalah persamaan yang mengekspresikan setiap elemen dari [[urutan]] sebagai fungsi dari yang sebelumnya. Lebih tepatnya, dalam kasus di mana hanya elemen sebelumnya yang terlibat, relasi perulangan memiliki bentuk
:<math>u_n=\varphi(n, u_{n-1})\quad\text{untuk}\quad n>0,</math>
dimana 
:<math>\varphi:\mathbb N\times X \to X</math>
adalah sebuah fungsi, di mana {{mvar | X}} adalah himpunan yang harus dimiliki elemen-elemen urutan. Untuk apapun <math>u_0\in X</math>, ini mendefinisikan urutan unik dengan <math> u_0 </math> sebagai elemen pertamanya, yang disebut nilai awal.<ref>Jacobson, Nathan , Basic Algebra 2 (2nd ed.), § 0.4. pg 16.</ref>

Sangat mudah untuk mengubah definisi untuk mendapatkan urutan mulai dari indeks 1 atau lebih tinggi.

Ini mendefinisikan relasi perulangan ''orde pertama''. Relasi perulangan '' orde''{{mvar | k}} memiliki bentuk 
:<math>u_n=\varphi(n, u_{n-1}, u_{n-2}, \ldots, u_{n-k})\quad\text{for}\quad n\ge k,</math>

dimana <math>\varphi: \mathbb N\times X^k \to X</math> adalah fungsi yang melibatkan {{mvar | k}} elemen berurutan dari urutan tersebut.
Dalam kasus ini, nilai awal {{mvar | k}} diperlukan untuk menentukan urutan.

== Contoh ==
=== Faktorial ===
[[Faktorial]] ditentukan oleh relasi perulangan
:<math>n!=n(n-1)!\quad\text{untuk}\quad n>0,</math>
dan kondisi awal
:<math>0!=1.</math>

=== Peta logistik ===
Contoh relasi perulangan adalah [[peta logistik]]:

:<math>x_{n+1} = r x_n (1 - x_n),</math>

dengan konstanta tertentu '' r ''; mengingat istilah awal ''x''<sub>0</sub> setiap suku berikutnya ditentukan oleh relasi ini.

Memecahkan relasi perulangan berarti memperoleh [[solusi bentuk tertutup]]: fungsi non-rekursif dari '' n ''.

=== Bilangan Fibonacci ===
Pengulangan urutan dua yang dipenuhi oleh [[Bilangan Fibonacci]] adalah pola dasar dari relasi perulangan [[pengulangan linier|linier]] yang homogen dengan koefisien konstan (lihat di bawah). Urutan Fibonacci ditentukan menggunakan pengulangan

:<math>F_n = F_{n-1}+F_{n-2}</math>

dengan [[kondisi awal]] (nilai benih)

:<math>F_0 = 0</math>
:<math>F_1 = 1.</math>

Secara eksplisit, pengulangan menghasilkan persamaan
:<math>F_2 = F_1 + F_0</math>
:<math>F_3 = F_2 + F_1</math>
:<math>F_4 = F_3 + F_2</math>
etc.

Kami mendapatkan urutan angka Fibonacci, yang dimulai
:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Pengulangan dapat diselesaikan dengan metode yang dijelaskan di bawah ini menghasilkan [[rumus Binet]], yang melibatkan pangkat dua akar dari karakteristik polinomial ''t''<sup>2</sup>&nbsp;=&nbsp;''t''&nbsp;+&nbsp;1; [[fungsi pembangkit]] dari barisan tersebut adalah [[fungsi rasional]]
:  <math>\frac{t}{1-t-t^2}.</math>

=== Koefisien binomial ===
Contoh sederhana dari relasi perulangan multidimensi diberikan oleh [[koefisien binomial]] <math>\tbinom{n}{k}</math>, yang menghitung jumlah cara memilih elemen '' k '' dari satu set elemen '' n ''.
Mereka dapat dihitung oleh relasi perulangan
:<math>\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},</math>
dengan kasus dasar <math>\tbinom{n}{0}=\tbinom{n}{n}=1</math>. Menggunakan rumus ini untuk menghitung nilai semua koefisien binomial menghasilkan larik tak hingga yang disebut [[segitiga Pascal]]. Nilai yang sama juga dapat dihitung secara langsung dengan rumus berbeda yang bukan merupakan pengulangan, tetapi membutuhkan perkalian dan bukan hanya penambahan untuk menghitung:
<math>\binom{n}{k}=\frac{n!}{k!(n-k)!}.</math>

== Hubungan persamaan perbedaan didefinisikan secara sempit ==
Diberikan urutan [[urutan]] <math>\left\{a_n\right\}_{n=1}^\infty</math> dari [[bilangan riil]]: '''perbedaan pertama''' <math>\Delta(a_n)</math> didefinisikan sebagai

:<math>\Delta(a_n) = a_{n+1} - a_n.</math>

'''Perbedaan kedua''' <math>\Delta^2(a_n)</math> didefinisikan sebagai

:<math>\Delta^2(a_n) = \Delta(a_{n+1}) - \Delta(a_n),</math>

yang dapat disederhanakan menjadi

:<math>\Delta^2(a_n) = a_{n+2} - 2a_{n+1} + a_n.</math>

Lebih umum lagi: '''''k''-perbedaan''' dari urutan ''a<sub>n</sub>'' ditulis sebagai <math>\Delta^k(a_n)</math> didefinisikan secara rekursif sebagai

:<math>\Delta^k(a_n) = \Delta^{k-1}(a_{n+1}) - \Delta^{k-1}(a_n)=\sum_{t=0}^k \binom{k}{t} (-1)^t a_{n+k-t}.</math>

(Urutan dan perbedaannya terkait dengan [[transformasi binomial]].) Definisi yang lebih ketat dari '' persamaan perbedaan adalah persamaan yang terdiri dari a<sub>n</sub>'' dan itu ''k''<sup>th</sup> perbedaan. (Definisi yang lebih luas digunakan secara luas memperlakukan "persamaan perbedaan" sebagai sinonim dengan "hubungan rekurensi". Lihat contoh [[persamaan perbedaan rasional]] dan [[persamaan perbedaan matriks]])

Sebenarnya, mudah dilihat bahwa,

:<math>a_{n+k} = 
{k\choose 0}a_n + {k\choose 1} \Delta(a_n)  + \cdots + {k\choose k} \Delta^k(a_n).
</math>

Dengan demikian, persamaan perbedaan dapat didefinisikan sebagai persamaan yang melibatkan 
''a<sub>n</sub>'', ''a<sub>n-1</sub>'', ''a<sub>n-2</sub>'' dll. (atau dengan kata lain
''a<sub>n</sub>'', ''a<sub>n+1</sub>'', ''a<sub>n+2</sub>'' dll.)

Karena persamaan perbedaan adalah bentuk pengulangan yang sangat umum, beberapa penulis menggunakan kedua istilah tersebut secara bergantian. Misalnya persamaan selisih

:<math>3\Delta^2(a_n) + 2\Delta(a_n) + 7a_n = 0</math>

setara dengan hubungan perulangan

:<math>3a_{n+2} = 4a_{n+1} - 8a_n.</math>

Dengan demikian seseorang dapat menyelesaikan banyak relasi perulangan dengan menyusunnya kembali sebagai persamaan perbedaan, dan kemudian menyelesaikan persamaan perbedaan, analog dengan bagaimana seseorang memecahkan [[persamaan diferensial biasa]]. Namun, [[bilangan Ackermann]] adalah contoh relasi perulangan yang tidak memetakan ke persamaan diferensial, apalagi titik pada solusi persamaan diferensial.

Lihat [[kalkulus skala waktu]] untuk penyatuan teori persamaan perbedaan dengan [[persamaan diferensial]].

[[Persamaan penjumlahan]] s berhubungan dengan persamaan perbedaan karena [[persamaan integral]] berhubungan dengan persamaan diferensial.

=== Dari urutan ke kisi ===
Hubungan pengulangan variabel tunggal atau satu dimensi adalah tentang urutan (yaitu fungsi yang ditentukan pada kisi satu dimensi). Relasi pengulangan multi-variabel atau n-dimensi adalah tentang kisi berdimensi-n. Fungsi yang ditentukan pada n-grid juga dapat dipelajari dengan '''persamaan perbedaan parsial'''.<ref>[https://books.google.com/books?id=1klnDGelHGEC Partial difference equations], Sui Sun Cheng, CRC Press, 2003, {{isbn|978-0-415-29884-1}}</ref>

== Stabilitas ==

=== Stabilitas pengulangan tingkat tinggi linier ===
Pengulangan [[Lincoln Near-Earth Asteroid Research|linear]] order ''d'',

:<math>a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d},  </math>

memiliki [[Karakteristik polinomial|persamaan karakteristik]]

:<math>\lambda^d - c_1 \lambda^{d-1} - c_2 \lambda^{d-2} - \cdots - c_d \lambda^0 =0. </math>

Pengulangannya adalah [[Teori stabilitas|stabil]], yang berarti bahwa iterasi menyatu secara asimtotik ke nilai tetap, jika dan hanya jika [[nilai eigen]] (yaitu, akar dari persamaan karakteristik), baik nyata maupun kompleks, semuanya kurang dari [[satuan (matematika)|kesatuan]] dalam nilai absolut.

=== Stabilitas pengulangan matriks orde pertama linear ===
{{Main|Persamaan perbedaan matriks}}

Dalam persamaan perbedaan matriks orde pertama

:<math>[x_t - x^*] = A[x_{t-1}-x^*]</math>

dengan vektor keadaan '' x '' dan matriks transisi '' A '', '' x '' menyatu secara asimtotik ke vektor keadaan mapan '' x '' * [[jika dan hanya jika]] semua nilai eigen dari matriks transisi ''A'' (apakah nyata atau kompleks) memiliki [[nilai absolut]] yang kurang dari 1.)
<!--
=== Stabilitas pengulangan urutan pertama nonlinear ===
Pertimbangkan perulangan urutan pertama nonlinear

:<math>x_n=f(x_{n-1}).</math>

Pengulangan ini adalah [[teori stabilitas | stabil secara lokal]], artinya [[batas urutan | menyatu]] ke titik tetap ''x''* from points sufficiently close to ''x''*, if the slope of ''f''  in the neighborhood of ''x''* is smaller than [[unity (mathematics)|unity]] in absolute value:  that is,

: <math>| f' (x^*) | < 1. </math>

A nonlinear recurrence could have multiple fixed points, in which case some fixed points may be locally stable and others locally unstable; for continuous ''f''  two adjacent fixed points cannot both be locally stable.

A nonlinear recurrence relation could also have a cycle of period ''k'' for ''k'' > 1.  Such a cycle is stable, meaning that it attracts a set of initial conditions of positive measure, if the composite function

:<math>g(x) := f \circ f \circ \cdots \circ f(x)</math>

with ''f'' appearing ''k'' times is locally stable according to the same criterion:

: <math>| g' (x^*) | < 1,</math>

where ''x''* is any point on the cycle.

In a [[chaos theory|chaotic]] recurrence relation, the variable ''x'' stays in a bounded region but never converges to a fixed point or an attracting cycle; any fixed points or cycles of the equation are unstable.  See also [[logistic map]], [[dyadic transformation]], and [[tent map]].
-->

== Hubungan dengan persamaan diferensial ==
Saat menyelesaikan sebuah [[persamaan diferensial biasa]] [[persamaan diferensial biasa numerik|secara numerik]], seseorang biasanya menemukan relasi perulangan. Misalnya, saat memecahkan [[masalah nilai awal]]

:<math>y'(t) = f(t,y(t)), \ \ y(t_0)=y_0,</math>

dengan [[metode Euler]] dan ukuran langkah '' h '', seseorang menghitung nilainya

:<math>y_0=y(t_0), \ \ y_1=y(t_0+h), \ \ y_2=y(t_0+2h), \ \dots</math>

oleh nilai

:<math>\, y_{n+1} = y_n + hf(t_n,y_n), t_n = t_0 + nh </math>

Sistem persamaan diferensial orde pertama linier dapat didiskritisasi secara analitis menggunakan metode yang ditunjukkan dalam artikel [[diskritisasi]].

== Lihat pula ==
{{colbegin}}

* [[Fungsi Holonomis|Urutan Holonomis]]
* [[Fungsi berulang]]
* [[Polinomial ortogonal]]
* [[Rekursi]]
* [[Rekursi (ilmu komputer)]]
* [[Generator Fibonacci Tertinggal]]
* [[Master teorema (analisis algoritma)]]
* [[Lingkaran titik segmen bukti]]
* [[Pecahan berlanjut]]
* [[Kalkulus skala waktu]]
* [[Prinsip kombinatorial]]
* [[Respon impuls tak hingga]]
* [[Integrasi dengan rumus pengurangan]]
* [[Induksi matematika]]
{{colend}}

== Catatan ==
{{reflist}}

== Referensi ==
* {{cite book|first1=Paul M. | last1=Batchelder
|title=An introduction to linear difference equations
|url=https://archive.org/details/introductiontoli0000paul |year=1967
|publisher=Dover Publications
}}
* {{cite book|first1=Kenneth S. | last1=Miller
|title=Linear difference equations
|year=1968 | publisher=W. A. Benjamin
}}
* {{cite news|first1=Jay P. | last1=Fillmore | first2=Morris L. | last2=Marx
|title=Linear recursive sequences | journal= SIAM Rev. | volume=10|number=3
|pages=324–353 | jstor=2027658| year=1968}}
* {{cite book| first1=Alfred | last1=Brousseau
|title=Linear Recursion and Fibonacci Sequences
|year=1971
|publisher=Fibonacci Association
|url=http://www.fq.math.ca/linear.html
}}
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. [[MIT Press]] and [[McGraw-Hill]], 1990. {{isbn|0-262-03293-7}}. Chapter 4: Recurrences, pp.&nbsp;62–90.
*{{cite book| first1=Ronald L. | last1=Graham |
first2=Donald E. | last2=Knuth
|first3=Oren | last3=Patashnik
|title=Concrete Mathematics: A Foundation for Computer Science
|edition=2
|publisher=Addison-Wesley
|year=1994 |isbn=0-201-55802-5
}}
*{{cite book
 |year        = 2010
 |url         = http://eu.wiley.com/WileyCDA/WileyTitle/productCd-EHEP000338.html
 |first1      = Walter
 |last1       = Enders
 |title       = Applied Econometric Times Series
 |edition     = 3
 |url-status     = dead
 |archiveurl  = https://web.archive.org/web/20141110221941/http://eu.wiley.com/WileyCDA/WileyTitle/productCd-EHEP000338.html
 |archivedate = 2014-11-10
}}
*{{cite book| first1=Paul | last1=Cull | first2=Mary | last2=Flahive|author2-link= Mary Flahive
|first3=Robbie | last3=Robson
|title=Difference Equations: From Rabbits to Chaos
|title-link= Difference Equations: From Rabbits to Chaos
|publisher=Springer | year=2005 | isbn=0-387-23234-6 }} chapter 7.
* {{cite book| first1=Ian | last1=Jacques
|title=Mathematics for Economics and Business
| url=https://archive.org/details/mathematicsforec00jacq | url-access=limited |edition=Fifth
|publisher=Prentice Hall
|year=2006
|isbn=0-273-70195-9
|pages=[https://archive.org/details/mathematicsforec00jacq/page/n561 551]–568
}} Chapter 9.1: Difference Equations.
* {{cite web | first1=Tang | last1=Minh | first2=Tan | last2=Van To | title=Using generating functions to solve linear inhomogeneous recurrence equations | pages=399–404 | url=http://www.wseas.us/e-library/conferences/2006lisbon/papers/517-481.pdf | year=2006 | work=Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06 | access-date=2020-10-21 | archive-date=2016-03-04 | archive-url=https://web.archive.org/web/20160304035925/http://www.wseas.us/e-library/conferences/2006lisbon/papers/517-481.pdf | dead-url=yes }}
* {{cite web| first1=Andrei D. | last1=Polyanin
|title=Difference and Functional Equations: Exact Solutions
|url=http://eqworld.ipmnet.ru/en/solutions/fe.htm}} at EqWorld - The World of Mathematical Equations.
* {{cite web| first1=Andrei D. | last1=Polyanin
|title=Difference and Functional Equations: Methods
|url=http://eqworld.ipmnet.ru/en/education/edu-fe.htm}} at EqWorld - The World of Mathematical Equations.
*{{cite journal | first1= Xiang-Sheng | last1=Wang
| first2=Roderick | last2=Wong
|title= Asymptotics of orthogonal polynomials via recurrence relations
|journal =  Anal. Appl. | year=2012 | volume=10 | number=2
|pages=215–235 | doi=10.1142/S0219530512500108 
|arxiv=1101.4371}}

== Pranala luar ==
* {{springer|title=Recurrence relation|id=p/r080150}}
* {{MathWorld | urlname= RecurrenceEquation | title= Recurrence Equation}}
* {{cite web |title= OEIS Index Rec|url=http://oeis.org/wiki/Index_to_OEIS:_Section_Rec}} [[OEIS]] index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients)

{{Authority control}}

[[Kategori:Aljabar]]
[[Kategori:Relasi perulangan| ]]
[[Kategori:Kombinatorika]]