Вычисление значения многочлена. Все ли тривиально в этом вопросе? Уравнения в высшей математике.Рациональные корни многочленов

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


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

Схема Горнера

Исключения

А есть что-то еще, ведь схема Горнера самая экономичная?

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

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

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

Схема Дж.Тодта для многочленов 6 степени

Коэффициенты определяются методом неопределенных коэффициентов исходя из условия . Из последнего условия составляем систему уравнений, приравнивая коэффициенты при равных степенях многочленов.

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

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

Схема Ю.Л. Кеткова

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

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

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

Схемы В.Я. Пана

В.Я. Пан занимался вопросами оптимального вычисления многочленов. В частности, им предложено несколько схем для вычисления действительных многочленов, которые весьма близко подобрались к оценкам Э. Белаги. Приведу некоторые схемы Пана для действительных многочленов.
1. Схема для вычисления многочленов четвертой степени.
Рассматривается многочлен .

Представим в виде:

Для вычисления значения многочлена используем выражения:

Эта схема на втором этапе требует умножения и сложения.

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

У В.Я. Пана существуют и другие схемы для вычисления многочленов, в том числе и для комплексных.

Заключение

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

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

Литература

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.

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. На рисунках показана эффективность реализации алгоритма встречной прогонки.

Горнер Уильям Джордж () Английский математик. Основные исследования относятся к теории алгебраических уравнений. Разработал способ приближенного решения уравнений любой степени. В 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)

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

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

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

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

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

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

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

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

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

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

Примечания

См. также

Литература

• Ананий В. Левитин Глава 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,… … Медицинская энциклопедия

Слайд 3

Горнер Вильямc Джордж (1786-22.9.1837)-английский математик. Родился в Бристоле. Учился и работал там же, затем в школах Бата. Основные труды по алгебре. В 1819г. опубликовал способ приближенного вычисления вещественных корней многочлена, который называется теперь способом Руффини-Горнера (этот способ был известен китайцам еще в XIII в.) Именем Горнера названа схема деления многочлена на двучлен х-а.

Слайд 4

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

Способ деления многочлена n-й степени на линейный двучленх - а, основанный на том, что коэффициенты неполного частного и остатокr связаны с коэффициентами делимого многочлена и с а формулами:

Слайд 5

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

Пример 1. Разделить Неполное частное равно х3-х2+3х - 13 и остаток равен 42=f(-3).

Слайд 6

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

Слайд 7

Пример2.

Докажем, что многочлен Р(х)=х4-6х3+7х-392 делится на х-7,и найдем частное от деления. Решение. Используя схему Горнера, найдем Р(7): Отсюда получаем Р(7)=0, т.е. остаток при делении многочлена на х-7 равен нулю и, значит, многочлен Р(х) кратен (х-7).При этом числа во второй строке таблицы являются коэффициентами частного от деления Р(х) на (х-7), поэтому Р(х)=(х-7)(х3+х2+7х+56).

Слайд 8

Разложить на множители многочлен x3 – 5x2 – 2x + 16.

Данный многочлен имеет целые коэффициенты. Если целое число является корнем этого многочлена, то оно является делителем числа 16. Таким образом, если у данного многочлена есть целые корни, то это могут быть только числа ±1; ±2; ±4; ±8; ±16. Непосредственной проверкой убеждаемся, что число 2 является корнем этого многочлена, то есть x3 – 5x2 – 2x + 16 = (x – 2)Q(x), где Q(x) − многочлен второй степени

Слайд 9

Полученные числа 1, −3, −8 являются коэффициентами многочлена, который получается при делении исходного многочлена на x – 2. Значит, результат деления: 1 · x2 + (–3)x + (–8) = x2 – 3x – 8. Степень многочлена, полученного в результате деления, всегда на 1 меньше, чем степень исходного. Итак: x3 – 5x2 – 2x + 16 = (x – 2)(x2 – 3x – 8).