Witam...
Poszukuje algorytmu do rozwiązania równania liniowego...
Niestety moje równanie ma 2 tys równań więc potrzebuje naprawdę baaardzo szybkiego algorytmu...
Może ktoś by mnie naprowadził na takie coś...
Metoda Doolittle'a nie wchodzi w rachubę (za wolna). Robiłem także metodą gauss'a (tą w której dodajemy macierz jednostkową )
jednak też chodzi jakoś wolniutko...
Może ktoś z was ma doświadczenie w tej dziedzinie... :)
A jaka to jest macierz? Pełna? Rzadka? Może twoje implementacje algorytmów są za wolne a nie metody? Korzystasz z GSL czy pisałes to sam?
macierz jest rzadka. Na początku napisałem kilka metod sam ale były srtasznie wolne...później znalazłem przykład w internecie który przerobiłem tak żeby pasował do mojego zadania... Ale to i tak za mało :/
używam tylko tych elementów macierzy (1- używane , 0- nie )
[1 1 0 0 0 0 0 0]
[1 1 1 0 0 0 0 0]
[0 1 1 1 0 0 0 0]
[0 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0]
[0 0 0 0 1 1 1 0]
[0 0 0 0 0 1 1 1]
[0 0 0 0 0 0 1 1]
z czego przekątne są faktycznie jedynkami (w moim zadaniu):)
Znaczy się masz macierz trójprzekątniową z samymi 1 na przekątnych i liczysz to zwykłym gaussem albo LU? o_O Zwariowałeś?
Najprościej będzie wykorzystać gaussa dla takiej macierzy. Zamiast liczyć gaussa dla całej macierzy to rozpisz sobie na kartce jak wygląda to realnie dla takiej macierzy. Gwarantuje że będzie znacznie szybciej ;)
Gdybys miał macierz rzadką, ale nie tak trywialną, to mozesz wtedy korzystać z metod iteracyjnych -> SR, SOR, Jacobiego
...hmm...
a jak można "skrócić" metodę gaussa ?
można np. zrobić tak ? :
[1 1 0 0 0 0 0 0]
[1 1 1 0 0 0 0 0]
[p 1 1 1 0 0 0 0]
[p p 1 1 1 0 0 0]
[p p p 1 1 1 0 0]
[p p p p 1 1 1 0]
[p p p p p 1 1 1]
[p p p p p p 1 1]
gdzie p - oznacza pominięcie obliczeń
czyli po prostu wszystkie elementy pod jedynkami zostaką pominiętę...Można tak w ogóle zrobić?
I czy da się jeszcze jakoś uprościć i zmniejszyć liczbę obliczeń?
poszperałem trochę i znalazłem algorytm na obliczanie macierzy tridiagonalnej. Tylko że po stworzeniu metody wyniki są ...niepokojąco różne....
wziąłem dwie metody i je porównałem (pierwsza to moja wcześniejsza a druga nowa) :
(podam kilka prób - za każdum razem inny rozmiar macierzy)
próba pierwsza
1 metoda - [1.417478010907464, 0.2990263869110431, -0.47635577286247527, -0.005226042180154722, 0.13320631267811317, 0.6505771248688345]
2 metoda - [1.2250786988457503, 0.5299055613850997, -0.4643231899265478, 0.5891920251836307, -0.0535152151101784, 0.5183630640083944]
próba druga
1 metoda - [-1.9369887997341226, 1.833709548238775, -0.05321380063139039, -1.196319839900209, 1.2442036232044416]
2 metoda - [-2.7029480008361437, 1.9482107967009752, 0.31476072126006205, -1.60417348290188, 1.6206839090521379]
wyniki niestety się różnią :/
co z tym zrobić?
czy te różnice są efektem błędów metody czy po prostu nie ten algorytm...
problem rozwiązany...
miałem błąd w kodzie :)
a tak nawiasem to dzięki za nakierowanie na temat :)
poprzednia metoda przy 1000 równaniach osiągała czas obliczeń 0,7 s
natomiast nowa metoda do obliczeń potrzebuje około 0,0002 s :)
dzienks :)