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

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 a_n,n to zamieniasz n'ty wiersz/kolumnę (sam wybierz które) z pierwszym oraz korekta = (−1)ⁿ⁺¹ 2. Jeżeli w trakcie działania procedury natrafiasz na '0' w pozycji a_k,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.

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 a_n,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'

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

Mariusz: Tutaj chyba lepiej byłoby dodać wiersz bądź kolumnę ale jeszcze nie sprawdzałem czy to zadziała

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 a_j,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ć)

wredulus_pospolitus: *miało być 'gdy r/q = ...'

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