Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Metody iteracyjne rozwiązywania układów równań liniowych
210 views
Skip to first unread message
Borneq
Dec 1, 2012, 1:07:34 AM12/1/12
to
Jakie są kryteria zbieżności? Czy macierz musi być dominująca wierszowo lub
kolumnowo? Według http://pl.wikipedia.org/wiki/Macierz_dominuj%C4%85ca
macierz dominująca to dominująca wierszowo. Co z przypadkiem gdy nie mamy
takiej macierzy?
kolumnowo? Według http://pl.wikipedia.org/wiki/Macierz_dominuj%C4%85ca
macierz dominująca to dominująca wierszowo. Co z przypadkiem gdy nie mamy
takiej macierzy?
bartekltg
Dec 1, 2012, 12:02:27 PM12/1/12
to
W dniu 2012-12-01 07:07, Borneq pisze:
zbieżności jest residuum, czyli ||A x - y||, gdzie x jest naszym
kandydatem na rozwiązanie. W większości metod r = A x - y
i tak jest wyliczane.
Czasem zamiast drugiej normy używa się jakiejś normy
energetycznej, powiązanej z precondicionerem (patrz niżej).
Tu jest niezłą, ogólnie dostępna książeczka na ten temat:
http://www-users.cs.umn.edu/~saad/books.html
> Według
> http://pl.wikipedia.org/wiki/Macierz_dominuj%C4%85ca macierz dominująca
> to dominująca wierszowo. Co z przypadkiem gdy nie mamy takiej macierzy?
Przecież piszą, że w wierszach.
Bierzemy jakąś współczesną metodę iteracyjną, nie starożytną (tzn
klasyczną) jak metoda Jacobiego.
Jakieś PCG dla symetrycznej czy GMRES lub BiCG dla ogólnych.
http://en.wikipedia.org/wiki/Preconditioned_conjugate_gradient_method#The_preconditioned_conjugate_gradient_method
http://en.wikipedia.org/wiki/Biconjugate_gradient_method
http://en.wikipedia.org/wiki/Generalized_minimal_residual_method
Co więcej, te metody mają lepszą zbieżność.
Jak klasyczne mają z każdą iteracją zmniejszenie błędu
(jakkolwiek liczonego) o czynnik (cond(A)-1)/(cond(A)+1),
tak te poważniejsze mają (cond(A)^0.5-1)/(cond(A)^0.5+1)
To znaczna poprawa.
Choć czasem te zbieżność jest w normie energetycznej.
Od razu też widać, że tym, co przeszkadza jest uwarunkowanie
rozwiązywanej macierzy. Cond(A) to z grubsza największa wartość
własna przez najmniejszą. Aby dobrze rozwiązywać iteracyjnie,
musimy "skompresować" spektrum.
Robi się to tak, że buduje 'procondicioner', macierz B,
dla której potrafimy szybko rozwiązać B u = v
(bo np B = M*N, a M i N są trójkątne) oraz dla której
np cond(A*B^-1) jest małe.
Często da się znaleźć lepsze, ale na pierwszy ogień
możesz próbować 'niekompletnymi rozkładami' LU lub Choleskiego.
Na wiki nic nie ma, ale jest cały rozdział 10 w linkowanej
książeczce. Są tam też sztuczki, jak nieco poprawić
uwarunkowanie w metodach klasycznych (np Twoim Jacobim).
pzdr
bartekltg
> Jakie są kryteria zbieżności? Czy macierz musi być dominująca wierszowo
> lub kolumnowo?
Mamy zagadnienie Ax = y, szukamy x. Najprostszym kryterium
> lub kolumnowo?
zbieżności jest residuum, czyli ||A x - y||, gdzie x jest naszym
kandydatem na rozwiązanie. W większości metod r = A x - y
i tak jest wyliczane.
Czasem zamiast drugiej normy używa się jakiejś normy
energetycznej, powiązanej z precondicionerem (patrz niżej).
Tu jest niezłą, ogólnie dostępna książeczka na ten temat:
http://www-users.cs.umn.edu/~saad/books.html
> Według
> http://pl.wikipedia.org/wiki/Macierz_dominuj%C4%85ca macierz dominująca
> to dominująca wierszowo. Co z przypadkiem gdy nie mamy takiej macierzy?
Bierzemy jakąś współczesną metodę iteracyjną, nie starożytną (tzn
klasyczną) jak metoda Jacobiego.
Jakieś PCG dla symetrycznej czy GMRES lub BiCG dla ogólnych.
http://en.wikipedia.org/wiki/Preconditioned_conjugate_gradient_method#The_preconditioned_conjugate_gradient_method
http://en.wikipedia.org/wiki/Biconjugate_gradient_method
http://en.wikipedia.org/wiki/Generalized_minimal_residual_method
Co więcej, te metody mają lepszą zbieżność.
Jak klasyczne mają z każdą iteracją zmniejszenie błędu
(jakkolwiek liczonego) o czynnik (cond(A)-1)/(cond(A)+1),
tak te poważniejsze mają (cond(A)^0.5-1)/(cond(A)^0.5+1)
To znaczna poprawa.
Choć czasem te zbieżność jest w normie energetycznej.
Od razu też widać, że tym, co przeszkadza jest uwarunkowanie
rozwiązywanej macierzy. Cond(A) to z grubsza największa wartość
własna przez najmniejszą. Aby dobrze rozwiązywać iteracyjnie,
musimy "skompresować" spektrum.
Robi się to tak, że buduje 'procondicioner', macierz B,
dla której potrafimy szybko rozwiązać B u = v
(bo np B = M*N, a M i N są trójkątne) oraz dla której
np cond(A*B^-1) jest małe.
Często da się znaleźć lepsze, ale na pierwszy ogień
możesz próbować 'niekompletnymi rozkładami' LU lub Choleskiego.
Na wiki nic nie ma, ale jest cały rozdział 10 w linkowanej
książeczce. Są tam też sztuczki, jak nieco poprawić
uwarunkowanie w metodach klasycznych (np Twoim Jacobim).
pzdr
bartekltg
Borneq
Dec 1, 2012, 2:19:04 PM12/1/12
to
Użytkownik "bartekltg" <bart...@gmail.com> napisał w wiadomości
news:k9dd75$vf4$1...@node2.news.atman.pl...
> Jakieś PCG dla symetrycznej czy GMRES lub BiCG dla ogólnych.
> http://en.wikipedia.org/wiki/Preconditioned_conjugate_gradient_method#The_preconditioned_conjugate_gradient_method
> http://en.wikipedia.org/wiki/Biconjugate_gradient_method
> http://en.wikipedia.org/wiki/Generalized_minimal_residual_method
>
Dzięki za informację, medyoda nie musi byc Jacobiego, zastanawiam się nad
działaniem szybkich metod dla macierzy rzadkich. Na przykład do obliczania
PageRank musi byc niezła metoda skoro w Google mamy 25 miliardów stron.
news:k9dd75$vf4$1...@node2.news.atman.pl...
> Jakieś PCG dla symetrycznej czy GMRES lub BiCG dla ogólnych.
> http://en.wikipedia.org/wiki/Preconditioned_conjugate_gradient_method#The_preconditioned_conjugate_gradient_method
> http://en.wikipedia.org/wiki/Biconjugate_gradient_method
> http://en.wikipedia.org/wiki/Generalized_minimal_residual_method
>
działaniem szybkich metod dla macierzy rzadkich. Na przykład do obliczania
PageRank musi byc niezła metoda skoro w Google mamy 25 miliardów stron.
bartekltg
Dec 1, 2012, 2:32:20 PM12/1/12
to
W dniu 2012-12-01 20:19, Borneq pisze:
http://www-users.cs.umn.edu/~saad/books.html :)
> Dzięki za informację, medyoda nie musi byc Jacobiego, zastanawiam się
> nad działaniem szybkich metod dla macierzy rzadkich. Na przykład do
> obliczania PageRank musi byc niezła metoda skoro w Google mamy 25
> miliardów stron.
A pegerank używa rozwiązywania macierzy? Chyba nie.
To raczej diagonalizacja (ten sam gość, książeczka obok)
i to chyba robi się pro prostu pewną iteracją.
pzdr
bartekltg
> Użytkownik "bartekltg" <bart...@gmail.com> napisał w wiadomości
> news:k9dd75$vf4$1...@node2.news.atman.pl...
>
>
>> Jakieś PCG dla symetrycznej czy GMRES lub BiCG dla ogólnych.
>> http://en.wikipedia.org/wiki/Preconditioned_conjugate_gradient_method#The_preconditioned_conjugate_gradient_method
>>
>> http://en.wikipedia.org/wiki/Biconjugate_gradient_method
>> http://en.wikipedia.org/wiki/Generalized_minimal_residual_method
Te linki to pierodły, gównie to:
> news:k9dd75$vf4$1...@node2.news.atman.pl...
>
>
>> Jakieś PCG dla symetrycznej czy GMRES lub BiCG dla ogólnych.
>> http://en.wikipedia.org/wiki/Preconditioned_conjugate_gradient_method#The_preconditioned_conjugate_gradient_method
>>
>> http://en.wikipedia.org/wiki/Biconjugate_gradient_method
>> http://en.wikipedia.org/wiki/Generalized_minimal_residual_method
http://www-users.cs.umn.edu/~saad/books.html :)
> Dzięki za informację, medyoda nie musi byc Jacobiego, zastanawiam się
> nad działaniem szybkich metod dla macierzy rzadkich. Na przykład do
> obliczania PageRank musi byc niezła metoda skoro w Google mamy 25
> miliardów stron.
To raczej diagonalizacja (ten sam gość, książeczka obok)
i to chyba robi się pro prostu pewną iteracją.
pzdr
bartekltg
0 new messages