2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5  След.
 
 
Сообщение21.07.2008, 22:36 
artful7 писал(а):
Вот тут и возникает вопрос: как получить значение Y при заданной координате Х ?

Решить кубическое уравнение (для данного участка $x_i\le X \le x_{i+1}$, описываемого ф-циями $x_i(t),\:y_i(t)$) $x_i(t_0)=X_i$, корень --- единственный --- должен найтись в пределах $0\le t_0 \le 1$ (альтернатива --- ошибка в программах) и вычислить $y(t_0)$.

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

ewert писал(а):
Это неверно. Если строить обычный сплайн, то однозначность обеспечивается просто по определению.

Знаки производных тут вообще не при чём.

О знаках производных я писал с оговоркой --- "при других построениях" (не сплайн, например).

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

Да и "обычный сплайн", мы, видимо понимаем по-разному. По мне, в "обычном сплайне" однозначность не требуется и не возникнет. Любого типа кривую --- вертикальную прямую, окружность --- мы можем (с некоторой точностью) "обычно просплайновать".

 
 
 
 
Сообщение21.07.2008, 22:41 
Алексей К. писал(а):
Да и "обычный сплайн, мы, видимо понимаем по-разному. По мне, в "обычном сплайне" однозначность не требуется и не возникнет. Любого типа кривую "обычно сплайнуем".

Это (если я правильно Вас понял) совершенно разные неоднозначности. Сплайны строятся неоднозначно, если не заданы некие дополнительные условия, кроме сшивания. Но уж коли они построены, то они уже суть вполне однозначные функции.

 
 
 
 
Сообщение21.07.2008, 22:44 
Да, согласен. (Просто не додумываю до конца --- гости уже на букву сц обозвали). Беру себя в руки, выключаю ЭВМ. :D

 
 
 
 
Сообщение21.07.2008, 23:47 
Аватара пользователя
Спасибо за полезные рассуждения. Продолжим позднее.

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

Особенно заинтересовало следующее:
Алексей К. писал(а):
Решить кубическое уравнение (для данного участка $x_i\le X \le x_{i+1}$, описываемого ф-циями $x_i(t),\:y_i(t)$) $x_i(t_0)=X_i$, корень --- единственный --- должен найтись в пределах $0\le t_0 \le 1$ (альтернатива --- ошибка в программах) и вычислить $y(t_0)$.

 
 
 
 
Сообщение22.07.2008, 00:19 
А что здесь интересного/непонятного? Пишите, не стесняйтесь... Может, Вы чего-то не понимаете (в известных вещах), может, мы (в постановке задачи), может, я где-то ракообразно выразился...

 
 
 
 
Сообщение22.07.2008, 00:42 
Аватара пользователя
Цитата:
Может, Вы чего-то не понимаете (в известных вещах)
С данной темой только начал разбираться.

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

Цитата:
(альтернатива --- ошибка в программах)
Это к чему относилось?

 
 
 
 
Сообщение22.07.2008, 00:51 
Ну, Ваша задача (в создавшемся у меня представлении) сильно напоминает программистскую деятельность (тянущую за собой относительно простую математику). Если описание кривой $y(x)$ (сплайнами ли, не-сплайнами ли) спрограммировано правильно, то упомянутый корень $0\le t_0 \le 1$ должен (а) быть и (б) быть в этом диапазоне единственным. Альтернатива --- ошибка в программах

 
 
 
 
Сообщение22.07.2008, 01:59 
Аватара пользователя
Но при решении кубического уравнения должны быть найдены 3 корня. Причем там будут и комплексные корни.

 
 
 
 
Сообщение22.07.2008, 10:38 
Либо 3 действительных, из которых один и только один будет, по Вашей задаче, в $t\in[0,1]$,
либо 1 действительный, который будет, по Вашей задаче, в $t\in[0,1]$.
По дискриминанту и коэффициентам количество действительный корней определяется сразу.
Вариант: убеждаетесь, что $x(t)$ монотонна на отрезке $[0,1]$ $(x'\ge 0)$, и ищете этот корешок сколь угодно точными приближёнными методами. Или по Кардано.

В суть эталонов и каркасов пока не проник, но Ваше акцентирование полиномов Бернштейна кажется излишним. По ewertу, аберрацией.

А подзадачка про определение ординаты --- вроде как совсем простая. Вас пугает кубическое уравнение?

 
 
 
 
Сообщение22.07.2008, 16:25 
Аватара пользователя
Цитата:
Вас пугает кубическое уравнение?

Пугает не задачка, а усложнения, возникающие при ее решении. Вот если, например, решать ее по методу Кардано (сделал выкладки решения вчера ночью), то в итоге получается нехилая формула, причем, что особенно неприятно, необходимо делать сравнение дискриминантов Q^3 и R^2, что покажет количество корней и их тип (действ./компл.)!

Цитата:
и ищете этот корешок сколь угодно точными приближёнными методами.
Это дополнительные затраты времени. А значение координаты Y на кривой Безье мне нужно будет определить не один раз, а многократно, т.к. вычисление координат точки на кривой Безье предполагается использовать в составе итерационной процедуры оптимизации, следовательно, приближенные методы определения координат сильно затормозят работу всего алгоритма в целом!

Я тут на досуге рассудил (но еще не успел проверить) следующим образом. Если известно, что параметр $t$ в уравнениях параметрической кривой отвечает за пропорциональное положение (в долях от нуля до единицы) точек вычисления соответствующих значений $x$ параметрической кривой, то не лучше ли будет сразу найти такое значение $t_0$, лежащее в интервале $t\in[0,1]$, которое точно будет соответствовать положению заданной абсциссы $x_0$ (для которой требуется вычислить значение $y_0$) - об этом Вы уже говорили выше, но предлагали для этого решить кубическое уравнение $x_i(t_0)=X_i$.
Мне подумалось, что определение значения $t_0$, совпадающего с положением абсциссы $x_0$ можно осуществить исходя из пропорции:
$t_0  = \frac{{x_0  - a }}{{b  - a }}$,
где $a$ и $b$ - соответственно начало и конец интервала (сегмента), на котором построена кривая (элементарная).

Таким образом, если $x_0$ совпадет с началом сегмента, то значение параметра $t_0=0$, а если $x_0$ совпадет с концом сегмента, то параметр $t_0=1$. Любое другое возможное значение абсциссы $x_0$ НА ДАННОМ ИНТЕРВАЛЕ(!) будет иметь соответствующее значение $t_0$, $t_0\in[0,1]$, пропорциональное длине интервала. В этом случае, получив величину $t_0$ найдем $y_0$.
Конечно же, перед вычислением значения $t_0$, необходимо будет очевидным способом определить, а на какой же именно сегмент составной кривой приходится значение заданной абсциссы $x_0$, иначе мы ошибочно попадем на "чужой" интервал (сегмент составной кривой) и, соответственно, на "чужие" параметрические уравнения соседнего сегмента.
Таким мне видится решение. Каково Ваше мнение?

 
 
 
 
Сообщение22.07.2008, 21:05 
Удалил свои наезды (хотя и лёгкие, всё равно извиняюсь). Да, Вы правы, если сплайн строится как функция $y(x)$, то $x$ играет роль традиционного $t$, в смысле $t_0  = \frac{{x_0  - a }}{{b  - a }}$, кубические уравнения отменяются (осознание этого случилось в очереди в магазине; сам слишком привык к кривым, описываемым парой $x(t),y(t)$...)

 
 
 
 
Сообщение23.07.2008, 00:02 
Аватара пользователя
Значит, метОда имеет место быть?

 
 
 
 
Сообщение23.07.2008, 08:22 
Господи, сколько ж можно этот несчастный сплайн мурыжить.

Ну берём набор узлов ("сетку"): $x_0<x_1<x_2<\dots<x_n$ и соответствующие значения $y_0,\;y_1,\;y_2,\;\dots,\;y_n$ (произвольные). Рассматриваем один из отрезков $[x_{i-1};\;x_i]$, $i=1,2,\dots,n$ и обозначаем для него:

$h_i\equiv x_i-x_{i-1}$ -- длина отрезка;

$\widetilde v_i\equiv{y_i-y_{i-1}\over h_i}$ -- "средний наклон" на этом отрезке (т.е. наклон прямой, соединяющей эти две точки);

$S_i(x)$ -- кубический многочлен, представляющий сплайн на этом отрезке.

Кроме того, обозначим через $v_0,\;v_1,\;v_2,\;\dots,\;v_n$ "наклоны" сплайна, т.е. значения первой производной сплайна в соответствующих узлах. Тогда выражение для $S_i(x)$ на указанном участке будет вполне явным и довольно простым:

$$ S_i(x)=y_i + \widetilde v_i\;(x-x_i)+ $$
$$ + (v_{i-1}-\widetilde v_i){(x-x_{i-1})(x-x_{i})^2 \over h_i^2} + $$
$$ + (v_{i}-\widetilde v_i){(x-x_{i-1})^2(x-x_i) \over h_i^2}\;. $$

Здесь первая строчка задаёт линейную функцию, график которой проходит через узловые точки (т.е. интерполяционный многочлен первой степени). Если только эту строку и оставить, то получится кусочно-линейная аппроксимация, график которой -- это ломаная линия. Две последних строки -- это многочлены 3-й степени, устроенные так, чтобы значения производной в узлах оказались бы правильными: $S_i'(x_{i-1})=v_{i-i}$ и $S_i'(x_{i})=v_{i}$ для каждого $i$.

График того, что получилось, представляет собой гладкую кривую (один раз гладкую, т.е. гарантирована непрерывность только первой производной). При любом расположении узлов $\{x_i\}$ вид кривой однозначно определяется наборами узловых значений $\{y_i\}$ и наклонов $\{v_i\}$, которые тоже могут задаваться произвольно.

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

 
 
 
 
Сообщение23.07.2008, 10:09 
В терминах контрольных точек желанная линейность $x(t)$ означает, что две контрольные точки с абсциссами $p_{1,2}$, $(a<p_1<p_2<b)$, разбивают Ваш отрезок $[a,b]$ на три равные части: $p_1=\frac{2a+b}{3},\;p_2=\frac{a+2b}{3}$. Играться можно только с ординатами.

 
 
 
 
Сообщение23.07.2008, 22:33 
Аватара пользователя
Можно вопросик насчет NURBS?
В такого рода кривых (плоских) есть особые параметры, позволяющие существенно изменять форму отдельных участков кривой и, следовательно, всей кривой в целом. Но в плоских кривых NURBS требуются два отдельных параметрических уравнения (от параметра t), что иногда не совсем удобно. Так вот, хочу узнать, возможно ли построить кривую, которая будет описана в виде $y=f(x)$ и при этом иметь широкие возможности настройки, как у кривых NURBS.

 
 
 [ Сообщений: 66 ]  На страницу Пред.  1, 2, 3, 4, 5  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group