ИССЛЕДОВАНИЕ КОМПЛЕКСНОЙ ДИНАМИКИ ОТОБРАЖЕНИЙ, ПОРОЖДАЕМЫХ МЕТОДОМ НЬЮТОНА

RESEARCH OF THE COMPLEX DYNAMICS OF DISPLAYS GENERATED BY THE NEWTON METHOD

Gayane Petrosyan

student, Vladimir state university named after Alexander and Nikolay Stoletovs,

Russia, Vladimir

Natalia Kuranova

scientific advisor, Candidate of Sciences in Physics and Mathematics, associate professor, Vladimir state university named after Alexander and Nikolay Stoletovs,

Russia, Vladimir

АННОТАЦИЯ

Метод Ньютона является фундаментальным инструментом в численном анализе, исследовании операций, оптимизации и управлении. Большинство наиболее эффективных методов в линейном и нелинейном программировании строятся на его основе. В работе описаны вопросы динамики метода Ньютона в комплексной области. Эта задача имеет два аспекта: изучение бассейнов притяжения неподвижных точек и изучение характера сходимости итераций. Оба аспекта допускают геометрическую интерпретацию с помощью раскраски соответствующих областей на комплексной плоскости. В работе построены фрактальные структуры, возникающие в методе Ньютона для уравнений разных степеней.

ABSTRACT

Newton's method is a fundamental tool in numerical analysis, operations research, optimization and control. Most of the more effective methods in linear and nonlinear programming are based on it. The article describes the dynamics of Newton's method in the complex area. This problem has two aspects: the study of the basins of attraction of fixed points and the study of the nature of the convergence of iterations. Both aspects admit geometric interpretation by coloring the relevant areas on the complex plane. In the work, fractal structures are constructed, which develop Newton's method for various degrees.

Ключевые слова: уравнение, фрактал, итерация, комплексный корень, степень.

Keywords: equation, fractal, iteration, complex root, degree.

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

При рассмотрении полиномов различных степеней, были получены результаты, имеющие фрактальную структуру. Области с фрактальными границами появляются при приближенном нахождении корней уравнения алгоритмом Ньютона на комплексной плоскости. Этот вопрос заинтересовал Артура Кэли ещё в 1879 году, однако разрешить его смогли лишь в 70-х годах двадцатого столетия с появлением вычислительной техники [1]. Оказалось, что на пересечениях этих областей (их принято называть областями притяжения) образуются так называемые фракталы — бесконечные самоподобные геометрические фигуры [4].

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

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

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

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

,

,

.

Выделяя действительную и мнимую части в формуле, получаем:

,

 .

Можно увидеть, что точка z с положительной действительной частью перейдет в значение , которое также имеет положительную действительную часть. Таким образом, все точки будут располагаться в I и IV координатных четвертях (сходятся к «положительному» корню ). Поведение точки z с отрицательной действительной частью аналогично, и она будет сходиться к «отрицательному» корню . Плоскость поделена на две части мнимой осью. Так ведут себя все точки комплексной плоскости за исключением точки A и точек мнимой и действительной осей. На рисунке 1 одна полуплоскость соответствует области сходимости к первому корню, а вторая – ко второму корню.

Рисунок 1. Области притяжения к комплексным корням уравнения

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

Рассмотрим простейшее кубическое уравнение   с корнями: ,  и .

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

Однако в действительности ситуация гораздо более сложная. Прежде всего, есть точка = 0, где метод не определен. У нее есть три прообраза. Вновь каждая из этих точек имеет три прообраза и так далее. Таким образом, существуют  точек  , которые после k итераций отображаются в точку = 0, и они порождают счетное множество начальных точек, для которых метод не определен на какой-либо итерации. Для всех остальных точек метод сойдется к одному из корней.

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

,

,

.

Действительная и мнимая части точки комплексной плоскости:

,

.

В 1976 году профессор Корнуолльского университета Джон Хаббард получил эту фрактальную структуру при решении кубических уравнений методом Ньютона.

Рисунок 2. Области притяжения к комплексным корням уравнения

Рисунок 3. Области притяжения к комплексным корням уравнения

Рисунок 4. Области притяжения к комплексным корням уравнения 

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

Рассмотрим еще один вопрос. Будем окрашивать точки одинаковым цветом, если они сходятся к корню за одно и то же число итераций, т.е. имеют одинаковое итерационное расстояние до корня. Каждая область будет окрашена в соответствии с необходимым количеством итераций при сходимости к корню. И снова возникает фрактальная структура.

Рисунок 5. Итерационные области притяжения к комплексным корням уравнения

Рисунок 6. Итерационные области притяжения к комплексным корням уравнения

Рисунок 7. Итерационные области притяжения к комплексным корням уравнения

Рисунок 8. Итерационные области притяжения к комплексным корням уравнения

Рисунок 9. Итерационные области притяжения к комплексным корням уравнения

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

Список литературы:

1. Cayley A. The Newton-Fourier imaginary problem. – Math II, 1879. – 97 с.
2. Julia G. Sur l’iteration des fonctions rationelles. – Journal de Mathematiques Pure et Applique, 1918, № 8. – P. 47–245.
3. Канторович Л. В. О методе Ньютона для функциональных уравнений. – Доклады АН СССР, 1948, 59 (7). – C.1237–1240.
4. Канторович Л. В. Некоторые дальнейшие применения метода Ньютона. – Вестник ЛГУ. Сер.: мат.-мех, 1957, № 7. – C.68–103.
5. Канторович Л. В., Акилов Г. П. Функциональный анализ в нормированных пространствах. – М: Физматгиз, 1959.
6. Newton’s Method and Dynamical System. – Ed. H. O. Peitgen. Berlin: Springer, 1989.