رابطهٔ بازگشتی، در ریاضیات، دنباله‌ای است که به صورت بازگشتی تعریف میشود.
واژه مدل تفاضلی (difference equation) مربوط به حالت خاصی از رابطه بازگشتی می باشد. به هر حال، "مدل تفاضلی" برای اشاره به هر گونه رابطه بازگشتی به کار می رود. نمونه ای از یک رابطه بازگشتی، نقشه لوجستیک (منطقی):
با ثابت داده شده r می باشد که با در نظر گرفتن x0 به عنوان مقدار اولیه، تمام مقادیر بعدی با این رابطه بدست می آید. بسیاری از روابط بازگشتی ممکن است رفتارهای پیچیده‌ای از خودشان نشان دهند این نوع روابط توسط فیزیکدانان و ریاضیدانان در شاخه‌ای از ریاضیات به نام انالیز غیر خطی مطالعه می‌شوند. حل یک معادله معادله بازگشتی یعنی به دست اوردن یک فرم بسته برای آن (یک تابع غیر بازگشتی از n )
محتویات
۱ فیبوناچی
۲ ساختار
۲.۱ رابطه بازگشتی خطی همگن با ضرایب ثابت
۲.۲ تابع مولد گویا
۲.۳ روابط تفاضلی به دقت تعریف شده
۲.۴ از توالی به شبکه
۳ روش حل
۳.۱ روش های کلی
۳.۲ حل به روش جبر خطی
۳.۳ حل با تبدیل z
۳.۴ قضایا
۳.۵ حل روابط بازگشتی ناهمگن
۳.۶ روابط بازگشتی همگن خطی کلی
۳.۷ روش حل معادلات تفاضلی گویا از مرتبه یک
۴ ثبات
۴.۱ ثبات روابط بازگشتی مرتبه های بالاتر
۴.۲ ثبات ماتریس بازگشتی خطی از مرتبه اول
۴.۳ ثبات روابط بازگشتی غیرخطی اولین مرتبه
۵ روابط مدل های تفاضلی
۶ کاربردها
۶.۱ زیست شناسی
۶.۲ پردازش سیگنال دیجیتال
۶.۳ اقتصاد
۶.۴ علم کامپیوتر
۷ منابع
فیبوناچی
اعداد فیبوناچی نمونه اولیه ای از یک رابطه بازگشتی همگن با ضرائب ثابت می باشد. این اعداد با رابطه خطی بازگشتی زیر تعریف می شوند:
F_n = F_{n-1}+F_{n-2}
با مقادیر اولیه :F_0 = 0
F_1 = 1
مشخصا رابطه بازگشتی معادله های زیر را ایجاد می کند:
F_2 = F_1 + F_0
F_3 = F_2 + F_1
F_4 = F_3 + F_2
به توالی اعداد فیبوناچی می رسیم که به شکل:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... آن را می توان با روش هایی که در ادامه توضیح داده می شوند، حل کرد؛ روش هایی که عبارتی بسته (closed-form expression) شامل توان های دو ریشه چندجمله ای مشخصه t2 = t + 1 دارند. تابع ایجاد کننده توالی، تابع گویای زیر است:
\frac{t}{1-t-t^2}.
ساختار
رابطه بازگشتی خطی همگن با ضرایب ثابت
رابطه بازگشتی خطی همگن با ضرایب ثابت از مرتبه d، معادله ای به شکل زیر است:
a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d},
که در آن d ضرایب ci (برای تمام i ها) ثابت است. می توان گفت، لیست معادلات خطی همزمان نامتناهی است که برای هر n>d−1 می¬باشد. یک توالی که رابطه ای چنینی داشته باشد، توالی بازگشتی خطی یا LRS نامیده می شود. d درجه آزادی برای LRS وجود دارد بدین معنا که مقادیر اولیه a_0,\dots,a_{d-1}هر مقداری را می توانند بگیرند ولی رابطه بازگشتی خطی توالی یکتایی را مشخص می کند. ضرایب یکسان چندجمله ای مشخصه را ایجاد می کنند:
p(t)= t^d - c_1t^{d-1} - c_2t^{d-2}-\cdots-c_{d}
که ریشه های d نقش مهمی در یافتن و فهمیدن توالی های درست از لحاظ تابع بازگشتی دارند. اگر ریشه های معادله مشخصه تماما مشخص باشند، حال راه حل بازگشتی به شکل زیر خواهد بود:
a_n = k_1 r_1^n + k_2 r_2^n + \cdots + k_d r_d^n,
که در آن ضرایب ki برای متناسب کردن شرایط اولیه رابطه بازگشتی مشخص می شوند. وقتی که ریشه های یکسان برای چندین بار اتفاق می افتند، قسمت هایی از این فرمول که مربوط به موارد دوم و بیشتر از یک ریشه است در توان های افزایشی از n ضرب می شوند. برای مثال، اگر چندجمله ای مشخصه فاکتوری از x−r)3) با ریشه تکراری سه باره r باشد، راه حل به شکل زیر خواهد بود:
a_n = k_1 r^n + k_2 n r^n + k_3 n^2 r^n.
در کنار اعداد فیبوناچی، دیگر توالی های ایجاد شده توسط روابط بازگشتی خطی همگن شامل اعداد لوکاس و توالی لوکاس، اعداد یاکوبسال، اعداد پل و معادله پل می باشد.
تابع مولد گویا
توالی های بازگشتی خطی دقیقا توالی هایی هستند که تابع مولدشان یک تابع گویا است. مخرج چندجمله ای بدست آمده از چندجمله ای مشخصه با معکوس کردن ترتیب ضرائب است و صورت با مقادیر اولیه توالی مشخص می شود. ساده ترین حالت ها توالی های دوره ای a_n = a_{n-d}, n\geq dهستند که توالی a_0,a_1,\dots,a_{d-1},a_0,\dots و تابع مولدی مجموع سری هندسی زیر دارند:
\begin{align}\frac{a_0 + a_1 x^1 + \cdots + a_{d-1}x^{d-1}}{1-x^d} =& \left(a_0 + a_1 x^1 + \cdots + a_{d-1}x^{d-1}\right) + \left(a_0 + a_1 x^1 + \cdots + a_{d-1}x^{d-1}\right)x^d + \\& \left(a_0 + a_1 x^1 + \cdots + a_{d-1}x^{d-1}\right)x^{2d} + \cdots.\end{align}
عموما در مورد رابطه بازگشتی زیر:
a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d}
با تابع مولد :
a_0 + a_1x^1 + a_2 x^2 + \cdots,
سری ها در <ad</sub و بالاتر به وسیله چندجمله ای زیر متوقف می شوند:
1- c_1x^1 - c_2 x^2 - \cdots - c_dx^d.
که این یعنی ضرب تابع مولد در چندجمله¬ای در پی خواهد داشت:
b_n = a_n - c_1 a_{n-1} - c_2 a_{n-2} - \cdots - c_d a_{n-d}
به طوری که ضرایب x^n برای n ≥ d حذف می شوند. پس:
\left (a_0 + a_1x^1 + a_2 x^2 + \cdots \right ) \left (1- c_1x^1 - c_2 x^2 - \cdots - c_dx^d \right) = \left (b_0 + b_1x^1 + b_2 x^2 + \cdots + b_{d-1} x^{d-1} \right )
و با تقسیم خواهیم داشت:
a_0 + a_1x^1 + a_2 x^2 + \cdots =\frac{b_0 + b_1x^1 + b_2 x^2 + \cdots + b_{d-1} x^{d-1}}{1- c_1x^1 - c_2 x^2 - \cdots - c_dx^d},
که نشان دهنده تابع مولد به عنوان تابع گویا است. مخرج x^d p\left(x^{-1}\right), است که تبدیلی از چندجمله ای مشخصه است. می توان هر مضربی از آن را استفاده کرد ولی این نرمال سازی هر دو را انتخاب کرده تا رابطه ساده تری برای چندجمله ای مشخصه داشته باشد و همچنین داشته باشد b_0 = a_0
روابط تفاضلی به دقت تعریف شده
دنباله اعداد حقیقی \left\{a_n\right\}_{n=1}^\infty را در نظر بگیرید. اولین دنباله تفاضلی برابر
\Delta(a_n) = a_{n+1} - a_n\,
است. دومین دنباله به صورت
:\Delta^2(a_n) = \Delta(a_{n+1}) - \Delta(a_n)
تعریف می شود که می تواند به صورت
\Delta^2(a_n) = a_{n+2} - 2a_{n+1} + a_n
ساده سازی شود.
به صورت کلی دنباله تفاضلی kام به صورت زیر تعریف می شود:
\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}
تعریف محدودتری از معادله تفاضلی معادله ای است بر حسب an و kامین تفاضل.
در واقع معادله زیر را داریم: a_{n+k} = {n\choose 0}a_n + {n\choose 1} \Delta(a_n) + \cdots + {n\choose k} \Delta^n(a_n).
بنابراین معادله تفاضلی می تواند معادله ای بر حسب an, an-1, an-2 یا an, an+1, an+2 باشد.
از آنجایی که معادلات تفاضلی یکی از رایج ترین معادلات بازگشتی هستند، بعضی از نویسنده ها آنها را به جای هم به کار می برند. به طور مثال معادله تفاضلی :3\Delta^2(a_n) + 2\Delta(a_n) + 7a_n = 0 با دنباله بازگشتی زیر برابر است.
3a_{n+2} = 4a_{n+1} - 8a_n
بنابراین معادلات تفاضلی می توانند به صورت بازگشتی حل شوند و به صورت مشابه می توان روش حل معادلات دیفرانسیل معمولی را یافت. اگرچه اعداد آکرمن نمونه ای از دنباله بازگشتی هستند، به معادلات تفاضلی نگاشته نمی شوند. معادلات جمعی مرتبط به معادلات تفاضلی هستند همان طور که معادلات انتگرال مربوط به معادلات دیفرانسیل هستند.
از توالی به شبکه
روابط تک متغیر و یا بازگشتی یک بعدی در مورد دنباله است در حالی که روابط بازگشتی چند متغیر و یا n بعدی در مورد شبکه های n بعدی است. توابعی که بر روی شبکه های n بعدی تعریف می شوند، با معادلات تفاضلی جزئی قابل حل اند.
روش حل
روش های کلی
برای دنباله بازگشتی از مرتبه 1 داریم :a_{n}=r a_{n-1} در نظر می گیریم an = rnوa0 = 1 و روش کلی تر آن an = krnو a0 = k است. معادله مشخصه این عبارت به سادگی به دست می آید که برابر t − r = 0 است. راه حل برای معادلات با مرتبه ی بالا تر با قواعد و اصول به دست آمده ، غالبا استفاده از روش an = rn برای مواقعی است کهt = r یک ریشه معادله مشخصه است. این می تواند به طور مستقیم یا با تابع مولد یا ماتریس به دست آید.
به طور مثال دنباله :a_{n}=Aa_{n-1}+Ba_{n-2}. را در نظر بگیرید، این دنباله چه موقع جواب an = rn را دارد؟ این را با دنباله بازگشتی :r^{n}=Ar^{n-1}+Br^{n-2} جایگزین کنید، در می یابیم که برای همه n > 1 معادله درست است. با تقسیم بر rn−2، همان معادلات را به صورت زیر خواهیم داشت :
r^2=Ar+B,
r^2-Ar-B=0,
که یک معادله مشخصه برای دنباله بازگشتی است. با حل کردن معادله دو ریشه برای r خواهیم داشت: λ1, λ2 ، که این ریشه ها، ریشه های مشخصه یا مقادیر ویژه معادله مشخصه نامیده می شوند. با توجه به ریشه ها، روش های متفاوتی برای حل معادله وجود دارد. اگر متمایز باشند، راه حل کلی :a_n = C\lambda_1^n+D\lambda_2^n را داریم و اگر برابر بودند
a_n = C\lambda^n+Dn\lambda^n
این کلی ترین روش است و C,D با توجه به a0 , a1 به دست می آیند. برای حالاتی که مقادیر ویژه مختلط اند ( که منجر به مختلط شدن C,D نیز می شوند) استفاده از اعداد مختلط را می توان با بازنویسی راه حل به صورت مثلثاتی حذف کرد. در این حالت مقادیر ویژه را می توان \lambda_1, \lambda_2 = \alpha \pm \beta i.
نشان داد. هم چنین معادله
a_n = C\lambda_1^n+D\lambda_2^n
را می توان به صورت زیر نشان داد.
a_n = 2 M^n \left( E \cos(\theta n) + F \sin(\theta n)\right) = 2 G M^n \cos(\theta n - \delta),
که
\begin{array}{lcl} M = \sqrt{\alpha^2+\beta^2} & \cos (\theta) =\tfrac{\alpha}{M} & \sin( \theta) = \tfrac{\beta}{M} \\ C,D = E \mp F i & & \\ G = \sqrt{E^2+F^2} & \cos (\delta ) = \tfrac{E}{G} & \sin (\delta )= \tfrac{F}{G} \end{array}
E ,F ثایت های حقیقی اند که وابسته به شرایط اولیه هستند.استفاده از فرمول های زیر راه حل را می تواند ساده تر کند
\lambda_1+\lambda_2=2 \alpha = A,
\lambda_1 \cdot \lambda_2=\alpha^2+\beta^2=-B,
a_n = (-B)^{\frac{n}{2}} \left( E \cos(\theta n) + F \sin(\theta n)\right),
که a1 , a2 مقادیر اولیه هستند و
\begin{align} E &=\frac{-A a_1 + a_2}{B} \\ F &=-i \frac{A^2 a_1 - A a_2 +2 a_1 B}{B \sqrt{A^2+4B}} \\ \theta &=a\cos \left (\frac{A}{2 \sqrt{-B}} \right ) \end{align}
در این روش دیگر احتیاجی به حل λ1 and λ2 نیست. در همه حالات (مقادیر ویژه متمایز حقیقی، مقادیر ویژه تکراری حقیقی، مقادیر ویژه مختلط) دنباله ثابت است( متغیر به مقدار ثابت، معمولا صفر، همگراست) اگر و فقط اگر هر دو مقدار ویژه از مقدار ثابت کوچکتر باشند. در این معادله از مرتبه دو، این شرط برای مقادیر ویژه می تواند به صورت A| < 1 − B < 2| یا A| < 1 − B , |B| < 1| نشان داد.
مثال نوشته شده مشابه معادله زیر است ولی بدون عدد ثابت. اگر یک دنباله بازگشتی ناهمگن:b_{n}=Ab_{n-1}+Bb_{n-2}+K را با عدد ثابت K را داشته باشیم، می توان آن را با روش زیر به معادله همگن تبدیل می کنیم.حالت دائمی (steady state) با جایگذاری *b به جای bn = bn−1 = bn−2 = bخواهیم داشت:
b^{*} = \frac{K}{1-A-B}.
سپس معادله بازگشتی ناهمگن به شکل زیر به صورت همگن نوشته می شود:
[b_n - b^*]=A[b_{n-1}-b^*]+B[b_{n-2}-b^*],
که با روش های بالا قابل حل است.
شرط ثبات بیان شده در بالا از نظر مقادیر ویژه برای معادلات از مرتبه دو، به طور کلی برای معادلات مرتبه n نیز معتبر است.معادله پایدار است اگر و تنها اگرتمام مقادیر ویژه از مقدار ثابت در نعادله مشخصه کوچکتر باشند.
حل به روش جبر خطی
یک دنباله بازگشتی y از مرتبه n به صورت :y_{n+k} - c_{n-1}y_{n-1+k} - c_{n-2}y_{n-2+k} + \cdots - c_{0}y_{k} = 0 است که برابر :y_{n} = c_{n-1}y_{n-1} + c_{n-2}y_{n-2} + \cdots +c_{0}y_{0}. است و می توان این معادله درجه n را با یک سیستم درجه n معادلات خطی ترجمه کرد:
\vec y_{n} = \begin{bmatrix}y_n\\y_{n-1}\\ \vdots \\ y_1 \end{bmatrix} = \begin{bmatrix}-c_{n-1} & -c_{n-2} & \cdots & -c_{0} \\ 1 & 0 & \cdots &0\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0\end{bmatrix}\begin{bmatrix}y_{n-1} \\y_{n-2} \\ \vdots \\ y_0 \end{bmatrix} = C\ \vec y_{n-1} = C^n \vec y_0.
مشاهده می کنید که \vec y_n را می توان با n برنامه کاربردی به دست آورد. با تجزیه کردن \vec y_n = \vec C^n\, \vec y_0 = c_1\,\lambda_1^n\,\vec e_1 + c_2\,\lambda_2^n\,\vec e_2 + \cdots + c_n\,\lambda_n^n\,\vec e_n با روش تجزیه آیگن به مقادیر آیگن \lambda_1, \lambda_2, \ldots, \lambda_n و بردارهای آیگن \vec e_1, \vec e_2, \ldots, \vec e_n می توان \vec y_n را به دست آورد.با تشکر از این واقعیت مهم که سیستم c هر بردار آیگن را با پوسته پوسته کردن اجزایش در λ دفعه، تجزیه می کند :
C\,\vec e_i = \lambda_i \vec e_i = C \begin{bmatrix}e_{i,n} \\e_{i,n-1} \\ \vdots \\ e_{i,1}\end{bmatrix} = \begin{bmatrix}\lambda_i\,e_{i,n} \\ \lambda_i\,e_{i,n-1} \\ \vdots \\ \lambda_i\,e_{i,1}\end{bmatrix}
این یک نسخه از بردار آیگن است که اجزای λ برابر بزرگتر دارد و بردارهای آیگن توان های λ هستند \vec e_i = \begin{bmatrix}\lambda_i^{n-1} & \cdots & \lambda_i^2 & \lambda_i & 1\end{bmatrix}^T,
, و بنابراین راه حل دنباله بازگشتی همگن خطی ترکیبی از توابع نمایی است \vec y_n = \sum_1^n {c_i\,\lambda_i^n\,\vec e_i} . متغیر های c_i به وسیله شروط اولیه به دست می آیند.
\vec y_0 = \begin{bmatrix}y_{0}\\ y_{-1} \\ \vdots\\ y_{-n+1}\end{bmatrix} = \sum_{i=1}^n {c_i\,\lambda_i^0\,\vec e_i} = \begin{bmatrix}\vec e_1 & \vec e_2 & \cdots & \vec e_n\end{bmatrix}\,\begin{bmatrix}c_1 \\ c_2 \\ \cdots \\ c_n\end{bmatrix} = E\, \begin{bmatrix}c_1 \\ c_2 \\ \cdots \\ c_n\end{bmatrix}
که ضرایب آن در زیر آمده :
\begin{bmatrix}c_1 \\ c_2 \\ \cdots \\ c_n\end{bmatrix} = E^{-1} \vec y_0 = \begin{bmatrix}\lambda_1^{n-1} & \lambda_2^{n-1} & \cdots & \lambda_n^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ \lambda_1 & \lambda_2 & \cdots & \lambda_n \\ 1 & 1 & \cdots & 1\end{bmatrix}^{-1}\,\begin{bmatrix}y_{0}\\ y_{-1} \\ \vdots\\ y_{-n+1}\end{bmatrix}.
این هم چنین با شروط کرانه ای دلخواه به دست می آیند:
\begin{bmatrix}y_a \\ y_b \\ \vdots\end{bmatrix} = \begin{bmatrix}\vec y_a[n] \\ \vec y_b[n] \\ \vdots\end{bmatrix} = \begin{bmatrix}\sum_{i=1}^n {c_i\,\lambda_i^a\,\vec e_i[n]} \\ \sum_{i=1}^n {c_i\,\lambda_i^b\,\vec e_i[n]} \\ \vdots\end{bmatrix} =\begin{bmatrix}\sum_{i=1}^n {c_i\,\lambda_i^a\,\lambda_i^{n-1}} \\ \sum_{i=1}^n {c_i\,\lambda_i^b\,\lambda_i^{n-1}} \\ \vdots\end{bmatrix} =
= \begin{bmatrix}\sum {c_i\,\lambda_i^{a+n-1}} \\ \sum {c_i\,\lambda_i^{b+n-1}} \\ \vdots\end{bmatrix} = \begin{bmatrix}\lambda_1^{a+n-1} & \lambda_2^{a+n-1} & \cdots & \lambda_n^{a+n-1} \\ \lambda_1^{b+n-1} & \lambda_2^{b+n-1} & \cdots & \lambda_n^{b+n-1} \\ \vdots & \vdots & \ddots & \vdots \end{bmatrix}\,\begin{bmatrix}c_1 \\ c_2 \\ \vdots \\ c_n\end{bmatrix}.
این توصیف، اگر چه روش کوتاهتری است، با روش کلی اولیه فرقی ندارد. و همچنین برای حالت هایی که چند دنباله بازگشتی داریم، به کار می آید :
{a_n =a_{n-1}-b_{n-1
{b_n =2a_{n-1}+b_{n-1
حل با تبدیل z
معادلات تفاضلی خاص _ معادلات تفاضلی خطی با ضرایب ثابت_ با تبدیل z قابل حل اند. این تبدیلات، تبدیلات انتگرالی هستند که به دستکاری جبری مناسب تر و روش های مستقیم منجر می شود. این ها شرایطی اند که در آنها به دست آوردن یک روش مستقیم غیر ممکن است ولی حل آنها با روش تبدیل انتگرالی مستقیم است.
قضایا
برای یک دنباله بازگشتی خطی همگن با ضریب ثابت و مرتبه d داریم:
t^d - c_1t^{d-1} - c_2t^{d-2}-\cdots-c_{d} = 0 \,
که هر ci به ci در دنباله بازگشتی اصلی مربوط می شود. فرض کنید λ یک ریشه (p(t (چند جمله ای مشخصه) با درجه تکرار r است. همچنین گفته می شود که (p(t بر t−λ)r) بخش پذیر است. دو خاصیت زیر برقرارند:
_ هر یک از دنباله هایr ،معادله \lambda^n, n\lambda^n, n^2\lambda^n,\dots,n^{r-1}\lambda^n را برای دنباله بازگشتی برآورده می سازند. _هر توالی صدق پزیر در رابطه بازگشتی را میتوان به صورت ترکیبی خطی از جواب های ایجاد شده در قسمت 1 به دست آورد. در نتیجه این قضیه یک دنباله بازگشتی خطی همگن با ضریب ثابت به صورت زیر حل می شود: _معادله مشخصه (p(t را پیدا کنید. _ریشه های معادله و تکرار آن را بیابید. _an را به صورت ترکیب خطی ریشه ها با توجه به تعداد تکرار آنها با ضرایب ناشناخته bi بنویسید:
a_n = \left (b_1\lambda_1^n + b_2n\lambda_1^n + b_3n^2\lambda_1^n+\cdots+b_r n^{r-1}\lambda_1^n \right )+\cdots+ \left (b_{d-q+1}\lambda_{*}^n + \cdots + b_{d}n^{q-1}\lambda_{*}^n \right )
این همان جواب کلی برای دنباله بازگشتی اصلی است. _هر a_0, a_1, \dots,a_d را با a_0, a_1, \dots,a_d شناخته شده از دنباله بازگشتی اصلی یکسان فرض کنید. اگر چه مقادیر an از دنباله اصلی مرتبط نیستند مگر در موارد استثنایی فقط d مورد نیاز است.این روند یک سیستم خطی با معادلات d را درست می کند.حل این معادلات برای ضرایب نامعلومb_1, b_2, \dots,b_d از راه حل کلی و جایگذاری آن در راه حل کلی یک روش خاص برای حل دنباله بازگشتی با شرایط اولیه به دست می آید. روش حل معادلات تفاضلی خطی نیز مانند بالاست.حدس هوشمندانه برای معادلات تفاضلی خطی با ضریب ثابت eλx که λ یک عدد مختلط است وجود دارد که با جایگزین کردن حدس در معادلات تفاضلی به دست می آید.
این یک قرارداد است. بسط تیلور یک روش حل برای معادلات تفاضلی خطی است:
\sum_{n=0}^\infin \frac{f^{(n)}(a)}{n!} (x-a)^n
دیده می شود که ضرایب این بسط برابر مشتق n ام تابع(f(x است. رابطه دیفرانسیلی مدل تفاضلی خطی ای را مربوط به این ضرایب ایجاد میکند. این هم ارزی می تواند برای حل روابط بازگشتی با ضرایب سری های توانی در راه حل معادلات تفاضلی خطی مورد استفاده قرار گیرد. قانون شست _ برای معادلات که در آن چند جمله ای ضرب دوره اول غیر صفر صفر است _این است :
y^{[k]} \to f[n+k]
و به صورت کلی تر:
x^m*y^{[k]} \to n(n-1)(n-m+1)f[n+k-m]
به طور مثال: دنباله بازگشتی برا ضرایب بسط تیلور در دنباله زیر
(x^2 + 3x -4)y^{[3]} -(3x+1)y^{[2]} + 2y = 0
به صورت زیر داده شده:
: n(n-1)f[n+1] + 3nf[n+2] -4f[n+3] -3nf[n+1] -f[n+2]+ 2f[n] = 0
که همان
:-4f[n+3] +2nf[n+2] + n(n-4)f[n+1] +2f[n] = 0.
است. این مثال نشان می دهد که چگونه مشکلاتی که با روش های کلی توانی در کلاس معادلات تفاضلی قابل حل اند، با روشی ساده تر حل می شوند.
مثال:معادله تفاضلی :ay'' + by' +cy = 0 راه حل : y=e^{ax}. را دارد. تبدیل این معادله به معادله تفاضلی با بسط تیلور به صورت زیر است:
:af[n + 2] + bf[n + 1] + cf[n] = 0.
که به آسانی دیده می شود که مشتق nام eax در که در an ارزیابی می شود برابر 0 است.
حل روابط بازگشتی ناهمگن
اگر رابطه بازگشتی ناهمگن باشد، جواب خاص را می توان با روش ضرائب غیرمشخص بدست آورد. جواب کلی برابر است با مجموع جواب های روابط همگن و خاص. روش دیگر حل یک رابطه بازگشتی ناهمگن، روش مشتق¬گیری سیمبلیک می¬باشد. برای مثال رابطه بازگشتی زیر را در نظر بگیرید:
a_{n+1} = a_{n} + 1
که یک رابطه بازگشتی ناهمگن است. اگرn ↦ n+1 جایگزین کنیم، به رابطه بازگشتی زیر می رسیم:
a_{n+2} = a_{n+1} + 1
با تفریق رابطه بازگشتی اصلی و رابطه بدست آمده به رابطه زیر می¬رسیم:
a_{n+2} - a_{n+1} = a_{n+1} - a_n
یا
a_{n+2} = 2 a_{n+1} - a_n
این یک رابطه بازگشتی همگن است که می¬توان آن را با روش های ذکر شده حل کرد. به صورت کلی، اگر یک رابطه بازگشتی خطی به شکل زیر وجود داشته باشد:
a_{n+k} = \lambda_{k-1} a_{n+k-1} + \lambda_{k-2} a_{n+k-2} + \cdots + \lambda_1 a_{n+1} + \lambda_0 a_{n} + p(n)
که در آن \lambda_0, \lambda_1, \dots, \lambda_{k-1} ضرائب ثابت و (p(n ناهمگنی باشد، در صورتی که(p(n چندجمله ای با درجه r باشد، می توان این رابطه بازگشتی ناهمگن را به رابطه بازگشتی همگن با استفاده از روش مشتق گیری سیمبلیک درجه r تبدیل کرد اگر
P(x) = \sum_{n=0}^\infty p_n x^n
تابع مولد ناهمگنی باشد و
A(x) = \sum_{n=0}^\infty a(n) x^n
تابع مولد رابطه بازگشتی ناهمگن باشد که در آن ضرائب ثابت ci به روش زیر بدست می آیند:
a_n = \sum_{i=1}^s c_i a_{n-i}+p_n,\quad n\ge n_r,
\left (1-\sum_{i=1}^sc_ix^i \right )A(x)=P(x)+\sum_{n=0}^{n_r-1}[a_n-p_n]x^n-\sum_{i=1}^s c_ix^i\sum_{n=0}^{n_r-i-1}a_nx^n.
اگر (P(x تابع مولد گویا باشد، (A(x هم مانند آن خواهد بود. در حالت بالا، که pn = K ثابت است،(P(x) = K/(1−x نمونه ای از این فرمول خواهد بود. نمونه ای دیگر، رابطه بازگشتی a_n=10 a_{n-1}+n با ناهمگنی خطی است که از تعریف اعداد schizophrenic بدست می¬آید. جواب روابط همگن به صورت p = P = 0 است. به علاوه، برای روابط بازگشتی ناهمگن مرتبه اول عمومی با ضرائب متغیر
a_{n+1} = f_n a_n + g_n, \qquad f_n \neq 0,
روش مناسبی برای حل وجود دارد.
a_{n+1} - f_n a_n = g_n
\frac{a_{n+1}}{\prod_{k=0}^n f_k} - \frac{f_n a_n}{\prod_{k=0}^n f_k} = \frac{g_n}{\prod_{k=0}^n f_k}
\frac{a_{n+1}}{\prod_{k=0}^n f_k} - \frac{a_n}{\prod_{k=0}^{n-1} f_k} = \frac{g_n}{\prod_{k=0}^n f_k}
فرض کنید
A_n = \frac{a_n}{\prod_{k=0}^{n-1} f_k},
حال
A_{n+1} - A_n = \frac{g_n}{\prod_{k=0}^n f_k}
\sum_{m=0}^{n-1}(A_{m+1} - A_m) = A_n - A_0 = \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}
\frac{a_n}{\prod_{k=0}^{n-1} f_k} = A_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}
a_n = \left(\prod_{k=0}^{n-1} f_k \right) \left(A_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}\right)
روابط بازگشتی همگن خطی کلی
بسیاری از روابط بازگشتی همگن خطی ممکن است با سری فوق هندسی تعمیم یافته حل شوند. شرایط خاصی از اینها منجر به چندجمله ای متعامد و بسیاری از توابع خاص می شوند. برای مثال راه حل دنباله زیر
:J_{n+1}=\frac{2n}{z}J_n-J_{n-1}
به صورت :J_n=J_n(z), \, است. تابع بسل تا وقتی که :(b-n)M_{n-1} +(2n-b-z)M_n - nM_{n+1}=0 \, به صورت :M_n=M(n,b;z) \, حل می شود که همریز سری فوق هندسی است.
روش حل معادلات تفاضلی گویا از مرتبه یک
معادلات تفاضلی گویا از مرتبه یک به صورت w_{t+1} = \tfrac{aw_t+b}{cw_t+d} هستند. این چنین معادلاتی با نوشتن w_t به صورت تبدیل غیرخطی از متغیر دیگر x_t که خود به صورت خطی است، حل می شوند. سپس روش های استاندارد مورد استفاده قرار می گیرند تا معادلات تفاضلی خطی x_t حل شود.
ثبات
ثبات روابط بازگشتی مرتبه های بالاتر
رابطه بازگشتی خطی از مرتبه d
a_n = c_1a_{n-1} + c_2a_{n-2}+\dots+c_da_{n-d}, \,
معادله مشخصه ای به شکل زیر خواهد داشت.
\lambda^d - c_1 \lambda^{d-1} - c_2 \lambda^{d-2} - \dots - c_d \lambda^0 =0. \,
رابطه بازگشتی پایدار است، بدین معنا که تکرارها بدون علامت خاصی همگرا به مقداری خاص هستند، اگر و تنها اگر مقادیر آیگن ( ریشه های معادله مشخصه)، خواه حقیقی یا مختلط، تماما کمتر از unity در قدر مطلق هستند.
ثبات ماتریس بازگشتی خطی از مرتبه اول
در معادله ماتریس بازگشتی خطی از مرتبه اول
[x_t - x^*] = A[x_{t-1}-x^*]\,
با بردار حالت x و ماتریس انتقالی x,A همگرا به بردار حالت یکنواخت *x خواهد بود اگر و تنها اگر تمام مقادیر آیگن از ماتریس انتقالی A مقدار قدر مطلقی کمتر از 1 داشته باشند.
ثبات روابط بازگشتی غیرخطی اولین مرتبه
رابطه بازگشتی غیرخطی اولین مرتبه زیر را در نظر بگیرید:
x_n=f(x_{n-1}).
این رابطه بازگشتی پایدار محلی است، بدین معنا که به نقطه ثابت x* از نقاط نزدیک به آن همگرا است، اگر دامنه f در همسایگی x* کوچکتر از unity در مقدار قدر مطلقی باشد؛ که یعنی:
| f' (x^*) | < 1. \,
یک رابطه بازگشتی غیر خطی می تواند چندین نقطه ثابت داشته باشد، که در آنها ممکن پایدار یا ناپایدار باشد. برای یک f پیوسته، دو نقطه ثابت نمیتوانند پایدار محلی باشند. یک رابطه بازگشتی غیر خطی می تواند چرخه ای از دوره k برای k > 1 داشته باشد. این چرخه پایدار است، بدین معنا که مجموعه ای از شرایط اولیه مثبت را جذب می کند اگر تابع مرکب
g(x) := f \circ f \circ \cdot \cdot \cdot \circ f(x)
با داشتن n بار از f، پایدار محلی است.
| g' (x^*) | < 1,
در یک رابطه بازگشتی chaotic، متغیر x در ناحیه بسته ای باقی می ماند ولی همگرا به نقطه ثابت یا یک چرخه نمی شود؛ هر گونه نقطه ثابت یا چرخه ای از معادلات ناپایدار اند. به نقشه منطقی، تبدیل دوتایی و نقشه چادر رجوع شود.
روابط مدل های تفاضلی
وقتی که به حل مدل های تفاضلی عادی عددی پرداخته می شود، عموما به روابط بازگشتی برخورد خواهیم کرد. برای مثال، در حل مساله مقدار اولیه
y'(t) = f(t,y(t)), \ \ y(t_0)=y_0,
با روش اویلر و اندازه گام h، مقادیر
y_0=y(t_0), \ \ y_1=y(t_0+h), \ \ y_2=y(t_0+2h), \ \dots
با رابطه بازگشتی
\, y_{n+1} = y_n + hf(t_n,y_n).
محاسبه خواهند شد. سیستم های مدل های تفاضلی مرتبه اول را می توان توسط روش های نشان داده شده در بخش گسسته سازی، گسسته ساخت.
کاربردها
زیست شناسی
برخی از بهترین مدل های تفاضلی شناخته شده از تلاش های صورت گرفته برای مدل سازی پویاشناسی جمعیت سرچشمه گرفته اند. برای مثال اعداد فیبوناچی در دوره ای برای مدل سازی رشد جمعیت خرگوش ها مورد استفاده قرار می گرفت. نقشه منطقی هم به صورت مستقیم برای مدل سازی رشد جمعیت و هم به عنوان نقطه شروعی برای مدل های مفصل تر استفاده می شود. در این مقاله، مدل های تفاضلی کوپل(جفتی) برای مدل سازی فعل و انفعال دو یا چند جمعیت مورد استفاده قرار می گیرند. برای مثال، مدل Nicholson-Bailey برای یک فعل و انفعال انگل میزبان به صورت زیر بدست می آید:
N_{t+1} = \lambda N_t e^{-aP_t} \,
P_{t+1} = N_t(1-e^{-aP_t}), \,
که در آن Nt نشان دهنده میزبان ها و Pt انگل ها در زمان t هستند. معادلات integrodifference شکلی از رابطه بازگشتی اند که برای اکولوژی فاصله ای مهم هستند. این و دیگر گونه های مدل های تفاضلی برای مدل سازی جمعیت های univoltine مورد استفاده قرار می گیرند.
پردازش سیگنال دیجیتال
در پردازش سیگنال دیجیتال، روابط بازگشتی می توانند بازخورد به سیستم را مدل سازی کنند که خروجی ها در یک زمان ورودی های زمان های آتی خواهد بود. بنابراین آنها در فیلتر دیجیتال پاسخ برانگیزش نامتناهی (IIR) دیده خواهند شد. برای مثال، معادله برای یک “feedforward” IIR فیلتر ترکیبی با تاخیر T برابر خواهد بود با:
y_t = (1 - \alpha) x_t + \alpha y_{t - T}
که در آن x_t ورودی در زمان math>y_t</math> , t> خروجی در زمان t و α کنترل کننده میزان سیگنال های تاخیری بازگشتی به خروجی ها می باشد. پس می توان گفت:
y_t = (1 - \alpha) x_t + \alpha ((1-\alpha) x_{t-T} + \alpha y_{t - 2T})
y_t = (1 - \alpha) x_t + (\alpha-\alpha^2) x_{t-T} + \alpha^2 y_{t - 2T})
اقتصاد
روابط بازگشتی، خصوصا روابط بازگشتی خطی، هم در اقتصاد تئوری و هم در اقتصاد تجربی مورد استفاده قرار می¬گیرد. به ویژه، در اقتصاد کلان، می توان مدلی از بخش های متفاوت بزرگ اقتصاد (مثل بخش مالی، بخش کالا، بازار کار و غیره) ایجاد کرد که در آنها اقدامات برخی آژانس ها وابسته به متغیر های تاخیری است. مدل را می توان با مقادیر فعلی متغیرهای اصلی حل کرد. برای اطلاعات بیشتر به آنالیز سری های زمانی رجوع شود.
علم کامپیوتر
در آنالیز الگوریتم ها، روابط بازگشتی اهمیت زیادی دارند. اگر یک الگوریتم گونه ای طراحی شود که یک مساله را به زیر مساله های کوچکتری تبدیل کند، زمان اجرای آن را می توان با روابط بازگشتی توصیف کرد. یک مثال ساده زمانی است که یک الگوریتم به طول می انجامد تا به دنبال یک جز در یک بردار مرتب n جزئی بگردد. یک الگوریتم ساده جست وجوی چپ به راست انجام می دهد که در هر لحظه یک جز را در نظر دارد. بدترین حالت ممکن این است که جز مورد نظر، آخرین جز باشد که در این صورت تعداد مقایسه ها برابر n می شود. الگوریتمی بهتر، جست وجوی دودویی است. ابتدا بررسی می کند که جز در میانه بردار وجود دارد یا خیر. اگر نباشد، بررسی می کند که جز میانه بزرگتر یا کوچکتر از جز مورد نظر است. در این نقطه، نیمی از بردار حذف شده و الگوریتم بر روی نیمه دیگر دوباره اجرا می¬شود. تعداد مقایسه ها با روابط زیر بدست می آید:
c_1=1
c_n=1+c_{n/2}
که نزدیک به \log_2(n) می¬باشد.