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

Zał: znamy pochodną funkcji $f'(x)$

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 niż bisekcja (zbieżność 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

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

float fp(float x)
{
   return 3.0 * x * x + 1.0;
}

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

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

   while(fabs(f(x0)) > EPS && i < n)	
   {
      x1 = x0 - f(x0) / fp(x0);
      printf("%d %f\n", i+1, x1);
      x0 = x1;
      i++;
   }

   if (i == n) printf("Nie znaleziono rozwiazania\n");   
   else 
   {
      printf("x = %f\n", x1);
      printf("ilosc iteracji = %d\n", i);
   }
}

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

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

Ćwiczenie: zaimplementuj program znajdujący miejsce zerowe $f(x) = x^3 + x - 1$ za pomocą metody iteracji prostej.

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

Ćwiczenie: 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

Zadanie 5

Treść zadania znajduje się w Moodle pod adresem Zadanie 5

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