§ 7. Схема Горнера
Схема Горнера – это некоторая вычислительная процедура, применимая во многих задачах, связанных с числами и многочленами. Здесь будут рассмотрены лишь некоторые простейшие примеры.
I. Вычисление значения многочлена
Пусть K – коммутативное кольцо, f(x) = fnxn+…+f1x+f0 K[x], K. Как вычислить значение многочлена в точке : f() = fnn+…+f1+f0 ? Непосредственное вычисление по этой формуле сопряжено с некоторыми проблемами. Упомянем лишь некоторые из них:
вычислять все степени i (2 i n), умножать их на соответствующие коэффициенты fi , а затем складывать – это очень трудоёмкая последовательность операций, требующая к тому же и ресурсов памяти;
во многих случаях невозможно (даже на современных ЭВМ) стандартными средствами вычислить степень n , но применяя другую схему вычислений можно, тем не менее, вычислить значение многочлена. Например, для f(x) = x32 – x31 – 1 вычислить точно 232 на 32-х разрядном компьютере не удастся (получится значение 0), но на самом деле f(2) = 232 – 231 – 1 = 231(2–1) – 1 = 231 – 1, и это значение вычислимо стандартными средствами;
если коэффициенты многочлена и – действительные числа, то при возведении в степени быстро накапливаются ошибки округления, что снижает точность результата.
Заметим, что f() = fnn+…+f1+f0 = ((…((((fn)+fn–1)+fn–2)+fn–3)…)+f1)+f0 . Обозначим Sn= fn , Sn–1 = (fn)+fn–1 = Sn+fn–1 , Sn–2 = ((fn)+fn–1)+fn–2 = Sn–1+fn–2 , … … , S1 = (…((((fn)+fn–1)+fn–2)+fn–3)…)+f1 = S2+f1 , S0 = S1+f0 = f() . Таким образом, имеют место следующие рекуррентные формулы:
,
которые и называются схемой Горнера.
Пример: Вычислить значение многочлена f(x) = 4x4–3x3+2x–1 при x = –2.
Оформим решение в виде таблицы:
fi |
4 |
–3 |
0 |
2 |
–1 |
Si(–2) |
4 |
4(–2)–3=–11 |
(–11)(–2)+0=22 |
22(–2)+2=–42 |
(–42)(–2)–1=83 |
Итак, f(–2) = 83.
Легко понять, что
реализация вычислений по схеме Горнера требует выполнения n умножений и n сложений. При этом в памяти нужно хранить лишь самое необходимое: коэффициенты многочлена fi (0 i n), значение и переменную, в которой последовательно насчитывается значение f();
во многих случаях, когда коэффициенты многочлена знакопеременные, по схеме Горнера удаётся вычислять значения многочлена, даже если невозможно вычислить степень n. Убедитесь самостоятельно, что можно вычислить, например f(2) для f(x) = x32 – x31 – 1.
ошибки округления при вычислении по схеме Горнера соизмеримы с ошибками, получающимися при возведении числа в n-ю степень.
Таким образом, даже самые минимальные косметические усилия по оптимизации вычислений, реализованные в схеме Горнера (и состоящие всего-то в правильной расстановке скобок !!), окупаются при решении вычислительных задач.