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

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