% Prove Mandelbrot set % % LaTeX doc: http://en.wikibooks.org/wiki/LaTeX % % Fut: Add 4D Mandelbrot % % v0.006, 2011/09/16 Budapest, TrueY % Add: Hiperkomplex, Algebrák % Add: New i, j, k vectors (italic, bold) % % v0.005, 2011/09/13 Budapest, TrueY % Add: png % Add: Lemma % % v0.004, 2011/09/08 Budapest, TrueY % Add: UTF-8. Use real Hungarian umlaut characters % Add: New sqrt with tail % Add: \Aeqref, \aeqref % % v0.003, 2011/08/20 Budapest, TrueY % Add: Start again % % v0.002, 2007/02/21, Budapest, TrueY % Add: Start again % % v0.001, 2006/01/14, Budapest, TrueY % Add: Mandelbrot proved, Julia not % Add: JAVA Applet % % v0.000, 2004/03/11, Budapest, TrueY % Add: Start work % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\tracingmacros=9 %\NeedsTexFormat{LaTeX2e} %fejlesztés alatt az első sor kell használni %\documentclass[a4paper, 11pt, magyar, draft, twocolumn]{article} \documentclass[a4paper, 11pt, magyar, twocolumn]{article} % Ide kell tenni a definíciót, különben a \Title rossz lesz \usepackage[utf8]{inputenc} % encoding of the input file %\usepackage[latin2]{inputenc} % encoding of the input file \newcommand{\Title}{Mandelbrot- és Júlia-halmazokról} \newcommand{\Author}{TrueY} \newcommand{\Version}{v0.005} \usepackage[T1]{fontenc} % elvalasztas jo magyar karakterekkel is %%%\usepackage[magyar]{babel} % Ez itt nem jó. Később kell definiálni! %\usepackage{t1enc} % elvalasztas jo magyar karakterekkel is \usepackage{xspace} % spaces after macros \usepackage{calc} % to do length calculations \usepackage{ifthen} % package for if-then-else constructions %\usepackage{latexsym} % symbols for diagrams \usepackage{amsmath} % Full math capability \usepackage{amssymb} % symbols for diagrams %\usepackage{amsthm} % Theorem styles %\usepackage{theorem} % Theorem styles \usepackage[thmmarks, standard]{ntheorem} % Theorem styles %\usepackage{subfigure} % subfigures \usepackage{fancyhdr} % Define headers and footers %\usepackage{afterpage} % to handle the float pages \newif\ifPDF \ifx\pdfoutput\undefinied\PDFfalse \else\ifnum\pdfoutput > 0\PDFtrue \else\PDFfalse \fi \fi \ifPDF %\usepackage[pdftex]{graphicx} \usepackage[pdftex]{graphicx, color} \usepackage[pdftex, bookmarks=false, %%%pdftoolbar=false, %%%pdfmenubar, pdffitwindow, %pdfpagemode=FullScreen, % Open Full Screen pdfpagemode=UseNone, %, pdfpagemode=None, pdfstartview=FitH %pdfwindowui=false, %pdfcenterwindow, colorlinks, linkcolor=red ]{hyperref} %\pdfimageresolution=288 \pdfimageresolution=300 \pdfcompresslevel=9 \else \usepackage[dvips]{graphicx} \usepackage[dvips]{hyperref} \fi \usepackage[magyar]{babel} % Ide kell tenni, kulonben a pdf elhal % Ehhez már kell a babel csomag! \ifPDF \hypersetup{ pdftitle={\Title}, pdfauthor={\Author}, pdfsubject={\Version}, pdfkeywords={Mandelbrot, Julia} } \fi \renewcommand{\headheight}{14pt} % Setting penalties for clubs and widows \clubpenalty=1000 % fattyusor - lap aljan \widowpenalty=1000 % ozvegy - lap tetejen \displaywidowpenalty=1000 %\overfullrule=6pt % show slug right to ugly lines \hyphenpenalty=0 % Hungarian likes the hyphenation \brokenpenalty=200 % Dont hyphen at the last line of page \doublehyphendemerits=0 % Hungarian likes the hyphenation. 2 elvalaszt 1 par-ban \finalhyphendemerits=0 % Hungarian likes the hyphenation. par utcso soraban %\renewcommand{\floatpagefraction}{.6} % instead of .5 %\renewcommand{\textfraction}{.15} % .2 %\renewcommand{\topfraction}{.8} % .7 %\renewcommand{\bottomfraction}{.5} % .3 \setcounter{topnumber}{3} % 2 \setcounter{bottomnumber}{1} % 1 \setcounter{totalnumber}{5} % 3 \setlength{\parskip}{1.5 ex plus 1 ex minus 0.5 ex} %\setlength{\parindent}{0 em} \fancypagestyle{myfancy}{ %declearing the modified fancy \lhead{\Title} %\chead{\Cat} \rhead{\Author} %\lfoot{left} %\cfoot{center} %\rfoot{\thepage} %\renewcommand{\headrulewidth}{0pt} %\renewcommand{\footrulewidth}{0pt} %\renewcommand{\plainheadrulewidth}{0pt} %\renewcommand{\plainfootrulewidth}{0pt}% } \pagestyle{myfancy} % %%%% Define commands %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % \A or \A[z_1] \newcommand{\A}[1][z]{\ensuremath{\left|#1\right|}} \newcommand{\FI}[1][]{ \ifthenelse{\equal{#1}{}} {\ensuremath{\varphi}} {\ensuremath{\varphi_#1}} } %\newcommand{\ii}[0]{\ensuremath{\mathbf{i}}} %\newcommand{\jj}[0]{\ensuremath{\mathbf{j}}} %\newcommand{\kk}[0]{\ensuremath{\mathbf{k}}} \newcommand{\ii}[0]{\ensuremath{\textbf{\emph{i}}}} \newcommand{\jj}[0]{\ensuremath{\textbf{\emph{j}}}} \newcommand{\kk}[0]{\ensuremath{\textbf{\emph{k}}}} \newcommand{\ef}[2][z]{\ensuremath{\left|#1\right| e^{\ii \FI[#2]}}} %generic/babel/magyar.ldf-bol ollózva! %3 betüsnek kell lennie, ezért az azr-te aze-nek írtam át és az eqref-t tettem bele \makeatletter \def\aeqref{\aze} \def\Aeqref{\Aze} \def\aze{a\@ifstar{\@aze}{\aze@}} \def\Aze{A\@ifstar{\@aze}{\aze@}} \def\aze@{\@ifnextchar ({\aze@@@}{\aze@@}} \def\aze@@#1{\@aze{#1}\nobreakspace\eqref{#1}} \def\aze@@@(#1{\@aze{#1}\nobreakspace(\eqref{#1}} \def\@aze#1{% \hun@tempadef{hun@r@#1}{r@#1}{}% \ifx\@tempa\empty \else \edef\@tempb{\noexpand\@@az\expandafter\@firstoftwo\@tempa\hbox!}% \@tempb \fi } \makeatother % % New definition of square root: % Src: http://commons.wikimedia.org/wiki/File:Latex_new_squareroot.png % % it renames \sqrt as \oldsqrt \let\oldsqrt\sqrt % it defines the new \sqrt in terms of the old one \def\sqrt{\mathpalette\DHLhksqrt} \def\DHLhksqrt#1#2{\setbox0=\hbox{$#1\oldsqrt{#2\,}$}\dimen0=\ht0 \advance\dimen0-0.2\ht0 \setbox2=\hbox{\vrule height\ht0 depth -\dimen0}% {\box0\lower0.4pt\box2}} % Állítás %http://en.wikibooks.org/wiki/LaTeX/Theorems \providecommand{\QED}{\ensuremath{\blacksquare}} \theoremstyle{change} \theoremseparator{:} \newtheorem{allitas}{Állítás}[subsection] \renewtheorem{lemma}{Lemma}[subsection] {\theorembodyfont{\upshape} \theoremsymbol{\QED} \renewtheorem*{proof}{Bizonyítás} % not numbered %\renewtheorem{proof}{Bizonyítás}[subsection]} % numbered by subsection } % %%%% Start document %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \begin{document} \phantomsection \title{\Title} \author{\href{mailto:qltura.truey@gmail.com?subject=Re:\%20Mandelbrot\%20docu}{\Author}} \date{\today} \maketitle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Bevezetés % \section{Bevezetés} % 1986-ben, amikor a Tudomány című újság, a Scientific American magyar kiadása indult, a címoldalán egy gyönyörű, színpompás ábra, egy \href{http://hu.wikipedia.org/wiki/Mandelbrot-halmaz}{Mandelbrot-halmaz} volt látható. %http://en.wikibooks.org/wiki/LaTeX/Importing_Graphics %\begin{figure}[htb] %\begin{figure} %\centering %\includegraphics[width=0.45\textwidth]{Mandelbrot_large.png} %%\includegraphics[width=70mm]{Mandelbrot_300.png} \includegraphics[width=70mm]{Mandelbrot_200.png} %\caption{Awesome Image} %\label{fig:awesome_image} %\end{figure} Rövid leírás következett az előállításának algoritmusáról. Az algoritmusban van egy lépés, ami azt állítja, hogy egy komplex szám bizonyosan nem eleme a Mandelbrot-halmaznak, ha a belőle képzett rekurzív sor bármely elemének nagysága nagyobb, mint 2. Rögvest felmerült bennem a kérdés, hogy miért pont 2? Később olvastam Roger Penrose egy könyvét (l. \cite[147.~o. alja]{Penrose1993}), amelyben -- sok mással egyetemben -- foglalkozik a Mandelbrot-halmazzal is. Ott azt állítja, hogy ez a korlát $1+\sqrt{2}$. Ugyanebben a könyvben a 2-es korlát is említésre kerül. Ismét felmerül hát a kérdés, hogy mennyi és miért annyi, amennyi? Ebben a cikkben foglalom össze annak bizonyítását, hogy miért 2 ez a korlát (l. \aref{sec:proof}.~fejezetben). Több esetben is írtam Mandelbrot-halmazt generáló programot. A legelsőt Sinclair QL-re (emlékszik valaki erre a szuper gépre?). Később, 2001-ben az egyik kollégám (Amorphka) írt Intel 80386/387 processzorra, DOS alá egy programot assembler nyelven, ami az FPU felhasználásával számolta és rajzolta ki a Mandelbrot-halmazt. A lefordított com file hossza 191 byte volt. Látható volt, hogy ennél lehet kisebb kódot is írni. Ebből végül is sikerült egy 100 byte-os programot készíteni (l. \aref{sec:asm}.~fejezetben). Mind e közben az is felmerült, hogy a számításokat egy nyomtató is elvégezheti. Erre a PostScript megfelelő nyelvnek tűnt. 2004-ben munkám során beleolvastam a PostScript programozási nyelv leírásába (l. \cite{PS1985}) és kb. a 80. oldalig kellett eljutnom, hogy 20 sorban megírjam a programot (l. \aref{sec:postscript}.~fejezetben). 2006-ban egy JAVA Applet-et is készítettem, amely a Mandelbrot- és Júlia-halmazokat rajzolja ki. Sajnos az évek során ez a meglehetősen egyszerű Applet eltűnt. De nem is nagy kár érte. Talán egyszer majd újra írom, de a neccen annyi Mandelbrot rajzoló program akad, hogy teljesen felesleges még egy lassú JAVA-s is. Erőimet inkább a GTK-s, GMP-s verzióra fókuszálom. 2007-ben, egy megfázás alkalmával ismét elkezdtem írni ezt a dokumentumot és akkor jutott eszembe, hogy a Mandelbrot- és Júlia-halmazokat ki lehetne terjeszteni Hiperkomplex számokra is (l. \cite{Kantor1985}). Ekkor az eredeti komplex halmaz csak egy 2 dimenziós alterét jelenti a tetszőleges n dimenziós hiperkomplex halmazoknak. Ezekről az kiterjesztett halmazokról \aref{sec:mandelX}.~fejezetben fogok néhány szót ejteni. Nagyjából ennyi a története ennek a dokumentumnak. Remélem néhányan hasznosnak találják! Jó olvasást! Ha bármilyen heJe sírási, sajtóhUbát, vagy levezetési problémát talál, kérem jelezze azt \href{mailto:qltura.truey@gmail.com?subject=Re:\%20Madelbrot\%20docu%20HIBA}{nekem}! \section{Komplex számok} % Azoknak, akik nem ismerősek a komplex számok világában igyekszem röviden bemutatni, hogy hogyan is képződnek (l. \cite{Kantor1985}, \cite{WikiHU_komplex}). A valós számok halmazán nem megoldható az $x^2 + 1 = 0$ egyenlet, de a \[\sqrt{-1}=\ii\] jelölés bevezetésével szimbolikusan megoldhatóvá válik. Nyilvánvaló, hogy $\ii^2=-1$, $\ii^3=-\ii$, $\ii^4=1$, $\ii^5=\ii$ stb. Ezzel a jelöléssel képezhetünk egy komplex számot. Egy tetszőleges komplex számot jelöljük $z$-vel, amely két részből áll: egy valós $(a)$, és egy képzetes részből $(b\ii)$ \[z=a+b\ii.\] % Ha a komplex számokat egy derékszögű koordináta-rendszerben ábrázoljuk, akkor egy vektort kapunk. Az abszcissza tengelyre mérjük fel a valós és az ordináta tengelyre a képzetes részt. A vektor és az abszcissza pozitív félegyenese által bezárt szöget jelölje $\FI$ (úgy, hogy a $\FI=+90^{\circ}$ az ordináta tengely pozitív félegyenese irányába mutat), a komplex vektor hosszát pedig jelölje $\A=\sqrt{a^2+b^2}$. Ekkor így is felírhatjuk a komplex számot: \[z = \A\cos{\FI} + \ii\A\sin{\FI} = \ef{}.\] Két komplex szám összege: % \begin{gather*} z_1+z_2=(a_1+b_1\ii)+(a_2+b_2\ii)=\\% =(a_1+a_2)+(b_1+b_2)\ii , \end{gather*} % szorzata: % \begin{gather*} z_1 z_2=(a_1+b_1\ii)(a_2+b_2\ii)=\\% =a_1 a_2 + a_1 b_2\ii + b_1 a_2\ii + b_1 b_2\ii\ii =\\% =a_1 a_2 - b_1 b_2 + (a_1 b_2+b_1 a_2)\ii =\\% =\ef[z_1]{1} \ef[z_2]{2}=\\% =\A[z_1]\A[z_2] e^{\ii (\FI[1] + \FI[2])}. \end{gather*} A komplex számokkal végzett összeadás és szorzás kommutatív és asszociatív. A szorzás pedig disztributív az összeadásra nézve. Bevezetjük a konjugálás műveletét: % \[\overline z=a -b\ii = \A e^{-\ii \FI}.\] % Ekkor az alábbi összefüggései igazak: % \begin{gather*} \overline{z_1+z_2}=\overline{z_1}+\overline{z_2},\\% \overline{z_1 z_2}=\overline{z_1}\:\overline{z_2},\\% z\overline z=a^2+b^2={\A}^2,\\% z+\overline z = 2 a,\\% z-\overline z = 2b\ii. \end{gather*} % Még egy hasznos jelölést vezetünk be: $Re(z)=a=\A\cos{\FI}$, amire nyilvánvalóan igaz, hogy % \begin{gather} \label{eq:Re} -\A \le Re(z) \le \A. \end{gather} % % Mandelbrot def % \section{Mandelbrot-halmaz definíciója} Most már minden szükségeset tudunk a komplex számokról és a velük végezhető műveletekről. Definiáljuk a Mandelbrot-halmazt. A halmazt jelöljük $\mathbb{M}$-mel. Vegyünk egy tetszőleges $z_0$ komplex számot és képezzük az alábbi rekurzív komplex sorozatot minden $n\ge 0$ egész számra. % \begin{gather}\label{eq:Mandelbrot} z_{n+1}=z_n^2+z_0. \end{gather} % Egy $z_0$ komplex szám eleme a Mandelbrot-halmaznak, ha a $z_n$ sorozat korlátos, azaz $z_0 \in \mathbb{M}$, ha $\exists P>0$, amelyre igaz, hogy $\forall n \ge 0$, esetén $\A[z_n]0$, amelyre igaz, hogy $\forall n \ge 0$, esetén $\A[z_n] 0 (N \in \mathbb{N})$, amelyre igaz, hogy $\A[z_N] > 2$, akkor \[\lim_{n \to \infty} \A[z_n] = \infty,\] azaz $z_0 \notin \mathbb{M}$. Két lépésben történik a bizonyítás. Az elsőben a $\A[z_0] > 2$ esetre bizonyítom (1-3. lépés) és utána a $\A[z_0] \le 2$ esetre. Egy megjegyzés: $z_0 = -2$ kiindulási értékkel a $\forall n > 0$-ra a $z_n = 2$ konstans elemű sorozat képződik. Tehát $-2 \in \mathbb{M}$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Bizonyítás Mandelbrot 1. % \begin{allitas} \label{all:M1} $\forall \A[z_0]>2$ esetén $\forall n>0$-ra $\A[z_n] > \A[z_0]$. \end{allitas} \begin{proof} A bizonyítás teljes indukcióval fog történni. n=1 esetre könnyen belátható a $\A[z_1] > \A[z_0]$ egyenlőtlenség. \Aeqref{eq:Abs_p1} egyenlőtlenség alkalmazhatósági feltétele igaz (mivel $\A[z_0]^2 > \A[z_0] > 2$), tehát a vizsgált egyenlőtlenség bal oldalán álló kifejezést alulról becsülhetjük. Azaz $\A[z_1] \ge \A[z_0]^2 - \A[z_0] > \A[z_0]$. A jobb oldali egyenlőtlenséget átrendezve $\A[z_0]^2 > 2\A[z_0]$. Egyszerűsítve \A[z_0]-lal, $\A[z_0] > 2$, ez pedig a kiindulási feltétel, azaz minden esetben igaz. Tegyük fel, hogy n-re igaz, azaz $\A[z_n] > \A[z_0]$. Vizsgáljuk meg, hogy n+1 esetre is igaz-e, azaz %$\A[z_{n+1}] \stackrel{?}{>} \A[z_0]$. % nem szép, nagy sorköz lesz $\A[z_{n+1}] > \A[z_0]$. \Aeqref{eq:Abs_p1} egyenlőtlenség alkalmazhatósági feltétele igaz ($\A[z_n]^2 > \A[z_0]$) , ezért a bizonyítandó sorozat elem alulról becsülhető: $\A[z_{n+1}] \ge \A[z_n]^2 - \A[z_0] > \A[z_0]$. A jobb oldali egyenlőtlenség átrendezés után $\A[z_n]^2 > 2\A[z_0]$. Ez nyilvánvalóan igaz, mivel $\A[z_n] > \A[z_0] > 2$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Bizonyítás Mandelbrot 2. % \begin{allitas} \label{all:M2} $\forall \A[z_0] > 2$ esetén $\forall n > 0$-ra $\A[z_{n+1}] > \A[z_n]$. \end{allitas} \begin{proof} \Aeqref{eq:Abs_p1} egyenlőtlenség alkalmazhatósági feltétele igaz , ezért a bizonyítandó egyenlőtlenség bal oldalát alulról becsülhetjük: $\A[z_{n+1}] \ge \A[z_n]^2 - \A[z_0] > \A[z_n]$. A jobb oldali egyenlőtlenséget átrendezve $\A[z_n]^2 > \A[z_n] + \A[z_0]$. \Aref{all:M1}. állítás miatt a jobb oldalt felülről becsüljük, ha \A[z_0], helyett \A[z_n]-et helyettesítünk. Ekkor a következő egyenlőtlenséget kapjuk: $\A[z_n]^2 > 2\A[z_n]$, azaz $\A[z_n] > 2$. Ez pedig a $\A[z_n] > \A[z_0] > 2$ miatt nyilvánvalóan igaz. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Bizonyítás Mandelbrot 3. % \begin{allitas} \label{all:M3} $\forall \A[z_0] > 2$ esetén $\forall n > 0$-ra $\A[z_{n+1}] - \A[z_n] \ge 2(\A[z_0] - 2)$, ami minden esetben $>0$. \end{allitas} \begin{proof} \Aeqref{eq:Abs_p1} egyenlőtlenség alkalmazhatósági feltétele igaz, ezért a bizonyítandó egyenlőtlenség bal oldalát alulról becsülhetjük: $\A[z_{n+1}] - \A[z_n] \ge \A[z_n]^2 - \A[z_0] - \A[z_n] \ge 2(\A[z_0] - 2)$. A jobb oldali egyenlőtlenség bal oldala alulról becsülhető, ha \A[z_0] helyére \A[z_n]-et helyettesítünk, azaz $\A[z_n]^2 - 2\A[z_n] = \A[z_n](\A[z_n] - 2) \ge 2(\A[z_0] - 2)$. Ez nyilvánvalóan igaz, mivel $\A[z_n] > \A[z_0] > 2$. \end{proof} \Aref{all:M3}. állításból következik, hogy a sorozat minden két szomszédos eleme közötti különbség alulról becsülhető egy nullától különböző pozitív számmal. Tehát \begin{gather} \label{eq:lim_gt_2} \forall \A[z_0] > 2 \textrm{-re} \lim_{n \to \infty} \A[z_n] = \infty. \end{gather} Most pedig lássuk a bizonyítást arra az esetre, amikor $\A[z_0] \le 2$ és $\exists N > 0 (N \in \mathbb{N}) \textrm{-re} \A[z_N] > 2$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Bizonyítás Mandelbrot 4. % \begin{allitas} \label{all:M4} Ha $\A[z_0] \le 2$ és $\exists N > 0$, amelyre $\A[z_N] > 2$ , akkor $\forall n \ge N$-re $\A[z_n] > 2$. \end{allitas} \begin{proof} A bizonyítás teljes indukcióval fog történni. $n=N$-re tehát $\A[z_n] > 2$. $n=N+1$ esetre könnyen belátható. \Aeqref{eq:Abs_p1} egyenlőtlenség alkalmazhatósági feltétele igaz $(\A[z_N]^2 > 4 > \A[z_0])$, ezért az $\A[z_{N+1}] \ge \A[z_N]^2 - \A[z_0] > 2$ egyenlőtlenség írható fel. A jobb oldali egyenlőtlenséget átrendezve kapjuk $\A[z_N]^2 > 2 + \A[z_0]$. Mivel $\A[z_N] > 2 \ge \A[z_0]$, ezért ez nyilvánvalóan igaz. Ebből következik, hogy minden $n > N$-re is igaz. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Bizonyítás Mandelbrot 5. % \begin{allitas} \label{all:M5} Ha $\A[z_0] \le 2$ és $\exists N > 0$, amelyre $\A[z_N] > 2$, akkor $\forall n \ge N$-re $\A[z_{n+1}] > \A[z_n]$. \end{allitas} \begin{proof} \Aeqref{eq:Abs_p1} egyenlőtlenség alkalmazhatósági feltétele igaz, ezért a bizonyítandó egyenlőtlenség bal oldalát alulról becsülhetjük, azaz a $\A[z_{n+1}] \ge \A[z_n]^2 - \A[z_0] > \A[z_n]$ egyenlőtlenség írható fel. A jobb oldali egyenlőtlenséget átrendezve kapjuk, hogy $\A[z_n]^2 > \A[z_n] + \A[z_0]$. Mivel $\A[z_n] > 2 \ge \A[z_0]$, ezért ez nyilvánvalóan igaz. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Bizonyítás Mandelbrot 6. % \begin{allitas} \label{all:M6} Ha $\A[z_0] \le 2$ és $\exists N > 0$, amelyre $\A[z_N] > 2$, akkor $\forall n \ge N$-re $\A[z_{n+1}] - \A[z_n] > 2(\A[z_N] - 2)$. \end{allitas} \begin{proof} \Aeqref{eq:Abs_p1} egyenlőtlenség alkalmazhatósági feltétele igaz, ezért a bizonyítandó egyenlőtlenség bal oldalán álló kifejezést alulról becsülhetjük: $\A[z_{n+1}] - \A[z_n] \ge \A[z_n]^2 - \A[z_0] - \A[z_n] > 2(\A[z_N] - 2)$ egyenlőtlenség írható fel. A jobb oldali egyenlőtlenséget alulról tudjuk becsülni, ha \A[z_0] helyére \A[z_n]-et helyettesítünk. $\A[z_n]^2 - 2\A[z_n] = \A[z_n](\A[z_n] - 2) > 2(\A[z_N] - 2)$ Mivel $\A[z_n] > \A[z_N] > 2$, ezért ez igaz. \end{proof} \Aref{all:M6}. állításból következik, hogy ha valamely $\A[z_0] \le 2$-re $\exists N>0$, amelyre igaz, hogy $\A[z_N] > 2$, akkor % \begin{gather} \label{eq:lim_le_2} \lim_{n \to \infty} \A[z_n] = \infty. \end{gather} % \Aeqref{eq:lim_gt_2} és \aeqref{eq:lim_le_2} egyenletek alapján elmondható, hogy ha egy sorozat tetszőleges elemére igaz, hogy $\A[z_n] > 2$, akkor biztos, hogy az ehhez a sorozathoz tartozó $z_0 \notin \mathbb{M}$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Bizonyítás: Julia % \subsection{Júlia-halmaz korlátossága} Ha $\A[c] \le 2$, akkor a bizonyítás megegyezik a Mandelbrot-halmaznál látott \ref{all:M4}., \ref{all:M5}. és \ref{all:M6}. állítások lépéseivel ($z_0$-at $c$-vel való helyettesítés után). Azt várhatnánk, hogy $\A[c] > 2$ esetén egyetlen $z_0$-ra sem lesz korlátos a sorozat. Furcsa mód ez nem igaz! % % Bizonyítás: Julia 1 % \begin{allitas} \label{all:J1} $\forall c$ komplex számhoz létezik $z_0$ komplex szám, amelyre igaz, hogy $z_0 \in \mathbb{J}_c$. \end{allitas} \begin{proof} Elegendő egyetlen ilyen számot találnunk a bizonyításhoz. Keressük azt a $z_0$ komplex számot, amelyre $z_1 = z_0$, azaz $z_0^2 + c = z_0$. Ekkor $\forall n>0$-ra igaz, hogy $z_n = z_1 = z_0^2 + c$, azaz a sorozat korlátos. Nyilvánvaló, hogy ha $z_0$-ra igaz, akkor $-z_0$-ra is igaz lesz az egyenlet. Tehát meg kell oldanunk $z_0^2 + c = \pm z_0$ egyenletet. Átrendezve $z_0^2 \mp z_0 + c = 0$. \[ z_{0_{1,2,3,4}} = \frac{\pm 1 \pm \sqrt{1 - 4 c}}{2} \] \end{proof} Feltehetjük az a kérdést is, hogy létezik-e olyan korlát \A[z_n]-re, amelynél nagyobb sorozat tagnál a sorozat többi eleme biztosan minden határon túl nő. A \A[c] korlát viszonylag könnyen bizonyítható \aref{all:M1}. - \ref{all:M3} analógiájára. \Aref{all:J1}. állításból kiindulva vizsgáljuk meg a \[ \frac{1 + \sqrt{1 + 4 \A[c]}}{2} \] korlátot. % % Bizonyítás: Julia 2 % \begin{allitas} Ha $\A[c] > 2$ és $\exists N > 0$, amelyre $\A[z_N] > \frac{1}{2} + \sqrt{\frac{1}{4} + \A[c]}$, akkor $\A[z_{N+1}] > \A[z_N]$. \end{allitas} \begin{proof} Mivel $\A[z_N] > \sqrt{\A[c]}$, ezért alkalmazható \aeqref{eq:Abs_p1} egyenlőtlenség a bizonyítandó egyenlőtlenség bal oldalának alul becslésére. $\A[z_{N+1}] \ge \A[z_N]^2 - \A[c] > \A[z_N]$. A jobb oldali egyenlőtlenséget átrendezve kapjuk, hogy igaz, ha $\A[z_N]^2 - \A[z_N] - \A[c] > 0$, azaz $\A[z_N]_{1,2} = \frac{1 \pm \sqrt{1 + 4 \A[c]}}{2}$. Csak a pozitív megoldás a helyes, ezért adódik az állítás feltétele $\A[z_N] > \frac{1}{2} + \sqrt{\frac{1}{4} + \A[c]}$. \end{proof} Mivel $\forall n > N$-re az előző állítás kiindulási feltételei igazak, ezért ha átlépjük ezt a korlátot, akkor szigorúan monoton növekvő sorozatot kapunk. % % Bizonyítás: Julia 3 % \begin{allitas} \label{all:J3} Ha $\A[c] > 2$ és $\exists N > 0$, amelyre $\A[z_N] > \frac{1}{2} + \sqrt{\frac{1}{4} + \A[c]}$, akkor $\forall n > N$-re $\A[z_{n+1}] - \A[z_n] > \A[z_N](\A[z_N] - 1) -\A[c]$. \end{allitas} \begin{proof} Mivel $\forall n > N$-re $\A[z_n] > \sqrt{\A[c]}$, ezért alkalmazható \aeqref{eq:Abs_p1} egyenlőtlenség a bizonyítandó egyenlőtlenség bal oldalának alulról történő becslésére. \begin{gather} \A[z_{n+1}] - \A[z_n] \ge \A[z_n]^2 - \A[c] - \A[z_n] =\nonumber\\% \A[z_n](\A[z_n] - 1) - \A[c]. \label{eq:J3} \end{gather} Mivel \A[z_n] szigorúan monoton növekvő sorozat, ezért \aeqref{eq:J3} egyenlőtlenség szerint a szomszédos elemek különbségeiből képzett sorozat is szigorúan monoton sorozatot alkot. Ennek nyilvánvaló alsó korlátja $\A[z_N](\A[z_N] - 1) - \A[c]$. \end{proof} \Aref{all:J3} állításból pedig az következik, hogy maga a sorozat minden határon túl nő, azaz ha $\A[c] > 2$ és $\exists N > 0$, amelyre $\A[z_N] > \frac{1}{2} + \sqrt{\frac{1}{4} + \A[c]}$, akkor \[\lim_{n \to \infty} \A[z_n] = \infty.\] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Általános % \section{Általános megjegyzések} \label{sec:other} \subsection{Mandelbrot-halmaz tengelyesen szimmetrikus} \begin{allitas} Ha $z_0 \in \mathbb{M}$, akkor $\overline{z_0} \in \mathbb{M}$, azaz a Mandelbrot-halmaz szimmetrikus a valós tengelyre. \end{allitas} \begin{proof} Definíció alapján $z_1 = z_0^2 + z_0$, ekkor ha $\overline{z_0}$-ból kiindulva $z'_1 = \overline{z_0}^2 + \overline{z_0} = \overline{z_0^2} + \overline{z_0} = \overline{z_0^2 + z_0} = \overline{z_1}$. Teljes indukcióval pedig könnyű belátni, hogy ez bármely $n$-re is igaz. \end{proof} \subsection{Júlia-halmazok centrálisan szimmetrikusak} \begin{allitas} Ha $z_0 \in \mathbb{J}_c$, akkor $-z_0 \in \mathbb{J}_c$, azaz minden Júlia-halmaz origóra szimmetrikus. \end{allitas} \begin{proof} Helyettesítsük be $-z_0$-at a Júlia-halmazt definiáló sorozatba, azaz $z'_1 = (-z_0)^2 + c = z_0^2 + c = z_1$. A $-z_0$-val induló sorozat összes többi eleme ugyanaz, mint a $z_0$-lal induló sorozat. \end{proof} \subsection{Minden $\mathbb{J}_c$ Júlia-halmaz és $\mathbb{J}_{\overline{c}}$ párja tengelyesen szimmetrikusak} \begin{allitas} Ha $z_0 \in \mathbb{J}_c$, akkor $\overline{z_0} \in \mathbb{J}_{\overline{c}}$ , azaz minden $c$-vel képzett Júlia-halmaznak van egy valós tengelyre szimmetrikus párja. \end{allitas} \begin{proof} Vizsgáljuk meg a $z'_1 = \overline{z_0}^2 + \overline{c}$ elemet. A konjugáltakra igaz azonosságok felhasználásával könnyen belátható, hogy $z'_1 = \overline{z_0}^2 + \overline{c} = \overline{z_0^2} + \overline{c} = \overline{z_0^2 + c} = \overline{z_1}$. Tegyük fel, hogy valamely $n>N$-re igaz, hogy $z'_n = \overline{z_n}$. Ekkor $z'_{n+1} = {z'}_{n}^2 + \overline{c} = \overline{z_n}^2 + \overline{c} = \overline{z_n^2} + \overline{c} = \overline{z_n^2 + c} = \overline{z_{n+1}}$. \end{proof} \section{Assembly program} \label{sec:asm} A program legutolsó verziója sajnos elkallódott, de a 101 byte-os verziónak a forrása megtekinthető az internet egy kies bugyrában. \href{http://qltura.blog.hu/2009/09/09/hajtek_mandelbrot_assembly_ben}{Mandelbrot halmaz kirajzolása x86 Assemblerben} \section{PostScript program} \label{sec:postscript} Engedjük, hadd számoljon a nyomtató. \href{http://qltura.blog.hu/2009/03/31/hajtek_postscript}{Mandelbrot halmaz kirajzolása PostScript-ben} \section{Mandelbrot- és Júlia halmazok általánosítása} \label{sec:mandelX} \subsection{Egyéb rekurzív függvények} Az egyik kézenfekvő megoldás, hogy más rekurzív sorozatot választunk (\cite{WikiEN}, \cite{WikiHU}). Ilyen lehet a $z_{n+1} = z_n^d + c$, ahol $d$ (például) egy egész szám. Esetleg $z_{n+1} = z_n^3 + 3kz_n + c$. Használhatunk egyén komplex argumentumú függvényeket is ($sin(z), log(z)$ stb.). Általában vegyünk egy $c$ komplex paramétertől függő függvénycsaládot. Ekkor az általánosított Mandelbrot- és Júlia-halmazokhoz jutunk. \[z_{n+1} = f_c(z_n)\] Ha $c$ a változó és $z_0 = c$ a rekurzió indító eleme, akkor egy Mandelbrot-halmazt kapunk. Ha $c$ egy konstans és $z_0$ a változó, akkor pedig egy Júlia-halmazt \footnote{forrás: \href{http://hu.wikipedia.org/wiki/Mandelbrot-halmaz\#.C3.81ltal.C3.A1nos.C3.ADt.C3.A1sai}{hu.wikipedia.org}}. \subsection{Egyéb számrendszerek} A komplex számok képzésénél a szorzást úgy definiáltuk, hogy $\ii\ii = -1$. De lehetne tetszőleges $\ii\ii = a + b\ii$ alakú is. Igazolható, hogy az általános definíció 3 féle eltérő rendszerhez vezet: \begin{align*} \ii\ii &= -1 - \text{komplex számok}\\ \ii\ii &= 0 - \text{Study-féle számok}\\ \ii\ii &= 1 - \text{hiperbolikus komplex számok} \end{align*} \subsection{Hiperkomplex számok} A komplex számokat kiterjeszthetjük egy újabb szimbolum hozzáadásával. Ekkor az alábbi alakú számot kapjuk: \[z = a + b\ii + c\jj.\] Az összeadás és a valós számmal való szorzás a szokásos alakú. A hiperkomplex számok szorzásánál meg kell adnunk a szimbolumok szorzásának eredményét \begin{align*} \ii\ii &= a_{ii} + b_{ii}\ii + c_{ii}\jj\\ \ii\jj &= a_{ij} + b_{ij}\ii + c_{ij}\jj\\ \jj\ii &= a_{ji} + b_{ji}\ii + c_{ji}\jj\\ \jj\jj &= a_{jj} + b_{jj}\ii + c_{jj}\jj \end{align*} Általános esetben egy $n$ képzetes tagból álló hiperkomplex szám \[z = a_0 + \sum\limits_{j=1}^n a_j\ii_j,\] és definiálni kell a szorzótáblát is. Minden $k, l \in \{1,\dots,n\}$-re \[\ii_k\ii_l = p_{kl,0} + \sum\limits_{j=1}^n p_{kl,j}\ii_j.\] Két kitüntetett hiperkomplex rendszer van. Az egyik a kvaterniók. \begin{align*} z &= a + b\ii + c\jj + d\kk \text{, ahol}\\ \ii^2 &= \jj^2 = \kk^2 = -1 \text{ és}\\ \ii\jj &= -\jj\ii = \kk,\\ \jj\kk &= -\kk\jj = \ii,\\ \kk\ii &= -\ii\kk = \jj. \end{align*} A másik a Cayley-számok. Itt 7 elemből áll a képzetes rész. Megjegyzés: Igazolható, hogy csak a valós számok, komplex számok, kvaterniók és Cayley-számok halmazán végezhető el az osztás művelete (\cite{Kantor1985}). \subsection{Algebrák} Általános esetben egy $n$ dimenziós algebrában értelmezhető számot jelölje \[z = \sum\limits_{j=1}^n a_j\ii_j,\] Az algebrákban csak az összeadás, valós számmal való szorzás, illetve két szám szorzása van definiálva. A szorzáshoz definiálni kell a szorzótáblát. Minden $k, l \in \{1,...,n\}$-hoz tartozó szimbolumra \[\ii_k\ii_l = \sum\limits_{j=1}^n p_{kl,j}\ii_j.\] Ennyi pont elegendő a polinomiális Mandelbrot- és Júlia-halmazok képzéséhez. A hiperkomplex számok az algebrák egy speciális részosztálya. Ezek az úgynevezett egységelemes algebrák. Ezekben létezik egy egységelem (jelölje ez $\ii_1$), amelykre igaz, hogy minden $j \in \{2, \dots, n\}$-re $\ii_1\ii_j = \ii_j\ii_1 = \ii_j$. A hiperkomplex számokról és az algebrákról bővebben a \cite{Kantor1985}-ban olvashatunk. Természetesen minden választott algebrához külön meg kell találni, hogy egy adott elem mikor biztosan nem eleme, vagy mikor biztosan eleme az adott halmaznak. \begin{thebibliography}{00} \bibitem{Kantor1985}Kantor, Iszaj Lvovics - Szolodovnyikov, Alexandr Szamuilovics: \emph{Hiperkomplex számok}, Gondolat, Budapest, 1985 (\href{http://www.antikvarium.hu/ant/book.php?konyv-cim=hiperkomplex-szamok&ID=324078}{antikvarium.hu}) \bibitem{Penrose1993}Penrose, Roger: \emph{A császár új elméje - Számítógépek, gondolkodás és a fizika törvényei}, Akadémiai Kiadó, Budapest, 1993 (\href{http://www.antikvarium.hu/ant/book.php?konyv-cim=a-csaszar-uj-elmeje&ID=121626}{antikvarium.hu}) \bibitem{PS1985} \emph{PostScript Language Tutorial and Cookbook}, Adobe Systems Incorporated, 1985 (\href{http://www-cdf.fnal.gov/offline/PostScript/BLUEBOOK.PDF}{BlueBook.pdf}) \bibitem{WikiHU_komplex} \emph{Komplex számok}, \href{http://hu.wikipedia.org/wiki/Komplex_sz%C3%A1mok}{hu.wikipedia.org} \bibitem{WikiEN} \emph{Mandelbrot set}, \href{http://en.wikipedia.org/wiki/Mandelbrot_set}{en.wikipedia.org} \bibitem{WikiHU} \emph{Mandelbrot-halmaz}, \href{http://hu.wikipedia.org/wiki/Mandelbrot-halmaz}{hu.wikipedia.org} \end{thebibliography} \end{document} \endinput