Procedura licząca wyznacznik macierzy trójdiagonalnej
Mariusz:
Użyję tutaj Pascala bo ma on tak czytelny kod że znając podstawy angielskiego
będziecie wiedzieli o co w nim chodzi nawet nie znając się na programowaniu
type
TArray = array of Double;
procedure MyPolynomial(deg:integer;var coeff:TArray);
var x,y:TArray;
j,k:integer;
p,q,r,xj: double;
begin
SetLength(x,deg+1);
SetLength(y,deg+1) ;
for k := 0 to deg do
x[k] := (k+1)/(deg + 1);
for k := 0 to deg do
begin
q := 1;
r := 0;
p := 1;
for j := deg downto 1 do
begin
q := (2 − 1/j) * x[k] − r/q;
r := 1 − 1/j;
p := p * q
end;
y[k] := p
end;
for k := 1 to deg do
for j := deg downto k do
y[j] := (y[j] − y[j−1])/(x[j] − x[j − k]);
coeff[deg] := y[deg];
for j := deg − 1 downto 0 do
begin
xj := x[j];
coeff[j] := y[j];
for k := j to deg − 1 do
coeff[k] := coeff[k] − xj * coeff[k + 1]
end;
end;
Procedura ma obliczać wyznacznik macierzy trójdiagonalnej dla której
* elementy na głównej przekątnej są równe (2 − 1/j)*x , gdzie j to numer wiersza
* elementy pod główną przekątną są równe 1 − 1/j , gdzie j to numer wiersza
* elementy nad główną przekątną są jedynkami
x należy do przedziału <−1;1>
Tutaj próbowałem operacjami elementarnymi sprowadzić macierz do macierzy dolnotrójkątnej
Problemem jest to że może wystąpić dzielenie przez zero przy czym wystąpienie
dzielenia przez zero nie jest równoznaczne z tym że wyznacznik jest równy zero
To jest macierz trójdiagonalna więc obliczenie wyznacznika nie powinno zająć
więcej niż O(n) operacji
Ponieważ elementami na głównej przekątnej są x więc wyznacznik będzie wielomianem
zatem potrzebujemy n+1 próbek gdzie nxn to wymiar macierzy
Zadanie jest takie
Zmodyfikować kod procedury aby liczyła poprawnie wyznacznik
w przypadku gdy teraz występuje dzielenie przez zero
16 wrz 02:29
wredulus_pospolitus:
Jako, że '0' może wystąpić JEDYNIE na głównej przekątnej, sprawa jest stosunkowo prosta i
obejdzie się bez 'paskudnych' przypadków. Wprowadzasz także wartość pomocniczą: korekta = 1
Wprowadzasz dwa warunki:
1. Jeżeli '0' występuje na an,n to zamieniasz n'ty wiersz/kolumnę (sam wybierz które) z
pierwszym oraz korekta = (−1)n+1
2. Jeżeli w trakcie działania procedury natrafiasz na '0' w pozycji ak,k zamieniasz tenże
wiersz/kolumnę (pamiętaj że musisz być konsekwentny − zamieniamy albo TYLKO wiersze albo TYLKO
kolumny) z wierszem/kolumną 'k+1' oraz korekta = −korekta
Bez wprowadzenia zmiennej korekta w wyniku otrzymasz wyznacznik z dokładnością co do znaku.
16 wrz 08:44
wredulus_pospolitus:
Poprawka −−− Jeden warunek w pętli zrobiony na samym początku zamieniający wiersz/kolumnę z
następnym.
Jeżeli '0' jest w an,n wtedy ostatni wiersz/kolumnę zamieniamy z pierwszym (albo
przedostatnim jeżeli tak wolisz, wtedy korekta = −korekta).
I oczywiście na końcu wartość wyznacznika przemnażasz przez wartość 'korekta'
16 wrz 08:53
Mariusz:
Ponieważ mamy macierz trójdiagonalną a elementy macierzy są wypisywane wg wzór to
to udało mi się zapisać macierz w dwóch zmiennych
W zmiennej q przechowywany jest bieżący element na głównej przekątnej
W zmiennej r przechowywany jest bieżący element poniżej głównej przekątnej
W zmiennej p przechowywana jest bieżąca wartość iloczynu elementów na głównej przekątnej
Problemem jest to że chciałbym wyeliminować możliwość dzielenia przez zero
bez zwiększania złożoności czasowej oraz pamięciowej
Jak zrealizować zamianę wierszy bądź kolumn bez pamiętania macierzy
16 wrz 20:32
Mariusz:
Tutaj chyba lepiej byłoby dodać wiersz bądź kolumnę
ale jeszcze nie sprawdzałem czy to zadziała
16 wrz 20:48
wredulus_pospolitus:
Wybacz ... moja umiejętność czytania kodów jest mocno zakurzona.
Żebyśmy się zrozumieli −−−>
1. Próbujesz policzyć wyznacznik z macierzy bez tworzenia (i zapisywania w pamięci) tejże
macierzy.
2. Wartości x[k] jest zawsze dodatnia, a przecież ma reprezentować x ∊ < −1 ; 1 >. Czy ten 'x'
niemiał być losowy (zakładałem, że oto Ci chodzi, bo tylko wtedy możemy mieć x=0 i pojawi się
na diagonalnej aj,j = 0)? I jeżeli miał być losowy, to ma być losowy dla każdego elementu
na diagonalnej czy tylko raz go wybierasz?
3. Jedyne dzielenia w kodzie masz w :
a. x[k] ale deg+1 jest liczbą dodatnią
b. q gdy r/g = (2 − 1/j)*x[k], to w następnym kroku masz dzielenie przez 0
c. y[j] ale x[j] ≠ x[j − k]
Więc jedynie w sytuacji (b) może wyskoczyć dzielenie przez 0, ale przy tak tworzonych x[k] czy
to w ogóle jest możliwe? (To by trzeba było sprawdzić)
16 wrz 22:23
wredulus_pospolitus:
*miało być 'gdy r/
q = ...'
16 wrz 22:26
Mariusz:
Ad 1
Tak
Ogólnie aby policzyć wyznacznik z macierzy trójdiagonalnej na ogół potrzebujemy
O(n) pamięci ale jeżeli wiemy że istnieje wzór na elementy to potrzebną pamięć
możemy zredukować do O(1)
Ad 2
Potrzebowałem n+1 wartości x i tak je dobrałem aby były liczbami dodatnimi
ale wartości dla x można zmienić byleby należały do przedziału < −1 ; 1>
Wybór x mógłby być losowy ale wtedy trzeba by było zadbać o to aby wartości się nie powtarzały
Co do wyboru elementu głównego to popsuje on nam strukturę macierzy
tzn po dokonaniu wyboru elementu głównego możemy nie dostać macierzy trójdiagonalnej
18 wrz 04:41