روشهای محاسبه دترمینان

دانش آموزان ریاضی و علاقه مندان ریاضیات تعریف اولیه دترمینان یک ماتریس مربعی از مرتبه n رو می دونن:

یا

که دترمینان ماتریس مربعی مرتبه n رو به دترمینان n تا ماتریس از مرتبه n - 1 تبدیل می کنه و البته برای مرتبه 2 داریم:

حالا فرض کنید تابعی نوشتیم که دترمینان یک ماتریس مربعی مرتبه n رو به روش خودفراخوانی (بازگشتی) محاسبه می کنه. فکر می کنید اگه n=20 باشه ، این تابع چند بار باید خودش را فرابخونه تا بتونه دترمینان رو حساب کنه؟ مرحله توقف تابع بازگشتی رو هم n = 2 در نظر بگیرید یعنی برای n = 2 تابع مستقیما دترمینان رو محاسبه می کنه.

فکر می کنید این عدد چقدر بزرگ باشه؟ حساب می کنیم:

فرض کنیم ( T( n تعداد فراخوانیها برای حساب کردن دترمینان ماتریس مرتبه n باشه. واضحه که T ( 2 ) = 1 ، و همینطور:

T( 3 ) = 3 T( 2 ) + 1 = 4

T( 4 ) = 4 T( 3 ) + 1 = 17

برای حساب کردن دترمینان ماتریس 3 در 3 یه بار تابع رو با n = 3 فراخوانی می کنیم . اون هم خودش سه بار تابع رو برای n = 2 فراخوانی می کنه. پس رو هم 4 بار تابع فراخوانی می شه و ...

با یه حساب سر انگشتی می تونید به این نتیجه برسید که اگه n به اندازه کافی بزرگ باشه (مثلا n > 10) می شه گفت:

T( n ) = n! ( e - 2 )

(e عدد نپر و !n برای فاکتوریل n)

یعنی مثلا برای n = 20 تابع باید بیشتر از 1.7 میلیارد میلیارد بار (یه 17 با 17 تا صفر جلوش!!) خودش رو فراخوانی کنه تا بتونه دترمینان رو حساب کنه!!!!!! تازه اینها فقط تعداد فراخوانیها رو نشون میده. اینکه هر بار محاسبات تابع چقدر طول می کشه و چقدر حافظه نیاز هست بماند ، که اگه بخوایم اونها رو هم حساب کنیم عددمون سر به فلک می کشه!!!

خوب حالا فکر می کنید کامپیوتر چطور دستگاههای بزرگ معادلات رو حل می کنه؟ محض اطلاع اون عزیزانی که اطلاع ندارن بگم توی مباحثی مثل تحقیق در عملیات و برنامه ریزی خطی ممکنه یه دستگاه معادلات 100 مجهوله داشته باشیم که اگه قرار باشه از روش بالا برای پیدا کردن جواب استفاده کنیم چند هزار سال با قویترین کامپیوتر ها طول می کشه!

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

اما آیا روش دیگه ای وجود داره؟

اگه بخش ضمیمه کتاب «حساب دیفرانسیل و انتگرال و هندسه تحلیلی» نوشته «جرج بی. توماس و ...» رو که تو هر دانشگاه و کتابخونه ای پیدا می شه بخونید ، یه روش خیلی جالب برای محاسبه دترمینان ارائه شده که دترمینان ماتریس مرتبه n رو فقط به یه دترمینان از مرتبه n - 1 تبدیل می کنه. روش جدید به این شکله:

البته باید توجه کنید که تو هر مرحله درایه سطر و ستون اول باید غیر صفر باشه که اگه نبود می شه سطرها رو جابه جا کرد. اگه جابه جایی سطرها هم اثر نداشت به این معنی که یه ستون با درایه های صفر داریم. پس دترمینان صفر می شه.

حالا اگه ( T ( n رو واسه این روش حساب کنیم (خودتون زحمتش رو بکشین) به دست می یاد:

T( n ) = ( 2 n3- 3 n2 + 7 n -12 ) / 6

اگه n = 20 باشه: T( 20 ) = 14928 که نشون میده این روش نسبت به روش اول فوق العاده کاراتره (15هزار کجا و 1.7 میلیارد میلیارد کجا !!!!) در ضمن محاسباتش هم نسبت به روش اول خیلی خیلی کمتره. ولی به پای روش گاوس – جردن نمی رسه.

خوب حالا فکر می کنید بتونید برنامه محاسبه دترمینان به روش سوم رو بنویسید؟ بسم ا ... ما منتظریم.

روشهای محاسبه دترمینان

مطالب مشابه :

روشهای محاسبه دترمینان

نمونه طرح درس حسابداری

بودجه بندی سوال های کنکور سراسری در سال های اخیر

بارم بندی دروس ریاضیات دوره |پیش دانشگاهی (سال چهارم )