Lab. 4 Rozwiązywanie równań nieliniowych

Znajdowanie pierwiastków

Iteracyjne metody znajdowania miejsc zerowych funkcji

$$f(x) = 0 $$

Problemy:

• lokalizacja pierwiastka (punkt startowy, przedział izolacji)
• zbieżność procesu iteracyjnego, szybkość zbieżności

Metody iteracyjne

• Metody dwupunktowe
  • bisekcji (połowienia)
  • siecznych
  • regula falsi
• Metody jednopunktowe
  • stycznych (Newtona)
  • metoda iteracji prostych

Przedział izolacji

• gdy $f(a) \cdot f(b) < 0$ dla funkcji ciągłych to istnieją pierwiastki w $[a, b]$
• gdy pochodna nie zmienia znaku w $[a, b]$ to istnieje jeden pierwiastek

Metoda bisekcji

1. wybieramy przedział $[a,b]$ taki aby $f(a)f(b)<0$
2. dzielimy przedział na połowy
   $$x_{0}=a+\frac{b-a}{2}$$
3. jeżeli $|f(x_0)| < \epsilon$ to $x_0$ jest znalezionym pierwiastkiem
4. jeżeli $f(x_0)$ ma ten sam znak co $f(a)$ to powtarzamy szukanie pierwiastka w przedziale $[x_0, b]$ (krok 2)
5. jeżeli $f(x_0)$ ma ten sam znak co $f(b)$ to powtarzamy szukanie pierwiastka w przedziale $[a, x_0]$ (krok 2)

• (prawie) zawsze zbieżna
• wolno zbieżna (zbieżność liniowa)
• nie uwzględnia kształtu funkcji w poszukiwaniu pierwiastka
• często stosowana do znalezienia przybliżonego przedziału pierwiastka dla szybciej zbieżnych metod

Przykład

Miejsca zerowe funkcji $f(x) = x^2 - 1$

Sprawdź przedziały izolacji: $[0, 1.5]$, $[2, 3]$.

Jaki jest problem z drugim przedziałem?

Czy proces jest zawsze zbieżny?

bisekcja.c

#include<stdio.h>
#include<math.h>

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

int main()
{
   float a, b, x0, eps;
   int i;
   
   printf("Podaj przedzial izolacji:");
   scanf("%f%f", &a, &b);

   eps = 1e-6;
   
   i=0;
   while(fabs(a-b)>eps)
   {
      i++;
      x0 = (a+b)/2;
      printf("%f %f %f\n", a, b, b-a);
      
      if (fabs(f(x0)) < eps) break;
      
      if(f(a)*f(x0) < 0) b=x0;
      else               a=x0;
   }
   
   printf("x0 = %f\niterations %d\n", x0, i);
   printf("f(%g)=%g\n", x0, f(x0));
   return 0;
}

Problemy bisekcji

Błąd metody

dla $n$ iteracji przedział izolacji maleje do rozmiaru

$$ \frac{1}{2^n}(b - a) $$

metoda jest zbieżna liniowo, ze stałą asymptotyczną błedu $\frac{1}{2}$.

Metoda siecznych

Dla dwóch wartości początkowych $x_0$ i $x_1$ kolejne przybliżenie za pomocą linii prostej (siecznej)

$$x_{n+1}=x_{n}-f\left(x_{n}\right)\left(\frac{x_{n}-x_{n-1}}{f\left(x_{n}\right)-f\left(x_{n-1}\right)}\right)$$

• w metodzie siecznych nie musi byc spełnione $f(x_n)\cdot f(x_{n+1}) < 0$, jednak zaleca się aby początkowe punkty $x_0, x_1$ spełniały tą zależność
• zatrzymanie algorytmu gdy $f(x_i) < \epsilon$ lub gdy $|x_{i}-x_{i-1}|<\epsilon$ (dla małych przedziałow $[a, b]$, w okolicy rozwiązania)
• proces może być rozbieżny, wówczas zatrzymanie algorytmu można zabezpieczyć przez:
  • ustalenie maksymalnej liczby iteracji
  • zatrzymanie gdy $|x_{i}-x_{i-1}|$ rośnie

Regula falsi

Metoda siecznych ze stałym punktem.

Złożenia:

• przedział $[a,b]$ jest przedziałem izolacji i ma jeden pierwiastek
• pierwsza i druga pochodna na odcinku $[a,b]$ nie zmienia znaku

Algorytm: regula falsi

1. wybieramy przedział $[a,b]$ taki aby $f(a)f(b)<0$
2. wyznaczamy przybliżenie pierwiastka

$$x_0= b-f\left(b\right)\left(\frac{b-a}{f\left(b\right)-f\left(a\right)}\right)$$

1. jeżeli $|f(x_0)| < \epsilon$ to $x_0$ jest znalezionym pierwiastkiem (koniec)
2. jeżeli $f(x_0) f(a) < 0$ to wyznaczamy kolejne przybliżenie ustawiając $b=x_0$ (krok 2)
3. w przeciwnym wypadku wyznaczamy kolejne przybliżenie ustawiając $a=x_0$ (krok 2)

Zadanie 4

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

Dodatkowe ćwiczenia

Ćw. 1

Napisz program znajdujący pierwiastki rzeczywiste jednego z poniższych równań z dokładnością $\epsilon=1\cdot10^{-6}$

• $x-2=\sqrt[3]{x}$
• $10x = e^{-x}$
• $x^2 - 6x - 8 = \ln{x}$

Ćw. 2 Rozwiąż zadanie z zajęć używając metody Regula falsi, która jest modyfikacją metody siecznych polegająca na tym, że jeden punktów $a$ lub $b$ jest stały.

Jakie warunki musi spełniać funkcja na odcinku $[a, b]$ aby ta metoda znalazła pierwiastek.