Bernstein多項式的移位-加算法

谷 峰

(浙江經濟職業技術學院，浙江 杭州 310018)

在高級計算系統中，可以很容易地找到Bernstein多項式的算法[3]。 例如 ，在 Mathematica中 ，(t)可以用BernsteinBasis[n，i，t]計算。用高級語言編程計算 Bernstein多項式也非常容易。本文討論如何在基本計算系統(僅具備移位、加和邏輯運算功能的計算系統)中計算Bernstein多項式。基本計算系統存在于許多系統中，例如工業控制系統、軍事應用系統、醫療應用系統等。典型的有單片機系統和FPGA(Field Programmable Gate Arrays)等。

CORDIC算法是可計算多種基本初等函數的移位-加算法[4-6]。參考文獻[7-8]擴展了CORDIC算法，其收斂性和誤差估計在參考文獻[7]中做了分析。隨著硬件技術的發展，這些快速統一移位-加算法可以用硬件實現，而且不需使用乘法器[9]，成本較低，也可以用匯編語言編程實現。本文提出一個基于CORDIC算法的Bernstein多項式移位-加算法。

1 算法的描述

[7]中定義了符號函數和正規序列：

設ε為誤差上界。Bernstein多項式的移位-加算法包含一個主程序和一個子程序：

注：(1)算法中僅使用了移位運算(即 2-i×t)和加法運算。

(2)迭代次數N根據后面的定理1確定。

(4)計算實踐表明子程序運行的迭代次數一般不超過28步，因此是個快速算法。

2 算法的收斂性和誤差分析

當 n充分大時，有 xn+1≈x，zn+1≈xy。

subprogram UV(u，v，ε)即基于迭代過程(1)。

(1)迭代過程(1)中的{xi}收斂于 x，且有|x-xN|≤δN-1。

(2)迭代過程(1)中的{zi}收斂于xy，且有誤差估計|zN-xy|≤|y|(1+|x|)(1+δN)δN。

(3)subprogram UV(u，v，ε)中的{zi}收斂于 xy，其計算誤差不大于ε。

(3)當u=0或v=0時，程序輸出結果 uv=0。當uv≠0時，u 和 v 在 subprogram UV(u，v，ε)中預處理為 uv=s×2m×u1v1。 這里 s為 1 或-1。u1和 v1在(0，1]中。 由(2)，計算結果 z′N有|z′N-u1v1|＜|u1|(1+|v1|)·δN-1≤2δN-1＜δN-2；迭代次數 N 滿足δN-2≤2-m×ε。 所以最終結果 zN=s×2m×z′N滿足|zN-uv|＜2m×δN-2≤ε。 證畢。定理 2 主程序 Bernstein(n，t，ε)的輸出值 Bn

j(t)(j=0，…，n)是n次Bernstein多項式的計算值。計算誤差上界是ε。

3 數值實驗

給定誤差上界ε=0.000 000 5，用本文給出的算法計算三次Bernstein多項式(t)(j=0，1，2，3)的數值。 計算值見表 1。 subprogram UV(u，v，ε)中的迭代次數不大于28。三次Bernstein多項式的函數值列表如表2所示。由此可見計算誤差符合要求。

參考文獻

[1]NATARAJ P S V，AROUNASSALAME M.A new subdivision algorithm forthe bernstein polynomialapproach to global optimization[J].International Journal of Automation and Computing， 2007，4(4):342-352.

[2]FARIN G.Curves and surfaces for computer-aided geometric design:a practical guide， 4th Ed.Academic Press， San Diego，1997.

[3]FENG Jieqing，PENG Qunsheng.Fast algorithm for composition of the bernstein polynomials[J].Journal of Computer-Aided Design&Computer Graophics， 2001，13(2).

[4]VOLDER J E.The CORDIC computing technique[J].IRE Transactions on Electronic Computers， 1959，8(9):330-334.

[5]MULLER J M.Elementary functions，algorithms and implementation.BirkhauserBoston， 1stedition，1997.2nd edition，2006:133-156.

[6]EKLUND N.CORDIC:elementary function computation using recursive sequences [C].InternationalConference on Technology，1998.

[7]GU Feng.Convergence and error estimation of coordinate rotating algorithm and its expansion[J].Chinese Journal of Numerical Mathematics and Applications， 2006，28(2):1-9.

[8]HU Xiaobo， HARBER R， BASS S.Expanding the range of convergence of the CORDIC algorithm[J].IEEE Transactions on Computers， 1991，40(1):13-21.

[9]ANDRAKA R.A survey of CORDIC algorithms for FPGA based computers[C].In Proceedings of the 1998 ACM/SIGDA Sixth International Symposium on Field Programmable Gate Arrays(FPGA)1998:191-200.

表1 三次Bernstein多項式的計算值

表2 三次Bernstein多項式的函數值