Лабораторная работа «Алгоритмы вычисления значений полиномов»

Цель: научиться использовать алгоритмы вычисления значений полиномов.

В алгебре деление многочленов столбиком (или уголком) — алгоритм деления многочлена {\displaystyle f(x)} на многочлен {\displaystyle g(x)}, степень которого меньше или равна степени многочлена {\displaystyle f(x)}. Алгоритм представляет собой обобщенную форму деления чисел столбиком, легко реализуемую вручную.

Для любых многочленов {\displaystyle f(x)} и {\displaystyle g(x)}, {\displaystyle g(x)\neq 0}, существуют единственные многочлены {\displaystyle q(x)} и {\displaystyle r(x)}, такие что

{\displaystyle {\frac {f(x)}{g(x)}}=q(x)+{\frac {r(x)}{g(x)}}},

причем {\displaystyle r(x)} имеет более низкую степень, чем {\displaystyle g(x)}.

Целью алгоритма деления многочленов в столбик является нахождение частного {\displaystyle q(x)} и остатка {\displaystyle r(x)} для заданных делимого {\displaystyle f(x)} и ненулевого делителя {\displaystyle g(x)}

Схе́ма Го́рнера (или правило Горнера, метод Горнера, метод Руффини-Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена[1], а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида {\displaystyle x-c}. Метод назван в честь Уильяма Джорджа Горнера, однако Руффини опередил Горнера на 15 лет, а китайцам этот способ был известен еще в XIII веке.

В самом общем виде степенной полином от нескольких переменных можно записать формулой

То есть в полином входят все одночлены, в которых сумма степеней переменных не превышает порядка полинома . Рассмотрим алгоритмы вычисления такого полинома, а также получения массива значений отдельных одночленов, входящих такой полином.

Вычислять каждый одночлен по-отдельности — не лучшая идея. Если верить известной книге Numerical Recipes, то когда машины захватят мир, люди, виновные в подобном издевательстве над компьютером, будут немедленно казнены.

На самом деле каждый одночлен порядка k может быть вычислен по одному из одночленов порядка k-1 с помощью только одного умножения. Например, одночлены первого порядка получаются домножением одночлена нулевого порядка (единицы) на одну из переменных. Домножив снова каждый из этих одночленов на одну из переменных, получим все возможные одночлены второго порядка и т.д. Одночлены k-1-го порядка

множим на одну из переменных и получаем одночлены k-го порядка.

Однако, начиная со второго порядка появляется проблема: одночлен будет получен два раза. Собственно, сколько есть вариантов перестановки сомножителей в формуле (2), столько раз и будет получен каждый одночлен. Чтобы не производить подобных повторных вычислений, договоримся, из всех последовательностей вычисления одночлена (2) выбирать такой, при котором индексы переменных упорядочены по возрастанию. Чтобы достичь этого, будем домножать на только те одночлены, которые не содержат переменных с номерами больше i. Тогда на домножаются только те, которые являются степенями , на — только содержащие и и т.д.