kontakt:
gornicki59@gmail.com
Procedurę, która wymaga wywołania samej siebie, nazywamy rekurencją. Tego typu sytuacje występują w informatyce i matematyce dość często, klasycznym przykładem jest rekurencyjna definicja ciągu Fibonacciego. W tym artykule przyglądamy się zbieżności kilku ciągów rekurencyjnych generowanych przez klasyczne średnie dwóch liczb dodatnich. Będziemy się przyglądać temu zagadnieniu od strony czysto analitycznej, warto jednak zaznaczyć, że poruszone tu kwestie mają pewne odzwierciedlenie w metodach numerycznych.
Ciąg Fibonacciego określony jest przez rekurencję \(F_0=0,\) \(F_1=1\) i \(F_{n+1}=F_n+F_{n-1}\) dla \(n>1.\)
Pisaliśmy o nim np. w \(\Delta^1_{79}\), \(\Delta^6_{20}\), \(\Delta^4_{22}\).
Ustalmy \(0<a<b.\) Jak wiadomo, zachodzą wówczas nierówności \[a<\frac{2ab}{a+b}<\sqrt{ab}<\frac{a+b}{2}<b \tag{1}\] (przypadku \(a=b\) nie będziemy dyskutować, bo wtedy wszystkie te wielkości są równe). Niech \(a_0=a,\) \(b_0=b.\) Ciągi \(\{a_n\}\) i \(\{b_n\}\) określamy wzorami (\({n=0,1,2,\ldots}\)):
Przy okazji przedstawienia różnych średnich zapytajmy, jaka jest średnia prędkość podróży samochodem, który pierwszą połowę drogi pokonuje z prędkością \(v_1,\) a drugą z prędkością \(v_2.\)
Odpowiedzią jest właśnie \(\frac{2v_1v_2}{v_1+v_2}.\)
\(a_{n+1}=\dfrac{2a_nb_n}{a_n+b_n},~~b_{n+1}=\dfrac{a_n+b_n}{2},\)
\(a_{n+1}=\sqrt{a_nb_n},~~b_{n+1}=\dfrac{a_n+b_n}{2},\)
\(a_{n+1}=\dfrac{2a_nb_n}{a_n+b_n},~~b_{n+1}=\sqrt{a_nb_n},\)
\(a_{n+1}=\dfrac{a_n+b_n}{2},~~b_{n+1}=\sqrt{a_{n+1}b_n}=\sqrt{\dfrac{a_n+b_n}{2}\cdot b_n}.\)
Problem. Czy ciągi \(\{a_n\}\) i \(\{b_n\}\) są zbieżne, a jeśli tak, to jakie są ich granice?
Najpierw pokażemy, że w każdym z tych przypadków ciągi \(\{a_n\}\) i \(\{b_n\}\) są zbieżne oraz \(\lim a_n =\lim b_n.\) Zrobimy to niejako „za jednym zamachem”, mając na uwadze nierówności (1). W jasny sposób wynika z nich, że w każdym z przypadków (a)–(d) dla dowolnej liczby naturalnej \(n\) zachodzi \[a_n<a_{n+1}<b_{n+1}<b_n,\tag{2}\] Udowodnimy, że w każdym z przypadków (a)–(d) zachodzi ponadto \[\vert a_{n+1}-b_{n+1}\vert <\frac{1}{2}\vert a_n - b_n\vert.\tag{3}\] Istotnie, w przypadkach (a)–(c) liczby \(a_{n+1}\) i \(b_{n+1}\) leżą w przedziale \(\left(a_n,\frac{a_n+b_n}{2}\right]\) o długości \(\frac12\vert a_n-b_n\vert.\) W przypadku (d) liczby te leżą w przedziale \(\left[\frac{a_n+b_n}{2},b_n\right)\) o tej samej długości.
Dla przykładu, w przypadku (a) nierówność (2) przybiera postać \[a_n<\tfrac{2a_nb_n}{a_n+b_n}<\tfrac{a_n+b_n}{2}<b_n,\] co wynika z (1). Skrajne nierówności można łatwo uzasadnić: \[\begin{gathered} a_n=\tfrac{2a_nb_n}{b_n+b_n}<\tfrac{2a_nb_n}{a_n+b_n},\\ \tfrac{1}{2}(a_n+b_n)<\tfrac{1}{2}(b_n+b_n)=b_n. \end{gathered}\]
Kontynuując przykład, w przypadku (a) liczby \(a_{n+1}=\frac{2a_nb_n}{a_n+b_n}\) oraz \(b_{n+1}=\frac{a_n+b_n}{2}\) mieszczą się w przedziale \(\left(a_n,\frac{a_n+b_n}{2}\right].\)
Oczywiście warunek (2) gwarantuje zbieżność występujących tam ciągów, ale nas interesuje wynikająca z niego zależność \([a_n,b_n]\supset[a_{n+1},b_{n+1}].\) Z warunku (3) wynika, że długości tych przedziałów dążą do zera. Zatem w każdym przypadku twierdzenie Cantora zapewnia, że przecięcie \([a,b]\cap [a_1,b_1]\cap\ldots\) zawiera dokładnie jeden punkt, który jest wspólną granicą ciągów \(\{a_n\}\) i \(\{b_n\}.\)
Twierdzenie (G. Cantor, 1880). Jeżeli \([a,b]\supset [a_1,b_1]\supset\ldots\) jest ciągiem niepustych domkniętych przedziałów w przestrzeni euklidesowej \(\mathbb{R},\) których długości dążą do zera, to przecięcie \([a,b]\cap [a_1,b_1]\cap\ldots\) zawiera dokładnie jeden punkt.
Pozostał problem wyznaczenia tych granic, jeśli jest to możliwe.
W sytuacji (a) mamy \(a_{n+1}b_{n+1}= a_nb_n =\ldots =a_1b_1=ab.\) Zatem jeśli \({\alpha =\lim a_n =\lim b_n},\) to \[\alpha ^2= \lim a_n \cdot \lim b_n = \lim (a_nb_n)= ab\] i \(\alpha = \sqrt{ab}.\) Niestety pozostałe przypadki są bardziej wymagające.
W przypadku (b) wspólną granicę ciągów \(\{a_n\}\) i \(\{b_n\}\) oznaczamy symbolem \(M(a,b),\) a w przypadku (c) symbolem \(N(a,b).\) Ponieważ w przypadku (c) \[\frac{1}{a_{n+1}}=\frac{1}{2}\bigg (\frac{1}{a_n}+\frac{1}{b_n}\bigg ),~~\frac{1}{b_{n+1}}=\sqrt{\frac{1}{a_n}\cdot\frac{1}{b_n}},\] więc granice \(M(\cdot,\cdot)\) i \(N(\cdot,\cdot)\) wiąże zależność \(M(\frac{1}{a},\frac{1}{b})=\frac{1}{N(a,b)}.\) Niestety dokładnej wartości tych granic nie potrafimy wyznaczyć! W 1800 roku Carl Gauss zauważył, że ciągi opisane wzorami (b) są bardzo szybko zbieżne, i pokazał, jak można je wykorzystać do obliczania przybliżonej wartości pewnych całek eliptycznych, których dokładnej wartości (na ogół) nie znamy. Gauss, mając 23 lata, wykazał równość \[\int_0^{\frac{\pi}{2}} \frac{dx}{\sqrt{a^2\sin^2x +b^2\cos^2x}} =\frac{1}{M(a,b)}\cdot\frac{\pi}{2}.\] W latach 1799–1800 Gauss podał, że w przypadku (d) wspólna granica ciągów \(\{a_n\},\) \(\{b_n\}\) jest równa \(\frac{\sqrt{b^2-a^2}}{\arccos \frac{a}{b}}.\) Wykażemy to na drodze elementarnych rozważań geometrycznych, korzystając z rozważań inspirowanych obserwacją Jacques’a Schwaba z 1813 roku (J. Schwab, Élémens de Géométrie, Premiére Partie, Géométrie Plane, Nancy, 1813):
O odkryciu Gaussa można przeczytać w artykule Jarosława Górnickiego w \(\Delta^6_{22}\).
Na temat zbieżności ciągów postaci (d) Gauss prowadził korespondencję z Johannem Pfaffem.
Niech \(P\) będzie \(n\)-kątem foremnym i niech \(P_1\) będzie \(2n\)-kątem foremnym, oba o tych samych obwodach. Jeżeli \(a\) i \(b\) są promieniami okręgów wpisanego i opisanego na wielokącie \(P,\) a \(a_1\) i \(b_1\) oznaczają analogiczne wielkości dla wielokąta \(P_1,\) to \(a_1=\frac{1}{2}(a+b),\) \(b_1=\sqrt{a_1b}.\)
Kreślimy trójkąt równoramienny \(OAB,\) w którym \(\vert OA\vert = \vert OB\vert = b\) i wysokość \(\vert OD\vert\) jest równa \(a\) (rys. 1). Niech \(\angle AOB =2\varphi.\) Na łuku okręgu o środku w punkcie \(O\) i promieniu \(b\) (opartym na kącie środkowym \(\angle AOB\)) wyznaczamy punkt \(C\) taki, że \(\vert AC\vert = \vert CB\vert.\)
Rys. 1
Rys. 2.
Niech \(A_1\) i \(B_1\) będą środkami odcinków \(AC\) i \(CB,\) odpowiednio. Niech \(D_1\) będzie punktem przecięcia odcinka \(A_1B_1\) z odcinkiem \(OC.\) Ponieważ \(D_1\) jest środkiem odcinka \(DC,\) więc \[\vert OD_1\vert = \frac{1}{2}(\vert OC\vert + \vert OD\vert )=\frac{1}{2}(b+a)=a_1.\] Trójkąt \(OA_1C\) jest prostokątny, a \(A_1 D_1\) jest jego wysokością, w związku z tym \(\frac{\vert OA_1\vert}{\vert OC\vert}=\frac{\vert OD_1 \vert}{\vert OA_1\vert},\) a zatem \[\vert OA_1\vert =\sqrt{\vert OD_1\vert\cdot\vert OC\vert}=\sqrt{a_1b}=b_1.\]
W ten sposób liczby \(a_1\) i \(b_1\) otrzymujemy z liczb \(a\) i \(b\) przy pomocy prostej konstrukcji geometrycznej (rys. 2). Jednocześnie w tej konstrukcji przeszliśmy od trójkąta \(OAB\) (gdzie \(\vert OA\vert = \vert OB\vert = b,\) \(\vert OD\vert = a\)) do trójkąta \(OA_1B_1\) (gdzie \(\vert OA_1\vert = \vert OB_1\vert = b_1,\) \(\vert OD_1\vert = a_1\)), w którym \[\angle A_1OB_1 = \frac{1}{2}\angle AOB = \varphi~~\hbox{i}~~\vert A_1B_1\vert =\frac{1}{2}\vert AB\vert.\] Powtarzając tę konstrukcję \(n\) razy, otrzymamy „wąski” trójkąt \(OA_nB_n,\) w którym \[\vert OA_n\vert = \vert OB_n\vert = b_n,~~\vert OD_n\vert = a_n,\] \[\angle A_nOB_n =\frac{1}{2^n}\angle AOB, ~~\vert A_nB_n\vert =\frac{1}{2^n}\vert AB\vert.\tag{4}\] Kreślimy teraz łuk okręgu o promieniu \(b_n,\) o środku w punkcie \(O\) i kącie środkowym \(\angle AOB=2\varphi.\) Dzieląc ten łuk na \(2^n\) przystających łuków, łącząc kolejno punkty podziału cięciwami, otrzymamy „wachlarz” złożony z \(2^n\) przystających kopii trójkąta \(A_nOB_n.\)
Dostajemy w ten sposób „wycinek wielokąta foremnego” mający \(2^n\) boków (o kącie środkowym \(\angle AOB\)), których łączna długość jest równa \(\vert AB\vert.\) Okręgi, o środku w punkcie \(O,\) opisane na tym wielokącie i wpisane w ten wielokąt mają promienie \(b_n\) i \(a_n,\) odpowiednio. Ponieważ długość łamanej (równa \(\vert AB\vert\)) zawiera się między długościami łuków okręgów wpisanego i opisanego, więc \[2\varphi\cdot a_n<\vert AB\vert < 2\varphi\cdot b_n.\]
Przy \(n\rightarrow\infty\) mamy \(\lim a_n=\lim b_n=\alpha,\) zatem \[\vert AB\vert = 2\varphi\cdot \alpha,\text{ skąd }{\alpha =\frac{\vert AB\vert}{2\varphi}=\frac{\vert AD\vert}{\varphi}}.\] Ponieważ trójkąt \(OAD\) jest prostokątny, więc \[\vert AD\vert =\sqrt{b^2-a^2} \text{ oraz } {\cos \varphi =\frac{\vert OD\vert}{b}=\frac{a}{b}},\] dlatego ostatecznie \[\alpha = \frac{\sqrt{b^2-a^2}}{\arccos \frac{a}{b}}.\]
Zauważmy jeszcze, że dla \(a=\tfrac{1}{2},\) \(b=\frac{1}{\sqrt{2}}\) otrzymujemy \(\alpha =\frac{2}{\pi},\) więc ciągi (d) pozwalają nam obliczać przybliżoną wartość \(\pi.\)
Czasem potrafimy coś obliczyć\(\ldots\) i to bez komputera!