基于數值分析思想對多項式求值的原理和應用進行探究

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

一般的求解會將特定的x代入到上式中，一個一個的計算，共需要花費10次的乘法和4次加法運算，但是我們可以通過霍納方法對多項式進行組合計算，在需要每秒對多個不同輸入的x多次計算多項式對應的值時，該方法可以極大的提高計算效率。

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

        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）

這里的多項式是從低階向高階項分解，關于x的冪次被分解為余下的多項式的乘積，然后可以從括號內層向外層進行求值計算。

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

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

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");
}

總結：

通過對多項式求值的計算，讓我更深刻的理解到在計算領域計算效率往往可以從最基礎的理論找到突破點，結果卻會產生巨大的效果。

其中，多項式求值的原理和應用體現了科學計算方法的最重要的特征：

（1）計算機在做簡單計算的時候速度很快；

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

最后，在對多項式求值理論進行研究后，我們將其推廣到更一般的形式，以適應更多實際的應用：

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

其中，r1，r2,r3,r4表示基點，當r1,r2,r3,r4為0時，則就是上式（1）中的特殊形式。