Szczepan - 2007-11-29 23:30:48 |
Mam takie zadania, których niestety nie umiem rozwiązać, może kto pomoże?
zad 1)
A= A^T q(A) = {-1 , 0, 3, 9}
x_(n+1) = x_n- - ł(b - (I + A^2)x_n )
a) Podać ł dla których xn jest zbieżne, policzyć granice x_n (w sensie A i b)
b)Podać ł(opt) dla którego zbieżność będzie najszybsza w ||*||2
zad 2)
(zbadać? wykazać?) zbieżność metodu Gaussa-Seidela A= L + D + U
x_(n+1) = x_n - (D+L)^(-1) (Ax_n -b)
pokazać zbieżność w ||*||inf
|
saf - 2007-11-30 15:40:58 |
q(A) to jest spektrum macierzy A?
Pomyśl czy nie da się sprowadzić tej iteracji (popraw mnie jeśli ją źle napiszę):
Do postaci
Wtedy może dałoby się znaleźć wartości własne macierzy B w zależności od \kappa?
Napisz co Ci wyjdzie :)
|
Szczepan - 2007-11-30 18:36:38 |
No ok, pewnie zaraz się tym zajmę,a póki co mała poprawka do drugiego zadania.
No dobra, wiec mam coś takiego: xn+1 = Bxn + c
gdzie B= -U(D+L)-1 c=(D+L)-1
i co? teraz muszę sprawdzić kiedy zachdzi: ||-U(D+L)-1|| inf < 1 ?
Ja nawet nie wiem co mam robić :D
to mieliśmy (z poprzedniego forum), no więc trzeba to udowodnić przy założeniach że macierz jest dominująca diagonalnie, czyli
|
saf - 2007-11-30 19:12:22 |
A co to znaczy "zbieżność w ||.||_\infty"?
Weź to pierwsze dokończ, albowiem jest fajniejsze :p
|
saf - 2007-11-30 23:02:14 |
Ok mam 3 pytania:
1) Skąd to wynika z Tw Jordana?
2) Czy zachodzi ||A||2 = max z |λk| ?
3) Normy są równoważne, czyli jak ||A||2 < 1 to każda inna też? :D:D
3) Na pewno nie zachodzi to dla wektorów, więc dla macierzy też raczej nie. Dla wektorów, dla ustalenia uwagi z R^2, weźmy punkt x = (sqrt(2)/2, sqrt(2)/2). ||x||_2 = 1, ale ||x||_1 = sqrt(2). Koniec kontrprzykładu :)
2) Nie wiem, ale podobno zachodzi . Skąd - nie pytaj :)
1) Twierdzenie Jordana mówi o istnieniu rozkładu , gdzie \Lambda jest postaci Jordana (ale dla B^T = B jest diagonalna z wartościami własnymi B na diagonali, przypadek kiedy nie jest diagonalna jest trochę trudniejszy, ale też działa - mieliśmy taką pracę domową).
Niech \alpha będzie rozwiązaniem równania x = Bx + f. Stąd:
Odejmując stronami mamy, że jeżeli e_k to błąd na k-tym kroku, to e_(k+1) = Be_k.
Rozwijamy rekurencję dostając e_k = B^k * e_0. No ale z tw. Jordana mamy, że . Chcemy, żeby B^k * e_k zbiegało do 0, ale e_0 jest dowolne (zależy od wyboru x_0), więc potrzebujemy, żeby to B^k -> 0 z k -> \infty. Na diagonali \Lambda^k są wartości własne podniesione do k-tej potęgi, więc żeby B^k -> 0, musi być, że każda wartość własna jest mniejsza od jedynki.
Uff.
|
Maciek - 2007-12-04 22:08:48 |
http://www.mimuw.edu.pl/~przykry/mn/mn- … n-2007.pdf
Zadanie 1. a)
Jak pokazać jak szybko takie cudo zbiega?
|
Szczepan - 2007-12-05 22:36:02 |
Ok odnośnie moich zadanek, w zad 1) dostałem coś takiego:
a)
znamy własności własne A są to -1,0,3,9 wartości własne A^2 to kwadraty 1 0 9 81 (bo A^T=A więc A=QDQ^T A^2 = QD^2Q^T gdzie D macierz diagonalna z wartościami własnymi), potem mnożymy to przez \tau i dodajemy (1 + \tau) i otrzymujemy:
promień spektralny macierzy B = 1 + 82*\tau (B <- macierz iteracyjna) no i on co do modułu musi być mniejszy od jedności więc
hmm?
Ale co to jest granica w sensie b i A to ja nie wiem ;/
b) Nie wiem gdzieś wyczytałem, że "promień spektralny jest pewną asymptotyczną miarą efektywności metody iteracyjnej" , zatem minimalizujemy go:
mamy takie wartości własne macierzy B |1+2\tau| , |1+\tau| , |1+10\tau| , |1+82\tau| no i minimum z maxa wartości tych funkcji wyszło mi dla |1+\tau| = |1+82\tau| co jest :
tylko po co w treści coś o normie drugiej mówią? ;/
|
saf - 2007-12-06 20:26:06 |
Jakiś brzydki ten wynik, no ale nie widzę błędów na pierwszy rzut oka. Testy robiłeś? :)
Co do normy, w której mierzymy zbieżność, to kto mi poda kontrprzykład na:
? Jeśli to prawda, to chyba zbieżność można mierzyć w dowolnej normie i wyjdzie na to samo?
Edit: po zastanowieniu się - z tego co powyżej, nawet jeżeli to prawda, to raczej nie wynika od razu ze szybkość zbieżności można mierzyć w którejkolwiek normie.
|
Maciek - 2007-12-06 20:41:53 |
saf napisał:Jeśli to prawda, to chyba zbieżność można mierzyć w dowolnej normie i wyjdzie na to samo?
Ponoć wszystkie normy w R^N są równoważne, czyli zbieżność można pokazywać na dowolnej.
|
Szczepan - 2007-12-07 18:57:31 |
Jakby kogoś interesowało, rozwiązanie mojego zadania drugiego, to jest ono tu:
http://www.maths.lancs.ac.uk/~gilbert/m306b/node18.html
|
saf - 2007-12-09 17:11:27 |
Rozwiązanie kolokwium z grupy Szczepana, proszę skrytykować jak coś źle (w szczególności jak źle zapamiętałem zadanie)
Oszacować rząd zbieżności metody Newtona w pobliżu pi/2 dla funkcji: a) cos x b) sin x - 1 (1 - sin x wygląda mniej więcej tak samo, więc nawet jak się pomyliłem co do treści to powinno być dobrze)
Będziemy iterację Newtona traktować jako iterację Banacha , gdzie .
Mamy oczywiście Fi(pi/2) = pi/2, bo pi/2 jest miejscem zerowym obu funkcji. Ale: Ad a)
Uwierzcie na słowo, że Fi'''(x) nie równa się zero.
No i teraz wytaczamy na tę muchę artylerię w postaci Wniosku z Twierdzenia Banacha o Kontrakcji (wykład 2., strona 16 mojego zeszytu i pewnie jeszcze gdzieś). Jeżeli Fi'(x*) = Fi''(x*) = 0, to iteracja jest zbieżna z wykładnikiem co najmniej 3.
Ad b) Można Wnioskiem, ale to "co najmniej" psuje obraz. Więc z wniosku z wniosku, który mam na stronie następnej zeszytu, a który mówi że jeżeli x* jest izolowanym m-krotnym miejscem zerowym f, czyli 0 = f(x*) = f'(x*) = ... = f^(m-1)(x*), to iteracja Newtona jest zbieżna tylko liniowo ze stałą (1 - 1/m), wynika, że zbieżność jest liniowa ze stałą 1/2 (lipnie).
Ujdzie?
|
wojtek - 2007-12-09 18:15:29 |
Oo, sympatycznie zrobione ;] Muszę sobię te wnioski spamiętać ;]
http://students.mimuw.edu.pl/~wl248271/ … 2005.11.16(1).gif http://students.mimuw.edu.pl/~wl248271/ … 2005.11.16(2).gif
tutaj fajne zadanka. Tym drugim może ktoś chce się zająć. Wydaje mi się, że schemat Hornera nie jest tu najlepszy.. ale nie mam tu pomysłów
|
saf - 2007-12-09 20:30:02 |
Czy węzły Czebyszewa pojawiły się na zajęciach?
(spojrzenie na definicję na http://wazniak.mimuw.edu.pl/index.php?title=MN09 wtłacza w mą głowę myśl, że nie było oraz że lepiej trzymać się od tego z daleka)
Edit: nie jest takie straszne, a nawet jest logiczne - chcemy zagęścić na końcach, więc bierzemy cosinus, bo na końcach przedziału [0, pi] wolno się zmienia. Ale dowód pominę do przeczytania na kiedy indziej :)
|
wojtek - 2007-12-09 20:35:19 |
nie, nie pojawiły się ;)
|
Szczepan - 2008-01-14 16:13:45 |
Ok moje zadanka ostatniej szansy na piątkową kartkówkę, najpierw to:
a = X_0 < ... < x_n=b h= (b-a)/N x_i = x_0 + ih
Znaleźć c,d należące do R t. że:
jest klasy
|
Szczepan - 2008-01-14 16:31:43 |
Zadanko drugie: niech pi - podział równomierny [a,b]
t.że:
Trzeba pokazać, że:
uff... 20 minut klepania (bez przerw) ;p
|
saf - 2008-01-14 17:22:54 |
W pierwszym - wydaje mnie się - jest błąd. Nie znajdziesz takiej funkcji liniowej, bo musiałaby mieć na jednym końcu przedziału pochodną dodatnią, na drugim ujemną. QED.
W drugim obejrzyj
http://wazniak.mimuw.edu.pl/index.php?t … 5.9B.C4.87
- dowód twierdzenia o błędzie interpolacji dla splajnu chyba liniowego, i sprobuj przez analogie :)
|