Algorytm Hornera

Zgodnie z prośbą cośniecoś postaram się z polskiego na nasze przełożyć ;)

No to tak, bierzemy jakiś wielomian, np 7x⁵ - 3x⁴ + 2x³ - 14x² + x - 3

Co z nim robimy?? Ano bierzemy siódemeczkę, mnożymy ją przez x, odejmujemy 3 i mnożymy wszystko przez x, dodajemy 2 i
mnożymy wszystko przez x i tak aż do końca. Co do implementacji… Nie daje głowy że to zadziała, a nie mam w tej chwili czasu na
testy więc sklecę coś na szybko ;)

#include <iostream>
 
using namespace std;
 
int main()
{
   int podstawy[1000], n, x;
   char znaki[1000];
   long long suma=0;
   cout << "Podaj największy wykładnik wielomianu i wartość x: ";
   cin >> n >> x;
   cout << "A teraz podstawy kolejnych potęg wraz ze znakami(oddzielone spacją):" << endl;
   for (int i=n; i>=0; i--)
      cin >> znaki[i] >> podstawy[i];
   for (int i=n; i>0; i--)
   {
      if (znaki[i]=='+')
         suma+=podstawy[i];
      else suma-=podstawy[i];
      suma*=x;
   }
   suma+=podstawy[0];
   cout << suma << endl;
   return 0;
}

Algorytm Hornera

pomaga obliczyć wartość dowolnego wielomianu, oraz jego pochodnych w dowolnym punkcie.
Wielomian możemy zapisać w postaci:

w(x)=anxn + an-1xn-1 + … + a2x2 + a1x + a0

gdzie ak(k=0,1,…,n) są liczbami rzeczywistymi, x jest zmienną. W zależności od wartości zmiennej x wielomian w(x) przyjmuje różne wartości.

Algorytm Hornera oblicza te wartości dla konkretnie przyjętych współczynników ak i zmiennej x. Wyłączając x sprowadźmy wielomian w do postaci:

w(x)=(anxn-1 + an-1xn-2 + … + a2x + a1)x + a0.

Powtarzając to postępowanie otrzymujemy następującą równoważną postać wielomianu w :

w(x)=(…((anx + an-1)x + … + a2)x + a1)x + a0.

Powtarzające się operacje, które tworzą następujący schemat, zwany algortymem Hornera wygladają nastepująco :

// zmienna - pomocnicza zmienna
// := --->  operacja przypisania :) 
zmienna := an
zmienna := zmienna*q + an-i (tę linię powta kolejno dla i=1,2,...,n)

Otrzymana po wszystkich powtórzeniach wartość w zmiennej pom jest już szukaną wartością w(q).

Jednak nie to nas tak bardzo interesuje

Próbując ustawić otrzymywane kolejno wartości zmiennej zmienna w ciąg oznaczając je :

bn,bn-1,…,b2,b1,b0.

Wyglądałby on następująco:

bn = an
bi = bi+1*q + ai

gdzie i=n-1,n-2,…,1,0 oraz q jest punktem, dla którego poszukujemy wartości wielomianu w.
Okazuje się, że wielomian:

w1(x)=bnxn-1 + bn-1xn-2 + … + b2x + b1

jest ilorazem otrzymanym z dzielenia wielomianu w(x) przez x-q, a b0 - resztą z tego dzielenia.
Różniczkując to dalej stronami względem x otrzymujemy:

w|(x) = w1|(x)*(x-q) + w1(x).

W punkcie q mamy jednak: w|(q) = w1(q).

Widać, że aby otrzymać wartość pierwszej pochodnej wielomianu w w punkcie q należy tylko obliczyć wartość wielomianu w1 w tym samym punkcie q. Czyli powinniśmy wykonać algorytm Hornera dwa razy.

Myślę, że teraz po lekcjach o wielomianach na matematyce wszystko wydaje się zrozumiałe, zwłaszcza, że przerabialiśmy schemat Hornera i temat ten był często poruszany :)
 
Chase