صفحه‌ی اصلی

صفحه‌ی شخصی مسعود اقدسی‌فام
الگوریتمستان - برنامه‌نویسی و طراحی الگوریتم
RSS Feed
● وب‌گاه مجموعه سوالات منطقه‌ای و جهانی مسابقات برنامه‌نویسی ACM-ICPC، با امکان ارسال پاسخ و بررسی جواب.
● علاقه‌مندان به شرکت در مسابقات برنامه‌نویسی و حل سوالات الگوریتمی می‌توانند از این وب‌گاه معتبر به همراه کتاب‌های معرفی شده جهت تمرین و آمادگی بیشتر استفاده کنند.
امروز: جمعه، 15 اسفند ماه 1393 ، کاربران حاضر در وب‌گاه: 4 نفر
جستجو در نوشته‌های وب‌گاه:   
بحث در مورد مسأله‌ی کاشی‌کاری یا فرش کردن زمین با موزاییک به روش تقسیم و حل
آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C
بررسی مسأله‌ی برج هانوی و روش‌های حل بازگشتی و غیربازگشتی آن
آشنایی با روش مرتب‌سازی سریع، همراه با قطعه کدهای نمونه به زبان برنامه‌نویسی ++C
بررسی روش‌های مختلف محاسبه‌ی ضرایب دوجمله‌ای نیوتن یا ترکیب دو عدد با قطعه کد به زبان برنامه‌نویسی ++C
بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه‌ی دترمینان ماتریس مربعی، و پیچیده‌گی زمانی آنها
آشنایی با روش Divide and Conquer (تقسیم و حل / تقسیم و غلبه) و کاربردهای آن در مرتب‌سازی، جستجو و حل مسائل الگوریتمی دیگر
بررسی مسأله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
آشنایی با دنباله‌ی عددی کاتالان، کاربردها و روش پیاده‌سازی آن به زبان برنامه‌نویسی ++C
بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
آشنایی با درخت جستجوی دودویی (Binary Search Tree) و عملیات جستجو و درج و حذف گره
آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها

  »  

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


              یکشنبه، 17 بهمن ماه 1389
www.aachp.ir
آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «روشهای محاسبه دترمینان ماتریس» خرداد ماه 1385 از طریق وب‌گاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وب‌گاه الگوریتمستان) منتشر شده بود.

دترمینان ماتریس مربعی - که به صورت |A| یا ( det( A نمایش داده می‌شود - یکی از مفاهیم مشهور جبر خطی است که کاربردهای بسیاری در علوم مختلف دارد. امکان محاسبه‌ی سریع دترمینان یک ماتریس با ابعاد بزرگ، بحث مهمی است که در ادامه سه روش محاسباتی رایج و پیچیده‌گی زمانی آنها مرور خواهند شد.

    طبق تعریف دترمینان، اگر اندازه‌ی ابعاد ماتریس مربعی یک باشد (n = 1)، دترمینان همان مقدار تک‌عضو آن است. یعنی:

      

\[ det( \begin{bmatrix} a \end{bmatrix} ) = \vert \begin{bmatrix} a \end{bmatrix} \vert = a \]

      

    اما اگر مرتبه‌ی ماتریس بزرگتر از یک باشد (n > 1)، دترمینان را به یکی از روش‌های زیر می‌توان محاسبه کرد.

      

\[ A_{n \times n} = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix} \]

      

بسط لاپلاس دترمینان

بسط لاپلاس (یا بسط همسازه‌ای) برای محاسبه‌ی دترمینان ماتریس مرتبه‌ی n، به فرم زیر است:

      

\[ \vert A \vert = \sum_{j=1}^{n} {(-1)}^{i+j} a_{ij} \vert A_{ij} \vert \qquad , \qquad 1 \leq i \leq n \]

      

    یا

      

\[ \vert A \vert = \sum_{i=1}^{n} {(-1)}^{i+j} a_{ij} \vert A_{ij} \vert \qquad , \qquad 1 \leq j \leq n \]

      

    که در حالت اول بسط بر اساس سطر دلخواه i و در حالت دوم بر اساس ستون دلخواه j صورت گرفته است. منظور از Aij (ماتریس کهاد)، ماتریسی است که از حذف سطر iام و ستون jام ماتریس اصلی به دست آمده است.

    به عنوان مثال اگر ماتریس مربعی A به صورت زیر تعریف شده باشد:

      

\[ A = \begin{bmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 2 & 2 & 2 \end{bmatrix} \]

      

    دترمینان آن با بسط روی سطر اول به این ترتیب محاسبه می‌شود:

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 2 & 2 & 1 \end{vmatrix} = {(-1)}^{1+1} \times 1 \times \begin{vmatrix} 3 & 1 \\ 2 & 1 \end{vmatrix} + {(-1)}^{1+2} \times (-1) \times \begin{vmatrix} 0 & 1 \\ 2 & 1 \end{vmatrix} \] \[ + {(-1)}^{1+3} \times 8 \times \begin{vmatrix} 0 & 3 \\ 2 & 2 \end{vmatrix} = 1 \times \Big({(-1)}^{1+1} \times 3 \times \vert 1 \vert + {(-1)}^{1+2} \times 1 \times \vert 2 \vert \Big) \] \[ + 1 \times \Big({(-1)}^{1+1} \times 0 \times \vert 1 \vert + {(-1)}^{1+2} \times 1 \times \vert 2 \vert \Big) \] \[ + 8 \times \Big({(-1)}^{1+1} \times 0 \times \vert 2 \vert + {(-1)}^{1+2} \times 3 \times \vert 2 \vert \Big) \] \[ 1 \times( 3 - 2 ) + 1 \times ( 0 - 2 ) + 8 \times ( 0 - 6 ) = 1 - 2 - 48 = -49 \]

      

    و با بسط روی ستون دوم:

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 2 & 2 & 1 \end{vmatrix} = {(-1)}^{1+2} \times (-1) \times \begin{vmatrix} 0 & 1 \\ 2 & 1 \end{vmatrix} + {(-1)}^{2+2} \times 3 \times \begin{vmatrix} 1 & 8 \\ 2 & 1 \end{vmatrix} \] \[ + {(-1)}^{3+2} \times 2 \times \begin{vmatrix} 1 & 8 \\ 0 & 1 \end{vmatrix} = 1 \times \Big( {(-1)}^{1+2} \times 1 \times \vert 2 \vert + {(-1)}^{2+2} \times 1 \times \vert 0 \vert \Big) \] \[ + 3 \times \Big( {(-1)}^{1+2} \times 8 \times \vert 2 \vert + {(-1)}^{2+2} \times 1 \times \vert 1 \vert \Big) \] \[ - 2 \times \Big( {(-1)}^{1+2} \times 8 \times \vert 0 \vert + {(-1)}^{2+2} \times 1 \times \vert 1 \vert \Big) \] \[ 1 \times( -2 + 0 ) + 3 \times ( -16 + 1 ) - 2 \times ( 0 + 1 ) = -2 - 45 -2 = -49 \]

      

    توجه داشته باشید که منظور از | | علامت قدرمطلق نیست.

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

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 0 & 2 & 1 \end{vmatrix} = {(-1)}^{1+1} \times 1  \times \begin{vmatrix} 3 & 1 \\ 2 & 1 \end{vmatrix} + {(-1)}^{2+1} \times 0  \times \begin{vmatrix} -1 & 8 \\ 2 & 1 \end{vmatrix} \] \[ + {(-1)}^{3+1} \times 0 \times \begin{vmatrix} -1 & 8 \\ 3 & 1 \end{vmatrix} = 1 \times \Big( {(-1)}^{1+1} \times 3 \times \vert 1 \vert + {(-1)}^{2 + 1} \times 2 \times \vert 1 \vert \Big) + 0 + 0 = 1 \]

      

پیچیده‌گی زمانی بسط لاپلاس

همانطور که از تعریف مشخص است، در روش بسط لاپلاس، محاسبه‌ی دترمینان یک ماتریس مرتبه‌ی n، به محاسبه‌ی دترمینان n ماتریس کهاد از مرتبه‌ی n - 1 شکسته می‌شود. اگر عمل اصلی محاسبات را اعمال ضرب و جمع در نظر گرفته و ( T1( n تعداد این اعمال را برای محاسبه‌ی دترمینان ماتریس مرتبه‌ی n به روش بسط لاپلاس نشان دهد، می‌توان نوشت:

      

\[ T_1( n ) = n T_1( n - 1 ) + n + n + n - 1 = n T_1( n - 1 ) + 3n - 1 \qquad, \qquad T_1( 1 ) = 0 \]

  

( n T1( n - 1: تعداد اعمال لازم برای محاسبه‌ی زیرمسائل

n: تعداد ضرب‌های بین aij و توان‌های زوج یا فرد منفی یک

n: تعداد ضرب‌های بین aij و ( det( Aij

n - 1: تعداد جمع‌های لازم برای محاسبه‌ی نهایی

      

    حل این رابطه‌ی بازگشتی نشان می‌دهد که ( T1( n از مرتبه‌ی ( !O( n است که برای nهای بزرگ کارایی ندارد.

      

روش گاوس

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

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

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 3 & 3 & 1 \\ 7 & 2 & 1 \end{vmatrix} = - \begin{vmatrix} 3 & 3 & 1 \\ 1 & -1 & 8 \\ 7 & 2 & 1 \end{vmatrix} \]

      

    2- اگر تمام درایه‌های یک سطر (یا یک ستون) ماتریس در عددی مانند k ضرب شود، حاصل دترمینان نیز k برابر می‌شود. در مثال زیر سه برابر بودن درایه‌های متناظر سطر دوم ماتریس سمت چپ، نسبت به سطر دوم ماتریس سمت راست، مقدار دترمینان آن را نیز سه برابر کرده است:

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 3 & 3 & 6 \\ 7 & 2 & 1 \end{vmatrix} = 3 \times \begin{vmatrix} 1 & -1 & 8 \\ 1 & 1 & 2 \\ 7 & 2 & 1 \end{vmatrix} \]

      

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

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 3 & 3 & 6 \\ 7 & 2 & 1 \end{vmatrix} = \begin{vmatrix} 1 & -1 & 8 \\ 3 & 3 & 6 \\ 7 + 5 \times 1 & 2 + 5 \times (-1) & 1 + 5 \times 8 \end{vmatrix} \]

      

    4- دترمینان یک ماتریس مثلثی (ماتریسی که تمامی درایه‌های بالای قطر اصلی یا پایین قطر اصلی و یا هر دو صفر باشند) برابر حاصلضرب درایه‌های قطر اصلی آن است:

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 6 \\ 0 & 0 & 4 \end{vmatrix} = 1 \times 3 \times 4 = 12 \]

      

    5- ماتریسی که تمامی درایه‌های یک سطر (یا یک ستون) آن صفر باشد، دترمینان آن نیز صفر خواهد بود:

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 9 & 3 & 6 \\ 0 & 0 & 0 \end{vmatrix} = 0 \]

      

    در روش گاوس مراحل زیر انجام می‌شود:

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

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

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

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 2 & 1 & 1 \end{vmatrix} = \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 2 + (-2) \times 1 & 1 + (-2) \times (-1) & 1 + (-2) \times 8 \end{vmatrix} = \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 0 & 3 & -15 \end{vmatrix} \]

      

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

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 0 & 3 & -15 \end{vmatrix} = {(-1)}^{1+1} \times 1 \times \begin{vmatrix} 3 & 1 \\ 3 & -15 \end{vmatrix} = \begin{vmatrix} 3 & 1 \\ 3 & -15 \end{vmatrix} \]

      

    مرحله‌ی چهارم: محاسبه‌ی دترمینان ماتریس از مرتبه‌ی n به محاسبه‌ی دترمینان ماتریس مرتبه‌ی n - 1 تقلیل یافته است. با ادامه‌ی این مراحل برای این ماتریس، تا رسیدن به ماتریسی از مرتبه‌ی یک، مقدار دترمینان اصلی محاسبه می‌شود:

      

\[ \begin{vmatrix} 3 & 1 \\ 3 & -15 \end{vmatrix} = \begin{vmatrix} 3 & 1 \\ 3 + (-1) \times 3 & -15 + (-1) \times 1 \end{vmatrix} = \Big( (-1) ^ {1+1} \times 3 \times \vert -16 \vert  \Big) = -48 \]

      

    و در نتیجه:

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 2 & 1 & 1 \end{vmatrix} = -48 \]

      

پیچیده‌گی زمانی روش گاوس

اعمال ضرب و جمع را اعمال اصلی این روش در نظر گرفته و ( T2( n را تعداد این اعمال برای محاسبه‌ی دترمینان به روش گاوس تعریف می‌کنیم. برای صفر کردن ستون اول هر سطر، ضریب مشخصی را محاسبه می کنیم که به یک عمل تقسیم (هم‌ارز ضرب) نیاز دارد. سپس حاصلضرب این ضریب در درایه‌های سطر اول را به درایه‌های متناظر آن سطر اضافه می‌کنیم. در نتیجه این مرحله برای هر سطر n عمل ضرب و n عمل جمع دارد که برای n - 1 سطر باید اعمال شود. در پایان نیز با بسط لاپلاس روی ستون اول و یک عمل ضرب، به محاسبه‌ی دترمینان مرتبه‌ی n - 1 می‌رسیم. پس می‌توان نوشت:

      

\[ T_2(n) = 1 + (n-1)(n+n)  + T_2( n-1) + 1 = T_2 ( n-1) + 2n^2  - 2n + 2 \; \; , \; \; T_2(1) = 0 \]

      

    چنین رابطه‌ی بازگشتی‌ای از مرتبه‌ی ( O( n3 است که بهبود چشمگیری در مقایسه با روش بسط لاپلاس با مرتبه‌ی ( !O( n دارد.

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

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 2 & 1 & 1 \end{vmatrix} = \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 0 & 3 & -15 \end{vmatrix} = \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 0 & 0 & -16 \end{vmatrix} = 1 \times 3 \times -16 = -48 \]

      

    پیاده‌سازی این الگوریتم به سه حلقه‌ی تکرار تو در تو نیاز دارد که با یک حساب سرانگشتی مرتبه‌‌ی ( O( n3 را نشان می‌دهد.

    توجه: در برخی منابع این روش با عنوان گاوس-جردن معرفی می‌شود.

      

روش تحویل

    در بخش ضمیمه‌ی کتاب «حساب دیفرانسیل و انتگرال و هندسه تحلیلی» نوشته‌ی «جرج بی. توماس» و «راس ال. فینی»، فرمول تحویل از مقاله‌ی میلر به صورت زیر بیان شده است:

      

\[ \vert A \vert = \Big( \frac{1}{a_{11}} \Big)^{n-2} \begin{vmatrix} \begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{vmatrix} & \begin{vmatrix} a_{11} & a_{13} \\ a_{21} & a_{23} \end{vmatrix} & \cdots & \begin{vmatrix} a_{11} & a_{1n} \\ a_{21} & a_{2n} \end{vmatrix} \\ \begin{vmatrix} a_{11} & a_{12} \\ a_{31} & a_{32} \end{vmatrix} & \begin{vmatrix} a_{11} & a_{13} \\ a_{31} & a_{33} \end{vmatrix} & \cdots & \begin{vmatrix} a_{11} & a_{1n} \\ a_{31} & a_{3n} \end{vmatrix} \\ \vdots & \vdots & \ddots & \vdots \\ \begin{vmatrix} a_{11} & a_{12} \\ a_{n1} & a_{n2} \end{vmatrix} & \begin{vmatrix} a_{11} & a_{13} \\ a_{n1} & a_{n3} \end{vmatrix} & \cdots & \begin{vmatrix} a_{11} & a_{1n} \\ a_{n1} & a_{nn} \end{vmatrix} \end{vmatrix} \]

      

    یا به عبارت دیگر:

      

\[ \vert A \vert = \Big( \frac{1}{a_{11}} \Big)^{n-2} \begin{vmatrix} c_{11} & c_{12} & \cdots & c_{1(n-1)} \\ c_{21} & c_{22} & \cdots & c_{2(n-1)} \\ \vdots & \vdots & \ddots & \vdots \\ c_{(n-1)1} & c_{(n-1)2} & \cdots & c_{(n-1)(n-1)} \\ \end{vmatrix} \; , \; c_{ij} = \begin{vmatrix} a_{11} & a_{i(j+1)} \\ a_{(i+1)1} & a_{(i+1)(j+1)} \end{vmatrix} \]

      

    به عنوان مثال:

      

\[ \begin{vmatrix} 2 & 4 & 1 & 1 \\ 0 & 2 & 1 & -1 \\ -2 & 1 & 2 & 0 \\ -1 & 1 & 0 & 3 \end{vmatrix} = \Big( \frac{1}{2} \Big)^{4-2} \begin{vmatrix} \begin{vmatrix} 2 & 4 \\ 0 & 2 \end{vmatrix} & \begin{vmatrix} 2 & 1 \\ 0 & 1 \end{vmatrix} & \begin{vmatrix} 2 & 1 \\ 0 & -1 \end{vmatrix} \\ \begin{vmatrix} 2 & 4 \\ -2 & 1 \end{vmatrix} & \begin{vmatrix} 2 & 1 \\ -2 & 2 \end{vmatrix} & \begin{vmatrix} 2 & 1 \\ -2 & 0 \end{vmatrix} \\ \begin{vmatrix} 2 & 4 \\ -1 & 1 \end{vmatrix} & \begin{vmatrix} 2 & 1 \\ -1 & 0 \end{vmatrix} & \begin{vmatrix} 2 & 1 \\ -1 & 3 \end{vmatrix} \end{vmatrix} \] \[ = \Big( \frac{1}{2} \Big)^{2} \begin{vmatrix} 4 & 2 & -2 \\ 10 & 6 & 2 \\ 6 & 1 & 7 \end{vmatrix} = \Big( \frac{1}{2} \Big)^{2} \Big( \frac{1}{4} \Big)^{3-2} \begin{vmatrix} 4 & 28 \\ -8 & 40 \end{vmatrix} = \frac{1}{4} \times \frac{1}{4} \times (160+224) = 24 \]

      

    واضح است که برای چنین محاسبه‌ای باید a11 غیر صفر باشد. اگر اینچنین نبود، طبق اعمال مقدماتی سطر و ستون باید با جابجایی سطرها مقدار آن را غیر صفر کرد.

    این فرمول، مسأله از مرتبه‌ی n را به یک زیرمسأله از مرتبه‌ی n - 1، و n - 1 )2 ) زیرمسأله از مرتبه‌ی 2 تبدیل می‌کند.

پیچیده‌گی زمانی فرمول تحویل

    اگر ( T3( n تعداد اعمال ضرب و جمع برای محاسبه به این روش باشد، می‌توان نوشت:

      

\[ T_3(n)=n-1+ T_3(n-1)+(n-1)^2 T_3(2) = T_3(n-1)+3n^2-5n+2 \;, \; T_3(2) = 3 \]

      

n - 1: تعداد تقسیم و ضرب‌های (یک تقسیم و n - 2 ضرب) لازم برای محاسبه‌ی توان (n- 2)ام معکوس a11 و ضرب آن در دترمینان

( T3( n - 1: تعداد اعمال لازم برای حل زیرمسأله

( n - 1 )2 T3( 2 ): تعداد اعمال لازم برای محاسبه‌ی درایه‌های ماتریس زیرمسأله

      

    حل این رابطه‌ی بازگشتی نیز مرتبه‌ی پیچیده‌گی ( O( n3 را نشان می‌دهد.

      

مقایسه‌ی روش‌های سه‌گانه

عملکرد سه روش بررسی شده را می‌توان اینگونه خلاصه کرد که:

    1- محاسبه‌ی پیچیده‌گی زمانی روش‌های سه‌گانه فوق نشان می‌دهد، کارآیی زمانی دو روش گاوس و فرمول تحویل تقریبا یکسان بوده و بسیار بهتر از روش بسط لاپلاس هستند.

    2- فضای مصرفی هر سه روش در صورت پیاده‌سازی بهینه‌ی آنها، همان فضای لازم برای ذخیره‌ی یک ماتریس مربعی از مرتبه‌ی n است.

    3- هر سه روش ظاهری بازگشتی - با روش تقسیم و غلبه - دارند که حل مسأله از مرتبه‌ی n را به حل زیرمسأله یا زیرمسائلی از مرتبه‌ی n - 1 تقسیم می‌کنند. اما پیاده‌سازی غیربازگشتی این روش‌ها نیز ممکن است که در روش گاوس توضیح مختصری داده شد.

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

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

      

\[ \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 2 & 2 & 1 \end{vmatrix} = \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 2 + (-2) \times 1 & 2 + (-2) \times (-1) & 1 + (-2) \times 8 \end{vmatrix} = \] \[ \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 0 & 4 & -15 \end{vmatrix} = \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 0 & 4 + (-1.333333) \times 3 & -15 + (-1.333333) \times 1 \end{vmatrix} \] \[ = \begin{vmatrix} 1 & -1 & 8 \\ 0 & 3 & 1 \\ 0 & 0 & -16.333333 \end{vmatrix} = -48.999999 \]

      

    این مسأله زمانی اهمیت دارد که محاسبه‌ی دقیق مد نظر بوده و امکان انجام عملیات حسابی روی اعداد گویا وجود نداشته باشد.

      

روش ساروس

دترمینان ماتریس سه در سه با استفاده از بسط لاپلاس به این ترتیب محاسبه می‌شود:

      

\[ \begin{vmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{vmatrix} \] \[ = (-1)^{1+1}a_{11} \begin{vmatrix} a_{22} & a_{23} \\ a_{32} & a_{33} \end{vmatrix} + (-1)^{1+2}a_{12} \begin{vmatrix} a_{21} & a_{23} \\ a_{31} & a_{33} \end{vmatrix} + (-1)^{1+3}a_{13} \begin{vmatrix} a_{21} & a_{22} \\ a_{31} & a_{32} \end{vmatrix} \] \[ = a_{11} (a_{22} a_{33}-a_{23}a_{32} ) - a_{12} (a_{21} a_{33}-a_{23}a_{31} ) + a_{13} (a_{21} a_{32}-a_{22}a_{31} ) \] \[ = a_{11} a_{22} a_{33} + a_{12} a_{23} a_{31} + a_{13} a_{21} a_{32} - a_{11} a_{23} a_{32} - a_{12} a_{21} a_{33} - a_{13} a_{22} a_{31} \]

      

    این عملیات را می‌توان با کمک گرفتن از یک تصویر ذهنی به ترتیب زیر انجام داد:

      

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

      

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

    تذکر: روش ساروس صرفا برای محاسبه‌ی دترمینان ماتریس‌های سه در سه بوده و در سایر ابعاد قابل استفاده نیست.


این نوشته آخرین بار در تاریخ چهارشنبه، 30 مهر ماه 1393 مورد بازبینی علمی قرار گرفته است.
‌چاپ نوشته
نسخه‌ی قابل چاپ مشاهده‌ی نسخه‌ی قابل چاپ و ارسال به چاپگر
به اشتراک‌گذاری نوشته
FriendFeed       Twitter       Facebook       Google Plus       LinkedIn       Cloob
دسته‌بندی
محاسبات ریاضی
‌برچسب‌ها

محاسبات ریاضی

،

روش تقسیم و غلبه

،

ماتریس

امتیاز نوشته
1 2 3 4 5
ارسال پیام
» hedieh

دوشنبه، 23 اسفند ماه 1389، ساعت 21:33
rastesh man terme 2 bargham! khodetoon midoonid bara hale madar bayad determinan balad bashi! khola3 ma ham yademoon rafte bood!
alan besyar azatoon mamnoonam!

» سفدر

سه‌شنبه، 6 اردیبهشت ماه 1390، ساعت 20:03
خیلی ممنون دوست من. عالی بود . به خصوص روش تحول.

» محسن

چهارشنبه، 4 خرداد ماه 1390، ساعت 23:16
درود بر شما
سپاس از مطالب مفیدی که در سایت قرار می دهید.
اگر ممکن است الگوریتم حل دستگاه های چند معادله و چند مجهولی را بگذارید.

» هادی

شنبه، 28 آبان ماه 1390، ساعت 15:27
از مطلب خوب شما استفاده کردم ممنون
موفق باشید

» ساسان

دوشنبه، 28 آذر ماه 1390، ساعت 12:40
با سلام وتشكر از مطالب مفيدتان .لطفا كمي هم از برنامه نويسي
بااستفاده از توابع بازگشتي مطلب و مثال بگذاريد.ممنون!

» میترا

دوشنبه، 19 دی ماه 1390، ساعت 16:33
با تشکر,بسیار مفید بود,موفق باشید

» فرهاد

سه‌شنبه، 4 بهمن ماه 1390، ساعت 10:43
ممنون بسیار مفید بود

» بهنام

جمعه، 7 بهمن ماه 1390، ساعت 09:58
سلام
دستت درد نکنه این مطلب خیلی به کارم اومد
موفق باشی

» سامان

شنبه، 15 بهمن ماه 1390، ساعت 03:40
ممنون

» مهرداد

یکشنبه، 16 بهمن ماه 1390، ساعت 09:26
سلام
مطالب مفید بودند،ممنون. اگه میتونید نحوه ذخیره سازی و عملیات معکوس گیری از ماتریسهای با درایه های اعداد مختلط رو هم توضیح بدید.
(ترجیحا در "C")

» arash

سه‌شنبه، 29 فروردین ماه 1391، ساعت 19:20
سلام
می خواستم دستوراضافه کردن دو ماتری به هم در مطلب رو بدونم
مثلا 2 فایل txt به صورت ماتریسی بشت سر هم به هم اضافه شوند.جمع نشند ها.
برای مثال
m*n   و    p*n   بشوند p+m*n  
اول ماتریس m*n بعد پشت سرش ماتریسp*n  
mamnoon

» samira

سه‌شنبه، 25 مهر ماه 1391، ساعت 21:20
ali bod kheyli estefade kardam

» سمانه

یکشنبه، 7 آبان ماه 1391، ساعت 22:51
یک روش ساده تر هم وجود داره که اینجا ذکر نشده.
نمیدونم چرا؟
اما منم جزئیاتشو فراموش کردم و اومدم پیداش کنم که متاسفانه نبود.


یکشنبه، 7 آبان ماه 1391، ساعت 22:57
مسعود اقدسی‌فام:
اگه پیدا کردید بگید تا من هم آشتا بشم.
البته روش ساروس هم وجود داره که مختص ماتریس‌های سه در سه هستش.

» abd

دوشنبه، 30 بهمن ماه 1391، ساعت 23:53
آیا روشی برای محاسبه ی دترمینان ماتریس چهار در چهار وجود داره؟
با تشکر

» سمانه

سه‌شنبه، 8 اسفند ماه 1391، ساعت 15:14
سلام لطفا روش ریاضی حل معکوس ماتریس مربعی را هم بگذارید.
از طرف دانشجوی عاجز ترم اول ارشد برق

» مسعود

دوشنبه، 21 اسفند ماه 1391، ساعت 13:20
سلام
خسته نباشید
میشه به این سوال من جواب بدید؟
الگوریتمی بنویسید که شعاع و مرکز دایره را بگیرد ان را در سیستم رستری رم کند
اگر کمکم کنید یه دنیا ممنونتون میشم
باتشکر

» مهناز

یکشنبه، 5 خرداد ماه 1392، ساعت 21:08
سلام
ممکنه راهنمای کنید که اگر بخواهیم یک ماتریس تبدیل خطی طراحی کنیم که با داشتن مقسوم و مقسوم علیه باقیماندهو خارج قسمت تقسیم به پیمانه 2 را تولید کند ، چه باید کرد؟
ممنونم

» سجاد

شنبه، 23 آذر ماه 1392، ساعت 23:50
با سلام
برنامه ای در محیط سی بنویسید که یک ماترس 2*2 را از ورودی گرفته و مقادیر ویژه آن را محاسبه کند.
فقط خیلی عجله دارم ممنون میشم راهنماییم کنی دوست عزیز

» مصطفی

سه‌شنبه، 29 بهمن ماه 1392، ساعت 11:54
سلام
میخاستم بدونم روش ساروس برای ماتریسn*nوجود داره میشه برام ایمیل کنیی البته اگه وجود داره
ممنون

» رضا آدم پیرا

چهارشنبه، 6 فروردین ماه 1393، ساعت 19:49
سلام
میخاستم بدونم روش حل ماتریس سه قطری بلوکی به روش توماس رو دارید ؟
اگر مقدوره براتون بهمراه کدc++  برام میل کنید.
ممنون

» سجاد

دوشنبه، 1 اردیبهشت ماه 1393، ساعت 11:59
مرسی خوب بود

» صابر

چهارشنبه، 17 اردیبهشت ماه 1393، ساعت 19:19
آقا دمت گرم شارژ شدیم

» الهه

چهارشنبه، 16 مهر ماه 1393، ساعت 18:19
مرسی دوست عزیز خیلی مفید بود

» بابابرقی

پنجشنبه، 15 آبان ماه 1393، ساعت 14:12
سلام ممنون خوب بودpdfروهم میذاشتین ازخوب هم بهتر میشد درضمن اکثربچه های برق مشکل دترمینان رودارن قابل توجه بعضیا،بازم ممنون

» saleh

جمعه، 30 آبان ماه 1393، ساعت 16:04
Hey there  . Thank you so much.

» اسماعیل

چهارشنبه، 19 آذر ماه 1393، ساعت 21:09

باسلام وتشکر از زحمات شما
درروش تحویل - درایۀ سطردوم ،ستون اول ازدترمینان واقع دردرایۀ سطر دوم ، ستون دوم دترمینان ماتریس(1-n-1) * (n) (که باc22 نمایش داده شده) بایستی a31 نوشته شود که a21 درج گردیده است .


پنجشنبه، 20 آذر ماه 1393، ساعت 00:49
مسعود اقدسی‌فام:
سلام
ممنون از تذکرتون. اصلاح شد.

» محمد

پنجشنبه، 11 دی ماه 1393، ساعت 23:37
ها

» هومن

چهارشنبه، 1 بهمن ماه 1393، ساعت 20:03
سلام. روز خوبی داشته باشید.
مطلب شما خیلی خوب بود. به منم کمک کرد.
بسیار ممنون.
موفق باشید.



دوست عزیزم، لطفا قبل از ارسال پیام به موارد زیر توجه داشته باشید:

1- تا حد ممکن از حروف فارسی برای نگارش پیام خود استفاده کنید. امکان ارسال پیام لاتین و کدهای برنامه‌نویسی با چیدمان چپ به راست نیز وجود دارد.
2- به درخواست پروژه‌های آماده و موارد مشابه پاسخ داده نخواهد شد.
3- از قرار دادن هرگونه نشانی یا شماره تماس در متن پیام خودداری کنید.
4- از ارسال پیام‌های تبلیغاتی خودداری کنید.
5- از ارسال سوال و پیام غیرمرتبط با این نوشته خودداری کنید.
6- لطفا نظر خود را در مورد این نوشته با ثبت امتیاز مشخص نمایید.

پیشاپیش از همکاری شما سپاسگذارم.


نام:  
پست الکترونیک
وب‌گاه:
متن پیام: