رابطه بازگشتی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

رابطهٔ بازگشتی، در ریاضیات، دنباله‌ای است که به صورت بازگشتی تعریف می‌شود.

معادلهٔ تفاضلی نوع خاصی از رابطهٔ بازگشتی است.

بسیاری از روابط بازگشتی ممکن است رفتارهای پیچیده‌ای از خودشان نشان دهند این نوع روابط توسط فیزیکدانان و ریاضیدانان در شاخه‌ای از ریاضیات به نام انالیز غیر خطی مطالعه می‌شوند. حل یک معادله معادله بازگشتی یعنی به دست اوردن یک فرم بسته برای ان (یک تابع غیر بازگشتی از n).

رابطهٔ بازگشتی خطی همگن با ضرایب ثابت[ویرایش]

اصطلاح خطی به این معناست که هر جمله‌ای این توالی به صورت یک تابع خطی از جمله‌های قبلی تعریف می‌شود. مرتبهٔ یک رابطهٔ بازگشتی خطی برابراست با تعداد جمله‌های قبلی مورد نیاز توسط تعریف. به عنوان مثال a_n = a_{n-2} از مرتبهٔ ۲ است.زیرا حتماً باید جملهٔ قبل وجود داشته باشند(چه هر دو استفاده شوند، چه نشوند)

فرم کلی رابطهٔ بازگشتی خطی همگن از مرتبهٔ d: :a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d} + c \,

c \,وc_i \, می‌توانند به n وابسته باشند اما a_i \,ها نه. اگر تمامc_i \,ها مستقل از n باشند گفته می‌شود این رابطه دارای ضرایب ثابت است، همچنین اگر c = 0 \, گفته می‌شود که رابطهٔ بازگشتی خطی است که گاهی LRS نیز گفته می‌شود.

رابطهٔ بازگشتی خطی با مقادیر اولیهٔ (شرایط اولیه)a_0,\dots,a_{d-1} یک توالی یکتا را مشخص می‌کند.

مثال:اعداد فیبوناچی[ویرایش]

اعداد فیبوناچی به صورت رابطه بازگشتی خطی تعریف می‌شوند: F_{n} = F_{n-1}+F_{n-2} \, با مقادیر اولیهٔ :F_1 = 1 \,و:F_2 = 1. \, دنبالهٔ اعداد فیبوناچی ...۱،۱،۲،۳،۵،۸ این دنباله را می‌توان با راه حل ماتریسی که در زیر شرح داده می‌شود حل کرد.

حل کردن توسط جبر خطی[ویرایش]

با داشتن یک رابطهٔ بازگشتی خطی می‌توان ماتریسی برای ان نوشت :\begin{bmatrix}a_0\\
\vdots\\
a_{d-1}\end{bmatrix} = b_1v_1 + \cdots + b_dv_d

\begin{bmatrix}a_n\\
\vdots\\
a_{n+(d-1)}\end{bmatrix}
= C^n\begin{bmatrix}a_0\\
\vdots\\
a_{d-1}\end{bmatrix}
= C^n(b_1v_1 + \cdots + b_dv_d)
= \lambda_1^nb_1v_1 + \cdots + \lambda_d^n b_dv_d

پس فرم بسته a_n بدست امد.

حل کردن به صورت عمومی[ویرایش]

راه حل‌ها برای رابطهٔ بازگشتی اصولی با قاعده هستند . اغلب با تابع مولد یا با توجه به این کهrn یک جواب برای مقادیر ویژه r است.رابطهٔ باز گشتی زیر را در نظر بگیرید:a_{n}=Aa_{n-1}+Ba_{n-2}. \,فرض کنید جواب ان به فرم an = rn است . در نتیجه :r^{n}=Ar^{n-1}+Br^{n-2}. \, با تقسیم بر rn − ۲

r^2=Ar+B, \,
r^2-Ar-B=0. \,

به این معادله، معادله مشخصهٔ رابطه بازگشتی گفته می‌شود با حل این معادله دو مقدار برایr، بدست می اید که اگر متمایز باشند جواب عبارتست از :

a_n = C\lambda_1^n+D\lambda_2^n \,

اما اگر λ۱، λ۲ برابر باشند جواب عبارتست از :

a_n = C\lambda^n+Dn\lambda^n \,

CوD با مقادیر اولیه a۰ = a، a۱ = b مشخص می‌شوند.

منابع[ویرایش]

ویکی‌پدیای انگلیسی