Jednym z ważnych algorytmów mocno polegających na odróżnieniu liczby zerowej od niezerowej jest algorytm eliminacji Gaussa tj sprowadzania macierzy do postaci schodkowej całkowicie zredukowanej. Aby właściwie zaimplementować ten algorytm w arytmetyce zmiennoprzecinkowej należy go odpowiednio zmodyfikować
1 Przed obliczeniami należy macierz znormalizować tj obliczyć największy co do wartości bezwzględnej element macierzy i podzielić przez niego wszystkie elementy macierzy. (otrzymujemy w ten sposób macierz o wartościach z przedziału od -1 do 1).
2 W zwykłym algorytmie Gaussa używamy dowolnego elementu niezerowego kolumny do uzyskania wartości 1 i wyzerowania reszty kolumny. Aby uzyskać algorytm numerycznie stabilny, należy zastąpić pytanie o zerowanie się elementów kolumny porównaniem z epsilonem maszynowym (mała w porównaniu z 1.0 liczbą dodatnia. Zamiast brać pierwszy lepszy element niezerowy powinniśmy wybrać wiersz zawierający w danej kolumnie element największy co do wartości bezwzględnej (oczywiście pod warunkiem, że kolumna zawiera choćby jeden element większy od epsilon - w przeciwnym wypadku kolumnę należy uznać za zerową).
3 Przykład. Załóżmy, że macierz (a właściwie pierwsza kolumna macierzy) ma postać
4 0.125 * *
5 -0.5 * *
6 0.25 * *
7 W przypadku zwykłego algorytmu użylibyśmy pierwszego wiersza do otrzymania 1.0 na pozycji (1,1) (w notacji algebraicznej) i wyzerowania pozostałych elementów pierwszej kolumny. W przypadku omawianej wersji należałoby najpierw przestawić wiersze pierwszy i drugi (gdyż -0.5 jest największą co do wartości bezwzględnej liczbą w pierwszej kolumnie). Analogicznie należy postępować w następnych kolumnach.
8 Przy drukowaniu postaci zredukowanej zastąp elementy macierzy wynikowej mniejsze od epsilona zerami.
W załączonym pliku zdefiniowano pewną macierz. Dopisz do tego pliku kod odpowiedzialny za eliminację Gaussa w/g przedstawionej powyżej wersji algorytmu. Pamiętaj, że kod powinien być uniwersalny, niezależny od konkretnej macierzy. Przetestuj kod na przykładach różnych macierzy (różnych funkcji zapełniających macierz liczbami.
**Napisałem trochę kodu, konkretnie od komentarza /tu powinien zacząc się algorytm eliminacji/ przed tym komentarzem program jest dany do zadania. Kompletnie nie wiem co dalej zrobić, proszę o jakieś podpowiedzi. **
#include<stdio.h>
#include<math.h>
/* dyrektywa preprocesora: M i N zostaną przed kompilacją zastąpione odpowiednimi napisami*/
#define M 50
#define N 100
const double eps = 1e-12; /* stała przybliżenia zera*/
int main(void){
float a[M][N], maksimum, bufor;
int m,n,i,j,w;
/*użytkownik podaje prawdziwe rozmiary macierzy*/
printf("podal liczbe wierszy macierzy <= %d\n", M);
scanf("%d", &m);
printf("podal liczbe wierszy macierzy <= %d\n", N);
scanf("%d", &n);
/*nadanie początkowych wartosci macierzy*/
for( i=0; i<m; i++)
for( j=0; j<n; j++ )
a[i][j] = i-j;
maksimum = fabsf(a[0][0]);
w=0;
/*tu powinien zacząc się algorytm eliminacji*/
/*szukania wartości bewzględnej największego elementu*/
for( i=0; i<m; i++)
for( j=0; j<n; j++ )
if(fabsf(a[i][j])>fabsf(maksimum))
maksimum = a[i][j];
/*normalizacja macierzy*/
for( i=0; i<m; i++)
for( j=0; j<n; j++)
{
a[i][j] = a[i][j]/maksimum;
}
/*szukanie elementu największego w kolumnie*/
for( j=0; j<n; j++)
{
for( i=0; i<m; i++)
{
if(fabsf(a[i][j])>fabsf(maksimum))
{
maksimum = a[i][j];
w=i;
}
}
/*zamiana wierszy*/
for(i=0; i<n; i++)
{
bufor = a[0][i];
a[0][i] = a[w][i];
a[w][i] = bufor;
}
}
/*wydruk zredukowanej macierzy*/
return 0;
}