2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: to worm2
Сообщение19.10.2007, 12:56 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
oliva писал(а):
worm2 писал(а):
Можно попробовать решать тупым перебором на компьютере с каким-то шагом.


Над этим и "пыхтю" :roll:
Проблема в том, что интервал измерения переменный и влияет на соседние. Т.е. при попытке подобрать один интервал (если подходить строго) нужно пересчитывать остальные, что усложняет, запутывает и ставит под сомнение результативность алгоритма.


Я имел в виду такой подход: берём весь диапазон температур, который может измерять датчик (например, 100-5000 К). Зависимость измеряемой температуры от показаний датчика в этом интервале примерно (качественно) нам известна (f(x)). Пробуем построить кубические сплайны по "всевозможным" пяти точкам на этом отрезке. "Всевозможным" означает, что мы берём точки кратными, например, 10 градусам...
Хотя нет...
По функции f(x) сразу должно быть видно, где точки брать гуще, а где реже...
Я, кажется, начал понимать, про какие интервалы Вы говорите...
Ну тогда можно, наверное, предварительно вручную разбить интервал на подинтервалы, в каждом из которых функция "ведёт себя" примерно одинаково? Разве нет? Это, конечно, ещё одно упрощение...

Добавлено спустя 2 минуты 20 секунд:

Полиномы Чебышёва, наверное, в Вашем случае хуже, чем сплайны. У сплайнов почти наверняка погрешность будет меньше. Всё-таки гораздо больше степеней свободы. Исправлено: написанному про степени свободы не верить :)

 Профиль  
                  
 
 Re: to worm2
Сообщение19.10.2007, 13:12 


04/01/07
90
worm2 писал(а):
предварительно вручную разбить интервал на подинтервалы, в каждом из которых функция "ведёт себя" примерно одинаково


Ну вобщем-то с этого все началось и к этому же я потихоньку и пришел :)
Просто некоторые операции ранее ручного подбора теперь автоматизировались.

worm2 писал(а):
Полиномы Чебышёва, наверное, в Вашем случае хуже, чем сплайны. У сплайнов почти наверняка погрешность будет лучше. Всё-таки гораздо больше степеней свободы.


Я боюсь тут у меня не достаточно теор. подготовки, но, если не сложно, уточните пожалуйста, что Вы имеете ввиду?

 Профиль  
                  
 
 Re: to worm2
Сообщение19.10.2007, 13:36 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
oliva писал(а):
worm2 писал(а):
Полиномы Чебышёва, наверное, в Вашем случае хуже, чем сплайны. У сплайнов почти наверняка погрешность будет лучше. Всё-таки гораздо больше степеней свободы.


Я боюсь тут у меня не достаточно теор. подготовки, но, если не сложно, уточните пожалуйста, что Вы имеете ввиду?

Полиномы Чебышёва используются для решения задачи т.н. полиномиальной интерполяции, когда на отрезке выбирают N точек интерполяции, а затем строят многочлен степени (N-1), который в этих N точках совпадает с данной функцией. Этот многочлен единственен (коль скоро выбраны точки интерполяции).
Уникальность же многочленов Чебышёва состоит именно в выборе точек интерполяции. При таком выборе точек теоретическая оценка погрешности полиномиальной интерполяции является минимально возможной (неулучшаемой). olga_helga Вам выписала формулы для выбора точек и оценки погрешности.

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

 Профиль  
                  
 
 
Сообщение19.10.2007, 13:46 


04/01/07
90
Понятно.
А что означает степень свободы?

 Профиль  
                  
 
 
Сообщение19.10.2007, 16:40 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
oliva писал(а):
А что означает степень свободы?

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

1) При полиномиальной интерполяции по N точкам мы строим полином степени (N-1). Число его коэффициентов, которые мы можем независимо друг от друга менять, равно N, т.е. числу точек.

2) При интерполяции кубическими сплайнами по N точкам мы строим 3(N-1) многочленов 3-й степени в каждом из отрезочков, на которые разбивают точки интерполяции отрезок [a,b] (сами концы отрезка также входят в эти N точек). У многочлена 3-й степени 4 неизвестных коэффициента. Таким образом, число степеней свободы здесь равно 4(N-1)...

:oops: Облажался :)

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

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

 Профиль  
                  
 
 
Сообщение19.10.2007, 19:13 


28/09/07
86
Насчет учебника: это пособие УДК 519.6 Кантор С.А. Вычислительная математика Алт.гос.технич. ун-т им. И.И. Ползунова.Барнаул 2004,240 с. Если мне кто-нибудь расскажет как скинуть на какой-нибудь файло-обменник могу скинуть.

 Профиль  
                  
 
 
Сообщение20.10.2007, 13:28 


04/01/07
90
Например http://kingly.ifolder.ru/.
Там нужно зарегистрироваться. На почту они вышлют "подтверждение регистрации". После нажатия ссылки-подтверждения регистрации "перейти на главную". Там слева "скачать", а справа "загрузить". Нужно нажать "обзор", выбрать нужный файл (обещанный :)) и нажать кнопку "загрузить".
Через несколько минут загрузка закончится и откроется окно "Подтверждение закачанных файлов".
Нужно справа внизу набрать зашифрованные цифры и нажать кнопку подтвердить.
Откроется окно "Файл № ... подтвержден" где внизу будет строчка "послать ссылку на файл друзьям". Эту ссылку можно разместить на єтом форуме или выслать мне на почту "trunc@bk.ru". Буду очень благодарен.

 Профиль  
                  
 
 Устойчивость сплайновой интерполяции
Сообщение09.07.2008, 07:27 


04/01/07
90
Доброго вам дня уважаемые!

Сталкивался ли кто-нибудь с "чувствительностью" сплайновой интерполяции к положению узлов сетки, на которой она проводится?

Попробую прояснить. Интерполирую я термометрические характеристики датчиков температуры по градуировочным данным, и придумал такой себе метод поиска оптимальной измерительной сетки для минимальной погрешности при минимальном числе точек (это уже обсуждалось
http://dxdy.ru/topic9563.html ) темы слиты (PAV)
Но оказалось, что минимальная погрешность не всегда есть хорошо. Если разместить точки уж очень неравномерно, можно достичь впечатляюще высоких результатов по точности для одной характеристики, но резко плохих для другой. Т.е. результат интерполяции не есть устойчив и малейшее изменение свойств интерполируемой функции или даже погрешность в измерениях какой-нибудь точки - и погрешность непрогнозируемо большая.
Мне нужно найти какой-нибудь критерий устойчивости сплайна.

Сталкивался ли кто-нибудь с такими проблемами и как бы Вы их решали, если б столкнулись ?

 Профиль  
                  
 
 
Сообщение09.07.2008, 08:40 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Может быть, в качестве критерия качества сетки брать наихудшую точность по всем характеристикам?

Добавлено спустя 4 минуты 30 секунд:

Если точек достаточно много, то можно выделить из них некоторую долю "проверочных", интерполяцию проводить по всем остальным ("обучающим"), а качество мерять на этих проверочных. Если же точек немного, то есть методы типа leave-one-out. Делите все значения на несколько (5-10) групп. Поочередно выбрасываете по одной группе из набора, интерполируете все остальные и считаете ошибку на выброшенной группе. Так делаете для всех групп и результаты усредняете. Это тоже может быть неплохим критерием качества выбранной сетки.

 Профиль  
                  
 
 
Сообщение09.07.2008, 09:31 
Заслуженный участник


11/05/08
32166
oliva писал(а):
olga_helga писал(а):
для зглаживания экспериментальных данных используют апроксимацию.


Да не нужно данные сглаживать :? Аппроксимацию со сглаживанием применяют когда данные получены с погрешностью и им не доверяют.
Я решаю задачу интерполяции и измеренным точкам доверяю больше чем каким-либо расчетным. Интерполяция - нахождение кривой, которая ПРОХОДИТ через экспериментальные точки. :!:

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

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

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

Абсолютные оценки погрешности практически недоступны; обычно применяют како-либо вариант правила Рунге. Это значит, что аппроксимацию проводят два раза: при исходном расположении узлов и при вдвое более частом, а потом смотрят на отклонение друг от друга полученных кривых. Она и будет хорошей оценкой точности (последнего приближения).

Сплайн характеризуется таким принципиальным параметром, как дефект; он определяется количеством условий сшивания на производные в узлах. Говоря формально, дефект -- это разность между степенью сплайна (как многочлена на каждом отрезке) и степенью его гладкости, т.е. к-вом производных, которые непрерывны на всёй совкупности отрезков. Применительно к кубическому сплайну дефект может быть равным либо 2 (когда в узлах сшиваются только первые производные), либо 1 (сшиваются и первые, и вторые производные). При грамотной постановке задачи в обоих случаях получается примерно один порядок точности аппроксимации. Однако сплайны с дефектом 2 слишком недоопределены, т.е. у них слишком много свободных параметров. Обычно недостающие требования определяют из значений "наклонов", т.е. первых производных в узлах, но поди ещё до них доберись в экспериментальной задаче. Поэтому чаще всего работают со спланами минимального (единичного) дефекта. При этом условия сшивания дают некоторую трёхдиагональную систему линейных уравнений, которые легко решаются методом прогонки.

И последнее, наверное. Даже для сплайна с дефектом 1 остаются два свободных параметра, которые обычно фиксируют какими-либо граничными условиями; общая точность аппроксимации, естественно, зависит от этих условий. Максимально достижимая точность для кубического сплайна есть $O(h^4)$ ($h$ -- это расстояние между узлами). Чтобы её не потерять, надо, например, в качестве граничных условиях зафиксировать значения производной на концах (с достаточной точностью -- не хуже $O(h^3)$, если мне не изменяет память). Часто в качестве граничных условий рекомендуют нулевые граничные условия на вторые производные на концах (это вроде как красиво, т.к. соответствует минимизации кривизны графика). Однако погрешность аппроксимации при этом резко загрубляется -- оказывается всего лишь порядка $O(h^2)$. Правда, заметно это огрубление лишь на крайних отрезках, а вглубь промежутка экспоненциально спадает.

 Профиль  
                  
 
 
Сообщение09.07.2008, 09:54 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Темы слиты в одну

Добавлено спустя 16 минут 20 секунд:

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

 Профиль  
                  
 
 
Сообщение09.07.2008, 09:56 
Заслуженный участник


11/05/08
32166
на то и сплайнирование, чтобы минимизировать влияние специфики класса

 Профиль  
                  
 
 
Сообщение09.07.2008, 12:06 


04/01/07
90
ewert писал(а):
Это напрасно Вы так доверчивы. Экспериментальные данные всегда имеют некоторую экспериментальную же погрешность, причём заметную.


Ну мое доверие определяется пониманием. Т.е. погрешность измеренных точек хотя-бы известна :!: . А вот оценить точность расчета - вещь в себе.

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


Мне нравится мысль про соизмеримость растояния между точками и погрешностью и/или расбросом между характеристиками (как в моем случае). Вы ничего не слышали о теоретическом обосновании этого ? Интуитивно я тоже к этому склоняюсь. Может где-то встречали в литературе ?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 28 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group