MN02LAB: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 38: Linia 38:
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
<div style="font-size:smaller; background-color:#f9fff9; padding: 1em"> Bardzo wygodnie napisać taki program w postaci skryptu Octave. Pamiętaj
+
<div style="font-size:smaller; background-color:#f9fff9; padding: 1em"> Bardzo wygodnie napisać taki program w postaci skryptu Octave. Pamiętaj jednak, by uniknąć w nim pętli w rodzaju
jednak, by uniknąć w nim pętli w rodzaju
 
  
 
<code style="color: #006">for xpixels = 1:1024, for ypixels = 1:768,... wyznacz kolor pixela ....</code>
 
<code style="color: #006">for xpixels = 1:1024, for ypixels = 1:768,... wyznacz kolor pixela ....</code>
  
Taka podwójnie zagnieżdżona pętla może skutecznie zniechęcić Cię do  
+
Taka podwójnie zagnieżdżona pętla może skutecznie zniechęcić Cię do Octave'a --- obrazek będzie liczyć się wieki --- zupełnie niepotrzebnie!  
Octave'a --- obrazek będzie liczyć się wieki --- zupełnie niepotrzebnie!  
 
 
  </div>
 
  </div>
 
</div></div>
 
</div></div>
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
<div style="font-size:smaller; background-color:#f9fff9; padding: 1em"> Kluczem do efektywnej implementacji w Octave jest przeprowadzenie
+
<div style="font-size:smaller; background-color:#f9fff9; padding: 1em"> Kluczem do efektywnej implementacji w Octave jest przeprowadzenie iteracji Newtona na <strong>wszystkich pikselach jednocześnie</strong>. W tym celu musisz skorzystać z prowadzenia działań na całych macierzach. </div>
iteracji Newtona na <strong>wszystkich pikselach jednocześnie</strong>. W tym celu musisz
 
skorzystać z prowadzenia działań na całych macierzach. </div>
 
 
</div></div>
 
</div></div>
  
Linia 67: Linia 63:
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
<div style="font-size:smaller; background-color:#f9fff9; padding: 1em"> Na pewno kusi Cię, by zaprogramować najpierw ogólnie funkcję "metoda
+
<div style="font-size:smaller; background-color:#f9fff9; padding: 1em"> Na pewno kusi Cię, by zaprogramować najpierw ogólnie funkcję "metoda Newtona", a następnie przekazać jej jako parametr naszą funkcję. Jednak gdy prostu wyliczysz na karteczce wzór na iterację dla <strong>tej konkretnej funkcji, <math>\displaystyle F(x) = x^2-a</math></strong>, będziesz miał szansę dokonać większych optymalizacji. </div>
Newtona", a następnie przekazać jej jako parametr naszą funkcję. Jednak gdy prostu wyliczysz na karteczce wzór na iterację dla <strong>tej konkretnej funkcji, <math>\displaystyle F(x) = x^2-a</math></strong>, będziesz miał szansę dokonać większych optymalizacji.  
 
</div>
 
 
</div></div>
 
</div></div>
  
Linia 89: Linia 83:
 
co właśnie tłumaczy się jako podwajanie liczby dokładnych cyfr znaczących wyniku po każdej iteracji.
 
co właśnie tłumaczy się jako podwajanie liczby dokładnych cyfr znaczących wyniku po każdej iteracji.
  
Ale jeśli <math>\displaystyle a=0</math>, to metoda zbieżna jest już tylko liniowo (z ilorazem 0.5 --- bo
+
Ale jeśli <math>\displaystyle a=0</math>, to metoda zbieżna jest już tylko liniowo (z ilorazem 0.5 --- bo jaki wtedy jest wzór na iterację?); dlatego kolejną dokładną cyfrę wyniku <math>\displaystyle x^*=0</math> będziemy dostawali co mniej więcej trzy kroki... Zbieżność będzie ''powolna!'' (Na szczęście, gdy <math>\displaystyle a=0</math>, nie ma żadnego problemu z podaniem ''dokładnego'' rozwiązania...)
jaki wtedy jest wzór na iterację?); dlatego kolejną dokładną cyfrę wyniku <math>\displaystyle x^*=0</math> będziemy dostawali co mniej więcej trzy kroki... Zbieżność będzie ''powolna!'' (Na szczęście, gdy <math>\displaystyle a=0</math>, nie ma żadnego problemu z podaniem ''dokładnego'' rozwiązania...)
 
  
 
Nie dyskutujemy tutaj sposobu doboru właściwego punktu startowego dla metody: na razie wiadomo, że musi być "dostatecznie blisko" rozwiązania. Czy jesteś w stanie sprawdzić --- wypisując bardziej precyzyjne oszacowanie błędu (zob. dowód twierdzenia o zbieżności) --- jakie <math>\displaystyle x_0</math> na pewno jest "dostatecznie blisko" rozwiązania?
 
Nie dyskutujemy tutaj sposobu doboru właściwego punktu startowego dla metody: na razie wiadomo, że musi być "dostatecznie blisko" rozwiązania. Czy jesteś w stanie sprawdzić --- wypisując bardziej precyzyjne oszacowanie błędu (zob. dowód twierdzenia o zbieżności) --- jakie <math>\displaystyle x_0</math> na pewno jest "dostatecznie blisko" rozwiązania?
Linia 173: Linia 166:
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
<div style="font-size:smaller; background-color:#f9fff9; padding: 1em"> Aby znaleźć graniczne <math>\displaystyle X_0</math>, czyli takie, dla którego dostaniesz
+
<div style="font-size:smaller; background-color:#f9fff9; padding: 1em"> Aby znaleźć graniczne <math>\displaystyle X_0</math>, czyli takie, dla którego dostaniesz oscylacje <math>\displaystyle X_0, -X_0,\ldots</math>,  musisz rozwiązać równanie nieliniowe:
oscylacje <math>\displaystyle X_0, -X_0,\ldots</math>,  musisz rozwiązać równanie nieliniowe:
 
  
 
<center><math>\displaystyle -X_0 = X_0 - \frac{\arctan(X_0)}{\frac{1}{1+X_0^2}}.
 
<center><math>\displaystyle -X_0 = X_0 - \frac{\arctan(X_0)}{\frac{1}{1+X_0^2}}.

Wersja z 20:12, 28 wrz 2006


Równania nieliniowe skalarne

Ćwiczenie: Metoda Newtona może być zbieżna globalnie

Wykaż, że jeśli jest rosnąca i wypukła na oraz dla , to metoda Newtona startująca z jest zbieżna.

Rozwiązanie

Ćwiczenie: Fraktale

Ciekawy zbiór o charakterze fraktalnym powstaje w wyniku zastosowania metody Newtona do rozwiązania równania w dziedzinie zespolonej. Punkt należy do basenu zbieżności metody, jeśli startująca z niego metoda Newtona jest zbieżna do (jakiegokolwiek) pierwiastka w/w równania. Kolor odpowiadający jest określany na podstawie liczby iteracji potrzebnych metodzie do zbieżności.

Zupełnie miłym (i estetycznie wartościowym) doświadczeniem jest napisanie programu w Octave, który wyświetla baseny zbieżności metody Newtona, takie jak na rysunku poniżej.

Basen zbieżności metody Newtona w okolicy początku układu współrzędnych, dla równania
Wskazówka
Wskazówka

Ćwiczenie: Pierwiastkowanie

Niech . Aby wyznaczyć , można skorzystać z metody Newtona dla równania . Zaprogramuj tę metodę i sprawdź, jak wiele dokładnych cyfr wyniku dostajesz w kolejnych krokach. Czy to możliwe, by liczba dokładnych cyfr znaczących z grubsza podwajała się na każdej iteracji? Wskaż takie , dla którego to nie będzie prawdą.

Wskazówka
Rozwiązanie

Ćwiczenie: Odwrotność bez dzielenia

Aby wyznaczyć dla bez dzielenia(!), można zastosować metodę Newtona do funkcji . Pokaż, że na -tym kroku iteracji,

Dla jakich metoda będzie zbieżna do , a dla jakich nie? Oceń, ile iteracji potrzeba do spełnienia warunku , gdy ,

Rozwiązanie

Ćwiczenie

Zaimplementuj metodę bisekcji. Sprawdź, jak będzie działać m.in. dla funkcji

  • ,
  • ,
  • (wzór A),
  • (wzór B),
  • (wzór C),
  • (wzór D),

gdy tolerancję błędu zadasz na poziomie .

Metoda bisekcji ma kłopoty, gdy funkcja zadana jest wzorem D.
Residuum też jest duże, gdy zadana jest wzorem D.

Jak wyjaśnić te wyniki? Czy możesz już być pewien, że masz dobrą implementację?

Rozwiązanie

Ćwiczenie

Wskaż wszystkie wartości , dla jakich metoda Newtona będzie zbieżna do rozwiązania równania

Wyznacz wartość , z którego startując powinieneś dostać ciąg oscylujący . Sprawdź eksperymentalnie, czy tak jest rzeczywiście.

Wskazówka
Rozwiązanie