Полное численное решение алгебраических уравнений

[alekcey]

Null в сообщении #350055 писал(а):

Сразу несколько минусов метода:
1.При маленьком шаге будет работать долго, при большом метод может перепрыгнуть через 2 близких корня.
2.Решение дифура может сильно отклониться от истинной линии.
3.Получился простой перебор точек. При чем здесь Драгилев?
Учтите что данная конкретная задача заключается в поиске корней 1ого уравнения, а этот метод слишком общий. Это пальба из пушки по воробьям, она промахивается.

Вы уже успели поработать с Методом? Или у Вас сильно развиты метафизические способности? Корни пропускаются, когда непосредственно движемся по x, потому что именно в этом случае сказывется влияние величины шага. А здесь мы движемся по самой линии графика (что важно при сильных осцилляционных и амплитудных изменениях ). Потом, мы не просто решаем дифур, решение которого готово соскочить с верного пути, а нас имеется исходное уравнение, ориентируясь на которое, мы всегда можем подкорректировать траекторию, Что касается скорости, то быстрее работают только сходящиеся методы, когда им подсовывают хорошее приближение. Здесь Вы смотрите на плоский пример и говорите о переборе точек, но не плоскости же, а, заметьте, линии, притом, ограниченной длины. То же самое происходит в пространстве любой размерности, где мера линии равна 0…
Ну, а, судя по всему, напоследок, поведайте, какие Вы знаете более быстрые алгоритмы, и какие кто знает вообще алгоритмы полного решения систем алгебраических уравнений?...

Алексей К. в сообщении #350039 писал(а):

alekcey в сообщении #350036 писал(а):

\[ \left\{ \begin{array}{l} dy = 2x - 2; \\ dx = 1; \\ \end{array} \right. \]

Здесь $d$ --- какой-то множитель или по-прежнему дифференциал?

Да какой там дифференциал, скорее всего, множитель, наверное, знак умножения забыл поставить…

[Null]

У Вас dx=1dt, шаг $\Delta t$ постоянный(противного не оговорено или что?), тогда и $\Delta x$ постоянный, так что можно сказать что мы непосредственно движемся по x. В поиске корней многочлена самое сложное локализовать корни, их поиск дихотомией+ньютоном выполниться быстро.
Так сходу алгоритм поиска корней $F^{(n)},F^{(n-1)},...,F', F$ будет наиболее устойчивым к глюкам с точностью вычисления. Сложность $n^2*(log M-log \epsilon)$, Где M - оценка сверху на корни, а $\epsilon$ - точность.

И давайте вначале с 1им уравнением разберемся.

[alekcey]

Null в сообщении #350141 писал(а):

У Вас dx=1dt, шаг $\Delta t$ постоянный(противного не оговорено или что?), тогда и $\Delta x$ постоянный, так что можно сказать что мы непосредственно движемся по x. В поиске корней многочлена самое сложное локализовать корни, их поиск дихотомией+ньютоном выполниться быстро.
Так сходу алгоритм поиска корней $F^{(n)},F^{(n-1)},...,F', F$ будет наиболее устойчивым к глюкам с точностью вычисления. Сложность $n^2*(log M-log \epsilon)$, Где M - оценка сверху на корни, а $\epsilon$ - точность.

И давайте вначале с 1им уравнением разберемся.

Вы чего это, какой постоянный шаг по x? Здесь же система дифф уравнений: y и x находятся согласованно, то есть, шаг адоптируется… Мы получаем решение алгебраического уравнения с двумя неизвестными (пусть, в данном случае искусственно составленного). Точки кривой есть его решение… Вы бы что-нибудь реализовали, или попросили кого, ведь есть же пакеты, или хотя бы примерами полюбопытствовали, а то сразу же оценили сложность…
Вы, извините меня, конечно, но тогда пусть и буква d будет множителем, так, судя по всему, многим будет легче, привычней и понятней… Да, собственно, и тема не про это, поэтому на счёт 3 все дружно забыли об алгебраических системах…

[Null]

Скажите тогда какой метод адаптации вы предлагаете использовать? И напишите какая сложность получиться.

[Алексей К.]

alekcey в сообщении #350156 писал(а):

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

А что, по Вашему буква $d$ в выражении $dx=1$ может быть чем-то ещё? Уж не дифференциалом ли, в самом деле?

[alekcey]

Алексей К. в сообщении #350171 писал(а):

alekcey в сообщении #350156 писал(а):

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

А что, по Вашему буква $d$ в выражении $dx=1$ может быть чем-то ещё? Уж не дифференциалом ли, в самом деле?

…а если бы он вёз макароны? Вижу, заснуть Вы спокойно не сможете, тогда специально для Вас. Система дифф уравнений – это нахождение вектора касательной в каждой точке кривой из условия, что произведение градиента и вектора касательной равно 0 (кстати, что это означает?). Добавьте недостающие буквы по вкусу, например ds, расположите их в удобном для Вас порядке и поместите их в удобное для Вас место. Будет желание, можете совершить ещё какие-нибудь известные Вам действия, результат всё равно для Вас не изменится…
На прощанье хочу Вас поблагодарить за общение по столь важному поводу, ведь как-никак корни, однако… виноват, буквы, всё-таки. Будет случай, передавайте привет остальным…

[alekcey]

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

[GAA]

Используя google, я не смог найти работу А.В. Драгилева, в которой бы он излагал метод, о котором пишет alekcey, т.е. найти такую работу не совсем просто. Сообщая на форуме dxdy данный метод, alekcey также не указывает ни работу А.В. Драгилева, в которой впервые был предложен этот метод, ни работы Драгилева, в которых он ссылается на этот метод, либо его использует.

Работу Иванов А. Б., Пахоменков Ю. М. О применении численного метода решения уравнения Драгилева при синтезе квазигармонических сигналов. // Системы управления и обработки информации: Научн.-техн. сб. / ФНПЦ «НПО «Аврора». СПб., 2007. — Вып. 13. — С. 125-134 в свободном доступе в электронном виде я не нашел, нашел только страницу с аннотацией.

Вторая из упомянутых alekcey работ Дубанов А.А. Численно-аналитическое построение линий пересечения поверхностей методом Драгилева //Электронный журнал Прикладная геометрия, Выпуск 9, номер 19, 2007 доступна в электронном виде: pdf на сайте журнала или html на blagovest2002.narod.ru. В этой работе вообще нет списка ссылок, имеются неточности и опечатки, но отсутствуют: точная формулировка метода, его строгое обоснование, исследование его свойств. Эта работа, возможно, интересна и годится в качестве предварительной электронной публикации, но не может являться официальной развернутой публикацией, посвященной этому методу.

Поскольку не представлены ссылки на работы, доступные в электронном виде или опубликованные в широко распространяемых журналах, дальнейшие ссылки на этот метод будут рассматриваться как откровенная реклама (которая запрещена на форуме). Для возможности дальше ссылаться на этот метод следует: либо подробно и стрго изложить его здесь в теме, и получить одобрение хотя бы одного заслуженного участника, либо привести ссылку (ссылки) на работу(-ты) в специализированном реферируемом журнале. В случае развития флейма в этой теме — тема будет перемещена в «Пургаторий (М)».

[alekcey]

Автор идеи умер в 1997. Его первое официальное сообщение на эту тему находится в сборнике докладов донецкого филиала УАН, вышедшего в первой половине 80-х. Если кто попытается его отыскать, то могу лишь совсем на немного уточнить координаты…
И хочу на всякий случай спросить, стоит ли излагать от себя чего далее по поводу корней, или заслуженные участники уже определили место, где быть теме?

[GAA]

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

Добавлено утром 11.09.10 =-

Донецкого филиала АН УССР не было. В Донецке размещено много академических институтов. Один из них — Институт прикладной математики и механики (ИПММ АН УССР, ныне ИПММ НАНУ). Труды этого института, насколько мне известно, выходили в изд-ве «Наукова думка» в различных сериях. Например, Теория отображений и приближений функкций./ Сборник науч. тр. — Киев: Наук. думка, 1983.

В надежде найти ссылки на работы А.В. Драгилева, я просмотрел номера РЖ Математика за 1976–1990 гг. Нашлась только одна ссылка (РЖ за 1981): Драгилев А.В. Нахождение периодических решений для обыкновенных дифференциальных уравнений на ЭВМ // Ин-т кибернет. АН УССР. Препринт, 1980, № 10.
(Ссылки в Интернете на работы А.В. Драгилева: mathnet.)

[alekcey]

Будем искать все корни алгебраического уравнения. Для этого мы представим переменную в виде суммы её вещественной и мнимой части. Произведя замену, приравняем 0 отдельно вещественную и мнимую часть выражения. Таким образом, у нас получилась система двух уравнений относительно двух неизвестных. Полное решение этой системы даст решение исходного уравнения… Рассмотрим все действия на конкретном примере \[ x^5 {\rm{ }} - {\rm{ }}1{\rm{ }} = {\rm{ }}0;
Приближённое решение этой системы такое:

\[ \begin{array}{l} x_1 {\rm{ = - 0}}{\rm{.8090169943 - }}i{\rm{0}}{\rm{.58778525}}22 \\ x_2 {\rm{ }} = {\rm{ }} - 0.8090169943{\rm{ }} + {\rm{ }}i0.5877852522 \\ {\rm{ }}x_3 {\rm{ }} = {\rm{ }}0.3090169943{\rm{ }} - i0.9510565162 \\ {\rm{ }}x_4 {\rm{ }} = {\rm{ }}0.3090169943{\rm{ }} + i0.9510565162 \\ {\rm{ }}x_5 {\rm{ }} = {\rm{ }}1 \\ \\ \end{array} \]

Посмотрим, каким способом это решение могло быть получено. Произведём замену переменной на сумму мнимой и вещественной части \[x = a + ib, подставим в уравнение, и получим систему:

\[ \begin{array}{l} a^5 {\rm{ }} - {\rm{ }}10a^3 {\rm{ }}b^2 {\rm{ }} + {\rm{ }}5ab^4 {\rm{ }} - {\rm{ }}1{\rm{ }} + {\rm{ }}ib(5a^4 {\rm{ }} - {\rm{ }}10a^2 b^2 {\rm{ }} + {\rm{ }}b^4 {\rm{ }}){\rm{ }} = {\rm{ }}0; \\ \left\{ \begin{array}{l} a^5 {\rm{ }} - {\rm{ }}10a^3 {\rm{ }}b^2 {\rm{ }} + {\rm{ }}5ab^4 {\rm{ }} - {\rm{ }}1 = 0; \\ b(5a^4 {\rm{ }} - {\rm{ }}10a^2 b^2 {\rm{ }} + {\rm{ }}b^4 {\rm{ }}){\rm{ }} = {\rm{ }}0; \\ \end{array} \right. \\ \end{array} \]

Посмотрим на картинке, как решается эта система. Синий график – это линия уровня первого уравнения (вещественного), красный график – линия уровня мнимого уравнения. Окружность показывает область корней. По теории радиус окружности должен быть равен 6, Чёрными точками помечены места пересечения окружности с линией вещественного уравнения, а сиреневыми точками – уже корни уравнения. То есть, корни уравнения соответствуют точкам пересечения линий уровня обоих уравнений. От черных точек по синей линии мы движемся внутрь окружности до пересечения с линией красной. По рисунку корни ищутся с повтором, но это вопрос технический. Аналогично можно двигаться по красной линии вместо синей.
Любое алгебраическое уравнение представимо в виде двух уравнений, линии уровня которых распадаются на связные участки, являющиеся неограниченными множествами…

[alekcey]

alekcey в сообщении #350884 писал(а):

По теории радиус окружности должен быть равен 6,

… по теории радиус окружности в примере равен, конечно же, 2…

[alekcey]

\[ x^{21} {\rm{ }} - {\rm{ }}5x^{10} {\rm{ }} - {\rm{ }}2x^4 {\rm{ }} + {\rm{ }}0.5x^2 {\rm{ }} - {\rm{ }}3x{\rm{ }} + {\rm{ }}11{\rm{ }} = {\rm{ }}0; \]

Красный цвет вещественный, синий мнимый… Как видим, все корни (21) отражены на рисунке. Если провести соответствующую окружность, то все корни окажутся внутри неё, и все участки линий пересекут эту окружность.
Почти то же самое происходит в случае системы алгебраических уравнений, только там будет сфера в пространстве 2n (n – размерность исходной системы), а линии как пересечения по 2n-1 поверхностей между собой …

[GAA]

Чтобы не перегружать это сообщение, я добавил текст к своему предыдущему сообщению.

То, что корни уравнения можно интерпретировать как точки пересечения двух кривых — очевидно.
Используя компьютер, можно приближенно найти точки пересечения этих линий, и тем самым найти решения системы. Если для уравнения n-ой степени приближенно найдено n-корней, то, очевидно, мы приближенно нашли все корни. Вопрос возникает только в случае, если число корней меньше n.

(Пакеты)

На сегодняшний день пакеты компьютерной алгебры «умеют» приближенно находить все корни алгебраического уравнения. Например, решение уравнения второго примера в Maple 12

> fsolve(x^21 - 5*x^10 - 2*x^4 +1/2*x^2 - 3*x +11=0, x, complex);
     -1.147839622-.3401121547*I,   -1.147839622+.3401121547*I,   -.8836122633-.6264001362*I, 
     -.8836122633+.6264001362*I,   -.7580555137-.9266594129*I,   -.7580555137+.9266594129*I,
     -.3196004161-1.027091971*I,   -.3196004161+1.027091971*I,   -.1238784345-1.154956315*I, 
    -.1238784345+1.154956315*I,   .2970797159-1.007975954*I,   .2970797159+1.007975954*I,
      .5234454821-1.043854517*I,   .5234454821+1.043854517*I,   .8670505793-.6811721792*I,
      .8670505793+.6811721792*I,   .9839508951-.5467672333*I,   .9839508951+.5467672333*I,
     1.072112661,   1.109930892,   -1.059124400

Универсальные пакеты довольно несовершенны, например Maple 12

> equ:= expand((x-1)^2*(x-0.9999)^3):
      equ := x^5-4.9997*x^4+9.99880003*x^3-9.998200090*x^2+4.998800090*x-.9997000300
> fsolve(equ);
                 1., 1., 1.
> fsolve(equ, x, complex);
    > .9998500000-.8660254038e-4*I, .9998500000+.8660254038e-4*I, 1., 1., 1.

Однако «руление» интерфейсными и системными переменными, для алгебраического уравнения, проблемы решает

> Digits:= 20;
> fsolve(equ, x, complex);
      .99990000000000000000, .99990000000000000000, .99990000000000000000, 1., 1.

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

В силу всего сказанного выше (в том числе, в предыдущем moderatorial), Ваше, alekcey, сообщение из темы Квадратичные формы 2-й степени выделено в самостоятельную тему, закрыто и перемещено в Карантин. В последующем, подобные Ваши сообщения вне этой темы — будут удаляться, а к Вам — применяться санкции.

Ref. [*]Н. Н. Калиткин, И. П. Пошивайло, “Определение кратности корня нелинейного алгебраического уравнения”, Ж. вычисл. матем. и матем. физ., 48:7 (2008), 1181–1186.

[alekcey]

GAA в сообщении #351264 писал(а):

...

\[{\rm{(x - 1)}}^{{\rm{10}}} {\rm{ = 0;}}\

GAA, сколько раз красный вещественный график проходит через одну точку на оси абсцисс, такой же является кратность корня, но делённая на два. Вот Вам вся проблема кратности корней.
Если здесь и приведены картинки, то это не значит, что ими всё ограничивается. Примеры пересечений с текстами на Маткаде и не только находятся по моей ссылке на сайт экспоненты…
Не привёл я чего, текста программ? Или академической статьи с описанием Метода? На академическую статью я лично не способен, но среди посетителей форума, уверен, есть такие, которые сталкиваются или сталкивались с проблемой полного решения, обобщим, полного решения СНАУ, и с помощью своих вопросов они без Вас разберутся в происходящем. Вы же, скажу прямо, по не совсем понятным причинам процессу мешаете По содержанию Вы проявляете, мягко говоря, некомпетентность (например, если Вы ещё до сих пор не знаете, то меньше, чем максимальная степень n, числа корней в алгебраическом уравнении с вещественными коэффициентами не бывает, так уж случилось…), а ссылки на книги и копание в Интернете эту ситуацию не изменят…
Ни секунды не сомневаюсь о последствиях данного сообщения, но и тратить силы не по содержанию, преодолевая состояние чьего-либо административного восторга и непонятно чего ещё, сами понимаете, хочется не очень…
Почему бы ни общаться по содержанию? Но опыт показывает, что по содержанию не получается, проще общаться ни о чём, потому что, похоже, цели у данного и схожего с ним проектов примерно одинаковые…