СХЕМА ГОРНЕРА НА MATHCAD 15

Схе́ма Го́рнера – алгоритм вычисления значения многочлена, записанного в виде суммы одночленов, при заданном значении переменной. Метод назван в честь Уильяма Джорджа Горнера [2].

Схема Горнера позволяет:

• отыскивать корни многочлена;
• вычислять значение многочлена и его производной в заданной точке;
• производить деление многочлена на бином .

Рассмотрим как «работает» схема Горнера на примере. Пусть необходимо найти корни уравнения

Сначала методом подбора определим один корень. По теореме Виета его следует искать среди делителей свободного члена. В данном случае целыми делителями числа 120 являются: ±1, ±2, ±3, ±4, ±5, ±6, ±8, ±10, ±12, ±15, ±20, ±24, ±30, ±40, ±60, ±120.

Далее, используя схему Горнера, определим корень  и осуществим деление многочлена  на одночлен . Для этого многочлен переписывается в виде

Таким образом, многочлен приобретает вид «матрёшки» а вычисления следует проводить, начиная с внутренней «самой маленькой матрёшки».

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

Таблица 1.

Перебор возможных корней для уравнения четвёртой степени.

В верхней строке прописываются коэффициенты исходного многочлена. В первой ячейке второй строки ставится возможный корень из ранее определённого списка. Далее в этой строке пишутся коэффициенты многочлена, вычисленные по принципу «матрёшек» (2). Значение в последнем столбце – это остаток от деления. Если остаток равен нулю, то проверяемое число является корнем уравнения. В противном случае – число не является корнем. При этом получены значения функции:

, , .

В нашем примере числа 1 и – 1 не являются корнями, а число 2 – корень. При этом значения, полученные в последней строке, являются коэффициентами многочленами, представляющего собой частное от деления данного многочлена на одночлен. Таким образом, , а исходный многочлен может быть разложен на множители:

.

Далее будем искать корни уравнения

.

Список возможных целых корней: ±1, ±2, ±3, ±4, ±5, ±6, ±10, ±12, ±15, ±20, ±30, ±60. Но т.к. ±1 не являлись корнями исходного уравнения, то они исключатся из нашего списка. Далее заполняем таблицу 2.

Таблица 2.

Перебор возможных корней для уравнения третьей степени.

Таким образом, , а исходный многочлен может быть разложен на множители:

.

Далее будем искать корни уравнения

Список возможных целых корней: ±1, ±3, ±5, , ±15. Значения ±1 и ±3 исключаем, остаются только ±15. Далее заполняем таблицу 3.

Таблица 3.

Перебор возможных корней для уравнения второй степени.

Таким образом,  и , а исходный многочлен может быть разложен на множители:

.

Замечание: корни уравнения (3) можно искать как корни квадратного уравнения, используя дискриминант.

Как видно из рассмотренного примера процесс отыскания корней «вручную» довольно затруднителен. Он становится тем сложнее, чем выше степень многочлена. В этом случае целесообразно использовать ЭВМ. Использование схемы Горнера для вычисления значений многочленов не только экономит машинное время (требуется 2п вычислительных операций), но и увеличивает точность вычислительного процесса за счёт уменьшения машинных (компьютерных) погрешностей [1, 3].

Блок-схема вычислительного алгоритма представлена в работе [1].

Рассмотрим реализацию схемы Горнера на MathCAD 15.

Для того, чтобы вычислить корни многочлена, следует записать коэффициенты при х в матрицу-столбец.

Функция, осуществляющая перебор корней, возвращает число, кратное свободному члену многочлена, чередуя положительные и отрицательные возможные корни:

Функция подсчёта новых коэффициентов, возвращающая массив, который содержит коэффициенты многочлена, получившегося в результате деления начального многочлена на .

Функция, редактирующая матрицу (убирает последний 0). Нужна для того случая, когда свободный член многочлена равен 0.

Основной фрагмент программы:

Список литературы:

1. Зубехин А.А., Бородавченко Д.В., Агишева Д.К., Светличная В.Б., Матвеева Т.А. ВЫЧИСЛЕНИЕ ЗНАЧЕНИЙ ПОЛИНОМА С ПОМОЩЬЮ СХЕМЫ ГОРНЕРА // Материалы VIII Международной студенческой электронной научной конференции «Студенческий научный форум» [электронный ресурс] — Режим доступа. — URL: http://www.scienceforum.ru/2016/1762/20652 (дата обращения: 12.04.2016).
2. Материал из Википедии – свободной энциклопедии: Схема Горнера. – Режим доступа: https://ru.wikipedia.org/wiki/Схема_Горнера (дата обращения: 12.04.16)
3. Турчак Л.И. Основы численных методов: Учеб. пособие. – М.: Наука. Гл. ред. физ.-мат. лит., 1987. – 320 с.