Relasi pengulangan

Dalam matematika, relasi pengulangan adalah persamaan yang rekursif 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 pengulangan tertentu. Namun, "persamaan perbedaan" sering digunakan untuk merujuk ke hubungan pengulangan dengan apa saja .

DefinisiSunting

Hubungan 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 pengulangan memiliki bentuk

 

dimana

 

adalah sebuah fungsi, di mana X adalah himpunan yang harus dimiliki elemen-elemen urutan. Untuk apapun  , ini mendefinisikan urutan unik dengan   sebagai elemen pertamanya, yang disebut nilai awal.[1]

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

Ini mendefinisikan hubungan pengulangan urutan pertama . Relasi pengulangan order k memiliki bentuk

 

dimana   adalah fungsi yang melibatkan k elemen berurutan dari urutan tersebut. Dalam kasus ini, nilai awal k diperlukan untuk menentukan urutan.

ContohSunting

FaktorialSunting

Faktorial ditentukan oleh relasi perulangan

 

dan kondisi awal

 

Peta logistikSunting

Contoh relasi pengulangan adalah peta logistik:

 

dengan konstanta tertentu r ; mengingat istilah awal x0 setiap suku berikutnya ditentukan oleh relasi ini.

Memecahkan relasi pengulangan berarti memperoleh solusi bentuk tertutup: fungsi non-rekursif dari n .

Angka FibonacciSunting

Pengulangan urutan dua yang dipenuhi oleh Bilangan Fibonacci adalah pola dasar dari hubungan pengulangan linier yang homogen dengan koefisien konstan (lihat di bawah). Urutan Fibonacci ditentukan menggunakan pengulangan

 

dengan kondisi awal (nilai benih)

 
 

Secara eksplisit, pengulangan menghasilkan persamaan

 
 
 

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

 

Koefisien binomialSunting

Contoh sederhana dari relasi pengulangan multidimensi diberikan oleh koefisien binomial  , yang menghitung jumlah cara memilih elemen k dari satu set elemen n . Mereka dapat dihitung oleh relasi perulangan

 

dengan kasus dasar  . 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:  

Hubungan persamaan perbedaan didefinisikan secara sempitSunting

Diberikan urutan urutan   dari bilangan riil: perbedaan pertama   didefinisikan sebagai

 

Perbedaan kedua   didefinisikan sebagai

 

yang dapat disederhanakan menjadi

 

Lebih umum lagi: k-perbedaan dari urutan an ditulis sebagai   didefinisikan secara rekursif sebagai

 

(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,

 

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

 

setara dengan hubungan perulangan

 

Dengan demikian seseorang dapat menyelesaikan banyak hubungan pengulangan 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 pengulangan 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 kisiSunting

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

StabilitasSunting

Stabilitas pengulangan tingkat tinggi linierSunting

Pengulangan linear order d,

 

memiliki persamaan karakteristik

 

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 linearSunting

Dalam persamaan perbedaan matriks orde pertama

 

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 diferensialSunting

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

 

dengan metode Euler dan ukuran langkah h , seseorang menghitung nilainya

 

oleh nilai

 

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

Lihat pulaSunting

CatatanSunting

  1. ^ Jacobson, Nathan , Basic Algebra 2 (2nd ed.), § 0.4. pg 16.
  2. ^ Partial difference equations, Sui Sun Cheng, CRC Press, 2003, ISBN 978-0-415-29884-1

ReferensiSunting

Pranala luarSunting