Matematické Fórum

CzechMan · 01. 10. 2007 00:52 — Editoval Kondr (03. 10. 2007 15:25)

Ony ty algoritmy jsou vůbec kapitolou samy pro sebe.
Narazil jsem na aproximační metodu výpočtu hodnoty třetí odmocniny z čísla.
Nebudu ho sem psát (no pravděpodobně ho i znáte :) ), ale přepíšu do podoby posloupnosti.

Chceme znát $\sqrt[3]{X}$ .

Mějme $\textstyle (a_n)_{n=1}^{\infty}$
Položme pak:
$a_1=X$
Rekurentně je aproximace vyjádřená:
$\Large a_n=a_{n-1}+\frac{\frac{a_1}{a_{n-1}^2}-a_{n-1}}{3}$

Posloupnost by měla konvergovat právě k $\sqrt[3]{X}$ , tedy
$\lim_{n \to \infty}a_n\ =\ \sqrt[3]{X}$

Dá se tento vztah dokázat?(nebo aspoň-jak se k němu mohlo dojít?) Možná, kdyby existoval vzorec pro n-tý člen, což pochybuju.

Kondr · 11. 10. 2007 11:48

Položme $x^3=X$ , $a_{n-1}=x(1+t)$ . Předpokládejme, že t>0. Dosazením do vzorce pro a_n máme
$a_n=x\left(\frac23(1+t)+\frac13\cdot\frac1{(1+t)^2}\right)$ .
Druhý sčítanec v závorce je menší než 1/3, součet v závorce je menší než 1+(2t/3).
Pomocí AG nerovnosti nebo derivací snadno nahlédneme, že součet v závorce je větší než 1. Proto každým krokem algorimu relativní odchylka zůstává kladná a zmenšuje se s kvocientem nejvýše 2/3, proto v některém kroku bude libovolně malá.

Pro t<0 je a_n>x (opět AG nerovnost), od dalšího kroku se pak budou odchylky chovat tak, jak bylo popsáno výše.

Algoritmus lze zefektivnit tak, že jako a_1 zvolíme nějaký lepší odhad třetí odmocniny (třeba 2^((počet biitů X)/3))).

andrew · 11. 10. 2007 14:00 — Editoval andrew (11. 10. 2007 14:02)

Dá se tento vztah dokázat?

Imho ten predpis ti vypadne kdyz pouzijes Newtonovu metodu na nalezeni korene nelinearni rovnice
$f(x) = x^3 - a = 0, a>0$ a pro $a<0$ to bude obdobne...

Matematické Fórum

#1 01. 10. 2007 00:52 — Editoval Kondr (03. 10. 2007 15:25)

Algoritmus pro třetí odmocninu

#2 11. 10. 2007 11:48

Re: Algoritmus pro třetí odmocninu

#3 11. 10. 2007 14:00 — Editoval andrew (11. 10. 2007 14:02)

Re: Algoritmus pro třetí odmocninu