\documentclass[a4paper]{article}
\usepackage[dutch]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}
\newtheorem{stelling}{Stelling}[section]
\newtheorem{gevolg}{Gevolg}[stelling]
\newtheorem{lemma}{Lemma}[stelling]
\newtheorem{definitie}{Definitie}[section]
\newtheorem{voorbeeld}{Voorbeeld}[section]
\newtheorem{opmerking}{Opmerking}[section]
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Zn}{\mathbb{Z}_n}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\abs}[1]{\lvert #1\rvert}
\newcommand{\p}[1]{\left( #1 \right)}
\newcommand{\pmM}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)}
\newcommand{\pmMr}[1]{\left(\begin{smallmatrix*}[r] #1 \end{smallmatrix*}\right)}
\newcommand{\pM}[1]{\left(\begin{matrix} #1 \end{matrix}\right)}
\newcommand{\pMr}[1]{\left(\begin{matrix*}[r] #1 \end{matrix*}\right)}
\newcommand{\dmM}[1]{\left|\begin{smallmatrix} #1 \end{smallmatrix}\right|)}
\newcommand{\dmMr}[1]{\left|\begin{smallmatrix*}[r] #1 \end{smallmatrix*}\right|)}
\newcommand{\dM}[1]{\left|\begin{matrix} #1 \end{matrix}\right|}
\newcommand{\dMr}[1]{\left|\begin{matrix*}[r] #1 \end{matrix*}\right|}
\title{The incredible shrinking point chain}
\author{naar een idee van Dirk Danckaert}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
\noindent Wiskundecollega Pedro Tytgat ontdekte onlangs een merkwaardige applet op het internet. Op http://functionspace.org/topic/1638/opinion/7591 vond hij tussen een hele serie animated gifs een applet voor de krimpende puntenketting die meetkundig gezien niet veel meer doet dan het berekenen van het midden van een lijnstuk. Deze applet viel niet alleen op door haar meetkundige schoonheid maar ook door een korte discussie over een mogelijke verklaring via dominante eigenwaarden en eigenvectoren.De aangekondigde verklaring ontbrak echter op deze site. Korte tijd na de ontdekking van de stelling van de krimpende puntenketting kwam er een compacte maar ge\"inspireerde analyse van Dirk Danckaert. In dit verslag probeer ik zijn idee\"en iets breedvoeriger uit te schrijven.
\end{abstract}
\section{Probleemstelling}
We kiezen een willekeurige gesloten ketting van $k$ punten $(A_i)_{i=1 \cdots k}$ in het vlak. Als we de waarden van de index in $\Z_k$ nemen dan kan $i$ een willekeurige waarde in $\Z$ aannemen.Vervolgens nemen we de afbeelding $A_i \mapsto (A_i + A_{i+1})/2$ die elk punt vervangt door het midden van het volgende lijnstuk. Zo ontstaat er een nieuwe puntenketting.
\begin{figure} [h]
\centering
\includegraphics[width=0.8\textwidth]{fig4.jpg}
\caption{Een willekeurige gesloten ketting met 10 punten}
\end{figure}
Aanvankelijk lijkt er geen regelmaat te zitten in de twee puntenkettingen. Maar als we deze afbeelding een groot aantal keer iteratief toepassen, lijkt de puntenketting mooi aan te sluiten bij een ellips.
\begin{figure} [h]
\centering
\includegraphics[width=0.9\textwidth]{fig1.jpg}
\caption{Configuratie na 30 iteratiestappen}
\end{figure}
In dit artikel tonen we aan dat elke ketting bij benadering op een ellips komt te liggen na $n$ iteratiestappen met $n \to \infty$. De ori\"entatie van de ellips (en ook de verhouding van haar assen) zal afhangen van de positie van de hoekpunten van de oorspronkelijke veelhoek. De ellips zal na verloop van tijd per iteratiestap inkrimpen met een vaste inkrimpingsfactor. Deze factor hangt enkel af van het aantal punten in de ketting en niet van hun positie. We tonen eveneens aan dat de puntenketting altijd ineenkrimpt tot een puntketting in het zwaartepunt van de oorspronkelijke puntenverzameling.
\section{Algebra\"ische structuur}
De lineaire afbeelding $A_i \mapsto (A_i + A_{i+1})/2$ doet aanvoelen dat we minstens een vectorruimtestructuur nodig hebben om dit probleem op te lossen. Vermits de gegeven punten in een vlak liggen, kunnen we opteren voor een vectorruimte met dimensie 2. Echter, ook indien de punten $(A_i)_{i=1 \cdots k}$ willekeurig gekozen worden in een driedimensionale ruimte (of een ruimte met een hogere dimensie) zal het iteratieproces resulteren in een ellips.
Om volledig zicht te krijgen op het probleem van de krimpende puntenketting moeten we het opentrekken tot een \emph{complexe vectorruimte} met dimensie $k$. Daarom hier defini\"eren we de vectorruimte $\C,V,+$ met
\[V=\left\{ \sum_{j=1}^k x_jA_j \mid x_i \in \C \right\}. \]
De punten $(A_i)_{i=1 \cdots k}$ vormen een basis van deze vectorruimte. De optelling in deze vectorruimte is de \emph{puntsgewijze optelling}.
Het iteratieproces is gebaseerd op het berekenen van middelpunten van lijnstukken tussen opeenvolgende punten in een puntenketting. Elk punt in de ketting heeft precies \'e\'en opvolger. Deze opvolgers leggen een \emph{doorschuifoperator} D vast:
\[ \text{D}:V \to V: \sum_{j=1}^k x_jA_j \mapsto \sum_{j=1}^k x_jA_{j+1}. \]
In paragraaf \ref{doorschuif} berekenen we de eigenwaarden en eigenvectoren van deze lineaire transformatie van $V$.
Vervolgens onderzoeken we de \emph{middelpuntsoperator} M:
\[ \text{M}:V \to V: \sum_{j=1}^k x_jA_j \mapsto \sum_{j=1}^k x_j \frac {A_j+A_{j+1}}{2}. \]
Ook van deze lineaire transformatie berekenen we de eigenwaarden en de eigenvectoren. Er zullen voldoende eigenvectoren gevonden worden om een basis te vormen.
Deze basis is orthogonaal ten opzichte van een inproduct ( \emph{Hermitisch product})
\[ \langle \cdot, \cdot \rangle: V \times V \to \C: \left( \sum_{j=1}^k x_jA_j,\sum_{j=1}^k y_jA_j \right) \mapsto \sum_{j=1}^k x_j^ \ast \cdot y_j. \]
We kunnen elke beginvector $A_i$ op een unieke manier schrijven als een lineaire combinatie van de vectoren van deze orthogonale basis. In deze inproductruimte (\emph{Hermitische ruimte}) is het mogelijk de beelden van een beginvector $A_i$ na $n$ keer iteratief toepassen van de lineaire transformatie M op een eenvoudige manier te berekenen.
Voor $n$ naar oneindig zullen alleen de eigenvectoren van M met de \emph{grootste} eigenwaarde van belang zijn. Deze dominante eigenvectoren zullen ons leiden naar een verklaring voor de regelmaat in de krimpende puntenketting.
\section{De doorschuifoperator} \label{doorschuif}
Stel dat er vier punten $A_1, A_2, A_3$ en $A_4$ gegeven zijn. Elke vector $x_1A_1+x_1A_2+x_1A_3+x_1A_4$ met vier gelijke co\"effici\"enten wordt door de doorschuifoperator D op zichzelf afgebeeld. Deze vectoren zijn eigenvectoren met eigenwaarde 1. Elke vector van de vorm $x_1A_1-x_1A_2+x_1A_3-x_1A_4$ wordt afgebeeld op $x_1A_2-x_1A_3+x_1A_4-x_1A_1$. Vectoren van dit type zijn eigenvectoren met eigenwaarde -1. Je kan makkelijk inzien dat er geen andere re\"ele eigenwaarden van deze lineaire transformatie kunnen bestaan dan 1 en -1.
We kunnen alle eigenwaarden $\lambda$ van de lineaire transformatie D via de transformatiematrix
\[ A = \pmM{0&0&0&1\\1&0&0&0\\0&1&0&0\\0&0&1&0} \]
berekenen als nulpunten van de karakteristieke veelterm $\chi_A(\lambda)=\lambda^4-1$. Deze nulpunten zijn de vier vierdemachtswortels van 1, namelijk 1, -1, i en -i. Twee van deze eigenwaarden zijn complexe getallen. De bijbehorende eigenvectoren hebben complexe co\"effici\"enten. Vandaar dat we ervoor gekozen hebben om in een complexe vectorruimte te werken. Ook in het algemene geval zijn de eigenwaarden van de doorschuifoperator complexe eenheidswortels.
Stel algemeen dat er $k$ punten gegeven zijn. We kunnen dan aantonen dat de eigenvectoren van D van de vorm
\[U=\sum_{j=1}^k e^{ij\alpha} A_j \]
zijn want
\[\text{D}U=\sum_{j=1}^k e^{ij\alpha} A_{j+1}=\sum_{j=1}^k e^{i(j-1)\alpha} A_{j}=\frac{1}{e^{i\alpha}} \sum_{j=1}^k e^{ij\alpha} A_j=\frac{1}{e^{i \alpha}} U.\]
De eigenwaarde van deze eigenvector is $e^{-i\alpha}$. Omdat de co\"effici\"enten van $A_i$ periodiek moeten zijn in $j$, moet $e^{ik\alpha}=1$ zodat
\[\alpha = m \cdot \frac{2 \pi}{k} \qquad \text{met} \quad m \in \Z_k.\]
Als we het $k$-de deel van de volle hoek benoemen met de letter $\theta$, d.w.z. $\theta=\frac{2 \pi}{k}$, dan is
\[U_m=\sum_{j=1}^k e^{ijm \theta} A_j \]
de eigenvector van de doorschuifoperator D met eigenwaarde $e^{-im \theta}$. Voor elke $m \in \{1, 2, \cdots ,k\}$ vinden we dus een eigenwaarde die overeenkomt met een complexe eenheidswortel. Door de periodiciteit zal $m=k$ dezelfde eenheidswortel opleveren als $m=0$.
De eigenvectoren $U_0$ en $U_1$ zullen een belangrijke rol spelen het de volgende paragrafen, voornamelijk bij de ontknoping in paragraaf \ref{limiet}:
\[\begin{aligned}
&U_0=\sum_{j=1}^k A_j;\\
&U_1= \sum_{j=1}^k e^{ij \theta}A_j=\sum_{j=1}^k \cos \left( {j \theta} \right) A_j + i \sum_{j=1}^k \sin \left( {j \theta} \right) A_j = W + i Z.
\end{aligned}\]
\section{De middelpuntsoperator}
De middelpuntsoperator M is nauw verwant met de doorschuifoperator D. Dit wordt duidelijk in de volgende afleiding:
\[ \text{M}A_j=\frac{1}{2}(A_j+A_{j+1})=\frac{1}{2}(A_j+\text{D} A_j)= \frac{1}{2}(1+\text{D}) A_j.\]
Hieruit volgt dat M dezelfde eigenvectoren $U_m$ heeft als D maar met eigenwaarden:
\[\lambda_m=\frac{1}{2}(1+e^{-im \theta}).\]
We zoeken nu de dominante eigenwaarde, d.w.z. de eigenwaarde met de grootste modulus, en de subdominante eigenwaarde, d.w.z. die met de op \'e\'en na grootste modulus. Om deze modulus makkelijk te berekenen, herschrijven we de eigenwaarden als volgt:
\[\begin{aligned}
\lambda_m &= \frac{1}{2} \left( e^{im \frac{\theta}{2}}+e^{-im \frac{\theta}{2}} \right) e^{-im \frac{\theta}{2}}\\
&= \frac{1}{2} \left( \cos \left( {m \frac{\theta}{2}} \right)+i \sin \left( {m \frac{\theta}{2}} \right) + \cos \left( {m \frac{\theta}{2}} \right) - i \sin \left( {m \frac{\theta}{2}}\right) \right) e^{-im \frac{\theta}{2}}\\
&= \cos \left( m \frac{\theta}{2} \right) e^{-im \frac{\theta}{2}}.
\end{aligned}\]
Hieruit volgt dat $\abs{\lambda_m} = \abs{\cos \left( m \frac{\theta}{2} \right)}$. Deze modulus is maximaal voor $m=0$. De grootste modulus is dus $\abs{\lambda_0}=1$. De tweedegrootste modulus vinden we voor $m=1$ en tegelijkertijd voor $m=-1$. De functie $\lambda_m$ is immers even in $m$. Deze subdominante modulus is $\abs{\lambda_1}= \cos \frac{\theta}{2}= \cos \frac{\pi}{k}$. De eigenwaarde met de derdegrootste modulus vinden we voor $m=2$ en $m=-2$. De subsubdominante modulus is bijgevolg $\abs{\lambda_2}= \cos \theta= \cos \frac{2 \pi}{k}$. Zo blijven de moduli van de eigenwaarden afnemen tot wanneer deze cosinus nul is.
\section{Een orthogonale basis van eigenvectoren}
De eigenvectoren $U_m$ met $m=1 \cdots k$ zijn lineair onafhankelijk. Ze vormen een basis van de vectorruimte $\C,V,+$. Meer nog, er kan aangetoond worden dat ze een orthogonale basis vormen ten opzichte van het Hermitische product $\langle \cdot, \cdot \rangle$. Voor $l \neq m$ geldt immers dat:
\[ \begin{aligned}
\langle U_l, U_m \rangle &= \langle \sum_{j=1}^k e^{ijl \theta} A_j, \sum_{j=1}^k e^{ijm \theta} A_j \rangle = \sum_{j=1}^k e^{-ijl \theta} e^{ijm \theta} = \sum_{j=1}^k \left( e^{i(m-l) \theta} \right)^j \\ &= \frac{e^{ik(m-l)\theta }-1}{e^{i(m-l)\theta }-1} = \frac{e^{i(m-l)2 \pi }-1}{e^{i(m-l)\theta }-1} =\frac{{e^{2 \pi i }}^{m-l}-1}{e^{i(m-l)\theta }-1}=0.
\end{aligned} \]
Zonder veel berekeningen kan ingezien worden dat $\langle U_m, U_m \rangle = k$. De basis van eigenvectoren is dus niet genormeerd. De orthogonaliteit van de basis maakt het evenwel makkelijker om een willekeurig vector te ontbinden in componenten volgens deze basisvectoren. We kunnen bijvoorbeeld een beginvector $A_j$ op de volgende manier ontbinden in een lineaire combinatie van de eigenvectoren:
\[A_j=\sum_{m=0}^{k-1} a_{jm} U_m.\]
Vermenigvuldigen we $A_j$ langs links met $U_m$ dan vinden we:
\[\langle U_m, A_j \rangle= a_{jm} \langle U_m, U_m \rangle = a_{jm} k \]
waaruit volgt dat:
\[a_{jm}=\frac{1}{k} \langle U_m, A_j \rangle =\frac{1}{k} \langle \sum_{j=0}^{k-1} e^{ijm \theta}, A_j \rangle = \frac{1}{k} e^{-ijm \theta}. \]
\noindent Voor de volgende berekeningen is de nulde co\"effici\"ent van bijzonder belang:
\[a_{j0}=\frac{1}{k}.\]
\section{Iteratie met een groot aantal iteratiestappen} \label{limiet}
In de vorige paragraaf hebben we alle beginvectoren $A_j$ uitgedrukt als een lineaire combinatie $\sum_{m=0}^{k-1} a_{jm} U_m$ van de eigenvectoren $U_m$ van de middelpuntsoperator M. Hierdoor is het eenvoudig geworden om de middelpuntsoperator $n$ keer recursief te laten inwerken op $A_j$:
\[ \begin{aligned}
\text{M}^n A_j &= \sum_{m=0}^{k-1} a_{jm} \lambda_m^n U_m \\
&= a_{j0} \lambda_0^n U_0+a_{j1} \lambda_1^n U_1+a_{j,-1} \lambda_0^{-1} U_{-1}+a_{j2} \lambda_2^n U_2+a_{j,-2} \lambda_0^{-2} U_{-2} + \cdots.
\end{aligned}\]
\noindent In deze uitdrukking staan de eigenvectoren genoteerd in volgorde van dominantie.
Voor $n$ naar oneindig blijft alleen eerste term met eigenwaarde $\lambda_0=1$ over. De machten in de volgende termen gaan naar 0. Zo vinden we:
\[\lim_{n \to \infty} \left( \text{M}^n A_j \right) = a_{j0} U_0 = \frac{1}{k} \sum_{j=1}^k A_j \]
waaruit duidelijk blijkt dat alle beginpunten na een eindeloze iteratie naar het zwaartepunt $Z$ van de oorspronkelijke puntenverzameling convergeren.
Voor zeer grote waarden van $n$ spelen alleen de drie eerste termen een rol in de berekening. De eerste term benadert het zwaartepunt $Z$. Van de twee volgende termen kan aangetoond worden dat ze complex toegevoegd zijn. Een goede benadering van het iteratieve beeld van $A_j$ voor een groot aantal iteratiestappen is:
\[\text{M}^n A_j \approx Z + 2 \text{Re} (a_{j1} \lambda_1^n U_1).\]
\noindent Vervangen we hierin $U_1$ door $W+iZ$ (zie eerder) en $a_{j1}\lambda_1^n$ door $\rho e^{-i \phi}$ met $\rho=\frac{1}{k} \cos^n (\frac{\theta}{2})$ en $\phi=(2j+n) \frac{\theta}{2}$ dan vinden we de volgende vergelijking (reken na)
\[\text{M}^n A_j \approx Z + 2 \rho (W \cos \phi + Z \sin \phi)\]
\noindent die duidelijk een bundel ellipsen voorstellen met middelpunt $Z$ en met toegevoegde assen volgens de richtingen van $W$ en $Z$. De ori"entatie van deze ellipsen hangt af van de configuratie van de oorspronkelijke punten. De inkrimpingsfactor van de opeenvolgende ellipsen in de iteratie is gelijk aan $\cos (\theta /2)$. Deze factor hangt dus alleen af van het aantal beginpunten en niet van hun onderlinge positie.
\begin{figure} [h]
\centering
\includegraphics[width=0.8\textwidth]{chain1.jpg}
\caption{15 iteratiestappen door middel van de middelpuntsoperator M}
\end{figure}
\begin{figure} [h]
\centering
\includegraphics[width=0.8\textwidth]{chain2.jpg}
\caption{Benadering van 15 iteratiestappen door ellipsen}
\end{figure}
Deze berekeningen bewijzen nog niet volledig dat elke puntenketting convergeert naar een ellips door de iteratieve toepassing van de middelpuntsoperator M. Indien immers de vectoren $W$ en $Z$ gelijk zijn aan de nulvector vallen de tweede en de derde term in de ontwikkeling van $\text{M} ^n A_j$ weg. We moeten dan ook de subsubdominante eigenvectoren in rekening brengen. De berekening verloopt analoog. Indien $U_2=T+iS$ vinden we een ellips met hoofdassen in de richting van $T$ en $S$. De inkrimpingsfactor van de opeenvolgende ellipsen is gelijk aan $\cos\theta$ (reken na).
\end{document}
