Метод Ньютона и бассейны Ньютона.

Немного теории.

Метод Ньютона - это один из таких методов решения уравнений, когда мы не знаем точную формулу для нахождения всех корней, или эта формула ну о-о-очень трудоёмка. Такие методы называются "Численные методы решения уравнений" - мы определяем корни приближенно с требуемой точностью.

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

Сам Ньютон рассматривал свой метод для полиномов:

Так выглядит полином в общем случае

Вот такой вот сложный вид полинома может быть. Но многочлен 7-й степени в общем случае имеет 7 корней (пересечений с осью X).

Формула метода Ньютона следующая:

Выполняем итерации до тех пор, пока найденный корень при подстановке в уравнение не даст 0 с требуемой точностью.

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

На каждом шаге итерации мы приближаемся к корню.

Обобщение на комплексную плоскость.

Метод Ньютона можно обобщить на комплексную плоскость:

z = x + y*i

Возьмём, к примеру, уравнение 5-й степени

Z**5 - 1 = 0

Поскольку степень равна пяти, это уравнение имеет пять корней, и они расположены где-то по окружности с радиусом r=1 вокруг центра 0+0i:

Правый корень на оси X равен 1+0i. Число итераций всего 4 - корни (чёрный цвет) находятся за 4 итерации только при z0 в пяти закрашенных областях.

Так что же все-таки называют бассейнами Ньютона?

Если мы будем выбирать начальные точки z0 по всей комплексной плоскости, метод Ньютона после итераций будет приводить нас к ближайшему корню. Но, на примере уравнения Z**5 - 1 = 0, на границах секторов и в центре будут наблюдаться спонтанные флюктуации направления приближения к корню.

Если каждую точку раскрасить в свой цвет, в зависимости от корня, к которому она стремится, то мы получим так называемые бассейны Ньютона, раскрашенные каждый в свой цвет. Для уравнения Z**5 - 1 = 0, это пять равных секторов с размытыми границами - на границах и в центре фракталы Ньютона как раз наиболеее выражены:

Здесь число итераций достаточно большое - около 100.

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

Это я и попытался сделать в своей программе.

Описание работы программы для метода Ньютона.

Исходные данные:

Параметры метода Ньютона - как выглядят на экране программы.

Степень k можно менять от 2-х до 12-и.

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

Кроме количества итераций, важное значение имеет и показатель погрешности - при очень маленькой погрешности бассейны имеют всё более стандартный вид секторов:

Степень равна девяти - девять секторов.

При меньшей точности картина может меняться до неузнаваемости:

Точность всего 0.1 (для степени 12)

Само собой, фрагмент можно выделить и увеличить - картины выходят непредсказуемые:

Степень=5, точность=0.01

Названия примеров

В программе есть 10 примеров - по нажатию кнопки рисуется что-то интересное. При этом можно наблюдать и использованные параметры.

Что-то необъяснимое с точки зрения такого дилетанта как я.

Спасибо за внимание тому, кто дочитал.