matematykaszkolna.pl
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 = ...' emotka
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