Аппроксимация функции

[FuntPND]

Есть функция $F(t,z)=0$, которая решается численным методом для каждого $t$; Есть еще 2 функции $x = F_x(t,z)$ и $y=F_y(t,z)$.
Нужно аппроксимировать функцию $y=F(x)$ прямыми с заданной точностью $\delta$.
Т.е., по идеи, вот так (или как еще в данном случае можно точность понимать?):
Где $DB=\delta$.

Так вот, точка $A$ есть, как найти точку $C$?

Можно получить одно уравнение найдя расстояние от точки $B$ до прямой $AC$. Если выразить все в $z$ и $t$, учитывая, что есть функция $F(t,z)=0$, получим 2 неизвестные (две точки $B, C$): $z_B, z_C$. Где взять еще одно уравнение?

[AKM]

FuntPND в сообщении #596252 писал(а):

Есть функция $F(t,z)=0$, которая решается численным методом для каждого $t$; Есть еще 2 функции $x = F_x(t,z)$ и $y=F_y(t,z)$.
Нужно аппроксимировать функцию $y=F(x)$

Вы очень коряво задачу описали. Во-первых, буковка F использована для обозначения двух совершенно разный функций (одной и двух переменных). $F(t,z)=0$ --- это не функция, а уравнение ("которОЕ решается численным методом..." функции не решаются). Возможно, оно определяет функцию $z(t)$.

Во-вторых, неудачные обозначения типа $F_x$ напоминают частные производные, о которых, как я понимаю, здесь речи нет. А читать трудно, путаница производится. Вам буковок не хватает? $x=X(t,z)$, или $x=G(t,z)$.

Не хотите переписать аккуратнее?

[Алексей К.]

Думаю, полезно было бы сообщить, как заданы функции $F_{x,y}$, обозначения которых я ниже меняю на $X,Y$. Можно ли из системы

$$\begin{cases}x=X(t,z),\\y=Y(t,z),\end{cases}$$

выразить явно $t=T(x,y)$, $z=Z(x,y)$?

[FuntPND]

AKM в сообщении #596293 писал(а):

Вы очень коряво задачу описали. Не хотите переписать аккуратнее?

К сожалению первое сообщение уже не могу подправить, попробую еще раз.
Есть уравнение $E(t,z)=0$, из которого, к сожалению, нельзя явным образом получить функцию $z(t)$. Для нахождения $z$ по заданному $t$ используется метод Ньютона.
Нужно построить кусочно-линейную аппроксимацию функции $F(x,y)$, где $x=X(t,z)$ и $y=Y(t,z)$.

Точка $A$ известна (известны границы $t$, таким образом для начальной $t$ можно получить $z$ из $E(t,z)=0$, а дальше посчитать $x, y$).

Дальше нужно найти точку $C$ так, чтобы наибольшее расстояние от точки на кривой $F(x,y)$ (в промежутке от $A$ до $C$) до прямой $AC$ было равно $\delta$.
Т.е., можно построить функцию расстояние от любой точки на $F(x,y)$ до $AC$. Учитывая, что $DB=\delta$ получим одно уравнение. И Учитывая, что $DB$ должно быть максимумом этой функции получим другое уравнение. Имея $E(t,z)=0$ можно будет решить систему...

-- 18.07.2012, 11:23 --

Алексей К. в сообщении #596307 писал(а):

Можно ли из системы

$$\begin{cases}x=X(t,z),\\y=Y(t,z),\end{cases}$$

выразить явно $t=T(x,y)$, $z=Z(x,y)$?

К сожалению нет :(

[Алексей К.]

Самое тупое: с каким-то достаточно малым шагом по тэ вычисляете $x_i(t_i), y_i(t_i)$. Шаг можно делать переменным, проверяя как далеко ушла i-я точка от i-минус-первой. И вот какое-то $t_{n}$ (седьмое, или сотое, или каждое) проверяете: $C=(x_n,y_n)$.
Проводите прямую $AC{:}\;ax+by+L=0,\;a^2+b^2=1!,$ и считаете $|\delta_i|=|ax_i+by_i+L|$. Проверяете максимум.

Вообще-то условие экстремума функции $\delta(t)$ можно выписать явно через частные производные $X'_t,X'_z,\ldots,E'_z$, но у меня нет уверенности-ясности, полезно ли это для Вашего дела.

[FuntPND]

Алексей К. в сообщении #596485 писал(а):

Вообще-то условие экстремума функции $\delta(t)$ можно выписать явно через частные производные $X'_t,X'_z,\ldots,E'_z$, но у меня нет уверенности-ясности, полезно ли это для Вашего дела.

Спасибо за вариант.
В идеале конечно хотелось бы получить систему, которую, я так понимаю, можно было бы решить многомерным методом Ньютона и найти $B, C$ без подбора точки $C$. Но на практике, выражения $E(t,z), X(t,z), Y(t,z)$ настолько громоздкие, что даже если точка $C$ известна, я все равно никак не могу представить как получить такую систему и сколько на это может уйти времени :( .

[Алексей К.]

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

Далее, легко выписать, если хотите, упомянутое условие экстремума для случая фиксированной точки С.

Наконец, если оно Вам чем-то приглянётся и не отпугнёт, можно попробовать выписать систему уравнений с двумя неизвестными $t,v$ $(0<t<v)$, где $v$ будет изображать конец отрезка, теперь не фиксированный. Типа

$$D(t,v)=a(v)x(t)+b(v)y(t)+L(v),\quad \begin{cases}D'_t=0,\\D'_v=0. \end{cases}$$

Мне слабо верится в эффективность этого занятия, но можно попробовать, увидеть и бросить. Думаю, лет 100 назад я это пережил (для кривых Безье), бросил, но забыл подробности. Второй попытки должно хватить на оставшиеся N лет...

-- 18 июл 2012, 16:09:00 --

Ой, да не будет там, наверное экстремума функции двух переменных... Думать надо будет. (Этого ещё не хватало, в июле-то!)

[FuntPND]

Алексей К. в сообщении #596579 писал(а):

Я даже не знаю, сообщил ли я Вам что-то новое, написав нормированное уравнение прямой, левая часть которого даёт расстояние (со знаком) от точки до прямой.

Сообщили :)

Алексей К. писал(а):

Ой, да не будет там, наверное экстремума функции двух переменных... Думать надо будет. (Этого ещё не хватало, в июле-то!)

Мне кажется там будет условный экстремум одной переменной (если правильно выразился). Т.е. с помощью нахождения максимума мы фиксируем точку $B$, соответственно нужно искать экстремум только относительно $t$. Но поскольку функция расстояния до прямой зависит и от $z$, а $z$ зависит от $t$, то при поиске экстремума нужно учитывать $E(t,z)=0$, т.е. использовать метод Лагранжа....

[Алексей К.]

Вот так, наверное: $D'_t(t,v)=0$ даст зависимость $t_{extr}(v)$ (хорошо бы единственную), а уравнение $|D(t_{extr}(v),v)|=\delta_{max}$ даст искомое $v$. А уж как это теоретизирование уложится в "пароходы, строчки и другие добрые дела" --- пока неясно...

[FuntPND]

Алексей К. в сообщении #596485 писал(а):

Самое тупое: с каким-то достаточно малым шагом по тэ вычисляете $x_i(t_i), y_i(t_i)$. Шаг можно делать переменным, проверяя как далеко ушла i-я точка от i-минус-первой. И вот какое-то $t_{n}$ (седьмое, или сотое, или каждое) проверяете: $C=(x_n,y_n)$.
Проводите прямую $AC{:}\;ax+by+L=0,\;a^2+b^2=1!,$ и считаете $|\delta_i|=|ax_i+by_i+L|$. Проверяете максимум.

Имеется в виду взять например 10 точек, провести прямую между первой и 10-й точками. Посчитать расстояние от точек с второй по девятую до прямой. Проверить расстояния, если одно из них очень близко к заданной точности - взять 10-ю точку, если нет - идти дальше в право (увеличивать $t$) или вернуться назад (уменьшать $t$)...
Я так понимаю, этот метод не будет гарантировать, что для любой точки полученная аппроксимация будет удовлетворять условию точности. Но при малых шагах на "глаз" оно будет очень близко к заданной точности....

Или Вы имели в виду, что можно перебирать $t$, для каждой строить $AC$. Потом найти условный максимум (экстремум функции расстояния $DB(t,z)$ с учетом $E(t,z)=0$, где $t$ определяет точку $B$) и проверить, выполняется ли условия по точности, исходя из которого двигаться вперед или назад?

[Алексей К.]

FuntPND в сообщении #596964 писал(а):

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

Условия точности всё же обычно не рассматриваются как жёсткие неравенства. Ваше $\delta$ может трактоваться как $\delta\pm10\%$. Или можно в алгоритмах положить дельту типа 0.8 от заданной, для подстраховки.
Если Вы нашли, например, максимум последовательности в 7-й точке, то максимум функции можно уточнить квадратичной интерполяцией по точкам 6,7,8.

Ведь у Вас, похоже, хорошо конкретизированная задача, и это может как-то упростить дело.

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

Посмотрите пока сюда. Там окружностями аппроксимировалось с заданной точностью, а у Вас прямыми. Малость подправить будет несложно, думаю.