一元多項(xiàng)式最大公因式的求法及比較

PAGE目錄一引言………………11.1背景…………11.2研究現(xiàn)狀……………………11.3目的…………1二問題的提出………………………1三問題的解決………………………53.1矩陣法………………………53.2矩陣初等行（列）初等變換法……………83.3數(shù)值矩陣法…………………12四問題的總結(jié)………………………15致謝……………17參考文獻(xiàn)……………18一元多項(xiàng)式最大公因式的求法及比較摘要設(shè)是一個數(shù)域，為數(shù)域上的一元多項(xiàng)式環(huán)，多項(xiàng)式是多項(xiàng)式的一個最大公因式，那么存在中的多項(xiàng)式使得（1）成立.采用因式分解法和輾轉(zhuǎn)相除法可求得最大公因式.然而并不是所有的一元多項(xiàng)式都能因式分解，在輾轉(zhuǎn)相除的過程中不能用一個非零的常數(shù)去乘以除式及被除式，增加了運(yùn)算困難，并且當(dāng)次數(shù)較高時，運(yùn)用輾轉(zhuǎn)相法時顯得十分麻煩.本文中，在因式分解法和輾轉(zhuǎn)相除法兩種方法的基礎(chǔ)上，我們給出更簡便的求解最大公因式的方法，并通過相應(yīng)數(shù)值例子對各種方法進(jìn)行比較分析.關(guān)鍵詞最大公因式；公因式；多項(xiàng)式；矩陣初等變換中國分類號：o151LUOJiaojiao(SchoolofMathematicsandStatistics,TianshuiAbstract:LetP[x]beapolynomialringonnumericalfieldP.Supposethatisapolynomialgreatestcommonfactorof,then

.

(1)

Wecanobtainthegreatestcommonfactorbyusingfactorizationmethodoffactorandtheflounderdivision,butitisalwaysnotefficientforthepolynomialwithlargesizesInparticular,thedivisiormaynotbeanon-zeroconstant,whichincreasethecomputingdifficulties.Inthispaper,weproposesomesimplerapproachstofindthegreatestcommonfactor.Thesemethodsarecomparedbynumericalexamples.Keywords:Greatestcommonfactor;commonfactor;polynomial;Matrixtranspose數(shù)學(xué)與統(tǒng)計(jì)學(xué)院2009屆畢業(yè)論文PAGE19一元多項(xiàng)式最大公因式的求法及比較一引言1.1背景最大公因式的概念是多項(xiàng)式代數(shù)的重要內(nèi)容，關(guān)于最大公因式的求法一般只討論兩個多項(xiàng)式的最大公因式的求法，方法主要有因式分解法和輾轉(zhuǎn)相除法.考慮個多項(xiàng)式的最大公因式時，往往也是通過兩兩多項(xiàng)式求最大公因式，因此求多個多項(xiàng)式的最大公因式需要多次對兩個多項(xiàng)式進(jìn)行運(yùn)算.為了改進(jìn)方法逐漸出現(xiàn)了矩陣初等變換法等利用多項(xiàng)式矩陣和數(shù)字矩陣的運(yùn)算來求解最大公因式，雖然不盡完善，但也是一種很大的突破.本文將在此基礎(chǔ)之上對求最大公因式的方法進(jìn)一步作一個較全面的探討（包括理論研究和實(shí)例說明），最后對各種方法的優(yōu)劣性進(jìn)行綜述.1.2研究現(xiàn)狀文獻(xiàn)對因式分解法和輾轉(zhuǎn)相除法作了簡要介紹；利用矩陣來求解最大公因式的方法在文獻(xiàn)中都有所體現(xiàn).1.3本文研究的問題通過對各種求最大公因式的方法的探討和比較能夠靈活合理利用矩陣（多項(xiàng)式矩陣或數(shù)值矩陣）的相關(guān)性質(zhì)去求個多項(xiàng)式的最大公因式.二問題的提出在高等教材中，有如下定義和定理：定義1如果多項(xiàng)式既是的因式，又是的因式，那么就稱為與的一個公因式.定義2設(shè)，是中兩個多項(xiàng)式.中多項(xiàng)式稱為，的一個最大公因式，如果它滿足下面兩個條件：1）是，的公因式；2），的公因式全是的因式.定理1對于中任意兩個多項(xiàng)式，，在中存在一個最大公因式，且可以表成，的一個組合，即有中多項(xiàng)式,使.①證明如果，有一個為零，譬如說，，那么就是一個最大公因式，且.下面來看一般的情形.無妨設(shè).按帶余除法,用除,得到商,余式;如果,就再用除,得到商,余式;又如果,就用除,得出商,余式;如此輾轉(zhuǎn)相除下去,顯然,所得余式的次數(shù)不斷降低,即因此在一有限次之后，必然有余式為零，于是我們有一串等式；，，…………,…………,,.與0的最大公因式是.根據(jù)前面的說明，也就是與的一個最大公因式；同樣的理由，逐步推上去，就是與的一個最大公因式.由上面的倒數(shù)第二個等式，我們有再由倒數(shù)第三式，代入上式可消去得到然后根據(jù)同樣的方法用它上面的等式逐個消去，再并項(xiàng)就得到這就是定理的①式.證畢由最大公因式的定義不難看出，如果是與的兩個最大公因式，那么一定有與，也就是，.這就是說，兩個多項(xiàng)式的最大公因式在可以相差一個非零的常數(shù)倍的意義下是唯一確定的.我們知道，兩個不全為零的多項(xiàng)式的最大公因式總是一個非零多項(xiàng)式.在這個情形，我們約定，用來表示首項(xiàng)系數(shù)為1的那個最大公因式.由定義1和定義2我們很容易得到一種求多項(xiàng)式的最大公因式的方法—因式分解法.由定理1的證明過程我們找到另一種求多項(xiàng)式的最大公因式的方法—輾轉(zhuǎn)相除法.例1求與的最大公因式：解用輾轉(zhuǎn)相除法，得用等式寫出來就是故而于是，令就有對于因式分解法，我們知道并不是所有的一元多項(xiàng)式都能因式分解，即使可以因式分解但分解的過程往往比較困難，故此方法并不理想.對于輾轉(zhuǎn)相除法，求得后再利用逐步代入法求得使得（1）式成立，但是當(dāng)次數(shù)較高時，運(yùn)用輾轉(zhuǎn)相法時顯得十分麻煩.特別，在輾轉(zhuǎn)相除的過程中不能用一個非零的常數(shù)去乘以除式及被除式，增加了運(yùn)算困難.于是我們提出這樣的問題：如何利用定義和定理，尋找到一種比較簡便可行的方法來求個多項(xiàng)式的最大公因式并找出，從而把表示成的一個組合，使得三問題的解決3.1矩陣法1.求兩個多項(xiàng)式的最大公因式令是兩個多項(xiàng)式，不妨設(shè)，用去除有，，即.設(shè)可知是可逆陣，再用去除有，，即.設(shè)，則也是可逆陣，依次做下去，由于在絕對遞減，必有某時有或.不妨設(shè)，，則.，其中是可逆陣.設(shè)的第一列為，則有.②又由于，于是均可由表示，即是的公因式.綜合②得是的最大公因式.例2求與的最大公因式，并求使的解作除法，即再作除法，即再作除法，即則且由于在第2列，所以的第2列即是.，使.注：通常要求為首一多項(xiàng)式，這只需將上述的除以的首項(xiàng)系數(shù)即可.2.求3個多項(xiàng)式的最大公因式是3個多項(xiàng)式，，用去除，有,即.不妨設(shè)，再用去除和，有，即.繼續(xù)作下去，由于絕對遞減，必有某時中有一個不為零，其余全為零.不妨設(shè)，則有，記，則有.設(shè)的第一列為則.又，即均可由表示，即是的公因式.故是最大公因式.例3求的最大公因式，并求使.解最小，用去除，有即最小，再作除法，即是最大公因式.取，有.3.求個多項(xiàng)式的最大公因式是個多項(xiàng)式，用去除有即設(shè)（必是可逆陣）不妨設(shè)，再用去除有即設(shè)（必是可逆陣）.繼續(xù)下去，由于絕對遞減，必有某時中只有一個不為零其余全為零.不妨設(shè)，則.設(shè)是可逆陣，，設(shè)的第一列為，有，且均可由表示，即是的公因式.故是最大公因式.3.2矩陣的初等行（列）變換法在這里我們以初等列變換法為例（初等行變換法原理一樣）定理2設(shè)則定理3把中任意個多項(xiàng)式寫成矩陣形式，存在階方陣，使得其中，是的最大公因式.證明對于存在最大公因式：且存在使得：令于是有，對于存在最大公因式且存在使得：令：.于是有如此繼續(xù)下去，將得到又由定理2可知：故這里只要令定理得證.證畢定理4對于定理2中的，可以表示成有限個初等矩陣的乘積形式.證明不妨對進(jìn)行證明這個初等變換的過程可以寫成：即：對于其它都可以表示成初等矩陣的乘積形式，所以可以表示成初等矩陣的乘積形式.注：分別表示矩陣的三種初等變換；是形式表達(dá)式并不會出現(xiàn)的倒數(shù)形式.定理5設(shè)是上的非零陣，，是階單位矩陣，，為定理2中的，則矩陣，經(jīng)過一系列初等列變換可化為，而的第一列元素就是，使得成立.證明是上的非零陣，由定理3知，存在上的階可逆陣，使得，于是在的右邊乘上，則有，且的第一列元素就是，使得：成立.證畢例4對于整系數(shù)多項(xiàng)式求它們的最大公因式；且求：使得成立.解令對其進(jìn)行如下的的行初等變換：其中，經(jīng)驗(yàn)證成立.注：進(jìn)行初等變換的目的是要把的第一行變成形式，在作初等列變換過程中，系數(shù)保持是整數(shù)，在這個原則下可以隨意地作初等列變換，得到的是唯一的.但由于作法不同，得到的的第一列元素可能不同，故線性表示不唯一，但都能使成立.3.3數(shù)值矩陣法我們在前面介紹了矩陣的初等變換法，其實(shí)質(zhì)是利用多項(xiàng)式矩陣的初等行（列）變換求多項(xiàng)式矩陣的一階行列式因子，并且，在求解的過程中，仍然是多項(xiàng)式的運(yùn)算，有一定的難度.下面我們利用多項(xiàng)式的某些性質(zhì)建立一種利用數(shù)值矩陣的行初等變換求解多個多項(xiàng)式最大公因式的方法—矩陣數(shù)值法.該方法擺脫了求解過程中的多項(xiàng)式運(yùn)算，而單純運(yùn)用數(shù)值矩陣的初等行變換，直觀明了，簡單易行.設(shè)一元次多項(xiàng)式其性質(zhì)由其系數(shù)唯一決定.即它和由其系數(shù)所形成的行矩陣一一對應(yīng).對于個一元多項(xiàng)式③若③中至少有一個多項(xiàng)式的次數(shù)是次，在不計(jì)次序的情況下，它與其系數(shù)所形成的矩陣也是一一對應(yīng)的.其系數(shù)矩陣為④而最大公因式與次序無關(guān)，所以③的最大公因式由唯一決定.定理6若則由定理6：當(dāng)時，有；當(dāng)時，有；當(dāng)時，有.又有.所以對④實(shí)施初等行變換后，其所對應(yīng)的多項(xiàng)式組與③有相同的最大公因式.定理7設(shè)均不為零，則⑴當(dāng)，有；當(dāng)，有；⑵當(dāng)時，有.證明當(dāng)時，令，其中而，則有⑤因?yàn)?，故⑤?dāng)時，此時，有，因?yàn)?，有證畢也就是說，對于④中的任意兩行，分別時所在行中列數(shù)最大的非零元素，分別是所在行中列數(shù)最小的非零元素.有如下結(jié)論：⑴若，不妨假設(shè)，則第行的非零元素向右平移個列（下面將該過程簡稱右對齊）后，其所對應(yīng)的多項(xiàng)式組與③有相同的最大公因式；⑵若，而時，則第行的非零元素向左平移個列（下面將該過程簡稱左對齊）后，其所對應(yīng)的多項(xiàng)式組與③有相同的最大公因式.另外，由，可知去掉④中的所有元素都為0的行后其所對應(yīng)的多項(xiàng)式組與③有相同的最大公因式；若出現(xiàn)行，則③的最大公因式為1.定理8利用以上性質(zhì)一定能將④變成型矩陣.該矩陣對應(yīng)的多項(xiàng)式即為③的最大公因式.利用以上結(jié)論，就可以利用矩陣的初等行變換求出一元多項(xiàng)式組的最大公因式，其一般步驟為：㈠將系數(shù)矩陣?yán)贸醯刃凶儞Q化為階梯矩陣.㈡考察矩陣，若出現(xiàn)元素都是0的行，則去掉該行；若某行變?yōu)闀r，多項(xiàng)式的最大公因式為1，計(jì)算終止；若出現(xiàn)每一行的列數(shù)最大的非零元素不在同一列時，則施行右對齊；若每一行的列數(shù)最大的非零元素在同一列時，則施行左對齊；將變成非階梯矩陣，然后，以非零元素最少的行將其再化成階梯矩陣.㈢反復(fù)循環(huán)上述步驟，直到變?yōu)樾途仃嚕瑒t對應(yīng)的多項(xiàng)式即是③的最大公因式.例5設(shè)求的最大公因式.解系數(shù)矩陣所以，最大公因式為.四問題的總結(jié)我們已經(jīng)對求解多項(xiàng)式的最大公因式的問題給出了5種可行方法，各方法各有優(yōu)缺點(diǎn)，現(xiàn)我們總結(jié)如下：方法優(yōu)點(diǎn)缺點(diǎn)因式分解法直觀，原理簡單易懂.沒有廣泛適用性，分解過程往往比較難且某些多項(xiàng)式不能因式分解.輾轉(zhuǎn)相除法具有可操作性，較因式分解法適用范圍更廣，可有具體的格式進(jìn)行操作.當(dāng)已知的多項(xiàng)式次數(shù)較高時，輾轉(zhuǎn)相除次數(shù)較多顯得十分麻煩；在求時，輾轉(zhuǎn)相除的過程不能用一個非零的常數(shù)去乘除式和被除式，運(yùn)算困難.矩陣法結(jié)合多項(xiàng)式最大公因式的定義與矩陣的運(yùn)算性質(zhì)，不緊可以求兩個多項(xiàng)式的最大公因式還可以求得多個多項(xiàng)式的最大公因式并同時求得關(guān)于的線性組合.雖采用的是矩陣形式，但仍需要兩兩多項(xiàng)式作除法，隨著多項(xiàng)式的個數(shù)增加計(jì)算量大大增加，計(jì)算過程比較復(fù)雜.矩陣的初等行（列）變換法直接構(gòu)造矩陣，利用多項(xiàng)式矩陣的初等變換一舉求得最大公因式及其線性表達(dá)式，具有較廣的使用范圍且運(yùn)算過程較靈活，避免了多項(xiàng)式之間繁瑣的除法運(yùn)算.由于構(gòu)造的是多項(xiàng)式矩陣，故在運(yùn)算過程中仍是多項(xiàng)式的運(yùn)算，有一定的難度.數(shù)值矩陣法根據(jù)多項(xiàng)式與其系數(shù)間的一一對應(yīng)關(guān)系，構(gòu)造多項(xiàng)式組的系數(shù)矩陣，再由多項(xiàng)式最大公因式的性質(zhì)導(dǎo)出一種單純運(yùn)用數(shù)字矩陣（系數(shù)矩陣）的初等變換求得最大公因式的方法，直觀明了，簡單易行.不能像矩陣法和矩陣的初等行（列）變換法可以求得最大公因式的同時求得最大公因式的線性表達(dá)式.因此，我們可以依照以上的對比結(jié)果根據(jù)多項(xiàng)式的表達(dá)式特征、多項(xiàng)式的個數(shù)以及是否需要得到最大公因式的線性表達(dá)等情況的不同靈活選擇不同的方法來求最大公因式.致謝通過完成此次畢業(yè)論文，我深切體會到知識