Корни уравнения сложной функции. Метод Ньютона. (Нужен только совет)

@Arcor · Регистрация: 20.11.2009

Author24 — интернет-сервис помощи студентам

Приветствую всех

.

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

вот имеем такую функцию(надеюсь при переносе сюда, не ошибся нигде)

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{((x-x0)cos(\alpha) +(y-y0)sin(\alpha))^2 }{R1^2} + \frac{(-(x-x0)sin(\alpha) +(y-y0)cos(\alpha))^2 }{R2^2}=1$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?(x-x0)$
сдвиги по х
$https://www.cyberforum.ru/cgi-bin/latex.cgi?(y-y0)$
и по у

$https://www.cyberforum.ru/cgi-bin/latex.cgi?(R1^2)$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?(R2^2)$
радиусы
ну и синусы с косинусами угла осуществляют поворот..

Решаю я все это дело Методом Ньютона.. все хорошо все красиво и главное быстро решается, за 10-15 итераций находится с точностью до 10^-6

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

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

а так как корней может быть 1-4:
1(соприкосновение)
2(пересечение)
3(пересечение + соприкосновение)
4(двойное пересечение)

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

я попробовал примерно таким алгоритмом искать, но не очень получилось хорошо:
берется центральная точка эллипса, того эллипса, который находится левее первого, к ней прибавляем максимальный радиус по х и по у, для верности берем масимально отдаленное расстояние. иными словами так ставим далекую точку в 1 квадранте, так же же для 2 квадранта, чтобы искать в другую сторону и так далее, для всех 4 квадрантов. Вот вроде бы логически верно. Но работает для случая, когда центральные точки эллипсов находтся недалеко друг от друга, в других случаях находятся те точки, которые уже были найдены, находятся по второму, а то и по третьему разу, вот собственно и возникает трудность с нахождением всех

Буду благодарен совету, или другому методу решения

@jogano · 11.06.2015, 02:51

Судя по вашей записи уравнения эллипса, вы поворачиваете оси эллипса на угол $https://www.cyberforum.ru/cgi-bin/latex.cgi?\alpha$ против часовой стрелки, а затем сдвигаете его центр в точку $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(x_0;y_0 \right)$ .
Во-первых, обозначения. У вас два эллипса и у каждого два радиуса. Лучше бы пользоваться традиционными обозначениями для полуосей $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_1,b_1$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_2,b_2$ вместо $https://www.cyberforum.ru/cgi-bin/latex.cgi?R_{11},R_{12},R_{21},R_{22}$ - чёрт ногу сломит...
Метод решения:
Первый эллипс вы записываете в параметрической форме через угол $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varphi$ - угол отклонения радиус-вектора из нового центра $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(x_1,y_1\right)$ в точку эллипса от правого конца большой полуоси (которая наклонена): $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(x\left(\varphi \right),y\left(\varphi \right)\right)=\left(x_1+a_1\cos \varphi \cos \alpha _1-b_1 \sin \varphi \sin \alpha _1; \: y_1+a_1\cos \varphi \sin \alpha _1+b_1 \sin \varphi \cos \alpha _1\right)$
А второй эллипс в каноническом виде $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{\left(\left(x-x_2 \right)\cos \alpha _2+\left(y-y_2 \right)\sin \alpha _2 \right)^2}{a_2^2}+\frac{\left(-\left(x-x_2 \right)\sin \alpha _2+\left(y-y_2 \right)\cos \alpha _2 \right)^2}{b_2^2}=1$
Дальше перебираете значения угла $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varphi \in \left[0;2 \pi \right)$ с какой-то там дискретностью, скажем, 0,01 радиана. Полученную при каждом значении угла пару координат первого эллипса $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left( x\left( \varphi\right),y\left(\varphi \right)\right)$ подставляете в каноническое уравнение второго эллипса. Если точка лежит внутри эллипса, левая часть будет <1,а если вне - то >1. Вам нужно запомнить пары значений угла $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varphi$ , при котором меняется знак сравнения с 1. Вот вам и концы интервала для метода Ньютона. Как нашли первую точку - продолжаете перебирать дальше, пока не обойдёте весь первый эллипс.
Т.о., метод Ньютона применяется для нахождения $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varphi$ . Подставляете найденное значение этого угла в параметрическое уравнение первого эллипса и получаете координаты (x,y) пересечения. Причём все возможные. Единственный нюанс - можно пропустить касание эллипсов. Лечится только повышением уровня дискретности перебора угла $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varphi$ .

@Alex5 · 11.06.2015, 09:24

Сообщение от Arcor

как-то задавать стартовые значения

Сообщение от jogano

... перебираете значения угла...

Другой вариант.
1) Несколько точек одного из эллипсов используем в качестве начальных для метода.
2) Например, для точек phi=0^o, 90^o, 180^o, 270^o применяем метод Ньютона. Если нашли меньше 4 решений, для начальных
точек 45^o, 135^o, ... применяем метод. И т.д.

@Том Ардер · 11.06.2015, 10:57

Сообщение от Arcor

так как корней может быть 1-4

Вариант 0 (отсутствие общих точек) - тоже надо рассматривать.

@Arcor · 11.06.2015, 11:32 **[ТС]**

Сообщение от Том Ардер

Вариант 0 (отсутствие общих точек) - тоже надо рассматривать.

ну это то само собой

я сделал это следующим образом если за 100 итераций ничего не найдено было и ошибка поиска растет - то прекратить поиск

Добавлено через 28 минут

Сообщение от jogano

Во-первых, обозначения. У вас два эллипса и у каждого два радиуса. Лучше бы пользоваться традиционными обозначениями

ну я сразу сказал, что я не математик, тут уж простите за несоответствие в написании обозначений

Сообщение от jogano

Дальше перебираете значения угла $https://www.cyberforum.ru/cgi-bin/latex.cgi? \in \left[0;2 \pi \right )$ с какой-то там дискретностью, скажем, 0,01 радиана. Полученную при каждом значении угла пару координат первого эллипса $https://www.cyberforum.ru/cgi-bin/latex.cgi? x\left( \varphi\right),y\left(\varphi \right)$ подставляете в каноническое уравнение второго эллипса.

не плохо, но будет очень долго

Сообщение от Alex5

1) Несколько точек одного из эллипсов используем в качестве начальных для метода.
2) Например, для точек phi=0o, 90o, 180o, 270o применяем метод Ньютона. Если нашли меньше 4 решений, для начальных
точек 45o, 135o, ... применяем метод. И т.д.

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

всем спасибо, будем биться дальше

Добавлено через 4 минуты

Не по теме:

что-то все куда-то уехало при цитировании, не могу больше изменить сообщение, поправьте пожалуйста

Корни уравнения сложной функции. Метод Ньютона. (Нужен только совет)

Решение

Решение

@Arcor 5705 / 2296 / 466 Регистрация: 20.11.2009 Сообщений: 7,720 Записей в блоге: 1
		1
	Корни уравнения сложной функции. Метод Ньютона. (Нужен только совет) 10.06.2015, 18:24. Показов 1626. Ответов 4 Метки нет (Все метки) Приветствую всех . Ребята нужен совет. В общем я пишу программу, один кусочек ее, это найти точки пересечения двух эллипсов, повернутых и сдвинутых отдносительно начала координат, с точки зрения программирования естественно нету вопросов, вопрос с точки зрения математики. вот имеем такую функцию(надеюсь при переносе сюда, не ошибся нигде) $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{((x-x0)cos(\alpha) +(y-y0)sin(\alpha))^2 }{R1^2} + \frac{(-(x-x0)sin(\alpha) +(y-y0)cos(\alpha))^2 }{R2^2}=1$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?(x-x0)$ сдвиги по х $https://www.cyberforum.ru/cgi-bin/latex.cgi?(y-y0)$ и по у $https://www.cyberforum.ru/cgi-bin/latex.cgi?(R1^2)$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?(R2^2)$ радиусы ну и синусы с косинусами угла осуществляют поворот.. Решаю я все это дело Методом Ньютона.. все хорошо все красиво и главное быстро решается, за 10-15 итераций находится с точностью до 10^-6 берем производные по 2 переменным(х, у), первой и второй функции эллипса, составление матрицы, решение системы уравнений, нахождение приближения х и у, и повторение алгоритма пока не будет достигнута определенная точность, ну вы в курсе, что я тут... проблема вся в том заключается, для того, чтобы искать корни уравнения этим методом, необходимо некое стартовое значение а так как корней может быть 1-4: 1(соприкосновение) 2(пересечение) 3(пересечение + соприкосновение) 4(двойное пересечение) необходимо как-то задавать стартовые значения 4 раза, т.е. предугадывать желательно значение в окресности реальной точки пересечения, так как пользователь не должен принимать участия в решении задачи, я имею ввиду, не должен задавать некие приближения. Я не знаю как сделать, может есть какое-то математическое определение для данной проблемы, выбор некой точки... я попробовал примерно таким алгоритмом искать, но не очень получилось хорошо: берется центральная точка эллипса, того эллипса, который находится левее первого, к ней прибавляем максимальный радиус по х и по у, для верности берем масимально отдаленное расстояние. иными словами так ставим далекую точку в 1 квадранте, так же же для 2 квадранта, чтобы искать в другую сторону и так далее, для всех 4 квадрантов. Вот вроде бы логически верно. Но работает для случая, когда центральные точки эллипсов находтся недалеко друг от друга, в других случаях находятся те точки, которые уже были найдены, находятся по второму, а то и по третьему разу, вот собственно и возникает трудность с нахождением всех Буду благодарен совету, или другому методу решения 0

@jogano $Эксперт по математике/физике$ 6358 / 4065 / 1512 Регистрация: 09.10.2009 Сообщений: 7,550 Записей в блоге: 4
	11.06.2015, 02:51	2
	Сообщение было отмечено Arcor как решение Решение Судя по вашей записи уравнения эллипса, вы поворачиваете оси эллипса на угол $https://www.cyberforum.ru/cgi-bin/latex.cgi?\alpha$ против часовой стрелки, а затем сдвигаете его центр в точку $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(x_0;y_0 \right)$ . Во-первых, обозначения. У вас два эллипса и у каждого два радиуса. Лучше бы пользоваться традиционными обозначениями для полуосей $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_1,b_1$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_2,b_2$ вместо $https://www.cyberforum.ru/cgi-bin/latex.cgi?R_{11},R_{12},R_{21},R_{22}$ - чёрт ногу сломит... Метод решения: Первый эллипс вы записываете в параметрической форме через угол $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varphi$ - угол отклонения радиус-вектора из нового центра $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(x_1,y_1\right)$ в точку эллипса от правого конца большой полуоси (которая наклонена): $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(x\left(\varphi \right),y\left(\varphi \right)\right)=\left(x_1+a_1\cos \varphi \cos \alpha _1-b_1 \sin \varphi \sin \alpha _1; \: y_1+a_1\cos \varphi \sin \alpha _1+b_1 \sin \varphi \cos \alpha _1\right)$ А второй эллипс в каноническом виде $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{\left(\left(x-x_2 \right)\cos \alpha _2+\left(y-y_2 \right)\sin \alpha _2 \right)^2}{a_2^2}+\frac{\left(-\left(x-x_2 \right)\sin \alpha _2+\left(y-y_2 \right)\cos \alpha _2 \right)^2}{b_2^2}=1$ Дальше перебираете значения угла $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varphi \in \left[0;2 \pi \right)$ с какой-то там дискретностью, скажем, 0,01 радиана. Полученную при каждом значении угла пару координат первого эллипса $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left( x\left( \varphi\right),y\left(\varphi \right)\right)$ подставляете в каноническое уравнение второго эллипса. Если точка лежит внутри эллипса, левая часть будет <1,а если вне - то >1. Вам нужно запомнить пары значений угла $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varphi$ , при котором меняется знак сравнения с 1. Вот вам и концы интервала для метода Ньютона. Как нашли первую точку - продолжаете перебирать дальше, пока не обойдёте весь первый эллипс. Т.о., метод Ньютона применяется для нахождения $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varphi$ . Подставляете найденное значение этого угла в параметрическое уравнение первого эллипса и получаете координаты (x,y) пересечения. Причём все возможные. Единственный нюанс - можно пропустить касание эллипсов. Лечится только повышением уровня дискретности перебора угла $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varphi$ . 2

@Alex5 1130 / 789 / 232 Регистрация: 12.04.2010 Сообщений: 2,012
	11.06.2015, 09:24	3
	Сообщение было отмечено Arcor как решение Решение Сообщение от Arcor как-то задавать стартовые значения Сообщение от jogano ... перебираете значения угла... Другой вариант. 1) Несколько точек одного из эллипсов используем в качестве начальных для метода. 2) Например, для точек phi=0^o, 90^o, 180^o, 270^o применяем метод Ньютона. Если нашли меньше 4 решений, для начальных точек 45^o, 135^o, ... применяем метод. И т.д. 1

@Том Ардер $Эксперт по математике/физике$ 4217 / 3412 / 396 Регистрация: 15.06.2009 Сообщений: 5,818
	11.06.2015, 10:57	4
	Сообщение от Arcor так как корней может быть 1-4 Вариант 0 (отсутствие общих точек) - тоже надо рассматривать. 0

@Arcor 5705 / 2296 / 466 Регистрация: 20.11.2009 Сообщений: 7,720 Записей в блоге: 1
	11.06.2015, 11:32 [ТС]	5
	Сообщение от Том Ардер Вариант 0 (отсутствие общих точек) - тоже надо рассматривать. ну это то само собой я сделал это следующим образом если за 100 итераций ничего не найдено было и ошибка поиска растет - то прекратить поиск Добавлено через 28 минут Сообщение от jogano Во-первых, обозначения. У вас два эллипса и у каждого два радиуса. Лучше бы пользоваться традиционными обозначениями ну я сразу сказал, что я не математик, тут уж простите за несоответствие в написании обозначений Сообщение от jogano Дальше перебираете значения угла $https://www.cyberforum.ru/cgi-bin/latex.cgi? \in \left[0;2 \pi \right )$ с какой-то там дискретностью, скажем, 0,01 радиана. Полученную при каждом значении угла пару координат первого эллипса $https://www.cyberforum.ru/cgi-bin/latex.cgi? x\left( \varphi\right),y\left(\varphi \right)$ подставляете в каноническое уравнение второго эллипса. не плохо, но будет очень долго Сообщение от Alex5 1) Несколько точек одного из эллипсов используем в качестве начальных для метода. 2) Например, для точек phi=0o, 90o, 180o, 270o применяем метод Ньютона. Если нашли меньше 4 решений, для начальных точек 45o, 135o, ... применяем метод. И т.д. вот приблизительно то, что я делал, но я точки брал которые не лежали на эллипсе, а просто произвольные в той округе всем спасибо, будем биться дальше Добавлено через 4 минуты Не по теме: что-то все куда-то уехало при цитировании, не могу больше изменить сообщение, поправьте пожалуйста 0