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)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]$
5. jeżeli $f(x_0)$ ma ten sam znak co $f(b)$ to powtarzamy szukanie pierwiastka w przedziale $[a, x_0]$

• (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

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

• zatrzymanie algorytmu gdy $|x_{i}-x_{i-1}|<\epsilon$ lub gdy $f(x_i) < \epsilon$
• proces może być rozbieżny (ustalenie maks. liczby iteracji lub zatrzymanie gdy $|x_{i}-x_{i-1}|$ rośnie)

Zadanie:

Zaimplementuj program znajdujący rozwiązanie równania postaci

$$x = \sin{x} + \frac{1}{4}$$

za pomocą metod bisekcji oraz siecznych

Program wczytuje wartości początkowe $a$ i $b$ po czym wypisuje dla każdej z metod:

• przybliżoną wartość miejsca zerowego $x_0$ lub informację o braku znalezienia pierwiastka lub o tym, że proces jest rozbieżny
• wartość funkcji $f(x_0)$ w wyznaczonym punkcie
• wartość zastosowanej precyzji obliczeń $\epsilon$
• ilość wykonanych iteracji

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.