Реферат: Интерполяция - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

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

Банк рефератов / Технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 44 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!

Узнайте стоимость написания уникальной работы




Введение

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

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

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

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

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

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

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

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

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

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

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


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

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


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

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

является требуемым многочленом степени n; он равен 1, если x=xj и 0, когда x=xi, ij. Многочлен 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

y(x)=a0+a1x+a2x2+…+amxm

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



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

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


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

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

Полиномы Чебышева определяются следующим образом: Tn(x)=cos(narccos(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).


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


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

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

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

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

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

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


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

  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)

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


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

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

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

.

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

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

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

.

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

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

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

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

.

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

  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-й.

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


1Авиация и космонавтика
2Архитектура и строительство
3Астрономия
 
4Безопасность жизнедеятельности
5Биология
 
6Военная кафедра, гражданская оборона
 
7География, экономическая география
8Геология и геодезия
9Государственное регулирование и налоги
 
10Естествознание
 
11Журналистика
 
12Законодательство и право
13Адвокатура
14Административное право
15Арбитражное процессуальное право
16Банковское право
17Государство и право
18Гражданское право и процесс
19Жилищное право
20Законодательство зарубежных стран
21Земельное право
22Конституционное право
23Конституционное право зарубежных стран
24Международное право
25Муниципальное право
26Налоговое право
27Римское право
28Семейное право
29Таможенное право
30Трудовое право
31Уголовное право и процесс
32Финансовое право
33Хозяйственное право
34Экологическое право
35Юриспруденция
36Иностранные языки
37Информатика, информационные технологии
38Базы данных
39Компьютерные сети
40Программирование
41Искусство и культура
42Краеведение
43Культурология
44Музыка
45История
46Биографии
47Историческая личность
 
48Литература
 
49Маркетинг и реклама
50Математика
51Медицина и здоровье
52Менеджмент
53Антикризисное управление
54Делопроизводство и документооборот
55Логистика
 
56Педагогика
57Политология
58Правоохранительные органы
59Криминалистика и криминология
60Прочее
61Психология
62Юридическая психология
 
63Радиоэлектроника
64Религия
 
65Сельское хозяйство и землепользование
66Социология
67Страхование
 
68Технологии
69Материаловедение
70Машиностроение
71Металлургия
72Транспорт
73Туризм
 
74Физика
75Физкультура и спорт
76Философия
 
77Химия
 
78Экология, охрана природы
79Экономика и финансы
80Анализ хозяйственной деятельности
81Банковское дело и кредитование
82Биржевое дело
83Бухгалтерский учет и аудит
84История экономических учений
85Международные отношения
86Предпринимательство, бизнес, микроэкономика
87Финансы
88Ценные бумаги и фондовый рынок
89Экономика предприятия
90Экономико-математическое моделирование
91Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
- Что ты со своей девушкой разошёлся?
- Полная дура она. Знала же, у меня пена для бритья заканчивается и носки дырявые. А на 23 февраля подарила ноутбук.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru