MaIn forum

Forum matematyczno-informatyczne


#1 2007-11-29 23:30:48

Szczepan

Użytkownik

Zarejestrowany: 2007-11-29
Posty: 13
Punktów :   

Zadania domowo-kartkówkowe

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

Offline

 

#2 2007-11-30 15:40:58

saf

Administrator

3457910
Skąd: Zakręt
Zarejestrowany: 2007-11-29
Posty: 56
Punktów :   
WWW

Re: Zadania domowo-kartkówkowe

q(A) to jest spektrum macierzy A?

Pomyśl czy nie da się sprowadzić tej iteracji (popraw mnie jeśli ją źle napiszę):

http://www.texify.com/img/%5Cnormalsize%5C%21%5Cvec%20x_%7Bn%2B1%7D%20%3D%20%5Cvec%20x_n%20%5C%2C%20-%20%5C%2C%20%5Ckappa%20%28%5Cvec%20b%20%5C%2C%20-%20%5C%2C%20%28I%20%2B%20A%5E2%29%20%5Cvec%20x_n%29.gif


Do postaci

http://www.texify.com/img/%5Cnormalsize%5C%21%5Cvec%20x_%7Bn%2B1%7D%20%5C%2C%20%3D%20%5C%2C%20B%20%5Cvec%20x_n%20%2B%20%5Cvec%20f.gif



Wtedy może dałoby się znaleźć wartości własne macierzy B w zależności od \kappa?

Napisz co Ci wyjdzie

Offline

 

#3 2007-11-30 18:36:38

Szczepan

Użytkownik

Zarejestrowany: 2007-11-29
Posty: 13
Punktów :   

Re: Zadania domowo-kartkówkowe

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ć

to mieliśmy (z poprzedniego forum), no więc trzeba to udowodnić przy założeniach że macierz jest dominująca diagonalnie, czyli

http://www.texify.com/img/%5CLARGE%5C%21%7Ca_%7Bii%7D%7C%20%3E%20%5Csum_%7Bi%20%5Cneq%20j%20%7D%7Ca_%7Bij%7D%7C.gif

Offline

 

#4 2007-11-30 19:12:22

saf

Administrator

3457910
Skąd: Zakręt
Zarejestrowany: 2007-11-29
Posty: 56
Punktów :   
WWW

Re: Zadania domowo-kartkówkowe

A co to znaczy "zbieżność w ||.||_\infty"?

Weź to pierwsze dokończ, albowiem jest fajniejsze

Offline

 

#5 2007-11-30 23:02:14

saf

Administrator

3457910
Skąd: Zakręt
Zarejestrowany: 2007-11-29
Posty: 56
Punktów :   
WWW

Re: Zadania domowo-kartkówkowe

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ż?

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 http://www.texify.com/img/%5CLARGE%5C%21%7C%7C%20A%20%7C%7C_2%20%5Ccdot%20%7C%7CA%5E%7B-1%7D%7C%7C_2%20%3D%20cond_%7B2%7D%28A%29%20%3D%20%5Cfrac%7B%5Clambda_%7Bmax%7D%7D%7B%5Clambda_%7Bmin%7D%7D.gif. Skąd - nie pytaj

1) Twierdzenie Jordana mówi o istnieniu rozkładu http://www.texify.com/img/%5CLARGE%5C%21A%20%5C%2C%20%3D%20%5C%2C%20Q%5E%7B-1%7D%5CLambda%20Q.gif, 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:

http://www.texify.com/img/%5CLARGE%5C%21%5C%7B%20%7B%20x_%7Bk%2B1%7D%20%3D%20Bx_k%20%2B%20f%20%5C%5C%20%5Calpha%20%3D%20B%5Calpha%20%2B%20f%20%7D%20.gif


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 http://www.texify.com/img/%5CLARGE%5C%21B%5Ek%20%5C%2C%20%3D%20%5C%2C%20Q%5E%7B-1%7D%20%5CLambda%5Ek%20Q.gif. 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.

Offline

 

#6 2007-12-04 22:08:48

Maciek

Użytkownik

Zarejestrowany: 2007-11-29
Posty: 32
Punktów :   

Re: Zadania domowo-kartkówkowe

http://www.mimuw.edu.pl/~przykry/mn/mn- … n-2007.pdf

Zadanie 1. a)

Jak pokazać jak szybko takie cudo zbiega?

Offline

 

#7 2007-12-05 22:36:02

Szczepan

Użytkownik

Zarejestrowany: 2007-11-29
Posty: 13
Punktów :   

Re: Zadania domowo-kartkówkowe

Ok odnośnie moich zadanek, w zad 1) dostałem coś takiego:

a)
http://www.texify.com/img/%5CLARGE%5C%21x_%7Bn%2B1%7D%20%3D%20x_n%20%28%20I%20%2B%20%5Ctau%20I%20%2B%20%5Ctau%20A%5E2%20%29%20-%20%5Ctau%20b.gif

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

http://www.texify.com/img/%5CLARGE%5C%21%5Ctau%20%5Cin%20%28-%5Cfrac%7B1%7D%7B41%7D%20%2C%200%29.gif

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 :
http://www.texify.com/img/%5CLARGE%5C%21%5Ctau%20%3D%20-%5Cfrac%7B2%7D%7B83%7D.gif

tylko po co w treści coś o normie drugiej mówią? ;/

Offline

 

#8 2007-12-06 20:26:06

saf

Administrator

3457910
Skąd: Zakręt
Zarejestrowany: 2007-11-29
Posty: 56
Punktów :   
WWW

Re: Zadania domowo-kartkówkowe

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:

http://www.texify.com/img/%5CLARGE%5C%21%5Cforall%5Climits_%7Bx%2C%20y%20%5Cin%20%5Cmathbb%7BK%7D%7D%20%28%20%7B%20%7C%7Cx%7C%7C_%5Calpha%20%5Cle%20%20%7C%7Cy%7C%7C_%5Calpha%20%5CRightarrow%20%7C%7Cx%7C%7C_%5Cbeta%20%5Cle%20%7C%7Cy%7C%7C_%5Cbeta%20%7D%20%29.gif


? 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.

Offline

 

#9 2007-12-06 20:41:53

Maciek

Użytkownik

Zarejestrowany: 2007-11-29
Posty: 32
Punktów :   

Re: Zadania domowo-kartkówkowe

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.

Offline

 

#10 2007-12-07 18:57:31

Szczepan

Użytkownik

Zarejestrowany: 2007-11-29
Posty: 13
Punktów :   

Re: Zadania domowo-kartkówkowe

Jakby kogoś interesowało, rozwiązanie mojego zadania drugiego, to jest ono tu:

http://www.maths.lancs.ac.uk/~gilbert/m306b/node18.html

Offline

 

#11 2007-12-09 17:11:27

saf

Administrator

3457910
Skąd: Zakręt
Zarejestrowany: 2007-11-29
Posty: 56
Punktów :   
WWW

Re: Zadania domowo-kartkówkowe

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 http://www.texify.com/img/%5CLARGE%5C%21x_%7Bn%2B1%7D%20%5C%2C%20%3D%20%5C%2C%20x_n%20-%20%7B%20f%28x_n%29%20%5Cover%20f%27%28x_n%29%20%7D.gif traktować jako iterację Banacha http://www.texify.com/img/%5CLARGE%5C%21x_%7Bn%2B1%7D%20%5C%2C%20%3D%20%5C%2C%20%5CPhi%28x_n%29.gif, gdzie http://www.texify.com/img/%5CLARGE%5C%21%5CPhi%28x%29%20%3D%20x%20-%20%5Cfrac%7Bf%28x%29%7D%7Bf%27%28x%29%7D.gif.

Mamy oczywiście Fi(pi/2) = pi/2, bo pi/2 jest miejscem zerowym obu funkcji. Ale:
Ad a)
http://www.texify.com/img/%5CLARGE%5C%21%5CPhi%27%28x%2A%29%20%3D%201%20%2B%20ctg%27%28x%2A%29%20%3D%200.gif
http://www.texify.com/img/%5CLARGE%5C%21%5CPhi%27%27%28x%2A%29%20%3D%20%281%20-%20%5Cfrac%7B1%7D%7Bsin%5E2%28x%2A%29%7D%29%20%3D%202%20%5Cfrac%7Bcos%28x%2A%29%7D%7Bsin%5E3%28x%2A%29%7D%20%3D%200.gif
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?

Offline

 

#12 2007-12-09 18:15:29

wojtek

Użytkownik

Zarejestrowany: 2007-11-30
Posty: 30
Punktów :   

Re: Zadania domowo-kartkówkowe

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

Offline

 

#13 2007-12-09 20:30:02

saf

Administrator

3457910
Skąd: Zakręt
Zarejestrowany: 2007-11-29
Posty: 56
Punktów :   
WWW

Re: Zadania domowo-kartkówkowe

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

Offline

 

#14 2007-12-09 20:35:19

wojtek

Użytkownik

Zarejestrowany: 2007-11-30
Posty: 30
Punktów :   

Re: Zadania domowo-kartkówkowe

nie, nie pojawiły się

Offline

 

#15 2008-01-14 16:13:45

Szczepan

Użytkownik

Zarejestrowany: 2007-11-29
Posty: 13
Punktów :   

Re: Zadania domowo-kartkówkowe

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:

http://www.texify.com/img/%5CLARGE%5C%21%5Clarge%20B_i%28x%29%3D%20%5Cfrac1%7Bh%5E2%7D%5C%20%5C%7B%5C%20%28x-x_%7Bi-1%7D%29%5E2%20%5Ctext%7B%20gdy%20%7D%20x%5Cin%20%5Bx_%7Bi-1%7D%2Cx_i%5D%20%20%5C%5Cc%28x-x_%7Bi%2B%5Cfrac1%7B2%7D%7D%29%2Bd%20%5Ctext%7B%20gdy%20%7D%20%20x%5Cin%20%5Bx_i%2Cx_%7Bi%2B1%7D%5D%20%20%5C%5C%28x_%7Bi%2B2%7D-x%29%5E2%20%5Ctext%7B%20gdy%20%7D%20x%5Cin%20%5Bx_%7Bi%2B1%7D%2Cx_%7Bi%2B2%7D%5D..gif

jest klasy  http://www.texify.com/img/%5CLARGE%5C%21C%5E1%28%5Ba%2Cb%5D%29.gif

Offline

 

#16 2008-01-14 16:31:43

Szczepan

Użytkownik

Zarejestrowany: 2007-11-29
Posty: 13
Punktów :   

Re: Zadania domowo-kartkówkowe

Zadanko drugie:
niech pi - podział równomierny [a,b]

http://www.texify.com/img/%5CLARGE%5C%21%20f%20%5Cin%20C%5E3%5Ba%2Cb%5D%20%5C%5CS_%7B2%2CN%7Df%20%5Cin%20C%5Ba%2Cb%5D%20%20.gif

t.że:

http://www.texify.com/img/%5CLARGE%5C%21S_%7B2%2CN%7Df%20%5Cin%20P_2%20%5Ctext%7B%20na%20%7D%20%5Bx_i%2Cx_%7Bi%2B1%7D%5D%20%5Ctext%7B%20i%20%7D%20S_%7B2%2CN%7Df%28x_i%29%3Df%28x_i%29%2C%20i%3D0..N%20%20%5C%5CS_%7B2%2CN%7Df%20%28x_%7Bi%2B%5Cfrac1%7B2%7D%7D%29%20%3D%20f%20%28x_%7Bi%2B%5Cfrac1%7B2%7D%7D%29%20%5Ctext%7B%20gdzie%20%7D%20x_%7Bi%2B%5Cfrac1%7B2%7D%7D%20%3D%20%5Cfrac%7Bx_i%2Bx_%7Bi%2B1%7D%7D%7B2%7D%20%5C%5C.gif

Trzeba pokazać, że:

http://www.texify.com/img/%5CLARGE%5C%21%7C%7Cf-S_%7B2%2CN%7Df%7C%7C_%5Cinfty%20%5Cleq%20C%20h%5E3%20%7C%7Cf%5E%7B%283%29%7D%7C%7C_%5Cinfty.gif


uff... 20 minut klepania (bez przerw) ;p

Ostatnio edytowany przez Szczepan (2008-01-14 16:32:15)

Offline

 

#17 2008-01-14 17:22:54

saf

Administrator

3457910
Skąd: Zakręt
Zarejestrowany: 2007-11-29
Posty: 56
Punktów :   
WWW

Re: Zadania domowo-kartkówkowe

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

Offline

 

Stopka forum

RSS
Powered by PunBB
© Copyright 2002–2008 PunBB
Polityka cookies - Wersja Lo-Fi


Darmowe Forum | Ciekawe Fora | Darmowe Fora
www.slash-pokemon.pun.pl www.bap-poland.pun.pl www.linkomania.pun.pl www.el-trans.pun.pl www.pbfwwe.pun.pl