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

Введение

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

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

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

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

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

Существуют 3 класса или группы функций, широко применяемых в численном анализе. Первая группа включает в себя линейные комбинации функций 1, х, х2, тАж, хn, что совпадает с классом всех многочленов степени n (или меньше). Второй класс образуют функции cos aix, sin aix. Этот класс имеет отношение к рядам Фурье и интегралу Фурье. Третья группа образуется функциями e-az. Эти функции встречаются в реальных ситуациях. К ним, например, приводят задачи накопления и распада.

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

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

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

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

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

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

является требуемым многочленом степени n; он равен 1, если x=xj и 0, когда x=xi, i≠j. Многочлен Lj(x)⋅yj принимает значения yi в i-й узловой точке и равен 0 во всех других узлах. Из этого следует, что есть многочлен степени n, проходящий через n+1 точку (xi, yi).

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

P(x)=P(x0)+(x-x0)P(x0,x1)+(x-x0)(x-x1)P(x0,x1,x2)+тАж+

(x-x0)(x-x1)тАж(x-xn)P(x0,x1,тАж,xn);

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

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

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

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

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

Другой метод аппроксимации тАФ сплайн-аппроксимация тАФ отличается от полиномиальной аппроксимации Лагранжем и Ньютоном. Сплайном называется функция, которая вместе с несколькими производными непрерывна на отрезке [a, b], а на каждом частном интервале этого отрезка [xi, xi+1] в отдельности являются некоторым многочленом невысокой степени. В настоящее время применяют кубический сплайн, то есть на каждом локальном интервале функция приближается к полиному 3-го порядка. Трудности такой аппроксимации связаны с низкой степенью полинома, поэтому сплайн плохо аппроксимируется с большой первой производной. Сплайновая интерполяция напоминает лагранжевую тем, что требует только значения в узлах, но не её производных.

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

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

Один из наиболее общих случаев применения этого метода состоит в том, что имеющиеся n наблюдений (xi, yi) (i=1, 2, тАж, n) требуется приблизить многочленом степени m<n

y(x)=a0+a1x+a2x2+тАж+amxm

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

РГ

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

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

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

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

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

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

T1(x)=cos(θ)=x,

T2(x)=cos(2θ)=cos2(θ)-sin2(θ)=2x2-1.

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

Tn+1(x)=cos(nθ+θ)=cos(nθ)cos(θ)-sin(nθ)sin(θ),

Tn-1(x)=cos(nθ-θ)=cos(nθ)cos(θ)-sin(nθ)sin(θ).

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

Tn+1(x)+Tn-1(x)=2cos(nθ)cos(θ)=2xTn(x);

Tn+1(x)=2xTn(x)-Tn-1(x).

Рис. 1

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

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

, (j=0, 1, 2, тАж,N-1)

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

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

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

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

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

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

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

В этих программах использовались следующие алгоритмы:

Преобразование коэффициентов полинома Чебышева в коэффициенты традиционного многочлена.
Вводим коэффициенты a0, a1, тАж, an многочлена T(x) и образуем массив ai.
Для j=2, 3, тАж, n и k=n, n-1, тАж, j в первом случае поднимаясь, а во втором спускаясь, проводим преобразование коэффициентов по следующим формулам:

а) ak-1=ak-2-ak

б) ak=2ak

В результате получаем коэффициенты полинома Pn(x)

Преобразование коэффициентов полинома Pn(x) в коэффициенты полинома Tn(x)
Вводим коэффициенты полинома Pn(x) тАФ аi
Для j=n, n-1, тАж, 2 и k=j, j+1, тАж, n в первом случае спускаясь, а во втором поднимаясь, проводим преобразование коэффициентов по следующим формулам:

а) ak=ak/2

б) ak-2=ak-2+ak

с) a0=2a0

В результате получим коэффициенты полинома Тn(x). Любопытно было бы узнать, какую ошибку мы получаем при разложении степенной функции по полиномам Чебышева. Для этого, используя выше описанные алгоритмы, я сначала представлял функцию y=xn (где n брал от 1 до 10) через полиномы Чебышева (Tn), а затем чтобы оценить ошибку чебышевское разложение снова превращал в многочлен. Выполнив эти операции, я получил достаточно интересные результаты. Для нечётных n ошибка настолько мала, что её едва можно различить на графиках (стр. ). Для чётных же степеней мы наблюдаем смещение графика, полученного в результате преобразования, вниз относительно оригинала. Это можно объяснить следующим образом. За смещение графика несёт ответственность коэффициент перед x0. Вспомним алгоритмы, они построены так, что каждый предыдущий коэффициент вычисляется через последующий. То есть в результате накапливающаяся ошибка вычисления больше всего влияет на коэффициент при x0. Следствием этого является смещение графиков чётных степеней, так как в их разложении присутствует этот коэффициент. Заметим также, что смещение при разложении функции y=x2 больше, чем при разложении функции y=x10. Этот тоже легко объяснить, так как при увеличении степени вклад T0 в разложении степенной функции уменьшается. Что же касается нечётных степеней, то мы получили такое хорошее совпадение так как чётные коэффициенты в разложении нечётных степеней равны 0, а коэффициенты при всех степенях x, кроме нулевой влияют лишь на отклонение ветвей. Подтверждением этого служат графики на странице .

Следующим этапом работы являлось приближение полиномами Чебышева произвольной функции. В качестве исходной функции я взял функцию y=sin(4x/3). Используемая в работе программа представлена на странице . Для её написания был использован следующий алгоритм:

Приближение функции f(x) по Чебышеву.
Задаём степень n многочлена Tn(x) и пределы [a; b] изменения аргумента функции f(x).
Для i=0, 1, тАж, n на отрезке [-1; 1] формируем сетку оптимальных значений аргумента в узлах чебышевской интерполяции:

Переводим в отрезок [a; b]:

и вычисляем f(xi)

Для k=0, 1, тАж, n и i=0, 1, тАж, n вычисляем:

В результате получаем коэффициенты a0, a1, тАж, an многочлена T(), приближающего функцию f(x).

Вычисление значений T(x) выполняется по следующему алгоритму:
Считая заданным массив ak, задаём память под массив из n+2 вспомогательных коэффициентов bk. Полагаем bn+2=0, bn+1=0.
Задаём значения x на [a; b] и переводим их в отрезок [-1; 1] с помощью преобразований:

Для k=n, n-1, тАж, 1 вычисляем bk=ak-bk+2+2xbk+1.
Находим T()=a0/2 - b2 +xb1

Также в программе было использовано разложение в ряд Тейлора для сравнения с разложением по полиномам Чебышева. Прежде всего я рассмотрел приближение на интервале [-1; 1]. Наложив на график sin(4x/3) график его приближения полиномами Чебышева и график, построенный с помощью разложения в ряд Тейлора, я получил очень точное совпадение. Визуально нельзя различить три кривых. Рассмотрим график ошибок. В соответствии с теорией ошибка Чебышева знакопеременна и распределена более или менее равномерно по всему интервалу. Ошибка же Тейлора небольшая около 0 и сильно увеличивается при приближении к 1 (заметим, что в этом и в других случаях ряд Тейлора содержит те же степени x, но с другими коэффициентами). Интереснее рассмотреть приближение на более длинных интервалах. На интервале [-1; 1] приближение полиномами Чебышева 7-й степени достаточно хорошее, но уже на интервале [-10; 10] приближение этой же степенью очень плохое (стр. ). Рассмотрим приближение на этом же интервале полиномом более высокой степени (T11). Получим неплохое приближение, причём на графике очень чётко видно, что ошибка распределена равномерно. Здесь опять хотелось бы сравнить с разложением в ряд Тейлора. Если посмотреть на графики на странице , мы увидим, что приближение с помощью рядов Тейлора очень хорошее в середине интервала, но сильно отклоняется от эталона на концах. Сравним ошибки чебышевского приближения и приближения с помощью рядов Тейлора. При этом сравнении ясно проявляются свойства полиномов Чебышева тАФ максимальная ошибка меньше, чем при использовании ряда Тейлора.

Итак, мы получили, что на большом интервале хорошее приближение можно построить только используя достаточно большие степени. Действительно, трудно представить себе приближение нескольких периодов синуса с помощью полиномов 3-й, 4-й, 5-й степеней и уж совсем невозможно 1-й и 2-й.

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

Вместе с этим смотрят:

Искусственный интеллект
Использование определенного интеграла для определения площади тела вращения
Исследование кривых и поверхностей второго порядка
Исследование свойств прямоугольного тетраэдра