Математическое описания полиномов

Математическое описания полиномов

     В математике, многочлены или полиномы от одной переменной — функции  вида

     

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

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

     Весьма  удобным является представление  двоичных чисел в виде полиномов  степени n -1, где n – количество разрядов числа.

     Идея  представления числа в виде полинома состоит в следующем – основание  системы счисления заменяется некоторой  фиктивной переменной, например x. Степень этой переменной будет соответствовать номеру разряда числа, а коэффициент значению самого разряда. Рассмотрим пример: Запишем двоичное число и его разложение в виде степеней двойки (аналогично переводу в десятичную систему счисления): . Теперь, заменим двойку на фиктивную переменную x, при этом получим выражение: .

     Исключив  элементы с нулевым коэффициентом, получим полиномиальное представление  числа: . 

ПОЛИНОМЫ  ЧЕБЫШЕВА

Введение 

Допустим, задана функция y ( x ), это означает, что любому допустимому значению х сопоставлено значение у. Но иногда оказывается, что найти это значение очень трудно. Например, у( х ) может быть определено как решение сложной задачи, в которой х играет роль параметра или у( х ) измеряется в дорогостоящем эксперименте. В этом случае можно вычислить небольшую таблицу значений функции, но прямое нахождение этой функции при большом числе значений аргумента будет практически невозможно. Функция у( х ) может существовать в каких-нибудь физико-технических или математических расчётах, где её необходимо будет многократно вычислять. В этой ситуации удобно заменить функцию у( х ) приближённой формулой, то есть подобрать некоторую функцию j ( х ), которая приближается   в некотором смысле к у( х ) и просто вычисляется. Затем при всех значениях аргумента полагать, что у( х ) » j ( х )

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

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

Всё изложенное выше можно сформулировать в виде четырёх вопросов:

Какие значимые точки мы будем использовать?

Какой класс  приближающих функций будет нами использован?

Какой критерий согласия-«равенства» мы применим?

Какая точность нам необходима?

Существуют три  группы функций, которые широко применяемых  в численном анализе. Первая группа включает в себя линейные комбинации функций 1, х , х ² , …, х ⁿ , что совпадает с классом всех многочленов степени n (или меньше). Второй класс - включает в себя функции cos a _i x , sin a _i x . Этот класс имеет непосредственное отношение к рядам Фурье и интегралу Фурье. Третья группа образована функциями e ^{- az} . Эти функции часто встречаются в реальных ситуациях, к ним, например, часто приводят задачи накопления и распада

Что касается критерия согласия или «равенства», то классическим критерием согласия является «точное  совпадение в значимых - узловых  точках». Этот критерий обладает преимуществами простоты теории и выполнения вычислений, но он также имеет неудобство из-за игнорирования шума (погрешности, возникающей  при измерении или вычислении значений в значимых (узловых) точках). Другой достаточно хороший критерий — есть «наименьшие квадраты». Это  означает, что сумма квадратов  отклонений в узловых точках должна быть наименьшей возможной или, другими  словами, приведена к минимуму. Этот критерий использует неточную информацию, чтобы получить наименьшее количество шума. Третий критерий напрямую связан с именем Чебышева. Основная идея его заключается в том, чтобы привести максимальное отклонение к минимуму. Конечно, могут быть возможны и другие критерии

Более точно  ответить на поставленные нами четыре вопроса можно лишь исходя из условий  и цели каждой задачи в отдельности 

Интерполяция  многочленами

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

Методы  интерполяции Лагранжа и Ньютона 

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

 

является требуемым  многочленом степени n , который равен 1, если x = x _j и 0, когда x = x _i , i № j . Многочлен L _j ( x ) Ч y _j принимает значения y _i в i - й узловой точке и равен 0 во всех других узлах. Из чего следует, что   имеется многочлен степени n , проходящий через n +1 точку ( x _i , y _i )

Другой подход — метод Ньютона (метод разделённых  разностей). Этим методом можно получить аппроксимирующие значения функции  без построения в явном виде аппроксимирующего  полинома. В результате чего получаем формулу для полинома P _n , аппроксимирующую функцию f ( x ):

P(x)=P(x ₀ )+(x-x ₀ )P(x ₀ ,x ₁ )+(x-x ₀ )(x-x ₁ )P(x ₀ ,x ₁ ,x ₂ )+…+

(x-x ₀ )(x-x ₁ )…(x- x _n )P(x ₀ ,x ₁ ,…, x _n );                   

   — разделённая разность 1-го порядка;                   

   — разделённая разность 2-го порядка и т.д

Значения P _n ( x ) в узлах совпадают со значениями f ( x )

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

Сплайн-аппроксимация 

Ещё один метод  аппроксимации — сплайн-аппроксимация  — отличается от полиномиальной аппроксимации  Лагранжем и Ньютоном. Сплайном называется функция, которая вместе с несколькими  производными непрерывна на отрезке  [ a , b ], а на каждом частном интервале этого отрезка [ x _i , x _{i +1} ] в отдельности являются некоторым многочленом невысокой степени. В настоящее время используют кубический сплайн, то есть на каждом локальном интервале функция приближается к полиному третьего порядка. Трудности такой аппроксимации связаны с низкой степенью полинома, поэтому сплайн плохо аппроксимируется с большой первой производной. Сплайновая интерполяция может напоминать лагранжевую тем, что требует только значения в узлах, но не её производных

Метод наименьших квадратов 

Допустим, что  требуется заменить некоторую величину и делается n измерений, результаты которых равны x _i = x + e _i ( i =1, 2, …, n ), где e _i — это ошибки (или шум) измерений, а х — истинное значение. Метод наименьших квадратов утверждает, что наилучшее приближённое значение   есть такое число, для которого минимальна сумма квадратов отклонений от :                   

 

Один из наиболее частых случаев применения этого  метода заключается в том, что  имеющиеся n наблюдений ( x _i , y _i ) ( i =1, 2, …, n ) требуется приблизить многочленом степени m < n                     

 y(x)=a ₀ +a ₁ x+a ₂ x ² +…+ a _m x ^m

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

            

Для нахождения минимума дифференцируем  по каждой из неизвестных a _k . В результате получим:                   

 

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

Полиномы  Чебышева

Критерии согласия данного метода — минимизация  максимальной ошибки

Полиномы Чебышева определяются следующим образом: T _n ( x )= cos ( n Ч arccos ( x ))

Например:    T ₀ ( x )= cos (0)=1,                   

T ₁ ( x )= cos ( q )= x ,                   

T ₂ (x)= cos (2 q )=cos ² ( q )-sin ² ( q )=2x ² -1

Можно было бы и  дальше использовать тригонометрические соотношения для нахождения полиномов  Чебышева любого порядка, но будет лучше  установить для них рекурентное соотношение, связывающее T _{n +1} ( x ), T _n ( x ) и T _{n -1} ( x ):                   

 T _n+1 (x)= cos (n q + q )= cos (n q ) cos ( q )-sin(n q )sin( q ),                   

T _n-1 (x)= cos (n q - q )= cos (n q ) cos ( q )-sin(n q )sin( q )

Складывая эти  неравенства, получим:                   

T _{n +1} ( x )+ T _{n -1} ( x )=2 cos ( n q ) cos ( q )=2 xT _n ( x );                   

 T _n+1 (x)=2xT _n (x)-T _n-1 (x)

 

   

               Рис. 1

Применяя полученные формулы можно найти любой  полином Чебышева. Например, Т  ₃ ( x )=2 xT ₂ ( x )- T ₁ ( x ). Подставляя значения T ₂ ( х ) и Т ₁ ( х ) имеем Т ₃ ( х )=2х(2х ² -1)-х=4х ³ -3х. Графически первые 10 полиномов Чебышева изображены ниже. Последующие полиномы по-прежнему колеблются между +1 и -1, причём период колебания уменьшаются с ростом порядка полинома

Преобразования  q = arccos ( x ) можно рассмотреть как проекцию пересечений полукруга с множеством прямых, имеющих углы равные между собой (рис.1). Таким образом, множество точек x _j , на котором система чебышевских многочленов T _n ( x ) ортогональна, есть:                   

, ( j =0, 1, 2, …, N -1)

Так как T _n ( x ) есть, по существу, cos ( n q ), то они являются равноколеблющимися функциями, и так как они многочлены, то обладают всеми свойствами, которые имеют ортогональные многочлены

Чебышев доказал, что из всех многочленов Р _n ( x ) степени n старшим коэффициентом 1, у многочлена   точная верхняя грань абсолютных значений на интервале -1 Ј x Ј 1 наименьшая. Так как верхняя грань T _n ( x )=1, указанная верхняя грань равна

Практическое  задание 

На практике нам необходимо было изучить приближение  нашей функции полиномами Тейлора 

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

Ниже приведена  таблица коэффициентов первых двенадцати полиномов Чебышева, а также таблица  коэффициентов перед полиномами Чебышева, выражающие первые двенадцать степеней х

Эти данные мы получили, используя программы на страницах 

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

Вводим коэффициенты a ₀ , a ₁ , …, a _n многочлена T ( x ) и образуем массив a _i

Для j =2, 3, …, n и k = n , n -1, …, j в первом случае поднимаясь, а во втором спускаясь, осуществляем преобразование коэффициентов по следующим формулам:

а ) a _k-1 =a _k-2 -a _k