MN02LAB: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 1: Linia 1:
 +
 
<!--  
 
<!--  
Konwertowane  z pliku LaTeX przez latex2mediawiki, zob. http://www.ii.uj.edu.pl/&nbsp;pawlik1/latex2mediawiki.php
+
Konwertowane  z pliku LaTeX przez latex2mediawiki, zob. http://www.ii.uj.edu.pl/&nbsp;pawlik1/latex2mediawiki.php.
 +
Niezb�dne rozszerzenia i modyfikacje oryginalnego latex2mediawiki
 +
wprowadzi� przykry@mimuw.edu.pl
 
-->
 
-->
 
   
 
   
=Ćwiczenia: równania nieliniowe skalarne=
+
=Równania nieliniowe skalarne=
  
 
<div style="margin-top:1em; padding-top,padding-bottom:1em;">
 
<div style="margin-top:1em; padding-top,padding-bottom:1em;">
Linia 25: Linia 28:
 
Ciekawy zbiór o charakterze fraktalnym powstaje w wyniku zastosowania metody
 
Ciekawy zbiór o charakterze fraktalnym powstaje w wyniku zastosowania metody
 
Newtona do rozwiązania równania <math>\displaystyle z^n-1=0</math> w dziedzinie zespolonej. Punkt <math>\displaystyle z_0 =
 
Newtona do rozwiązania równania <math>\displaystyle z^n-1=0</math> w dziedzinie zespolonej. Punkt <math>\displaystyle z_0 =
(x_0,y_0)</math> należy do <strong>basenu zbiezności metody</strong>, jeśli metoda Newtona jest
+
(x_0,y_0)</math> należy do <strong>basenu zbieżności metody</strong>, jeśli startująca z niego metoda Newtona jest zbieżna do (jakiegokolwiek) pierwiastka w/w równania. Kolor odpowiadający <math>\displaystyle z_0</math> jest określany na podstawie liczby iteracji potrzebnych metodzie do
z nim zbieżna do (jakiegokolwiek) pierwiastka w/w równania. Kolor odpowiadający
 
<math>\displaystyle z_0</math> jest określany na podstawie liczby iteracji potrzebnych metodzie do
 
 
zbieżności.
 
zbieżności.
  
 
Zupełnie miłym (i estetycznie wartościowym) doświadczeniem jest napisanie
 
Zupełnie miłym (i estetycznie wartościowym) doświadczeniem jest napisanie
programu w Octave, który jak poniżej wyświetla baseny zbieżności metody Newtona.
+
programu w Octave, który wyświetla baseny zbieżności metody Newtona, takie jak na rysunku poniżej.
  
[[Image:MNfraktal.png|thumb|450px|center|Basen zbieżności metody Newtona w okolicy początku układu
+
[[Image:MNfraktal.png|thumb|550px|center|Basen zbieżności metody Newtona w okolicy początku układu
 
współrzędnych, dla równania <math>\displaystyle z^5-1=0</math>]]
 
współrzędnych, dla równania <math>\displaystyle z^5-1=0</math>]]
  
 
<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:#efe"> 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>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  
Linia 48: Linia 49:
  
 
<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:#efe"> 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
 
iteracji Newtona na <strong>wszystkich pikselach jednocześnie</strong>. W tym celu musisz
 
skorzystać z prowadzenia działań na całych macierzach. </div>
 
skorzystać z prowadzenia działań na całych macierzach. </div>
Linia 66: Linia 67:
  
 
<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:#efe"> 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ę. To oczywiście
+
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.  
będzie działać. W dodatku praktycznie tak samo szybko jak drugi sposób, w którym po prostu
+
</div>
wyliczysz na karteczce wzór na iterację dla <strong>tej konkretnej funkcji, <math>\displaystyle F(x) =
 
x^2-a</math></strong> i potem go zaimplementujesz. Jednak
 
drugie podejście jest tutaj godne polecenia, bo ma na sobie znak charakterystyczny dla numeryki: niech
 
wszystko, co programujesz będzie tak proste, jak tylko możliwe (ale nie
 
prostsze)! </div>
 
 
</div></div>
 
</div></div>
  
Linia 84: Linia 80:
 
</math></center>
 
</math></center>
  
Jest to, znana już w starożytności, metoda Herona. Teraz jest jasne, dlaczego
+
Jest to, znana już w starożytności, <strong>metoda Herona</strong>. Teraz jest jasne, dlaczego zbiega tak szybko do <math>\displaystyle \sqrt{a}</math>.
zbiega tak szybko do <math>\displaystyle \sqrt{a}</math>.
 
 
Dla <math>\displaystyle a\neq 0</math>, spełnione są założenia twierdzenia o zbieżności metody Newtona,
 
Dla <math>\displaystyle a\neq 0</math>, spełnione są założenia twierdzenia o zbieżności metody Newtona,
 
więc
 
więc
Linia 92: Linia 87:
 
</math></center>
 
</math></center>
  
co właśnie tłumaczy się jako podwajanie liczby dokładnych cyfr
+
co właśnie tłumaczy się jako podwajanie liczby dokładnych cyfr znaczących wyniku po każdej iteracji.
znaczących wyniku.
 
  
 
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ę?), co mniej więcej trzy kroki będziemy więc
+
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...)
dostawali kolejne zero dokładnego wyniku <math>\displaystyle x^*=0</math>.
+
 
+
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?
 +
 
 
</div></div></div>
 
</div></div></div>
  
Linia 105: Linia 100:
 
<div class="exercise">
 
<div class="exercise">
  
Aby wyznaczyć <math>\displaystyle 1/a</math> dla <math>\displaystyle a>0</math> bez dzielenia(!) można zastosować metodę Newtona
+
Aby wyznaczyć <math>\displaystyle 1/a</math> dla <math>\displaystyle a>0</math> bez dzielenia(!), można zastosować metodę Newtona
 
do funkcji <math>\displaystyle f(x) = 1/x - a</math>. Pokaż, że na <math>\displaystyle k</math>-tym kroku iteracji,
 
do funkcji <math>\displaystyle f(x) = 1/x - a</math>. Pokaż, że na <math>\displaystyle k</math>-tym kroku iteracji,
 
<center><math>\displaystyle  
 
<center><math>\displaystyle  
Linia 117: Linia 112:
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"><div style="margin-left:1em">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"><div style="margin-left:1em">   
Proste ćwiczenie z analizy. Warunkiem zbieżności jest oczywiście (ze względu na
+
Proste ćwiczenie z [[Analiza_matematyczna_1|analizy matematycznej]]. Warunkiem zbieżności jest oczywiście (ze względu na
 
równość w wyrażeniu na błąd iteracji powyżej) <math>\displaystyle |ax_0 - 1| < 1</math>, to znaczy  
 
równość w wyrażeniu na błąd iteracji powyżej) <math>\displaystyle |ax_0 - 1| < 1</math>, to znaczy  
 
<center><math>\displaystyle 0 < x_0 < \frac{2}{a}.</math></center>
 
<center><math>\displaystyle 0 < x_0 < \frac{2}{a}.</math></center>
Linia 137: Linia 132:
 
gdy tolerancję błędu zadasz na poziomie <math>\displaystyle 10^{-10}</math>.
 
gdy tolerancję błędu zadasz na poziomie <math>\displaystyle 10^{-10}</math>.
  
[[Image:MNbisekcjawblad.png|thumb|450px|center|Metoda bisekcji ma kłopoty, gdy funkcja zadana jest
+
[[Image:MNbisekcjawblad.png|thumb|550px|center|Metoda bisekcji ma kłopoty, gdy funkcja zadana jest
 
wzorem D.]]
 
wzorem D.]]
[[Image:MNbisekcjawresid.png|thumb|450px|center|Residuum też jest duże, gdy <math>\displaystyle f</math> zadana jest
+
[[Image:MNbisekcjawresid.png|thumb|550px|center|Residuum też jest duże, gdy <math>\displaystyle f</math> zadana jest
 
wzorem D.]]
 
wzorem D.]]
  
Linia 149: Linia 144:
  
 
Jeśli nie pomylisz się, metoda powinna zbiegać bez problemów do zera funkcji
 
Jeśli nie pomylisz się, metoda powinna zbiegać bez problemów do zera funkcji
<math>\displaystyle \sin</math>, dawać komunikat o błędzie dla <math>\displaystyle \sin^2</math> (bo nie ma przeciwnych znaków).
+
<math>\displaystyle \sin(x)</math>, dawać komunikat o błędzie dla <math>\displaystyle \sin^2(x)</math> (bo nie ma przeciwnych znaków).
  
Zapewne zauważyłeś, że wzory A i B są matematycznie równoważne, podobnie zresztą
+
Zapewne zauważyłeś, że wzory A i B są matematycznie równoważne, podobnie zresztą jak wzory C i D. Niestety, tylko wzór A i C dają w efekcie dobre przybliżenia miejsca zerowego, podczas gdy wzory B i D prowadzą do oszacowania na miejsce zerowe, które <strong>w ogóle nie zawierają</strong> prawdziwego miejsca zerowego.
jak wzory C i D. Niestety, tylko wzór A i C dają w efekcie dobre przybliżenia
 
miejsca zerowego, podczas gdy wzory B i D prowadzą do oszacowania na miejsce
 
zerowe, które <strong>w ogóle nie zawierają</strong> prawdziwego miejsca zerowego.
 
  
Wyjaśnieniem tego fenomenu jest zjawisko redukcji cyfr przy odejmowaniu.
+
Wyjaśnieniem tego fenomenu jest zjawisko redukcji cyfr przy odejmowaniu, o którym mowa w następnym wykładzie.
  
 
Jeśli chodzi o pewność... No cóż, sprawdziłeś, że <strong>działa</strong> w przypadkach,
 
Jeśli chodzi o pewność... No cóż, sprawdziłeś, że <strong>działa</strong> w przypadkach,
dla których spodziewałeś się, że będzie działać. Że tam, gdzie spodziewałeś się
+
dla których oczekiwałeś, że będzie działać. Że tam, gdzie spodziewałeś się
 
kłopotów, lub komunikatu o błędzie --- tak rzeczywiście się stało. Wreszcie,
 
kłopotów, lub komunikatu o błędzie --- tak rzeczywiście się stało. Wreszcie,
 
potwierdziłeś, że zachowanie metody jest zgodne z jej znanymi właściwościami.
 
potwierdziłeś, że zachowanie metody jest zgodne z jej znanymi właściwościami.
Linia 181: Linia 173:
  
 
<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:#efe"> 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:
  
Linia 196: Linia 188:
 
Dla <math>\displaystyle -X_0 < x_0 < X_0</math> mamy zbieżność. Dla <math>\displaystyle |x_0| = |X_0|</math> oscylacje, dla
 
Dla <math>\displaystyle -X_0 < x_0 < X_0</math> mamy zbieżność. Dla <math>\displaystyle |x_0| = |X_0|</math> oscylacje, dla
 
większych wartości --- rozbieżność. Jednak w eksperymencie wszystko zależy od
 
większych wartości --- rozbieżność. Jednak w eksperymencie wszystko zależy od
tego, jak dokładnie wyznaczyliśmy <math>\displaystyle X_0</math>. Na przykład, mój solver w Octave
+
tego, jak dokładnie wyznaczyliśmy <math>\displaystyle X_0</math>. Na przykład, funkcja <code style="color: #006">fzero</code> w Octave
wyznaczył wartość <math>\displaystyle X_0</math>, dla której metoda Newtona dała następujący ciąg:
+
wyznaczyła (przy standardowych ustawieniach) numeryczne przybliżenie <math>\displaystyle X_0</math>, dla którgo metoda Newtona dała następujący ciąg:
<div class="output" style="background-color:#e0e8e8; padding:1em"><pre>
+
<div style="font-family: monospace; white-space: pre; border-style: dashed; border-width: thin; border-color: black; margin: 1em; padding:1em; color: #444; background-color:#fdfdfd;"><nowiki>Iteracja:  1,  x = -1.39175
 
Iteracja:  1,  x = -1.39175
 
 
Iteracja:  2,  x = 1.39175
 
Iteracja:  2,  x = 1.39175
 
Iteracja:  3,  x = -1.39175
 
Iteracja:  3,  x = -1.39175
Linia 231: Linia 221:
 
Iteracja:  46,  x = inf
 
Iteracja:  46,  x = inf
 
Iteracja:  47,  x = nan
 
Iteracja:  47,  x = nan
</pre></div>
+
</nowiki></div>
 
   
 
   
 
</div></div></div>
 
</div></div></div>

Wersja z 20:08, 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