منو
 کاربر Online
719 کاربر online

عمل قهقرایی

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)




عمل قهقرایی

عمل به قهقرا در یک مساله به معنای آن است که نتیجه آن مساله را بپذیریم و بر این اساس، پس از نتیجه گیری های متوالی از نتیجه، به آنچه معلوم است یا به حکمی که بتوان آن را به سادگی ثابت کرد، دست یابیم. پس از رسیدن به فرض یا معلوم، مراحل استدلال را معکوس می کنیم و به سوی حکم اصلی پیش می رویم.
این شیوه در جبر و مثلثات دبیرستانی معمول است. مثلا برای یافتن همه عددهای حقیقی که در معادله صدق می کنند، به شکل زیر استدلال می کنیم. فرض کنید در معادله صدق کند. در این صورت با اضافه کردن 2 به دو طرف معادله و تقسیم دو طرف آن بر 5، به دست می آوریم . از آنجا که هر یک از گام های به کار رفته در استدلال برگشت پذیر است، نتیجه می گیریم که 2 واقعا در معادله صدق می کند و این تنها جواب ممکن است.
اغلب در عمل های رایجی، چون مثال قبلی، بازنویسی گام های استدلال به شکل صریح انجام نمی شود. ولی این مطلب مهم است که بدانیم چه چیزی برگشت پذیر است و چه چیزی برگشت پذیر نیست. مثلا معادله را در نظر بگیرید. (در اینجا مطابق معمول، ریشه دوم مثبت در نظر گرفته شده است.) معادله را به شکل بنویسید و دو طرف را به توان دو برسانید تا به دست آورید و یا معادله . اگر بار دیگر دو طرف را به توان دو برسانیم، به دست می آوریم یا . بنابراین نتیجه می گیریم که اگر عددی چون در معادله صدق کند، آن عدد باید باشد. ولی در معادله اصلی صدق نمی کند.به دلیل برابری به برابری می رسیم. ولی وقتی عملیات را به ترتیب عکس در نظر بگیریم، از به خواهیم رسید.
عمل قهقرایی هم مانند روش جستجوی الگو و سایر روش ها مختص مسایل استقرایی نیست ولی بعضی از مسایل استقرایی را می توان به این شکل حل کرد. در مسایل استقرایی معمولا ما حکم استقرا یعنی را درست فرض می کنیم، سپس با استفاده از فرض استقرا ، حکم مساله را ساده می کنیم تا به یک چیز معلوم یا درست برسیم، در نتیجه حکم استقرا ثابت می شود.
باید دقت داشت که تمام مسایلی که با روش قهقرایی می توان حل کرد را می توان با روش مستقیم نیز حل کرد ولی در بعضی از موارد این روش مناسب تر از روش مستقیم می باشد. این روش مخصوصا در اثبات نامساوی ها کاربرد فراوانی دارد.

مثال1

به ازای هر ثابت کنید:

اثبات.
به ازای که نامساوی برقرار است.
حال فرض می کنیم که حکم استقرا درست باشد پس:

طبق فرض استقرا داریم:

در نتیجه داریم:

با ساده کردن نامساوی بالا و به توان رساندن دو طرف نامساوی داریم: (دقت کنید که چون طرفین نامساوی بالا، مثبتند می توانیم آنها را به توان برسانیم.)

که چون پس به یک حکم معلوم رسیدیم. پس با معکوس کردن استدلال بالا می توان به حکم استقرا رسید و درستی آن را ثابت کرد.



مثال2

اگر باشند، ثابت کنید به ازای هر داریم:

و تساوی وقتی و فقط وقتی برقرار است که یا باشد.
اثبات.
اگر باشد که واضح است که حکم برقرار است. پس ثابت می کنیم اگر وباشد، است.
به ازایکه حکم برقرار است زیرا، پس.
حال طبق روش قهقرایی فرض می کنیم حکم استقرا درست باشد یعنی:

طبق فرض استقرا داریم: ، پس:

پس با ساده کردن طرفین داریم:

با فاکتور گیری از طرفین نامساوی داریم:

که نامساوی فوق درست است زیرا و. حال اگر استدلال را معکوس به عقب برگردیم، اثبات کامل است.
حال بهتر است سری هم به دترمینان ها بزنیم. خیلی از مسایل مربوط به دترمینان ها را می توان با استقرا حل کرد.



مثال 3

فرض کنید اعداد حقیقی باشند و. همچنین تعریف می کنیم

نشان دهید
img/daneshnameh_up/3/3c/comm0007a.JPG

اثبات.
به ازای داریم و و

و لذا حکم برقرار است.
فرض کنید که حکم به ازای درست باشد، حال می خواهیم مسئله را برای عدد حقیقی ثابت کنیم. می خواهیم مقدار
img/daneshnameh_up/c/c5/comm0007b.JPG

را به دست آوریم. ستون دوم را از ستون اول کم می کنیم (این کار مقدار دترمینان را تغییر نمی دهد.)
img/daneshnameh_up/2/26/comm0007c.JPG

حال دترمینان را نسبت به ستون اول بسط می دهیم. مقدار زیر به دست می آید:
img/daneshnameh_up/3/3a/comm0007d.JPG

هر دو دترمینان بالا را- که به صورت ماتریس های هستند- می توان از فرض استقرا به دست آورد. اگر و باشند. طبق فرض استقرا داریم:

از طرفی داریم و پس داریم:


و حکم با استقرا ثابت شد.



استقرای قهقرایی

می خواهیم قضیه زیر را اثبات کنیم:

قضیه ( نابرابری میانگین حسابی – هندسی)

اگر ، عدد حقیقی نامنفی باشند و
و

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



اصل استقرای قهقرایی

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

تساوی هم وقتی و فقط وقتی برقرار است که باشد. پس حکم را به ازای پایه استقرا ثابت کردیم.
حال می خواهیم حکم را به ازای ثابت کنیم. فرض کنید:
و

و

و

طبق تعریف و داریم: و .
حال اگر اعداد و را در نظر بگیرید، طبق پایه استقرا داریم:



طبق فرض استقرا داریم: و . بنابراین:

بنابراین ثابت کردیم که است. حال فرض کنید . درنتیجه طبق پایه استقرا باید و طبق نامساوی بالا باید و . بنابراین طبق فرض استقرا باید داشته باشیم:


بنابراین باید باشد و حکم ثابت شد.
حال که درستی شرط ب (استقرای قهقرایی) را ثابت کردیم؛ باید درستی شرط الف (استقرای قهقرایی) را نیز ثابت کنیم.
فرض کنید:

حال اگر به جای قرار دهیم . نتیجه می شود:

اگر طرفین نامساوی را به توان برسانیم، نتیجه می شود:

درنتیجه:

واضح است که تساوی در بالا برقرار است اگر و تنها اگر باشد که . درنتیجه و اثبات تمام شد.

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

http://olympiad.roshd.ir/computer/content/pdf/0011.pdf

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




تعداد بازدید ها: 17493


ارسال توضیح جدید
الزامی
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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..