Перейти к содержанию

Вычисление значения многочлена. Все ли тривиально в этом вопросе? Тема урока "Теорема Безу

Содержание статьи

1.1 Общее описание алгоритма

1.1.1 Решаемая задача

Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

На рис.4 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Согласно данному рисунку, реализация схемы Горнера показывает низкую производительность работы с памятью. Может показаться странным, что значение daps в этом случае значительно меньше, чем для тестов STREAM, несмотря на то, что профиль обращений во всех случаях очень похож – несколько одновременно выполняемых последовательных переборов массивов.

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

for (int i = 1 ; i < size ; i ++ ) { c [ i ] = a [ i ] + c [ i - 1 ] * x ; }

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

Подобный пример лишний раз показывает, насколько сложно утроена подсистема памяти – совсем небольшое изменение строения тела цикла приводит к достаточно неожиданному серьезному замедлению программы.

Вычисление значения многочлена. Все ли тривиально в этом вопросе? Тема урока "Теорема Безу

Рисунок 4. Сравнение значений оценки daps

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рис.5 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что реализация схема Горнера обладает очень высокой локальностью согласно оценке cvg.

Вычисление значения многочлена. Все ли тривиально в этом вопросе? Тема урока "Теорема Безу

Рисунок 5. Сравнение значений оценки cvg

Как мы видели ранее, это плохо соотносится с реальной производительностью работы с памятью из-за особенностей строения памяти. Однако здесь необходимо сделать два замечания. Во-первых, подобные случаи, когда производительность работы с памятью настолько сильно зависит от специфичных аппаратных особенностей строения подсистемы памяти, на практике встречаются не так часто. Во-вторых, cvg предназначена для получения машинно-независимой оценки локальности; на данном уровне учесть подобные аппаратные особенности, по крайней мере, без потери доли машинно-независимых свойств, вряд ли представляется возможным.

2.3 Возможные способы и особенности параллельной реализации алгоритма

Описываемый алгоритм не предполагает параллельной реализации.

2.4 Масштабируемость алгоритма и его реализации

Понятие масштабируемости неприменимо, поскольку описываемый алгоритм не предполагает параллельной реализации. Проведём исследование масштабируемости вширь реализации алгоритма согласно методике . Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета . Набор и границы значений изменяемых параметров запуска реализации алгоритма:

  • число процессоров 1;
  • размер области с шагом 10240.

В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:

  • минимальная эффективность реализации 0.0324%;
  • максимальная эффективность реализации 0.0331%.

На следующих рисунках приведены графики производительности и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.

Вычисление значения многочлена. Все ли тривиально в этом вопросе? Тема урока "Теорема Безу

Рисунок 6. Реализация алгоритма. Изменение производительности в зависимости от размера вектора.

Вычисление значения многочлена. Все ли тривиально в этом вопросе? Тема урока "Теорема Безу

Рисунок 7. Реализация алгоритма. Изменение эффективности в зависимости от размера вектора.

Мизерная эффективность, по-видимому, связана с избыточной локальностью, описанной в разделе о .

2.5 Динамические характеристики и эффективность реализации алгоритма

В силу последовательности алгоритма и его избыточной локальности, исследование его динамических характеристик малоценно.

Для проведения экспериментов использовалась реализация алгоритма схемы Горнера, в реализации, доступной . Все результаты получены на суперкомпьютере "ГрафИТ!". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор Gnu 4.4.7. На рисунках показана эффективность реализации алгоритма встречной прогонки.

Цели урока:

  • научить учащихся решать уравнения высших степеней используя схему Горнера;
  • воспитывать умение работать в парах;
  • создать в совокупности с основными разделами курса базу для развития способностей учащихся;
  • помочь ученику оценить свой потенциал, развивать интерес к математике, умение мыслить, высказываться по теме.

Оборудование: карточки для работы в группах, плакат со схемой Горнера.

Метод обучения: лекция, рассказ, объяснение, выполнение тренировочных упражнений.

Форма контроля: проверка задач самостоятельного решения, самостоятельная работа.

Ход урока

1. Организационный момент

2. Актуализация знаний учащихся

Какая теорема позволяет определить, является ли число корнем данного уравнения (сформулировать теорему)?

Теорема Безу. Остаток от деления многочлена Р(х) на двучлен х-с равен Р(с), число с называют корнем многочлена Р(х), если Р(с)=0. Теорема позволяет, не выполняя операцию деления, определить, является ли данное число корнем многочлена.

Какие утверждения облегчают поиск корней?

а) Если старший коэффициент многочлена равен единице, то корни многочлена следует искать среди делителей свободного члена.

б) Если сумма коэффициентов многочлена равна 0, то один из корней равен 1.

в)Если сумма коэффициентов стоящих на четных местах, равна сумме коэффициентов, стоящих на нечетных местах, то один из корней равен -1.

г) Если все коэффициенты положительны, то корнями многочлена являются отрицательные числа.

д) Многочлен нечетной степени имеет хотя бы один действительный корень.

3. Изучение нового материала

При решении целых алгебраических уравнений приходиться находить значения корней многочленов. Эту операцию можно существенно упростить, если проводить вычисления по специальному алгоритму, называемому схемой Горнера. Эта схема названа в честь английского ученого Уильяма Джорджа Горнера. Схема Горнера это алгоритм для вычисления частного и остатка от деления многочлена Р(х) на х-с. Кратко, как он устроен.

Пусть дан произвольный многочлен Р(х)=а 0 х n + а 1 х n-1 + …+ а n-1 х+ а n . Деление этого многочлена на х-с – это представление его в виде Р(х)=(х-с)g(х) + r(х). Частное g(х)=в 0 х n-1 + в n х n-2 +…+в n-2 х + в n-1 , где в 0 =а 0 , в n =св n-1 +а n , n=1,2,3,…n-1. Остаток r(х)= св n-1 +а n . Этот метод вычисления и называется схемой Горнера. Слово « схема» в названии алгоритма связана с тем, что обычно его выполнение оформляют следующим образом. Сначала рисуют таблицу 2(n+2). В левой нижней клетке записывают число с, а в верхней строке коэффициенты многочлена Р(х). При этом левую верхнюю клетку оставляют пустой.

в 0 =а 0

в 1 =св 1 +а 1

в 2 =св 1 + а 2

в n-1 =св n-2 +а n-1

r(х)=f(с)=св n-1 +а n

Число, которое после выполнения алгоритма оказывается записанным в правой нижней клетке, и есть остаток от деления многочлена Р(х) на х-с. Другие числа в 0 , в 1 , в 2 ,… нижней строки являются коэффициентами частного.

Например: Разделить многочлен Р(х)= х 3 -2х+3 на х-2.

Получаем, что х 3 -2х+3=(х-2) (х 2 +2х+2) + 7.

4. Закрепление изученного материала

Пример 1: Разложите на множители с целыми коэффициентами многочлен Р(х)=2х4-7х 3 -3х 2 +5х-1.

Ищем целые корни среди делителей свободного члена -1: 1; -1. Составим таблицу:

X = -1 – корень

Р(х)= (х+1) (2х 3 -9х 2 +6х -1)

Проверим 1/2.

Х=1/2 - корень

Следовательно, многочлен Р(х) можно представить в виде

Р(х)= (х+1) (х-1/2) (х 2 -8х +2) = (х+1) (2х -1) (х 2 - 4х +1)

Пример 2: Решить уравнение 2х 4 - 5х 3 + 5х 2 - 2 = 0

Так как сумма коэффициентов многочлена, записанного в левой части уравнения, равна нулю, то один из корней 1. Воспользуемся схемой Горнера:

Х=1 - корень

Получаем Р(х)=(х-1) (2х 3 -3х 2 =2х +2). Будем искать корни среди делителей свободного члена 2.

Выяснили, что целых корней больше нет. Проверим 1/2; -1/2.

Х= -1/2 - корень

Ответ: 1; -1/2.

Пример 3: Решить уравнение 5х 4 – 3х 3 – 4х 2 -3х+ 5 = 0.

Корни данного уравнения будем искать среди делителей свободного члена 5: 1;-1;5;-5. х=1 - корень уравнения, так как сумма коэффициентов равна нулю. Воспользуемся схемой Горнера:

уравнение представим в виде произведения трех множителей: (х-1) (х-1) (5х 2 -7х + 5)=0. Решая квадратное уравнение 5х 2 -7х+5=0, получили Д=49-100=-51, корней нет.

Карточка 1

  1. Разложите на множители многочлен: х 4 +3х 3 -5х 2 -6х-8
  2. Решите уравнение: 27х 3 -15х 2 +5х-1=0

Карточка 2

  1. Разложите на множители многочлен: х 4 -х 3 -7х 2 +13х-6
  2. Решите уравнение: х 4 +2х 3 -13х 2 -38х-24=0

Карточка 3

  1. Разложите на множители: 2х 3 -21х 2 +37х+24
  2. Решите уравнение: х 3 -2х 2 +4х-8=0

Карточка 4

  1. Разложите на множители: 5х 3 -46х 2 +79х-14
  2. Решите уравнение: х 4 +5х 3 +5х 2 -5х-6=0

5. Подведение итогов

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

Домашнее задание:

Решите уравнения:

а) х 4 -3х 3 +4х 2 -3х+1=0

б) 5х 4 -36х 3 +62х 2 -36х+5=0

в) х 4 +х 3 +х+1=4х 2

г) х 4 +2х 3 -х-2=0

Литература

  1. Н.Я. Виленкин и др., Алгебра и начала анализа 10 класс (углубленное изучение математики): Просвещение, 2005.
  2. У.И. Сахарчук, Л.С. Сагателова, Решение уравнений высших степеней: Волгоград, 2007.
  3. С.Б. Гашков, Системы счисления и их применение.


Горнер Уильям Джордж () Английский математик. Основные исследования относятся к теории алгебраических уравнений. Разработал способ приближенного решения уравнений любой степени. В 1819 г. ввёл важный для алгебры способ деления многочлена на двучлен (х – а) (схема Горнера).


Вывод формул для схемы Горнера Разделить с остатком многочлен f(x) на двучлен (x-c) значит найти такой многочлен q(x) и такое число r, что f(x)=(x-c)q(x)+r Запишем это равенство подробно: f 0 x n + f 1 x n-1 + f 2 x n-2 + …+f n-1 x + f n = =(x-c) (q 0 x n-1 + q 1 x n-2 + q 2 x n-3 +…+ q n-2 x + q n-1)+r Приравняем коэффициенты при одинаковых степенях: x n: f 0 = q 0 => q 0 = f 0 x n-1: f 1 = q 1 - c q 0 => q 1 = f 1 + c q 0 x n-2: f 2 = q 2 - c q 1 => q 2 = f 2 + c q 1 … X 0: f n = q n - c q n-1 => q n = f n + c q n-1 q 0 = f 0 x n-1: f 1 = q 1 - c q 0 => q 1 = f 1 + c q 0 x n-2: f 2 = q 2 - c q 1 => q 2 = f 2 + c q 1 … X 0: f n = q n - c q n-1 => q n = f n + c q n-1">


Демонстрация работы схемы Горнера С помощью схемы Горнера разделим с остатком многочлен f(x) = x 3 - 5x на двучлен x-2 Записываем коэффициенты исходного многочлена f 0, f 1, f 2, f 3. f0f0 f1f1 f2f2 f3f c 2 Если делим на (x-c), то во второй строке слева пишем с Готовим пустые клетки для остатка r и коэффициентов неполного частного q 0, q 1,q 2 q0q0 q1q1 q2q2 r g 0:=f 0 =1 1 g 1:= с *g 0 + f 1 * + =2 * 1 + (-5)=-3 g 2:= с *g 1 + f 2 =2 * (-3) + 0=-6 * + r:= с *g 2 + f 3 =2 * (-6) + 8= * + -4 Ответ: g(x)=x 2 -3x-6 ; r= -4. f(x)= (x-2)(x 2 -3x-6)-4


Разложение многочлена по степеням двучлена Используя схему Горнера, разложим многочлен f(x)=x 3 +3x 2 -2x+4 по степеням двучлена (x+2) f(x)=x 3 +3x 2 -2x+4 =(x+2)(x 2 +x-4) f(x)=x 3 +3x 2 -2x+4= (x+2)((x-1)(x+2)-2) f(x)=x 3 +3x 2 -2x+4= (((1*(x+2)-3)(x+2)-2)(x+2)) f(x) = x 3 +3x 2 -2x+4 = (x+2)(x 2 +x-4)+12 = (x+2)((x-1)(x+2)-2)+12 = = (((1*(x+2)-3)(x+2)-2)(x+2))+12 = (x+2) 3 -3(x+2) 2 -2(x+2)+12


Домашняя работ а 1. Разделить f(x)=2x 5 -x 4 -3x 3 +x-3 на x-3; 2. Используя схему Горнера, найдите целые корни многочлена f(x)=x 4 -2x 3 +2x 2 -x-6 (*Замечание: целые корни многочлена с целыми коэффициентами нужно искать среди делителей свободного члена ±1;±2;±3;±6)


Многочлен вида
a n x n + a n-1 x n-1 + a n-2 x n-2 + ... + a 1 x + a 0
можно разложить на множители по схеме Горнера, если известен хотя бы 1 его корень.

Разберем деление по схеме Горнера на примере:

2x 4 + 9x 3 - 10x 2 - 27x - 10

Для начала нужно методом подбора найти один корень. Обычно он является делителем свободного члена. В данном случае делителями числа -10 являются ±1, ±2, ±5, ±10. Начнем их подставлять по-очереди:

1: 2 + 9 - 10 - 27 - 10 = -36 ⇒ число 1

-1: 2 - 9 - 10 + 27 - 10 = 0 ⇒ число -1 является корнем многочлена

Мы нашли 1 из корней многочлена. Корнем многочлена является -1, а значит исходный многочлен должен делиться на x + 1 . Для того, чтобы выполнить деление многочленов, воспользуемся схемой Горнера:

2 9 -10 -27 -10
-1

В верхней строке выставляются коэффициенты исходного многочлена. В первой ячейке второй строки ставится найденный нами корень -1. Во второй строке пишутся коэффициенты многочлена, который получится в результате деления. Они считаются так:

2 9 -10 -27 -10
-1 2
Во вторую ячейку второй строки запишем число 2, просто перенеся его из соответствующей ячейки первой строки.
2 9 -10 -27 -10
-1 2 7
-1 ∙ 2 + 9 = 7
2 9 -10 -27 -10
-1 2 7 -17
-1 ∙ 7 - 10 = -17
2 9 -10 -27 -10
-1 2 7 -17 -10
-1 ∙ (-17) - 27 = -10
2 9 -10 -27 -10
-1 2 7 -17 -10 0
-1 ∙ (-10) - 10 = 0

Последнее число - это остаток от деления. Если он равен 0, значит мы все верно посчитали.

2x 4 + 9x 3 - 10x 2 - 27x - 10 = (x + 1)(2x 3 + 7x 2 - 17x - 10)

Но это еще не конец. Можно попробовать разложить таким же способом многочлен 2x 3 + 7x 2 - 17x - 10.

Опять ищем корень среди делителей свободного члена. Как мы уже выяснили, делителями числа -10 являются ±1, ±2, ±5, ±10.

1: 2 + 7 - 17 - 10 = -18 ⇒ число 1 не является корнем многочлена

-1: -2 + 7 + 17 - 10 = 12 ⇒ число -1 не является корнем многочлена

2: 2 ∙ 8 + 7 ∙ 4 - 17 ∙ 2 - 10 = 0 ⇒ число 2 является корнем многочлена

Напишем найденный корень в нашу схему Горнера и начнем заполнять пустые ячейки:

2 9 -10 -27 -10
-1 2 7 -17 -10 0
2 2
Во вторую ячейку третьей строки запишем число 2, просто перенеся его из соответствующей ячейки второй строки.
2 9 -10 -27 -10
-1 2 7 -17 -10 0
2 2 11
2 ∙ 2 + 7 = 11
2 9 -10 -27 -10
-1 2 7 -17 -10 0
2 2 11 5
2 ∙ 11 - 17 = 5
2 9 -10 -27 -10
-1 2 7 -17 -10 0
2 2 11 5 0
2 ∙ 5 - 10 = 0

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

2x 4 + 9x 3 - 10x 2 - 27x - 10 = (x + 1)(x - 2)(2x 2 + 11x + 5)

Многочлен 2x 2 + 11x + 5 тоже можно разложить на множители. Для этого можно решить квадратное уравнение через дискриминант , а можно поискать корень среди делителей числа 5. Так или иначе, мы придем к выводу, что корнем этого многочлена является число -5

2 9 -10 -27 -10
-1 2 7 -17 -10 0
2 2 11 5 0
-5 2
Во вторую ячейку четвертой строки запишем число 2, просто перенеся его из соответствующей ячейки третьей строки.
2 9 -10 -27 -10
-1 2 7 -17 -10 0
2 2 11 5 0
-5 2 1
-5 ∙ 2 + 11 = 1
2 9 -10 -27 -10
-1 2 7 -17 -10 0
2 2 11 5 0
-5 2 1 0
-5 ∙ 1 + 5 = 0

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

2x 4 + 9x 3 - 10x 2 - 27x - 10 = (x + 1)(x - 2)(x + 5)(2x - 1)

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

Задан многочлен :

.

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

.

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

… …

Искомое значение . Покажем, что это так.

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

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

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

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

, .

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

Примечания

См. также

Литература

  • Ананий В. Левитин Глава 6. Метод преобразования: Схема Горнера и возведение в степень // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. - М .: «Вильямс», 2006. - С. 284-291. - ISBN 0-201-74395-7
  • Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера // Численные методы. - Учеб. пособие для вузов. - 2-е изд., испр. - М .: Наука, 1987. - 248 с.
  • С. Б. Гашков §14. Схема Горнера и перевод из одной позиционной системы в другую // Системы счисления и их применение . - М .: МЦНМО , 2004. - С. 37-39. - (Библиотека «Математическое просвещение»). - ISBN 5-94057-146-8

Ссылки

  • Вычисление многомерных полиномов - обобщение схемы Горнера на случай полинома от нескольких переменных.

Wikimedia Foundation . 2010 .

  • Хлорхинальдол
  • Штильмарк, Александр Робертович

Смотреть что такое "Схема Горнера" в других словарях

    ГОРНЕРА СХЕМА - прием для нахождения неполного частного и остатка при делении многочлена на двучлен, где все коэффициенты лежат в нек ром поле, напр., в поле комплексных чисел. Всякий многочлен единственным способом представим в виде где есть неполное частное,… … Математическая энциклопедия

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

    Корень многочлена - У этого термина существуют и другие значения, см. Корень (значения). Корень многочлена (не равного тождественно нулю) над полем k элемент, такой что выполняются два следующих равносильных условия: данный многочлен делится на многочлен;… … Википедия

    Деление многочленов столбиком - В алгебре деление многочленов столбиком алгоритм деления многочлена на многочлен, степень которого меньше или равна степени многочлена. Алгоритм представляет собой обобщенную форму деления чисел столбиком, легко реализуемую вручную. Для… … Википедия

    Хорнер, Уильям Джордж - Уильям Джордж Хорнер (1786 год, Бристоль 22 сентября 1837 года) британский математик. Родился в 1786 году в городе Бристоль в Англии. Получил образование в Кингствудской школе Бристоля. В возрасте 14 лет он стал помощником директора в… … Википедия

    Плечевое сплетение - I Плечевое сплетение (plexus brachialis) сплетение нервных волокон передних ветвей 4 8 шейных и 1 2 грудных спинномозговых нервов в несколько стволов и пучков, в результате последующего разделения которых формируются короткие и длинные нервы… … Медицинская энциклопедия

    РАДИКУЛИТЫ - (от лат. radix корень), заболевания корешков спинномозговых нервов, термин, утвердившийся в начале 20 в. благодаря работам Дежерина и его школы. В основе Р. лежит воспалительно дегенеративный процесс в корешках [см. отдельную таблицу (ст. 255… …

    ЩИТОВИДНАЯ ЖЕЛЕЗА - (gl. thyreoidea, син. corpus thyreoideum), одна из важнейших желез внутренней секреции позвоночных животных. В эмбриональном развитии Щ. ж. возникает из эпителия нижней стенки жаберной части кишечника; у личинок круглоротых рыб она имеет еще вид… … Большая медицинская энциклопедия

    Радикулит - I Радикулит (radiculitis; лат. radicula корешок + itis) воспалительное и компрессионное поражение корешков спинномозговых нервов. Сочетанное поражение переднего и заднего корешков на уровне их соединения в общий канатик (рис.) ранее обозначали… … Медицинская энциклопедия

    Спина́льное кровообраще́ние - (синоним спинномозговое кровообращение) Установлено, что несколько верхних шейных сегментов спинного мозга снабжают кровью передняя и задняя спинальные артерии, отходящие от позвоночных артерий. Сегменты, расположенные ниже сегментов CIII CIV,… … Медицинская энциклопедия