Задачка

Все, что вы хотели знать о программизме, но боялись спросить.
Аватара пользователя
aissp
Маньяк
Сообщения: 2710
Зарегистрирован: 07 ноя 2005, 09:51

Задачка

Сообщение aissp »

А напомните мне кто-нибудь плиз (неохота рыться в литературе а на вскидку не помню).

Надо сгладить векторное поле:

Дано: хаотический набор точек
В каждой точке задано направление вектора и его величина.

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

Функция изначально предполагается хорошей - все что надо непрерывно и дифференцируемо.
8)
Аватара пользователя
Marmot
Графоман
Сообщения: 39279
Зарегистрирован: 17 фев 2003, 17:58
Откуда: Caulfeild
Контактная информация:

Сообщение Marmot »

Первая после прочтения мысль: работать с каждой компонентой вектора как с обычной функцией, скока-у-тебя-мерного пространства в котором определено поле.
А потом востановить вектора в нужных тебе точках.
Хоть сплайнами это можно сделать...

PS хмм, про ошибки я уже потом прочитал :) может сплайны и не самое хорошее решение :)
Аватара пользователя
папа Карло
Шарманщик
Сообщения: 8565
Зарегистрирован: 17 фев 2003, 15:04
Откуда: НН -> BC -> WA -> UT -> CA

Сообщение папа Карло »

B-Spline?
Аватара пользователя
aissp
Маньяк
Сообщения: 2710
Зарегистрирован: 07 ноя 2005, 09:51

Сообщение aissp »

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

ЗЫ По сплайнам я немножко о другом. Естественно там строиться либо триангуляция делоне и дельше аппроксимируются по трегуольникам (можно плоскостями можно один раз диффиринцируемую поверхность натянуть), можно минимизировать дисперсию в кажлй точке (x, y) ето вроде ак кригинг называтся, есть еще что то похожее на кригинг но не он - но ето все о функции f(x, y) а не \vec f(x, y). Я совсем не пойму как ощибку в таком случае считать :(
Аватара пользователя
Azazello
Житель
Сообщения: 769
Зарегистрирован: 16 янв 2007, 04:31

Сообщение Azazello »

Как всегда, хочется влезть в разговор умных людей - не бейте больно если пургу буду нести ;)...
Если я правильно понял, задачка об интерполяции векторного поля с одной сетки на другую. Что использовать для интерполяции - splines, kriging или что-то более простое - это, по-моему, зависит от векторного поля и требуемой точности интерполяции. Если функция заведомо непрерывна и дифференцируема, я бы splines первыми попробовал.
По поводу векторов. Вектор, если мне память не изменяет, определяется N координатами в N-мерном пространстве, будь то декартовы координаты или криволинейные какие. Выбор системы координат зависит от симметрии проблемы, это Вам, aissp, виднее. Если нижеследующее слишком обще, то можно в конкретной системе координат изложить.
В произвольной системе координат {xi} = x1, x2, ..., xN вектор в новой сетке задан как линейная комбинация компонент:

A = SUM( ei * fi( x1, x2, ..., xN ) )

где SUM обозначает суммирование по i oт 1 до N (размерность пространства), {еi} - базис(в общем, необязательно совпадающий с базисом старой системы координат, но, для простоты, считаем, что базисы совпадают), а fi - некие заданные функции координат - интерполяционные функции, зависящие от координат начал и концов неких известных нам векторов старой сетки. При этом, имеем ошибку интерполяции dfi для каждой из функций fi в точках новой сетки. Как эту ошибку считать - вопрос метода интерполяции ( я себе представляю, как считать ошибку для интерполяции полиномами; splines - частный случай полиномов; расписывать сейчас времени, к сожалению, нет, но коротко, в одномерном случае для полинома степени n ошибка интерполяции в точке х:

df = f(x) - pn(x) = f[x1, ..., xn+1, x] * PRO( x - xi )

где PRO - произведение по i от 1 до n+1, a

f[x1, ..., xn+1, x] = SUM( f( xj ) / PRO( xj - xk ) )

где SUM - сумма по j от 1 до n+1, a PRO - произведение по k от 1 до n+1, где k неравно j. ).

Длина вектора даётся, в общем виде, как квадратный корень из скалярного произведения вектора на себя:

|A| = sqrt( < A, A > ) = sqrt( SUM( < ei, ei > * Fi^2 ) )

где Fi - значение функции fi данной точке. Заметим, что в общем случае произвольных криволинейных координат < ei, ei> не равно 1 (но лучше провести нормировку, чтоб мозги себе не парить). Направление вектора задаётся коллинеарным и сонаправленным ему единичным вектором

Е = A / |A|

или направляющими косинусами этого единичного вектора с базисными векторами. В общем виде,

COS( ai ) = < Е, ei > / ( |E| * |ei| )

Ошибка dfi интерполяции в fi приводит, естественно, к ошибкам в |A| и COS( ai ). Ошибка в функции G от неких коррелированных переменных {gi} при неточности измерения dgi даётся выражением, насколько я помню:

dG = sqrt( SUMi( SUMk( Delta_G/Delta_gi * Delta_G/Delta_gk * Ci,k ) ) )

где суммирование идёт по i и k от 1 до N, Delta_G/Delta_gi(gk) - частная производная функции G по переменной gi(gk), и Ci,k - элементы ковариационной матрицы, причём Ci,i = dgi^2.
Однако, если базис {еi} ортонормирован, то наши переменные fi - некоррелированны, т.к. мы независимо интерполируем по каждой из новых координат в ортонормированном базисе, то есть, Ci,k = KroneckerDelta(i,k) * dgi * dgk, то имеем

dG = sqrt( SUM( ( dgi * Delta_G/Delta_gi )^2 ) ),

где G - это наши |A| и COS( ai ) как функции переменных fi с ошибками dfi.

Пардон, что так длинно - я так понимаю, вопрос был в основном именно о последнем уравнении - вычисление ошибок, но мне показалось, что ответ из одного уравнения будет неполным, и Вы, aissp, мне поставите "незачёт" ;)...

Если где напортачил - намекните, но не объясняйте, я постараюсь сам допереть ;).
Аватара пользователя
Garik
Завсегдатай
Сообщения: 480
Зарегистрирован: 02 ноя 2006, 21:03
Откуда: Киев->Торонто->куда глаза глядят

Сообщение Garik »

а поле периодическое или нет? если периодическое, то Фурье конечно же. Если нет, то можно рекурсивно полиномами. оценка тоже рекурсивно считается. попробуй на маслабе покрутить - там можно легко помоделировать любые поля и аппроксимации (хотя еще и не было указано, аппроксимация нужна или интерполяция).
Аватара пользователя
aissp
Маньяк
Сообщения: 2710
Зарегистрирован: 07 ноя 2005, 09:51

Сообщение aissp »

хм то есть все таки утверждается что x, y компоненты вектора независимы и можно инетрполировать по каждой из них.

задача не на аппроксимацию, я видимо плохо объяснил, ща попробую на примере, тока для иллюстрации.

гляди некий заводик неважно какой обогащает скажем уран. Часть етого урана через невысокую трубу просачивается наружу и переноситься с ветром. ну и падает потихоньку. есть некая страна типа Х где находятся 20 таких заводиков разбросанных по всей территории. Так же в етой стране есть 30 шпионов-резидентов которые сидят в точках никак не связанных ни с заводиками ни между собой. Каждые 6 часов шпиены замеряют скорость и направление ветра. На предприятие шпиенов внедрить не удалось:( надо решать обратную задачу из предположения что концентрация в трубе постоянна.

Вся информация стекается в некий мозговой центр где сидит очень умный но ленивый аналист. А его глупый но вредный начальник спрашивает его где концентрация урана будет самой большой и какую ощибку он при етом допустил. Потому как надо послать туда шпиенов в ети точки чтобы взяли пробы грунта для оценки мощности урано перерабатывающего потенциала страны.
8)

Один из ответов считать f(x,y) двумя разными функциями f_x(x,y) f_y(x,y) провести анализ каждой (аппроксимировав функцию заданную в хаотически разбросанных точках (x,y) на квадратную решетку), а затем по етой уже решетки посчитать уравнение переноса тем или иным методом. При аппроксимации отдельно посчитать дисперсии для каждой компонент Df_x(x, y) Df_y(x, y). И учесть ети компоненты при дальнейшем моделировании.

Так? 8)
ura
Житель
Сообщения: 915
Зарегистрирован: 09 мар 2003, 22:46

Сообщение ura »

Аутсорснуть аспиранта или доцента из универа в Киеве, Питере, Москве. Он построит модель и обоснует, Вы ее алгоритмизируете.
Аватара пользователя
aissp
Маньяк
Сообщения: 2710
Зарегистрирован: 07 ноя 2005, 09:51

Сообщение aissp »

:lol: не не катит потому как (1) я лучше ети деньги пропью (2) хороший аспирант доуент проффесор за деньги обоснует все чего угодно :)

Да и меня вобщем то принцЫп интересен.
Аватара пользователя
ajkj3em
Маньяк
Сообщения: 2063
Зарегистрирован: 12 ноя 2006, 06:53

Сообщение ajkj3em »

aissp писал(а):хм то есть все таки утверждается что x, y компоненты вектора независимы и можно инетрполировать по каждой из них.

задача не на аппроксимацию, я видимо плохо объяснил, ща попробую на примере, тока для иллюстрации.

гляди некий заводик неважно какой обогащает скажем уран. Часть етого урана через невысокую трубу просачивается наружу и переноситься с ветром. ну и падает потихоньку. есть некая страна типа Х где находятся 20 таких заводиков разбросанных по всей территории. Так же в етой стране есть 30 шпионов-резидентов которые сидят в точках никак не связанных ни с заводиками ни между собой. Каждые 6 часов шпиены замеряют скорость и направление ветра. На предприятие шпиенов внедрить не удалось:( надо решать обратную задачу из предположения что концентрация в трубе постоянна.

Вся информация стекается в некий мозговой центр где сидит очень умный но ленивый аналист. А его глупый но вредный начальник спрашивает его где концентрация урана будет самой большой и какую ощибку он при етом допустил. Потому как надо послать туда шпиенов в ети точки чтобы взяли пробы грунта для оценки мощности урано перерабатывающего потенциала страны.
8)

Один из ответов считать f(x,y) двумя разными функциями f_x(x,y) f_y(x,y) провести анализ каждой (аппроксимировав функцию заданную в хаотически разбросанных точках (x,y) на квадратную решетку), а затем по етой уже решетки посчитать уравнение переноса тем или иным методом. При аппроксимации отдельно посчитать дисперсии для каждой компонент Df_x(x, y) Df_y(x, y). И учесть ети компоненты при дальнейшем моделировании.

Так? 8)
чисто чтобы разговор поддержать. можно решать ... перебором :)

типа, допустим заводы - расположены так, поcчитали, не угадали,
повторяем ... по науке - метод, понимаешь, монте-карлы. может
кстати оказатcя быстрее обcчитать так, чем сплайны прикручивать
и модель отлаживать
Аватара пользователя
ajkj3em
Маньяк
Сообщения: 2063
Зарегистрирован: 12 ноя 2006, 06:53

Сообщение ajkj3em »

aissp писал(а):хороший аспирант доуент проффесор за деньги обоснует все чего угодно :)
xaxaxa ... это точно
Аватара пользователя
Azazello
Житель
Сообщения: 769
Зарегистрирован: 16 янв 2007, 04:31

Сообщение Azazello »

Хмм... Если базис ортогональный - то независимы. В не ортогональном всё тоже решаемо, но головной боли больше. Я задумался, зависят ли в данном случае fi от компонент, отличных от i-той - похоже, что нет. Так что, всё даже проще.
Однако! Если задача стоит о нахождении положения заводов, то, по-моему, всё ещё проще:
1. Получаем векторное поле от шпионов (или, всё же скалярное поле - замеры радиации в координатах?) и оператор ВЕТЕР.
2. Применяем к этому полю оператор ВЕТЕР - получаем векторное поле переноса радиации (или оно у нас есть сразу - вроде так по условиям задачи).
3. Разбиваем страну на маленькие объёмы (квадраты, если в 2D задача) - размер зависит от корреляционной длины ветра, скорости выпадения радиации, утечки из плоскости (в космос ;)). Считаем поток векторного поля через замкнутую границу (теорема о дивергенции / теорема Стокса поможет), ограничивающую объём. Если он равен нулю ( с учётом потерь) - завода в объёме нет, если нет - завод в объёме; разбиваем объём на более мелкие объёмы - повторяем операцию - находим позицию завода итерационно.
4. Бомбим заводы.

Если я что-то не понял - поясните, будем думать ;)... Вражеские заводы будут разбомблены!!!

Edit: Упс... Всё равно нужно будет на однородную сетку переводить... тьфу ты...
Последний раз редактировалось Azazello 18 апр 2007, 12:18, всего редактировалось 1 раз.
Аватара пользователя
aissp
Маньяк
Сообщения: 2710
Зарегистрирован: 07 ноя 2005, 09:51

Сообщение aissp »

да не пока я не понял ответа :) но думаю 8)

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

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

Теперь замеры скорости ветра есть через каждые 6 часов, время жизни гадости порядка суток, скорость ветра средняя по месяце примерно 6 м/c.

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

Вопрос был - есть ли общие подходы к решению такого класса задач? Когда я могу сказать например что если расстояние между точками замеров гладкой функции 10 км а скорости ветра 6 м с то делать из етого клетку с расстяонием 3 км по стороне имеет смысл а 1 км уже нет. Ну и тд итп. Сыылочку бы :)
Аватара пользователя
Azazello
Житель
Сообщения: 769
Зарегистрирован: 16 янв 2007, 04:31

Сообщение Azazello »

aissp, интересная задачка, спасибо ;)! Сейчас надо пойти своих баранов пасти, но я подумаю. Кое-какие идеи есть, но надо прикинуть... Ссылки, как и знания общего подхода - нет :(...
Но, в общем, размер ячейки сетки должен быть "хорошим" для вычислений. У меня где-то "Численные методы" есть - там хорошо это описано на примере метода Рунге-Кутта. Я посмотрю, там может какие общие формулки есть. Мелкий размер сетки информации нам не прибавит, естественно, но сходимость может повысить. В худшем случае, надо попробовать разные размеры.
Последний раз редактировалось Azazello 18 апр 2007, 13:03, всего редактировалось 1 раз.
Аватара пользователя
sobomax
Маньяк
Сообщения: 3699
Зарегистрирован: 29 июн 2006, 22:53
Откуда: Vancouver

Сообщение sobomax »

Мне вот интересно, где люди такую забористую траву берут, а? :weedman:

-Maxim
Ответить