محاسبه دترمینان ماتریس با روش گاوس¶
مسئله: یک ماتریس $A$ با ابعاد $N \times N$ داده شده است. دترمینان آن را محاسبه کنید.
الگوریتم¶
ما از ایده‌های روش گاوس برای حل دستگاه معادلات خطی استفاده می‌کنیم.
ما همان مراحل حل دستگاه معادلات خطی را انجام می‌دهیم، با این تفاوت که از تقسیم سطر جاری بر $a_{ij}$ صرف نظر می‌کنیم. این عملیات قدر مطلق دترمینان ماتریس را تغییر نمی‌دهند. با این حال، هنگامی که دو سطر از ماتریس را جابجا می‌کنیم، علامت دترمینان می‌تواند تغییر کند.
پس از اعمال روش گاوس بر روی ماتریس، به یک ماتریس قطری می‌رسیم که دترمینان آن برابر با حاصل‌ضرب درایه‌های روی قطر اصلی است. همانطور که قبلاً ذکر شد، علامت دترمینان را می‌توان با توجه به تعداد سطرهای جابجا شده تعیین کرد (اگر تعداد جابجایی‌ها فرد باشد، علامت دترمینان باید معکوس شود). بنابراین، می‌توانیم از الگوریتم گاوس برای محاسبه دترمینان ماتریس با پیچیدگی زمانی $O(N^3)$ استفاده کنیم.
باید توجه داشت که اگر در مرحله‌ای، در ستون فعلی هیچ درایه غیرصفری پیدا نکنیم، الگوریتم باید متوقف شود و مقدار 0 را برگرداند.
پیاده‌سازی¶
const double EPS = 1E-9;
int n;
vector < vector<double> > a (n, vector<double> (n));
double det = 1;
for (int i=0; i<n; ++i) {
int k = i;
for (int j=i+1; j<n; ++j)
if (abs (a[j][i]) > abs (a[k][i]))
k = j;
if (abs (a[k][i]) < EPS) {
det = 0;
break;
}
swap (a[i], a[k]);
if (i != k)
det = -det;
det *= a[i][i];
for (int j=i+1; j<n; ++j)
a[i][j] /= a[i][i];
for (int j=0; j<n; ++j)
if (j != i && abs (a[j][i]) > EPS)
for (int k=i+1; k<n; ++k)
a[j][k] -= a[i][k] * a[j][i];
}
cout << det;