Теоретическое описание схемы Горнера

Схема Горнера (или правило Горнера, метод Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена, а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида . Метод назван в честь Уильяма Джорджа Горнера.

Пусть задан многочлен:

.

Пусть требуется вычислить значение данного многочлена при фиксированном значении . Представим многочлен в следующем виде:

.

Определим следующую последовательность:

…

…

Искомое значение Р(x₀)=b₀ . Покажем, что это так.

В полученную форму записи Р(x₀) подставим х=x₀ и будем вычислять значение выражения, начиная со внутренних скобок. Для этого будем заменять подвыражения через :

Использование схемы Горнера для деления многочлена на бином

При делении многочлена на получается многочлен с остатком ,

при этом коэффициенты результирующего многочлена удовлетворяют рекуррентным соотношениям:

, .

При вычислениях применяют таблицу:

Таким же образом можно определить кратность корней (использовать схему Горнера для нового полинома). Так же схему можно использовать для нахождения коэффициентов при разложении полинома по степеням х-с:

 

1.2 Пошаговый алгоритм нахождение значение многочлена

по схеме Горнера

1) Введем значение x₀

2) Введем степень многочлена n

3) Начало цикла по i от 1 до n+1

4) Введем n+1 коэффициентов многочлена в массив a

5) Конец цикла

6) b[1]=a[1], где b – массив «новых» коэффициентов

7) Начало цикла по i от 2 до n+1

8) b[i]:=a[i]+b[i-1]*x₀

9) Выводим таблицу значений a[i] и b[i]

10) Выводим b_0, что и будет искомым ответом.

1.3 Код программы, реализующей схему Горнера

var n,i: integer;

a,b: array [1..1000] of real;

x,x0:real;

Begin

{Вводим степень многочлена и значение х0}

writeln('введите степень многочлена');

readln(n);

writeln('введите аргумент');

readln(x0);

{Цикл заполнения массива}

For i:=1 to n+1 do begin

writeln('введите коэффициент при степени ',n+1-i);

readln(a[i]);

b[i]:=a[i];

end;

b[1]:=a[1];

{считаем значения b[i]}

for i:=2 to n+1 do begin

b[i]:=a[i]+b[i-1]*x0;

end;

{вывод ответов}

For i:=1 to n+1 do begin

writeln;

writeln('степень: ',n+1-i);

writeln('коэффициент при степени ',n+1-i,' = ',a[i]);

writeln('элемент последовательности = ',b[i]);

end;

 

{вывод итогового ответа}

writeln;

writeln('Ответ = ',b[n+1]);

end.

1.4 Описание контрольного примера

Найти значение многочлена по схеме Горнера в заданной точке х=х₀:

Ответ:

1.5 Скриншот решения контрольного примера

 

1.6 Описание примера №2

Найти значение выражения по схеме Горнера:

,

при заданном многочлене:

1.7 Скриншот примера №2

 

 

Презентационные материалы по методу «Схема Горнера»

 

 

 

4.

 

 

 

Вычислительный практикум

Вариант 14