[ Pobierz całość w formacie PDF ]
warunkowych.
" Jeśli wyborem steruje wartość typu porządkowego, lepszym rozwiązaniem jest
użycie instrukcji wyboru case.
52 Turbo Pascal programowanie
RozwiÄ…zujemy
dowolne równanie
Problem rozwiązania dowolnego równania nie należy bynajmniej do zadań typu
kamienia filozoficznego czy uniwersalnego rozpuszczalnika. Chociaż dla pewnych klas
równań istnieją dawno opracowane wzory i metody, spora grupa równań nieliniowych
nie daje się rozwiązać na papierze w sposób dokładny. Nie oznacza to jednak, że nie
można ich w ogóle rozwiązać: kwestii przybliżonego rozwiązywania równań nielinio-
wych poświęcono z niezłym skutkiem spory dział matematyki znany jako metody
numeryczne. W niniejszym rozdziale spróbujemy zademonstrować jedną z najprost-
szych metod rozwiązywania równań nieliniowych tak zwaną metodę bisekcji. Jest
ona na tyle prosta, że praktycznie nie wymaga znajomości skomplikowanej matematyki
(a jedynie logicznego myślenia), a jednocześnie całkiem skuteczna.
f(x)
c4 c3 c1 b
x
a c2
c
Rysunek 9. Zasada działania metody bisekcji
Załóżmy, że chcemy znalezć miejsce zerowe funkcji f(x) przedstawionej powyżej.
Szukamy więc takiego punktu c na osi x, dla którego f(c) = 0. Wybierając na osi x dwa
punkty a i b takie, by wartości f(a) i f(b) miały przeciwne znaki, możemy z pewnością
stwierdzić, że funkcja ma pomiędzy a i b co najmniej jedno miejsce zerowe (gdyż musi
gdzieś przeciąć oś x). Podzielmy przedział pomiędzy a i b na dwie równe części. War-
tość funkcji w nowo uzyskanym punkcie c1 ma nadal znak przeciwny do f(a), a zatem
miejsce zerowe leży gdzieś pomiędzy a i c1. Podzielmy nowo uzyskany przedział na
połowy: tym razem okazuje się, że wartość funkcji w punkcie c2 ma znak przeciwny do
Rozwiązujemy dowolne równanie 53
f(c1), a więc miejsce zerowe leży pomiędzy c1 a c2. Wykonując kolejne podziały
dojdziemy w końcu do punktu... no, właśnie. Zauważ, że z każdym kolejnym podziałem
zbliżamy się do miejsca zerowego coraz wolniej: za każdym razem przedział poszuki-
wania zawężany jest dwukrotnie, tak więc (teoretycznie) dokładne położenie miejsca
zerowego (odpowiadające przedziałowi o zerowej szerokości, czyli pojedynczemu
punktowi) osiągniemy po nieskończonej liczbie podziałów. Chyba nie masz zamiaru
czekać aż tak długo!
Rozwiązaniem tego problemu jest właściwe sformułowanie tzw. kryterium zakończenia
obliczeń lub kryterium stopu. W naszym przypadku kolejne cykle podziałów (zwane
fachowo iteracjami) będziemy prowadzili tak długo, aż bezwzględna wartość funkcji
w punkcie cn zmaleje poniżej zadanego progu.
Spróbujmy zapisać w bardziej formalny sposób pojedynczy podział:
poczÄ…tek
wyznacz punkt c w połowie odległości pomiędzy a i b
jeżeli f(a) ma znak różny od f(c), to przenieś punkt b do punktu c
w przeciwnym przypadku przenieÅ› punkt a do punktu c
koniec
Ale jak zabrać się za wykonywanie kolejnych podziałów? Oczywiście nie będziesz mu-
siał wielokrotnie wpisywać odpowiednich instrukcji: zamiast tego wykorzystasz do ich
cyklicznego wykonywania instrukcję pętli.
Spośród trzech dostępnych w Pascalu struktur pętli do realizacji naszego zadania
odpowiednie są dwie while i repeat (trzecią pętlą, for, zajmiemy się nieco
pózniej). Należą one do grupy pętli sterowanych warunkiem, co oznacza, że wykonują
się tak długo, jak długo spełnione będzie odpowiednie kryterium (while powtarzaj,
dopóki...) lub do momentu, kiedy zostanie ono spełnione (repeat powtarzaj, aż...).
Nie trzeba chyba dodawać, że owym kryterium będzie właśnie nasze kryterium stopu:
zakończ iteracje, jeśli wartość bezwzględna f(c) jest mniejsza od zadanego progu.
Której instrukcji użyć? W zasadzie w naszym przypadku jest to obojętne. Działanie
pętli while i repeat jest bardzo zbliżone, zaś różnica sprowadza się do faktu, że
w pierwszej z nich warunek przerwania pętli sprawdzany jest na początku:
while warunek
do instrukcja
zaś w drugiej na końcu pętli:
repeat instrukcja
until warunek
W konsekwencji instrukcje tworzące zawartość pętli repeat muszą wykonać się co
najmniej raz, zaś w przypadku pętli while mogą nie wykonać się ani razu (jeśli waru-
nek będzie od razu spełniony). Ponadto musisz pamiętać, że sformułowanie warunku
jest dla obu pętli dokładnie przeciwne (pętla while wykonuje się tak długo, jak długo
54 Turbo Pascal programowanie
warunek jest spełniony, repeat tak długo, jak długo jest niespełniony). Zapamiętaj
również, że umieszczając kilka instrukcji w pętli while musisz połączyć je w instrukcję
złożoną słowami begin i end, zaś w przypadku pętli repeat konieczność ta nie
występuje (ogranicznikami instrukcji złożonej są tu słowa repeat i until).
Spróbujmy zapisać nasz algorytm z wykorzystaniem pętli repeat. Będzie on wyglądał
mniej więcej tak:
poczÄ…tek
wprowadz wartości krańców przedziału i dokładności
powtarzaj
wyznacz punkt c w połowie odległości pomiędzy a i b
jeżeli f(a) ma znak różny od f(c), to przenieś punkt b do punktu c
w przeciwnym przypadku przenieÅ› punkt a do punktu c
aż do momentu, gdy wartość bezwzględna f(c) jest mniejsza od zadanego progu
wypisz znalezione miejsce zerowe
koniec
Załóżmy, że chcemy rozwiązać równanie
1 - esin xÅ"cos x = 0
posiadające (jak nietrudno obliczyć na kartce) pierwiastek w punkcie x = 0. Tłumacząc
powyższy schemat na angielski (i Pascal) otrzymamy następujący program:
program Bisekcja;
var
begin
writeln('Program znajduje miejsce zerowe funkcji')
writeln('w przedziale [a;b]');
readln(a);
write('Podaj wartosc b: ');
readln(b);
write('Podaj dokladnosc: ');
readln(eps);
repeat
if (1 - exp(sin(a)*cos(a)))*(1 - exp(sin(c)*cos(c)))
then
b := c { funkcja ma przeciwne znaki w a i c }
else
a := c; { funkcja ma przeciwne znaki w b i c }
writeln(c);
until abs(1 - exp(sin(c)*cos(c)))
writeln('Miejsce zerowe: c = ',c:12:8);
readln;
Rozwiązujemy dowolne równanie 55
end.
Nasz program dość dokładnie odpowiada schematowi podanemu powyżej i w zasadzie
nie wymaga dodatkowych komentarzy (mimochodem poznałeś kilka nowych funkcji
arytmetycznych exp, sin, cos i abs). Warto jednak zwrócić uwagę na kryterium
stopu:
until abs(1 - exp(sin(c)*cos(c)))
Jak wspomnieliśmy, zapis ten pozwala uniknąć nieskończenie długiego dochodzenia
kolejnych podziałów do punktu stanowiącego właściwe rozwiązanie. Ale czy tylko?
Spróbuj wykonać poniższy program:
program Dodawanie;
{ zmiennoprzecinkowych }
var x : real;
begin
x := 0.0
repeat
x := x + 0.1;
writeln(x:16:12);
until
end. [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl akte20.pev.pl
warunkowych.
" Jeśli wyborem steruje wartość typu porządkowego, lepszym rozwiązaniem jest
użycie instrukcji wyboru case.
52 Turbo Pascal programowanie
RozwiÄ…zujemy
dowolne równanie
Problem rozwiązania dowolnego równania nie należy bynajmniej do zadań typu
kamienia filozoficznego czy uniwersalnego rozpuszczalnika. Chociaż dla pewnych klas
równań istnieją dawno opracowane wzory i metody, spora grupa równań nieliniowych
nie daje się rozwiązać na papierze w sposób dokładny. Nie oznacza to jednak, że nie
można ich w ogóle rozwiązać: kwestii przybliżonego rozwiązywania równań nielinio-
wych poświęcono z niezłym skutkiem spory dział matematyki znany jako metody
numeryczne. W niniejszym rozdziale spróbujemy zademonstrować jedną z najprost-
szych metod rozwiązywania równań nieliniowych tak zwaną metodę bisekcji. Jest
ona na tyle prosta, że praktycznie nie wymaga znajomości skomplikowanej matematyki
(a jedynie logicznego myślenia), a jednocześnie całkiem skuteczna.
f(x)
c4 c3 c1 b
x
a c2
c
Rysunek 9. Zasada działania metody bisekcji
Załóżmy, że chcemy znalezć miejsce zerowe funkcji f(x) przedstawionej powyżej.
Szukamy więc takiego punktu c na osi x, dla którego f(c) = 0. Wybierając na osi x dwa
punkty a i b takie, by wartości f(a) i f(b) miały przeciwne znaki, możemy z pewnością
stwierdzić, że funkcja ma pomiędzy a i b co najmniej jedno miejsce zerowe (gdyż musi
gdzieś przeciąć oś x). Podzielmy przedział pomiędzy a i b na dwie równe części. War-
tość funkcji w nowo uzyskanym punkcie c1 ma nadal znak przeciwny do f(a), a zatem
miejsce zerowe leży gdzieś pomiędzy a i c1. Podzielmy nowo uzyskany przedział na
połowy: tym razem okazuje się, że wartość funkcji w punkcie c2 ma znak przeciwny do
Rozwiązujemy dowolne równanie 53
f(c1), a więc miejsce zerowe leży pomiędzy c1 a c2. Wykonując kolejne podziały
dojdziemy w końcu do punktu... no, właśnie. Zauważ, że z każdym kolejnym podziałem
zbliżamy się do miejsca zerowego coraz wolniej: za każdym razem przedział poszuki-
wania zawężany jest dwukrotnie, tak więc (teoretycznie) dokładne położenie miejsca
zerowego (odpowiadające przedziałowi o zerowej szerokości, czyli pojedynczemu
punktowi) osiągniemy po nieskończonej liczbie podziałów. Chyba nie masz zamiaru
czekać aż tak długo!
Rozwiązaniem tego problemu jest właściwe sformułowanie tzw. kryterium zakończenia
obliczeń lub kryterium stopu. W naszym przypadku kolejne cykle podziałów (zwane
fachowo iteracjami) będziemy prowadzili tak długo, aż bezwzględna wartość funkcji
w punkcie cn zmaleje poniżej zadanego progu.
Spróbujmy zapisać w bardziej formalny sposób pojedynczy podział:
poczÄ…tek
wyznacz punkt c w połowie odległości pomiędzy a i b
jeżeli f(a) ma znak różny od f(c), to przenieś punkt b do punktu c
w przeciwnym przypadku przenieÅ› punkt a do punktu c
koniec
Ale jak zabrać się za wykonywanie kolejnych podziałów? Oczywiście nie będziesz mu-
siał wielokrotnie wpisywać odpowiednich instrukcji: zamiast tego wykorzystasz do ich
cyklicznego wykonywania instrukcję pętli.
Spośród trzech dostępnych w Pascalu struktur pętli do realizacji naszego zadania
odpowiednie są dwie while i repeat (trzecią pętlą, for, zajmiemy się nieco
pózniej). Należą one do grupy pętli sterowanych warunkiem, co oznacza, że wykonują
się tak długo, jak długo spełnione będzie odpowiednie kryterium (while powtarzaj,
dopóki...) lub do momentu, kiedy zostanie ono spełnione (repeat powtarzaj, aż...).
Nie trzeba chyba dodawać, że owym kryterium będzie właśnie nasze kryterium stopu:
zakończ iteracje, jeśli wartość bezwzględna f(c) jest mniejsza od zadanego progu.
Której instrukcji użyć? W zasadzie w naszym przypadku jest to obojętne. Działanie
pętli while i repeat jest bardzo zbliżone, zaś różnica sprowadza się do faktu, że
w pierwszej z nich warunek przerwania pętli sprawdzany jest na początku:
while warunek
do instrukcja
zaś w drugiej na końcu pętli:
repeat instrukcja
until warunek
W konsekwencji instrukcje tworzące zawartość pętli repeat muszą wykonać się co
najmniej raz, zaś w przypadku pętli while mogą nie wykonać się ani razu (jeśli waru-
nek będzie od razu spełniony). Ponadto musisz pamiętać, że sformułowanie warunku
jest dla obu pętli dokładnie przeciwne (pętla while wykonuje się tak długo, jak długo
54 Turbo Pascal programowanie
warunek jest spełniony, repeat tak długo, jak długo jest niespełniony). Zapamiętaj
również, że umieszczając kilka instrukcji w pętli while musisz połączyć je w instrukcję
złożoną słowami begin i end, zaś w przypadku pętli repeat konieczność ta nie
występuje (ogranicznikami instrukcji złożonej są tu słowa repeat i until).
Spróbujmy zapisać nasz algorytm z wykorzystaniem pętli repeat. Będzie on wyglądał
mniej więcej tak:
poczÄ…tek
wprowadz wartości krańców przedziału i dokładności
powtarzaj
wyznacz punkt c w połowie odległości pomiędzy a i b
jeżeli f(a) ma znak różny od f(c), to przenieś punkt b do punktu c
w przeciwnym przypadku przenieÅ› punkt a do punktu c
aż do momentu, gdy wartość bezwzględna f(c) jest mniejsza od zadanego progu
wypisz znalezione miejsce zerowe
koniec
Załóżmy, że chcemy rozwiązać równanie
1 - esin xÅ"cos x = 0
posiadające (jak nietrudno obliczyć na kartce) pierwiastek w punkcie x = 0. Tłumacząc
powyższy schemat na angielski (i Pascal) otrzymamy następujący program:
program Bisekcja;
var
begin
writeln('Program znajduje miejsce zerowe funkcji')
writeln('w przedziale [a;b]');
readln(a);
write('Podaj wartosc b: ');
readln(b);
write('Podaj dokladnosc: ');
readln(eps);
repeat
if (1 - exp(sin(a)*cos(a)))*(1 - exp(sin(c)*cos(c)))
then
b := c { funkcja ma przeciwne znaki w a i c }
else
a := c; { funkcja ma przeciwne znaki w b i c }
writeln(c);
until abs(1 - exp(sin(c)*cos(c)))
writeln('Miejsce zerowe: c = ',c:12:8);
readln;
Rozwiązujemy dowolne równanie 55
end.
Nasz program dość dokładnie odpowiada schematowi podanemu powyżej i w zasadzie
nie wymaga dodatkowych komentarzy (mimochodem poznałeś kilka nowych funkcji
arytmetycznych exp, sin, cos i abs). Warto jednak zwrócić uwagę na kryterium
stopu:
until abs(1 - exp(sin(c)*cos(c)))
Jak wspomnieliśmy, zapis ten pozwala uniknąć nieskończenie długiego dochodzenia
kolejnych podziałów do punktu stanowiącego właściwe rozwiązanie. Ale czy tylko?
Spróbuj wykonać poniższy program:
program Dodawanie;
{ zmiennoprzecinkowych }
var x : real;
begin
x := 0.0
repeat
x := x + 0.1;
writeln(x:16:12);
until
end. [ Pobierz całość w formacie PDF ]