Составные кривые Безье

[uni]

Если я правильно осознал тему, то нужно с программистской точки зрения написать как делать аппроксимацию кубическими сплайнами.
Вот могу предложить посмотреть для artful7 следующие документы:
http://slil.ru/26004489 (~450 КБ)
Там:
"Нахождение коэффициентов m1 и m2.pdf"
"Экстраполяционный кубический сплайн.pdf"
"Апроксимация таблицы F(u,x).pdf"

Я делал некую квазидвумерную аппроксимацию экстраполяционным кубическим сплайном.
Метода ewert'а изложена в разных местах, в частности тут:

> Название: Численные методы - использование MATLAB
> Автор: Mathews J. H., Fink K. D.
> Издательство: Williams
> Год: 2001
> Страниц: 716
> Формат: djvu
> Размер: 16 mb
> ISBN: 5-8459-0162-6
> Качество: хорошее
> Серия или Выпуск: 3 издание
> Язык: русский
> В данной книге, ориентированной на пакет MATLAB, изложены основные методы
> численного анализа: численные решения нелинейных уравнений, систем линейных
> уравнений,
> дифференциальных уравнений и т. д. Все методы иллюстрируются примерами, в которых
> используются программы из пакета MATLAB. Книга также содержит приложение, которое
> знакомит читателя с основными принципами построения пакета MATLAB.
> Книга рассчитана на студентов технических вузов, прослушавших курс высшей
> математики и имеющих представление о программировании. Ее целесообразно
> использовать как
> учебник при чтении курсов, посвященных численным методам. Книга выдержала три
> издания и широко используется в высших учебных заведениях США и других стран.

Я слегка доработал. Книжка есть тут: http://www.infanata.org/

Вот картинка применения для тех, кому просто любопытно:


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

Или вот:
http://slil.ru/26004527

Это пример аппроксимации (каким-то, не вспомню) сплайном на неравномерной сетке (тут математики куда больше):


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

P.S. Ой, я наврал. Это не экспоненциальные.
Вот: http://slil.ru/26004551 - это экспоненциальный сплайн.
Картинка похожа:


Приведены готовые алгоритмы. Их можно писать на ЯВУ и будет то же самое.

[artful7]

Цитата:

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

Речь шла о кривых Безье.

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

Интересуют прежде всего широкие возможности настройки формы получаемой кривой.

[uni]

Нее, по формам я не спец. Это к математикам, у них много определений на разные случаи из жизни. Гладкость такая, гладкость сякая. Приближение по тому-то, то по этому-то. Ничего не понятно.

Возможности настройки формы зависят от природы, которая заложена в методику аппроксимации. Также не плохо бы дать чёткие указания что понимается под самими возможностями. Перечислить уже имеющиеся с плюсами и минусами, а там, глядишь, и идеи может быть будут приходить. Широкие-то в сравнении с чем-то ведь. "Широкость" ограничена природой. Я бы даже эту "широкость" понимал как степени свободы некие. Есть методы на равномерной сетке и на неравноотстоящих отсчётах, методы требующие 2, 3, 4 точки и т.д. Методы, которые проходят через начальные точки или приближаются к ним. Есть даже такие, лучше которых приблизиться уже нельзя.

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

Добавлено спустя 1 час 19 минут 13 секунд:

ewert, а не подскажите для $S_{i.j}(x, y)$ как это выражение будет выглядеть или где почитать? Я уже решаюсь на самостоятельный вывод аналогичного построения, но сам я долго буду соображать, чтобы учесть все точки и условия. Ведь где-то, кто-то уже делал.

[artful7]

Подскажите, как в методе Кардано, получив 3 корня, отделить 1 действительный.

[ewert]

uni писал(а):

ewert, а не подскажите для $S_{i.j}(x, y)$ как это выражение будет выглядеть или где почитать? Я уже решаюсь на самостоятельный вывод аналогичного построения, но сам я долго буду соображать, чтобы учесть все точки и условия. Ведь где-то, кто-то уже делал.

Не подскажу, я лично никогда аппроксимациями ФНП не занимался.

artful7 писал(а):

Подскажите, как в методе Кардано, получив 3 корня, отделить 1 действительный.

Если вещественный корень только один, то элементарно -- тупо применив формулу Кардано (именно в этом случае подкоренные выражения оказываются вещественными).

Формула Кардано вообще парадоксальна. Если уравнение имеет комплексные корни, то их можно найти, работая только с вещественными числами. А вот если все корни вещественны -- то для их нахождения без привлечения комплексных чисел не обойтись.

[artful7]

Исходя из смысла искомой переменной $t$, напрашивается проверочное условие: $\[0 \leqslant t \leqslant 1\]$, по которому можно отделить нужный корень из трех полученных.

[Алексей К.]

artful7 писал(а):

Подскажите, как в методе Кардано, получив 3 корня, отделить 1 действительный.

Есть так называемое тригонометрическое решение кубического уравнения (полагаю, во всех популярных справочниках). Комплексные и действительные корни выпиcываются в явном виде (т.е $Re\pm\mathrm{i}\cdot Im$) в зависимости от знаков дискриминанта и коэффициента при $x^1$ приведённого уравнения.

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

Нашёл книжку за 1906 год, Параграф 86.

[artful7]

Цитата:

Формула Кардано вообще парадоксальна.

А альтернатива - приближенный численный метод?

[ewert]

artful7 писал(а):

Цитата:

Формула Кардано вообще парадоксальна.

А альтернатива - приближенный численный метод?

Да. А поскольку Вы собираетесь работать на фиксированном промежутке, т.е. корни у Вас уже локализованы, то, скорее всего, альтернатива даже более эффективная. Т.е. метод Ньютона даст результат даже быстрее, чем формула Кардано.

Но что ещё важнее: этот приближённый метод наверняка даст более точный результат, чем точная формула!

[Алексей К.]

Приближённые методы здесь просты и надёжны (точны). А деление отрезка пополам ещё и быстро кодируется...
Забыл точный смысл слова альтернатива. Их бывает две?
Тригонометрическое решение и численное --- две альтернативы формуле Кардано?

[artful7]

Цитата:

Тригонометрическое решение и численное --- две альтернативы формуле Кардано?

Какое точнее/стабильнее?

[ewert]

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

Забыл точный смысл слова альтернатива. Их бывает две?

Да, ровно. Всегда.

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

[Алексей К.]

artful7 писал(а):

Какое точнее/стабильнее?

Эти вещи во многом зависят от Вас. Здесь уже обсуждались примеры плохих алгоритмов для решения, например, квадратных уравнений. Или, если Вы $a^2-b^2$ программируете как $a^2-b^2$, то получится (может получиться) плохо, а если как $(a-b)*(a+b)$ --- хорошо.

Тригонометрический способ --- я уже писал --- даёт Вам чётко желанные действительные корни (возжелаете комплексных --- получите их). Впарьте в программу оба способа, сравните результаты, в случае заметного расхождения --- ищите, где Вы ошиблись, где плохо спрограммировали. В тригонометрическом решении, полагаю, могут быть такого рода фокусы при вычислении углов. Типа, "не лучше ли мне в этом случае определить угол по синусу, а не по косинусу, как предлагает справочник". Нашли его в более современном изложении? (Корн, Бронштейн-Семендяев; у меня сейчас только тоненький Цыпкин, там есть).

Чего Вы так упираете на эту точность/скорость? Мало задач (с нынешними ЭВМами), где эти штуки критичны (т.е. их много, но типа в другом месте). Или это учебный процесс?

[artful7]

Цитата:

Мало задач, где эти штуки критичны. Или это учебный процесс?

ШУтите! Это самое, самое реальное производство! Цена ошибки слишком высока (в прямом и переносном смысле). Каждые несколько секунд поступают новые данные и накопление ошибки весьма критично, как и скорость.

[ewert]

artful7 писал(а):

ШУтите! Это самое, самое реальное производство! Цена ошибки слишком высока (в прямом и переносном смысле). Каждые несколько секунд поступают новые данные и накопление ошибки весьма критично, как и скорость.

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