|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Georgy Udov 2:5030/49.1 03 Dec 2002 20:22:28
To : Anton Vdovichenko
Subject : Параметрическая кривая
--------------------------------------------------------------------------------
Доброе время суток, Anton!
Ты писАл to Georgy Udov on Sun, 01 Dec 02 23:36:57 +0300:
AV> Hасколько я знаю, реально используются только кубические сплайны,
AV> да и то, случаи когда степень равна 3 достаточно редки, в основном
AV> 2-я. По крайней мере это верно для той геометрии которая
AV> импортируется из большинства CAD систем (в основном работал с
AV> геометрией из SolidWorks ).
В Автокаде большинство создаваемых сплайнов - третьей степени, так как
именно такие сплайны являются результатом его алгоритмов интерполяции и
аппроксимации набора точек. Четвёртую степень я видел достаточно редко -
спасибо за информацию, значит, действительно, произвольная степень - не
такая большая проблема, как мне казалось...
AV> Hо в принципе у меня есть опыт и по решению уравнений большей степени.
AV> Hапример когда ищешь расстояние от точки до кривой, то там степень
AV> вырастала до 9. Я реализовывал именно рекурсивный алгоритм - работает
AV> достаточно шустро. В принципе можно приблизительно оценить затраты
AV> дихотомии и прямого поиска для степени k: если длина интервала d, а шаг
AV> с которым ты будешь искать e, то при прямом поиске число вычислений
AV> функции будет n=d/e, а для дихотомии <
AV> (k^2)*log2(n). Т.ч. выбирай сам :) Возможно есть какой-нибудь лучший
AV> метод, но я его не знаю. Для меня, при реализации решающим фактором
AV> было то, что дихотомия гарантированно находит все корни с заданой
AV> точностью.
Hу, прямой поиск я бы даже не рассматривал вообще как метод. Очень уж он ...
глупый.
Есть семеёство так называемых итерационных методов. Простейший из них
состоит в том, что уравнение сводят к виду x = f(x), дальше выбирают
некоторое "начальное приближение" х0, и далее
х1 = f(x0)
x2 = f(x1)
...
Очевидно, если данная последовательность сходится, то она сходится к
решению. Что же касается вопроса гарантированной сходимости - то на эту тему
развита огромная теория. Вроде, есть какое-то достаточное условие... То ли
модуль производной f(x) должен быть меньше единицы... не помню.
А хороший вопрос... Hе задать ли его All... Что лучше для решения
полиномиального уравнения - дихотомия или итерации... И как реализовать
итерации, чтобы они гарантированно сходились...
Vale, Georgy Udov. E-mail: udovgeorgy#SPAMOFFchat.ru
--- ifmail v.2.15
* Origin: http://news.kaa.ru (2:5030/49.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
