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

Введение

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

(х),которая близка в некотором смысле к у(х) и простовычисляется. Затем при всех значениях аргумента полагают у(х)»j(х).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

является требуемыммногочленом степени n; он равен 1, если x=xjи 0, когда x=xi, i¹

j. Многочлен Lj(x)×yjпринимает значения yiв i-й узловой точке и равен 0 во всех других узлах. Изэтого следует, что <img src="/cache/referats/488/image004.gif" v:shapes="_x0000_i1026"> есть многочлен степени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);

<img src="/cache/referats/488/image006.gif" v:shapes="_x0000_i1027"> — разделённая разность 1-го порядка;

<img src="/cache/referats/488/image008.gif" v:shapes="_x0000_i1028"> — разделённая разность2-го порядка и т.д.

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

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

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

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

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

Предположим, что требуетсязаменить некоторую величину и делается nизмерений, результатыкоторых равны xi=x+e

i(i=1, 2, …, n), где ei— это ошибки (или шум)измерений, а х — истинное значение. Метод наименьшихквадратов утверждает, что наилучшее приближённое значение <img src="/cache/referats/488/image010.gif" v:shapes="_x0000_i1029"> есть такое число, длякоторого минимальна сумма квадратов отклонений от <img src="/cache/referats/488/image012.gif" v:shapes="_x0000_i1030">:

Один из наиболее общихслучаев применения этого метода состоит в том, что имеющиеся 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(q

)=x,

T2(x)=cos(2q

)=cos2(q)-sin2(q)=2x2-1.

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

Tn+1(x)=cos(nq

+q)=cos(nq)cos(q)-sin(nq)sin(q),

Tn-1(x)=cos(nq

-q)=cos(nq)cos(q)-sin(nq)sin(q).

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

Tn+1(x)+Tn-1(x)=2cos(nq

)cos(q)=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, причём период колебания уменьшаются сростом порядка полинома.

Преобразования q

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

<img src="/cache/referats/488/image022.gif" v:shapes="_x0000_i1035">j=0, 1, 2, …,N-1)

Так как Tn(x)есть, по существу, cos(nq

), тоони являются равноколеблющимеся функциями, и так какони многочлены, то обладают всеми свойствами ортогональных многочленов.

Чебышев показал, что из всехмногочленов Рn(x) степени nстаршим коэффициентом 1, у многочлена <img src="/cache/referats/488/image024.gif" v:shapes="_x0000_i1036"> точная верхняя граньабсолютных значений на интервале -1£

x£1 наименьшая. Так какверхняя грань Tn(x)=1, óêàçàííàÿâåðõíÿÿ ãðàíü ðàâíà<img src="/cache/referats/488/image026.gif" v:shapes="_x0000_i1037">.

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

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

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

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

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

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

I.

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

1) Вводим коэффициенты a0,a1, …, an многочлена T(x)и образуем массив ai.

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

а) ak-1=ak-2-ak

б) ak=2ak

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

II. Преобразование коэффициентовполинома Pn(x) вкоэффициенты полинома Tn(x)

1) Вводим коэффициенты полинома Pn(x)— аi

2) Для 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).Используемая в работе программа представлена на странице . Для её написания был использован следующийалгоритм:

I.

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

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

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

Переводим<img src="/cache/referats/488/image030.gif" v:shapes="_x0000_i1039"> в отрезок [a; b]:

<img src="/cache/referats/488/image032.gif" v:shapes="_x0000_i1040"> и вычисляем f(xi)

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

В результате получаем коэффициенты a0, a1, …, an многочлена T(<img src="/cache/referats/488/image036.gif" v:shapes="_x0000_i1042">), ïðèáëèæàþùåãîôóíêöèþf(x).

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

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

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

3) Для k=n, n-1, …, 1 вычисляем bk=ak-bk+2+2xbk+1.

4) Находим T(<img src="/cache/referats/488/image036.gif" v:shapes="_x0000_i1044">)=a0/2 — b2 +xb1

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

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

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

еще рефераты

Еще работы по математике

Реферат по математике

Решение задач - методы спуска

29 Августа 2013

Реферат по математике

Основы математики

20 Июня 2015

Реферат по математике

Призма

29 Августа 2013

Реферат по математике

Цилиндр

3 Августа 2015