View as presentation
→ Slide 1

Lab. 5 Rozwiązywanie równań nieliniowych

→ Slide 2

Metody iteracyjne

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

Metoda Newtona

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

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

→ Slide 4

Przykład

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

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}$$

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);
   }
}
→ Slide 5

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)$

→ Slide 6

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} $$

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);
   }
}
→ Slide 7

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}$

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

→ Slide 8

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
→ Slide 9

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$$