Szukanie miejsc zerowych
$$f(x)=0$$
Jak to zrobić?
Problem (1)
Problem (2)
Zadanie jest proste:
- Mamy funkcję $f(x)$ ciągłą i taką, że na końcach pewnego przedziału $\lbrack A,B\rbrack$ $f(A)f(B) < 0$. Zatem, funkcja ta zmienia znak w przedziale $\lbrack A,B\rbrack$ (co najmniej raz) ma zatem (co najmniej jedno) miejsce zerowe w tym przedziale.
- Przedział $\lbrack A,B\rbrack$ dzielimy na pół (wyznaczając odpowiednio punkt $C$).
- Odrzucamy ten z przedziałów $\lbrack A,C\rbrack$, $\lbrack C,B\rbrack$ w którym funkcja nie zmienia znaku (to znaczy ma ten sam znak na końcach przedziału).
- Postępowanie prowadzimy tak długo, aż długość przedziału $\lbrack A,B\rbrack$ będzie mniejsza od zadanej liczby $\varepsilon$.
Schemat blokowy
graph LR
start([Start]) --> ala["C=(A+B)/2"]
ala --> przedzial{"f(a)*f(c)<0"}
przedzial --> |TAK| Be[B = C]
przedzial --> |NIE| Aa[A = C]
Be --> koniec{"fabs(A-B)> EPS"}
Aa --> koniec
koniec --> |TAK| ala
koniec --> |NIE| stop([STOP])
Dane
wejściowe
Końce przedziału, w którym funkcja zmienia znak
double A, B;Dokładność obliczeń
double eps;
robocze
double C;wyniki
- Współrzędna punktu najbliższa miejscu zerowemu
Co zrobić gdy w zadanym przedziale funkcja znaku nie zmienia?
Ba!
Kod algorytmu
do
{
C = ( A + B ) / 2.;
if ( f(C) == 0 )
// wynikiem jest C
else if ( f(A) * f(C) > 0 )
A = C;
else
B = C;
}while ( fabs(A - B) > eps );
// wynikiem będzie ( A + B ) / 2.;
Jak użyć tego algorytmu?
#include <stdio.h>
int main(int argc, char **argv)
{
double A, B, eps;
A = 1;
B = 2;
eps = 0.001;
double C;
do
{
C = ( A + B ) / 2.;
if ( f(C) == 0 )
// wynikiem jest C
else if ( f(A) * f(C) > 0 )
A = C;
else
B = C;
}while ( fabs(A - B) > eps );
// wynikiem będzie ( A + B ) / 2.;
return 0;
}
Co z funkcją f?
- Funkcja jednej zmiennej
x - argument typu zmiennoprzecinkowego
- wynik typu zmiennoprzecinkowego
double f(double x)
{
return exp(x) - sin(x);
}
czyli szukamy rozwiązania problemu
$$\sin(x)=e^{x}$$
Uwaga
Kod funkcji musimy dodać przed main()
Co to znaczy „wynikiem jest/będzie”?
W miejscu tych komentarzy wydrukujemy podaną wartość
Teraz algorytm „zamkniemy w funkcji”
double pol(double A, double B, double eps)
{
double C;
do
{
C = ( A + B ) / 2.;
if ( f(C) == 0 )
// wynikiem jest C
else if ( f(A) * f(C) > 0 )
A = C;
else
B = C;
}while ( fabs(A - B) > eps );
// wynikiem będzie ( A + B ) / 2.;
}
Co to znaczy „wynikiem jest/będzie”?
W tym miejscu wstawimy polecenie return (z odpowiednim wyrażeniem)
double pol(double A, double B, double eps)
{
double C;
do
{
C = ( A + B ) / 2.;
if ( f(C) == 0 )
return C;// wynikiem jest C
else if ( f(A) * f(C) > 0 )
A = C;
else
B = C;
}while ( fabs(A - B) > eps );
return ( A + B ) / 2.;// wynikiem będzie ( A + B ) / 2.;
}
Kod programu
#include <math.h>
#include <stdio.h>
double f(double x)
{
return exp(x) - sin(x);
}
double pol(double A, double B, double eps)
{
double C;
do
{
C = ( A + B ) / 2.;
if ( f(C) == 0 )
return C; // wynikiem jest C
else if ( f(A) * f(C) > 0 )
A = C;
else
B = C;
}while ( fabs(A - B) > eps );
return ( A + B ) / 2.; // wynikiem będzie ( A + B ) / 2.;
}
int main(int argc, char **argv)
{
double x;
x = pol(1., 3., 0.00001);
printf("miejscemn zerowym jest %f\n", x);
printf( "wartość funkcji %f\n", f(x) );
return 0;
}
Udoskonalenia kodu
- Co zrobić gdy w pierwszym wywołaniu funkcji
pol()nie jest spełniony warunek $f(A)*f(B)<0$?
Pojawiły się pomysły, żeby zaraz po wejściu do funkcji sprawdzić ten warunek i:
- Wypisać komunikat „Nie ma miejsc zerowych!”
- Żeby funkcja zwracała wartość $-1$.
Ale oba powyższe pomysły są do nieczego: co będzie gdy miejsce zerowe funkcji wypadnie w punkcie $-1$? A kto przeczyta tekst komunikatu?
Można tak
if ( f(A) * f(B) > 0)
return INFINITY;
A po wyjściu z funkcji
x = pol(A, B, eps);
if (x == INFINITY)
printf("Funkcja nie ma miejsc zerowych\n") // lub cokolwiek innego