牛頓插值算法在因式分解中的設(shè)計與實現(xiàn)

《牛頓插值算法在因式分解中的設(shè)計與實現(xiàn)》由會員分享，可在線閱讀，更多相關(guān)《牛頓插值算法在因式分解中的設(shè)計與實現(xiàn)（3頁珍藏版）》請在裝配圖網(wǎng)上搜索。

牛頓插值算法在因式分解中的設(shè)計與實現(xiàn)摘要：本文基于 Kronecker 所提供的一元多項式因式分解的構(gòu)造算法、一元整系數(shù)多項式在整數(shù)環(huán)上因式分解理論，利用牛頓向前差分插值算法代替拉格朗日插值算法，把有理域上一元高次多項式因式分解化為在整數(shù)環(huán)上的因式分解，得到了整數(shù)環(huán)上的一元多項式因式分解的構(gòu)造性算法及其具體實現(xiàn)過程。論文關(guān)鍵詞：Newton 插值、不可約多項式、因式構(gòu)造、算法0 引言計算機出現(xiàn)以后，研究多項式因式分解的構(gòu)造和算法實現(xiàn)問題成為計算機代數(shù)的重要課題，對此國內(nèi)外很多學(xué)者做了大量的工作，吳文俊教授在文獻[2]中作了系統(tǒng)詳細(xì)的研究，給出因式分解方法，A.K.Lenstra,H.K.Lenstra 和 L.Lova’sz 三人于 1982 年首次提出了一元整系數(shù)多項式分解算法[3]，即著名的 L3 算法。本文基于 Kronecker 因式分解的基本思想[4]：在有理數(shù)域內(nèi)，任何 n 次多項式都能經(jīng)有限此算術(shù)運算分解為不可約多項式的乘積。設(shè) f(x)為整系數(shù)多項式且 f(x)= g(x)q(x),則適當(dāng)調(diào)整系數(shù)后，可使 f(x)的因式 g(x)、q(x)也為整系數(shù)多項式。對于整數(shù) a，等式 f(a)= g(a)q(a)中的 g(a)的數(shù)值必為 f(a)的因數(shù)，數(shù)學(xué)論文由于 f(a)的因數(shù)是有限個，所以只能得到有限個 g(a)；設(shè) f(x)有 k 次因式 g(x)，f(x) 在某 k+1 個點 x0、x1、…、xk 處的值分別為 f(x0)、f(x1) 、 …、f(xk)，再對 f(xi)(其中 i=0,1,…,k)進行因式分解，所得的因數(shù)個數(shù)為 pi(其中 i=0,1,…,k),從 f(xi)的因數(shù)集中取一個因數(shù)，一共有 種不同的方法，利用拉格朗日插值公式求出多項式 g(x)，判定所求多項式 g(x)是否為 f(x)的因式。在因式分解中涉及多項式的整除性，本文利用多項式整除性的一些性質(zhì)，對多項式可能存在的因式進行判斷，找出多項式的因式。一般情況下，人工可以進行 4 次及一下的多項式的分解，而高于 4 次的多項式很難進行分解，于是設(shè)想用計算機來解決這個問題，把高次多項式分解成一些不可約多項式的積，提高解題效率。1 算法原理分析1.1 Newton 向前差分插值算法在 Kronecker 提供的因式分解構(gòu)造性算法中，采用了朗格朗日插值算法。拉格朗日插值算法雖格式整齊和規(guī)范，但計算量大、沒有承襲性，當(dāng)需要增加差值節(jié)點時，不得不重新計算所有插值基函數(shù)，同時內(nèi)存消耗大[5]。且有時會產(chǎn)生切斷誤差而不能進行精確因式分解。于是本文用牛頓向前差分差值算法[6]代替拉格朗日算法。定義：設(shè)等距節(jié)點 xi=x0+ih， h 是步長，i=0，1 ，2，…記函數(shù) f 的值 fi=f(xi)， i=0，1，2 ，…則稱一階向前差分△fi=fi+1-fi，n 階向前差分△nfi=△n-1fi+1-△n-1fi定理 1：向前差分與函數(shù)的關(guān)系為：其中現(xiàn)討論等距節(jié)點情形：x0 由定理 1 有： f[x0、x1、…、xk]= △kfi/(k!hk)于是牛頓插值公式簡化為Nn(x)=f0+(x-x0)△1f0/(1!h1)+(x-x0)(x-x1) △2f0/(2!h2)+…+(x-x0)(x-x1)… (x-xn-1)△nf0/(n!hn)本算法采用等距節(jié)點 h=1 的情況，于是 k 次多項式 Nk(x)的系數(shù)分別為：1.2 因式判斷在本文中 F(x)表示數(shù)域上 F 上的全體，設(shè) f(x)、g(x) F(x)，物流管理畢業(yè)論文范文如果存在多項式 f(x)= g(x)q(x)，則稱 f(x)能被 g(x)整除，記為 f(x)g(x)。整除有以下幾個定理來判斷：定理 2[6]:若 R 是整數(shù)環(huán)，R(x)也是整數(shù)環(huán)，因而必有商域稱為 R 上的一元有理分式域。于是有:(1)若 g(x) =0，那么根據(jù)整除的定義，g(x)只能整除零多項式；(2)若 g(x) 0，那么由以上定理，當(dāng)且僅當(dāng) g(x)除以 f(x)的余式 r(x)=0 時，g(x)能整除 f(x)。1.3 多項式相除算法設(shè) f(x)= g(x)q(x)則 (0 t n)亦，當(dāng) a0=0，ai 0 時，f(x)必有因式 g(x)=x；當(dāng) c0=0 時，f(x)可能有因式 g(x)=x；當(dāng) c0 0 時，d0=a0/c0,dn-k=an/ck(t=1,2,…,n-k-1)2 算法分析及實現(xiàn)用構(gòu)造性算法(如圖 1)找出 f(x)可能的因式 g(x)，若 g(x)為整系數(shù)多項式且最高項系數(shù)不為 0，則 flag=1;否則 flag=0。若 flag=1 并驗證出 g(x)是 f(x)的因式，則輸出 g(x),facmon=1,f(x)=f(x)/g(x)(即令 n=n-k)；否則繼續(xù)構(gòu)造。若構(gòu)造的 g(x)的次數(shù)k[n/2]且 facmom=0,則 f(x)是不可約多項式；若構(gòu)造的 g(x)的次數(shù) k[n/2]且facmom=1，則輸出 f(x)的最后一個因式 f(x)，否則繼續(xù)構(gòu)造。3 結(jié)束語本文利用多項式整除性的一些性質(zhì)，對多項式可能存在的因式進行判斷，找出多項式的因式。一般情況下，人工可以進行低次多項式的分解，而高次多項式很難進行分解，于是設(shè)想用計算機來解決這個問題，把高次多項式分解成一些不可約多項式的積，提高解題效率。本文把有理數(shù)域上一元高次多項式因式分解化為在整數(shù)環(huán)上的因式分解，得到了整數(shù)環(huán)上的一元多項式因式分解的構(gòu)造性算法及其具體實現(xiàn)過程。