Technika obliczeniowa i
symulacyjna (TOiS lub TOS)
dr inż. Czesław Michalik
ITA, KTS
Zajęcia 2
Wybrane algorytmy obliczeniowe
Obliczanie wartości wielomianu w
zadanym punkcie
x0
Przypomnienie wiadomości
Postać ogólna wielomianu:
p(x) =� a1xn +� a2xn-�1 +�...+� anx +� an+�1
Jak obliczyć wartość wielomianu w
punkcie?
Wez
my przykładowy wielomian stopnia 4&
p(x) =� 2x4 -� 5x2 +� 4x +�1
I zadaną wartość
3
x0 =� .
2
Szukamy:
p(x0) =� 2x04 -� 5x02 +� 4x0 +�1
Jak to zrobić? Nic prostszego& wystarczy wstawić
określoną wartość do wielomianu..
42
33 3 3
pć� �� =� 2ć� �� -� 5ć� �� +� 4ć� �� +�1 =�
�� �� �� �� �� �� �� ��
22 2 2
Ł� ł� Ł� ł� Ł� ł� Ł� ł�
3 3 3 3 3 3 3
ć� ��
2ć� ��ć� ��ć� ��ć� �� -� 5�� ��ć� �� +� 4ć� �� +�1 =�
�� ���� ���� ���� �� ���� �� ��
2 2 2 2 2 2 2
Ł� ł�Ł� ł�Ł� ł�Ł� ł� Ł� ł�Ł� ł� Ł� ł�
81 9 3
2ć� �� -� 5ć� �� +� 4ć� �� +�1 =�
��16 �� �� �� �� ��
4 2
Ł� ł� Ł� ł� Ł� ł�
81 45 9 7 47
-� +� 6 +�1 =� -� +� 7 =� 5 =�
8 4 8 8 8
Pytanie:
Czy nie ma lepszej
metody, obliczania
wartości wielomianu w
punkcie?
Odp. JEST!!!
Z pomocą przychodzi nam twierdzenie
brytyjskiego matematyka& Williama
George a Hornera
znane jako:
SCHEMAT HORNERA
Zastosujmy schemat do naszego przykładu
p(x) =� 2x4 -� 5x2 +� 4x +�1 =� 2xxxx -� 5xx +� 4x +�1 =�
=� x(x(x(x �� 2 +� 0) -� 5) +� 4) +�1
Teraz wstawiamy wartość i otrzymujemy
��
3 3 3 ć� 3 3 �� 3 ć� 3 9 ��
ć� �� ć� ć�
p =�
��
�� ��2 2 2 2 �� �� ��
�� ���� 2 +� 0�� -� 5�� +� 4�� +�1 =� ��-� 5�� +� 4�� +�1 =�
2 2 2 2
Ł� ł� Ł� ł� Ł� ł�
Ł�ł� Ł� ł�
Ł�ł�
3 ć� 3 1 �� 3 3 3 13 47
ć��� ć�
=� -� +� 4�� +�1 =� -� +� 4�� +�1 =� +�1 =�
�� ���� �� ��
2 2 2 2 4 2 4 8
Ł�ł� Ł� ł�
Ł�ł�
Tabelka i Horner
p(x) =� 2x4 -� 5x2 +� 4x +�1
Obliczenia praktycznie jest przeprowadzać w tabeli: w
jej pierwszym wierszu wypisujemy wszystkie (!!!)
współczynniki wielomianu p(x), a w dolnym wpisujemy
kolejno wyniki obliczeń:
-�5
41
2
0
3 13 47
3 1 13
3 1 ��+�4=�
3 3
�� +�1=�
��ć�-�
2 ��2+�0=�3 ��3-�5=� -�
��
2 4 8
2 2�� 4
2 2 2 2
Ł� ł�
Algorytm
p(x) =� a1xn +� a2xn-�1 +�...+� anx +� an+�1
W punkcie x0 wyraża się wzorem rekurencyjnym
b1 =� a1,
bi =� ai +� x0bi-�1 (i =� 2,...n +�1),
p(x0) =� bn+�1
Jeśli pośrednie bi nie są interesujące to algorytm można
przedstawić w postaci następującego schematu
Schemat Hornera
(w Matlabie funkcja polyval)
b = a1,
i =1, x0
i = i+1,
b = bx0 +ai
Tak
?
Nie
Wyjście
i=n+1
p(x0) = b
Inne zastosowanie
Zauważmy, że dzieląc wielomian stopnia n przez dwumian
(x c), otrzymujemy wielomian stopnia n 1
p(x) - stopień n
w(x) -stopień n-1
p(x) =� (x -� x0)w(x) +� r
r - reszta
Współczynniki wielomianu w(x)
otrzymujemy z dolnego wiersza
tabelki!!!
W naszym przypadku
Wielomian
p(x) =� 2x4 -� 5x2 +� 4x +�1
-�5
41
2
0
3 13 47
3 1 13
��+�4=�
3 3 3 1
�� +�1=�
��ć�-�
��2+�0=�3
��3-�5=� -�
2
��
2 4 8
2 2�� 4
2 2
2 2 Ł� ł�
Możemy zapisać w postaci:
3 113 47
p(x) =� (x -� )(2x3 +� 3x2 -� x +� ) +�
2 248
Schemat Hornera
(w Matlabie funkcja deconv)
b1 = a1,
i =1, x0
i = i+1,
bk = bk-1x0 +ai
Tak
?
Nie
Wyjście
i=n+1
b
Dzielenie wielomianu przez dwumian
- inny przykład
Dzielenie krok po kroku w schemacie Hornera
(x3 -� 4x2 +� 3x -� 5) : (x -� 2)
Dzielenie wielomianu przez dwumian
x-x0
(x3 -� 4x2 +� 3x -� 5) : (x -� 2)
x0 = 2
Schemat
x0 = 2
Hornera
x0 = 2
Schemat Hornera c.d
(x3 -� 4x2 +� 3x -� 5) : (x -� 2)
x0 = 2
Zalety schematu Hornera
Obliczanie wartości wielomianu
w zadanej wartości, przy wykorzystaniu
schematu oszczędza Nasz cenny czas&
upraszcza obliczenia (możemy odstawić
w kąt kalkulatory)& sprawia, że dzielenie
wielomianów przez dwumian nie jest
takie straszne J�
Schemat Hornera
zamiana liczby zapisanej w innym systemie niż
dziesiętnym
aa2...an+1 b = abn +a2bn-1 +...+anb+an+1
()
1 1
b  podstawa systemu,
b � 2,9
[ ]
Widać, że to jest wartość wielomianu p(x) w punkcie x =x0 = b
Zadanie dla studentów
Sformułowanie problemu
Mamy N=100 liczb naturalnych z zakresu
<0, 100>. Wśród tych liczb są pewne liczby, które
powtarzają się (np. k razy), pewnych liczb
brakuje. Naszym zadaniem jest wskazanie jakich
liczb z przedziału <0, 100> brakuje oraz jakie
liczby powtarzają się więcej niż jeden raz.
Badany zbiór liczb wygenerować za pomocą
instrukcji w Matlabie
r=round(100*rand(1,100)).