МенюСхема на Хорнер за полиноми
Полиномите имат следния вид:
$f(x)=\sum\limits_{k=0}^{n} a_k x^k$
или
Където ak са реални числа, наречени коефициенти на полинома, а
xk са променливи.
Казваме, че полиномът по-горе е от nта степен, т.е. deg(f(x)) = n, където n е най-голямата степен на променливата.
Правилото на Хорнер за деление на полиноми се използва, за да опростим процеса на намиране на стойността на полином f(x) за определена стойност x = x0 като разделим полинома на едночлени(полиноми от 1ва степене). Всеки едночлен включва не повече от едно умножение и едно събиране. Резултатът получен от един едночлен се прибавя към резултата получен от следващия едночлен и т.н. Това разделение процес е известен като синтетично разделение.
Нека да илюстрираме казаното по-горе с общия вид на полинома:
Той може да се запише като:
За да изчислим стойността на полинома трябва да направим следните стъпки:
2. Нека bk = ak
3. Нека bk - 1 = ak - 1 + bkx0
4. Нека k = k - 1
5. Ако k ≥ 0 връщаме се в 3
Край
Ще илюстрираме написаното по-горе с полином от 5-та степен
и ще намерим стойността на полинома за x = x0 като го преобразуваме във вида:
Друг начин, за да представим резултата от алгоритъма е чрез таблицата по-долу:
| K | 5 | 4 | 3 | 2 | 1 | 0 |
| b5 = a5 | b4 = a4 + x0b5 | b3 = a3 + x0b4 | b2 = a2 + x0b3 | b1 = a1 + x0b2 | b0 = a0 + x0b1 |
Пример: определете стойността на полинома f(x) = x4 + 3x3 + 5x2 + 7x + 9 за x = 2
Решение:
Тъй като полинома е от 4та степен, тогава n = 4
| K | 4 | 3 | 2 | 1 | 0 |
| Стъпка | b4 = 1 | b3 = 3 + 2 . 1 | b2 = 5 + 2 . 5 | b1 = 7 + 2 . 15 | b0 = 9 + 2 . 37 |
| Резултат | 1 | 5 | 15 | 37 | 83 |
Следователно, f(2) = 83.
