Матрицын тодорхойлогчийг Гауссын аргаар бодох¶
Бодлого: $N \times N$ хэмжээтэй $A$ матриц өгөгдсөн. Түүний тодорхойлогчийг бод.
Алгоритм¶
Бид шугаман тэгшитгэлийн системийг бодох Гауссын арга-ын санааг ашиглана.
Бид шугаман тэгшитгэлийн системийг бодохтой ижил алхмуудыг гүйцэтгэх бөгөөд зөвхөн одоогийн мөрийг $a_{ij}$-д хуваахыг оруулахгүй. Эдгээр үйлдэл нь матрицын тодорхойлогчийн абсолют утгыг өөрчлөхгүй. Гэвч бид матрицын хоёр мөрийг сольж солиход тодорхойлогчийн тэмдэг өөрчлөгдөж болно.
Матриц дээр Гауссыг хэрэглэсний дараа бид диагональ матриц олж авах ба түүний тодорхойлогч нь зүгээр л диагональ дээрх элементүүдийн үржвэр юм. Тэмдгийг өмнө дурдсанчлан сольсон мөрийн тоогоор тодорхойлж болно (сондгой бол тодорхойлогчийн тэмдгийг эсрэгээр нь болгоно). Ингэснээр бид Гауссын алгоритмыг ашиглан матрицын тодорхойлогчийг $O(N^3)$ complexity-тэйгээр тооцоолж болно.
Ямар нэг цэгт бид одоогийн баганад тэг биш нүд олохгүй бол алгоритм зогсож 0 буцаах ёстойг тэмдэглэх нь зүйтэй.
Implementation¶
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;