Funktioiden sortteeraamisesta
Jukka Liukkonen
Mat. yo. evp.
Arvot järjestykseen — johdatusta arvokeskusteluun
Päättyvän lukujonon alkioiden järjestäminen1 esimerkiksi laskevaan suuruusjärjestykseen on helppoa ainakin, jos luvut ovat pieniä positiivisia kokonaislukuja, niitä on vähän, ja ne on esitetty arabialaisilla numeroilla suoraan, turhia venkoilematta: \[(6,2,3,5,2) \xrightarrow{\rm sort} (6,5,3,2,2).\] Epävarmuutta aiheuttaa korkeintaan se, kumpi kakkosista tulee laittaa viimeiseksi. Tässä artikkelissa ei puututa filosofisiin kysymyksiin. Tarkoituksena ei myöskään ole esitellä erilaisia lajittelualgoritmeja. Artikkelin tavoitteena on tutkia, mitä lajittelulla tarkoitetaan silloin, kun lajiteltavia lukuja on äärettömän monta. Varsinainen ongelma on, miten reaalimuuttujan reaaliarvoisen funktion eli reaalifunktion arvot laitetaan suuruusjärjestykseen; toisin sanoen kuinka funktio järjestetään uudeksi funktioksi niin, että jälkimmäisessä on edellisen arvot vaikkapa laskevaan suuruusjärjestykseen lajiteltuina? Voidaanko järjestäminen toteuttaa jonkinlaisella reaalilukuvälin permutoinnilla?
Esimerkkilukujono esitetään ohessa pylväsdiagrammina. Funktioiden järjestämistä ennakoiden luodaan havainnollinen mielikuva, jossa pylväät ovat aluksi veden pinnan alla uppeluksissa. Veden vähetessä pylväät pulpahtavat esiin yksi tai useampi kerrallaan. Vedenpinnan tasoa merkitään kreikkalaisella kirjaimella \(\alpha\). Kun vesi laskee eli \(\alpha\) pienenee, ensimmäisenä veden alta ilmestyy korkein pylväs. Silloin \(\alpha=6\). Vedenpinnan edelleen laskiessa pylväät ilmestyvät näkyviin laskevassa suuruusjärjestyksessä, jolloin ne on helppoa poimia jonoon samassa järjestyksessä. Kun pinta saavuttaa tason \(\alpha=2\), viimeisinä vedenpinnan puhkaisevat kaksi lyhintä pylvästä.
Päättyvä lukujono \(\boldsymbol{x}=(x_1,x_2,\ldots,x_n)\) liittää indeksijoukon \(I_n=\{1,2,\ldots,n\}\) jokaiseen alkioon \(i\) reaaliluvun \(x_i\). Itse asiassa lukujono onkin funktio, nimittäin kuvaus \[f:I_n\to{\mathbb R},\quad f(i)=x_i.\] Jos jono \(\boldsymbol{x}^\ast=(x_1^\ast,x_2^\ast,\ldots,x_n^\ast)\) on saatu jonosta \(\boldsymbol{x}\) permutoimalla jälkimmäisen alkiot laskevaan suuruusjärjestykseen, on muodostettu uusi funktio \[f^\ast:I_n\to{\mathbb R},\quad f^\ast(i) = x_i^\ast.\] Tälle uudelle funktiolle pätee \[f^\ast(1)\ge f^\ast(2)\ge\ldots\ge f^\ast(n).\] Jos funktio \(f\) saa tietyn arvon \(k\) kertaa, toisin sanoen kyseinen luku esiintyy \(k\) kertaa jonossa \(\boldsymbol{x}\), myös funktio \(f^\ast\) saa tuon arvon tasan \(k\) kertaa. Tämä on tärkeä havainto siirryttäessä päättyvistä jonoista päättymättömiin ja lopulta reaalifunktioihin.
Järjestämisen jälkeen esimerkkipylväikkö näyttää tältä:
Koska jonossa \(\boldsymbol{x}^\ast\) on täsmälleen samat luvut kuin jonossa \(\boldsymbol{x}\), summan vaihdannaisuuden seurauksena \[\sum_{i=1}^nx_i = \sum_{i=1}^nx_i^\ast.\] Jos \(\boldsymbol{y}=(y_1,y_2,\ldots,y_n)\) on toinen jono, vektorien pistetulon kaltaisille tulojen summille pätevät uudelleenjärjestelyepäyhtälöt (engl. rearrangement inequality) \[\sum_{i=1}^nx_i^\ast y_{n+1-i}^\ast \le \sum_{i=1}^nx_i y_i \le \sum_{i=1}^nx_i^\ast y_i^\ast.\] Ne on hyvin helppoa todistaa binäärisille eli pelkistä nollista ja ykkösistä muodostetuille jonoille. Yleisen tapauksen todistus on esitetty Wikipedian sivulla [5]. Itse asiassa vasen ja oikea epäyhtälö ovat yksi ja sama tulos kahdella eri tavalla esitettynä, mikä nähdään tarkastelemalla jonon \(\boldsymbol{y}\) sijaan vastajonoa \(-\boldsymbol{y}=(-y_1,-y_2,\ldots,-y_n)\).
Uudelleenjärjestelyepäyhtälöllä on hauska fysikaalinen tulkinta. Lukuja \(y_i\) voidaan ajatella painoina, jotka on kiinnitetty vaakasuoraan tankoon etäisyyksien \(x_i\) päähän tangon toisessa päässä sijaitsevasta referenssipisteestä. Suurin momentti \(\sum_{i=1}^nx_i y_i\) saadaan aikaan, kun raskaimmat painot kiinnitetään mahdollisimman kauas referenssipisteestä. Kun isot painot ovat lähellä referenssipistettä, momentti on vastaavasti pienin.
Sananen päättymättömistä jonoista
Päättymättömän jonon järjestäminen ei aina onnistu. Esimerkiksi positiivisten rationaalilukujen jonossa \[\left(\frac{1}{2},\frac{4}{3},\frac{5}{6},\frac{8}{7},\ldots, \frac{2i-1}{2i},\frac{2i+2}{2i+1},\ldots\right)\] on ääretön määrä sekä ykköstä pienempiä alkioita että ykköstä suurempia alkioita. Vaikka ne laitettaisiin mihin tahansa järjestykseen, ensimmäisen ykköstä pienemmän alkion jälkeen olisi jossain kohdassa ykköstä suurempi alkio, ja sen jälkeen taas jossain kohdassa ykköstä pienempi alkio. Ei sellainen jono ole sen enempää nouseva kuin laskevakaan. Jonolta pitää vaatia jotain, että se voidaan järjestää.
Jos rajoitutaan positiivisiin lukuihin ja niiden järjestämiseen laskevaksi jonoksi, riittävä joskaan ei välttämätön ehto jonon järjestämisen onnistumiseksi on, että jonolla on raja-arvo nolla. Sortteeraaminen tehdään samalla vedensäännöstelytoimenpiteellä kuin päättyvänkin jonon järjestely. Yhtälö \(\sum_i x_i=\sum_i x_i^\ast\) ja epäyhtälö \(\sum_i x_iy_i\le\sum_i x_i^\ast y_i^\ast\) pätevät myös päättymättömille summille ainakin, jos ne suppenevat. Todistus on ilmeisin muutoksin sama kuin päättyvillekin summille.
Reaalifunktion järjestäminen
Eteen tulevia hankalan näköisiä kaavoja ei tule pelästyä. Lajittelun idean ymmärtäminen onnistuu ilman kaavojakin muun tekstin ja kuvien avulla. Tarkkaa lukijaa varten sanottakoon, että turhan monimutkaisuuden välttämiseksi funktioiden uudelleenjärjestelyssä rajoitutaan sellaisiin reaalimuuttujan reaaliarvoisiin funktioihin \(f\), että
\(f\) on kuvaus \([0,\infty[\,\to{\mathbb R}\);
\(f\) on jatkuva ainakin paloittain2;
\(f(x)\ge 0\) kaikilla \(x\ge 0\);
\(f(x)=0\) riittävän suurilla \(x\).
Viimeinen ehto tarkoittaa sellaisen positiivisen (ja yleensä hyvin suuren) luvun \(M\) olemassaoloa, että \(f(x)=0\) kaikilla lukua \(M\) suuremmilla muuttujan \(x\) arvoilla; ts. \(f\) yhtyy nollafunktioon (so. vakiofunktioon nolla), kunhan mennään tarpeeksi kauas origosta. Ehdon ansiosta vältytään eräiltä raja-arvotarkasteluilta. Samoin vältytään tilanteelta, jossa erään funktion arvoksi tulisi joskus ääretön.
Sortteeraamisen tarkastelu aloitetaan yksinkertaisesta esimerkistä, nimittäin paloittain vakiosta funktiosta, jolla on samat arvot kuin edellä tarkastellulla viiden alkion mittaisella jonolla. Funktio \(f:[0,\infty[\,\to{\mathbb R}\) saa väleillä \([0,1[\), \([1,2[\), \([2,3[\), \([3,4[\), \([4,5[\) ja \([5,\infty[\) arvot \(6\), \(2\), \(3\), \(5\), \(2\) ja \(0\) tässä järjestyksessä. Jokainen arvo tulee äärettömän monessa pisteessä. Voidaanko kuvitella mitään järkevää tapaa järjestää funktio \(f\) laskevaksi funktioksi \(f^\ast\)?
Aikaisemmin sanotusta tulee varmaankin ensimmäisenä mieleen funktion \(f\) upottaminen uppeluksiin veden alle, minkä jälkeen annetaan vedenpinnan laskea. Pylväiden tapaan funktio \(f\) paljastuu pikkuhiljaa esiin veden alta, korkeimmat osat ensiksi. Funktiohan muistuttaakin pylväikköä, pylväät ovat vaan leveämpiä ja kiinni toisissaan. Voidaan siis tehdä samat temput kuin pylväille. Näin syntyy seuraavan kuvan esittämä uusi funktio \(f^\ast:[0,\infty[\,\to{\mathbb R}\).
Huomataan, että vedenkorkeudella \(\alpha\) sekä järjestetyn funktion että alkuperäisen funktion kuvaaja kulkee täsmälleen saman vaakasuuntaisen matkan vedenpinnan yläpuolella (katkoviivaa täydentävät katkottomat osuudet). Täsmällisesti ilmaisten vedenpinnan tasoon \(\alpha\) liittyvän tasojoukon (engl. level set) \[E_\alpha(f) = \big\{\,x\in[0,\infty[\,\big|\,f(x)>\alpha\,\big\}\] mitta3 (engl. measure) \[\mu(E_\alpha(f)),\] ei muutu funktiota järjestettäessä. Tämä mitan muuttumattomuus on juuri se ominaisuus, joka tekee funktion uudelleenjärjestelystä laskevaksi funktioksi (engl. decreasing rearrangement) järkevän: kaikilla \(\alpha\ge 0\) \[\mu(E_\alpha(f^\ast)) = \mu(E_\alpha(f)).\] Mitta voidaan esittää myös integraalina: \[\mu(E_\alpha(f)) = \int_0^\infty{{\mathbb 1}_{{\hspace{-0.2ex}}_{f\hspace{-0.1ex}>\hspace{-0.1ex}\alpha}}}(x)\,{\text{d}}x = \int_0^\infty{{\mathbb 1}_{{\hspace{-0.2ex}}_{f^\ast\hspace{-0.1ex}>\hspace{-0.1ex}\alpha}}}(x)\,{\text{d}}x,\] missä on merkitty \[{{\mathbb 1}_{{\hspace{-0.2ex}}_{f\hspace{-0.1ex}>\hspace{-0.1ex}\alpha}}}(x) = \left\{\begin{array}{rl}1,&f(x)>\alpha\\0,&f(x)\le\alpha.\end{array}\right.\] Funktion \(f^\ast\) arvo pisteessä \(x\) syntyy niin, että annetaan vedenpinnan laskea niin kauan kuin mitta \(\mu=\mu(E_\alpha(f))\) on korkeintaan \(x\). Tasan siinä kohdassa, jossa ehto \(\mu\le x\) lakkaa olemasta voimassa, ja sen tilalle astuu ehto \(\mu>x\), asetetaan \(f^\ast(x)=\alpha\). Toisin sanoen: kun vedenpinta laskee niin paljon, että saarien yhteenlaskettu mitta on ylittämäisillään arvon \(x\), merkitään vedenkorkeus \(\alpha\) muistiin, jolloin \(f^\ast(x)=\alpha\). Lukijaa kehotetaan miettimään asiaa seuraavien kahden kuvan avulla. Vahvennetut katkoviivat havainnollistavat arvojen \(f^\ast(1.3)\) ja \(f^\ast(3.2)\) määräytymistä. Laskeva funktio \(f^\ast\) tietyssä mielessä pannaan kokoon vaakasuorista viipaleista \[E_\alpha(f)\times\{\alpha\} = \big\{\,(x,\alpha)\,\big|\,x\ge 0,\;f(x)>\alpha\,\big\}\] liu’uttamalla ne kullakin tasolla erikseen peräkkäin vasemmalle tiiviiksi, katkeamattomaksi janaksi.
Kuuluisa Cavalierin periaate [2] takaa sen, että funktion kuvaajan ja \(x\) -akselin väliin jäävä pinta-ala ei muutu liu’uttamisen seurauksena: \[\int_0^\infty f(x)\,{\text{d}}x = \int_0^\infty f^\ast(x)\,{\text{d}}x.\] Kun kaksi funktiota \(f\) ja \(g\) uudelleenjärjestetään laskeviksi funktioiksi \(f^\ast\) ja \(g^\ast\), funktionelikolle pätee Hardyn-Littlewoodin epäyhtälö (engl. Hardy-Littlewood inequality) \[\int_0^\infty f(x)g(x)\,{\text{d}}x \le \int_0^\infty f^\ast(x)g^\ast(x)\,{\text{d}}x,\] joka todistetaan hieman muunnetussa yleisemmässä tilanteessa Wikipedian sivulla [3]. Aikaisemmin esiintyneet yhtälö \(\sum_i x_i=\sum_i x_i^\ast\) ja epäyhtälö \(\sum_i x_iy_i\le\sum_i x_i^\ast y_i^\ast\) ovat samaa sukujuurta vastaavien integraaliyhtälön ja -epäyhtälön kanssa (summa on erikoistapaus yleisestä integraalin käsitteestä).
Matematiikan kieli pyrkii olemaan täsmällistä, eikä mitään määritelmää tai tulosta ole sallittua jättää pelkästään havainnollisen mielikuvan varaan. Funktion \(f^\ast\) täsmällinen määritelmä on tämä: \[f^\ast:\,[0,\infty[\,\to{\mathbb R},\; f^\ast(x) = \inf\big\{\,\alpha\ge 0\;\big|\;\mu\big(E_\alpha(f)\big)\le x\,\big\}.\] Tässä \(\inf\) tarkoittaa alhaalta rajoitetun joukon infimumia eli suurinta alarajaa. Jos käsite ei ole lukijalle tuttu, se kannattaa opiskella esimerkiksi Wikipedian sivulta [4]. Itse asiassa funktion \(f^\ast\) määritelmässä joukko, jolle infimum muodostetaan, on aina tyyppiä \([a,\infty[\), missä \(a\) on reaaliluku. Sille, vastaavalle avoimelle välille \(]a,\infty[\) ja yleisemminkin ei-tyhjälle välille infimum on välin vasen päätepiste eli tässä tapauksessa \(a\).
Epäaito epäyhtälö \(\mu\big(E_\alpha(f)\big)\le x\) funktion \(f^\ast\) määritelmässä takaa sen, että funktio \(f^\ast\) on oikealta jatkuva samoin kuin esimerkiksi todennäköisyysjakaumien kertymäfunktiot: \[\lim_{h\to 0^+}f^\ast(x+h)=f^\ast(x).\]
Seuraavat kaksi kuvaa esittävät jatkuvan funktion järjestämistä alenevaan järjestykseen vedenlaskuperiaatteella. Ensimmäisen kuvan funktio konstruoidaan jatkamalla sinikäyrän jaksopari nollafunktiona äärettömyyteen: \[f(x) = \left\{\begin{array}{c@{ \ }ll} A\sin^2(wx) &,& 0\le x\le\tfrac{2\pi}{w} \\[2ex] 0 &,& x>\tfrac{2\pi}{w}\,, \end{array}\right.\] missä \[A = 6,\quad w = \frac{9\pi}{20}\,.\] Jälkimmäinen kuva esittää järjestettyä funktiota. Sillä on lauseke \[f^\ast(x) = \left\{\begin{array}{c@{ \ }ll} A\cos^2\left(\frac{1}{4}\,wx\right) &,& 0\le x\le\tfrac{2\pi}{w} \\[2ex] 0 &,& x>\tfrac{2\pi}{w}\,. \end{array}\right.\]
Kohdissa \(x_1\), \(x_2\), \(x_3\) ja \(x_4\) olevat pylväät kuvautuvat järjestettäessä yhdeksi pylvääksi kohtaan \(x_\ast\). Tällainen ei ole sallittua lukujonojen sorttauksessa, permutoitaessa eri pylväät säilyvät erillisinä. Huomaa kuitenkin, että yhteen sulautuvien \(x\)-arvojen joukko on nollamittainen. Lukusuorallahan mitta on joukon pituus, ja yhden pisteen mitta on nolla. Sen takia äärellisen monen pisteen muodostaman joukonkin mitta on nolla. Myös äärettömän joukon mitta on usein nolla, esimerkkinä vaikkapa luonnollisten lukujen joukko \({\mathbb N}=\{1,2,3,\ldots\}\). Se koostuu nollamittaisista pisteistä, joiden yhteenlaskettu mitta on \(0+0+0+\ldots = 0\).
Kaksoiskolmio – lukujonon ja funktion vertailua
Funktion uudelleenjärjestämisen kannalta kahden aallon sinifunktio on oleellisesti samanlainen kuin pelkistetty ja laskennallisesti helpompi kaksoiskolmiofunktio, jonka kuvaaja on piirretty alle.
Funktion arvo pisteessä \(x\) on \[f(x) = \left\{\begin{array}{c@{ \ }ll} 2x &,& 0\le x<1 \\ 4-2x &,& 1\le x<2 \\ 2x-4 &,& 2\le x<3 \\ 8-2x &,& 3\le x<4 \\ 0 &,& 4\le x. \end{array}\right.\] Kaksoiskolmio on helppoa järjestää laskevaksi viistouttamalla (engl. shear) kolmiot vasemmalle niin, että niiden kannat pysyvät paikoillaan, ja ylimmät kärjet siirtyvät vaakasuunnassa \(y\)-akselille pisteeseen \((0,2)\). Viistoutus saadaan aikaan muunnoksella \[(x',y') = \left\{\begin{array}{c@{ \ }ll} \left(x-\frac{1}{2}\,y,\;y\right) &,& 0\le x<2 \\[2ex] \left(x-\frac{3}{2}\,y,\;y\right) &,& 2\le x, \end{array}\right.\] missä tason piste \((x,y)\) muuntuu pisteeksi \((x',y')\), ja lopputulos näyttää tältä:
Järjestetyllä funktiolla on lauseke \[f^\ast(x) = \left\{\begin{array}{c@{ \ }ll} 2-\tfrac{1}{2}\,x &,& 0\le x<4 \\[1ex] 0 &,& 4\le x. \end{array}\right.\] Kun jatkuva kaksoiskolmiofunktio niin sanotusti diskretoidaan ottamalla mukaan funktion arvot ainoastaan tasavälisessä pisteistössä, saadaan kuvaan piirrettyä pylväikköä vastaava lukujono, jonka lopussa on äärettömän monta nollaa.
Funktio ja pylväät järjestetään erikseen laskevaan suuruusjärjestykseen, jolloin samanpituiset pylväät muodostavat tasanteita, ja niistä syntyy vasemmalle nouseva portaikko.
Pylväikköä tihennettäessä tasanteet kapenevat, ja järjestettyjen pylväiden yläpäät ovat lähempänä järjestetyn funktion kuvaajaa kuin aikaisemmin.
Seuraavissa kuvissa pylväikköä on tihennetty edelleen. Tietyt kahdeksan pylvästä, neljä sinistä ja neljä punaista, on otettu erityistarkkailuun.
Tihennystä ajatellaan jatkettavan loputtomiin. Silloin tasapituiset pylväsnelikot lopulta sulautuvat yhdeksi äärettömän ohueksi pylvääksi, nelikon “raja-arvoksi’. Näin syntyy jo edellä siniaallon järjestelyn yhteydessä havaittu ilmiö. Yhteensulautumisen takia funktion arvoja ei yleensä saada järjestykseen permutoimalla argumentin \(x\) arvoja!
Jos \(x\) -arvoja ei permutoida, millaisella kuvauksella niitä sitten muutellaan? Seuraavista kuvista nähdään, miten pylvään \(x\) -koordinaatti muuttuu siirrettäessä pylväs suuruusjärjestyksen määräämälle paikalle. Ensimmäinen kuva liittyy diskretoituun funktioon, joka järjestyy permutaatiolla. Vaaka-akselilla ovat pylväiden paikat \(x\) ennen sorttausta ja pystyakselilla paikat \(\sigma(x)\) sorttauksen jälkeen; toisin sanoen pisteistö on permutaatiofunktion \(\sigma\) kuvaaja. Siniset ja punaiset pisteet liittyvät edellisten kuvien sinisiin ja punaisiin pylväisiin.
Jälkimmäinen kuva esittää permutaatiota vastaavaa funktiota \(T\), sanottakoon sitä vaikkapa kvasipermutaatioksi, joka järjestää diskretoimattoman kaksoiskolmion. Järjestettävä funktio \(f\) on jatkuva ja muutenkin yksinkertainen (äärellinen määrä huippuja). Silloin järjestäminenkin sujuu siistillä jatkuvalla funktiolla \(T\). Järjestävän kvasipermutaation ei kuitenkaan tarvitse olla siisti, sillä funktion arvoja \(f(x)=0\) vastaavia argumentin \(x\) arvoja voidaan permutoida keskenään hyvinkin villisti; häntä oikeassa ylänurkassa voidaan “pörhistää ja laittaa heilumaan”.
Sinivihreät varjostukset kuvassa havainnollistavat sitä tosiseikkaa, että kuvauksessa \(T\) kuvapuolen välin \(U\) mitta on yhtäsuuri kuin alkukuvan \(T^{-1}(U)\) mitta. Tämä on oleellista. Vaatimus mittojen yhtymisestä tulee suoraan järjestämisen periaatteesta.
Kiitän Heikki Vistiä käsikirjoituksen lukemisesta ja arvokkaista kommenteista.
Viitteet
[1] Almut Burchard, Galia Dafni & Ryan Gibara: New Bounds and Continuity for Rearrangements on BMO and VMO. October 28, 2020. Artikkeli arXiv palvelussa. https://arxiv.org/pdf/2010.15024.pdf
[2] Wikipedia: Cavalieri’s principle.
https://en.wikipedia.org/wiki/Cavalieri's_principle
[3] Wikipedia: Hardy-Littlewood inequality.
https://en.wikipedia.org/wiki/Hardy-Littlewood_inequality
[4] Wikipedia: Infimum and supremum.
https://en.wikipedia.org/wiki/Infimum_and_supremum
[5] Wikipedia: Rearrangement inequality.
https://en.wikipedia.org/wiki/Rearrangement_inequality
[6] Wikipedia: Symmetric decreasing rearrangement.
https://en.wikipedia.org/wiki/Symmetric_decreasing_rearrangement
Alaviitteet
Järjestämisestä käytetään myös nimityksiä lajittelu, sorttaus, sortteeraaminen ja uudelleenjärjestäminen.↩︎
Paloittain jatkuvalla funktiolla on korkeintaan äärellinen määrä epäjatkuvuuskohtia, joissa sillä on äärelliset toispuoleiset raja-arvot.↩︎
Mitta on yleinen matemaattinen käsite. Tämän artikkelin lukijalle riittää tietää, että erillisistä jananpätkistä koostuvan joukon mitta on sama kuin kyseisten jananpätkien yhteenlaskettu pituus.↩︎