Что такое полиномиальная функция
Полиномиальные функции
Напомним, что полиномиальной называется функция, которая может быть записана в форме f (n) = a0 + a1n + a2n2 + …+ ad nd для некоторой целочисленной константы d > 0, где последний коэффициент ad отличен от нуля. Значение d называется степенью (или порядком) полинома. Например, упоминавшиеся ранее функции вида pn2 + qn + r (где p ≠ 0) представляют собой полиномиальные функции со степенью 2.
Так как нас интересуют только функции, получающие неотрицательные значения, наше внимание будет ограничено полиномиальными функциями, у которых член высшего порядка имеет положительный коэффициент ad > 0.
(2.7) Предположим, f является полиномиальной функцией степени d с положительным коэффициентом ad. В этом случае f = O(nd).
Доказательство. Условие записывается в виде f = a0 + a1n + a2n2 + …+ ad nd, где ad > 0. Верхняя граница напрямую следует из (2.5). Во-первых, следует заметить, что коэффициенты aj для j Прежде всего, многие алгоритмы имеют время выполнения в форме O(nx) для некоторого числа x, которое не является целым. Например, в главе 5 представлен алгоритм с временем выполнения O(n1,59); также встречаются экспоненты меньшие 1, как в границах типа O() = O(n1/2).
Другой распространенный пример: часто встречаются алгоритмы, время выполнения которых записывается в форме O(n log n). Такие алгоритмы также имеют полиномиальное время выполнения: как будет показано далее, log n ≤ n для всех n ≥ 1, а следовательно, n log n ≤ n2 для всех n ≥ 1.
Другими словами, если алгоритм имеет время выполнения O(n log n), он также имеет время выполнения O(n2), а следовательно, является алгоритмом с полиномиальным временем.
Полиномиальные функции определяются полиномиальными выражениями. Они представлены выражением:
Каждая полиномиальная функция связана с одним полиномом, поэтому мы называем полиномиальные функции также полиномами.
Числовое значение полинома
Чтобы найти числовое значение полинома, подставляем числовое значение в переменную x.
пример
Подставляя значение в переменную x, получаем:
Степень полиномов
В зависимости от наивысшего показателя степени, который они имеют по отношению к переменной, многочлены классифицируются на:
Графики полиномиальных функций
Мы можем связать график с полиномиальной функцией, присвоив значения ax в выражении p (x).
Таким образом, мы найдем упорядоченные пары (x, y), которые будут точками, принадлежащими графу.
Соединив эти точки, мы получим контур графика полиномиальной функции.
Вот несколько примеров графиков:
Полиномиальная функция степени 1
Полиномиальная функция степени 2
Полиномиальная функция степени 3
Полиномиальное равенство
Два полинома равны, если все коэффициенты членов одной степени равны.
пример
Чтобы полиномы были равны, соответствующие коэффициенты должны быть равны.
Полиномиальные операции
Ниже приведены примеры операций между многочленами:
Дополнение
Вычитание
Умножение
Деление
Разделение состоит из дивидендов, делителей, частных и остатков.
разделитель. частное + остаток = дивиденд
Теорема покоя
Теорема об остатке представляет собой остаток от деления многочленов и имеет следующее утверждение:
Вестибулярные упражнения с обратной связью
а) 6
б) 21
в) 36
г) 720
д) 1080
СОДЕРЖАНИЕ
Этимология
Обозначения и терминология
что формально оправдывает существование двух обозначений для одного и того же многочлена.
Определение
Многочлен от одного неопределенного x всегда можно записать (или переписать) в виде
Это можно выразить более кратко, используя обозначение суммирования :
Классификация
Сумма нескольких членов дает многочлен. Например, это многочлен:
Оценка полинома состоит из подставляя численное значение каждого неопределенный и проведения указанных умножений и дополнений. Для многочленов от одной неопределенности оценка обычно более эффективна (меньшее количество арифметических операций для выполнения) с использованием метода Хорнера :
Арифметика
Сложение и вычитание
Многочлены могут быть добавлены с использованием ассоциативного закона сложения (группировка всех их членов в единую сумму), возможно, с последующим переупорядочиванием (с использованием закона коммутативности ) и объединением подобных членов. Например, если
можно переупорядочить и перегруппировать как
а затем упрощен до
Когда полиномы складываются вместе, получается еще один многочлен.
Вычитание многочленов аналогично.
Умножение
Многочлены также можно умножать. Чтобы разложить произведение двух полиномов на сумму членов, многократно применяется закон распределения, в результате чего каждый член одного полинома умножается на каждый член другого. Например, если
Проведение умножения в каждом члене дает
Объединение похожих условий дает
который можно упростить до
Как и в примере, произведение многочленов всегда является многочленом.
Состав
Разделение
Факторинг
Все многочлены с коэффициентами в уникальной области факторизации (например, целые числа или поле ) также имеют факторизованную форму, в которой многочлен записывается как произведение неприводимых многочленов и константы. Эта факторизованная форма уникальна до порядка множителей и их умножения на обратимую константу. В случае поля комплексных чисел неприводимые множители линейны. Над действительными числами они имеют степень один или два. Над целыми и рациональными числами неприводимые множители могут иметь любую степень. Например, факторизованная форма
над целыми и действительными числами, и
над комплексными числами.
Исчисление
Вычисление производных и интегралов от многочленов особенно просто по сравнению с другими видами функций. Производная многочлена
Полиномиальные функции
является полиномиальной функцией одной переменной. Полиномиальные функции нескольких переменных определяются аналогично, используя многочлены от более чем одной неопределенной переменной, как в
Графики
Полиномиальные графы анализируются в исчислении с использованием пересечений, наклонов, вогнутости и поведения концов.
Уравнения
является полиномиальным уравнением.
Решение уравнений
Обобщения
Есть несколько обобщений понятия многочленов.
Тригонометрические полиномы
Если sin ( nx ) и cos ( nx ) раскрываются в терминах sin ( x ) и cos ( x ), тригонометрический полином становится полиномом от двух переменных sin ( x ) и cos ( x ) (с использованием списка тригонометрических тождеств. # Формулы для нескольких углов ). И наоборот, каждый многочлен от sin ( x ) и cos ( x ) может быть преобразован с помощью тождеств «произведение к сумме» в линейную комбинацию функций sin ( nx ) и cos ( nx ). Эта эквивалентность объясняет, почему линейные комбинации называются полиномами.
Матричные полиномы
Матричный многочлен является многочленом с квадратными матрицами в качестве переменных. Для обычного скалярного многочлена
этот многочлен, вычисленный в матрице A, равен
Полиномы Лорана
Многочлены Лорана похожи на многочлены, но допускают появление отрицательных степеней переменной (переменных).
Рациональные функции
Хотя полиномиальные функции определены для всех значений переменных, рациональная функция определяется только для значений переменных, знаменатель которых не равен нулю.
Рациональные дроби включают многочлены Лорана, но не ограничивают знаменатели степенями неопределенного.
Силовая серия
Формальные степенные ряды похожи на многочлены, но допускают появление бесконечного числа ненулевых членов, так что они не имеют конечной степени. В отличие от многочленов, они, как правило, не могут быть явно и полностью записаны (как и иррациональные числа ), но правила манипулирования их членами такие же, как и для многочленов. Неформальные степенные ряды также обобщают многочлены, но умножение двух степенных рядов может не сходиться.
Другие примеры
Приложения
Абстрактная алгебра
Можно думать о кольце R [ x ] как о возникающем из R путем добавления одного нового элемента x к R и минимальном расширении до кольца, в котором x не удовлетворяет никаким другим соотношениям, кроме обязательных, плюс коммутация со всеми элементами из R (то есть xr = rx ). Для этого нужно также сложить все степени x и их линейные комбинации.
Делимость
Позиционное обозначение
Интерполяция и приближение
Другие приложения
История
История обозначения
Что такое полиномиальная функция
В качестве моделей трендов используют различные элементарные функции и их сочетания, а также степенные ряды, иногда называемые полиномиальными моделями. Наибольшую точность обеспечивают модели в виде рядов Фурье, однако не многие статистические пакеты позволяют их использовать. [c.102]
Данная глава посвящена моделированию фактического распределения сделок с помощью регулируемого распределения, то есть поиску функции и ее подходящих параметров, которые моделируют фактическую функцию плотности вероятности торговых P L с двумя точками перегиба. Вы можете использовать уже известные функции и методы, например, полиномиальную интерполяцию или экстраполяцию, интерполяцию и экстраполяцию рациональной функции (частные многочленов), или использовать сплайн-интерполяцию. После того как теоретическая функция найдена, можно определить ассоциированные вероятности тем же методом расчета интеграла, который использовался при поиске ассоциированных вероятностей регулируемого распределения, или рассчитать интеграл с помощью методов математического анализа. Одна из целей этой книги — позволить трейдерам, использующим немеханические системы, применять те же методы управления счетом, что и трейдерам, использующим механические системы. Регулируемое распределение требует расчета параметров, они относятся к первым четырем моментам распределения. Именно эти моменты — расположение, масштаб, асимметрия и эксцесс — описывают распределение. Таким образом, кто-либо, торгующий по немеханическому методу, например по волнам Эллиотта, [c.141]
Априорную плотность вероятности можно оценить различными способами. В параметрических методах предполагается, что плотность вероятности (PDF) является функцией определенного вида с неизвестными параметрами. Например, можно попробовать приблизить PDF при помощи гауссовой функции. Для того чтобы произвести классификацию, нужно предварительно получить оценочные значения для вектора среднего и матрицы ковариаций по каждому из классов данных и затем использовать их в решающем правиле. В результате получится полиномиальное решающее правило, содержащее только квадраты и попарные произведения переменных. Вся описанная процедура называется квадратичным дискриминантным анализом (QDA). В предположении, что матрицы ковариаций у всех классов одинаковы, QDA сводится к линейному дискриминантному анализу (LDA). [c.47]
Оцените параметры этой же модели при величине лага 3 и 4 в предположении полиномиальной структуры лага (в качестве функции, описывающей структуру лага, выберите полином второй степени). Проанализируйте полученные результаты. Сравните их с результатами, полученными вами в п.1. Сделайте выводы. [c.180]
Кусочно-полиномиальной С.-ф. называется потому, что состоит из отдельных кусков, представляющих собой графики многочленов (ср. рис. К.8 к ст. Кусочно-линейная функция»), которые «склеены» гладким образом (если отказаться от математической терминологии — они плавно переходят друг в друга). С помощью С.-ф. удобно проводить интерполирование, т.е. восстановление недостающих элементов временного ряда. Они применяются также для построения приближенных решений обыкновенных дифференциальных уравнений. [c.339]
При всех отмеченных выше недостатках проводимого анализа, учитывающего только основные выделенные блоки и связи экономической системы, представляется, что именно абстрагирование от частностей может позволить выявить основные механизмы реальной экономики, представляя их в обобщенном виде, очищенном от наслоений повседневной турбулентности реальной экономической конкретики. При этом полиномиальный характер зависимости от времени в формуле (4.5.9) представляет собой наиболее естественную форму общих моделей развития, широко используемую, в том числе, в экономических исследованиях. Новым фактом является, следовательно, только конкретизация конструкции коэффициентов разложения, как мультипликативных функций от инвестиций, позволяющая выявить принципы их согласованной работы в блоках экономики в рассматриваемой здесь общей задаче развития Производства. [c.371]
Полиномиальный характер роста реальных экономических процессов впервые был выделен и изучен Н. Д. Кондратьевым в знаменитой работе Большие циклы конъюнктуры 1925 г. [Кондратьев, 1993]. Там было показано, что систематический рост изученных им экономических показателей капиталистических стран может быть описан полиномами разных степеней по времени. Сопоставляя закон роста (4.5.9) с данными Н. Д. Кондратьева, можно предположить, что этот закон конкретизирует конструкции коэффициентов общей теоретической формы полиномиальных рядов экономического роста. Структура коэффициентов как мультипликативных функций [c.371]
Метод структурной минимизации риска может быть использован для восстановления регрессии в различных классах функций. Применим его для построения полиномиальной регрессии. [c.196]
При проверке линейности регрессии (так Же, впрочем, как и при проверке гипотезы о полиномиальном характере регрессии заданного порядка т) в нормальных схемах зависимостей типа В и Сх описанный общий критерий является точным. При этом в линейном случае статистика у2, определенная соотношением (6.16), может быть выражена в более удобной форме, не требующей предварительного вычисления выборочной аппроксимирующей функции регрессии, а именно [c.203]
Полиномиальная регрессия. Рассмотрим случай скалярного (т. е. одномерного, р = 1) предиктора к, и пусть искомая функция регрессии / (х) принадлежит классу алгебраических полиномов степени т, т. е. [c.349]
Многообразие и сложность экономических процессов предопределяет многообразие моделей, используемых для эконометрического анализа. С другой стороны, это существенно усложняет процесс нахождения максимально адекватной формулы зависимости. Для случая парной регрессии подбор модели обычно осуществляется по виду расположения наблюдаемых точек на корреляционном поле. Однако нередки ситуации, когда расположение точек приблизительно соответствует нескольким функциям и необходимо из них выявить наилучшую. Например, криволинейные зависимости могут аппроксимироваться полиномиальной, показательной, степенной, логарифмической функциями. Еще более неоднозначна ситуация для множествен- [c.189]
Разложение временного ряда на компоненты. Стационарные и нестационарные ряды. Автокорреляционная функция. Типы и виды трендов. Полиномиальный тренд. Экспоненциальный и гармонический тренды. Логистическая кривая. Фильтрация тренда. Скользящие средние. Экспоненциальное сглаживание. Метод последовательных разностей. Сплайны. [c.85]
Один из распространенных подходов к прогнозированию состоит в следующем ряд раскладывается на долговременную, сезонную (в том числе, циклическую) и случайную составляющие затем долговременную составляющую подгоняют полиномом, сезонную — рядом Фурье, после чего прогноз осуществляется экстраполяцией этих подогнанных значений в будущее. Однако этот подход может приводить к серьезным ошибкам. Во-первых, короткие участки стационарного ряда (а в экономических приложениях редко бывают достаточно длинные временные ряды) могут выглядеть похожими на фрагменты полиномиальных или гармонических функций, что приведет к их неправомерной аппроксимации и представлению в качестве неслучайной составляющей. Во-вторых, даже если ряд действительно включает неслучайные полиномиальные и гармонические компоненты, их формальная аппроксимация может потребовать слишком большого числа параметров, т.е. получающаяся параметризация модели оказывается неэкономичной. [c.48]
IFPS имеет встроенный набор математических и статистических функций, в частности, функции линейной регрессии, линейной интерполяции, полиномиальной автокорреляции и скользящего среднего [c.314]
Задачи, допускающие гарантированное нахождение оптимума целевой функции за полиномиальное время, образуют класс Р. Этот класс являюется подклассом более обширного класса NP задач, в которых за полиномиальное время можно всего лишь оценить значение целевой функции для конкретной конфигурации, что, естественно, гораздо проще, чем выбрать наилучшую из всех конфигураций. До сих пор в точности не известно, совпадают ли эти два класса, или нет. Эта проблема, Р Ф NP, о которую сломано уже немало математических копий. Если бы эти классы совпадали, для любой задачи комбинаторной оптимизации, точное можно было бы гарантированно найти за полиномиальное время. В такой «подарок судьбы» никто не верит, и практически разрешимыми считаются задачи, допускающие полиномиальное решение хотя бы для типичных (а не наихудших) случаев. Такова, например, общая задача линейного п рогра м м и рова н ия. [c.110]
При сложных полиномиальных функциях с большим числом факторов необходимо помнить, что каждый параметр преобразованной функции является средней величиной, которая должна быть подсчитана по достаточному числу наблюдений. Если число наблюдений невелико, что, как правило, имеет место в эконометрике, то увеличение числа параметров функции приведет к их статистической незначимости и соответственно потребует упрощения вида функции. Если один и тот же фактор вводится в регрессию в разных степенях, то каждая степень рассматривается как самостоятельный фактор. Так, если модель имеет вид полинома второго порядка [c.104]
СПЛАЙН-ФУНКЦИЯ [spline-fun tion] — гладкая кусочно-полиномиальная функция, используемая для выравнивания временных рядов. Применение С.-ф. вместо обычных функций тренда эффективно, когда внутри анализируемого периода меняется тенденция, направление ряда. С.-ф. помогает выделить подпериоды, внутри которых динамика показателя не претерпевает существенного изменения. [c.339]
Регрессионный анализ с помощью функции может выполнять простой, полиномиальный и анализ. Результат включает линейное уравнение регрессии, таблицу коэффициентов скорректированный таблицу ANOVA, таблицу соответствий и остатков, которые дали необычные наблюдения. Другие доступные характеристики включают ступенчатую регрессию, наилучшие подмножества, график подогнанной линии регрессии и диаграммы остатков. [c.675]
Путеводитель по полиномам и сплайнам для программиста
Итак, вы программист. Зачем вам вообще могут понадобится полиномы? Например затем, что это хорошая геометрическая глина, из которой можно слепить разные вещи.
Из нашей статьи, объясняющей сущность математического анализа на примере 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).
Но интерполяция при этом сохраняет свою повсеместность. Изменение первой точки по-прежнему влияет на работу функции возле последней, хотя и не настолько существенно.
Сплайны
Существует довольно много разновидностей сплайнов, но всех их объединяет один сценарий применения. Как только глобальная интерполяция по какой-либо причине перестает годиться для наших задач, мы можем разделить наш интервал на более малые фрагменты и определить отдельные функции для интерполяции на каждом из них.
Единственное, что нам нужно учесть, так это необходимость их соединения на концах для сохранения непрерывности. Если мы гарантируем непрерывность не только итоговой, кусочно-заданной функции, но и ее первой производной, то в таком случае тангенсы каждого ее отрезка будут совпадать, а ее график будет выглядеть плавно.
Существует определенная классификация сплайнов. Например, возьмем полиномиальный сплайн, состоящий из двух фрагментов. Если каждый его фрагмент определяется полиномом третьей степени, то он называется кубическим. Он может обладать, например, таким свойством, как непрерывность первой производной, поскольку тангенсы на стыке фрагментов совпадают. Его фрагменты имеют не равную ширину. Он не естественного происхождения, поскольку мы можем управлять производными на его концах. И конечно же это интерполяционный сплайн, поскольку он проходит точно через указанные нами точки сетки.
Заключение
Вероятность того, что вам когда-либо придется реализовывать на практике собственную интерполяцию крайне мала. Существует много готовых решений и в большинстве случаев вам надо будет просто выбрать правильный инструмент для работы. Эта область знаний не так сложна, но количество неизвестных слов и названий может оттолкнуть.
Целью этого путеводителя было предоставить вам базовое понимание идей, используемых для работы с полиномами и сплайнами. Он ни в коем случае не претендует на полноту изложения, ведь на самом деле, по каждой из небольших глав этого материала написаны целые книги. Но мы надеемся, по крайней мере, что интерактивный подход к изложению в этом материале будет полезен не только для краткого ознакомления, но, если такая потребность возникнет, поможет вам освоить и более продвинутые темы.