1、毕业论文文献综述 信息与计算科学 结式理论及其应用 一、 前言部分 高等代数是大学数学最主要的基础课程之一。高等代数课程的教学内容包含三个方面:线性代数,多项式理论,群,环,域的基本概念。线性代数占的比重最大,它研究线性空间及其线性映射(包括具有度量的线性空间及与度量有关的线性变换)。多项式理论是研究一元和多元多项式环。,群,环,域的基本概念是紧密结合多项式理论和线性变换(包括与度量有关的线性变换)理论,水到渠成地介绍一元(多元)多项式环、矩阵环、线性变换环、模 p剩余类域、正交群、酉群和辛群。 1 随着现代工程技术的发展,多项式理论的用途越来越广泛。特别是在现代控制理论中,频域法就是以多项式
2、理论为数学工具的一种系统设计方法。而结式 (resultant)是多项式理论中一个比较重要的概念,它主要用于多项式之间互质性的判定 2 。本综述从多项式的结式概念人手,提出应用结式理论来确定多元非线性多项式所有零点的系统方法,并借助计算机强大的计算能力验证该方法在解非线性方程组的计算中是行之有效的。凡是可化为多项式方程组求解的问题,均可采用本综述的方 法进行研究,特别是在电力电子领域中的谐波抑制方面有广泛的应用。 4,3 二、 主题部分 2.1 一元多项式 定义 1.1 设 n 是一个非负整数,形式表达式 10 1 1 1 0+ + , , ,nn n n n na x a x a x a a
3、 a a K (1.1) 称为系数在数域 K 中的一元多项式,或称数域 K 上的一元多项式 ()polynomial 。 在多项式 (1.1) 中, iiax 称为 i 次项 ()term , ia 称为第 i 次项的系数。我们把数域 K 上所有 一元多项式的集合记为 Kx。用 ( ), ( ),f x g x 或 ,fg 等符号表示多项式。 我们还规定:两个多项式 ()fx与 ()gx 的同次项的系数全相等,并记为 ( ) ( )f x g x 。又把所有系数都等于 0 的多项式称为零多项式,记为 0。 多项式中系数不等于 0 的最高次数的项称 为多项式的首项 ()leadingterm ,
4、其系数称为首相系数 ()leading coefficient, 首 相 系 数 等 于 1 的 多 项 式 称 为 首 一 多 项 式()monic polynomial。首项的次数称为多项式的次数 ()degree 。多项式 ()fx的次数记为degf 。例如 (1.1) 式的多项式 中如果 0na ,其首项就是 nnax ,首项系数就是 na ,次数等于 n 。规定零多项式的次数等于 . 的运算规则如下: () +任何整数 = , ( ) ( ) , 任 何 整 数 零次多项式就是一个非零常数 0 0aK 。 多项式在需多方面的性质非常类似于整数。首先定义多项式的加法运算。设 110 0
5、( ) +nn n in n iif x a x a x a a x (1.2) 110 0( ) + bmm m jm m jjg x b x b x a x (1.3) 不妨设定 nm 。为方便起见令 11 0n n mb b b 。那么 ()fx和 ()gx 的和为: 11 1 0 00( ) ( ) ( ) ( ) ( ) ( )nn n in n n n i iif x g x d e f a b x a b x a b a b x 显然数域 K 上的多项式之和仍是一个 K 上的多项式。 很容易验证多项式的加法具有类似于 整数加法(以及向量加法)的性质: (1)A 加法结合律: (
6、( ) ( ) ) ( ) ( ) ( ( ) ( ) ) ;f x g x h x f x g x h x (2)A 加法交换律: ( ) ( ) ( ) ( ) ;f x g x g x f x (3)A 零多项式的特性: 0 ( ) ( ) ( ) 0 ;f x f x f x (4)A 对于任意的多项式 110( ) +nnnnf x a x a x a 存在被称为负多项式的多项式110() nnnnf x d e f a x a x a ,使得 ( ) ( ( ) 0.f x f x 有了负多项式的概念就可以定义多项式的减法。把两个多项式 ()fx与 ()gx 的差定义为: ( )
7、( ) ( ) ( ( ) )f x g x de f f x g x 再定义多项式的乘法:设多项式 ()fx与 ()gx 如 (1.2) , (1.3) 式所示则定义它们的积为: 11 1 1 0 0 1 0 0( ) ( ) ( ) ( ) ;n m n mn m n m n mf x g x d e f a b x a b a b x a b a b x a b 其中 s 次项的系数为: 0 1 1 1 1 0s s s s i ji j sa b a b a b a b a b (1.4) 所以 ( ) ( )f xg x 可以表示成 0( ) ( ) ( )nm sijs i j s
8、f x g x a b x 多项式的乘法也均有类似于整数乘法的性质: ( 1)M 乘法结合律: ( ( ) ( ) ) ( ) ( ) ( ( ) ( ) ) ;f x g x h x f x g x h x ( 2)M 乘法交换律: ( ) ( ) ( ) ( );f x g x g x f x ( 3)M 多项式 1 的特征: 1 ( ) ( ) ( ) 1;f x f x f x 此外乘法与加法之间还满足分配律: ( ) ( ( ) ( ) ) ( ) ( ) ( ) ( ) ;f x g x h x f x g x f x h x 以及 ( ( ) ( ) ) ( ) ( ) ( )
9、( ) ( ) ;f x g x h x f x h x g x h x 以后我们把数域 K 上一元多项式的全体 Kx 称为一元多项式环,简称多项式环()polynomial ring。 在观察多项式的和与积的次数。 命题 1.1 对于多项式的乘法,有 d e g ( ( ) ( ) ) d e g d e g ,f x g x f g 特别当 ( ) 0, ( ) 0f x g x时有 ( ) ( ) 0f x g x 。 推论 1.2 多项式的乘法满足消去律:如果 ( ) ( ) ( ) ( )f x g x f x h x ,且 ( ) 0fx ,那么( ) ( )g x h x 。 5
10、 命题 1.2 设 ( ), ( ) f x g x K x ,则 (1 ) d e g ( ) d e g ( ) , 0c f x f x c K ( 2 ) d e g ( ( ) ( ) ) m a x d e g ( ) , d e g ( )f x g x f x g x6 2.2 结式的定义 我们知道,结式在代数中有着许多重要应用。利用结式能有效地解决两个一元多项式以及两个二元多项式的公共零点问题。我们还知道,判别式在多项式理论中占有重要的地位。根据判别式不但可以判定一个多项式是否有重根,而且还可以根据判别式的符号判定实系数多项式的根的情况。而判别式恰与结式有密切联系,前者往往通
11、过后者进行计算。 结式能够起到在两个联立的多项式方程中消去一个变量的作用。 先考虑两个一元多项式 10 1 1( ) + + ,nn nnf x a x a x a x a K x 10 1 1( ) + b + b ,mm mmg x b x b x x K x 其中 ,0nm ,并且允许首项系数 00,ab等于 0。 用 12, , ,1mmx x x 分别乘 ()fx,用 12, , ,1nnx x x 分别乘 ()gx ,可以得到以下等式组: 1 1 2 101( ) +m n m n m mnx f x a x a x a x 2 2 20( ) +m n m mnx f x a x
12、 a x 101( ) +nn nf x a x a x a 1 1 2 10 1 1( ) + bn n m n m nmx g x b x b x x 2 2 20( ) + bn n m nmx g x b x x 101( ) + bmm mg x b x b x (1) 我们把等式组右边的系数矩阵记为 010101010101b b b b b bb b bnnnmmma a aa a aa a a mAn 行 行 (2) 则 ()nmA M K 。现在用矩阵 A的最后一列元素的代数余子式1 , 2 , , , ,n m n m n m n mA A A 分别去乘 (1) 的各个等式
13、并把乘积相加。根据行列式的代数余子式的性质,等式右边的 1,nmxx 的系数都等于 0,只有常数项系数等于行列式 A 。也就是说得到下述结果: 0011( , ) ( ) ( 1 ) ( )nmm n m nijijR e s f g a g a b f 8,7 111 , , 1 , ,( ) ( ) ( ) ( )mnn m m n m m n m n m n mA x A f x A x A g x A +? + (3) 我们引进以下定义: 定义 1 设 10 1 1( ) + + ,nn nnf x a x a x a x a 10 1 1( ) + b + b ,mm mmg x b
14、 x b x x 是 Kx的两个多项式,并且 ,0nm 。则称行列式 010101010101b b b b b bb b bnnnmmma a aa a aa a a mn 行 行 为 ()fx与 ()gx 的结式 ()resultant ,记为 ( , )Res f g 。 根据结式的定义,我们可以把 (3) 式改写成以下形式: ( ) ( ) ( ) ( ) ( , )u x f x v x g x R e s f g。 其中 11 , ,( ) ,mn m m n mu x A x A + 11 , ,( ) .nm n m n m n mv x A x A + 显然有 d e g (
15、 ) , d e g ( ) .u x m v x n 这样就证明了以下命题 命题 1 设 10 1 1( ) + + ,nn nnf x a x a x a x a 10 1 1( ) + b + b ,mm mmg x b x b x x 是 Kx的两个多项式,并且 ,0nm 。则存在多项式 ( ), ( ) u x v x K x ,d e g ( ) , d e g ( )u x m v x n,使得 ( ) ( ) ( ) ( ) ( , )u x f x v x g x R e s f g (4) 利用这个命题可以证明下面的定理。 定理 2设 10 1 1( ) + + ,nn n
16、nf x a x a x a x a 10 1 1( ) + b + b ,mm mmg x b x b x x 是 Kx的两个多项式,其中 ,0nm 。则结式 ( , ) 0Res f g 的充分必要条件是:或者000ab,或者 ()fx与 ()gx 有次数大于 0的公因式(或等价地, ()fx和 ()gx 有公共的复数根)。 证明: () 设 ( , ) 0Res f g 则 (2) 式矩阵 A 的行向量 1,mn 线性相关,存在不全为零的数 1,mnkk 使得 11 0m n m nkk +? + 。用 ik 分别乘等式组 (1) 的各式并相加,就可得到 1111( ) ( ) ( )
17、( ) 0mnm m m nk x k f x k x k g x +? +? 令 1111( ) , ( ) ,mnm m m nu x k x k v x k x k +? +?则 ( ), ( )ux vx 不全为零,且 ( ) ( ) ( ) ( )u x f x v x g x 若 00,ab不全为零, 不妨设 0 0,a 则 deg ( )f x n ,因而 ( ) ( ) ( )f x v x g x 。如果( ( ), ( ) 1f x g x ,有 ( ) ( )f x v x 。若 ( ) 0vx 会得到 ( ) 0ux ,与 ( ), ( )ux vx 不全为零矛盾。但
18、d e g ( ) d e g ( ),v x n f x 又导出矛盾。所以 deg( ( ), ( ) 0f x g x 。令( ) ( ( ), ( )d x f x g x 。由于 ()dx 次数大于 0,它一定有一个复数根 c 。根据多项式的根与一次因式的关系,有 ()x cd x 。由于 ()dx 是 ()fx与 ()gx 的最大公因式,因此又有( ), ( ).x c f x x c g x再次利用根与一次因式的关系,就可得到 ( ) ( ) 0.f c g c这说明()fx与 ()gx 有公共的复数根 c 。 () 如果 000ab,则由结式的定义, ( , ) 0.Res f
19、g 设 ( ) ( ( ), ( )d x f x g x 。如果 ()dx 次数大于 0,则由上证, ()fx与 ()gx 有公共的复数根 c 。把 c 代入 (4) , 即有( , ) 0.Res f g 9 2.3 结式的一些传统算法 2.3.1 预备知识 我们知道 , 结式在代数中有着许多重要应用。利用结式能有效地解决两个一元多项式以及两个二元多项式的公共零点问题我们还知道 , 判别式在多项式理论中占有重要的地位根据判别式不但可以判定一个多项式是否有重根 , 而且还可以根据判别式的符号判定实系数多项式的根的情况而判别式恰与结式有密切联系 , 前者往往通过后者进行计算有关结式的计算 ,
20、在一般高等代数教程中大致有以下两种 方法 , 其一是行列式法 ,其二是公式法 .本综述给出另一种计算结式的方法这种方法在计算结式时只须对所给两个一元多项式进行有限次带余除法即 (辗转相除 )就可以了这种方法的优点在于它既可以避免高阶行列式的复杂计算 , 又可以避开求多项式的所有根的困难实践表明 , 就连普通的中学生也可以根据本综述所给出的方法计算结式。 10 我们的讨论要用到以下预备知识: 仅限于在复数域上进行讨论。 设 101() nn nf x a x a x a ( 0)n (1) 与 101() mm mg x b x b x b ( 0)m (2) 均为复数域上两个一元多项式。 我们
21、称 mn 阶 ()Sylvester 行列式: 010101010101b b b b b bb b bnnnmmma a aa a aa a a mn 行 行 (3) 为 ()fx与 ()gx 的结式,记作 ( , )Res f g 。 不难证明下列诸式成立: ( , ) ( 1 ) ( , )nmR e s f g R e s g f (4) 若 000, 0,ab又 12, , , na a a 与 12,m 分别为 ()fx与 ()gx 的全部(复)根,则 0011( , ) ( ) ( 1 ) ( )nmm n m nijijR e s f g a g a b f (5) 为了本综述
22、的需求,我们再给出关于结式的一个补充定义:若 ()gx 为任一次数大于零的多项式, r 为任一复数,我们规定: ( ( ) , ) ( , ( ) ) mR e s g x r R e s r g x r (6) 其中 0( ( )g x m(记号 0( ( )gx 表示 ()gx 的次数) 关于 (6) 式的合理性可作如下的解释:根据结式定义 , 因为 ()gx 是 m ( 0)m 次多项式,若数 0r ,则 r 是零次多项式,故 ()gx 与 r 的结式应该是 0m 阶行列式,而 ()gx 的系数不应在行列式中出现,既( m 阶行列式)。 ( ( ) , ) = mrrR e s g x
23、r rr 特别地,我们规定 ( ( ) , 0 ) ( 0 , ( ) ) 0R e s g x R e s g x (7) 2.3.2 主要结果 命 题 1 若 ()fx, ()gx (见式 (1) , (2) )满足 ( ) ( ) ( ) ( )f x g x q x r x且 ( ) 0rx ,则 ! 0( , ) ( 1 ) ( , )n m m n lR e s f g b R e s r g (8) 其中 0( ( )r x l 证 若 0l ,根据公式 (5) ,我们有 ( , ) ( ( ) ( ) ( ) , ( ) )R e s f g R e s g x q x r x
24、 g x 0011( 1 ) ( ) ( ) ( ) ( 1 ) ( )mmn m n n m nj j j jjjb g q r b r 0 0 01( 1 ) ( 1 ) ( ) ( 1 ) ( , )mn m m l n l m l l n m m l n ljjb b r b R e s r g 若 0l ,既 ()rx 为 某 一 非 零 数 r , 借 助 于 我 们 规 定 的 式 (6) 易知00( , ) ( 1 ) ( 1 ) ( , )n m n m n m nR e s f g b r b R e s r g 。从而式 (8) 获证。 类似地,由公式 (4) 与 (8) 不难证明 命题 2 若 ()fx, ()gx (见式 (1) , (2) )满足 ( ) ( ) ( ) ( )g x f x q x r x且 ( ) 0rx ,则 10( , ) ( , )mR es f g a R es f r (9) 其中 0( ( )r x l。