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

From

Anton Vdovichenko (2:5025/3.8)

To

Georgy Udov

Date

2002-12-03T22:32:24Z

Area

RU.ALGORITHMS

Hello Georgy.

03 Dec 30 19:22, Georgy Udov wrote to Anton Vdovichenko:

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

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

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

  Вообще то я имел ввиду не просто гарантированную сходимость, а гаранию того,
что будут найдены _все_ корни на интервале. Если корней больше одного, то во-первых все равно нужно определять их количество, а во-вторых для каждого из них (т.к. только один из них будет правильным ответом) как то нужно искать хорошее приближение, даже если корень один на интервале, то алгоритм может уйти к какому-нибудь другому корню, за пределами интервала. Я с этим столкнулся когда решал эту же задачу для поверхности, а не для кривой. В этом случае приходилось решать систему из двух нелинейных уравнений и там кроме Ньютона ничего сначала придумать не удалось.
  Кстати, если кто-нибудь здесь знает как гарантированно найти парметрические координаты точки на NURBS поверхности - хотелось бы услышать.

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

  Кажется у того же Ньютона квадратичная сходимость, что гораздо лучше по скорости, чем дихотомия, но зато он обладает всеми вышеперечисленными недостатками :)

Anton

--- GoldED 2.50+
 * Origin: ... (2:5025/3.8)