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

Контрольная работа

на тему: «Интерполяция многочленами»

Введение

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

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

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

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

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

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

3. Какой критерий согласия мы применим?

4. Какую точность мы хотим?

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

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

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

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

Цель задачи о приближении (интерполяции): данную функцию у(х) требуется приблизительно заменить некоторой функцией 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] в отдельности являются некоторым многочленом невысокой степени. В настоящее время применяют кубический сплайн, то есть на каждом локальном интервале функция приближается к полиному 3-го порядка. Трудности такой аппроксимации связаны с низкой степенью полинома, поэтому сплайн плохо аппроксимируется с большой первой производной. Сплайновая интерполяция напоминает лагранжевую тем, что требует только значения в узлах, но не её производных.

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

Предположим, что требуется заменить некоторую величину и делается 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)=2cos(n q)cos(q)=2xT _n (x);

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

Применяя полученные формулы можно найти любой полином Чебышева. Например, Т ₃ (x)=2xT ₂ (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, указанная верхняя грань равна.

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

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

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

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

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

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

Преобразование коэффициентов полинома Чебышева в коэффициенты традиционного многочлена.

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

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

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

б) a _k =2a _k

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

Преобразование коэффициентов полинома P_n (x) в коэффициенты полинома T_n (x)

1. Вводим коэффициенты полинома P_n (x) - а_i

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

а) a_k =a_k /2

б) a_k-2 =a_k-2 +a_k

с) a₀ =2a ₀

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

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

Приближение функции f(x) по Чебышеву.

1. Задаём степень n многочлена T_n (x) и пределы [a; b] изменения аргумента функции f(x).

2. Для i=0, 1, …, n на отрезке [-1; 1] формируем сетку оптимальных значений аргумента в узлах чебышевской интерполяции:

Переводим в отрезок [a; b]: и вычисляем fx_i

3. Для k=0, 1, …, n и i=0, 1, …, n вычисляем:

В результате получаем коэффициенты a₀ , a₁ , …, a_n многочлена T, приближающего функцию f(x).

Вычисление значений T(x) выполняется по следующему алгоритму:

1. Считая заданным массив a_k , задаём память под массив из n+2 вспомогательных коэффициентов b_k. Полагаем b_n+2 =0, b_n+1 =0.

2. Задаём значения x на [a; b] и переводим их в отрезок [-1; 1] с помощью преобразований:

1. Для k=n, n-1, …, 1 вычисляем b_k =a_k -b_k+2 +2xb_k+1.

2. Находим

T=a ₀ /2 - b₂ +xb₁

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

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

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