Интерполяция

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

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

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

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

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

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

Методы интерполяции Лагранжа и Ньютона Один из подходов к задаче интерполяции метод Лагранжа.Основная идея этого метода состоит в том, чтобы прежде всего найти многочлен, который принимает значение 1 в одной узловой точке и 0 во всех других. Легко видеть, сто функция является требуемым многочленом степени n он равен 1, если xxj и 0, когда xxi, ij. Многочлен Ljxyj принимает значения yi в i-й узловой точке и равен 0 во всех других узлах.

Из этого следует, что есть многочлен степени n, проходящий через n1 точку xi, yi. Другой подход метод Ньютона метод разделнных разностей.Этот метод позволяет получить аппроксимирующие значения функции без построения в явном виде аппроксимирующего полинома.

В результате получаем формулу для полинома Pn, аппроксимирующую функцию fx PxPx0x-x0Px0,x1x-x0x-x1Px0,x1,x2 x-x0x-x1x-xnPx0,x1 xn разделнная разность 1-го порядка разделнная разность 2-го порядка и т.д. Значения Pnx в узлах совпадают со значениями fx Фактически формулы Лагранжа и Ньютона порождают один и тот же полином, разница только в алгоритме его построения. Сплайн-аппроксимация Другой метод аппроксимации сплайн-аппроксимация отличается от полиномиальной аппроксимации Лагранжем и Ньютоном.

Сплайном называется функция, которая вместе с несколькими производными непрерывна на отрезке a, b, а на каждом частном интервале этого отрезка xi, xi1 в отдельности являются некоторым многочленом невысокой степени.В настоящее время применяют кубический сплайн, то есть на каждом локальном интервале функция приближается к полиному 3-го порядка. Трудности такой аппроксимации связаны с низкой степенью полинома, поэтому сплайн плохо аппроксимируется с большой первой производной.

Сплайновая интерполяция напоминает лагранжевую тем, что требует только значения в узлах, но не е производных.Метод наименьших квадратов Предположим, что требуется заменить некоторую величину и делается n измерений, результаты которых равны xixi i1, 2 n, где i это ошибки или шум измерений, а х истинное значение. Метод наименьших квадратов утверждает, что наилучшее приближнное значение есть такое число, для которого минимальна сумма квадратов отклонений от Один из наиболее общих случаев применения этого метода состоит в том, что имеющиеся n наблюдений xi, yi i1, 2 n требуется приблизить многочленом степени m n yxa0a1xa2x2amxm Вычисленная кривая ух в некотором смысле дат сложное множество значений уi. Метод наименьших квадратов утверждает, что следует выбирать многочлен, минимизирующий функцию. Для нахождения минимума дифференцируем по каждой из неизвестных ak. В результате получим Определитель этой системы отличен от нуля и задача имеет единственное решение.

Но система степеней не ортогональна, и при больших значениях n задача плохо обусловлена.

Эту трудность можно обойти, используя многочлены ортогональные с заданным весом на заданной системе точек, но к этому прибегают только в задачах, связанных с особенно тщательной статической обработкой эксперимента. Полиномы Чебышева Критерии согласия данного метода минимизация максимальной ошибки.Полиномы Чебышева определяются следующим образом Tnxcosnarccosx Например T0xcos01, T1xcosx, T2xcos2cos2-sin22x2-1. Можно было бы и дальше использовать тригонометрические соотношения для нахождения полиномов Чебышева любого порядка, но будет лучше установить для них рекурентное соотношение, связывающее Tn1x, Tnx и Tn-1x Tn1xcosncosncos-sinnsin, Tn-1xcosn-cosncos-sinnsin.

Складывая эти неравенства, получим Tn1xTn-1x2cosncos2xTnx Tn1x2xTnx-Tn-1x. Применяя полученные формулы можно найти любой полином Чебышева.Например, Т3x2xT2x-T1x. Подставляя значения T2х и Т1х имеем Т3х2х2х2-1-х4х3-3х. Графически первые 10 полиномов Чебышева изображены ниже. Последующие полиномы по-прежнему колеблются между 1 и -1, причм период колебания уменьшаются с ростом порядка полинома.

Преобразования arccosx можно рассматривать как проекцию пересечения полукруга с множеством прямых, имеющих равные углы между собой рис.1. Таким образом, множество точек xj, на котором система чебышевских многочленов Tnx ортогональна, таково , j0, 1, 2, ,N-1 Так как Tnx есть, по существу, cosn, то они являются равноколеблющимеся функциями, и так как они многочлены, то обладают всеми свойствами ортогональных многочленов.

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

Как уже упоминалось выше, многочлены Тейлора легко вычислять, а так же превращать в степенные ряды. В этом мы и убедились на практике.Ниже представлена таблица коэффициенты первых 12-и полиномов Чебышева, а также таблица коэффициентов перед полиномами Чебышева, выражающие первые 12 степеней х. Эти данные мы получили, используя программы на страницах В этих программах использовались следующие алгоритмы I. Преобразование коэффициентов полинома Чебышева в коэффициенты традиционного многочлена. 1 Вводим коэффициенты a0, a1 an многочлена Tx и образуем массив ai. 2 Для j2, 3 n и kn, n-1 j в первом случае поднимаясь, а во втором спускаясь, проводим преобразование коэффициентов по следующим формулам а ak-1ak-2-ak б ak2ak В результате получаем коэффициенты полинома Pnx II. Преобразование коэффициентов полинома Pnx в коэффициенты полинома Tnx 1 Вводим коэффициенты полинома Pnx аi 2 Для jn, n-1 2 и kj, j1 n в первом случае спускаясь, а во втором поднимаясь, проводим преобразование коэффициентов по следующим формулам а akak2 б ak-2ak-2ak с a02a0 В результате получим коэффициенты полинома Тnx. Любопытно было бы узнать, какую ошибку мы получаем при разложении степенной функции по полиномам Чебышева.

Для этого, используя выше описанные алгоритмы, я сначала представлял функцию yxn где n брал от 1 до 10 через полиномы Чебышева Tn, а затем чтобы оценить ошибку чебышевское разложение снова превращал в многочлен.

Выполнив эти операции, я получил достаточно интересные результаты.

Для нечтных n ошибка настолько мала, что е едва можно различить на графиках стр Для чтных же степеней мы наблюдаем смещение графика, полученного в результате преобразования, вниз относительно оригинала. Это можно объяснить следующим образом. За смещение графика нест ответственность коэффициент перед x0. Вспомним алгоритмы, они построены так, что каждый предыдущий коэффициент вычисляется через последующий.То есть в результате накапливающаяся ошибка вычисления больше всего влияет на коэффициент при x0. Следствием этого является смещение графиков чтных степеней, так как в их разложении присутствует этот коэффициент.

Заметим также, что смещение при разложении функции yx2 больше, чем при разложении функции yx10. Этот тоже легко объяснить, так как при увеличении степени вклад T0 в разложении степенной функции уменьшается.Что же касается нечтных степеней, то мы получили такое хорошее совпадение так как чтные коэффициенты в разложении нечтных степеней равны 0, а коэффициенты при всех степенях x, кроме нулевой влияют лишь на отклонение ветвей.

Подтверждением этого служат графики на странице . Следующим этапом работы являлось приближение полиномами Чебышева произвольной функции.В качестве исходной функции я взял функцию ysin4x3. Используемая в работе программа представлена на странице . Для е написания был использован следующий алгоритм I. Приближение функции fx по Чебышеву. 1 Задам степень n многочлена Tnx и пределы a b изменения аргумента функции fx. 2 Для i0, 1 n на отрезке -1 1 формируем сетку оптимальных значений аргумента в узлах чебышевской интерполяции . Переводим в отрезок a b и вычисляем fxi 3 Для k0, 1 n и i0, 1 n вычисляем . В результате получаем коэффициенты a0, a1 an многочлена T , приближающего функцию fx. II. Вычисление значений Tx выполняется по следующему алгоритму 1 Считая заданным массив ak, задам память под массив из n2 вспомогательных коэффициентов bk. Полагаем bn20, bn10. 2 Задам значения x на a b и переводим их в отрезок -1 1 с помощью преобразований . 3 Для kn, n-1 1 вычисляем bkak-bk22xbk1. 4 Находим T a02 - b2 xb1 Также в программе было использовано разложение в ряд Тейлора для сравнения с разложением по полиномам Чебышева. Прежде всего я рассмотрел приближение на интервале -1 1. Наложив на график sin4x3 график его приближения полиномами Чебышева и график, построенный с помощью разложения в ряд Тейлора, я получил очень точное совпадение.

Визуально нельзя различить три кривых.

Рассмотрим график ошибок.

В соответствии с теорией ошибка Чебышева знакопеременна и распределена более или менее равномерно по всему интервалу. Ошибка же Тейлора небольшая около 0 и сильно увеличивается при приближении к 1 заметим, что в этом и в других случаях ряд Тейлора содержит те же степени x, но с другими коэффициентами. Интереснее рассмотреть приближение на более длинных интервалах.На интервале -1 1 приближение полиномами Чебышева 7-й степени достаточно хорошее, но уже на интервале -10 10 приближение этой же степенью очень плохое стр Рассмотрим приближение на этом же интервале полиномом более высокой степени T11. Получим неплохое приближение, причм на графике очень чтко видно, что ошибка распределена равномерно.

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

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

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