Relasi perulangan - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-25T09:02:56Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 25 Agustus 2026 09.02
Baris 1:		Baris 1:
	Dalam [[matematika]], '''relasi perulangan''' 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.		Dalam [[matematika]], '''relasi perulangan'''<ref>Seymour Lipschutz. ''Matematika Diskret''. Erlangga. 2008.</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 ''.		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 ''.
Baris 6:		Baris 6:
	''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		''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>		:<math>u_n=\varphi(n, u_{n-1})\quad\text{untuk}\quad n>0,</math>
	di mana		di mana
	:<math>\varphi:\mathbb N\times X \to X</math>		:<math>\varphi:\mathbb N\times X \to X</math>
	adalah sebuah fungsi, di mana 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.		adalah sebuah fungsi, di mana 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.		Sangat mudah untuk mengubah definisi untuk mendapatkan urutan mulai dari indeks 1 atau lebih tinggi.

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

Baris 84:		Baris 84:
	Sebenarnya, mudah dilihat bahwa,		Sebenarnya, mudah dilihat bahwa,

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

	Dengan demikian, persamaan perbedaan dapat didefinisikan sebagai persamaan yang melibatkan		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. (atau dengan kata lain
	''a<sub>n</sub>'', ''a<sub>n+1</sub>'', ''a<sub>n+2</sub>'' dll.)		''a<sub>n</sub>'', ''a<sub>n+1</sub>'', ''a<sub>n+2</sub>'' dll.)
Baris 107:		Baris 107:

	=== Dari urutan ke kisi ===		=== 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'''.		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,</ref>

	== Stabilitas ==		== Stabilitas ==

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

	=== Stabilitas pengulangan matriks orde pertama linear ===		=== Stabilitas pengulangan matriks orde pertama linear ===


	Dalam persamaan perbedaan matriks orde pertama		Dalam persamaan perbedaan matriks orde pertama

Baris 130:		Baris 127:

	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.)		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 ==		== Hubungan dengan persamaan diferensial ==
Baris 148:		Baris 144:

	== Lihat pula ==		== Lihat pula ==


	* [[Fungsi Holonomis\|Urutan Holonomis]]		* [[Fungsi Holonomis\|Urutan Holonomis]]
	* [[Fungsi berulang]]		* [[Fungsi berulang]]
Baris 164:		Baris 158:
	* [[Integrasi dengan rumus pengurangan]]		* [[Integrasi dengan rumus pengurangan]]
	* [[Induksi matematika]]		* [[Induksi matematika]]


	== Catatan ==		== Catatan ==


	~~== Referensi ==~~
	*
	*
	*
	*
	* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. [[MIT Press]] and [[McGraw-Hill]], 1990. . Chapter 4: Recurrences, pp. 62–90.
	*
	*
	* chapter 7.
	* Chapter 9.1: Difference Equations.
	*
	* at EqWorld - The World of Mathematical Equations.
	* at EqWorld - The World of Mathematical Equations.
	*

	== Pranala luar ==		== Pranala luar ==
	*		*
	*		*
	* [[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)		* [[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)

			== Referensi ==
			<references />

	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Relasi+perulangan&oldid=29303195 Wikipedia bahasa Indonesia], revisi 29303195 (2026-06-01T11:05:27Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Relasi+perulangan&oldid=29303195 Wikipedia bahasa Indonesia], revisi 29303195 (2026-06-01T11:05:27Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29303195; atribusi sumber disertakan.

2026-08-25T08:34:04Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29303195; atribusi sumber disertakan.

Halaman baru

Dalam [[matematika]], '''relasi perulangan''' 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>
di mana
:<math>\varphi:\mathbb N\times X \to X</math>
adalah sebuah fungsi, di mana 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.

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

Ini mendefinisikan relasi perulangan ''orde pertama''. Relasi perulangan '' orde'' 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>

di mana <math>\varphi: \mathbb N\times X^k \to X</math> adalah fungsi yang melibatkan elemen berurutan dari urutan tersebut.
Dalam kasus ini, nilai awal 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''0 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''2 = ''t'' + 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 ''an'' 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 an'' dan itu ''k''th 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
''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

:<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'''.

== 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 ===

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

== 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 ==

* [[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]]

== Catatan ==

== Referensi ==
*
*
*
*
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. [[MIT Press]] and [[McGraw-Hill]], 1990. . Chapter 4: Recurrences, pp. 62–90.
*
*
* chapter 7.
* Chapter 9.1: Difference Equations.
*
* at EqWorld - The World of Mathematical Equations.
* at EqWorld - The World of Mathematical Equations.
*

== Pranala luar ==
*
*
* [[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)

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Relasi+perulangan&oldid=29303195 Wikipedia bahasa Indonesia], revisi 29303195 (2026-06-01T11:05:27Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.