基于最佳一次逼近多項式的求平方根迭代法

何斯日古楞

(呼和浩特民族學(xué)院 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，內(nèi)蒙古 呼和浩特 010051)

平方根計算雖是一種古老的問題[1]，但被廣泛用于現(xiàn)代數(shù)學(xué)和工程計算。算數(shù)平方根計算主要用于信號處理[2]、微機(jī)保護(hù)裝置[3]和微處理器計算[4]等。嵌入式微處理器無專門的開方指令，需借助牛頓迭代法和逐位循環(huán)[5]等算法實(shí)現(xiàn)開方。文獻(xiàn)[2～5]研究開方算法的硬件實(shí)現(xiàn)，然而相關(guān)理論分析甚少。文獻(xiàn)[6]介紹了基于二項展開式的逐位近似算法及其發(fā)展歷史。

1 迭代公式的推導(dǎo)以及收斂分析

定理1[7,8]設(shè)f(x)是區(qū)間[α,β]上的連續(xù)函數(shù)，令Hn表示所有次數(shù)不超過n的多項式以及零多項式構(gòu)成的集合。P(x)∈Hn是f(x)的最佳逼近多項式的充要條件是P(x)在[α,β]上至少有n+2個輪流為“正”“負(fù)” 的偏差點(diǎn)，即有n+2個點(diǎn)α≤x1

設(shè)a>0，xk-1，xk為二次方程f(x)=x2-a=0的兩個已知近似根，且不妨假設(shè)xk-10，故根據(jù)定理1可知，f(x)=x2-a在區(qū)間[xk-1,xk]上有最佳一次逼近多項式P(x)=a0+a1x，且至少有3個點(diǎn)xk-1≤y1

因此，函數(shù)g(x)=P(x)-f(x)滿足g(y1)=g(y3).又由于f″(x)在[xk-1,xk]上不變號，故f′(x)單調(diào)。于是用羅爾中值定理知，g′(x)=a1-f′(x)在(xk-1,xk)內(nèi)只有一個零點(diǎn)，記為y2，即

g′(y2)=a1-f′(y2)=0.另外兩個偏差點(diǎn)必在區(qū)間端點(diǎn)，即y1=xk-1，y3=xk，且滿足

P(y1)-f(y1)=P(y3)-f(y3)=-[P(y2)-f(y2)]

于是，解得

進(jìn)而，求解P(x)=0可得迭代公式(1)

(1)

證明 由迭代公式(1)可得

(3)

又從迭代公式(1)和(3)式，有

(4)

據(jù)此反復(fù)遞推，得

(5)

又由假設(shè)x0=x1，知e0=e1.因此，對(6)式反復(fù)遞推，有

即

證明 對已知迭代值xk-1,xk，二次方程f(x)=x2-a=0的弦截格式為

相應(yīng)的誤差方程為

此外，對給定的迭代值xk-1,xk，誤差方程 (2) 可寫成

進(jìn)一步，有

注意到，利用定理3的結(jié)論，可得

進(jìn)而，有

2 數(shù)值例子與結(jié)論

表的數(shù)值計算結(jié)果