Метод Ньютона и метод Галлея - фракталы.

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

Я уже писал про один из численных методов решения уравнений - метод Ньютона:

Формула метода Ньютона для комплексных чисел.

и бассейны Ньютона:

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

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

Формула метода Галлея.

Можно преобразовать эту формулу и тогда она примет следующий вид:

Преобразованная формула метода Галлея.

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

• - f(x)/f'(x) мы вычисляем только раз;
• f''(x)/f'(x) очень хорошо упрощается во многих случаях, в том числе для функции f(x)=x**k - 1, которая и используется в моей программе.

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

Так как метод Галлея более точный, чем метод Ньютона (потому что он дополнительно учитывает вторую производную), он имеет кубическую сходимость по сравнению с квадратичной сходимостью метода Ньютона.

Это значит, что корни находятся быстрее, за меньшее число итераций.

Это я и решил проверить, доработав свою программу.

Уравнение используется одно и тоже.

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

F(z) = z**k -1

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

Я оставил несколько примеров из метода Ньютона также для метода Галлея:

Список примеров для метода Галлея.

Как и ожидалось, метод Галлея находит корни намного быстрее - на фракталах фон исчезает быстрее. Например, "Нейроны":

Метод Ньютона

Метод Галлея.

Или "Полёт":

Метод Ньютона.

Метод Галлея.

А вот и вариант "Чёрного квадрата" Казимира Малевича - только метод Галлея не научился так ровно закрашивать одним цветом :-)

Зелёный квадрат метода Галлея.

Кстати, добавил функциональность для управления границами области.

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

Кнопки управления областью (точнее, её границами).

Теперь стало намного удобнее.

Спасибо за внимание.