Бассейны Ньютона

Бассейны Ньютона

Бассейны Ньютона для полинома пятой степени [math]\displaystyle{ p(x)=x^5-1 }[/math]. Разными цветами закрашены области притяжения для разных корней. Более тёмные области соответствуют большему числу итераций

Бассе́йны Нью́тона, фракталы Ньютона — разновидность алгебраических фракталов.

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

Применим метод Ньютона для нахождения нуля функции комплексного переменного, используя процедуру:

[math]\displaystyle{ z_{n+1}=z_n-\frac{f(z_n)}{f'(z_n)}. }[/math]

Выбор начального приближения [math]\displaystyle{ z_0 }[/math] представляет особый интерес. Так как функция может иметь несколько нулей, в различных случаях метод может сходиться к различным значениям. Однако, какие именно области обеспечат сходимость к тому или иному корню?

История

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

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

Три корня

Рассмотрим уравнение:

[math]\displaystyle{ p(z)=0 }[/math], [math]\displaystyle{ p(z)=z^3-1 }[/math]

Оно имеет три корня. При выборе различных [math]\displaystyle{ z_0 }[/math] процесс будет сходиться к различным корням (областям притяжения). Артур Кэли поставил задачу описания этих областей, границы которых, как оказалось, имеют фрактальную структуру.

Построение

По следующей формуле:

[math]\displaystyle{ z_{i+1} = z_i-\frac{p(z_i)}{p'(z_i)}=z_i-\frac{z_i^3-1}{3\,z_i^2} }[/math]

Масштабирование

Если переместить центр экрана в точку [math]\displaystyle{ z_0 }[/math]и произвести масштабирование ([math]\displaystyle{ z = z_0 + \cfrac{Z}{\alpha} }[/math]), то вместо подстановки [math]\displaystyle{ z }[/math] в многочлен [math]\displaystyle{ P(z) }[/math], можно изменить сам многочлен. Так как [math]\displaystyle{ z_{n+1} = F(z_n) =\gt (z_0+\cfrac{Z_{n+1}}{\alpha}) = F(z_0 + \cfrac{Z_n}{\alpha}) }[/math], а [math]\displaystyle{ F(z) = z-\cfrac{p(z)}{p'(z)} =\gt F(z_0 + \cfrac{Z_n}{\alpha}) = z_0 + \cfrac{Z_n}{\alpha} - \cfrac{p(z(Z))}{p'_z(z(Z))} }[/math], то [math]\displaystyle{ Z_{n+1} = Z_n+\alpha\cdot \cfrac{p(z(Z_n)}{p'_z(z(Z_n)} }[/math]. Так как [math]\displaystyle{ p'_Z(z(Z)) = p'_z(z(Z))\cdot z'_Z(Z) = \cfrac{p'_z(z(Z))}{\alpha} }[/math], то [math]\displaystyle{ p'_z(z(Z)) = \alpha \cdot p'_Z(z(Z)) }[/math].

Тогда

[math]\displaystyle{ Z_{n+1} = Z_n+\cfrac{p(z(Z_n)}{p'_Z(z(Z_n)} }[/math], считая новый многочлен [math]\displaystyle{ P(Z) = p(z(Z)) }[/math], получаем [math]\displaystyle{ Z_{n+1} = Z_n+\cfrac{P(Z_n)}{P'(Z_n)} }[/math]

Литература

1. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
2. Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
3. Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
4. Вавилов С. И. Исаак Ньютон. — М.: Изд. АН СССР, 1945.
5. Волков Е. А. Численные методы. — М.: Физматлит, 2003.
6. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
7. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
8. Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
9. Максимов Ю. А.,Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
10. Морозов А. Д. Введение в теорию фракталов. — МИФИ, 2002.
11. Мандельброт Б. Фрактальная геометрия природы. — М.: «Институт компьютерных исследований», 2002.
12. Пайтген Х.-О., Рихтер П. Х. Красота фракталов. — М.: «Мир», 1993.
13. Федер Е. Фракталы. — М: «Мир», 1991.
14. Фоменко А. Т. Наглядная геометрия и топология. — М.: изд-во МГУ, 1993.
15. Фракталы в физике. Труды 6-го международного симпозиума по фракталам в физике, 1985. — М.: «Мир», 1988.
16. Шредер М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. — Ижевск: «РХД», 2001.
17. Морозов А. Д. Введение в теорию фракталов. — Москва-Ижевск: Институт компьютерных исследований, 2002, 109—111.
18. Кроновер Р. М. Фракталы и хаос в динамических системах. Основы теории. Москва: Постмаркет, 2000. 248—251.

Ссылки

• Красота фракталов
• Построение бассейнов Ньютона на MATLAB