Penyelesai Relasi Rekurensi

Tentang Penyelesai Relasi Rekurensi

Penyelesai Relasi Rekurensi menghitung solusi bentuk tertutup dari setiap rekurensi homogen linear dengan koefisien konstan dengan menyelesaikan persamaan karakteristiknya, memplot akar-akar pada bidang kompleks, dan menghasilkan N suku pertama dari urutan tersebut. Masukkan rekurensi baik sebagai daftar koefisien teratur atau sebagai ekspresi matematika alami seperti a(n) = 3·a(n−1) − 2·a(n−2), dan alat ini menangani akar riil yang berbeda, akar berulang, dan pasangan konjugasi kompleks secara otomatis.

Apa Itu Relasi Rekurensi Linear?

Sebuah relasi rekurensi homogen linear dengan koefisien konstan orde k memiliki bentuk:

di mana c₁, c₂, …, c_k adalah bilangan riil tetap dan k adalah ordenya. Bersama dengan k nilai awal a(0), a(1), …, a(k−1), rekurensi mendefinisikan setiap suku berikutnya secara unik. Contoh klasiknya meliputi:

• Fibonacci: a(n) = a(n−1) + a(n−2), nilai awal 0, 1 → 0, 1, 1, 2, 3, 5, 8, 13, …
• Lucas: a(n) = a(n−1) + a(n−2), nilai awal 2, 1 → 2, 1, 3, 4, 7, 11, 18, 29, …
• Angka Pell: a(n) = 2·a(n−1) + a(n−2), nilai awal 0, 1 → 0, 1, 2, 5, 12, 29, 70, …
• Tribonacci: a(n) = a(n−1) + a(n−2) + a(n−3), nilai awal 0, 0, 1 → 0, 0, 1, 1, 2, 4, 7, 13, 24, …

Metode Persamaan Karakteristik

Untuk menemukan formula bentuk tertutup bagi a(n), kita mencari solusi dalam bentuk a(n) = rⁿ. Mensubstitusi ke dalam rekurensi dan membagi dengan r^n−k menghasilkan:

Ini adalah persamaan karakteristik — polinomial derajat k dalam r. Berdasarkan Teorema Dasar Aljabar, ia memiliki tepat k akar kompleks (menghitung multiplisitas). Solusi umum untuk rekurensi tergantung pada struktur akar-akar ini:

Kasus 1: Akar riil berbeda r₁, …, r_k

Konstanta A₁, …, A_k ditetapkan dengan memasukkan n = 0, 1, …, k−1 dan menyelesaikan sistem linear terhadap nilai awal.

Kasus 2: Akar r dengan multiplisitas m

Setiap akar yang berulang berkontribusi m urutan basis independen linear rⁿ, n·rⁿ, n²·rⁿ, …, n^m−1·rⁿ.

Kasus 3: Akar konjugasi kompleks r = ρ·e^iθ, r̄ = ρ·e^−iθ

Ketika rekurensi memiliki koefisien riil, akar kompleks selalu datang dalam pasangan konjugasi. Setiap pasangan bergabung menjadi suku osilasi riil dengan selubung geometris ρⁿ dan frekuensi θ.

Klasifikasi Pertumbuhan Berdasarkan Akar Dominan

Misalkan ρ = max|r_i| adalah magnitudo akar terbesar (jari-jari spektral). Perilaku jangka panjang dari a(n) diatur oleh:

Fibonacci — Contoh Pengerjaan

Pertimbangkan rekurensi Fibonacci a(n) = a(n−1) + a(n−2) dengan a(0) = 0 dan a(1) = 1.

1. Persamaan karakteristik: r² − r − 1 = 0
2. Akar (rumus kuadrat): r = (1 ± √5) / 2, jadi φ ≈ 1.6180 dan ψ ≈ −0.6180
3. Bentuk umum: a(n) = A·φⁿ + B·ψⁿ
4. Terapkan kondisi awal: A + B = 0 dan A·φ + B·ψ = 1, yang menghasilkan A = 1/√5, B = −1/√5
5. Formula Binet: a(n) = (φⁿ − ψⁿ) / √5

Karena |ψ| < 1, suku kedua menghilang saat n → ∞, sehingga a(n) kira-kira φⁿ / √5 — inilah sebabnya angka Fibonacci tumbuh kira-kira dengan faktor φ per langkah.

Cara Menggunakan Penyelesai Ini

1. Pilih mode input: Terpandu memungkinkan Anda memilih orde dan memasukkan koefisien yang dipisahkan koma; Ekspresi bentuk bebas menerima rekurensi lengkap seperti a(n) = a(n-1) + 6*a(n-2) - 8*a(n-3).
2. Masukkan koefisien atau ekspresi. Desimal (0.5) dan pecahan (1/2) keduanya diterima.
3. Berikan nilai awal. Anda harus menyediakan tepat k nilai yang sesuai dengan orde rekurensi: a(0), a(1), …, a(k−1).
4. Pilih berapa banyak suku untuk ditampilkan (hingga 60).
5. Klik Selesaikan. Halaman hasil menunjukkan persamaan karakteristik, lokasi akar pada bidang kompleks, formula bentuk tertutup, dan diagram batang animasi dari urutan tersebut.

Kasus yang Didukung & Batasan

• Orde: 1 sampai 6 (polinomial karakteristik diselesaikan secara numerik untuk orde ≥ 3 melalui iterasi Durand–Kerner).
• Koefisien konstan riil: koefisien kompleks tidak didukung; Anda harus memiliki c_i riil.
• Hanya homogen: Alat ini menyelesaikan rekurensi homogen (tidak ada suku paksaan seperti + n atau + 2ⁿ). Untuk rekurensi non-homogen, selesaikan bagian homogen di sini dan tambahkan solusi partikular secara terpisah.
• Presisi numerik: hasil dihitung dalam presisi ganda IEEE-754; untuk rekurensi yang sangat tidak stabil (rentang magnitudo akar yang lebar), lencana verifikasi akan menandai setiap penyimpangan antara nilai bentuk tertutup dan iteratif.

Aplikasi

• Analisis algoritma: waktu proses algoritma divide-and-conquer sering kali memenuhi rekurensi linear (teorema Master).
• Kombinatorika: menghitung urutan — angka Catalan, derangement, ubin — sering kali diberikan oleh rekurensi.
• Pemrosesan sinyal: sistem LTI waktu-diskrit dengan umpan balik adalah rekurensi linear; stabilitasnya ditentukan oleh lokasi akar (di dalam lingkaran satuan ⇔ stabil).
• Dinamika populasi & keuangan: bunga majemuk, model populasi terstruktur usia, deret waktu autoregresif AR(p).
• Fisika: model kisi satu dimensi, Hamiltonian ikatan kuat, dan metode matriks transfer.

Pertanyaan yang Sering Diajukan

Apa itu relasi rekurensi linear dengan koefisien konstan?

Relasi rekurensi linear dengan koefisien konstan adalah persamaan bentuk a(n) = c₁·a(n−1) + c₂·a(n−2) + … + c_k·a(n−k), di mana c₁, c₂, …, c_k adalah bilangan riil tetap dan k adalah ordenya. Setiap suku dalam urutan adalah kombinasi linear dari k suku sebelumnya. Contoh umum termasuk rekurensi Fibonacci a(n) = a(n−1) + a(n−2) dan rekurensi Lucas dengan nilai awal yang berbeda.

Apa itu persamaan karakteristik dari sebuah rekurensi?

Diberikan rekurensi a(n) = c₁·a(n−1) + c₂·a(n−2) + … + c_k·a(n−k), persamaan karakteristiknya adalah r^k − c₁·r^k−1 − c₂·r^k−2 − … − c_k = 0. Persamaan polinomial ini memiliki tepat k akar kompleks (menghitung multiplisitas), dan setiap solusi dari rekurensi adalah kombinasi linear dari urutan bentuk n^j·rⁿ di mana r adalah akar dan j berjalan hingga multiplisitasnya dikurangi 1.

Bagaimana cara mendapatkan formula bentuk tertutup untuk a(n)?

Selesaikan persamaan karakteristik untuk menemukan akar-akarnya r₁, r₂, …, r_k. Jika semua akar berbeda, bentuk tertutupnya adalah a(n) = A₁·r₁ⁿ + A₂·r₂ⁿ + … + A_k·r_kⁿ, di mana konstanta A_i ditentukan dengan memasukkan nilai awal dan menyelesaikan sistem linear. Jika akar r memiliki multiplisitas m, ia berkontribusi pada m suku basis: rⁿ, n·rⁿ, n²·rⁿ, …, n^m−1·rⁿ. Kalkulator ini melakukan seluruh prosedur secara otomatis.

Apa arti akar kompleks bagi urutan tersebut?

Ketika rekurensi memiliki koefisien riil, akar kompleks selalu muncul dalam pasangan konjugasi r = ρ·e^iθ dan r̄ = ρ·e^−iθ. Pasangan tersebut menghasilkan perilaku osilasi: bentuk tertutup mengandung suku 2·ρⁿ·[α·cos(nθ) − β·sin(nθ)]. Jika ρ sama dengan 1, urutan berosilasi dengan amplitudo konstan; jika ρ kurang dari 1, osilasi meluruh; jika ρ lebih besar dari 1, amplitudo tumbuh secara geometris.

Mengapa akar dominan memberi tahu saya cara urutan tumbuh?

Saat n menjadi besar, suku dengan |r| terbesar mendominasi setiap suku lainnya karena magnitudonya tumbuh lebih cepat. Jadi jika ρ = max|r_i|, maka |a(n)| secara asimtotik proporsional dengan ρⁿ, dengan faktor polinomial tambahan jika akar dominan berulang. Penyelesai mengklasifikasikan urutan Anda berdasarkan prinsip ini: konvergen ke nol ketika ρ < 1, terbatas ketika ρ = 1, pertumbuhan geometris ketika ρ > 1.

Dapatkah alat ini menyelesaikan urutan Fibonacci?

Ya. Masukkan rekurensi a(n) = a(n−1) + a(n−2) dengan nilai awal 0, 1. Kalkulator menurunkan persamaan karakteristik r² − r − 1 = 0 dengan akar φ = (1 + √5)/2 dan ψ = (1 − √5)/2, dan mengembalikan formula Binet a(n) = (φⁿ − ψⁿ) / √5. Klik contoh cepat Fibonacci di atas formulir input untuk melihat solusi pengerjaan lengkap.

Apakah alat ini menangani rekurensi non-homogen seperti a(n) = a(n−1) + n?

Tidak — alat ini hanya menyelesaikan rekurensi homogen (tanpa suku paksaan). Untuk rekurensi non-homogen, uraikan solusi umum menjadi bagian homogen (dapat diselesaikan di sini) ditambah solusi partikular yang sesuai dengan suku paksaan. Ansatz solusi partikular yang umum adalah: polinomial dengan derajat yang sama dengan paksaan polinomial, C·rⁿ untuk paksaan eksponensial, atau A·cos(nθ) + B·sin(nθ) untuk paksaan trigonometri.

Bacaan Lebih Lanjut

• Relasi rekurensi — Wikipedia
• Rekurensi linear dengan koefisien konstan — Wikipedia
• Persamaan karakteristik — Wikipedia
• Urutan Fibonacci — Wikipedia
• Metode Durand–Kerner — Wikipedia

Alat terkait lainnya:

Peralatan urutan:

• Kalkulator Barisan Aritmatika Presisi Tinggi
• Daftar Kubik
• n Bilangan Prima Pertama
• Kalkulator Barisan Geometri
• Daftar Bilangan Fibonacci
• Daftar Bilangan Prima
• Daftar Bilangan Kuadrat
• Kalkulator Konjektur Collatz Baru
• Kalkulator Angka Bahagia Baru
• Generator Persegi Ajaib Baru
• Generator Bilangan Catalan Baru
• Kalkulator Notasi Sigma Penjumlahan Baru
• Kalkulator Notasi Produk Pi Baru
• Generator Segitiga Pascal Baru
• Pencari Prima Kembar Baru
• Kalkulator Fungsi Partisi Baru
• Penyelesai Relasi Rekurensi Baru