О численном решении полинома с комплексными коэффициентами

[APTEM]

Здравствуйте,
Вы не могли бы мне подсказать литературу о численном решении алгебраических уравнений n-нной степени с комплексными коэффициентами.

[Comga]

http://www.library.cornell.edu/nr/bookfpdf/f9-5.pdf

[Woland]

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

А также методом последовательных приближений, если предворительно
доказать, что многочлен является сжатием на некотором замкнутом множестве
$G\subset C$.

[незваный гость]

Woland писал(а):

если в качестве начального прближения взять не вещественное а комплексное число

Это, к сожалению, не является ни необходимым, ни достаточным условием. Возможны ситуации, когда выбор действительного начального значения позволит успешно применить метод Ньютона, и возможен неудачный выбор начального комплексного значения, который приведет к комплексной раскачке (аналогичной вещественному случаю; по крайней мере, при бесконечной точности вычислений). Пример: $x^2-14 + 48 {\rm i}$, начальное значение $x_0 = 3 + 4 {\rm i}$. В тоже время выбор $x_0 = 1$ (вещественное) быстро сойдется к корню.

Одним из эвристических методов является внесение случайной комплексной ошибки, меньшей заказанной точности решения.

[ГАЗ-67]

Может быть стоит попробовать выделить мнимую и действительную части и решать традиционными методами ?

[Woland]

ГАЗ-67 писал(а):

Может быть стоит попробовать выделить мнимую и действительную части и решать традиционными методами ?

А ,что такое "традиционные методы"? Многочлен степени выше 4
не имеет решения в радикалах. Если же имеются ввиду: численные
методы. То, какие именно Вы имеете ввиду?

Кроме того , что значит выделить "мнимую и действительную части"?
Это что, представить многочлен ввиде P(x)=G(x)+i*R(x)?
Ну хорошо, представили- а дальше то, что?
Совместно решить следующую систему уравнений, что ли:
G(x)=0
R(x)=0

Тогда вот пример:
$x^2+2ix+5i+1=0$
Выделяем:
$(x^2+1)+(2x+5)i=0$
$P(x)=x^2+1=0$
$G(x)=2x+5=0$
Но ихнии множества решений не пересекаются. И даже не одна комбинация их
корней в числе- a+bi , не удовлетворяет исходному уравнению.

незваный гость писал(а):

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

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

[незваный гость]

Woland писал(а):

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

Побойтесь Бога! Comga дал ссылку на конкретную главу книжки с подробным описанием и примерами программ (я не поленился проверить). Не нравится Фортран -- этот же текст применительно к C. Там и обсуждения, и тексты (и программы, кстати, отлажены).

Woland писал(а):

А сам обобщать, я как то не решился.

А что Вас смутило? Приведите пример, поможем...

[Woland]

незваный гость писал(а):

Побойтесь Бога! Comga дал ссылку на конкретную главу книжки с подробным описанием и примерами программ (я не поленился проверить). Не нравится Фортран -- этот же текст применительно к C. Там и обсуждения, и тексты (и программы, кстати, отлажены).

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

незваный гость писал(а):

А что Вас смутило? Приведите пример, поможем...

Теорема.
Пусть x=w -корень уравнения F(w)=0, а F'(w) отлична от нуля и F''(w)-непрерывна. Тогда существует окрестность D корня w такая,что если начальное приближение W0 пренадлежит этой окрестности, то для метода Ньютана последовательность значений {Wk} сходится к w при $k \to\infty $. При этом для погрешности корня $ e_k=w-w_k $ имеет место соотношение
$lim|\frac{e_k}{e^2_{k-1}}|= |\frac{F''(w)}{2F'(w)}}| $

[незваный гость]

Все правильно. Только в определении окрестности проще сказать "существует $\varepsilon > 0$, такое что если $|w_0 - w| < \varepsilon$....)

К сожалению, эта теорема неконструктивна в том смысле, что работает в некоторой окрестности корня -- а ведь его еще найти надо! Поэтому-то и возникают проблемы. В частности, в случае, о котором я писал выше, в окрестностях точек $\pm \sqrt2 (4-3{\rm i})$ все будет хорошо. Только как угадать?!?

[Woland]

незваный гость писал(а):

Только как угадать?!?

Незнаю.
Но существует теорема о границе распределения корней полинома.

[Woland]

незваный гость писал(а):

К сожалению, эта теорема неконструктивна в том смысле, что работает в некоторой окрестности корня -- а ведь его еще найти надо! Поэтому-то и возникают проблемы. В частности, в случае, о котором я писал выше, в окрестностях точек все будет хорошо. Только как угадать?!?

И

незваный гость писал(а):

Одним из эвристических методов является внесение случайной комплексной ошибки, меньшей заказанной точности решения.

В чём его суть?

[незваный гость]

вместо $x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$ используется $x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} + \varepsilon \, {\rm rand}()$, где $\varepsilon$ несколько меньше ошибки, а ${\rm rand}()$ -- случайная величина. Сходимость, разумеется, несколько хуже, но зато меньше проблем с начальным значением.

"Плохие" начальные легко проверяются в том смысле, что если $z$ плохое, то $f(z x)$ как полином от $x$ имеет все коэффициенты вещественные (точнее, отношения коэффициентов вещественные). Поэтому их легко отсеять до начала итераций. Уйдя же раз с прямой $z\,x$, мы возвращаемся туда только к корню (если он на этой прямой).

[ГАЗ-67]

Woland писал:
Совместно решить следующую систему уравнений, что ли:
G(x)=0
R(x)=0

Тогда вот пример:
$x^2+2ix+5i+1=0$
Выделяем:
$(x^2+1)+(2x+5)i=0$
$P(x)=x^2+1=0$
$G(x)=2x+5=0$
Но ихнии множества решений не пересекаются. И даже не одна комбинация их
корней в числе- a+bi , не удовлетворяет исходному уравнению.

/*********************************************************************************************/
Вы проводите выкладки в предположении , что x- действительное число . Если предположить , что x комплексное число, т.е. x=a+b*i , результат будет , очевидно , другим .
Методов же решения данной проблемы существует много . Методы Лина , Бэрстоу напр.