Параметрическая кривая

From

Georgy Udov ()

To

Anton Vdovichenko

Date

2002-12-03T19:22:28Z

Area

RU.ALGORITHMS

From: "Georgy Udov" <udovgeorgy@chat.ru>

Доброе время суток, Anton!
Ты писАл to Georgy Udov on Sun, 01 Dec 02 23:36:57 +0300:

 AV>  Насколько я знаю, реально используются только кубические сплайны,
 AV> да и то, случаи когда степень равна 3 достаточно редки, в основном
 AV> 2-я. По крайней мере это верно для той геометрии которая
 AV> импортируется из большинства CAD систем (в основном работал с
 AV> геометрией из SolidWorks ).

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

 AV> Но в принципе у меня есть опыт и по решению уравнений большей степени.
 AV> Например когда ищешь расстояние от точки до кривой, то там степень
 AV> вырастала до 9. Я реализовывал именно рекурсивный алгоритм - работает
 AV> достаточно шустро.   В принципе можно приблизительно оценить затраты
 AV> дихотомии и прямого поиска для степени k: если длина интервала d, а шаг
 AV> с которым ты будешь искать e, то при прямом поиске число вычислений
 AV> функции будет n=d/e, а для дихотомии <
 AV> (k^2)*log2(n). Т.ч. выбирай сам :) Возможно есть какой-нибудь лучший
 AV> метод, но я его не знаю. Для меня, при реализации решающим фактором
 AV> было то, что дихотомия гарантированно находит все корни с заданой
 AV> точностью.

Ну, прямой поиск я бы даже не рассматривал вообще как метод. Очень уж он ...
глупый.
Есть семеёство так называемых итерационных методов. Простейший из них
состоит в том, что уравнение сводят к виду x = f(x), дальше выбирают
некоторое "начальное приближение" х0, и далее

х1 = f(x0)
x2 = f(x1)
...

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

А хороший вопрос... Не задать ли его All... Что лучше для решения
полиномиального уравнения - дихотомия или итерации... И как реализовать
итерации, чтобы они гарантированно сходились...

Vale, Georgy Udov.  E-mail: udovgeorgy#SPAMOFFchat.ru


--- ifmail v.2.15
 * Origin: http://news.kaa.ru (2:5030/49.1)