lauantai 25. heinäkuuta 2020

Geodeettinen käyrä 2

Pinnan $z=\sin(x)\sin(y)$ geodeettinen käyrä

Piirtelin geodeettisia käyriä aiemmassa postauksessani ja lupasin vielä palata asiaan.

Pinnan geodeettisen käyrän voi luonnehtia kahta pinnan pistettä yhdistävänä lyhimpänä pintaa pitkin kulkevana tienä. Toinen vaihtoehto on ajatella käyrää mahdollisimman suorana pintaa pitkin kulkevana tienä. Valitaanpa kumpi tahansa, niin käyrälle voidaan johtaa differentiaaliyhtälö, jonka ratkaisuna käyrä saadaan, kuten aiemmin hahmottelin. Differentiaaliyhtälö voidaan kuitenkin ratkaista alkeisfunktioiden avulla yleensä vain poikkeustapauksissa, ja yleensä on turvauduttava numeeriseen ratkaisemiseen ja siten käyrän approksimaatioon. Riittävään tarkkuuteen pääseminen esimerkiksi piirtämistä varten ei kuitenkaan ole ongelma laskentaohjelmia käytettäessä.

Voisiko käyrän approksimaation sitten löytää jollakin muulla tavalla käyttämättä differentiaaliyhtälöä?  Käyrää voitaisiin approksimoida murtoviivalla, jossa viivan solmupisteet sijaitsevat pinnalla, ja minimoida murtoviivan pituus pitäen muuttujina solmupisteiden koordinaatteja. Tämä johtaa moniulotteiseen minimointiprobleemaan, mutta yleensä laskentaohjelmissa on valmiiksi ohjelmoituina algoritmit tällaisten probleemojen ratkaisemiseen.

Jos pinnan parametriesitys on
\[
s(u,v) = (x(u,v),y(u,v),z(u,v)),
\]
voidaan $n$-osaisen murtoviivan solmupisteitä merkitä
\[
s(u_k,v_k) = (x(u_k,v_k),y(u_k,v_k),z(u_k,v_k)), \quad k=0,\dots,n.
\]
Indeksin arvoilla $k=0$ ja $k=n$ saadaan murtoviivan kiinteät päätepisteet $s(u_0,v_0)$ ja $s(u_n,v_n)$, mutta muut parametriarvot $(u_k,v_k)$, $k=1,\dots,n-1$, ovat minimointiprobleeman muuttujia.  Kyseessä on siten $2(n-1)$-ulotteinen minimointiprobleema. Minimoitava funktio — probleeman kohdefunktio — on murtoviivan pituus:
\[
L(u_1,\dots,u_{n-1},v_1,\dots,v_{n-1}) = \sum_{k=1}^n \lVert s(u_k,v_k) - s(u_{k-1},v_{k-1}) \rVert.
\]
Tässä $\lVert s(u_k,v_k) - s(u_{k-1},v_{k-1}) \rVert$ tarkoittaa murtoviivan $k$:nnen osan pituutta.

Yleisesti käytetty minimointialgoritmi ei kuitenkaan suoriudu pelkästään tällä tavalla annetusta minimointitehtävästä, vaan sille on lisäksi annettava muuttujien alkuarvot. Näistä lähtien algoritmi laskee, mihin suuntaan arvoja on muutettava, jotta kohdefunktion arvo pienenee. Muutetut arvot otetaan uusiksi lähtöarvoiksi ja kierros toistetaan. Näin jatketaan, kunnes kohdefunktion arvo ei enää pienene.

Tilanne on periaatteessa samanlainen kuin yhden muuttujan funktion minimikohdan etsiminen lähtemällä jostakin pisteestä ja katsomalla derivaatan avulla, kumpaan suuntaan on siirryttävä, jotta funktion arvo pienenee. Toistamalla askelta ajaudutaan johonkin minimikohtaan, mutta tämä ei välttämättä ole globaali minimi. Lähtöarvon valinnasta siten riippuu, löydetäänkö globaali minimi vai jokin muu.

Funktion $f(x)=\frac{1}{2}x^4+\frac{1}{3}x^3-3x^2$ minimin etsiminen aloittamalla pisteestä $x=0.5$

Moniulotteisessa minimointiprobleemassa tilanne on samanlainen. Alkuarvojen valinnasta riippuu, mikä minimi löydetään. Toisaalta alkuarvojen valinta ei ole yksinkertaista, jos etsittävästä käyrästä ei enempää tiedetä. Usein alkuarvot valitaankin satunnaisesti ja katsotaan, millaisia tuloksia eri tapauksissa saadaan.

Esitetty minimointiprobeeman määrittely on yksinkertainen ja luonnollinen, mutta se sisältää sudenkuopan. Murtoviivan minimipituus nimittäin saadaan kasaamalla kaikki solmupisteet käyrän alku- (tai loppu-) pisteeseen, jolloin murtoviivaan jää vain yksi osa, jonka pituus ei ole $=0$. Tämä on päätepisteitä yhdistävä jänne, joka ei (yleensä) sijaitse pinnalla. Tarvitaan siis jokin lisäehto, joka takaa, että murtoviivan osat eivät lyhene liiaksi. Tällaiseksi kelpaa esimerkiksi vaatimus, että murtoviivan kaikkien osien pituudet $\lVert s(u_k,v_k) - s(u_{k-1},v_{k-1}) \rVert$, $k=1,\dots,n$, ovat keskenään yhtä suuria. Lisäehdot ovat tavanomaisia minimointiprobleemoissa ja valmiiksi ohjelmoiduissa algoritmeissa tällaisia onkin mahdollista antaa.

Lieriön geodeettiset käyrät ovat ruuviviivoja. Alla olevissa kuvissa on kolme vaihtoehtoa samojen päätepisteiden välisistä käyristä. Nämä on saatu valitsemalla toistuvasti satunnaiset minimoinnin alkuarvot 30-osaiselle murtoviivalle.


Ei kommentteja: