Kezdőlap


Feladat:	F.3035	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Braun Gábor , Elek Péter , Erdélyi László , Farkas Illés , Kovács Baldvin , Kováts Antal , Rozmán András , Ruzsa Gábor , Séllei Béla , Szádeczky-Kardoss Szabolcs , Szőke Ervin , Valkó Benedek , Varga Tamás , Véber Miklós
Füzet:	1995/április, 219 - 222. oldal		PDF \| MathML
Témakör(ök):	Sorozat határértéke, Rekurzív sorozatok, Feladat
Hivatkozás(ok):	Feladatok: 1994/november: F.3035

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Ha $A = 0$ , akkor a sorozat definíciója értelmetlen. Ha $A > 0$ , akkor a sorozat minden eleme pozitív ( $x_{1}$ pozitív, és a rekurzió alapján $x_{n}$ pozitivitásából következik $x_{n + 1}$ pozitivitása is). Ha $A < 0$ , akkor a sorozat minden eleme negatív. Ezekben az esetekben tehát a rekurzió értelmes.
Az esetszétválasztások elkerülése érdekében legyen $y_{n} = \frac{x_{n}}{\sqrt[3]{A}}$ . A kérdés az, hogy az $(y_{n})$ sorozat tetszőleges pontossággal megközelíti-e az $1$ -et (azaz $y_{n} \to 1$ ).
Azt állítjuk, hogy az $(y_{n})$ sorozatra a következő rekurzió teljesül:

\begin{matrix} y_{1} = ∣ A ∣^{\frac{2}{3}}, y_{n + 1} = \frac{y_{n} + \frac{1}{y_{n}^{2}}}{2} . \end{matrix}

(2)

Az első állítás egyszerűen következik

y_{1}

definíciójából. A másodikhoz írjunk (1)-ben

x_{n}

helyére

\sqrt[3]{A} y_{n}

-et,

y_{n + 1}

helyére

\sqrt[3]{A} x_{n + 1}

-et:

\begin{matrix} \sqrt[3]{A} y_{n + 1} = \frac{\sqrt[3]{A} y_{n} + \frac{A}{{(\sqrt[3]{A} y_{n})}^{2}}}{2} . \end{matrix}

Ezt

\sqrt[3]{A}

-val osztva éppen (2)-t kapjuk. (Észrevehető, hogy a feladatot tulajdonképpen az

A = 1

esetre vezettük vissza.)
Mielőtt a konvergencia bizonyításához hozzákezdenénk, először az

(y_{n})

sorozat elemeire bizonyítunk két becslést.
I. Az

(y_{n})

sorozat minden eleme pozitív. Ez következik az első elem pozitív voltából.
II. Ha

n \geq 2

, akkor

y_{n} > \frac{9}{10}

. A rekurzió, valamint a számtani és mértani közép közötti egyenlőtlenség alapján ugyanis

\begin{matrix} y_{n} = \frac{y_{n - 1} + \frac{1}{y_{n - 1}^{2}}}{2} = \frac{3}{2} \cdot \frac{\frac{y_{n - 1}}{2} + \frac{y_{n - 1}}{2} + \frac{1}{y_{n - 1}^{2}}}{3} \geq \frac{3}{2} \sqrt[3]{\frac{y_{n - 1}}{2} \cdot \frac{y_{n - 1}}{2} \cdot \frac{1}{y_{n - 1}^{2}}} = \frac{3}{2} \sqrt[3]{\frac{1}{4}} > \frac{9}{10} . \end{matrix}

Vizsgáljuk meg, mi az összefüggés

y_{n}

és

y_{n + 1}

1-től való távolsága között. A rekurzió alapján

\begin{matrix} \begin{matrix} | y_{n + 1} - 1 | = | \frac{y_{n} + \frac{1}{y_{n}^{2}}}{2} - 1 | = | \frac{y_{n}^{3} - 2 y_{n}^{2} + 1}{2 y_{n}^{2}} | = | \frac{y_{n}^{2} - y_{n} - 1}{2 y_{n}^{2}} | \cdot | y_{n} - 1 | = \\ = \frac{1}{2} | 1 - \frac{1}{y_{n}} - \frac{1}{y_{n}^{2}} | \cdot | y_{n} - 1 | = \frac{1}{2} | \frac{5}{4} - {(\frac{1}{y_{n}} + \frac{1}{2})}^{2} | \cdot | y_{n} - 1 | . \end{matrix} \end{matrix}

n \geq 2

, akkor

y_{n} > \frac{9}{10}

, ezért

0 < \frac{1}{y_{n}} < \frac{10}{9}

és

\begin{matrix} \frac{5}{4} \geq \frac{5}{4} - {(\frac{1}{y_{n}} + \frac{1}{2})}^{2} > \frac{5}{4} - {(\frac{10}{9} + \frac{1}{2})}^{2} > - \frac{3}{2} . \end{matrix}

Mindezek alapján pedig

\begin{matrix} \begin{matrix} | \frac{5}{4} - {(\frac{1}{y_{n}} + \frac{1}{2})}^{2} | < \frac{3}{2}, \\ | y_{n + 1} - 1 | < \frac{3}{4} | y_{n} - 1 | . \end{matrix} \end{matrix}

Ebből az eredményből teljes indukcióval azonnal bebizonyítható, hogy

n > 2

esetén

\begin{matrix} | y_{n} - 1 | < | y_{2} - 1 | \cdot {(\frac{3}{4})}^{n - 2} . \end{matrix}

A jobb oldalon álló mértani sorozat 0-hoz tart, mert a hányadosa 1-nél kisebb abszolút értékű, következésképpen

y_{n} - 1

is 0-hoz tart,

y_{n}

1-hez, végül

x_{n}

\sqrt[3]{A}

-hoz tart.
Az

(x_{n})

sorozat tehát

\sqrt[3]{A}

-hoz tart minden olyan esetben, amikor

A \neq 0

Braun Gábor (Budapest, Szent István Gimn., II. o.t.)

Megjegyzések. 1. Ha

y

már ,,közel'' van az 1-hez, akkor a hiba minden lépésnél körülbelül a felére csökken, mert

| 1 - \frac{1}{y_{n}} - \frac{1}{y_{n}^{2}} |

értéke is körülbelül 1. Ez a ,,sebesség'' még mindig sokkal kisebb, mint a négyzetgyökvonáshoz használt rekurzió sebessége, ahol (kis hiba esetén) a hiba minden lépésben körülbelül az előző hiba négyzetének (!) felére csökken. Ez azt is jelenti, hogy a sorozat következő tagjának legalább kétszer annyi helyes jegye van.
2. Ha

k

-adik gyököt (

k \geq 4

) akarnánk vonni az

\begin{matrix} x_{n + 1} = \frac{x_{n} + \frac{A}{x_{n}^{k - 1}}}{2} \end{matrix}

rekurzióval, érdekes eredményre jutnánk. Ez a sorozat ugyanis

k = 4

-re még konvergens (bár a konvergencia nagyon lassú),

k > 4

esetén azonban már mindig divergens, kivéve azt az esetet, amikor

x_{1} = \sqrt[k]{A}

.
3. Tegyük fel, hogy

x = \sqrt[3]{A} + ε

és

ε

,,kicsi'' abszolút értékű. Ekkor

\begin{matrix} \frac{A}{x^{2}} = \frac{A}{{(\sqrt[3]{A} + ε)}^{2}} = \frac{A {(\sqrt[3]{A} - ε)}^{2}}{{({\sqrt[3]{A}}^{2} - ε^{2})}^{2}} \approx \frac{A ({\sqrt[3]{A}}^{2} - 2 ε \sqrt[3]{A})}{{\sqrt[3]{A}}^{4}} = \sqrt[3]{A} - 2 ε . \end{matrix}

\approx

jel azt jelenti, hogy a két mennyiség különbsége sokkal kisebb, mint

ε

.) A kapott közelítéshez

2 x = 2 \sqrt[3]{A} + 2 ε

-t hozzáadva, majd ebből

\sqrt[3]{A}

-t kifejezve:

\begin{matrix} \sqrt[3]{A} \approx \frac{2 x + \frac{A}{x^{2}}}{3} . \end{matrix}

Ez az eredmény azt mutatja, hogy inkább érdemes az

\begin{matrix} x_{n + 1} = \frac{2 x_{n} + \frac{A}{x_{n}^{2}}}{3} \end{matrix}

rekurziót használni.
Be lehet bizonyítani, hogy az így felírt sorozat

\sqrt[3]{A}

-hoz tart, és a helyes jegyek száma minden iterációnál megduplázódik.
A két sorozat konvergencia-sebessége közötti különbség szemléltetésére álljanak itt azok az értékek, amelyeket

A = 8

köbgyökének becslésére adnak:

\begin{matrix} \begin{matrix} x_{n + 1} = \frac{x_{n} + \frac{A}{x_{n}^{2}}}{2} & x_{n + 1} = \frac{2 x_{n} + \frac{A}{x_{n}^{2}}}{3} \\ n = 1 & 8.000000000 & 8.000000000 \\ n = 2 & 4.062500000 & 5.375000000 \\ n = 3 & 2.273616864 & 3.675635479 \\ n = 4 & 1.910602556 & 2.647803979 \\ n = 5 & 2.051070966 & 2.145564608 \\ n = 6 & 1.976356160 & 2.009652410 \\ n = 7 & 2.012247902 & 2.000046287 \\ n = 8 & 1.993987646 & 2.000000001 \\ n = 9 & 2.003033397 & 2.000000000 \\ n = 10 & 1.998490189 & 2.000000000 \end{matrix} \end{matrix}

4. Általában

k

-adik gyökvonásra használható az

\begin{matrix} x_{n + 1} = \frac{(k - 1) x_{n} + \frac{A}{x_{n}^{k - 1}}}{k} \end{matrix}

rekurzió.
Ennek a rekurziónak megvan az a jó tulajdonsága, hogy a sorozat elemei a második elemtől kezdve nagyobbak

\sqrt[k]{A}

-nál, monoton fogynak, a helyes jegyek száma minden lépésben körülbelül megduplázódik.