On 9 Wrz, 00:58, Mariusz Marszałkowski <m...@g...com> wrote:
> On 8 Wrz, 23:15, bartekltg <b...@g...com> wrote:> On 8 Wrz, 19:35, Mariusz
Marszałkowski <m...@g...com> wrote:
> > > Obawiam się że nie można tego faktu z istotnym zyskiem
> > > wykorzystać, przynajmniej mi nic istotnego nie przychodzi
> > > do głowy. Macierz układu równań już nie będzie miała zer.
>
> > Jak to nie.
>
> To mówimy o jakimś innym układzie :) W takim razie z
> Twoich słów wynika że jest szybsza metoda od tej którą
> to zadanie zawsze liczyłem. Na razie nic o niej nie wiem.

Mówiłem to ostatnio, mialem to raz jeszcze napisać
w odpowiedzi ktorą powolitku pisze dla drugiej odnogi wątku,
ale wspomne o tym teraz: moze jednak zatrudnijcie jakiegos
matematyka/numeryka.

> Na stronie 864 mam " W praktyce równanie normalne
> rozwiązujemy mnożąc y przez A^t, a następnie znajdując
> rozkład LU macierzy A^t x A" - wydaje mi się że zawsze
> tak to robiłem.

Cormen nie jest podręcznikiem do numerkow;)

Ta metoda nazywa się rownaniem normalnym i ma
pewne wady. Są inne metody. [chociaz ostatnio
ta polecalem, bo ladnie pasowala do 'poprzedniego'
problemu].


> Nie rozumiem o czym mówicie.

:(

> Ja to widzę tak, że elementy macierzy A równania Ax=b
> w postaci normalnej będą się składały z odpowiednich
> sum  iloczynów, zsumują się do dużych wartości.

Nazywasz dwie macierze ta samną literką? To sie nie dogadamy;)
Nazwijmy B=A^t*A.

B rzeczywiscie jest gęsta, ale A jest rzadka.

Dla przypomnienia, zagadnienie jest n*N n>N (n=1000N)
N=K*M.
A ma n*K niezerowych elementow.

Nie kazda metoda zminimalizowania norm(Ax-b)
opiera sie na operacjach na maczierzy B.

Jest druga 'szkolna' metoda, przez rozklad QR.

A=QR
R=[R_1; 0]
liczymy Q^t *b, powstaly wektor obcianmy
no N wspolrzednych (wektor w) i rozwiazujemy
uklad trojkatny

R_1 x = w.

Jako zalazek do poszukiwan:
http://en.wikipedia.org/wiki/Numerical_methods_for_l
inear_least_squares#Orthogonal_decomposition_methods


QR jest czasem lepsze, bo "operujemy na A" a nie na "A kwadarat".
Uwarunkowanie!
No, ta metoda (ani SVD) do tego zagadnienia tez sie nie specjalnie nie
nadadza.


Zeby nie mnozyc bytów:

On 6 Wrz, 18:26, Mariusz Marszałkowski <m...@g...com> wrote:
> On 6 Wrz, 17:33, bartekltg <b...@g...com> wrote:> Ile jest wektorów?
powiedzmy n >> N.

> A jeśli N jest równe milion? :)

Hmm, to ciezko bedzie:) Skąd wezmiesz 8 pata(10^15) bajtow dysku:)


> po roku mogę ich mieć nawet cały dysk.
>
> Oryginalny wektor ma niecałe 100 wartości ze małego zbioru
> liczb całkowitych, np. <-7,+7>. Wektor ten będzie mapowany
> przy pomocy nieliniowej funkcji w dużo większy wektor
> zero-jedynkowy o takich własnościach jak napisałem - tylko
> jedna jedynka w każdej części.

Dosc interesujace, co moze sie za tym kryć;)
Pewnie znowu nie opowiesz, to moze powtorze to co
ostatnio napisalem: zatrudnijcie jakiegos matematyka/numeryka;-)
U mnie jak potrzebny do powaznej rzeczy elektronik,
to sie bierze elektronika (jak do malo powaznej, to studenta,
co sie nie zawsze dobrze konczy;).

> Sprawdziłem algorytm zachłanny na losowych zerach i jedynkach
> ( z zachowaniem jednej jedynki w każdej części ). Na kilku zbiorach
> dał rozwiązanie gorsze od optymalnego o 0.5%. Zrobiłem mniej/więcej
> tak:
> 1) Wszystkie współczynniki a_i <-- 0
> 2) j <--0
> 2) Rozwiąż układ tylko dla grupy j
> 3) Odejmij do żądanej wartości F(x) -= suma a_i * v_i : j*ilosc_grup
> <= i <= (j+1)*ilosc_grup
> 4) skocz 2 jeśli j < ilosc_grup.

A nie działa to dlagtego, ze jest ladnie losowo i na kazdą
z grup przypada 'tele samo wektora'?

Są algorytmy 'iteracyjne', w tym 'randomizowane'.
mozna pojsc w tym kierunku, zwlaszcza, ze dane
naplywają stopniowo.

Na szybko. Mamy Ax-b=r
Popatrzmy na losową składową wektora wspołczynnikow,
x_i. Sprobujmy ja poprawić. Niech korekta w=(0,0..1..0,0).

A(x+c*w)-b=r-c*Aw
r-c*v; v=Aw; c-liczb rzeczywista.

powstalo 'jednowymiarowe' zagadnienie najmniejszych kwadratow:)
c=<v,r>/<v,v>.

Losujemy kolejny element do poprawki i tak w kolko.
To algorytm z naswiskiem, uzywany nawet, ale nie pamietam
namiarow.

Mozna 'na raz' optymalizować wiecej niz jeden skladnik
wektora wspolczynnikow x, ale na oko nie jest to oplacalne.

Uzywamy wlasciwie tylko mnozenia przez rzadką A
(musisz ja zapisać rozsadnie, aby nie iterowc po zerach).
ilosc potrzebnych interacji to juz inna sprawa, jesli masz
gigabajty, to nie spodziewaj sie szybko wyniku;)

Powinno sie wygoglac bardziej zaawansowane tego typu metody,
poszukaj po least squares, sparse, moze cos o iterowaniu i wariacje.


Zupelnie inna metoda. Reszta r=Ax-b spełnia dla optymalnego x
A^t * r =0.
Uklad rownan mozemy zapisać lacznie jako
[ I A] [x]
[ A^t 0 ] [r]
=
[b]
[0]

I -macierz jednostkowa. Zagadnienie jest znacznie wieksze,
ale macierz jest nadal rzadka (rzedu n*(2*K+1) elementow ).
Jesli K jest małe, jakaś sprytniejsza metoda iteracyjna rozwiazywania
rownan liniowych da wynik szybko (pewnei precondicioner by sie
przydal)

Zaletą jest, ze (w wersji bez prec.) nie trzymamy w pamieci zadnej
macierzy,
tylko iterowany wektor (rozmiar n+N). A mnozenie, jesli odpowqiednio
zapiszesz swoją macierz (wektory z pomiarow), zajmuje tylko tyle
czasu,
ile jest niezerowych elementow.

Bardzo mozliwe, ze w tym przypadku da sie zastosowac albo wymyslic
jakis prosty (aby dal sie w biegu liczyc, byl oparty na A etc, aby nie
trzymac
duzej macierzy w pamieci) precondiconer, przez co mozemy dostać
przyzwoite
rozwiązania przy niewielkiej ilosci iteracji. Ale to juz na dłuzsze
głowkowanie.
Zaletą metod iteracyjnych bedize tez to, ze jesli dojdą nowe wektory
(skladniki A)
to juz mamy obliczony wczesniej przyzwoity punkt startowy.

Przy okazji, Y. Saad na swojej stronie wystawił wielka ksiązke do
matod iteracyjnych:)



pozdrawiam
bartekltg