Wykład z Metod Numerycznych
dr Marek J. Śmietański
2000/2001
0. Literatura
1. BJÖRCK, 
., DAHLQUIST, G. - Metody numeryczne.
2. DEMIDOWICZ, B.P., MARON, L.A. - Metody numeryczne. Część I.
3. FORTUNA, Z., MACUKOW, B., W
SOWSKI, J. - Metody numeryczne.
4. STOŻEK, E. - Metody numeryczne w zadaniach. Część I.
1. Wstęp
METODY NUMERYCZNE - dział matematyki stosowanej zajmujący się opracowywaniem i badaniem metod
przybliżonego rozwiązywania problemów obliczeniowych w modelach matematycznych innych dziedzin nauki,
np.
ðzyki, ekonomii, medycyny i oczywiÅ›cie informatyki.
Badania teoretyczne koncentrujÄ… s/
e na tworzeniu technik obliczeniowych oraz obejmują analizę błędów i
kosztów metod przybliżonych.
Wobrębie klasycznych metod numerycznych możemy wyróżnić m.in. takie zagadnienia jak:
² analiza bÅ‚Ä™dów zaokrÄ…gleÅ„;
² interpolacja
² aproksymacja
² caÅ‚kowanie i różniczkowanie numeryczne
² rozwiÄ…zywanie równaÅ„ nieliniowych
² rozwiÄ…zywanie ukÅ‚adów równaÅ„ liniowych
² obliczanie wartoÅ›ci wÅ‚asnych i wektorów wÅ‚asnych macierzy
² rozwiÄ…zywanie zagadnieÅ„dla równaÅ„różniczkowych zwyczajnych i czÄ…stkowych
Metody numeryczne jako sztuka - wybór metody rozwiązania, która jest  najlepiej dostosowana do danego
zadania.
2. Podstawowe pojęcia
2.1. Elementy teorii błędów
2.1.1. y
ródła błędów
Na wyniki obliczeń numerycznych wpływa wiele rodzajów błędów. Można je podzielić na kilka grup:
1. Błędy zagadnienia (uproszczenia modelu matematycznego) - przy matematycznym formułowaniu zadania w
większości zastosowań trzeba wyidealizować realne zjawiska. Bardzo trudno oszacować skutki takich błędów.
2. Błędy danych wejściowych - są związane z obecnością w obliczeniach wyników pomiarów podlegających za-
kłóceniom lub posiadających tylko pewną ograniczoną dokładność. Ewentualnie mogą s/
e pojawíc na skutek
konieczności zaokrąglenia niewymiernych parametrów liczbowych. Niektóre możliwe do oszacowania.
3. Błędy obcięcia - pojawiająsię wtedy, gdy obliczenia kończy się przed osiągnięciem wartości granicznej. Bardzo
wiele zagadnień można rozwiązać dokładnie tylko za pomocą procesów nieskończonych. Nietrudno je osza-
cować.
1
4. Błędy obliczeń - spowodowane zaokrąglaniem wyników obliczeń związane z precyzją danej maszyny (zależą
od procesora i języka programowania). Mogą być bardzo dotkliwe w skutkach, ale można je zbadać.
5. Błędy człowieka i błędy maszynowe - wkażdych obliczeniach mogąpojawićsiębłędy powstające na skutek pomyłek,
błędy pisarskie, błędy w programie, błędy przy wprowadzaniu danych, itp.. Niemożliwe do przewidzenia.
Błąd całkowity obliczeń powstaje w wyniku skumulowania wszystkich rodzajów błędów.
2.1.2. Błędy bezwzględne i względne
Niech x oznacza wartość przybliżoną pewnej wielkości, której wartością dokładną jest x.
Ä…
DEFINICJA 1. Błędem bezwzględnym óx wartości x nazywamy normę różnicy pomiędzy wartością przybliżoną
x i wartościądokładną x, tj.
Ä…
óx = kx Ą xk .(1)
Ä…
Ponieważbłąd bezwzględny nie charakteryzuje w pełni dokładności obliczeń, to często w zagadnieniach numerycznych
korzysta się z błędu względnego:
DEFINICJA 2. Błędem względnym ąx wartości x nazywamy stosunek błędu bezwzględnego ó tej wartości do
normy wartości dokładnej x, tj.
Ä…
kx Ä„ xk
Ä…
Ä…x = ,(2)
kxk
Ä…
oile x =0.
Ä… 6
Błąd względny można również wyrażać procentowo, tzn. ą% = ą ó 100%.
UWAGA: Oczywiście
óx = kxk ąx .
Ä…
2.1.3. Przenoszenie się błędów
TWIERDZENIE 3. BłędyP działań arytmetycznych wyrażająsię następującymi wzorami:
wyników
n
(i) dla dodawania - jeśli y = xi, to
i=1
n n
X X
jxij Ä…xi
óy = óxi oraz ąy = ;
jyj
i=1 i=1
(ii) dla odejmowania - jeśli y = x1 Ą x2, to
jx1j Ä…x1 + jx2j Ä…x2
óy =óx1 +óx2 oraz ąy = ;
jyj
Qn
(iii) dla mnożenia - jeśli y = xi, to
i=1
Å» Å»
n n
X X
Å» Å»
y
Å» Å»
óy = óxi oraz ąy = ąxi ;
Żxi Ż
i=1 i=1
(iv) dla dzielenia - jeśli y = x1=x2, x2 =0, to
6
jx1j óx2 + jx2j óx1
óy = oraz ąy = ąx1 + ąx2 ;
x2
2
UWAGA: Różnica dwóch liczb bardzo bliskich sobie może mieć bardzo małą dokładność względną, np. niech
1 1
x1 =0:5764 ż ó 10Ą4 i x1 =0:5763 ż ó 10Ą4 ,
2 2
wówczas
x1 Ą x2 =0:0001 oraz óx1Ąx2 =0:0001
czyli błąd bezwzględny różnicy jest tak samo duży, jak otrzymana różnica, a stąd ąx1Ąx2 =100%.
Podstawowe zadanie teorii błędów można sformułować następująco: wyznaczyć błąd danej funkcji, gdy znane są
błędy wszystkich jej argumentów.
Niech będzie dana funkcja różniczkowalna y = f (x1; x2; :::; xn). Przypuśćmy, że znane są błędy bezwzględne
argumentów tej funkcji jóxij ; i =1; :::; n.
2
TWIERDZENIE 4. Ogólny wzór na przenoszenie się błędów jest postaci:
Å» Å»
n
X
Å» Å»
@f
Å»
óy = óxi ,(3)
Å» Å»
@xi
i=1
czyli błąd bezwzględny óy aproksymuje się zapomocąróżniczk%2ł zupełnej funkcji f.
WNIOSEK 5. Błąd względny wartości funkcji jest równy błędowi bezwzględnemu jej logarytmu naturalnego, tzn.
Å» Å»
Å» Å»
n @f n
Å» Å»
X X
Å» Å»
@
Å» @xi
Å»
ąy = Ż Ż óxi =
Ż@xi ln yŻ óxi .(4)
Å»
Å» Å»
y
i=1 i=1
PRZYKA
AD: Oszacowaćbłąd obliczenia objętości kuli, jeśli j
j promień wynosi r =1:85cmż0:05cm, a ź =3:14.
Traktując r i ź jako wielkości zmienne obliczamy pochodne cząstkowe
@V 4 @V
= r3 =8:44, =4źr2 =42:99
@ź 3 @r
Na mocy wzoru (3) błąd bezwzględny objętości kuli wynosi
Å» Å» Å» Å»
Å»@V Å» Å»@V Å»
Å» Å» Å» Å»
óV = óź + ór =8:44 ó 0:0016 + 42:99 ó 0:05 = 0:0135 + 2:1495 = 2:163cm3 .
Å» Å» Å» Å»
@ź @r
Zatem
4
V = źr3 =26:51cm3 ż 2:16cm3 ,
3
skąd błąd względny objętości równa się
2:163cm3
ąV = =0:0816 ź 8% .
26:51cm3
2.1.4. Odwrotne zadanie teorii błędów
W praktyce często zdarza sie również sytuacja odwrotna,tzn. trzeba odpowiedzieć na pytanie: jakie mogąbyćbłedy
bezwzględne argumentów funkcji, aby błąd bezwzględny funkcji nie przekroczył zadanej wielkości ?
Najprościej można takiŻproblem rozwiązać, wykorzystując tzw. zasadę równego wpływu, czyli zakładając, że wszys-
Å»
Å»
Å» @f
tkie różniczki cząstkowe óxi; i = 1; :::; n wpływają jednakowo na powstanie ogólnego błędu bezwzględnego
Å» Å»
@xi
funkcji y = f (x1; x2; :::; xn).
Niech wielkość błędu bezwzględnego funkcji będzie dana i wynosi óy. Wówczas na mocy wzoru (3) mamy
Å» Å»
n
X
Å» Å»
@y
Å» Å»
óy = óxi .
Å» Å»
@xi
i=1
Zakładając, że wszystkie składniki powyższej sumy są równe, otrzymujemy że
Å» Å» Å» Å» Å» Å»
Å» Å» Å» Å» Å» Å»
@y @y @y óy
Å» Å» Å» Å» Å» Å»
óx1 = óx2 = ::: = óxn = ,
Å»@x1 Å» Å»@x2 Å» Å»@xn Å»
n
skÄ…d
óy Ż;
óxi = i =1; 2; :::; n .(5)
Å» @y
Å»
n Å» Å»
@xi
Zdarza się jednak, że przy taim sposobie rozwiązani

problemu otrzymane wielkości błędów bezwzględnych dla odd-
zielnych zmiennych niezależnych są tak małe, że praktycznie nie ma możliwości określenia tych zmiennych z żadaną
dokładnością. Rezygnuje się wtedy z zasady równego wpływu i odpowiednio dobiera się dopuszczalne błędy różnych
zmiennych (zaostrzając wymagania dla części zmiennych, uzyskuje się osłabienie wymagań dla pozostałych).
PRZYKA
AD: Określić, z jaką dokładnością należy zmierzyć promieńkoła r =30:5cm i z iloma cyframi dziesięt-
nymi wziąć ź, aby powierzchnię tegokoła można było obliczyć z dokładnością do 2cm2.
Mamy S = źr2 i óS =2cm2. Przyjmując r =30:5cm i ź =3:14, otrzymamy w przybliżeniu
@S @S
= r2 =930:25 oraz =2źr =191:54 .
@ź @r
Ponieważ n =2, tona podstawie wzoru(5) mamy
2 2
óź = < 0:0011 oraz ór = < 0:0053cm .
2 ó 930:25 2 ó 191:54
3
Zatem należałoby wziąć ź =3:141 i promień r zmierzyć z dokładnością do tysięcznych części centymetra. Jest
Å»@S Å»
Å» Å»
to w zwykłych warunkach trudne, więc wygodniej jest przyjąć ź =3:1416, skąd óź < 0:00001, a wtedy ór =
@r
Å»@S Å»
Å» Å»
óS Ą óź =2 Ą 930:25 ó 0:00001 = 1:9907. w/
ec ór < 0:011cm, cojuż jest łatwiejsze.
@ź
2.2. Komputerowa reprezentacja liczb
Komputery komunikująsięzużytkownikami w układzie dziesiątkowym, ale wykonujądziałania w układzie dwójkowym.
Oczywiście działania mogą bżc wykonywane jedynie na liczbach rzeczywistych przedstawionych za pomocą skońc-
zonej ilości cyfr, nie większej niż pewna ustalona liczba.
Wukładzie dziesiątkowym każda liczba rzeczywista może być przedstawiona w znormalizowanej postaci zmi-
ennopozycyjnej (zmiennoprzecinkowej), tzn.
x = r ó 10n ,
gdzie r jest liczbą rzeczywistą spełniającą
0:1 ·jrj < 1 albo 1 ·jrj < 10 ,
zaś n jest liczbą całkowitą, o ile x =0.
6
Wukładzie dwójkowym znormalizowana postać zmiennopozycyjna jest następująca:
x = q ó 2m ,(6)
gdzie q jest liczbą spełniającą
1
·jqj < 1 albo 1 ·jqj < 2 ,
2
zaś m jest liczbą całkowitą, oile x =0.
6
Liczby r i q nazywamy mantysą, zaś m cechą lub wykładnikiem. Ograniczenia na q i m w komputerach są wyznac-
zone przez długość słowa maszynowego. Jego część jest przeznaczona na mantysę, a część na cechę, a mianowicie:
m0 m1 m2 ... mk c0 c1 ... cl
gdzie kolejne bity zawierają następujące informacje: m0 - znak mantysy, m1; :::; mk - cyfry mantysy, c0 - znak cechy,
c1; :::; cl - cyfry cechy.
PRZYKA
AD: W komputerze, w którym długość słowa maszynowego wynosi 32 bity, na mantysę przeznaczone są
23 bity, natomiast na cechę - 7. Oznacza to, że rozważany komputer może wykonywaćdziałania na liczbach o wartości
7
bezwzględnej od (około) 10Ą38 do 1038 (ponieważ 22 Ą1 =2127 ź 1038). Ten zakres (typ Single w Pascalu, Float
wC) jest często niewystarczający dla pewnych obliczeń numerycznych, więc często używa się arytmetyki o podwójnej
dokładności (Double) - liczba jest reprezentowana wtedy przez dwa słowa maszynowe.
DEFINICJA 6. Jeśli liczba rzeczywista x daje się zapisać w postaci zmiennopozycyjnej w danym komputerze, to
mówimy, że x jest liczbą maszynową.
Oznacza to, że liczba x może być dokładnie przedstawiona w tym komputerze. Większość liczb rzeczywistych
nie daje s/
e dokładnie przedstawić w postaci liczb maszynowych. Bez względu na to czy taka liczba pojawi się jako
wprowadzana dana, czy jako wynik obliczeń, to powstanie błąd wynikający z przybliżenia tej liczby przez najbliższą
jej liczbÄ™ maszynowÄ….
PRZYKA
AD: Rozważmy najprostszy typ rzeczywisty Float w języku C. Taka liczba zmiennopozycyjna zajmuje 4
bajty i jest reprezentowana nastepujÄ…co:
z m1 ... m23 c1 ... c8
gdzie 1 bit (z) jest przeznaczony na znak, 23 bity (m1; ::; m23) - na mantysę oraz 8 bitów (c1; :::; c8) - na cechę .
Ponieważ 23 cyfry binarne mantysy odpowiadają 7 cyfrom dziesiętnym, więc taka reprezenacja oferuje 7-cyfrową
precyzję zmiennopozycyjną. Natomiast 8-cyfrowy wykładnik daje zakres 0 Ą 255, ale z powodu stosowanego kodu
mamy zakres Ą126 Ą +127 (127 jest automatycznie odejmowane od wykładnika, dla 0 i 255 wartość liczby jest
określana inaczej). Np.
0 101100110:::0 11000010
Pierwszy bit z lewej jest 0, więc liczba jest dodatnia. Następne 23 bity wskazują, że mantysa wynosi
1 ó 2Ą1 +1ó 2Ą3 +1ó 2Ą4 +1ó 2Ą7 +1ó 2Ą8 =0:69921875
natomiast ostatnie 8 bitów jest równoważne liczbie dziesiętnej
1 ó 27 +1ó 26 +1ó 21 =194:
4
W konsekwencji, rozważana liczba maszynowa reprezentuje liczbę dziesiętną
+0:69921875 ó 2194Ą127 =+1: 031 864 747 ó 1020 = r:
Jednak, następną liczbą maszynową jest
0 101100110:::01 11000010 =+1: 031 864 923 ó 1020
zaÅ› poprzedniÄ…
0 101100101:::1 11000010 = 1: 031 864 571 ó 1020;
a to oznacza, że pierwsza z rozważanych liczb maszynowych reprezentuje nie tylko liczbę r, ale również wiele liczb,
które są między nią a sąsiędnimi liczbami maszynowymi.
Liczby maszynowe są rozłożone nierówno na osi liczbowej, tzn. są położone gęściej w pobliżu 0 i coraz rzadziej w
kierunku krańców zakresu. Im liczba większa, tym ma większy wykładnik, zatem odległość m/
edzy kolejnymi coraz
większymi co do wartości bezwzględnej liczbami maszynowymi rośnie, a przecież między kolejnymi potęgami liczby
2 jest zawsze ta sama ilość liczb maszynowych. W konsekwencji wszystkie liczby rzeczywiste x z pewnego przedziału
są przybliżane tylko przez jedną najbliższą im liczbę maszynową xń . Będzie ona oddalona nie więcej niż o połowę
większej z odległości a1 i a2 między dwoma liczbami maszynowymi położonymi w pobliżu x.
Przyjmijmy dla uproszczenia, że a1 = a2 = a i spróbujmy oszacować błąd względny przybliżenia zmiennopozy-
cyjnego. Błąd bezwzględny wynosi
1
Å„
óx = ó 2mĄk .
2
Zde
ðnicji postaci zmiennoprzecinkowej (6) mamy
jxj ¸1 ó 2m ,
skąd otrzymujemy oszacowanie błędu względnego
ń ó 2mĄk
óx 1 1
2
Å„
Ä…x · · = " , gdzie " = ó 2Ä„k .
jxj 2m 2
Najmniejsza z możliwych takich wartości " jest nazywana epsilonem maszynowym.
DEFINICJA 7. Epsilon maszynowy jest to graniczna wartośćbłędu względnego przybliżenia zmiennoprzecinkowego
(określenie maszynowy podkreśla, że wartość tazależy od komputera).
Praktycznie oznacza to, że dane reprezentowane w komputerze nie mogąbyćpamiętane z dokładnościąwiększąniż
". Intuicyjnie: 1+" jest najmniejszą liczbą większą od 1, którą komputer potra
ð odróżnić od 1. Bardziej uogólniajÄ…c,
można powiedzieć, że jxjó" jest dobrym oszacowaniem błędu bezwzględnego przybliżenia zmiennopozycyjnego liczby
x przez najbliższą jej liczbę maszynową.
Z kolei liczba całkowita w komputerze zajmuje całe słowo maszynowe, z tym że jeden bit jest zarezerwowany dla
jej znaku, tzn.
d0 d1 d2 ... dk
gdzie bit d0 jest przeznaczony na znak, zaś bity d1; :::; dk na cyfry liczby całkowitej.
PRZYKA
AD: W komputerze, w którym długośćsłowa maszynowego wynosi 32 bity można posługiwaćsię liczbami
całkowitymi z zakresu od Ą231 do 231 Ą 1 =2:147:483:647.
2.3. Zaokrąglenie i obcięcie liczby
DEFINICJA 8. Cyfrą znaczącą wartósci przybliżonej liczby rzeczywistej nazywamy każdą zachowaną cyfrę
rozwinięcia dziesiętnego tej liczby różną od zera oraz zero, jeśli jest ono zawarte między cyframi znaczącymi lub zna-
jduje się na zachowanej pozycji. Mówimy, że liczba przybliżona ma n poprawnych (dokładnych) cyfr znaczących,
jeżeli błąd bezwzględny tej liczby nie przewyższa połowy jedności pozycji, określonej przez n-tą cyfrę znaczącą, licząc
od lewej.
PRZYKA
AD: Dla liczby dokładnej x = 35:97 jej przybliżenie x = 36:00 posiada 4 cyfry znaczące, ale tylko 3
Ä…
1
cyfry są poprawne, gdyż óx =0:03 < 0:05 = ó 10Ą1 (ąx =8: 3 ó 10Ą4).
2
UWAGA: (i) Początkowe zera służa jedynie do wskazania pozycji dziesiętnych innych cyfr. Końcowe zera są
cyframi znaczącymi, ponieważ wskazują, że w liczbie przyblizonej zachowano daną pozycję.
(ii) Liczba cyfr znaczących daje pojęcie o wielkości błędu względnego, liczba cyfr poprawnych - o wielkości błędu
bezwzględnego.
5
REGUA
A ZAOKR
GLANIA:
Aby zaokrąglić liczbę do n cyfr znaczących, należy obciąć wszystkie jej cyfry zapisane z prawej strony n-tej cyfry
znaczÄ…cej. Przy tym:
1
(i) jeśli fragment liczby znajdujący się na prawo od n-tej cyfry dziesiętnej jest mniejszy co do modułuod ó 10Ąn, to
2
n-tą cyfrę dziesiętną pozostawia się bez zmian;
1
(ii) jeśli fragment ten jest co do modułuwiększy niż ó 10Ąn, todo n-tej cyfry dodaje się 1;
2
1
(iii) jeśli fragment ten jest równy ó 10Ąn, to n-tą cyfrę zw/
esza siÄ™ o 1, jésli jest nieparzysta, a pozostawia siÄ™ bez
2
zmian, gdy jest parzysta.
Innymi słowy: jeśli przy zaokrąglaniu odrzuca się mniej niż połowę jedności ostatniej pozostawionej pozycji
dziesiętnej, to cyfry na pozostawionych pozycjach nie ulegną zmianie. Jeśli część odrzucona jest większa niż połowa
jedności ostatniej pozostawionej pozycji dziesiętnej, to cyfrę ne tej pozycji zwiększa się o 1. Gdy odrzucona część
dokładnie równa siępołowie jedności pozostawionej pozycji, to dla jednakowej częstości błedów ujemnych i dodatnich
postępuje się zgodnie z regułą parzystości cyfry.
PRZYKA
AD: ZaokrÄ…glanie do 4 cyfr znaczÄ…cych:
liczba odrzucony fragment zaokrąglenie błąd bezwzględny
3:1497 0:7 ó 10Ą3 3:150 0:3 ó 10Ą3
Ą3:1497 0:7 ó 10Ą3 Ą3:150 0:3 ó 10Ą3
3:1435 0:5 ó 10Ą3 3:144 0:5 ó 10Ą3
3:1425 0:5 ó 10Ą3 3:142 0:5 ó 10Ą3
UWAGA: (i) Większość komputerów, w których wykonuje się zaokrąglenie, tylko zwiększa albo tylko zmniejsza
1
liczbę o ó 10Ąn w przypadku (iii) (lub o analogiczną liczbę ze stosowanego układu niedziesiętnego), gdyż jest to
2
technicznie Å‚atwiejsze.
(ii) Błąd bezwzględny zaokrąglenia nie przewyższa połowy jedności pozycji dziesiętnej, określonej przez ostatnią po-
zostawionÄ… cyfrÄ™ znaczÄ…cÄ…, tzn.
1
jx Ä„ xj · ó 10Ä„n .
Ä…
2
2.4. Algorytmy i zbieżność
DEFINICJA 9. Mówimy, że zadanie jest dobrze uwarunkowane, jeśli małe zmiany danych wejściowych powodują
odpowiednio małe zmiany danychwyjściowych. W przeciwnym razie, mówimy, że zadanie jest z
le uwarunkowane.
Czyli innymi słowy uwarunkowanie zadania określa, jak rozwiązanie tego zadania jest wrażliwe na małe zmiany
danych wejściowych.
DEFINICJA 10. Algorytmem nazywamy procedurę numeryczną opisującą w jednoznaczny sposób skończony ciąg
kroków, które należy wykonać w podanej kolejności, aby znalez
ć rozwiązanie problemu lub przybliżenie rozwiązania.
Jesteśmy oczywiście zainteresowani wybieraniem takich metod, które dają dokładne wyniki. Jednym z warunków,
które nakłada się na algorytm, o ile jest to możliwe, jest stabilność.
DEFINICJA 11. Mówimy, że algorytm jest stabilny, jeśli posiada następującą własność: małe błędy powstałe w
pewnym kroku algorytmu nie sąpowiększane w innych krokach oraz nie powodująpoważnego ograniczenia dokadności
wszystkich obliczeń. W przeciwnym razie, mówimy, że algorytm jest niestabilny.
Niektóre algorytmy są stabilne zawsze (bez względu na dane wejściowe), zaś stabilność innych zależy od wyboru
danych wejściowych.
DEFINICJA 12. Niech " będzie błędem zaokrąglenia i En błędem po wykonaniu n kroków algorytmu. Jeśli jEnj ź
Cn", gdzie C jest pewnÄ… staÅ‚Ä… niezależnÄ… od n, to mówimy, że wzrost bÅ‚Ä™du jest liniowy. Jésli jEnj ź kn", dla
pewnego k >1, towzrost błędu jest wykładniczy.
Liniowy wzrost błędu jest zwykle nie do uniknięcia i gdy C oraz " są małe, to wyniki są ogólnie akceptowalne.
Wzrostu wykładniczego powinno się unikać, gdyż prowadzi do nieakceptowalnych niedokładności. W konsekwencji,
algorytm, który charakteryzuje się liniowym wzrostem błędu, jest stabilny, zaś agorytm z wykładniczym wzrostem jest
niestabilny.
Oczywiście, aby uniknąć efektów błędu zaokrąglenia, można używać w/
ekszej precyzji obliczeń (podwójnej lub
rozszerzonej), o ile maszyna lub oprogramowanie oferują taką możliwość. Należy jednak pamietać, że im wyższa
precyzja obliczeń, tym bardziej są one czaso- i pamięcio-chłonne.
Przedyskutujemy teraz pewnÄ… terminolog/
e, która będzie używana do opisywania zbieżności różnych technik nu-
merycznych i umożliwi porównywanie różnych metod.
DEFINICJA 13. Przypuśćmy, że ciÄ…g f®ng1 jest zbieżny do wartoÅ›ci ®. Mówimy, że f®ng1 jest zbieżny do ®
n=1 n=1
6
z rzędem zbieżności O (Żn), jeśli fŻng1 jest takim ciągiem, że Żn =0 dla każdego n oraz
6
n=1
j®n Ä„ ®j
· C dla dostatecznie dużego n,
jŻnj
i C jest staÅ‚Ä… niezależnÄ…odn. Inaczej mówiÄ…c ®n = ®+ O (Å»n).
PRZYKA
AD. Rozważmy ciągi:
sin n n +3
®n = oraz ®n = dla n ¸ 1:
^
n n3
Chociaż limn!1 ®n = limn!1 ®n =0, toszybkość zbieżnoÅ›ci obu ciÄ…gów jest różna.
^
^
Jeśli przyjmiemy Żn =1=n i Żn =1=n2 dla każdego n, to
Å» Å» Å» Å»
Å»(sin n) =n Ä„ 0Å» Å»(n +3) =n3 Ä„ 0Å» Å» +3Å»
Żn Ż
Å» Å» Å» Å» Å» Å»
= jsin nj ·1 oraz = · 4;
Å» Å» Å» Å»
1=n 1=n2 Å» Å» n
Ą ó Ą ó
1 1
zatem ®n =0 + O , natomiast ®n =0 + O . A to implikuje, że ciÄ…g ®n jest szybciej zbieżny do 0 niżciÄ…g ®n.
^ ^
n n2
Powyższą notację można uogólnić na funkcje:
DEFINICJA 14. Jeśli limx!0 F (x) =L, to mówimy, że zbieżność jest rzędu O (G(x)), jesli istnieje liczba K>0,
niezależna od x, taka że
jF (x) Ä„ Lj
· K dla dostatecznie maÅ‚ych jxj > 0:
jG(x)j
Inaczej mówiąc F (x) =L + O (G(x)).
2.5. Schemat Hornera
Przy obliczaniu wartoÅ›ci funkcji zadanych wzorem nie jest obojÄ™tne, jakÄ… postác ma ten wzór. CzÄ™sto wzory
równoznaczne matematycznie nie są równoznaczne numerycznie, ze względu na sposób przeprowadzania obliczeń.
Ztegowzględu należy zadbać, aby przy obliczaniu wartości funkcji wykonywać jak najmniej operacji arytmetycznych,
co zmniejszy kumulowanie się błędów obliczeń zmiennopozycyjnych. Z drugiej strony pod kątem programistycznym
wygodnie jest wykonywanie tych operacji zamknąć w powtarzających się krótkich cyklach, czyli za pomocą rekurencji.
Niech będzie dany wielomian zmiennej rzeczywistej x stopnia n:
P (x) =anxn + anĄ1xnĄ1 + ::: + a1x + a0
owspółcznnikach rzeczywistych ak; k =0; 1; :::; n. Idea Hornera sprowadza się do obliczenia wartości wielomianu P
w dowolnym punkcie według wzoru:
P (x) =(::: ((anx + anĄ1) x + anĄ2) x + ::: + a1) x + a0 ,(7)
z którego wynika następujący schemat Hornera:
bn = an (8)
bk = ak + bk+1x dla k = n Ą 1; nĄ 2; :::; 1; 0
Z postaci wielomianu (7) i konstrukcji (8) wynika, że
P (x) =b0 .
UWAGA: Oczywiście, jeżeli pośrednie wartości bk nie są potrzebne, to algorytm można opisać bez indeksowania.
Wielkości bk mają jednak pewne konkretne znaczenie, gdyż zachodzi równość:
nĄ1
X
P (x) Ä„ P (z)
= bk+1xk .
x Ä„ z
k=0
Powyższy wzór przedstawia tzw. dzielenie syntetyczne, które stosuje się np. przy rozwiązywaniu równań algebraicznych,
gdy stopniowo eliminuje się obliczone już pierwiastki, aby otrzymać równanie niższego stopnia. Taki proces nazywamy
deðacjÄ….
n(n+1)
Obliczanie wartości wielomianu n-tego stopnia w postaci normalnej wymaga mnożeńi n dodawań, natomiast
2
przy wykorzystaniu schematu Hornera wykonuje się tylko n mnożeńi n dodawań.
7