Для чего нужны полиномы

Что такое полином и чем он полезен

Определение

Определение термину полином можно дать через понятие монома, или одночлена.

Вам будет интересно: Образование в Ирландии: структура, система, особенности

Чтобы понять, что такое полином, можно посмотреть на конкретные примеры.

Многочлен с двумя переменными может выглядеть так: х2-ху+у2. Такой полином называют еще неполным квадратом разности х и у.

Классификации полиномов

По степени полинома

Кстати, любую константу можно считать многочленом степени ноль.

Приведенные и неприведенные полиномы

Однородные и неоднородные полиномы

Если степени всех членов полинома равны, то говорят, что такой полином однороден. Все остальные полиномы считаются неоднородными.

Однородные многочлены: х2-ху+у2, xyz+х3+у3. Неоднородные: х+1, х2+у.

Существуют специальные названия для полинома из двух и трех членов: бином и трехчлен соответственно.

В отдельную категорию выделяют многочлены одной переменной.

Применение полинома одной переменной

Многочлены одной переменной хорошо приближают непрерывные функции различной сложности от одного аргумента.

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

Легко искать производные многочленов. Для нахождения корней у полиномов 4-й степени и ниже существуют готовые формулы, а для работы с более высокими степенями используются приближенные алгоритмы высокой точности.

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

Бином Ньютона

Знаменитыми полиномами являются полиномы Ньютона, выведенные ученым для нахождения коэффициентов выражения (х+у)n.

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

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

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

При взгляде на иллюстрацию все становится понятно.

Разумеется, приведенными примерами, наиболее широко известными, применение многочленов в математике не ограничивается.

Источник

Полином

где c_i фиксированные коэффициенты, а x — переменная. Многочлены составляют один из важнейших классов элементарных функций.

Изучение полиномиальных уравнений и их решений составляло едва ли не главный объект «классической алгебры». С изучением многочленов связан целый ряд преобразований в математике: введение в рассмотрение нуля, отрицательных, а затем и комплексных чисел, а также появление теории групп как раздела математики и выделение классов специальных функций в анализе.

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

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

Содержание

Определение

Многочлен (или полином) от n переменных — есть конечная формальная сумма вида

,

где I = (i₁,i₂. i_n) есть набор из целых неотрицательных чисел (называется мультииндекс), c_I — число (называемое «коэффициент многочлена»), зависящее только от мультииндекса I.

В частности, многочлен от одной переменной есть конечная формальная сумма вида

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

Связанные определения

Делимость

Например, многочлен x 4 + 2, неприводимый в поле рациональных чисел, разлагается на два множителя в поле вещественных чисел и на четыре множителя в поле комплексных чисел.

Вообще, каждый многочлен от одного переменного x разлагается в поле вещественных чисел на множители первой и второй степени, в поле комплексных чисел — на множители первой степени (основная теорема алгебры).

Для двух и большего числа переменных этого уже нельзя утверждать. Над любым полем для любого n > 2 существуют многочлен от n переменных, неприводимые в любом расширении этого поля. Такие многочлены называются абсолютно неприводимыми.

Полиномиальные функции

.

В случае если R есть поле вещественных или комплексных чисел (а также любое другое поле с бесконечным числом элементов) то функция полностью определяет многочлен p. Однако в общем случае это неверно, например: многочлены и из определяют тождественно равные функции .

Источник

Что нам стоит полином Жегалкина построить…

Думаю, каждый, кто изучал или изучает в университете дискретную математику, знаком с понятием многочлена Жегалкина.

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

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

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

Под катом приведен один удобный алгоритм, для построения полиномов Жегалкина, который студенты воспринимают «на ура», т.к. требует только выполнение «механических действий» без применения каких-либо умственных усилий. Краткое описание метода можно найти в Википедии, но на мой взгляд по нему не совсем понятно, как быстро проводить вычисления. Мне метод известен под названием «метод треугольника Паскаля».

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

Метод треугольника Паскаля

Требуется построить полином Жегалкина для функции f. Для примера, в качестве функции f возьмем функцию голосования .

Шаг 1. Строим таблицу значений функции (строки в таблице идут в порядке возрастания двоичных кодов). Таблицу лучше разместить в левой части листа.

Шаг 2. Построение треугольника.

Для этого берем вектор значения функции и выписываем его напротив первой строки таблицы:

Далее заполняем треугольник, складывая попарно соседние значения по модулю 2, результат сложения выписываем ниже.

Продолжаем вычисления, пока в строке не останется лишь одна цифра.

Шаг 3. Построение полинома Жегалкина.

Нас интересует левая сторона треугольника (значения выделены жирным):

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

Теперь выпишем для наглядности эти конъюнкции. Конъюнкции выписываем по двоичным наборам в левой части таблицы по следующему принципу: если напротив переменной xi стоит 1, то переменная входит в конъюнкцию; в противном случае переменная отсутствует в конъюнкции. Набору (0,0,0) соответствует константа 1.

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

Для построения полинома нужны только конъюнкции из строк с единицами на левой стороне треугольника.

Это и есть конъюнкции, входящие в состав полинома Жегалкина. Осталось лишь выписать сам полином:

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

Источник

Полиномы

где c_i фиксированные коэффициенты, а x — переменная. Многочлены составляют один из важнейших классов элементарных функций.

Изучение полиномиальных уравнений и их решений составляло едва ли не главный объект «классической алгебры». С изучением многочленов связан целый ряд преобразований в математике: введение в рассмотрение нуля, отрицательных, а затем и комплексных чисел, а также появление теории групп как раздела математики и выделение классов специальных функций в анализе.

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

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

Содержание

Определение

Многочлен (или полином) от n переменных — есть конечная формальная сумма вида

,

где I = (i₁,i₂. i_n) есть набор из целых неотрицательных чисел (называется мультииндекс), c_I — число (называемое «коэффициент многочлена»), зависящее только от мультииндекса I.

В частности, многочлен от одной переменной есть конечная формальная сумма вида

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

Связанные определения

Делимость

Например, многочлен x 4 + 2, неприводимый в поле рациональных чисел, разлагается на два множителя в поле вещественных чисел и на четыре множителя в поле комплексных чисел.

Вообще, каждый многочлен от одного переменного x разлагается в поле вещественных чисел на множители первой и второй степени, в поле комплексных чисел — на множители первой степени (основная теорема алгебры).

Для двух и большего числа переменных этого уже нельзя утверждать. Над любым полем для любого n > 2 существуют многочлен от n переменных, неприводимые в любом расширении этого поля. Такие многочлены называются абсолютно неприводимыми.

Полиномиальные функции

.

В случае если R есть поле вещественных или комплексных чисел (а также любое другое поле с бесконечным числом элементов) то функция полностью определяет многочлен p. Однако в общем случае это неверно, например: многочлены и из определяют тождественно равные функции .

Источник

Путеводитель по полиномам и сплайнам для программиста

Итак, вы программист. Зачем вам вообще могут понадобится полиномы? Например затем, что это хорошая геометрическая глина, из которой можно слепить разные вещи.

Из нашей статьи, объясняющей сущность математического анализа на примере python’а, крови и динамита, видно, что вы можете анализировать и синтезировать произвольные функции в качестве многочленов. Однако вовсе не обязательно работать именно с функциями. Иногда вам может понадобиться смоделировать сплайн из нескольких точек или свойств, вроде тангенсов кривых. Например, вам надо слепить какую-нибудь анимацию, или приятный видео эффект, или провести кривую, проходящую через определенные точки, или создать поверхность плоскую в одном месте и изогнутую в другом.

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

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

А это уже всего 3 умножения и 3 сложения. Вот видите, мы только начали, а вы уже научились избавляться от одной трети вычислений.

Полиномиальная интерполяция

Задача адаптации многолчена n-ной степени под n+1 точку пространства называется полиномиальной интерполяцией. Существует несколько способов ее реализации. Вы можете воспользоваться интерполяционными формулами Ньютона или Лагранжа, однако самый простой способ получения интерполяционного многочлена — решение системы линейных уравнений.

Если многочлен проходит через точку, значит, мы, очевидно, можем утверждать, что P(xi) = yi. Допустим, мы хотим адаптировать полином под набор из трех точек. Это означает, что:

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

Поскольку xs и ys известны, нам остается только решить систему и узнать коэффициенты a, b, c, и поскольку эта система из трех уравнений и трех переменных, мы как правило можем получить одно единственное решение.

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

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

Обратная ситуация еще интереснее. Мы можем провести бесконечное количество парабол через две заданные точки. Все они одинаково подходят в качестве решения задачи. И в то же время мы не можем получить некое однозначно лучшее решение для систем из n уравнений и n+1 переменных.

Но что если это все-таки возможно? Что если мы можем ввести некоторый дополнительный критерий для выбора наиболее подходящего варианта?

Синтез

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

Производная функции тесно связана с геометрическими свойствами ее графика. Первая производная определяет тангенс угла наклона касательной, а вторая — кривизну.

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

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

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

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

Феномен Рунге

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

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

Узлы Чебышева

Один из способов борьбы с хаосом заключается в выборе специальной сетки для интерполяции — узлов Чебышева. Это специальные значения x, которые получаются путем деления полукруга с радиусом 1 на равные фрагменты и их проецирования на ось x.

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

Конечно, вы можете расширить интервал по оси X настолько, насколько нужно с помощью одномерного аффинного преобразования. Не обязательно придерживаться отрезка (-1; 1).

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

Сплайны

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

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

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

Заключение

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

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

Источник