is_реклам:

пошук, категорії та ін. показати ▼

Басейни Ньютона в графіці

Басейни Ньютона в графіці
автор опубліковано

Області з фрактальними межами з’являються при наближенні коренів нелінійного рівняння за допомогою алгоритму Ньютона на комплексній площині.

Для знаходження комплексних коренів z=x+iy рівняння P_n(z)=0, де P_n(x) – алгебраїчний многочлен із дійсними коефіцієнтами, алгоритм методу Ньютона має класичний вигляд:

z_{k+1}=z_k-\frac{P_n(z_k)}{P'_n(z_k)}, \ \ \ k=0, 1, ..

Цей метод ґрунтується на ітеративній лінеаризації процесу. Метод Ньютона вперше був опублікований у 1669 р. Але обчислювалась не послідовність наближень, а послідовність многочленів. У 1690 р. Дж. Рафсон описав метод, використовуючи послідовні наближення, але також обмежуючи його застосування алгебраїчними многочленами. Тому його часто називають методом Ньютона–Рафсона. Як ітераційний метод розв’язування нелінійних рівнянь і систем двох рівнянь метод Ньютона у сучасному вигляді в 1740 р. сформулював Т.Сімпсон.

Метод Ньютона призначений для розв’язування нелінійних рівнянь, це ітераційний метод, для нього треба задати початкове значення z_0, і запустити ітераційний процес. Чим більше зроблено ітерацій, тим краще уточнено корінь рівняння. Для функції дійсної змінної метод Ньютона часто називають методом січних.

Знаходження комплексних коренів можна звести до розв’язування системи двох алгебраїчних рівнянь, якщо виділити дійсну і уявну частини функції P_n(z). Тоді P_n(x+iy)=f_1(x,y)+i f_2(x,y)=0 і одержимо систему нелінійних рівнянь вигляду

 f_1(x,y)=0,
f_2(x,y)=0.

Цікавим питанням є знаходження множини початкових значень для кожного з коренів, для яких метод Ньютона збіжний. Виявляється, що на межах цих областей початкових значень утворюються фрактали – нескінченні самоподібні структури. Оскільки Ньютон розвинув свій метод для алгебраїчних рівнянь, то фрактали такого типу називаються фракталами або басейнами Ньютона.

Наприклад, рівняння z^3-1=0, як відомо, має три корені. При виборі різних початкових значень, процес буде збігатися до різних коренів. Артур Келі поставив задачу опису цих областей притягання. І виявилося, що межі цих областей мають фрактальну структуру.
Ця задача належить до розділу комп’ютерної графіки, але ці надзвичайні фрактали були відкриті саме при застосуванні обчислювальних методів до розв’язування нелінійних рівнянь, що вкотре демонструє, наскільки близькі програмування графіки і чиста математика.
Для рівнянь z^3-1=0, z^4-1=0 та z^8-1=0 басейни Ньютона показані на рисунках. Для початкових значень із областей, зафарбованих темнішими кольорами, відповідає більша кількість ітерацій. Скільки на малюнку різних кольорів – стільки у нього коренів.

Фрактали, що утворюються для інших алгебраїчних рівнянь, можна переглянути в галереї Paul Bourke

Демонстраційну програму для рівняння z^k-a=0 для випадків k=3, a=1 і k=5, a=1, можна скачати, клікнувши на малюнку. Програма написана автором засобами мови Delphi.

при клацанні на зображення, можна скачати цю програму

при клацанні на зображення, можна скачати цю програму

Кольори точок першого та другого фракталів визначаються відповідно функціями

RGB((9*n mod 256),0,0) і RGB(0,0,(15*n mod 256)), де n – кількість ітерацій. Тому для початкових значень із областей, зафарбованих темнішими кольорами необхідна була більша кількість ітерацій.

Для подальшого обговорення застовування методу Ньютона до алгебраїчних рівнянь, програмування динамічних фракталів, та застосування числових методів в комп’ютерній графіці, пишіть в коментарях до даної статті, або скористайтесь формою звязку

схоже за тегами

1 коментар

  1. я писав для k=3, k=5, k=7, тут головне виразити рекурентне рівняння для наближенного обчислення

Залишити коментар:

Яндекс цитирования UA TOP Bloggers