Решение системы нелинейных уравнений методом Ньютона

[Abraziv]

DLL в сообщении #1063883 писал(а):

Давайте сузим вашу задачу. Вам что собственно требуется?
Найти численно все решения системы, правильно?
Ее можно выписать в виде системы полиномиальных уравнений? Выпишите ее явно и укажите, что неизвестные, а что параметры...

Вообще желательно и аналитически научиться решать и численно. Но приоритет численный, так как можно задавать погрешность. Могу записать в полиномиальном виде.

-- 18.10.2015, 18:31 --

Вот в таком виде пойдёт?

\left\{ \begin{array}{lcl} x^2 - 2xx_1 + x_1^2 + y^2 - 2yy_1 + y_1^2 +z^2 - 2zz_1 + z_1^2 = R_1^2 \\ x^2 - 2xx_2 + x_2^2 + y^2 - 2yy_2 + y_2^2 +z^2 - 2zz_2 + z_2^2 = R_1^2 + 2R_1R_{21} + R_{21}^2\\ x^2 - 2xx_3 + x_3^2 + y^2 - 2yy_3 + y_3^2 +z^2 - 2zz_3 + z_3^2 = R_2^2 \\ x^2 - 2xx_4 + x_4^2 + y^2 - 2yy_4 + y_4^2 +z^2 - 2zz_4 + z_4^2 = R_2^2 + 2R_2R_{43} + R_{43}^2\\ x^2 + y^2 + bz^2 = a^2 \end{array} \right.

где $x,y,z,R_1,R_2$ - неизвестные, которые требуется найти.
Остальное константы.
Нужно найти все вектора решения данной системы.

Если есть идея, расскажите о ней подробнее пожалуйста.

[iifat]

Abraziv в сообщении #1063868 писал(а):

А, что толку то

Насчёт толка — это к вам. Мне показалось, вы спрашивали, как избавиться от радикалов. Как по мне, квадраты как-то приятнее, впрочем, это мои личные предпочтения. Ну и, как понимаю, факт существования, помимо линейных, ещё и нелинейных уравнений нам обоим известен.

Abraziv в сообщении #1063868 писал(а):

Я как раз и дифференцирую радиус вектор $R(x,y,z)$

Хм. Ну, если радиус-вектор удовлетворяет некоему соотношению, то и взятие производной соотношения менять не должно бы. Хотя смысл ваших действий мне по-прежнему неясен. Никакого движения я в ваших уравнениях не усматриваю.

Abraziv в сообщении #1063868 писал(а):

$R_{21} = R_2 - R_1$

Вот тут только напомню, что равенство — векторное, а константа — не вектор $R_{21}$, а его длина. Так что соотношения куда сложенее.

[Abraziv]

iifat
Нахождение производной это параллельный вопрос. Я не пытаюсь путём дифференцирования избавиться от нелинейности. Это бред если бы я так делал. Про производную я спрашиваю, так как есть ещё одна система немного сложнее, где как раз будет уравнение производной от $R_{ij}$. Вот мне и интересно, эквивалентно ли будет находить производную от уравнения гиперболоида в лоб и нахождением производной от двух уравнений записанных через сферы. Вы понимаете о чём я спрашиваю? Просто если эквивалентно, это сильно упрощает жизнь. Извиняюсь за недопонимание друг друга.

[iifat]

Abraziv в сообщении #1063895 писал(а):

Я не пытаюсь путём дифференцирования избавиться от нелинейности

Разве ж я вас в чём-то подобном обвинял?

Abraziv в сообщении #1063895 писал(а):

эквивалентно ли будет находить производную от уравнения гиперболоида в лоб и нахождением производной от двух уравнений записанных через сферы

Насколько я понимаю, вы таки упорно хотите продифференцировать куб, маскируя свои желания туманными формулировками. Вот смотрите, пример попроще:

$$\left\{\begin{array}{rcl}x^2+y^2&=&2 \\(x-2)^2+y^2&=&2\\\end{array}\right.$$

Решение — $(1,\pm1)$. Теперь дифференцируем.

$$\left\{\begin{array}{rcl}2xdx+2ydy&=&0 \\2(x-2)dx+2ydy&=&0\\\end{array}\right.$$

И чо? В смысле — какой разумный вывод вы хотите/можете/надеетесь из этого извлечь?

[Abraziv]

Хорошо добавлю немного подробностей.
Вот уравнение гиперболоида:
$\sqrt[2]{(x-x_2)^2 + (y-y_2)^2 + (z-z_2)^2}-\sqrt[2]{(x-x_1)^2 + (y-y_1)^2 + (z-z_1)^2} = R_{21}$

Мне известно из начальных условий $R_{21},x_1,x_2,y_1,y_2,z_1,z_2$.

Вот производная от вышеприведенного уравнения:
$ \frac{\partial R_{21}}{\partial t} = v_{21} = \frac{(x-x_2)V_{x2} + (y-y_2)V_{y2} + (z-z_2)V_{z2}}{\sqrt[2]{(x-x_2)^2 + (y-y_2)^2 + (z-z_2)^2}} - \frac{(x-x_1)V_{x1} + (y-y_1)V_{y1} + (z-z_1)V_{z1}}{\sqrt[2]{(x-x_1)^2 + (y-y_1)^2 + (z-z_1)^2}} $

Мне так известно из начальных условий $V_{x1},V_{x2},V_{y1},V_{y2},V_{z1},V_{z2}, v_{21}$.
Теперь понимаете зачем производная? И вот если удастся доказать эквивалентность, о чём я писал в других постах, то этого страшного уравнения удастся избежать.
Но опять же. Это параллельная задача и не мешайте пожалуйста её с основной, т.е. желательно решить без скоростей .

[Dmitriy40]

Насколько понимаю у Вас каждый гиперболоид задан 7-ю числами: координаты двух фокусов и разность расстояний. А начало координат помещено в центр сферы/эллипсойда.
Мысли вслух: а не восстановить ли матрицу поворота/растяжения/смещения для первого гиперболоида и применить её к сфере? Тогда гиперболоид станет задан единичными коэффициентами в канонической форме (к примеру $x^2+y^2=z^2-1, z\geqslant 1$), а сфера всего лишь переместится куда-то из начала координат, повернётся (важно для эллипсоида) и растянется. Не будет ли это проще исходной задачи? Найти линию их пересечения (или точки или отсутствие решений). Потом решения преобразовать по второй матрице поворота до второго гиперболоида (он тоже станет единичным) и снова решить задачу о пересечении, она будет не сложнее предыдущей. А можно и исходную сферу повернуть до второго гиперболоида и потом объединить два решения (в виде линий или точек), нахождением их пересечений, не знаю что будет проще.
Ещё мысль, для случая сферы (а эллипсоид сводится к ней преобразованием единиц по осям) проверить наличие решений можно без решения всей системы, рассмотрев две подзадачи в двух плоскостях, проходящих через фокусы каждого гиперболоида и центр сферы. Что-то мне подсказывает можно будет отделить случаи отсутствия решений и наверное и все решения друг от друга.

[Abraziv]

Спасибо за идею и ответ.
Да всё правильно понимаете.
Идея светлая. Можно будет подумать, попробовать .
Вторую мысль если честно не совсем понял.

[Dmitriy40]

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

[Abraziv]

Давайте подумаем. Если мы перенесём эллипсоид в систему координат любого гиперболоида, то у нас всегда будут пересечения с эллипсоидом, т.к. гиперболоид будет расти из центра эллипсоида, причём пересечения будут описывать на эллипсоиде два сечения, т.е. два эллипса. Или я вас не понял. Вообще на сколько мне известно, только для поворота кривой второго порядка вводится дополнительное слагаемое $xy$ (например).

[Dmitriy40]

Abraziv в сообщении #1063972 писал(а):

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

Вовсе нет. Не перенесём гиперболоид или эллипсоид, а перенесём (и повернём и растянем) только лишь систему координат (далее СК), без изменения взаимного расположения объектов (сферы и гиперболоидов). Соответственно факт наличия (и координаты в исходной СК) решений не изменится.
При изменении СК выберем такую, чтобы гиперболоид определялся в ней попроще, ведь сфера от трансформации СК не изменится (ну кроме радиуса), а только лишь переместится (и изменится радиус). Зато в новой СК остаются лишь параметры координат центра сферы (3 числа) и её радиус (4-е число) и всё (вместо исходных 8-ми чисел, кстати при необходимых 6-ти), остальное "съелось" трансформацией СК. Ну и искать расстояние до сферы думаю проще (сравнить с радиусом и всё), чем до гиперболоида ...
Вот с эллипсоидом будет сложнее, но тут уж надо прикинуть насколько сложнее, возможно всё равно проще исходной задачи с гиперболоидом неизвестно где. Ведь для начала можно оценить наличие решений окружив эллипсоид сферой с максимальным (а можно ещё и минимальным) радиусом эллипсоида - если решений не будет, то их нет и для исходной задачи, часто это тоже важно быстро проверить.

-- 18.10.2015, 16:31 --

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

[Abraziv]

Спасибо за ответ. Независимо от того перемещаем мы систему координат, либо объекты в системе координат, это сразу же усложняет исходные уравнения. Особенно появление таких слагаемых,как $xy$, $yz$ - резко усложняют систему, а они появятся в том или ином уравнение. Вот исходная задача через 4 сферы и эллипсоид:

\left\{ \begin{array}{lcl} x^2 - 2xx_1 + x_1^2 + y^2 - 2yy_1 + y_1^2 +z^2 - 2zz_1 + z_1^2 = R_1^2 \\ x^2 - 2xx_2 + x_2^2 + y^2 - 2yy_2 + y_2^2 +z^2 - 2zz_2 + z_2^2 = R_1^2 + 2R_1R_{21} + R_{21}^2\\ x^2 - 2xx_3 + x_3^2 + y^2 - 2yy_3 + y_3^2 +z^2 - 2zz_3 + z_3^2 = R_2^2 \\ x^2 - 2xx_4 + x_4^2 + y^2 - 2yy_4 + y_4^2 +z^2 - 2zz_4 + z_4^2 = R_2^2 + 2R_2R_{43} + R_{43}^2\\ x^2 + y^2 + bz^2 = a^2 \end{array} \right.

[Dmitriy40]

Abraziv в сообщении #1063994 писал(а):

Независимо от того перемещаем мы систему координат, либо объекты в системе координат, это сразу же усложняет исходные уравнения. Особенно появление таких слагаемых,как $xy$, $yz$ - резко усложняют систему, а они появятся в том или ином уравнение.

Не думаю. После смены системы координат получим такие две системы (по одной для каждого гиперболоида):

$$\left\{\begin{array}{rcl}x'^2+y'^2&=&z'^2-1\\(x'-x'_0)^2+(y'-y'_0)^2+(z'-z'_0)^2&=&R'_0^2\\\end{array}\right.$$

Штрихованные величины относятся к новой системе координат. Второе уравнение выписано для сферы (как более простой случай). Величины $x'_0, y'_0, z'_0, R'_0$ - всего лишь числа, координаты и радиус сферы в новой системе координат, они пересчитываются из исходных параметров один раз.

Но перед точным решением данной системы я предлагаю для начала оценить есть ли вообще у неё решения. Для чего опять же оценить расстояние от гиперболоида до центра сферы. Это можно сделать аналитически, тем более что уравнение гиперболоида достаточно простое (и вероятно функцию расстояния до точки $(x_0,y_0,z_0)$ можно ещё упростить выбором другой системы координат). И если минимальное расстояние будет больше $R'_0$, то дальше и решать нечего.

А если взять плоскость с прямой $z$ и точкой центра сферы, то система ещё больше упростится:

$$\left\{\begin{array}{rcl}t'^2&=&z'^2-1\\(t'-t'_0)^2+(z'-z'_0)^2&=&R'_0^2\\\end{array}\right.$$

здесь $t'=\sqrt{x'^2+y'^2}$ - вторая (к $z'$) координата на плоскости, $t'_0=\sqrt{x'_0^2+y'_0^2}$.
Конечно решение в плоскости не даст полного решения исходной системы (с одним гиперболоидом), но зато позволит оценить наличие решений и даст минимум по одной точке на каждой линии-решении системы с одним гиперболоидом. А считать проще.

Получив же решение в новой системе координат можно пересчитать его в исходную систему или в систему координат второго гиперболоида.
Хотя повторюсь, думаю проще будет взять координаты всех найденные точек (на двух плоскостях от обоих гиперболоидов, проверив заодно совпадения) в исходной системе координат и использовать как начальные приближения для итерационных методов решения исходной системы.

PS. Конкретный вид формул перехода от $x_i, y_i, z_i, R_i$ к $x'_0, y'_0, z'_0, t'_0, R'_0$ выводить лень (думаю в матричной форме будет проще всего), главное что они есть и однозначные (конечно при осмысленных исходных данных по сфере и гиперболоидам). И вычисляются они всего два раза (туда и обратно).
PPS. В общем всё что мог уже сказал, идею выдвинул, дальше муторный труд по выводу формул и написании алгоритма ... Успехов!

-- 18.10.2015, 18:23 --

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

[Abraziv]

Dmitriy40 спасибо вам большое за подробнейший ответ и вашу светлую идею. Я всё обдумаю и попытаюсь реализовать. Ещё раз спасибо.

Можно сделать как говорил iifat, а именно избавиться от радикалов, но путём введения квадратов неизвестных $x,y,z$ в уравнениях гиперболоидов. Положив третье уравнение сферой, вычитаем его из 1 и 2. В итоге получаем два уравнения с 3 неизвестными, далее положим например $z =$ const и решаем систему линейных уравнений, путём исключения $x$ и $y$, далее полученные $x,y$ подставляем например в 3 уравнение (сферы) и приводим подобные относительно $z$. Решаем полученное уравнение, правда не понятно какой степени оно должно получиться (по идеи должно получиться 4). Нашли корни для $z$, далее подставляем в полученные методом исключения выражения $x$ и $y$ и находим корни для оставшихся неизвестных. В итоге получили все корни, но для сферы. Теперь, когда корни для сферы известны и при условии что сплюснутость эллипсоида будет небольшой, а она будет небольшой, используем метод Ньютона для поиска корней системы с эллипсоидом. Бред?

[Abraziv]

Что то я в полу дрёме, не заметил, что можно сразу же использовать уравнение эллипсоида и принять $z^2$ = const, далее как описывал выше, вообщем попробую, если получится будет конечно круто.