To tylko jedna z 22 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
WYKŁAD 2
OBLICZANIE WARTOŚCI FUNKCJI
SCHEMAT HORNERA
Schemat Hornera jest najczęściej wykorzystywanym algorytmem obliczania wartości wielomianu
Pn ( x ) = an x n + an−1 x n−1 + ... + a0
(1)
ze znanymi współczynnikami rzeczywistymi a k ( k = 0, 1, ..., n ; a n ≠ 0). Wyznaczanie wartości wielomianu
dla x = ξ bezpośrednio ze wzoru (1) wymaga wykonania n (n + 1) 2 mno eń i n dodawań. Stosując
natomiast schemat Hornera:
b0 = an ,
b1 = b0 ξ + an−1 ,
.......................
bk = bk −1 ξ + an− k ,
.......................
bn = bn−1 ξ + a0 ,
(2)
odpowiadający obliczeniu wyra enia
( ... ((an ξ + an −1 ) ξ + a n − 2 ) ξ + ... + a1 ) ξ + a0 ,
wartość wielomianu
Pn (ξ) = bn
(3)
otrzymujemy wykonując tylko n mno eń i taką samą liczbę dodawań.
Liczby (2) są współczynnikami wielomianu
Qn−1 ( x ) = b0 x n−1 + b1 x n−2 + ... + bn−1 ,
(4)
będącego ilorazem uzyskanym przy dzieleniu danego wielomianu Pn ( x ) przez dwumian ( x − ξ ),
co wynika bezpośrednio z twierdzenia Bezouta
Pn ( x ) = Q n−1 ( x )( x − ξ ) + Pn ( ξ ).
(5)
Wstawiając bowiem wielomian (4) do wzoru (5), po uporządkowaniu wyrazów mamy
Pn ( x ) = b0 x n + (b1 − b0 ξ ) x n −1 + ... + (bn − bn−1 ξ )
i następnie przez porównanie współczynników tego wielomianu ze współczynnika-mi wielomianu
(1) dostajemy zale ności (2) i (3).
{Program 1.1}
uses
Crt;
var
k,n: Integer;
ksi,P: Real;
a,b: array[0..20] of Real;
zn: Char;
label powt;
begin
powt:
ClrScr;
Writeln('PROGRAM 1.1');
Writeln('Schemat Hornera.');
Writeln;
Write('Stopien wielomianu - n = ');
Read(n);
Writeln('Wspolczynniki wielomianu Pn(x):');
for k:=n downto 0 do begin
Write('
a[',k:2,'] = ');
Read(a[k]);
end;
Write('Argument - ksi = ');
Readln(ksi);
P:=a[n];
b[0]:=P;
for k:=1 to n do begin
P:=P*ksi+a[n-k];
b[k]:=P;
end;
Writeln;
Writeln('Pn(ksi) = ',P:13);
Writeln('Wspolczynniki wielomianu Qn-1(x):');
for k:=0 to n-1 do
Writeln('
b[',k:2,'] = ',b[k]:13);
Writeln;
Writeln('Nowe obliczenia: (t/n)?');
zn:=ReadKey;
if zn = 't' then goto powt;
end.
Program 1.1 oblicza przy u yciu schematu Hornera
wartość wielomianu (1) oraz współczynniki
wielomianu (4) po wczytaniu z klawiatury
współczynników a0 , a1 , ..., an i zadanej wartości ξ.
W charakterze przykładu wykonano następujące
obliczenia:
PROGRAM 1.1
Schemat Hornera.
Stopien wielomianu - n = 5
Wspolczynniki wielomianu Pn(x):
a[ 5] = 4
a[ 4] = 1
a[ 3] = 0
a[ 2] = -3
a[ 1] = 2
a[ 0] = -1
Argument - ksi = 3
Pn(ksi) = 1.031000E+03
Wspolczynniki wielomianu Qn-1(x):
b[ 0] = 4.000000E+00
b[ 1] = 1.300000E+01
b[ 2] = 3.900000E+01
b[ 3] = 1.140000E+02
b[ 4] = 3.440000E+02
Nowe obliczenia: (t/n)?
SUMOWANIE SZEREGÓW POTĘGOWYCH
Rozwijanie funkcji w szeregi potęgowe okazuje się w wielu przypadkach wygodnym sposobem
obliczania ich wartości. Zakładając, e funkcja f ( x) jest ciągła i ma dostateczną liczbę pochodnych w
otoczeniu punktu x = ξ mo emy przybli yć ją szeregiem potęgowym Taylora
n
f ( x) ≈ ∑
f
(i )
(ξ )
i
(x − ξ)
i!
i=0
(1)
lub te dla ξ = 0 szeregiem
(…)
… metod iteracyjnych jest metoda stycznych, nazywana najczęściej metodą
Newtona. Metodę tę zastosujemy do obliczania wartości funkcji uwikłanej, określonej równaniem
F ( x, y) = 0.
(1)
Zało ymy, e zarówno funkcja F ( x, y) jak i jej pochodna F ′( x, y) są ciągłe.
Ciąg kolejnych przybli eń metody stycznych Newtona napiszemy rozpatrując wykres funkcji (rys. 1.2)
z ( y ) = F ( x, y) ,
w której x pełni rolę…
… np.: wartość sinusa 2550° obliczona w podwójnej precyzji za pomocą szeregu (6)
wynosi 29.5.
Stąd te funkcje standardowe są wyznaczane przez kompilatory języków programowania przy
wykorzystaniu bardziej efektywnych algorytmów numerycznych.
Najbardziej optymalne algorytmy obliczania wartości szeregów potęgowych (5) ÷ (8) mo na uzyskać
wyznaczając zale ności rekurencyjne między kolejnymi wyrazami…
…)
w którym y0 jest zadanym przybli eniem początkowym.
Przerwanie obliczeń następuje w chwili, gdy dwa kolejne przybli enia
yn i yn+1
spełniają nierówność
yn +1 − yn < ε,
(5)
gdzie ε jest ądaną dokładnością obliczeń - co gwarantuje na ogół, e równie jest
y − yn+1 < ε,
gdy ciągi konstruowane w metodzie Newtona są bardzo szybkozbie ne i błędy zaokrągleń mają
niewielki wpływ na przebieg obliczeń. Proces iteracyjny…
... zobacz całą notatkę
Komentarze użytkowników (0)