Статья: Вычисление многочленов от Ньютона до наших дней
А что если для каждого многочлена существует своя схема, гораздо более экономная, чем схема Горнера?
Такие схемы можно было бы искать либо исходя из особенностей отдельного многочлена (искусно комбинируя его коэффициенты), либо сконструировав универсальный метод построения схем, намного более экономных, чем схема Горнера, но, возможно, для некоторых многочленов не наилучших. Недостаток первого подхода в том, что для каждого многочлена придется придумывать свои приёмы, и нет никакой гарантии, что нам это всегда удастся; позже (в §10) мы увидим, что второй путь надёжнее во всех отношениях.
Само собой разумеется, что оба эти метода уместны лишь в тех случаях, когда конкретный многочлен приходится вычислять так часто, что стоит потратить и время, и усилия, чтобы построить для него хорошую схему. Многочлены же «разового пользования» проще вычислять, скажем, по схеме Горнера.
Возможно, подобные рассуждения и привели в 1955 году к открытию универсальной схемы совершенно нового типа для многочлена шестой степени. Мы проиллюстрируем основную идею этой схемы на примере более простой схемы — для многочленов степени 4. Пусть
| f (x) = x4 + ax3 + bx2 + cx + d; | (4) |
положим
|
p1 = x(x + A), p2 = (p1 + B)(p1 + x + C) + D, f (x) = p2, | (5) |
где A, B, C и D — параметры.
Пример. Многочлен x4 + 3x3 + 6x2 + 3x + 2 можно вычислять по схеме: p1 = x(x + A), f (x) = (p1 – 1)(p1 + x + 5) + 7, содержащей два умножения (вместо трёх по Горнеру) и пять (вместо четырёх) (+, –)-операций; здесь A=1, B=–1, C=5, D=7.
Выпишем явное выражение для p2(x):
p2(x) = x4 + (2A + 1)·x3 + (A2 + A + B + C)·x2 +
+ (AB + B + AC)·x + BC + D;
приравняв коэффициенты f (x) и p2(x), выразим параметры, входящие в формулу (5), через коэффициенты (4):
|
A = (a – 1)/2; B = c – bA + A2(A + 1); C = b – B – A(A + 1); D = d – BC. | (6) |
Из этих формул ясно, что схема (5) универсальна.
Операции (6) мы будем называть предварительной обработкой коэффициентов многочлена; разумеется, они не включаются в число операций схемы: ведь для каждого данного многочлена они выполняются лишь однажды, а наша задача — научиться быстро считать значения произвольного, но фиксированного многочлена при разных x.
§5. Универсальная схема степени n
|
— Я думаю, — сказал глубокомысленно Пятачок, — что если бы Иа встал под деревом, а Пух встал к нему на спину, а я встал на плечи Пуха... — И если бы спина Иа-Иа неожиданно треснула, то мы бы все здорово посмеялись, — сказал Иа. А. А. Милн. Винни Пух |
В 1958 году была найдена общая универсальная схема с предварительной обработкой коэффициентов. Структура этой схемы для многочлена чётной степени (n=2k) напоминает пирамиду — в основании лежит схема (5) (в её «прочности» мы уже убедились), содержащаяся в схеме степени 6, которая содержится в схеме степени 8 и т.д.:
|
К-во Просмотров: 794
Бесплатно скачать Статья: Вычисление многочленов от Ньютона до наших дней
|