رابطه بازگشتی
رابطهٔ بازگشتی (به انگلیسی: Recurrence relation) در ریاضیات، دنبالهای است که بهصورت بازگشتی تعریف میشود.
واژه معادلهٔ تفاضلی (difference equation) مربوط به حالت خاصی از رابطۀ بازگشتی میباشد. به هر حال، «مدل تفاضلی» برای اشاره به هر گونه رابطۀ بازگشتی به کار میرود. نمونهای از یک رابطۀ بازگشتی، نقشه لجستیک (منطقی) با ثابت داده شدۀ
فیبوناچی
اعداد فیبوناچی نمونه اولیهای از یک رابطۀ بازگشتی همگن با ضرائب ثابت میباشد. این اعداد با رابطۀ خطی بازگشتی زیر:
با مقادیر اولیه:
تعریف میشوند. مشخصاً رابطۀ بازگشتی معادلههای زیر را ایجاد میکند:
به توالی اعداد فیبوناچی میرسیم که به شکل: ۰، ۱، ۱، ۲، ۳، ۵، ۸، ۱۳، ۲۱، ۳۴، ۵۵، ۸۹ و … است. آن را میتوان با روشهایی که در ادامه توضیح داده میشوند، حل کرد؛ روشهایی که عبارتی بسته (closed-form expression) شامل توانهای دو ریشه چندجملهای مشخصه
ساختار
رابطۀ بازگشتی خطی همگن با ضرایب ثابت
رابطۀ بازگشتی خطی همگن با ضرایب ثابت از مرتبۀ
که در آن
که ریشههای
که در آن ضرایب
در کنار اعداد فیبوناچی، دیگر توالیهای ایجاد شده توسط روابط بازگشتی خطی همگن شامل اعداد لوکاس و توالی لوکاس، اعداد یاکوبسال، اعداد پل و معادلۀ پل میباشد.
تابع مولد گویا
توالیهای بازگشتی خطی دقیقاً توالیهایی هستند که تابع مولدشان یک تابع گویا است. مخرج چندجملهای بدست آمده از چندجملهای مشخصه با معکوس کردن ترتیب ضرائب است و صورت با مقادیر اولیه توالی مشخص میشود. سادهترین حالتها توالیهای دورهای
هستند که توالی
و تابع مولدی مجموع سری هندسی زیر دارند:
عموماً در مورد رابطه بازگشتی زیر:
با تابع مولد:
سریها در ad و بالاتر به وسیله چندجملهای زیر متوقف میشوند:
که این یعنی ضرب تابع مولد در چندجملهای، در پی خواهد داشت:
بهطوریکه ضرایب
و با تقسیم خواهیم داشت:
که نشان دهنده تابع مولد به عنوان تابع گویا است.
مخرج
روابط تفاضلی به دقت تعریف شده
دنباله اعداد حقیقی
را در نظر بگیرید. اولین دنباله تفاضلی برابر
است. دومین دنباله به صورت
تعریف میشود که میتواند به صورت
سادهسازی شود. به صورت کلی دنباله تفاضلی k ام به صورت زیر تعریف میشود:
تعریف محدودتری از معادله تفاضلی معادلهای است بر حسب an و k امین تفاضل. در واقع معادله زیر را داریم:
بنابراین معادله تفاضلی میتواند معادلهای بر حسب an, an-1, an-2 یا an, an+1, an+2 باشد.
از آنجایی که معادلات تفاضلی یکی از رایجترین معادلات بازگشتی هستند، بعضی از نویسندهها آنها را به جای هم به کار میبرند. بهطور مثال معادله تفاضلی:
بنابراین معادلات تفاضلی میتوانند به صورت بازگشتی حل شوند و به صورت مشابه میتوان روش حل معادلات دیفرانسیل معمولی را یافت. اگرچه اعداد آکرمن نمونهای از دنباله بازگشتی هستند، به معادلات تفاضلی نگاشته نمیشوند. معادلات جمعی مرتبط به معادلات تفاضلی هستند همانطور که معادلات انتگرال مربوط به معادلات دیفرانسیل هستند.
از توالی به شبکه
روابط تک متغیر یا بازگشتی یک بعدی در مورد دنباله است در حالی که روابط بازگشتی چند متغیر یا n بعدی در مورد شبکههای n بعدی است. توابعی که بر روی شبکههای n بعدی تعریف میشوند، با معادلات تفاضلی جزئی قابل حلاند.
روش حل
روشهای کلی
برای دنباله بازگشتی از مرتبه ۱ داریم:
در نظر میگیریم an = rو a0 = ۱ و روش کلی تر آن an = krو a0 = k است. معادله مشخصه این عبارت به سادگی به دست میآید که برابر t − r = ۰ است. راه حل برای معادلات با مرتبهٔ بالاتر با قواعد و اصول به دست آمده، غالباً استفاده از روش an = r برای مواقعی است که t = r یک ریشه معادله مشخصه است. این میتواند بهطور مستقیم یا با تابع مولد یا ماتریس به دست آید.
بهطور مثال دنباله
که یک معادله مشخصه برای دنباله بازگشتی است. با حل کردن معادله دو ریشه برای r خواهیم داشت: λ1 و λ2، که این ریشهها، ریشههای مشخصه یا مقادیر ویژه معادله مشخصه نامیده میشوند. با توجه به ریشهها، روشهای متفاوتی برای حل معادله وجود دارد. اگر متمایز باشند، راه حل کلی:
این کلیترین روش است و C و D با توجه به a0 و a1 به دست میآیند. برای حالاتی که مقادیر ویژه مختلط اند (که منجر به مختلط شدن C و D نیز میشوند) استفاده از اعداد مختلط را میتوان با بازنویسی راه حل به صورت مثلثاتی حذف کرد. در این حالت مقادیر ویژه را میتوان به صورت
را میتوان به صورت زیر نشان داد.
که در آن
E و F ثابتهای حقیقی اند که وابسته به شرایط اولیه هستند. استفاده از فرمولهای زیر راه حل را میتواند سادهتر کند
که a1 و a2 مقادیر اولیه هستند و
در این روش دیگر احتیاجی به حل λ1 و λ2 نیست. در همه حالات (مقادیر ویژه متمایز حقیقی، مقادیر ویژه تکراری حقیقی، مقادیر ویژه مختلط) دنباله ثابت است. (متغیر به مقدار ثابت، معمولاً صفر، همگراست) اگر و فقط اگر هر دو مقدار ویژه از مقدار ثابت کوچکتر باشند. در این معادله از مرتبه دو، این شرط برای مقادیر ویژه را میتوان به صورت A| < 1 − B < 2| یا A| < 1 − B، |B| < 1| نشان داد.
مثال نوشته شده مشابه معادله زیر است ولی بدون عدد ثابت. اگر یک دنباله بازگشتی ناهمگن:
سپس معادله بازگشتی ناهمگن به شکل زیر به صورت همگن نوشته میشود:
که با روشهای بالا قابل حل است.
شرط ثبات بیان شده در بالا از نظر مقادیر ویژه برای معادلات از مرتبه دو، بهطور کلی برای معادلات مرتبه n نیز معتبر است. معادله پایدار است اگر و تنها اگر تمام مقادیر ویژه از مقدار ثابت در معادله مشخصه کوچکتر باشند.
حل به روش جبر خطی
یک دنباله بازگشتی y از مرتبه n به صورت:
مشاهده میکنید که
این یک نسخه از بردار ویژه است که اجزای λ برابر بزرگتر دارد و بردارهای ویژه توانهای λ هستند
که ضرایب آن در زیر آمده:
هم چنین با شرایط مرزی دلخواه به دست میآید:
این توصیف، اگر چه روش کوتاهتری است، با روش کلی اولیه فرقی ندارد و همچنین برای حالتهایی که چند دنباله بازگشتی داریم، به کار میآید:
حل با تبدیل z
معادلات تفاضلی خاص _ معادلات تفاضلی خطی با ضرایب ثابت_ با تبدیل z قابل حلاند. این تبدیلات، تبدیلات انتگرالی هستند که به دستکاری جبری مناسب تر و روشهای مستقیم منجر میشود. اینها شرایطی اند که در آنها به دست آوردن یک روش مستقیم غیرممکن است، ولی حل آنها با روش تبدیل انتگرالی مستقیم است.
قضایا
برای یک دنباله بازگشتی خطی همگن با ضریب ثابت و مرتبه d داریم:
که هر ci به ci در دنباله بازگشتی اصلی مربوط میشود. فرض کنید λ یک ریشه (p(t (چندجملهای مشخصه) با درجه تکرار r است. همچنین گفته میشود که (p(t بر t−λ)) بخش پذیر است. دو خاصیت زیر برقرارند:
- هر یک از دنبالههای r، معادله را برای دنباله بازگشتی برآورده میسازند.
- هر توالی صدق پذیر در رابطه بازگشتی را میتوان به صورت ترکیبی خطی از جوابهای ایجاد شده در قسمت ۱ به دست آورد.
در نتیجه این قضیه یک دنباله بازگشتی خطی همگن با ضریب ثابت به صورت زیر حل میشود:
- معادله مشخصه (p(t را پیدا کنید.
- ریشههای معادله و تکرار آن را بیابید.
- an را به صورت ترکیب خطی ریشهها با توجه به تعداد تکرار آنها با ضرایب ناشناخته bi بنویسید:
این همان جواب کلی برای دنباله بازگشتی اصلی است.
- هر را باشناخته شده از دنباله بازگشتی اصلی یکسان فرض کنید. اگر چه مقادیر an از دنباله اصلی مرتبط نیستند، مگر در موارد استثنایی، فقط d مورد نیاز است. این روند یک سیستم خطی با معادلات d را درست میکند. حل این معادلات برای ضرایب نامعلوماز راه حل کلی و جایگذاری آن در راه حل کلی یک روش خاص برای حل دنباله بازگشتی با شرایط اولیه به دست میآید.
روش حل معادلات تفاضلی خطی نیز مانند بالاست. حدس هوشمندانه برای معادلات تفاضلی خطی با ضریب ثابت e که λ یک عدد مختلط است، وجود دارد که با جایگزین کردن حدس در معادلات تفاضلی به دست میآید.
این یک قرارداد است. بسط تیلور یک روش حل برای معادلات تفاضلی خطی است:
دیده میشود که ضرایب این بسط برابر مشتق n ام تابع (f(x است. رابطه دیفرانسیلی مدل تفاضلی خطی ای را مربوط به این ضرایب ایجاد میکند. این همارزی میتواند برای حل روابط بازگشتی با ضرایب سریهای توانی در راه حل معادلات تفاضلی خطی مورد استفاده قرار گیرد. قانون شست _ برای معادلات که در آن چندجملهای ضرب دوره اول غیر صفر صفر است _این است:
و به صورت کلی تر:
بهطور مثال، دنباله بازگشتی برای ضرایب بسط تیلور در دنباله زیر
به صورت زیر داده شده:
که همان
است. این مثال نشان میدهد که چگونه مشکلاتی که با روشهای کلی توانی در کلاس معادلات تفاضلی قابل حل اند، با روشی سادهتر حل میشوند.
مثال: معادله تفاضلی
که به آسانی دیده میشود که مشتق n ام e در که در a ارزیابی میشود برابر صفر است.
حل روابط بازگشتی ناهمگن
اگر رابطۀ بازگشتی ناهمگن باشد، جواب خاص را میتوان با روش ضرایب نامعین بهدست آورد. جواب کلی برابر است با مجموع جوابهای روابط همگن و خاص. روش دیگر حل یک رابطۀ بازگشتی ناهمگن، روش مشتقگیری سمبلیک میباشد. برای مثال رابطۀ بازگشتی زیر را در نظر بگیرید:
که یک رابطۀ بازگشتی ناهمگن است. اگر
با تفریق رابطۀ بازگشتی اصلی و رابطۀ بهدست آمده، به رابطۀ زیر میرسیم:
یا
این یک رابطۀ بازگشتی همگن است که میتوان آن را با روشهای ذکر شده حل کرد. بهصورت کلی، اگر یک رابطه بازگشتی خطی به شکل زیر وجود داشته باشد:
که در آن
تابع مولد ناهمگنی باشد و
تابع مولد رابطۀ بازگشتی ناهمگن باشد که در آن ضرائب ثابت ci به روش زیر بدست میآیند:
اگر (P(x تابع مولد گویا باشد، (A(x هم مانند آن خواهد بود. در حالت بالا، که pn = K ثابت است، (P(x) = K/(1−x نمونهای از این فرمول خواهد بود. نمونهای دیگر، رابطه بازگشتی
روش مناسبی برای حل وجود دارد.
فرض کنید
حال
روابط بازگشتی همگن خطی کلی
بسیاری از روابط بازگشتی همگن خطی ممکن است با سری فوق هندسی تعمیم یافته حل شوند. شرایط خاصی از اینها منجر به چندجملهای متعامد و بسیاری از توابع خاص میشوند. برای مثال راه حل دنباله زیر
به صورت
روش حل معادلات تفاضلی گویا از مرتبه یک
معادلات تفاضلی گویا از مرتبه یک به صورت
ثبات
ثبات روابط بازگشتی مرتبههای بالاتر
رابطه بازگشتی خطی از مرتبه d
معادله مشخصهای به شکل زیر خواهد داشت.
رابطه بازگشتی پایدار است، بدین معنا که تکرارها بدون علامت خاصی همگرا به مقداری خاص هستند، اگر و تنها اگر مقادیر ویژه (ریشههای معادله مشخصه)، خواه حقیقی یا مختلط، تماماً کمتر از قدر مطلق واحد هستند.
ثبات ماتریس بازگشتی خطی از مرتبه اول
در معادله ماتریس بازگشتی خطی از مرتبه اول
با بردار حالت x و ماتریس انتقالی x,A همگرا به بردار حالت یکنواخت *x خواهد بود اگر و تنها اگر تمام مقادیر ویژه از ماتریس انتقالی A مقدار قدر مطلقی کمتر از واحد داشته باشند.
ثبات روابط بازگشتی غیرخطی اولین مرتبه
رابطه بازگشتی غیرخطی اولین مرتبه زیر را در نظر بگیرید:
این رابطه بازگشتی پایدار محلی است، بدین معنا که به نقطه ثابت x* از نقاط نزدیک به آن همگرا است، اگر دامنه f در همسایگی x* کوچکتر از واحد در مقدار قدر مطلقی باشد؛ که یعنی:
یک رابطه بازگشتی غیر خطی میتواند چندین نقطه ثابت داشته باشد، که در آنها ممکن پایدار یا ناپایدار باشد. برای یک f پیوسته، دو نقطه ثابت نمیتوانند پایدار محلی باشند. یک رابطه بازگشتی غیر خطی میتواند چرخهای از دوره k برای k > 1 داشته باشد. این چرخه پایدار است، بدین معنا که مجموعهای از شرایط اولیه مثبت را جذب میکند اگر تابع مرکب
با داشتن n بار از f، پایدار محلی است.
در یک رابطه بازگشتی آشوب، متغیر x در ناحیه بستهای باقی میماند ولی همگرا به نقطه ثابت یا یک چرخه نمیشود؛ هرگونه نقطه ثابت یا چرخهای از معادلات ناپایدارند. به نقشه منطقی، تبدیل دوتایی و نقشه چادر رجوع شود.
روابط مدلهای تفاضلی
وقتی که به حل مدلهای تفاضلی عادی عددی پرداخته میشود، عموماً به روابط بازگشتی برخورد خواهیم کرد. برای مثال، در حل مسئله مقدار اولیه
با روش اویلر و اندازه گام h، مقادیر
با رابطه بازگشتی
محاسبه خواهند شد. سیستمهای مدلهای تفاضلی مرتبه اول را میتوان توسط روشهای نشان داده شده در بخش گسسته سازی، گسسته ساخت.
کاربردها
زیستشناسی
برخی از بهترین مدلهای تفاضلی شناخته شده از تلاشهای صورت گرفته برای مدلسازی پویاشناسی جمعیت سرچشمه گرفتهاند. برای مثال اعداد فیبوناچی در دورهای برای مدلسازی رشد جمعیت خرگوشها مورد استفاده قرار میگرفت. نقشه منطقی هم به صورت مستقیم برای مدلسازی رشد جمعیت و هم به عنوان نقطه شروعی برای مدلهای مفصل تر استفاده میشود. در این مقاله، مدلهای تفاضلی جفتی (کوپل) برای مدلسازی فعل و انفعال دو یا چند جمعیت مورد استفاده قرار میگیرند. برای مثال، مدل نیکولسون-بیلی برای یک فعل و انفعال انگل-میزبان به صورت زیر بدست میآید:
که در آن Nt نشان دهنده میزبانها و Pt انگلها در زمان t هستند. معادلات دیفرانسیلی انتگرالی شکلی از رابطه بازگشتی اند که برای بومشناسی فاصلهای مهم هستند. این و دیگر گونههای مدلهای تفاضلی برای مدلسازی جمعیتهای univoltine مورد استفاده قرار میگیرند.
پردازش سیگنال دیجیتال
در پردازش سیگنال دیجیتال، روابط بازگشتی میتوانند بازخورد به سیستم را مدلسازی کنند که خروجیها در یک زمان، ورودیهای زمانهای آتی خواهد بود؛ بنابراین آنها در فیلتر دیجیتال پاسخ برانگیزش نامتناهی (IIR) دیده خواهند شد. برای مثال، معادله برای یک پسخور IIR فیلتر ترکیبی با تأخیر T برابر خواهد بود با:
که در آن
اقتصاد
روابط بازگشتی، خصوصاً روابط بازگشتی خطی، هم در اقتصاد نظری و هم در اقتصاد تجربی مورد استفاده قرار میگیرد. به ویژه، در اقتصاد کلان، میتوان مدلی از بخشهای متفاوت بزرگ اقتصاد (مثل بخش مالی، بخش کالا، بازار کار و غیره) ایجاد کرد که در آنها اقدامات برخی آژانسها وابسته به متغیرهای تأخیری است. مدل را میتوان با مقادیر فعلی متغیرهای اصلی حل کرد. برای اطلاعات بیشتر به تحلیل سریهای زمانی رجوع شود.
علم کامپیوتر
در تحلیل الگوریتمها، روابط بازگشتی اهمیت زیادی دارند. اگر یک الگوریتم به گونهای طراحی شود که یک مسئله را به زیر مسئلههای کوچکتری تبدیل کند، زمان اجرای آن را میتوان با روابط بازگشتی توصیف کرد. یک مثال ساده زمانی است که یک الگوریتم به طول میانجامد تا به دنبال یک جزء در یک بردار مرتب
که نزدیک به
منابع
مشارکتکنندگان ویکیپدیا. «Recurrence relation». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۴ بهمن ۱۳۹۳.