基于數(shù)值分析思想對多項(xiàng)式求值的原理和應(yīng)用進(jìn)行探究

摘要：多項(xiàng)式是由多個(gè)單項(xiàng)（符號項(xiàng)如：5x或者常數(shù)項(xiàng)4）通過四則運(yùn)算組合起來的式子,如P(x)=2x^4+3x^3-3x^2+5x-1

一般的求解會(huì)將特定的x代入到上式中，一個(gè)一個(gè)的計(jì)算，共需要花費(fèi)10次的乘法和4次加法運(yùn)算，但是我們可以通過霍納方法對多項(xiàng)式進(jìn)行組合計(jì)算，在需要每秒對多個(gè)不同輸入的x多次計(jì)算多項(xiàng)式對應(yīng)的值時(shí)，該方法可以極大的提高計(jì)算效率。

原理：采用霍納方法對上式進(jìn)行分解步驟如下：

        P(x) = -1+x(5-3x+3x^2+2x^3)

           = -1+x(5+x(-3+3x+2x^2))

           = -1+x(5+x(-3+x(3+2x)))

           = -1+x*(5+x*(-3+x*(3+2*x)))                 （1）

這里的多項(xiàng)式是從低階向高階項(xiàng)分解，關(guān)于x的冪次被分解為余下的多項(xiàng)式的乘積，然后可以從括號內(nèi)層向外層進(jìn)行求值計(jì)算。

算法實(shí)現(xiàn)：本文采用遞歸方式求解多項(xiàng)式，其中向量a 存儲(chǔ)的是從低次到高次多項(xiàng)式的常數(shù)項(xiàng)值，x為變量，n為多項(xiàng)式的次數(shù)，最開始為0

template < class T>
inline T Algorithm::polynomial(vector<T > a, T x, int n) //可定義模板類和模板函數(shù) //多項(xiàng)式相加
{
if (n < a.size() - 1)
{
return a[n] + polynomial(a, x, n + 1)*x;
}
else
{
return a[n]; //遞歸終止條件：當(dāng)n等于最大值的前個(gè)數(shù)是，遞歸截止
}
}

void main()
{
Algorithm testPloy;
vector<double> a;
double t;
cin >> t;
while (t)
{
a.push_back(t);
cin >> t;
}
cout<<testPloy.polynomial(a, 0.5, 0);
cout << endl;
system("pause");
}

總結(jié)：

通過對多項(xiàng)式求值的計(jì)算，讓我更深刻的理解到在計(jì)算領(lǐng)域計(jì)算效率往往可以從最基礎(chǔ)的理論找到突破點(diǎn)，結(jié)果卻會(huì)產(chǎn)生巨大的效果。

其中，多項(xiàng)式求值的原理和應(yīng)用體現(xiàn)了科學(xué)計(jì)算方法的最重要的特征：

（1）計(jì)算機(jī)在做簡單計(jì)算的時(shí)候速度很快；

（2）由于簡單計(jì)算可能會(huì)被進(jìn)行多次，盡可能有效地進(jìn)行簡單計(jì)算，可以大大提高計(jì)算的效率；

最后，在對多項(xiàng)式求值理論進(jìn)行研究后，我們將其推廣到更一般的形式，以適應(yīng)更多實(shí)際的應(yīng)用：

f(x)=c1+(x-r1)(c2+(x-r2)(c3+(x-r3)(c4+(x-r4)(c5))))

其中，r1，r2,r3,r4表示基點(diǎn)，當(dāng)r1,r2,r3,r4為0時(shí)，則就是上式（1）中的特殊形式。