~~NOCACHE~~
~~REVEAL theme=simple&size=1024x800~~

====== Lab. 5 Rozwiązywanie równań nieliniowych ======

===== Metody iteracyjne =====

  * Metody dwupunktowe 
    * bisekcji (połowienia)
    * siecznych 
    * regula falsi
  * Metody jednopunktowe
    * **stycznych (Newtona)**
    * **metoda iteracji prostych (punktu stałego)**

===== Metoda Newtona =====

Metoda stycznej (Newtona-Raphsona) uwzględnia kształt funkcji 

{{ zajecia:mn1_2021_2:metoda_newtona.png?600 |  }}

===== =====

Równanie stycznej w punkcie $x_0$

$$y(x)=f^{\prime}\left(x_{o}\right)\left(x-x_{o}\right)+f\left(x_{o}\right)$$

Przybliżenie, w miejscu przecięcia stycznej z osią OX - metoda Newtona-Raphsona

$$x_{i+1}=x_{i}-\frac{f\left(x_{i}\right)}{f^{\prime}\left(x_{i}\right)}$$

Warunek stopu: $|x_{x+1} - x_i|<\epsilon$ lub $|f(x_i)| < \epsilon$

=====  =====

  * szybciej zbieżna niz bisekcja (kwadratowa)
  * nie zawsze zbieżna, zbieżna gdy $f'$ ma taki sam znak co $f''$
  * wymagana analityczna wartość pochodnej $f'$, przybliżenie za pomocą metod różnicowych prowadzi do metody stycznych
    
{{ zajecia:mn1_2021_2:newton_problems.png?600 |  }}

===== Przykład =====

Funkcja $f(x) = x^3 + x - 1$

{{ zajecia:mn1_2021_2:fun_x3_plot.png?400 |  }}

Pochodna $f'(x) = 3x^2 + 1$

Wzór iteracyjny
$$x_{i+1}=x_{i}-\frac{f\left(x_{i}\right)}{f^{\prime}\left(x_{i}\right)} = x_i - \frac{x_i^3 + x - 1}{3x_i^2+1} = \frac{2x^3+1}{3x^2+1}$$

===== =====

<file C newton.c>
#include<stdio.h>
#include<math.h>
#define EPS 1e-6

float f(float x)
{
   return x * (x * x  + 1) - 1;
}

int main()
{
   float x0, x1;
   int i, n=100;

   printf("Punkt startowy : ");
   scanf("%f", &x0);

   for (i = 0; i < n; i++)
   {
      x1 = x0 - f(x0) / (3*x0*x0 + 1);
      if (fabs(x1 - x0) < EPS) break;
      x0 = x1;
   }

   if (i == n) printf("Nie znaleziono rozwiazania\n");   
   else 
   {
      printf("x = %f\n", x1);
      printf("iterations %d\n", i+1);
   }
}
</file>


===== Metoda iteracji prostych =====

Równanie $f(x)=0$ sprowadzamy do postaci 

$$x = g(x)$$

wówczas otrzymujemy zaleznośc rekurencyjną

$$x_{i+1} = g(x_{i})$$

===== =====

  * metoda może nie być zbieżna, zależy to od:
    * punktu startowego
    * postaci funkcji $g(x)$

{{ zajecia:mn1_2021_2:iteracje_proste.png?600 |  }}

===== Przykład =====

Funkcja $f(x) = x^3 + x - 1$

$$x = 1 - x^3 = g(x)$$

Wzór iteracyjny
$$x_{i+1}= 1 - x^3_{i} $$

===== =====

<file C fixed_point.c>
#include<stdio.h>
#include<math.h>
#define EPS 1e-6

int main()
{
   float x0, x1;
   int i, n=100;

   printf("Punkt startowy : ");
   scanf("%f", &x0);

   for (i = 0; i < n; i++)
   {
      x1 = -x0*x0*x0 + 1;
      // printf("%f\n", x1);
      if (fabs(x1 - x0) < EPS) break;
      x0 = x1;
   }

   if (i == n) printf("Nie znaleziono rozwiazania\n");   
   else 
   {
      printf("x = %f\n", x1);
      printf("iterations %d\n", i+1);
   }
}
</file>

===== Inna postać funkcji g(x) =====

$$x = 1 - x^3$$

  * $g(x) = 1 - x^3$    rozbieżna
  * $g(x) = \sqrt[3]{1-x}$
  * $g(x) = \frac{1+2x^3}{1+3x^2}$

Ćw: porównaj zbieżność metod dla punktu startowego $0.5$

===== =====

| $g(x) = 1 - x^3$ | $g(x) = \sqrt[3]{1 - x}$ | $g(x) = \frac{1+2x^3}{1+3x^2}$ |
| {{ zajecia:mn1_2021_2:fixed_point_ex1.png?350 |  }} | {{ zajecia:mn1_2021_2:fixed_point_ex2.png?350 |  }} | {{ zajecia:mn1_2021_2:fixed_point_ex3.png?350 |  }} |

Zbieżność gdy $|g'(x)| < 1$ w przedziale izolacji


===== Zadanie  ====

Napisz program wyznaczający wartość $\sqrt{a}$ dla $a>0$ korzystając z metody Newtona (stycznych) oraz metody punktu stałego (iteracji prostej).
Zadanie sprowadza się do znalezienia pierwiastków równania $f(x) = x^2 - a$.
Wyprowadź wzór iteracyjny dla obu metod oraz zaimplementuj program wg. poniższej specyfikacji.
Przyjmij dokładność obliczeń pierwiastka $\epsilon=10^{-6}$.

Dane wejściowe:
  * wartość $a$ 
  * początkowe przybliżenie pierwiastka $x_0$
Dane wyjściowe (dla każdej z metod osobno):
  * przybliżona wartość $\sqrt{a}$ lub informacja o braku zbieżności 
  * ilość wykonanych iteracji 
  * wartość $f(x)$ wyznaczoną dla znalezionego pierwiastka
  * błąd względny wyniku, gdzie wartość dokładna to wynik działania funkcji ''sqrt'' z biblioteki ''math.h''

===== Dodatkowe ćwiczenia =====

**Ćw. 1**

Napisz program wyznaczający wartość $\sqrt[N]{a}$ dla $a>0$ korzystając z metody Newtona (stycznych) oraz z metody iteracji prostych.
Zadanie sprowadza się do znalezienia pierwiastków równania $f(x) = x^N - a$. 

**Ćw. 2**

Napisz program wyznaczający za pomocą metody Newtona oraz metody iteracji prostych pierwiastki równania 

$$x^{2}-4 x \sin x+(2 \sin x)^{2}=0$$