C++ - Macierz odwrotna, wyznacznik

Tomek_B
Użytkownik
Użytkownik
Posty: 27
Rejestracja: 15 sie 2008, o 14:42
Płeć: Mężczyzna
Lokalizacja: z Polski
Pomógł: 1 raz

C++ - Macierz odwrotna, wyznacznik

Post autor: Tomek_B »

Witam, mam taki kawałek kodu :

Kod: Zaznacz cały

int wiersze;
int kolumny;
int i,j;
int zakres;
int tablica[15][15]; //maksymalny rozmiar macierzy
int macierz_transponowana[15][15];
int macierz_a[15][15];
int macierz_b[15][15];
long int macierz_c[15][15];
long int element_1(int i, int j);//dodawanie
long int element_2(int i, int j);//odejmowanie
long int element_3(int i, int j);//mnozenie
long int element_4(int i, int j);//transpozycja

void generator_macierzy ()
{
     printf ("
GENERUJ LOSOWA MACIERZ
");
     printf ("Podaj liczbe wierszy : ");
     scanf ("%d",&wiersze);
     printf ("Podaj liczbe kolumn  : ");
     scanf ("%d",&kolumny);
     printf ("Podaj zakres losowanych liczb : ");
     scanf ("%d",&zakres);
     //randomize ();
     //randomize ();
     for (i=0;i<wiersze;i++)
         {
         for (j=0;j<kolumny;j++)
             {
             tablica[i][j]=(rand ()%(zakres+1));
             }
         }
printf ("
WYGENEROWANA LOSOWO MACIERZ : 
");
for (i=0;i<wiersze;i++)
    {
    for (j=0;j<kolumny;j++)
        {
        printf ("%5d",tablica[i][j]);//cprintf
        }
    printf ("
");
    }
getch ();
}

void transpanowanie_macierzy ()
{
     printf ("
MACIERZ TRANSPONOWANA
");
     printf ("Podaj liczbe wierszy : ");
     scanf ("%i",&wiersze);
     printf ("Podaj liczbe kolumn  : ");
     scanf ("%i",&kolumny);
     for (i=0;i<wiersze;i++)
         {
         for (j=0;j<kolumny;j++)
             {
             printf ("Podaj element macierzy : %d %d
",i+1,j+1);
             scanf ("%d",&macierz_transponowana[i][j]);
             }
         }
             //wyswietl macierz
             printf ("
MACIERZ : 
");
             for (i=0;i<wiersze;i++)
                 {
                 for (j=0;j<kolumny;j++)
                     {
                     printf ("%5d",macierz_transponowana[i][j]);
                     }
                 printf ("
");
                 }
     getch ();
     //wyswietl macierz transponowana
     printf ("
MACIERZ TRANSPONOWANA : 
");
     for (i=0;i<wiersze;i++) 
         {
         for (j=0;j<kolumny;j++)
             {
             printf ("%5d",macierz_transponowana[j][i]);
             }
         printf ("
");
         }
getch ();
}

void generator_macierzy_transponowanej ()
{
     printf ("
GENERUJ LOSOWA MACIERZ
");
     printf ("Podaj liczbe wierszy : ");
     scanf ("%d",&wiersze);
     printf ("Podaj liczbe kolumn  : ");
     scanf ("%d",&kolumny);
     printf ("Podaj zakres losowanych liczb : ");
     scanf ("%d",&zakres);
     //randomize ();
     //randomize ();
     for (i=0;i<wiersze;i++)
         {
         for (j=0;j<kolumny;j++)
             {
             tablica[i][j]=(rand ()%(zakres+1));
             }
         }
printf ("
WYGENEROWANA LOSOWO MACIERZ : 
");
for (i=0;i<wiersze;i++)
    {
    for (j=0;j<kolumny;j++)
        {
        printf ("%5d",tablica[i][j]);//cprintf
        }
    printf ("
");
    }
    //wyswietl macierz wygenerowana macierz transponowana
    printf ("
MACIERZ TRANSPONOWANA
");
    for (i=0;i<wiersze;i++)
        {
        for (j=0;j<kolumny;j++)
            {
            printf ("%5d",tablica[j][i]);
            }
        printf ("
");
        }
getch ();
}
jak zrobić żeby można było policzyć z tych funkcji wyznacznik i macierz odwrotną.
Tzn funkcja generator - generuje macierz losową i z tej macierzy byłby policzony wyznacznik i macierz odwrotna, i podobnie funkcja transponuj i "generator transpozycji"?
Leogict
Użytkownik
Użytkownik
Posty: 40
Rejestracja: 21 mar 2008, o 20:01
Płeć: Mężczyzna
Podziękował: 14 razy

C++ - Macierz odwrotna, wyznacznik

Post autor: Leogict »

Musisz dokonać takich przekształceń, aby macierz pomnożona przez macierz odwrotną dała macierz jednostkową. Więc jeżeli mnożysz pierwszą macierz (którą chcesz odwrócić) przez drugą macierz i otrzymujesz macierz jednostkową, to ta druga macierz jest właśnie macierzą odwrotną do pierwszej.
Przykład z wiki:


http://upload.wikimedia.org/math/0/0/b/00b346588eab33a9bcea72cb9f09c92f.png

Inny sposób to sposób z "macierzą dołączoną", ale to jest wg mnie trudniejsze, bo trzeba liczyć wszystkie dopełnienia algebraiczne, minory, wyznacznik itp...

Co do wyznacznika - macierzy stopnia 2 - jest gotowy wzór (a11*a22-a21*a12), do macierzy stopnia 3 - masz metodę Sarrusa (dopisujesz z boku albo z dołu 2 wiersze lub kolumny i mnożysz po ukosie jak w stopniu 2), wyższe stopnie - metoda rozwinięć Laplace'a (też minory, dopełnienia algebraiczne i wyznaczniki).

Teraz tylko to przełożyć na C++ - ale to już Twoja głowa :)
spajder
Użytkownik
Użytkownik
Posty: 735
Rejestracja: 7 lis 2005, o 23:56
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 2 razy
Pomógł: 133 razy

C++ - Macierz odwrotna, wyznacznik

Post autor: spajder »

Wyznacznika nie liczy się tak (bo za dużo czasu to zajmuje - złożoność wykładnicza). Znajdź algorytm Gaussa - nadaje się zarówno do odwracania macierzy jak i znajdowania wyznacznika (tu wystarczy doprowadzić do macierzy schodkowej)
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6909
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

C++ - Macierz odwrotna, wyznacznik

Post autor: Mariusz M »

Zgadza się najlepiej zastosować eliminację Gaussa
albo metodę rozkładu LU=PA

Aby odwrócić macierz metodą LU trzeba rozwiązać n układów równań
liniowych gdzie wyrazami wolnymi są kolejne kolumny macierzy jednostkowej
Kolumny układamy zgodnie z macierzą permutacji
Złożoność tej metody jest porównywalna do metody eliminacji Gaussa
ponieważ rozkładu LU=PA dokonujemy tylko raz

Metoda rozkładu LU nadaje się także do obliczania wyznacznika
ponieważ zgodnie z twierdzeniem Cauchy'ego \(\displaystyle{ \det{A \cdot B}=\det{A}\cdot \det{B}}\)
Macierz permutacji pozwala ustalić znak wyznacznika

Rozkładu można dokonać za pomocą

1. Metody Doolitle
Polega ona na rozwiązaniu układu równań który można otrzymać ze wzoru
na mnożenie macierzy (Naiwne podejście do problemu rozkładu macierzy)
2.Metoda eliminacji Gaussa

Rozkład LU jest zaimplementowany w książce
"Numerical recipes in C"

Kod: Zaznacz cały

#include <math.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define TINY 1.0e-20; //A small number.

void ludcmp(float **a, int n, int *indx, float *d);
void lubksb(float **a, int n, int *indx, float b[]);

int main(){
return 0;
}

void ludcmp(float **a, int n, int *indx, float *d)
/*Given a matrix a[1..n][1..n], this routine replaces it by the LU decomposition of a rowwise
permutation of itself. a and n are input. a is output, arranged as in equation (2.3.14) above;
indx[1..n] is an output vector that records the row permutation eected by the partial
pivoting; d is output as 1 depending on whether the number of row interchanges was even
or odd, respectively. This routine is used in combination with lubksb to solve linear equations
or invert a matrix.*/
{
int i,imax,j,k;
float big,dum,sum,temp;
float *vv; //vv stores the implicit scaling of each row.
vv=(float*)malloc((n+1)*sizeof(float));
*d=1.0; //No row interchanges yet.
for (i=1;i<=n;i++) { //Loop over rows to get the implicit scaling informa
big=0.0; //tion.
for (j=1;j<=n;j++)
if ((temp=fabs(a[i][j])) > big) big=temp;
if (big == 0.0) printf("Singular matrix in routine ludcmp\n");
//No nonzero largest element.
vv[i]=1.0/big; //Save the scaling.
}
for (j=1;j<=n;j++) { //This is the loop over columns of Crout's method.
for (i=1;i<j;i++) { //This is equation (2.3.12) except for i = j.
sum=a[i][j];
for (k=1;k<i;k++) sum -= a[i][k]*a[k][j];
a[i][j]=sum;
}
big=0.0; //Initialize for the search for largest pivot element.
for (i=j;i<=n;i++) { //This is i = j of equation (2.3.12) and i = j+1 : ::N
sum=a[i][j]; //of equation (2.3.13).
for (k=1;k<j;k++)
sum -= a[i][k]*a[k][j];
a[i][j]=sum;
if ( (dum=vv[i]*fabs(sum)) >= big) {
//Is the gure of merit for the pivot better than the best so far?
big=dum;
imax=i;
}
}
if (j != imax) { //Do we need to interchange rows?
for (k=1;k<=n;k++) { //Yes, do so...
dum=a[imax][k];
a[imax][k]=a[j][k];
a[j][k]=dum;
}
*d = -(*d); //...and change the parity of d.
vv[imax]=vv[j]; //Also interchange the scale factor.
}
indx[j]=imax;
if (a[j][j] == 0.0) a[j][j]=TINY;
/*If the pivot element is zero the matrix is singular (at least to the precision of the
algorithm). For some applications on singular matrices, it is desirable to substitute
TINY for zero.*/
if (j != n) { //Now, nally, divide by the pivot element.
dum=1.0/(a[j][j]);
for (i=j+1;i<=n;i++) a[i][j] *= dum;
}
} //Go back for the next column in the reduction.
free(vv);
}

void lubksb(float **a, int n, int *indx, float b[])
/*Solves the set of n linear equations AX = B. Here a[1..n][1..n] is input, not as the matrix
A but rather as its LU decomposition, determined by the routine ludcmp. indx[1..n] is input
as the permutation vector returned by ludcmp. b[1..n] is input as the right-hand side vector
B, and returns with the solution vector X. a, n, and indx are not modied by this routine
and can be left in place for successive calls with dierent right-hand sides b. This routine takes
into account the possibility that b will begin with many zero elements, so it is ecient for use
in matrix inversion.*/
{
int i,ii=0,ip,j;
float sum;
for (i=1;i<=n;i++) { /*When ii is set to a positive value, it will become the
index of the rst nonvanishing element of b. Wenow
do the forward substitution, equation (2.3.6). The
only new wrinkle is to unscramble the permutation
as we go.*/
ip=indx[i];
sum=b[ip];
b[ip]=b[i];
if (ii)
for (j=ii;j<=i-1;j++) sum -= a[i][j]*b[j];
else if (sum) ii=i; //A nonzero element was encountered, so from now on we will have to 
b[i]=sum; //do the sums in the loop above.
}
for (i=n;i>=1;i--) { //Now we do the backsubstitution, equation (2.3.7).
sum=b[i];
for (j=i+1;j<=n;j++) sum -= a[i][j]*b[j];
b[i]=sum/a[i][i]; //Store a component of the solution vector X.
} //All done!
}


//To calculate determinant you have to insert this line
// for(i=1;i<=n;i++) (*d)*=a[i][i] in ludcmp function 

//To invert a matrix you have to insrt this block 

/*
float **a,**y,d,*col;
int i,j,*indx;
...
ludcmp(a,N,indx,&d); Decompose the matrix just once.
for(j=1;j<=N;j++) { Find inverse by columns.
for(i=1;i<=N;i++) col[i]=0.0;
col[j]=1.0;
lubksb(a,N,indx,col);
for(i=1;i<=N;i++) y[i][j]=col[i];
}
*/
ODPOWIEDZ