Обчислення значення многочлена. Все тривіально в цьому питанні?

Обчислення значення многочлена в точці є однією з найпростіших класичних задач програмування.
При проведенні різного роду обчислень часто доводиться визначати значення многочленів при заданих значеннях аргументів. Часто наближене обчислення функцій зводиться до обчислення апроксимуючих многочленів.
Пересічного читача Хабрахабр не можна назвати недосвідченим у застосуванні всіляких збочень. Кожен другий скаже, що многочлен треба обчислювати за правилом Горнера. Але завжди є маленьке «але», завжди схема Горнера є найбільш ефективною?


Я не ставлю за мету точно описати алгоритми для обчислення многочленів, а лише показати, що в деяких випадках можна (потрібно) застосовувати схеми відмінні правила Горнера. Для тих, кого зацікавить матеріал, в кінці статті наведено список літератури, з якої можна ознайомитися для більш детального вивчення питання.
Крім того, іноді стає образливо, що прізвища наших російських математиків залишаються маловідомими. До того ж мені просто приємно розповісти про наших роботах математиків.

Схема Горнера
При обчисленні значень багаточленів дуже широке застосування отримало правило Горнера. Метод названий на честь британського математика Уїльяма Джорджа Горнера.
У відповідності з цим правилом многочлен n-го ступеня:
{{P}_{n}}(x)={{a}_{0}}{{x}^{n}}+{{a}_{1}}{{x}^{n-1}}+...+{{a}_{n-1}}x+{{a}_{n}}
представляється у вигляді
{{P}_{n}}(x)=(...(({{a}_{0}}x+{{a}_{1}})x+{{a}_{2}})x+...+{{a}_{n-1}})x+{{a}_{n}}.
Обчислення значення многочлена проводиться в порядку, що визначається дужками. Що маємо? Щоб обчислити многочлен {{P}_{n}}(x)за схемою Горнера, треба виконати n множень і n-k додавань (тут k – число коефіцієнтів многочлена, рівних 0). Якщо {{a}_{0}}=1, то множень n-1.
Можна показати, що для обчислення многочленів, загального вигляду не можна побудувати схему економічнішу за кількістю операцій, ніж схема Горнера.
Найбільша привабливість схеми Горнера полягає в простоті алгоритму для обчислення значення многочлена.

Виключення
При обчисленні багаточленів спеціального виду може знадобитися менше сисло операцій, ніж при застосуванні універсальної схеми Горнера. Наприклад, обчислення ступеня {{x}^{n}}за схемою Горнера означає послідовне перемноження n множників і вимагає n-1 множення. Однак кожен перший читач скаже, що для обчислення, наприклад, {{x}^{8}}потрібно послідовно обчислити {{x}^{2}}=x\cdot x{{x}^{4}}={{x}^{2}}\cdot {{x}^{2}}, {{x}^{8}}={{x}^{4}}\cdot {{x}^{4}}, тобто виконати множення 3 замість 7.

А є щось ще, адже схема Горнера сама економічна?
Насправді все вирішують обсяги обчислень. Якщо потрібно обчислити одне значення многочлена, то краще схеми Горнера нічого не придумано. Але якщо значення многочлена обчислюються у багатьох точках, то з'являється можливість заощадити велику кількість операцій множення за рахунок попередніх обчислень, виконуваних рівно один раз. Це може значно прискорити роботу програми.

В деяких випадках для отримання значень многочленів доцільно використовувати двоетапні схеми. На першому етапі виконуються дії тільки над коефіцієнтами многочлена, перераховуються до спеціального виду. На другому ж етапі обчислюють вже значення самого многочлена при заданих значеннях аргументу. При цьому може виявитися, що кількість операцій, виконуваних на другому етапі буде менше, ніж при обчисленнях за схемою Горнера.

Знову зауважу, що такі методи обчислень доцільні при обчисленні значень многочлена {{P}_{n}}(x)для великого числа значень x. Виграш виходить, за рахунок того, що перший етап для многочлена виконується лише один раз. Прикладом може послужити обчислення елементарних функцій, де наближає многочлен готуватися заздалегідь.

У подальших міркуваннях, говорячи про кількість операцій для обчислення {{P}_{n}}(x), я буду мати на увазі складність другого етапу обчислень.

Схема Дж.Тодта для багаточленів 6 ступеня
Маємо такий многочлен:

{{P}_{6}}(x)={{x}^{6}}+A{{x}^{5}}+B{{x}^{4}}+C{{x}^{3}}+D{{x}^{2}}+Ex+F.
Для обчислень використовуємо наступні допоміжні многочлени:

{{p}_{1}}(x)=x(x+{{b}_{1}}),

{{p}_{2}}(x)=({{p}_{1}}+x+{{b}_{2}})({{p}_{1}}+{{b}_{3}}),

{{p}_{3}}(x)=({{p}_{2}}+{{b}_{4}})({{p}_{1}}+{{b}_{5}})+{{b}_{6}}.

Коефіцієнти {{b}_{j}}визначаються методом невизначених коефіцієнтів виходячи з умови {{p}_{3}}(x)\equiv {{P}_{6}}(x). З останнього умови складаємо систему рівнянь, прирівнюючи коефіцієнти при однакових ступенях многочленів.

Саму систему, тут приводити не буду. Але вона легко вирішується методом підстановки, при цьому доводиться вирішувати квадратні рівняння. Коефіцієнти можуть бути комплексними, але якщо коефіцієнти виявляються дійсними, то обчислення вимагають трьох множень і семи додавань замість п'яти множень і шести додавань за схемою Горнера.

Говорити про універсальність даної схеми не доводиться, але зате читач наочно може оцінити зменшення числа операцій порівняно зі схемою Горнера.

Схема К. Ю. Кеткова
Нарешті, добрався і до наших математиків.

Ю. К. Кетков дав загальне уявлення многочлена n-го ступеня для n>5, завжди приводить до дійсним виразами і вимагає для обчислення многочлене n-й ступеня виконання [(n+1)/2]+[n/4] множень і n+1 складань.

Наприклад, при n=2k схема Кеткова зводиться до знаходження многочленів:

{{N}_{2}}(x)=x({{b}_{0}}+x)
{{N}_{4}}(x)=({{N}_{2}}+{{b}_{1}}+x)({{N}_{2}}+{{b}_{2}})+{{b}_{3}},
{{N}_{6}}(x)={{N}_{2}}{{N}_{4}}+{{b}_{4}}x+{{b}_{5}},
\cdots\cdots\cdots
{{N}_{2k}}(x)=({{N}_{2}}+{{s}_{k}}{{b}_{2k-2}}){{N}_{2k-2}}+{{r}_{k}}{{b}_{2k-2}}x+{{b}_{2k-1}},
де {{r}_{k}}=0{{s}_{k}}=1k –парнім, і {{r}_{k}}=1{{s}_{k}}=0, якщо k непарне (k>2).

Всі невідомі коефіцієнти знаходяться з рівності {{P}_{n}}(x)={{N}_{2}}. У роботах Кеткова для вирішення виходять систем дається метод, що дає завжди дійсні коефіцієнти {{b}_{j}}.

Схеми В. Я. Пана
Е. Белага у своїх роботах дав суворе доказ неможливості побудови схеми обчислення довільних багаточленів n-го ступеня, використовує на другому етапі менше, ніж [(n+1)/2]+1 множень і n складань.

В. Я. Пан займався питаннями оптимального обчислення многочленів. Зокрема, їм запропоновано кілька схем для обчислення дійсних багаточленів, які дуже близько підібралися до оцінок Е. Белаги. Наведу деякі схеми Пана для дійсних многочленів.
1. Схема для обчислення многочленів четвертого ступеня.
Розглядається многочлен {{P}_{4}}(x)={{a}_{0}}{{x}^{4}}+{{a}_{1}}{{x}^{3}}+{{a}_{2}}{{x}^{2}}+{{a}_{3}}x+{{a}_{4}}.

Уявімо {{P}_{4}}(x)у вигляді:

g(x)=x(x+{{\lambda }_{1}}),
{{P}_{4}}(x)\equiv {{a}_{0}}\left( \left( g(x)+{{\lambda }_{2}} \right)\left( g(x)+x+{{\lambda }_{3}} \right)+{{\lambda }_{4}} \right),
де

{{\lambda }_{1}}=\frac{{{a}_{1}}-{{a}_{0}}}{2{{a}_{0}}},{{\lambda }_{2}}=\frac{{{a}_{3}}}{{{a}_{0}}}-{{\lambda }_{1}}\frac{{{a}_{2}}}{{{a}_{0}}}+({{\lambda }_{1}}+1)\lambda _{1}^{2},
{{\lambda }_{3}}=\frac{{{a}_{2}}}{{{a}_{0}}}-{{\lambda }_{1}}({{\lambda }_{1}}+1)-{{\lambda }_{2}},{{\lambda }_{4}}=\frac{{{a}_{4}}}{{{a}_{0}}}-{{\lambda }_{2}}{{\lambda }_{3}}.
2. Схема для обчислення {{P}_{n}}(x)n\ge 5.
Будуємо допоміжні многочлени g(x)h(x){{p}_{s}}(x):

g(x)=x(x+{{\lambda }_{1}}),h(x)=g(x)+x,{{p}_{0}}(x)=x,
{{p}_{s}}(x)={{p}_{s-1}}(x)\left( (g(x)+{{\lambda }_{4s-2}})(h(x)+{{\lambda }_{4s-1}})+{{\lambda }_{4s}} \right)+{{\lambda }_{4s+1}}, s=1,2,...,k.

Для обчислення значення многочлена використаємо вирази:

{{P}_{n}}(x)\equiv {{a}_{0}}{{p}_{k}}(x), при n=4k+1,

{{P}_{n}}(x)\equiv {{a}_{0}}x{{p}_{k}}(x)+{{\lambda }_{n}}, при n=4k+2,

{{P}_{n}}(x)\equiv {{a}_{0}}\left( {{p}_{k}}(x)(g(x)+{{\lambda }_{n-1}})+{{\lambda }_{n}} \right), при n=4k+3,

{{P}_{n}}(x)\equiv {{a}_{0}}x\left( {{p}_{k}}(x)(g(x)+{{\lambda }_{n-2}})+{{\lambda }_{n-1}} \right)+{{\lambda }_{n}}, при n=4k+4,

Ця схема на другому етапі вимагає [n/2]+2множення і n+1додавання.

Особливістю даної схеми є те, що коефіцієнти {{\lambda }_{j}}завжди існують при n\ge 5і дійсних коефіцієнтів вихідного многочлена.

У В. Я. Пана існують і інші схеми для обчислення многочленів, в тому числі і для комплексних.

Висновок
Резюмуючи сказане, зазначу, що обчислення одного або декількох значень полінома безперечно потрібно проводити з використанням схеми Горнера.

Однак, якщо кількість значень полінома, які потрібно обчислити велике, а продуктивність дуже важлива, то має сенс розглянути застосування спеціальних методів обчислення многочленів.

Деякі читачі скажуть, що возитися з застосуванням схем, відмінних від схеми Горнера, важко, клопітно і не варто з цим зв'язуватись. Однак у реальному житті зустрічаються задачі, в яких потрібно обчислювати просто величезна кількість значень многочленів з великими ступенями (наприклад, на їх обчислення можуть йти місяці), і зменшення числа множень в два рази дасть суттєвий виграш у часі, навіть якщо вам доведеться витратити кілька днів на реалізацію конкретної схеми для обчислення многочленів.

Література
  1. Кетков Ю. К. Про один спосіб обчислення поліномів на математичних машинах. // Известия ВУЗ'ів. Радіофізика, т. 1., № 4, 1958
  2. В. Я. Пан, «Обчислення многочленів за схемами з попередньою обробкою коефіцієнтів і програма автоматичного знаходження параметрів», Ж. обч. матем. і матем. фіз., 2:1 (1962), 133-140
  3. В. Я. Пан, «Про способи обчислення значень многочленів», ПМН, 21:1(127) (1966), 103-134
  4. В. Я. Пан, «Про обчислення многочленів п'ятої та сьомої ступеня з речовими коефіцієнтами», Ж. обч. матем. і матем. фіз., 5:1 (1965), 116-118
  5. Пан В. Я. Деякі схеми для обчислення значень многочленів з дійсними коефіцієнтами. Проблеми кібернетики. Вип. 5. М.: Наука, 1961, 17-29.
  6. Белага Е. Р. Про обчислення значень многочлена від однієї змінної з попередньою обробкою коефіцієнтів. Проблеми кібернетики. Вип. 5. М.: Физматгиз, 1961, 7-15.


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.