برنامه ی معکوس ماتریس n*n

[narnia-m]

سلام.برنامه ی معکوس ماتریس n*n رو کسی داره بهم بده.ممنون می شم

 

[secret_f]

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



همانطور که میدونید، دترمینان(determinant) با استفاده از همسازه ها بدست میاد که خودش با استفاده از ماترس کهاد(minor) بدست میاد. ماتریس کهاد هم با حذف یک سطر و ستون از ماتریس اصلی بدست میاد. ماتریس ها رو با یک آرایه دوبعدی نمایش میدیم، پس باید برای کهاد، از یک ماتریس دیگه که از ماتریس اصلی یک سطر و ستون کمتر داره استفاده کنیم.
یک جاش که یکم کار میخواد پر کردن ماتریس کهاد هست که خیلی هم سادست، میشه اینطور عمل کرد: فرض کنید ماتریس کهاد رو میخوایم سطر به سطر پر کنیم، وقتی به سطری میرسیم که باید از ماتریس اصلی حذف بشه پس از اون سطر رد میشیم. در هر سطر هم وقتی به ستون حذفی میرسیم از اون درایه صرف نظر میکنیم، همین!

در کد زیر تابع Determinant یک آرایه دو بعدی (a) رو میگیره که n*n و نوع اون T هست و مقدار برگشتیش هم دترمینان ماتریس a هست. استفاده از template(قالب) در ++C به کلی شدن تابع کمک میکنه، الان تابع ما میتونه آرایه هایی با هر نوعی رو بگیره (مثلاً اینجا انواعی مثل int و double مطرح هستند)، اما برای آرایه های دو بعدی یک کمک ویژه هم میکنه؛ میدونید که در ++C نمیشه بعد دوم رو مشخص نکرد، اما با استفاده از قالب میشه n رو بعنوان یک عدد فرض کرد که همون اندازه بعد دوم هست و عدد ثابتی برای بعد دوم مشخص نکرد و بعد در تابع هم استفاده کرد، پس نیازی به گرفتن اندازه ماتریس در یک پارامتر اضافه نیست (مزیتی دیگر!). متغیر det در آخر تابع مقدار دترمینان رو در خودش خواهد داشت.

درون تابع چندین حالت برای n تست میشه که اصل قضیه آخرین else هست که برای n های بزرگتر از 2 هست و بحث کهاد و همسازه ها مطرح میشه. ما باید نسبت به یک سطر یا ستونی ماتریس رو بسط بدیم، در اینجا نسبت به سطر اول بسط میدیم. for اول این else برای محاسبه تمام همسازه هاست. با j1 روی همه درایه های سطر اول حرکت میکنیم و بعد در for دوم و سوم (که برای محاسبه کهاد هر همسازه هست) درایه های کهاد رو یکی یکی از ماتریس اصلی بیرون میکشیم (ماتریس m برای کهاد هست). i از یک شروع میشه چون نسبت به سطر اول داریم بسط میدیم و سطر اول در هیچکدوم از کهادها در نظر گرفته نمیشه (اینم مزیت بسط روی سطر اول!). j2 هم برای مشخص کردن ستونی از کهاد هست که داریم پر میکنیم. در for سوم روی تمام ستونهاحرکت میکنیم و هرجا به ستونی که نباید در کهاد باشه میرسیم با continue از اون ستون رد میشیم و به j2 هم اضافه نمیشه. اینطوری در آخر هر تکرار for اول، کهاد همسازه مربوط رو در m خواهیم داشت، سپس همسازه رو حساب میکنیم و به det اضافه میکنیم. دو تا یکی که به j1 اضافه میشه یکی برای این هست که ستون های آرایه از صفر شروع میشن اما برای ماتریس ها در ریاضی از یک هستند و 1 دیگر همان شماره سطری است که داریم نسبت به آن بست میدیم.


کد قالب بندی شده:

/*

*/
template <typename T, int n>
T Determinant(T a[][n])
{
int i,j,j1,j2;
T det = 0;
T m[(n>1)?(n-1):1][(n>1)?(n-1):1];

if (n < 1)
{ /* Error */

}
else if (n == 1)
{ /* Shouldn't get used */
det = a[0][0];
}
else if (n == 2)
{
det = a[0][0] * a[1][1] - a[1][0] * a[0][1];
}
else
{
det = 0;
for (j1=0;j1<n;j1++)
{
for (i=1;i<n;i++)
{
j2 = 0;
for (j=0;j<n;j++)
{
if (j == j1)
continue;
m[i-1][j2] = a[j];
j2++;
}
}
det += (int)pow(-1.0,1+j1+1) * a[0][j1] * Determinant(m);
}
}
return(det);
}



محاسبه معکوس

برای محاسبه معکوس ماتریس باید ماتریس الحاقی اون رو بر دترمینانش تقسیم کنیم (که دترمینان صفر نباید باشه). دترمینان رو که از برگشتی تابع Determinant میگیریم، میمونه ماتریس الحاقی؛ تابع CoFactor ماتریس همسازه رو در b بهمون میده بعد باید b رو ترانهاده کنیم تا ماتریس الحاقی بشه؛ تابع Transpose ماتریس a رو ترانهاده میکنه (عملکردش ساده هست و نیاز به توضیح نداره).

توضیح تابع CoFactor : پارامتر b برای ماتریس همسازه هست و آرایه c برای کهاد (چون همیشه یک سطر و ستون کمتر داره ابعادش n-1 هست). دو for اول برای حرکت روی تمام درایه های ماتریس هست تا هر بار همسازه یکی از اون ها رو حساب کنیم و در درایه متناظر از b بریزیم. دوتا for درونی هم برای حساب کردن کهاد هستند.

پس حالا دیگه با توانایی محاسبه دترمینان و ماتریس همسازه (و ترانهاده اون)، نوشتن تابع معکوس (Reverse) ساده خواهد بود. این تابع ماتریس معکوس a رو در b تحویل میده. تنها نکته اینکه چون درایه های b حاصل یک تقسیم هستن ممکنه که اعشاری بشن، پس نوع b با a حتماً یکسان نیست و چون میتونه مختلف باشه (float و double و...) پس نوع کلی T1 رو براش در نظر میگیریم.


کد قالب بندی شده:
include ها : <cmath> برای ()pow لازم است
/*

*/ Find the cofactor matrix of a square matrix
template <typename T, typename T1, int n>
void CoFactor(T a[][n],T1 b[][n])
{
int i,j,ii,jj,i1,j1;
T det;
T c[n-1][n-1];

for (j=0;j<n;j++)
{
for (i=0;i<n;i++)
{

/* Form the adjoint a_ij */
i1 = 0;
for (ii=0;ii<n;ii++)
{
if (ii == i)
continue;
j1 = 0;
for (jj=0;jj<n;jj++)
{
if (jj == j)
continue;
c[i1][j1] = a[ii][jj];
j1++;
}
i1++;
}

/* Calculate the determinate */
det = Determinant(c);

/* Fill in the elements of the cofactor */
b[j] = (int)pow(-1.0,i+j+2) * det;
}
}
}

/*
Transpose of a square matrix, do it in place
*/
template <typename T, int n>
void Transpose(T a[][n])
{
int i,j;
T tmp;

for (i=1;i<n;i++) {
for (j=0;j<i;j++) {
tmp = a[j];
a[j] = a[j];
a[j] = tmp;
}
}
}

/*
Reverse of matrix 'a' in 'b'
*/
template <typename T, typename T1, int n>
void Reverse(T a[][n], T1 b[][n])
{
T det = Determinant(a);
CoFactor(a,b);
Transpose(b);

int i,j;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
b[j] = b[j]/det;
}



یک نمونه استفاده از تابع Reverse در کد زیر آمده :

کد قالب بندی شده:


int a[3][3] = {{3,1,2},{-2,5,4},{1,3,6}};
Reverse(a,b);

 

[narnia-m]

خیلی ممنون از توضیحتون