منو
 کاربر Online
800 کاربر online
تاریخچه ی: حل روابط بازگشتی ناهمگن

در حال مقایسه نگارشها

نگارش واقعی نگارش:2


این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


حل روابط بازگشتی ناهمگن

تعریف روابط بازگشتی غیرهمگن با ضرایب ثابت

رابطه بازگشتی درجه زیر غیر همگن است:

اگر An در رابطه بازگشتی همگن (1) صدق کند و در رابطه بازگشتی غیرهمگن صدق کند آنگاه نیز در رابطه غیرهمگن صدق می‌کند. زیرا:

در این حالت را جواب قسمت همگن رابطه و را یک جواب خاص آن گویند. مثلاً اگر
، آنگاه و چون ، قرار میدهیم
،
حال داریم:

در نتیجه، برای این که این رابطه یک اتحاد برای باشد، داریم: ، در این صورت، و خواهیم داشت:

با فرض داریم: پس:


حل روابط بازگشتی غیرهمگن

اگر رابطه بازگشتی غیرهمگن را به صورت زیر داشته باشیم:
(1)----------

که در آن ثابت است و چند جمله‌ای، از درجه بر حسب باشد، برای این رابطه، مشابه روابط بازگشتی همگن معادله سرشت‌نما به صورت زیر تعریف می‌شود:
(2)----------

با داشتن این معادله و به دست آوردن ریشه‌های آن مشابه قبل، جواب‌های این معادله به صورت ترکیب خطی بیان می‌شود. (تحقیق این موضوع به عهده شما.) به طورکلی ریشه‌های معادله سرشت‌نمای یک رابطه بازگشتی مشخص کننده جواب‌های رابطه بازگشتی است. با داشتن این معادله سرشت‌نما برای روابط بازگشتی بسیاری از این روابط با روشی مشابه روابط بازگشتی همگن، به راحتی قابل حل است.

مثال

الف. رابطه بازگشتی را حل کنید.
ب. رابطه بازگشتی را حل کنید.
حل .
الف. معادله سرشت‌نمای این رابطه به صورت در می‌آید، پس:
که با توجه به حالت‌های اولیه داده شده، می‌توان ها را به دست آورد.
ب. معادله سرشت‌نمااست، پس داریم:

در حالت کلی معادله سرشت‌نمای رابطه بازگشتی زیر:
(3) ----------

به صورت:

است.

مثال

رابطه بازگشتی را حل کنید.
حل .
معادله سرشت نمای آن به صورت است. پس:



و مثلاً اگر داریم:

بدین ترتیب بسیاری از روابط بازگشتی با ضرایب ثابت حل می‌شوند.
حال با حل مسأله‌ای کاربردی به روشی دیگر در حل روابط بازگشتی توجه می‌کنیم:

مثال. (بیست و یکمین المپیاد جهانی ریاضی)

و را دو رأس روبه‌روی یک 8 ضلعی منتظم می‌گیریم، قورباغه‌ای از رأس آغاز به جهیدن می‌کند و هربار به رأس مجاور می‌پرد. ولی وقتی به رأس رسید، همان‌جا متوقف می‌شود. را تعداد مسیرهایی می‌گیریم که قورباغه با جهش از به برسد. ثابت کنید:

که در آن و
حل.
8 ضلعی زیر را در نظر می‌گیریم. فرض کنید تعداد مسیرهایی باشد که قورباغه در آنها با جهش از به برسد. اگر قورباغه بخواهد از به برود، در دو جهش اول یا به می‌رسد یا به می‌رسد یا به برمی‌گردد و به دو طریق می‌تواند به بازگردد . حال از جایی که الان به آن رسیده باید شروع کند و باجهش به برسد، بنابراین. در مورد نیز مشابهاً می‌توان گفت (چرا؟)
img/daneshnameh_up/1/10/com0028a.jpg

دقت می‌کنیم که چون بین و ، 4 ضلع وجود دارد، برای رفتن از به حتماً تعداد زوجی حرکت لازم است. پس . برای حالت‌های زوج دو رابطه بازگشتی و
را داریم. حال دو روش وجود دارد،
روش اول. از تفاضل دو رابطه بدست می‌آید:

و در نتیجه با گذاشتن در رابطه اولی داریم:

حال اگر در نظر بگیریم، رابطه همگن (به ازای) بدست می‌آید که با توجه به حالت‌های اولیه و خواهیم داشت (با تشکیل معادله سرشت‌نما و حل آن بدست می‌آید):

حال مشابه مثال‌های قبل به دلیل اینکه ، می‌توان تحقیق کرد:
(4)----------

روش دوم. این روش با آنچه تا به حال گفتیم متفاوت است. ما به این روش در حل این مسأله بسنده می‌کنیم:


حال اگر بردار را به صورت تعریف کنیم، باید داشته باشیم:

برای تعیین بردار با این حالت خاصیت مقادیر ویژه ماتریس را تعیین می‌کنیم. این مقادیر ریشه‌های معادله مفسر ماتریس می‌باشند :
img/daneshnameh_up/5/59/com0028b.jpg

و بنابراین: و . بردارهای ویژه ماتریس ، یعنی و دارای این ویژگی هستند که: و و ……… که برای می‌توان آنها را پیدا کرد:

بنابراین یک ترکیب خطی از و است. یعنی:


و بدین ترتیب:



پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0049.pdf

همچنین ببینید





این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


حل روابط بازگشتی ناهمگن

تعریف روابط بازگشتی غیرهمگن با ضرایب ثابت

رابطه بازگشتی درجه زیر غیر همگن است:

اگر An در رابطه بازگشتی همگن (1) صدق کند و در رابطه بازگشتی غیرهمگن صدق کند آنگاه نیز در رابطه غیرهمگن صدق می‌کند. زیرا:

در این حالت را جواب قسمت همگن رابطه و را یک جواب خاص آن گویند. مثلاً اگر
، آنگاه و چون ، قرار میدهیم
،
حال داریم:

در نتیجه، برای این که این رابطه یک اتحاد برای باشد، داریم: ، در این صورت، و خواهیم داشت:

با فرض داریم: پس:


حل روابط بازگشتی غیرهمگن

اگر رابطه بازگشتی غیرهمگن را به صورت زیر داشته باشیم:
(1)----------

که در آن ثابت است و چند جمله‌ای، از درجه بر حسب باشد، برای این رابطه، مشابه روابط بازگشتی همگن معادله سرشت‌نما به صورت زیر تعریف می‌شود:
(2)----------

با داشتن این معادله و به دست آوردن ریشه‌های آن مشابه قبل، جواب‌های این معادله به صورت ترکیب خطی بیان می‌شود. (تحقیق این موضوع به عهده شما.) به طورکلی ریشه‌های معادله سرشت‌نمای یک رابطه بازگشتی مشخص کننده جواب‌های رابطه بازگشتی است. با داشتن این معادله سرشت‌نما برای روابط بازگشتی بسیاری از این روابط با روشی مشابه روابط بازگشتی همگن، به راحتی قابل حل است.

مثال

الف. رابطه بازگشتی را حل کنید.
ب. رابطه بازگشتی را حل کنید.
حل .
الف. معادله سرشت‌نمای این رابطه به صورت در می‌آید، پس:
که با توجه به حالت‌های اولیه داده شده، می‌توان ها را به دست آورد.
ب. معادله سرشت‌نمااست، پس داریم:

در حالت کلی معادله سرشت‌نمای رابطه بازگشتی زیر:
(3) ----------

به صورت:

است.

مثال

رابطه بازگشتی را حل کنید.
حل .
معادله سرشت نمای آن به صورت است. پس:



و مثلاً اگر داریم:

بدین ترتیب بسیاری از روابط بازگشتی با ضرایب ثابت حل می‌شوند.
حال با حل مسأله‌ای کاربردی به روشی دیگر در حل روابط بازگشتی توجه می‌کنیم:

مثال. (بیست و یکمین المپیاد جهانی ریاضی)

و را دو رأس روبه‌روی یک 8 ضلعی منتظم می‌گیریم، قورباغه‌ای از رأس آغاز به جهیدن می‌کند و هربار به رأس مجاور می‌پرد. ولی وقتی به رأس رسید، همان‌جا متوقف می‌شود. را تعداد مسیرهایی می‌گیریم که قورباغه با جهش از به برسد. ثابت کنید:

که در آن و
حل.
8 ضلعی زیر را در نظر می‌گیریم. فرض کنید تعداد مسیرهایی باشد که قورباغه در آنها با جهش از به برسد. اگر قورباغه بخواهد از به برود، در دو جهش اول یا به می‌رسد یا به می‌رسد یا به برمی‌گردد و به دو طریق می‌تواند به بازگردد . حال از جایی که الان به آن رسیده باید شروع کند و باجهش به برسد، بنابراین. در مورد نیز مشابهاً می‌توان گفت (چرا؟)
img/daneshnameh_up/1/10/com0028a.jpg

دقت می‌کنیم که چون بین و ، 4 ضلع وجود دارد، برای رفتن از به حتماً تعداد زوجی حرکت لازم است. پس . برای حالت‌های زوج دو رابطه بازگشتی و
را داریم. حال دو روش وجود دارد،
روش اول. از تفاضل دو رابطه بدست می‌آید:

و در نتیجه با گذاشتن در رابطه اولی داریم:

حال اگر در نظر بگیریم، رابطه همگن (به ازای) بدست می‌آید که با توجه به حالت‌های اولیه و خواهیم داشت (با تشکیل معادله سرشت‌نما و حل آن بدست می‌آید):

حال مشابه مثال‌های قبل به دلیل اینکه ، می‌توان تحقیق کرد:
(4)----------

روش دوم. این روش با آنچه تا به حال گفتیم متفاوت است. ما به این روش در حل این مسأله بسنده می‌کنیم:


حال اگر بردار را به صورت تعریف کنیم، باید داشته باشیم:

برای تعیین بردار با این حالت خاصیت مقادیر ویژه ماتریس را تعیین می‌کنیم. این مقادیر ریشه‌های معادله مفسر ماتریس می‌باشند :
img/daneshnameh_up/5/59/com0028b.jpg

و بنابراین: و . بردارهای ویژه ماتریس ، یعنی و دارای این ویژگی هستند که: و و ……… که برای می‌توان آنها را پیدا کرد:

بنابراین یک ترکیب خطی از و است. یعنی:


و بدین ترتیب:



پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0049.pdf

همچنین ببینید




تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:13 ]   3   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [08:59 ]   2   زینب معزی      v  c  d  s 
 سه شنبه 14 شهریور 1385 [12:10 ]   1   زینب معزی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..