راهنمایی درمورد برنامه محاسبه دترمینان ماتریس (به درخواست محمد رضا)

یا

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

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

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

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

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

T(4)=4T(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 تا صفر جلوش) خودش رو فراخوانی کنه تا بتونه دترمینان رو حساب کنه!!!!!! اصطلاحا گفته می شه که این روش از مرتبه O(n!) هست.تازه اینها فقط تعداد فراخوانیها رو نشون میده.اینکه هر بار محاسبات توی تابع چقدر طول می کشه و چقدر حافظه نیاز هست بماند ، که اگه بخوایم اونارم حساب کنیم عددمون سر به فلک می کشه!!!

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

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

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

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

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

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

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

که گفته می شه این الگوریتم از مرتبه O(n3) هست.

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

اینم از لیست برنامه ها بصورت عکس

نظر نداده می خوای بری

راهنمایی درمورد برنامه محاسبه دترمینان ماتریس (به درخواست محمد رضا)

مطالب مشابه :

معکوس ماتریس 3 در 3

معکوس ماتریس 3 * 3 و بالاتر ( n * n )

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

بدست آوردن معکوس ماتریس

بدست آوردن وارون یا معکوس یک ماتریس

راهنمایی درمورد برنامه محاسبه دترمینان ماتریس (به درخواست محمد رضا)

ماتریس

محاسبه دترمینان یک ماتریس

برنامه محاسبه معکوس ماتریس n * n ( زبان C# )