Jakarta Aktual
Jakarta Aktual

Berita Aktual dan Faktual

Jakarta Aktual
Jakarta Aktual© 2026
Jakarta Aktual
Jakarta Aktual

Berita Aktual dan Faktual

Kembali ke Wiki
Artikel Wikipedia

Relasi perulangan

Dalam matematika, relasi perulangan adalah persamaan yangrekursif mendefinisikan array nilai urutan atau multidimensi, sekali satu atau lebih istilah awal diberikan; setiap suku selanjutnya dari barisan atau larik didefinisikan sebagai fungsi dari suku-suku sebelumnya.

Wikipedia article
Diperbarui 17 Januari 2026

Sumber: Lihat artikel asli di Wikipedia

Definisi setiap suku dari suatu urutan sebagai fungsi dari suku-suku sebelumnyaTemplat:SHORTDESC:Definisi setiap suku dari suatu urutan sebagai fungsi dari suku-suku sebelumnya
"Persamaan beda" beralih ke halaman ini, yang bukan mengenai persamaan diferensial.
Artikel atau sebagian dari artikel ini mungkin diterjemahkan dari Recurrence relation di en.wikipedia.org. Isinya masih belum akurat, karena bagian yang diterjemahkan masih perlu diperhalus dan disempurnakan. Jika Anda menguasai bahasa aslinya, harap pertimbangkan untuk menelusuri referensinya dan menyempurnakan terjemahan ini. Anda juga dapat ikut bergotong royong pada ProyekWiki Perbaikan Terjemahan.
(Pesan ini dapat dihapus jika terjemahan dirasa sudah cukup tepat. Lihat pula: panduan penerjemahan artikel)

Dalam matematika, relasi perulangan[1] adalah persamaan yangrekursif mendefinisikan array nilai urutan atau multidimensi, sekali satu atau lebih istilah awal diberikan; setiap suku selanjutnya dari barisan atau larik didefinisikan sebagai fungsi dari suku-suku sebelumnya.

Syarat 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

u n = φ ( n , u n − 1 ) untuk n > 0 , {\displaystyle u_{n}=\varphi (n,u_{n-1})\quad {\text{untuk}}\quad n>0,} {\displaystyle u_{n}=\varphi (n,u_{n-1})\quad {\text{untuk}}\quad n>0,}

di mana

φ : N × X → X {\displaystyle \varphi :\mathbb {N} \times X\to X} {\displaystyle \varphi :\mathbb {N} \times X\to X}

adalah sebuah fungsi, di mana X adalah himpunan yang harus dimiliki elemen-elemen urutan. Untuk apapun u 0 ∈ X {\displaystyle u_{0}\in X} {\displaystyle u_{0}\in X}, ini mendefinisikan urutan unik dengan u 0 {\displaystyle u_{0}} {\displaystyle u_{0}} sebagai elemen pertamanya, yang disebut nilai awal.[2]

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

Ini mendefinisikan relasi perulangan orde pertama. Relasi perulangan orde k memiliki bentuk

u n = φ ( n , u n − 1 , u n − 2 , … , u n − k ) for n ≥ k , {\displaystyle u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{n-k})\quad {\text{for}}\quad n\geq k,} {\displaystyle u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{n-k})\quad {\text{for}}\quad n\geq k,}

di mana φ : N × X k → X {\displaystyle \varphi :\mathbb {N} \times X^{k}\to X} {\displaystyle \varphi :\mathbb {N} \times X^{k}\to X} adalah fungsi yang melibatkan k elemen berurutan dari urutan tersebut. Dalam kasus ini, nilai awal k diperlukan untuk menentukan urutan.

Contoh

Faktorial

Faktorial ditentukan oleh relasi perulangan

n ! = n ( n − 1 ) ! untuk n > 0 , {\displaystyle n!=n(n-1)!\quad {\text{untuk}}\quad n>0,} {\displaystyle n!=n(n-1)!\quad {\text{untuk}}\quad n>0,}

dan kondisi awal

0 ! = 1. {\displaystyle 0!=1.} {\displaystyle 0!=1.}

Peta logistik

Contoh relasi perulangan adalah peta logistik:

x n + 1 = r x n ( 1 − x n ) , {\displaystyle x_{n+1}=rx_{n}(1-x_{n}),} {\displaystyle x_{n+1}=rx_{n}(1-x_{n}),}

dengan konstanta tertentu r ; mengingat istilah awal x0 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 linier yang homogen dengan koefisien konstan (lihat di bawah). Urutan Fibonacci ditentukan menggunakan pengulangan

F n = F n − 1 + F n − 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}} {\displaystyle F_{n}=F_{n-1}+F_{n-2}}

dengan kondisi awal (nilai benih)

F 0 = 0 {\displaystyle F_{0}=0} {\displaystyle F_{0}=0}
F 1 = 1. {\displaystyle F_{1}=1.} {\displaystyle F_{1}=1.}

Secara eksplisit, pengulangan menghasilkan persamaan

F 2 = F 1 + F 0 {\displaystyle F_{2}=F_{1}+F_{0}} {\displaystyle F_{2}=F_{1}+F_{0}}
F 3 = F 2 + F 1 {\displaystyle F_{3}=F_{2}+F_{1}} {\displaystyle F_{3}=F_{2}+F_{1}}
F 4 = F 3 + F 2 {\displaystyle F_{4}=F_{3}+F_{2}} {\displaystyle F_{4}=F_{3}+F_{2}}

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 t2 = t + 1; fungsi pembangkit dari barisan tersebut adalah fungsi rasional

t 1 − t − t 2 . {\displaystyle {\frac {t}{1-t-t^{2}}}.} {\displaystyle {\frac {t}{1-t-t^{2}}}.}

Koefisien binomial

Contoh sederhana dari relasi perulangan multidimensi diberikan oleh koefisien binomial ( n k ) {\displaystyle {\tbinom {n}{k}}} {\displaystyle {\tbinom {n}{k}}}, yang menghitung jumlah cara memilih elemen k dari satu set elemen n . Mereka dapat dihitung oleh relasi perulangan

( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) , {\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},} {\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}

dengan kasus dasar ( n 0 ) = ( n n ) = 1 {\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1} {\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}. 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: ( n k ) = n ! k ! ( n − k ) ! . {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.} {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}

Hubungan persamaan perbedaan didefinisikan secara sempit

Diberikan urutan urutan { a n } n = 1 ∞ {\displaystyle \left\{a_{n}\right\}_{n=1}^{\infty }} {\displaystyle \left\{a_{n}\right\}_{n=1}^{\infty }} dari bilangan riil: perbedaan pertama Δ ( a n ) {\displaystyle \Delta (a_{n})} {\displaystyle \Delta (a_{n})} didefinisikan sebagai

Δ ( a n ) = a n + 1 − a n . {\displaystyle \Delta (a_{n})=a_{n+1}-a_{n}.} {\displaystyle \Delta (a_{n})=a_{n+1}-a_{n}.}

Perbedaan kedua Δ 2 ( a n ) {\displaystyle \Delta ^{2}(a_{n})} {\displaystyle \Delta ^{2}(a_{n})} didefinisikan sebagai

Δ 2 ( a n ) = Δ ( a n + 1 ) − Δ ( a n ) , {\displaystyle \Delta ^{2}(a_{n})=\Delta (a_{n+1})-\Delta (a_{n}),} {\displaystyle \Delta ^{2}(a_{n})=\Delta (a_{n+1})-\Delta (a_{n}),}

yang dapat disederhanakan menjadi

Δ 2 ( a n ) = a n + 2 − 2 a n + 1 + a n . {\displaystyle \Delta ^{2}(a_{n})=a_{n+2}-2a_{n+1}+a_{n}.} {\displaystyle \Delta ^{2}(a_{n})=a_{n+2}-2a_{n+1}+a_{n}.}

Lebih umum lagi: k-perbedaan dari urutan an ditulis sebagai Δ k ( a n ) {\displaystyle \Delta ^{k}(a_{n})} {\displaystyle \Delta ^{k}(a_{n})} didefinisikan secara rekursif sebagai

Δ k ( a n ) = Δ k − 1 ( a n + 1 ) − Δ k − 1 ( a n ) = ∑ t = 0 k ( k t ) ( − 1 ) t a n + k − t . {\displaystyle \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}.} {\displaystyle \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}.}

(Urutan dan perbedaannya terkait dengan transformasi binomial.) Definisi yang lebih ketat dari persamaan perbedaan adalah persamaan yang terdiri dari an dan itu kth 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,

a n + k = ( k 0 ) a n + ( k 1 ) Δ ( a n ) + ⋯ + ( k k ) Δ k ( a n ) . {\displaystyle a_{n+k}={k \choose 0}a_{n}+{k \choose 1}\Delta (a_{n})+\cdots +{k \choose k}\Delta ^{k}(a_{n}).} {\displaystyle a_{n+k}={k \choose 0}a_{n}+{k \choose 1}\Delta (a_{n})+\cdots +{k \choose k}\Delta ^{k}(a_{n}).}

Dengan demikian, persamaan perbedaan dapat didefinisikan sebagai persamaan yang melibatkan an, an-1, an-2 dll. (atau dengan kata lain an, an+1, an+2 dll.)

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

3 Δ 2 ( a n ) + 2 Δ ( a n ) + 7 a n = 0 {\displaystyle 3\Delta ^{2}(a_{n})+2\Delta (a_{n})+7a_{n}=0} {\displaystyle 3\Delta ^{2}(a_{n})+2\Delta (a_{n})+7a_{n}=0}

setara dengan hubungan perulangan

3 a n + 2 = 4 a n + 1 − 8 a n . {\displaystyle 3a_{n+2}=4a_{n+1}-8a_{n}.} {\displaystyle 3a_{n+2}=4a_{n+1}-8a_{n}.}

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.[3]

Stabilitas

Stabilitas pengulangan tingkat tinggi linier

Pengulangan linear order d,

a n = c 1 a n − 1 + c 2 a n − 2 + ⋯ + c d a n − d , {\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},} {\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},}

memiliki persamaan karakteristik

λ d − c 1 λ d − 1 − c 2 λ d − 2 − ⋯ − c d λ 0 = 0. {\displaystyle \lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.} {\displaystyle \lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.}

Pengulangannya adalah 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 kesatuan dalam nilai absolut.

Stabilitas pengulangan matriks orde pertama linear

Artikel utama: Persamaan perbedaan matriks

Dalam persamaan perbedaan matriks orde pertama

[ x t − x ∗ ] = A [ x t − 1 − x ∗ ] {\displaystyle [x_{t}-x^{*}]=A[x_{t-1}-x^{*}]} {\displaystyle [x_{t}-x^{*}]=A[x_{t-1}-x^{*}]}

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.)

Hubungan dengan persamaan diferensial

Saat menyelesaikan sebuah persamaan diferensial biasa secara numerik, seseorang biasanya menemukan relasi perulangan. Misalnya, saat memecahkan masalah nilai awal

y ′ ( t ) = f ( t , y ( t ) ) ,     y ( t 0 ) = y 0 , {\displaystyle y'(t)=f(t,y(t)),\ \ y(t_{0})=y_{0},} {\displaystyle y'(t)=f(t,y(t)),\ \ y(t_{0})=y_{0},}

dengan metode Euler dan ukuran langkah h , seseorang menghitung nilainya

y 0 = y ( t 0 ) ,     y 1 = y ( t 0 + h ) ,     y 2 = y ( t 0 + 2 h ) ,   … {\displaystyle y_{0}=y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots } {\displaystyle y_{0}=y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots }

oleh nilai

y n + 1 = y n + h f ( t n , y n ) , t n = t 0 + n h {\displaystyle \,y_{n+1}=y_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh} {\displaystyle \,y_{n+1}=y_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh}

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

Lihat pula

  • 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

Catatan

  1. ↑ Lipschutz, Seymour; Lipson, Marc (2008). Matematika Diskret. Diterjemahkan oleh Dr. Thombi Layukallo. Jakarta: Erlangga. Pemeliharaan CS1: Status URL (link)
  2. ↑ Jacobson, Nathan , Basic Algebra 2 (2nd ed.), § 0.4. pg 16.
  3. ↑ Partial difference equations, Sui Sun Cheng, CRC Press, 2003, ISBN 978-0-415-29884-1

Referensi

  • Batchelder, Paul M. (1967). An introduction to linear difference equations. Dover Publications.
  • Miller, Kenneth S. (1968). Linear difference equations. W. A. Benjamin.
  • Fillmore, Jay P.; Marx, Morris L. (1968). "Linear recursive sequences". SIAM Rev. Vol. 10, no. 3. hlm. 324–353. JSTOR 2027658.
  • Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association.
  • 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. 62–90.
  • Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (Edisi 2). Addison-Wesley. ISBN 0-201-55802-5.
  • Enders, Walter (2010). Applied Econometric Times Series (Edisi 3). Diarsipkan dari asli tanggal 2014-11-10.
  • Cull, Paul; Flahive, Mary; Robson, Robbie (2005). Difference Equations: From Rabbits to Chaos. Springer. ISBN 0-387-23234-6. chapter 7.
  • Jacques, Ian (2006). Mathematics for Economics and Business (Edisi Fifth). Prentice Hall. hlm. 551–568. ISBN 0-273-70195-9. Chapter 9.1: Difference Equations.
  • Minh, Tang; Van To, Tan (2006). "Using generating functions to solve linear inhomogeneous recurrence equations" (PDF). Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06. hlm. 399–404. Diarsipkan dari asli (PDF) tanggal 2016-03-04. Diakses tanggal 2020-10-21.
  • Polyanin, Andrei D. "Difference and Functional Equations: Exact Solutions". at EqWorld - The World of Mathematical Equations.
  • Polyanin, Andrei D. "Difference and Functional Equations: Methods". at EqWorld - The World of Mathematical Equations.
  • Wang, Xiang-Sheng; Wong, Roderick (2012). "Asymptotics of orthogonal polynomials via recurrence relations". Anal. Appl. 10 (2): 215–235. arXiv:1101.4371. doi:10.1142/S0219530512500108.

Pranala luar

  • Hazewinkel, Michiel, ed. (2001) [1994], "Recurrence relation", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
  • (Inggris) Weisstein, Eric W. "Recurrence Equation". MathWorld.
  • "OEIS Index 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)
Basis data pengawasan otoritas Sunting di Wikidata
Internasional
  • GND
Nasional
  • Amerika Serikat
  • Republik Ceko
  • Israel
Lain-lain
  • Yale LUX

Bagikan artikel ini

Share:

Daftar Isi

  1. Definisi
  2. Contoh
  3. Faktorial
  4. Peta logistik
  5. Bilangan Fibonacci
  6. Koefisien binomial
  7. Hubungan persamaan perbedaan didefinisikan secara sempit
  8. Dari urutan ke kisi
  9. Stabilitas
  10. Stabilitas pengulangan tingkat tinggi linier
  11. Stabilitas pengulangan matriks orde pertama linear
  12. Hubungan dengan persamaan diferensial
  13. Lihat pula
  14. Catatan
  15. Referensi
  16. Pranala luar

Artikel Terkait

Barisan Fibonacci

terjadi pada semua spesies). Barisan Fibonacci dapat didefinisikan oleh relasi perulangan F 0 = 0 , F 1 = 1 , {\displaystyle F_{0}=0,\quad F_{1}=1,} dan F n

Kereta api Manahan

layanan kereta api di Indonesia

Kereta api Argo Anjasmoro

layanan kereta api di Indonesia

Jakarta Aktual
Jakarta Aktual© 2026