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

رابطه بازگشتی (Recurrence relation)، در ریاضیات، دنباله‌ای است که به صورت بازگشتی تعریف می‌شود.
واژه نادان تفاضلی (difference equation) مربوط به حالت خاصی از رابطه بازگشتی می‌باشد. به هر حال، «مدل تفاضلی» برای اشاره به هر گونه رابطه بازگشتی به کار می‌رود. نمونه‌ای از یک رابطه بازگشتی، نقشه لوجستیک (منطقی) با ثابت داده شده r می‌باشد که با در نظر گرفتن x 0 به عنوان مقدار اولیه، تمام مقادیر بعدی با این رابطه بدست می‌آید. بسیاری از روابط بازگشتی ممکن است رفتارهای پیچیده‌ای از خودشان نشان دهند این نوع روابط توسط فیزیکدانان و ریاضیدانان در شاخه‌ای از ریاضیات به نام تحلیل غیر خطی مطالعه می‌شوند. حل یک معادله بازگشتی یعنی به دست آوردن یک فرم بسته برای آن (یک تابع غیر بازگشتی از n).
فیبوناچی
اعداد فیبوناچی نمونه اولیه‌ای از یک رابطه بازگشتی همگن با ضرائب ثابت می‌باشد. این اعداد با رابطه خطی بازگشتی زیر:
با مقادیر اولیه:
تعریف می‌شوند. مشخصا رابطه بازگشتی معادله‌های زیر را ایجاد می‌کند:
به توالی اعداد فیبوناچی می‌رسیم که به شکل: ۰، ۱، ۱، ۲، ۳، ۵، ۸، ۱۳، ۲۱، ۳۴، ۵۵، ۸۹ و … است. آن را می‌توان با روش‌هایی که در ادامه توضیح داده می‌شوند، حل کرد؛ روش‌هایی که عبارتی بسته (closed-form expression) شامل توان‌های دو ریشه چندجمله‌ای مشخصه t 2 = t + 1 دارند. تابع ایجادکننده توالی، تابع گویای زیر است:
ساختار
رابطه بازگشتی خطی همگن با ضرایب ثابت
رابطه بازگشتی خطی همگن با ضرایب ثابت از مرتبه d، معادله‌ای به شکل زیر است:
که در آن d ضرایب c i (برای تمام iها) ثابت است. می‌توان گفت، فهرست معادلات خطی هم‌زمان نامتناهی است که برای هر n>d−۱ می‌باشد. یک توالی که رابطه‌ای چنینی داشته باشد، توالی بازگشتی خطی یا LRS نامیده می‌شود. d درجه آزادی برای LRS وجود دارد بدین معنا که مقادیر اولیه هر مقداری را می‌توانند بگیرند ولی رابطه بازگشتی خطی توالی یکتایی را مشخص می‌کند. ضرایب یکسان چندجمله‌ای مشخصه را ایجاد می‌کنند:
که ریشه‌های d نقش مهمی در یافتن و فهمیدن توالی‌های درست از لحاظ تابع بازگشتی دارند. اگر ریشه‌های معادله مشخصه تماما مشخص باشند، حال راه حل بازگشتی به شکل زیر خواهد بود:
که در آن ضرایب k i برای متناسب کردن شرایط اولیه رابطه بازگشتی مشخص می‌شوند. وقتی که ریشه‌های یکسان برای چندین بار اتفاق می‌افتند، قسمت‌هایی از این فرمول که مربوط به موارد دوم و بیشتر از یک ریشه است در توان‌های افزایشی از n ضرب می‌شوند. برای مثال، اگر چندجمله‌ای مشخصه فاکتوری از 3 (x-r) با ریشه تکراری سه باره r باشد، راه حل به شکل زیر خواهد بود:
در کنار اعداد فیبوناچی، دیگر توالی‌های ایجاد شده توسط روابط بازگشتی خطی همگن شامل اعداد لوکاس و توالی لوکاس، اعداد یاکوبسال، اعداد پل و معادله پل می‌باشد.
تابع مولد گویا
توالی‌های بازگشتی خطی دقیقا توالی‌هایی هستند که تابع مولدشان یک تابع گویا است. مخرج چندجمله‌ای بدست آمده از چندجمله‌ای مشخصه با معکوس کردن ترتیب ضرائب است و صورت با مقادیر اولیه توالی مشخص می‌شود. ساده‌ترین حالت‌ها توالی‌های دوره‌ای هستند که توالی و تابع مولدی مجموع سری هندسی زیر دارند:
عموما در مورد رابطه بازگشتی زیر:
با تابع مولد:
سری‌ها در a d و بالاتر به وسیله چندجمله‌ای زیر متوقف می‌شوند:
که این یعنی ضرب تابع مولد در چندجمله‌ای، در پی خواهد داشت:
به‌طوری‌که ضرایب برای n ≥ d حذف می‌شوند. پس:
و با تقسیم خواهیم داشت:
که نشان دهنده تابع مولد به عنوان تابع گویا است.
مخرج است که تبدیلی از چندجمله‌ای مشخصه است. می‌توان هر مضربی از آن را استفاده کرد، ولی این نرمال سازی هر دو را انتخاب کرده تا رابطه ساده‌تری برای چندجمله‌ای مشخصه داشته باشد و همچنین داشته باشد .
روابط تفاضلی به دقت تعریف شده
دنباله اعداد حقیقی را در نظر بگیرید. اولین دنباله تفاضلی برابر
است. دومین دنباله به صورت
تعریف می‌شود که می‌تواند به صورت
ساده‌سازی شود. به صورت کلی دنباله تفاضلی k ام به صورت زیر تعریف می‌شود:
تعریف محدودتری از معادله تفاضلی معادله‌ای است بر حسب a n و k امین تفاضل. در واقع معادله زیر را داریم:
a_{n+k =
{n\choose 0a_n + {n\choose 1 \Delta(a_n) + \cdots + {n\choose k \Delta^n(a_n)
بنابراین معادله تفاضلی می‌تواند معادله‌ای بر حسب a n , a n-1 , a n-2 یا a n , a n+1 , a n+2 باشد.
از آنجایی که معادلات تفاضلی یکی از رایج‌ترین معادلات بازگشتی هستند، بعضی از نویسنده‌ها آن‌ها را به جای هم به کار می‌برند. به‌طور مثال معادله تفاضلی: با دنباله بازگشتی زیر برابر است.
بنابراین معادلات تفاضلی می‌توانند به صورت بازگشتی حل شوند و به صورت مشابه می‌توان روش حل معادلات دیفرانسیل معمولی را یافت. اگرچه اعداد آکرمن نمونه‌ای از دنباله بازگشتی هستند، به معادلات تفاضلی نگاشته نمی‌شوند. معادلات جمعی مرتبط به معادلات تفاضلی هستند همان‌طور که معادلات انتگرال مربوط به معادلات دیفرانسیل هستند.
از توالی به شبکه
روابط تک متغیر یا بازگشتی یک بعدی در مورد دنباله است در حالی که روابط بازگشتی چند متغیر یا n بعدی در مورد شبکه‌های n بعدی است. توابعی که بر روی شبکه‌های n بعدی تعریف می‌شوند، با معادلات تفاضلی جزئی قابل حل‌اند.
روش حل
روش‌های کلی
برای دنباله بازگشتی از مرتبه ۱ داریم:
در نظر می‌گیریم a n = r n و a 0 = ۱ و روش کلی‌تر آن a n = kr n و a 0 = k است. معادله مشخصه این عبارت به سادگی به دست می‌آید که برابر t − r = ۰ است. راه حل برای معادلات با مرتبه بالاتر با قواعد و اصول به دست آمده، غالبا استفاده از روش a n = r n برای مواقعی است که t = r یک ریشه معادله مشخصه است. این می‌تواند به‌طور مستقیم یا با تابع مولد یا ماتریس به دست آید.
به‌طور مثال دنباله را در نظر بگیرید، این دنباله چه موقع جواب a n = r n را دارد؟ این را با دنباله بازگشتی جایگزین کنید، در می‌یابیم که برای همه n > 1 معادله درست است. با تقسیم بر r n−2 ، همان معادلات را به صورت زیر خواهیم داشت:
که یک معادله مشخصه برای دنباله بازگشتی است. با حل کردن معادله دو ریشه برای r خواهیم داشت:  1 و  2 ، که این ریشه‌ها، ریشه‌های مشخصه یا مقادیر ویژه معادله مشخصه نامیده می‌شوند. با توجه به ریشه‌ها، روش‌های متفاوتی برای حل معادله وجود دارد. اگر متمایز باشند، راه حل کلی: را داریم و اگر برابر بودند
این کلی‌ترین روش است و C و D با توجه به a 0 و a 1 به دست می‌آیند. برای حالاتی که مقادیر ویژه مختلط اند (که منجر به مختلط شدن C و D نیز می‌شوند) استفاده از اعداد مختلط را می‌توان با بازنویسی راه حل به صورت مثلثاتی حذف کرد. در این حالت مقادیر ویژه را می‌توان به صورت نشان داد. هم چنین معادله
را می‌توان به صورت زیر نشان داد.
که در آن
\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 ثایت‌های حقیقی‌اند که وابسته به شرایط اولیه هستند. استفاده از فرمول‌های زیر راه حل را می‌تواند ساده‌تر کند
که a 1 و a 2 مقادیر اولیه هستند و
\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 و  2 نیست. در همه حالات (مقادیر ویژه متمایز حقیقی، مقادیر ویژه تکراری حقیقی، مقادیر ویژه مختلط) دنباله ثابت است. (متغیر به مقدار ثابت، معمولا صفر، همگراست) اگر و فقط اگر هر دو مقدار ویژه از مقدار ثابت کوچکتر باشند. در این معادله از مرتبه دو، این شرط برای مقادیر ویژه را می‌توان به صورت A|
1 داشته باشد. این چرخه پایدار است، بدین معنا که مجموعه‌ای از شرایط اولیه مثبت را جذب می‌کند اگر تابع مرکب
با داشتن n بار از f، پایدار محلی است.
در یک رابطه بازگشتی آشوب، متغیر x در ناحیه بسته‌ای باقی می‌ماند ولی همگرا به نقطه ثابت یا یک چرخه نمی‌شود؛ هرگونه نقطه ثابت یا چرخه‌ای از معادلات ناپایداراند. به نقشه منطقی، تبدیل دوتایی و نقشه چادر رجوع شود.
روابط مدل‌های تفاضلی
وقتی که به حل مدل‌های تفاضلی عادی عددی پرداخته می‌شود، عموما به روابط بازگشتی برخورد خواهیم کرد. برای مثال، در حل مسئله مقدار اولیه
با روش اویلر و اندازه گام h، مقادیر
با رابطه بازگشتی
محاسبه خواهند شد. سیستم‌های مدل‌های تفاضلی مرتبه اول را می‌توان توسط روش‌های نشان داده شده در بخش گسسته سازی، گسسته ساخت.
کاربردها
زیست‌شناسی
برخی از بهترین مدل‌های تفاضلی شناخته شده از تلاش‌های صورت گرفته برای مدل‌سازی پویاشناسی جمعیت سرچشمه گرفته‌اند. برای مثال اعداد فیبوناچی در دوره‌ای برای مدل‌سازی رشد جمعیت خرگوش‌ها مورد استفاده قرار می‌گرفت. نقشه منطقی هم به صورت مستقیم برای مدل‌سازی رشد جمعیت و هم به عنوان نقطه شروعی برای مدل‌های مفصل‌تر استفاده می‌شود. در این مقاله، مدل‌های تفاضلی جفتی (کوپل) برای مدل‌سازی فعل و انفعال دو یا چند جمعیت مورد استفاده قرار می‌گیرند. برای مثال، مدل نیکولسون-بیلی برای یک فعل و انفعال انگل-میزبان به صورت زیر بدست می‌آید:
که در آن N t نشان دهنده میزبان‌ها و P t انگل‌ها در زمان t هستند. معادلات دیفرانسیلی انتگرالی شکلی از رابطه بازگشتی‌اند که برای بوم شناسی فاصله‌ای مهم هستند. این و دیگر گونه‌های مدل‌های تفاضلی برای مدل‌سازی جمعیت‌های univoltine مورد استفاده قرار می‌گیرند.
پردازش سیگنال دیجیتال
در پردازش سیگنال دیجیتال، روابط بازگشتی می‌توانند بازخورد به سیستم را مدل‌سازی کنند که خروجی‌ها در یک زمان، ورودی‌های زمان‌های آتی خواهد بود؛ بنابراین آن‌ها در فیلتر دیجیتال پاسخ برانگیزش نامتناهی (IIR) دیده خواهند شد. برای مثال، معادله برای یک پسخور IIR فیلتر ترکیبی با تاخیر T برابر خواهد بود با:
که در آن ورودی در زمان t, خروجی در زمان t و  کنترل‌کننده میزان سیگنال‌های تاخیری بازگشتی به خروجی‌ها می‌باشد. پس می‌توان گفت:
اقتصاد
روابط بازگشتی، خصوصا روابط بازگشتی خطی، هم در اقتصاد نظری و هم در اقتصاد تجربی مورد استفاده قرار می‌گیرد. به ویژه، در اقتصاد کلان، می‌توان مدلی از بخش‌های متفاوت بزرگ اقتصاد (مثل بخش مالی، بخش کالا، بازار کار و غیره) ایجاد کرد که در آن‌ها اقدامات برخی آژانس‌ها وابسته به متغیرهای تاخیری است. مدل را می‌توان با مقادیر فعلی متغیرهای اصلی حل کرد. برای اطلاعات بیشتر به تحلیل سری‌های زمانی رجوع شود.
علم کامپیوتر
در تحلیل الگوریتم‌ها، روابط بازگشتی اهمیت زیادی دارند. اگر یک الگوریتم به گونه‌ای طراحی شود که یک مسئله را به زیر مسئله‌های کوچکتری تبدیل کند، زمان اجرای آن را می‌توان با روابط بازگشتی توصیف کرد. یک مثال ساده زمانی است که یک الگوریتم به طول می‌انجامد تا به دنبال یک جزء در یک بردار مرتب n جزئی بگردد. یک الگوریتم ساده، جست وجوی چپ به راست انجام می‌دهد که در هر لحظه یک جزء را در نظر دارد. بدترین حالت ممکن این است که جزء مورد نظر، آخرین جزء باشد که در این صورت تعداد مقایسه‌ها برابر n می‌شود. الگوریتمی بهتر، جست وجوی دودویی است. ابتدا بررسی می‌کند که جزء در میانه بردار وجود دارد یا خیر. اگر نباشد، بررسی می‌کند که جزء میانه بزرگتر یا کوچکتر از جزء مورد نظر است. در این نقطه، نیمی از بردار حذف شده و الگوریتم بر روی نیمه دیگر دوباره اجرا می‌شود. تعداد مقایسه‌ها با روابط زیر بدست می‌آید:
که نزدیک به می‌باشد.