Wednesday, May 27, 2020

Initialization fix for an old simple square root algorithm


. . . it's multiple proven that in general situation the iteration formula :
\[\sqrt{A}\leftarrow a_{n+1}=\frac{\frac{A}{a_n}+a_n}2\]
gives the fastest convergence , initialization :
\[a_0=A\rightarrow a_1=a_{1_1}=\frac{A+1}2\]

however i just explored a different approach with iterative formula :
\[\sqrt{A}\leftarrow a_{n+1}=\frac{2Aa_n}{A+a_n^2}=\frac2{\frac1{a_n}+\frac{a_n}A}=\frac{2A}{\frac A{a_n}+a_n}=\frac A{\frac{\frac{A}{a_n}+a_n}2}\]
which has an initialization :
\[a_0=1\rightarrow a_1=a_{1_2}=\frac{2A}{A+1}=1+\frac{A-1}{A+1}\]

the "Old" initialization gives quite large positive error ... while my "Latest" initialization gives quite large negative error . . . however the both averaged gives more reasonable positive error , where the :
\[a_1=a_{1_3}=\frac{a_{1_1}+a_{1_2}}2=\frac{A+1}4+\frac{A}{A+1}\]

while for each \(a_n\) where \(n>1\) the first iteration formula on this page applies

...

yet a lesser negative error is got by combining the two first initializations as :
\[a_1=a_{1_4}=\frac{2a_{1_1}a_{1_2}}{a_{1_1}+a_{1_2}}=\frac1{\frac{A+1}{4A}+\frac1{A+1}}=\frac{A}{a_{1_3}}\]

...

+ yet a significantly lesser positive error is got by combining the two last initializations as :
\[a_1=a_{1_5}=\frac{a_{1_3}+a_{1_4}}2=\frac{a_{1_3}+\frac{A}{a_{1_3}}}2\]

the last formula is actually the value of \(a_2\) for \(a_{1_3}\) . . . so , . . .

. . . anyway it give us quite accurate estimation formula for the near A=1 , as :

\[\sqrt{A}≈a=\frac{\frac{A+1}4+\frac A{A+1}+\frac A{\frac{A+1}4+\frac A{A+1}}}2\]

the error ≤ about 5% - from \(\frac1{20}...20\)


[Eop]

No comments: