Informatyka UJ forum

Yoter

Ok, to ja też mam pytanie...

Skąd się bierze równość Q(x+ar) = 1/2*a^2*r^t*A*r + a*r^t*r + 1/2*r^t*A^(-1)*r
przy metodzie gradientów?
r^t - r transponowane...

Albo przeoczyłem coś oczywistego, albo to nie wynika za wzoru na Q(x)...

Może mi to ktoś mądry wyjaśnić, proszę?

Spectro

@Yoter:
Cóż, mnie to też swego czasu nie wychodziło. Ale po tym, jak przeczytałem po raz pierwszy Twój post postanowiłem policzyć... i jednak da się to zrobić :p .

Niech r = Ax - b. Zauważmy, że Q(x) = 1/2 * r^t * A^(-1) * r, czyli ostatni z członów naszej równości z Q(x+a*r). Z A = A^t wynika, że: (a*r)^t * A * x = x^t * A * (a*r) = a * (A*x)^t * r. Teraz możemy przystąpić do rachunków...

Q(x+a*r)
= 1/2 * (x+a*r)^t * A * (x+a*r) - b^t * (x+a*r) + 1/2 * b^t * A^(-1) * b
= (1/2 * x^t * A * x - b^t * x + 1/2 * b^t * A^(-1) * b)
+ 1/2 * (a*r)^t * A * (a*r)
+ (1/2 * (a*r)^t * A * x + 1/2 * x^t * A * (a*r) - b^t * (a*r))
= Q(x)
+ 1/2 * a^2 * r^t * A * r
+ (a * (A*x)^t * r - a * b^t * r)
= 1/2 * r^t * A^(-1) * r
+ 1/2 * a^2 * r^t * A * r
+ a * (A*x-b)^t * r
= 1/2 * r^t * A^(-1) * r
+ 1/2 * a^2 * r^t * A * r
+ a * r^t * r

Q.U.E.D.

edit: Poprawiłem 2 plusy na minusy, aby wszystko faktycznie grało. Za dużo tych znaczków, człowiekowi się chrzani :roll: .

Yoter

Niiiiice... :D Wielkie dzięki Spectro. :)

exeman

Mam pytanie.
Jaki rozkład QR nas obowiązuje - Gramma-Schmidta czy Householdera, czy jakaś inna? I skąd wzieliście dowód jej poprawności (czy musimy go umieć)?

Pozdrawiam

Spectro

exeman

Spectro, a przypadkiem ten dowód poprawności nie tyczy się metody QR zamiast rozkładu QR?

Czy polecasz jakąś literaturę, gdzie są dobrze wytłumaczone te metody QR obie?

Pytanie ogólne
Czy Traple wymaga dowodów, których nie było na wykładzie?

chlebek

dzendras

Ma ktoś może notatki z wykładów, które obejmują zagadnienia od 37 wzwyż? Jeśli tak to prosiłbym o zeskanowanie, albo o pożyczenie do skserowania (w Krakowie) :)
Po udanej transakcji piwko postawię albo co :P

Spectro

Rogal

Traple wogóle dowodów wymagał mało. W pierwszej kolejności trzeba się nauczyć tych wszystkich 46 (czy ile ich tam jest) zagadnień bez dowodów, a dopiero później, jak zostanie czas i naprawdę wszystko będzie się umiało dobrze zacząć się dowodów uczyć.

Ale w sumie na poprawce może mu się wszystko zmienić, więc nie wiadomo jak to będzie.

exeman

Kolezanki i koledzy,

Pytanie mam związane z liniową algebrą.

Jak udowodnić, że det A^T = det A ?

dzendras

No bez jaj... Takich rzeczy to my chyba nie musimy udowadniać? Nie żebym wiedział jak to zrobić :) O nie :)

kafex

To czasem z laplace'a nie pójdzie ?

exeman

kafex: Dobry pomysł, możliwe, że to o to chodzi, sprawdzę.

Mam za to inne pytanie.

Dlaczego wskaźnik uwarunkowania zadania obliczania układu równań liniowych jest najlepszy dla <macierzy ortogonalnych (?)>, oraz co to znaczy "wartości własne mało rozrzucone", przecież to jest bez sensu (1000, 1001 - są mało rozrzucone, a ich iloczyn jest kosmiczny. Za to -10 oraz 10 są bardziej rozrzucone, a ich iloczyn jest o wiele lepszy).

Z góry dzięki!

Spectro

dzendras

Skrypt prof. Sędziwego z IF. Wyglądają ciekawie :)

[link widoczny dla zalogowanych](2007-02-03).pdf

PS. Na 27 stronie w pdf jakże zajmujący dowód tw. o wydobywaniu normy :)

yuuu

hmm a ja mam proste pytanie do zapewne prostej rzeczy : czy ktos mi moze wytłuamczyc ten fragment dowodu dla rozkladu choleskyego:

a_nn - L^HL = a_nn - [ ( [L_(n-1)]^(-1) * a )^H ]*( [L_(n-1)]^(-1) * a ) = i tutaj zaczyna sie z tym
b=[A_(n-1)]^(-1) * a i mnozeniem macierzy A przez b z obustron...zapewne to cos prostego i oczywistego ale po całym dniu rozgryzania wszelkich "sprytnych" przejsc jakie non stop w tych dowodach wystepuja (a ktore nie sa jakos wyraznie zaznaczone) juz nie mam sił nad tym sie głowic :|

Z góry dzieki :P

@dzendras: skrypcik jest fajny...szkoda ze u nas nie ma takiego czegos, tylko te notatki w ktorych sie non stop mozna zagubic i nie znaleźć :D

krzycho

W Jankowskich jest to fajnie napisane.

ale postaram sie coś naskrobać:

a_nn - L^HL - to jest taka zmyła,
ten szlaczek to
l_nn^2 = a_nn - L^HL,

chcemy pokazać, że l_nn istnieje i jest jednoznacze( w koncu chcemy pokazac ze istnieje macierz L_n dla A_n)

b := A_n-1^-1a, definiujemy po to by, korzystając z :

a) A_nn m. dodatnio określona - z zalozenia twierdzenia
b) A_nn dod. okreś. <=> x^HAx > 0

za x do x^HAx wstawiamy

x = [ b , -1 ]
gdzie, b = A_n-1^-1a,

x^HAx 'wykorzystamy' do zdefiniowania jednoznaczego l_nn.
tzn. obliczamy x^HAx, i jak wszystko pojdzie dobrze to otrzymujemy
0 < x^HAx = ... [#$%# < - kosodrzewina ] ... = a_nn - L^HL = l_nn^2

czyli zdefiniowaliśmy jednoznacznie l_nn, bo z załozenia tw. l_ii > 0
wiec l_nn := sqrt( a_nn - L^HL )

edit: teraz jest ok, wczesniej bylo pomieszane z l_nn.
uff...

za prosba dzendrasa dolaczam skany z jankowskich:
[link widoczny dla zalogowanych]

na dole skanow jest niewyraznie bo mi sie ksiazka nie zmiescila do skanera :P

jagm

sluchajcie narodzie ;] na po co my sie tak mamy meczyc i opracowywac wszystko samemu, skoro mozemy dzialac wspolnie ;] czy cos ;p
skoro mamy liste zagadnien, to wystarczy, ze kazdy dokladnie opracuje jedno zagadnienie i wypisze wszystko na kartce, a potem tylko sobie to pokserujemy i kazdy bedzie mial komplet i bedzie wiecej czasu na nauke zamiast kopac po roznych ksiazkach.
co Wy na to? ;] pomozecie? ;]

kafex

Siur popieram...można stworzyć topic z bazą wszystkiego or wykorzystać bunkier.

jagm

heh. no bunkier sie chyba nie nadaje ;] mi nie chodzi o to, zeby byly tam rozne twierdzenia powypisywane z osobna, bo potem na dopasowanie kazdego do odpowiedniego tematu tez sie bedzie tracilo czas. no chyba ze porobi sie tematy typu 'zagadnienie 1', itd.
a tak kazdy zmarnuje najwyzej pol dnia na dokladne opracowanie jednego tematu i rozpisanie go, udostepni calosc i teraz wystarczy sie tego nauczyc (ewentualnie wykuc na pamiec ;p) nie grzebiac po ksiazkach i internecie szukajac jakistam dodatkowych rzeczy i dowodow.

kafex

Dokładnie chodziło mi o bazę opracowanych tematów/zagadanień do egzamu ;] tak jak napisałeś żeby mieć wszystko odnośnie tematu w jednym miejscu.

jagm

ok. w takim razie poczekajmy na zdanie innych, bo poki co, to w dwojke niewiele zdzialamy ;p ale mam nadzieje, ze reszta tez sie zgodzi ;] wiec od razu moze piszcie, czy macie juz jakies tematy opracowane i jesli tak, to jakie, zebysmy sie nie powtarzali. a te tematy, ktore jeszcze nie sa opracowane jakos sie podzieli miedzy reszte ludzi ;]

cheater_

jagm

heh. moglem sie uczyc do numerkow zamiast ukladac pasjansa, to bym moze wiedzial ;p
tylko ze tak czy inaczej trzeba by to bardziej rozwinac, bo jak na razie, to w wiekszosci sa tam jakies ogolne rzeczy, wiec i tak trzeba sie grzebac w ksiazkach, zeby to rozwinac.
w takim razie ja sie deklaruje, ze moge uzupelnic punkt pierwszy, bo akurat na tym jestem w stoerze ;]