Referat na temat- SCHEMAT HORNERA.

Schemat Hornera – to sposób obliczania wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń, jest to również algorytm dzielenia wielomianu przez dwumian . Schemat ten wiązany jest z nazwiskiem Hornera, był jednak już znany Newtonowi, Ruffiniemu i matematykom chińskim w XII wieku. Przy dzieleniu wielomianów schemat Hornera można stosować tylko wtedy gdy w dwumianie nie ma przy żadnej potęgi i współczynnika. Dla przykładu: dla dzielenia przez dwumian można stosować schemat Hornera. Jednak dla dzielenia przez dwumian schematu Hornera stosować już nie wolno. Dla dzielenia wielomianu przez dwumian można stosować schemat Hornera, jeżeli najpierw podzieli się dwumian i wielomian, przez 3. Weźmy na przykład pod uwagę następujący wielomian: 7x4 + 3x3 + 5x2 + 9x + 1 Weźmy pod uwagę pierwsze cztery elementy naszego wielomianu. Możemy dla tych elementów wyłączyć wspólny czynnik przed nawias. Tym czynnikiem jest x: (7x3 + 3x2 + 5x + 9)x + 1 Teraz "wyciągamy" przed nawias x z pierwszych trzech elementów w nawiasie: ((7x2 + 3x + 5)x + 9)x + 1 Następnie wyłączmy przed nawias następne x z dwóch pierwszych elementów w wewnętrznym nawiasie: ((7x + 3)x + 5)x + 9)x + 1 I to wszystko! Na tym polega cały schemat Hornera. Niby nic... Proszę teraz porównać liczbę mnożeń w początkowym wielomianie i w tym na końcu. Dla przejrzystości rozpiszę je: 7*x*x*x*x + 3*x*x*x + 5*x*x + 9*x + 1, czyli 10 mnożeń i 4 dodawania ((7*x + 3)*x + 5)*x + 9)*x + 1, czyli 4 mnożenia i 4 dodawania Obydwa wyrażenia reprezentują to samo, ale dzięki zastosowaniu schematu Hornera drugie zawiera dużo mniej mnożeń. Dla wielomianu n-tego stopnia w zwykłej postaci należy wykonać n*(1+n)/2 mnożeń, a dla wielomianu po zastosowaniu schematu Hornera tylko n mnożeń! Różnica jest olbrzymia.