Cardioïde / bourgeon principal

Un moyen de limiter les calculs est de trouver au préalable les points appartenant à la cardioïde et au bourgeon principal, c'est-à-dire au disque de centre (–1, 0) et de rayon 1/4. Ces points coûtent particulièrement cher en calculs, puisqu'ils appartiennent à l'ensemble de Mandelbrot, et nécessitent donc d'aller jusqu'au maximum d'itérations. Avant de passer un point de coordonnées ${\displaystyle x+iy}$ dans l’algorithme itératif, il faut donc vérifier :

• si ${\displaystyle x<p-2p^{2}+{\frac {1}{4}}}$ avec ${\displaystyle p={\sqrt {\left(x-{\frac {1}{4}}\right)^{2}+y^{2}}}}$alors le point appartient à la cardioïde, donc à l'ensemble de Mandelbrot ;
• si ${\displaystyle (x+1)^{2}+y^{2}<{\frac {1}{16}}}$alors le point appartient au disque de centre (–1, 0) et de rayon 1/4, c'est-à-dire au bourgeon principal, et donc à l'ensemble de Mandelbrot.

Les autres bourgeons n'ont pas de test équivalent, puisqu'ils ne sont pas parfaitement circulaires. Il est néanmoins possible de vérifier si un point appartient à un cercle que l'on sait inscrit dans un de ces bourgeons, permettant à la plupart des points de ces derniers de ne pas lancer l'algorithme itératif.

Algorithme par perturbation

Il est possible de reformuler l'équation principale, de manière à raisonner sur la différence d'évolution par rapport à un point voisin. Cette méthode permet de ramener ces différences ${\displaystyle \Delta _{n}}$ à une faible précision (vingtaine de chiffres significatifs), dans le domaine des unités de calcul en virgule flottante matérielles de l'ordinateur, qui sont beaucoup plus rapides que les bibliothèques d'arithmétique multiprécision qui ne sont pas autant accélérées matériellement. L'ensemble est ainsi calculé à partir d'un (ou plusieurs) points de référence, calculés de manière absolue.

Si on raisonne en absolu, les nombres mis en œuvre pour le calcul de l'ensemble peuvent atteindre des milliers de chiffres significatifs pour des grands niveaux de zoom, et s'accroissant davantage avec le zoom. Avec cet algorithme, la vitesse de calcul reste relativement constante selon le niveau de zoom, la vitesse de calcul dépendant plus de la complexité de la scène^[23].

Cet algorithme est à la base d'un des programmes de calcul le plus rapide de l'ensemble de Mandelbrot en 2017 : Kalles Fraktaler^[24].

Principe^[23] :

${\displaystyle X_{n+1}=X_{n}^{2}+X_{0}}$

${\displaystyle Y_{n+1}=Y_{n}^{2}+Y_{0}}$

${\displaystyle \Delta _{n}=Y_{n}-X_{n}}$

${\displaystyle {\begin{aligned}\Delta _{n+1}=Y_{n+1}-X_{n+1}&=(Y_{n}^{2}+Y_{0})-(X_{n}^{2}+X_{0})\\&=((X_{n}+\Delta _{n})^{2}+X_{0}+\Delta _{0})-(X_{n}^{2}+X_{0})\\&=(X_{n}^{2}+2X_{n}\Delta _{n}+\Delta _{n}^{2}+X_{0}+\Delta _{0})-(X_{n}^{2}+X_{0})\\&=2X_{n}\Delta _{n}+\Delta _{n}^{2}+\Delta _{0}\end{aligned}}}$

Tous les ${\displaystyle \Delta _{n}}$, calculés à partir des ${\displaystyle X_{n}}$ de référence mémorisés, ont une faible précision, permettant d'utiliser les unités de calcul en virgule flottante matérielles de l'ordinateur pour les opérations les plus nombreuses et coûteuses.

Le calcul peut encore être davantage optimisé en exprimant ${\displaystyle \Delta _{n}}$ en utilisant l'approximation^[23] :

${\displaystyle \Delta _{n}=A_{n}\Delta _{0}+B_{n}\Delta _{0}^{2}+C_{n}\Delta _{0}^{3}+o(\Delta _{0}^{4})}$

avec ${\displaystyle A_{n},B_{n},C_{n}}$ ne dépendant pas de ${\displaystyle \Delta _{n}}$, mais seulement de ${\displaystyle X_{n}}$ (série du point de référence à partir duquel on calcule les perturbations).

Donc, une fois calculés et mémorisés tous les ${\displaystyle A_{n},B_{n},C_{n}}$ pour le point de référence (${\displaystyle \Delta _{0}=0}$), on peut rechercher directement pour tout point voisin (en faisant varier ${\displaystyle \Delta _{0}}$), par recherche dichotomique, le ${\displaystyle \Delta _{n}}$ qui provoque la divergence de la suite (puisqu'on n'a pas besoin du ${\displaystyle \Delta _{n-1}}$ pour calculer ${\displaystyle \Delta _{n}}$) et le calcul d'un point se fait avec une complexité en temps ${\displaystyle O(\log {N})}$ au lieu de ${\displaystyle O(N)}$, ${\displaystyle N}$ étant le nombre maximum d'itérations^[25].