久久影院久久香蕉国产线看观看,中文字幕久久精品,久久精品人人做人人爽电影

OpenCASCADE Interpolation - Lagrange

Posted on 2015-09-05 12:16 eryar 閱讀(2827) 評(píng)論(0) 編輯收藏引用所屬分類: 2.OpenCASCADE

OpenCASCADE Interpolation - Lagrange

Abstract. Power basis polynomial is the most simple polynomial function. It also be called power series. OpenCASCADE provides basic computation functions for polynomial functions, such as evaluate the result for a given polynomial, Lagrange interpolation, Hermite interpolation, .etc. The package named PLib, means Polynomial functions Library. The paper focus on the Lagrange interpolation usage of PLib.

Key Words. OpenCASCADE, PLib, Interpolation, Lagrange, 插值

1.Introduction

無窮級(jí)數(shù)是高等數(shù)學(xué)的一個(gè)重要組成部分，它是表示函數(shù)、研究函數(shù)性質(zhì)及進(jìn)行數(shù)值計(jì)算的一種工具。由高等數(shù)學(xué)中的無窮級(jí)數(shù)的概念可知，函數(shù)項(xiàng)級(jí)數(shù)中簡單而常見的一類級(jí)數(shù)就是各項(xiàng)都是冪函數(shù)的函數(shù)項(xiàng)級(jí)數(shù)即所謂的冪級(jí)數(shù)（Power Series）。因?yàn)閮缂?jí)數(shù)的形式簡單，易于理解，且可以高效計(jì)算曲線上的點(diǎn)及各階導(dǎo)數(shù)，所以在幾何造型中經(jīng)常用冪級(jí)數(shù)來近似表示曲線曲面。由于將函數(shù)展開成冪級(jí)數(shù)是有條件的，所有并不是所有的曲線曲面都可以用冪級(jí)數(shù)的多項(xiàng)式來逼近。

對(duì)無窮級(jí)數(shù)概念比較陌生的讀者可以把《高等數(shù)學(xué)》的書找出來翻翻看，重溫一下大學(xué)的時(shí)光。一打開做了筆記有點(diǎn)泛黃的舊書，就會(huì)回想起青澀的校園時(shí)光。

當(dāng)時(shí)學(xué)習(xí)《高等數(shù)學(xué)》的時(shí)候感覺很抽象難理解，因?yàn)闊o法將理論與實(shí)踐聯(lián)系起來，看不到直觀效果，有時(shí)也會(huì)冒出“學(xué)數(shù)學(xué)有什么用？”這種問題。當(dāng)你遇到相關(guān)的問題再去看國內(nèi)的教材時(shí)，覺得國內(nèi)的教材寫得還是很細(xì)致用心的。現(xiàn)在獲取信息已經(jīng)很便利了，如OpenCASCADE這個(gè)開源的庫，其TKMath工具箱可以看成是數(shù)值計(jì)算理論聯(lián)系實(shí)踐的一個(gè)具體實(shí)例。結(jié)合OpenCASCADE的源碼來對(duì)相關(guān)理論的學(xué)習(xí)，效率會(huì)事半功倍。

本文對(duì)冪級(jí)數(shù)的概念做簡單介紹，并結(jié)合源程序詳細(xì)說明OpenCASCADE中的PLib包中關(guān)于冪級(jí)數(shù)多項(xiàng)式的計(jì)算及Lagrange插值的用法。

2.Polynomial Evaluation

高等數(shù)學(xué)的書中把冪級(jí)數(shù)的重點(diǎn)落在如何將其他的函數(shù)展開成冪級(jí)數(shù)，即用冪級(jí)數(shù)來逼近函數(shù)，而沒有介紹如何用數(shù)值的方法來對(duì)冪級(jí)數(shù)進(jìn)行計(jì)算。在算法導(dǎo)論一書[2]中找到相關(guān)多項(xiàng)式的表示及計(jì)算的實(shí)現(xiàn)方法，給出了多項(xiàng)式在數(shù)據(jù)結(jié)構(gòu)上的表示方式及求值算法。對(duì)于一個(gè)冪級(jí)數(shù)多項(xiàng)式：

多項(xiàng)式的表示有系數(shù)表示法和點(diǎn)值表示法。系數(shù)表示法（Coefficient Representation）就是將多項(xiàng)式的系數(shù)組成一個(gè)向量來表示這個(gè)多項(xiàng)式。對(duì)用系數(shù)表示法表示的多項(xiàng)式的求值計(jì)算可以采用Horner法則，也是是著名的秦九韶算法。此算法的實(shí)現(xiàn)代碼在《The NURBS Book》[3]一書中給出了，此處略去，只給出OpenCASCADE中對(duì)冪級(jí)數(shù)多項(xiàng)式的計(jì)算的函數(shù)的使用。

void testPolynomialEvaluation(void)
{
    // evaluate 1 dimension polynmoial.
    Standard_Real aCoeff[3] = {2.0, 2.0, 3.0};

    Standard_Real aResult = 0.0;

    for (int i = 0; i < 3; ++i)
    {
        PLib::EvalPolynomial(i, 0, 2, 1, aCoeff[0], aResult);

        std::cout << "x=" << i << ", (2.0 + 2.0*x + 3.0*x^2): " << aResult << std::endl;
    }
}

從上述代碼可以看出，OpenCASCADE的PLib包中對(duì)多項(xiàng)式的表示方法是采用的系數(shù)表示法。其系數(shù)分別為：2.0，2.0，3.0，即表示了冪級(jí)數(shù)：

當(dāng)x=0, 1,2時(shí)計(jì)算結(jié)果如下圖所示：

Figure 2.1 Polynomial Evaluation

3.Polynomial Interpolation

多項(xiàng)式的插值問題是多項(xiàng)式求值的逆問題。多項(xiàng)式求值問題幾何意義就是已知曲線的表達(dá)式計(jì)算曲線上的點(diǎn)；而插值問題是已經(jīng)曲線上的一些點(diǎn)來求通過這些點(diǎn)的曲線表達(dá)式。多項(xiàng)式插值中最常見最基本的問題是求一次數(shù)不超過n的代數(shù)多項(xiàng)式：

使

滿足插值條件的多項(xiàng)式稱為函數(shù)f(x)在節(jié)點(diǎn)xi處的n次插值多項(xiàng)式。由插值條件可知，插值多項(xiàng)式的系數(shù)滿足線性方程組：

由線性代數(shù)可知，其系數(shù)行列式是n+1階Vandermonde行列式，且：

因?yàn)椴逯档狞c(diǎn)是不同的點(diǎn)，所以行列式V不為0，即線性方程組有唯一解。這也是算法導(dǎo)論一書中這樣說“從某種意義上說，多項(xiàng)式的系數(shù)表示法與點(diǎn)值表示法是等價(jià)的，即用點(diǎn)值形式表示的多項(xiàng)式都對(duì)應(yīng)唯一一個(gè)系數(shù)形式的多項(xiàng)式”的理論依據(jù)。即插值多項(xiàng)式的唯一性。這里不僅指出了插值多項(xiàng)式存在的唯性，而且也提供了一種解法，即通過解線性方程組來確定系數(shù)。根據(jù)這個(gè)思路，給出對(duì)上面已知系數(shù)求值的多項(xiàng)式進(jìn)行插值，代碼如下所示：

void testPolynomialInterpolation(void)
{
    // given three points: (0, 2), (1, 7), (2, 18) to interpolate a polynomial
    math_Matrix A(1, 3, 1, 3, 0.0);
    math_Vector B(1, 3);
    math_Vector X(1, 3);

    A(1, 1) = 1.0; A(1, 2) = 0.0; A(1, 3) = 0.0; B(1) = 2.0;
    A(2, 1) = 1.0; A(2, 2) = 1.0; A(2, 3) = 1.0; B(2) = 7.0;
    A(3, 1) = 1.0; A(3, 2) = 2.0; A(3, 3) = 4.0; B(3) = 18.0;

    // solve functions: Ax = B
    math_Gauss aSolver(A);
    aSolver.Solve(B, X);

    if (aSolver.IsDone())
    {
        std::cout << X << std::endl;
    }
}

已知多項(xiàng)式通過三個(gè)點(diǎn)（0, 2），（1, 7），（2, 18)，求通過這三個(gè)點(diǎn)的多項(xiàng)式表達(dá)式。根據(jù)插值條件列出線性方程組如下：

將系數(shù)a0,a1,a2看成線性方程組的待求變量，使用類math_Gauss來對(duì)線性方程組進(jìn)行求解，計(jì)算結(jié)果如下所示：

Figure 3.1 Polynomial Interpolation Result

由上圖可知，對(duì)線性方程組的求解結(jié)果與上節(jié)點(diǎn)的系數(shù)對(duì)應(yīng)。

4.Lagrange Interpolation

在《計(jì)算方法》、《數(shù)值逼近》等書中看到Lagrange的名字，就想到《高等數(shù)學(xué)》書中很多與之相關(guān)的定理、定義等，如：Lagrange中值定理、Lagrange型余項(xiàng)、條件極值的Lagrange乘數(shù)法等等。在網(wǎng)上搜索了下Lagrange，原來他也是OpenCASCADE的發(fā)源地的人：法國人。Joseph-Louis Lagrange，法國著名數(shù)學(xué)家、物理學(xué)家。1736年1月25日生于意大利都靈，1813年4月10日卒于法國巴黎。他在數(shù)學(xué)、力學(xué)和天文學(xué)三個(gè)學(xué)科領(lǐng)域都有歷史性的貢獻(xiàn)，其中尤以數(shù)學(xué)方面的成就最為突出。以下圖片來自網(wǎng)易公開課《數(shù)學(xué)傳奇》：從笛卡爾到龐加萊—法國數(shù)學(xué)的人文傳統(tǒng)，公開課網(wǎng)址：http://open.163.com/special/cuvocw/shuxuechuanqi.html

為什么優(yōu)雅浪漫的法國人的數(shù)學(xué)大師層出不窮呢？因?yàn)樗麄冏顑?yōu)秀的人在學(xué)習(xí)數(shù)學(xué)。數(shù)學(xué)已經(jīng)成為法國人傳統(tǒng)文化中最優(yōu)秀的一部分了。

數(shù)學(xué)也是中國傳統(tǒng)文化的一部分，中國古代數(shù)學(xué)成就也很多：《周髀算經(jīng)》；《九章算術(shù)》（三國時(shí)劉徽著）；祖沖之；算盤。天文學(xué)：天象觀察記錄，發(fā)明觀測儀器：圭表；渾儀；簡儀；高表；仰儀，制定歷法(農(nóng)歷)。想想后來為什么沒有大的發(fā)展，原因可能是科舉制度造成的，考試的內(nèi)容偏文。

Lagrange父親是法國陸軍騎兵里的一名軍官，后由于經(jīng)商破產(chǎn)，家道中落。據(jù)Lagrange本人回憶，如果幼年時(shí)家境富裕，他也就不會(huì)作數(shù)學(xué)研究了。經(jīng)歷了挫折之后沒被打倒的人后期成就會(huì)更大，像《紅樓夢(mèng)》的作者曹雪芹。嚴(yán)重跑題了，回到Lagrange插值問題上來。從Lagrange中值定理的證明及Lagrange乘數(shù)法求極值的方式中可以看出Lagrange有個(gè)特點(diǎn)，那就是喜歡引入輔助函數(shù)來解決問題，可以看出Lagrange是非常精明的。對(duì)多項(xiàng)式插值也不例外，通過構(gòu)造了一個(gè)Lagrange插值基函數(shù)來簡化多項(xiàng)式的插值，如下公式為Lagrange插值基函數(shù)：

設(shè)：

則Lagrange插值基函數(shù)可以表示為簡潔的形式：

則n次多項(xiàng)式

滿足插值條件。OpenCASCADE的PLib包中也提供了Lagrange插值的函數(shù)來進(jìn)行多項(xiàng)式插值計(jì)算。其用法的代碼如下所示：

void testLagrangeInterpolation(void)
{
    // given three points: (0,2), (1,7), (2,18) to interpolate a polynomial
    Standard_Real aValues[3] = {2.0, 7.0, 18.0};
    Standard_Real aParameters[3] = {0.0, 1.0, 2.0};
    Standard_Real aResult = 0.0;

    // this do not output the coeff of the interpolate polynomial
    PLib::EvalLagrange(1.5, 0, 2, 1, aValues[0], aParameters[0], aResult);

    std::cout << "Result: " << aResult << std::endl;
}

下面對(duì)PLib::EvalLagrange()函數(shù)的7個(gè)參數(shù)進(jìn)行說明：

Parameter	待根據(jù)Lagrange插值多項(xiàng)式求值的參數(shù)
DerivativeRequest	插值多項(xiàng)式導(dǎo)數(shù)次數(shù)
Degree	插值多項(xiàng)式的次數(shù)
Dimension	插值多項(xiàng)式的維次
Values	插值多項(xiàng)式的值
Parameters	插值多項(xiàng)式的參數(shù)
Results	參數(shù)Parameter在Lagrange插值多項(xiàng)式中的值

上述代碼計(jì)算的是這樣一個(gè)問題，已知f(0)=2; f(1)=7, f(2)=18，求f(1.5)的近似值。計(jì)算結(jié)果如下圖所示：

Figure 4.1 Lagrange Interpolation Result

由上圖可知，經(jīng)過Lagrange拋物插值得到的結(jié)果與直接計(jì)算得到的結(jié)果吻合。為了更好的說明OpenCASCADE中PLib包的Lagrange插值的用意，下面將《計(jì)算方法》[6]中Lagrange插值部分中的例題進(jìn)行計(jì)算來結(jié)計(jì)算結(jié)果進(jìn)行比較。已知

分別用線性插值和拋物插值求的近似值。相關(guān)計(jì)算代碼如下所示：

// sqrt(100)=10, sqrt(121)=11, sqrt(144)=12, evaluate sqrt(115) value.
Standard_Real aSqrtValues[3] = {10.0, 11.0, 12.0};
Standard_Real aSqrtParameters[3] = {100.0, 121.0, 144.0};

// linear interpolation
PLib::EvalLagrange(115.0, 0, 1, 1, aSqrtValues[0], aSqrtParameters[0], aResult);
std::cout << "Linear Interpolate Result: " << aResult << std::endl;

// Parabolic Interpolation
PLib::EvalLagrange(115.0, 0, 2, 1, aSqrtValues[0], aSqrtParameters[0], aResult);
std::cout << "Parabolic Interpolate Result: " << aResult << std::endl;

計(jì)算結(jié)果如下所示：

Figure 4.2 Linear Interpolate and Parabolic Interpolate Result

將上圖4.2的結(jié)果與書中的計(jì)算結(jié)果進(jìn)行對(duì)比發(fā)現(xiàn)，下面的結(jié)果為《計(jì)算方法》書中的結(jié)果：

PLib中Lagrange插值結(jié)果準(zhǔn)確，精度較高。

從上面的結(jié)果來看，Lagrange插值方法比直接解線性方程組的方法要簡單，且Lagrange插值法比解線性方程組的實(shí)現(xiàn)要簡單很多，只用一個(gè)函數(shù)即可。

5.Conclusion

通過將最簡單的多項(xiàng)式進(jìn)行求值，及用求解線性方程組的方法插值和Lagrange插值多項(xiàng)式，來學(xué)習(xí)曲線擬合中要求較高“插值”，因?yàn)槠湟笄€嚴(yán)格通過插值點(diǎn)。曲線擬合中的逼近就沒有這個(gè)要求，只是要求曲線與插值點(diǎn)之間的容差盡量小。

通過應(yīng)用OpenCASCADE的PLib包中的函數(shù)，可以發(fā)現(xiàn)對(duì)冪級(jí)數(shù)的多項(xiàng)式的表示法一般會(huì)用系數(shù)表示法，且都會(huì)使用高效的Horner法則，也是秦九韶算法。

直接根據(jù)定義來插值冪次多項(xiàng)式時(shí)，可以使用Gauss消元法來求解線性方程組。這種方式計(jì)算工作量大，而Lagrange插值法結(jié)構(gòu)緊湊，便于編程實(shí)現(xiàn)，且代碼相對(duì)簡單。通過對(duì)《計(jì)算方法》書中例題的計(jì)算，來驗(yàn)證PLib::EvalLagrange()函數(shù)的用法及計(jì)算結(jié)果。

6.References

1. 同濟(jì)大學(xué)數(shù)學(xué)教研室. 高等數(shù)學(xué). 高等教育出版社. 1996

2. 同濟(jì)大學(xué)應(yīng)用數(shù)學(xué)系. 線性代數(shù). 高等教育出版社. 2003

3. Thomas H. Cormen. Introduction to Algorithms. The MIT Press. 2001

4. Les Piegl, Wayne Tiller. The NURBS Book. Springer-Verlag. 1995

5. Shing Liu. Polynomial Library in OpenCASCADE. 2013

http://www.shnenglu.com/eryar/archive/2013/05/08/200118.html

6. 易大義,沈云寶,李有法. 計(jì)算方法. 浙江大學(xué)出版社. 2002

7. 蔣爾雄,趙風(fēng)光,蘇仰鋒. 數(shù)值逼近. 復(fù)旦大學(xué)出版社. 2012

8. 王仁宏,李崇君,朱春鋼. 計(jì)算幾何教程. 科學(xué)出版社. 2008

9. 蔡天新. 數(shù)學(xué)傳奇. http://open.163.com/special/cuvocw/shuxuechuanqi.html

10. 科學(xué)出版社名詞室. 新漢英數(shù)學(xué)詞匯. 科學(xué)出版社. 2004

PDF Version: OpenCASCADE Interpolation - Lagrange

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: OpenCASCADE HLR 輪廓線 OpenCASCADE-HLR Edge OpenCASCADE 線面求交 OpenCASCADE二維曲線求交 OpenCASCADE曲線上點(diǎn)的反求 OpenCASCADE - 曲線自交 OpenCASCADE 曲線求交 [書]-OpenCASCADE參考書籍 OpenCASCADE 掃掠曲面布爾數(shù)據(jù) 面的相交

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

eryar

導(dǎo)航

公告

常用鏈接

留言簿(107)

隨筆分類(692)

隨筆檔案(603)

Links

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

OpenCASCADE Interpolation - Lagrange

OpenCASCADE Interpolation - Lagrange