摘要:多項式是由多個單項(符號項如: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的冪次被分解為余下的多項式的乘積,然后可以從括號內層向外層進行求值計算。
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)中的特殊形式。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。