正交表的构造方法及Matlab实现*

河南师范大学数学与信息科学学院(453007)

庞善起 鹿姗姗

正交表的构造方法及Matlab实现*

河南师范大学数学与信息科学学院(453007)

庞善起 鹿姗姗

正交试验设计是研究多因素水平的试验设计方法,它是一种高效率、快速、经济的试验设计方法。正交表在卫生、统计、医药、农业、制造业等方面都有非常重要的应用,尤其是高强度正交表可以研究较多因素之间的相互作用,但是正交表的强度越高越难构造;另外,混合正交表的魅力在于它有较大的灵活性,允许试验因素具有不同水平数,得到了越来越多的关注。因此如何快速、高效地得到需要的正交表是有必要和有意义的。

至今为止,已经有许多组合数学家和统计学家致力于正交表的研究,例如杨子胥、庞善起、张应山、杜蛟等分别在文献[1-8]中给出了不同类型的正交表的构造方法,这些正交表不仅在试验设计中有广泛的应用,随着研究的不断深入,它们还可以被应用于编码学、密码学、计算机科学中。

正交表构造方法与原理

1.Ltu(tm)型正交表[1]

(1,0,0,…,0,0,0)

1个

(bu-1,1,1,0,…,0,0,0)

t个

(bu-2,1,bu-2,2,1,…,0,0,0)

t2个

⋮

⋮

(b2,1,b2,2,b2,3,…,b2,u-2,1,0)

tu-2个

(b1,1,b1,2,b1,3,…,b1,u-2,b1,u-1,1)

tu-1个

因为每个bij为域GF(t)的所有元素,即有t种取法,所以以上的向量,就是Vu的全部标准向量,共有

构造Ltu(tm)型正交表的方法和步骤如下:

第1步,先给出t阶有限域GF(t);

第3步,以全体向量为行号,以全部的标准向量为列号,做出所有内积即可得Ltu(tm)型正交表。

2.混合水平正交表

混合水平正交表[1]可由Ltu(tm)型正交表通过并列而产生。构造混合水平正交表的方法和步骤如下:

第1步,可借助上文Ltu(tm)型正交表的方法得到Ltu(tm)型正交表;

第2步,从Ltu(tm)中任意取定k个独立的列(k

第4步,再将这k列同行元素所构成的tk个互异的有序组,按字典排列法与tk个自然数1,2,…,tk建立一一对应,而把这k列所构成的每个有序组均换成它对应的自然数,便得到一个新的tk水平列;

3.高强度正交表

一个第j 列的元素是0,1,…,qj-1的ω×n矩阵A,称为一个强度为2的正交表,如果满足以下条件[4]:

(1)每一列中每个元素出现的次数相同;

(2)在任两列ai,aj(1≤i,j≤n)中的每一个数对(0,0),…,(0,qj-1),(1,0),…,(1,qj-1),…,(qj-1,0),…,(qj-1,qj-1)出现的次数相同。

只满足上述条件(1)的矩阵叫做强度1的正交表。如果A的任何ω×d的子矩阵包含所有可能的1×d行向量,且这些行向量出现的次数相同,称为强度为d的正交表。强度d≥3的正交表称为高强度正交表[4-6]。

引理1 设M是一个选自Qn的任意t(1≤t≤qn-1)个行向量构成的矩阵,则

是一个强度为1的正交表。

引理2 对于任意的整数1≤k≤q总存在Qn上的1-正交分划A1,A2,…,Ak。

证明:由于Qn本身就是一个正交表,所以当k=1时定理显然成立； 当k

由于Qn中有qn个q元n维向量,考虑将Qn分为行数相等的分划容量为q的A1,A2,…,Ak,其中的每个Ai(1≤i≤k)中都有qn-1个向量,为了得到Ai:

⋮

第2q-1步,将剩下的qn-1个向量,组成矩阵Aq,它当然是一个强度1的正交表。

这样就构造出了Qn的一个1-正交分划A1,A2,…,Aq。

引理3 若有Qn上的正交分划A1,A2,…,Aq,如果Ai(i=1,2,…,q)都是qn-1行n列的强度为t的正交表,那么下列矩阵都是强度为t+1的正交表,并且是Qn+1的(t+1)-正交分划。

其中的0,1,2,…,q-1均指与其对应的Ai有相同的行的元素全为0,1,2,…,q-1的向量,下文同。

高强度正交表的构造可由引理1,2得到强度为1的正交表,和Qn的1-正交分划,在这个前提下,再由引理3得到强度为2的正交表,和Qn+1的2-正交分划,接着由引理3得到强度为3的正交表,和Qn+2的3-正交分划,依次下去,逐步构造出高强度的正交表。

正交表构造的Matlab实现

为了更加直观详细地说明Matlab程序的可行性,下面我们将选取几个较为简单的正交表作为例子说明利用Matlab程序实现正交表的构造方法。

1.Ltu(tm)型正交表

clc;clear

t=2;u=3;%初始条件

p=t;V=[ ];K=[ ];L=[ ];D=[ ];L1=[ ];L2=[ ];

G=transpose(0:(t-1));%t阶有限域

i=1;

while(i<=u)

R=kron(kron(ones(t^(i-1),1),G),ones(t^(u-i),1));

V=[V,R];

i=i+1;

end

V%所有的u维向量

U=rref(V′);%标准化

[m,n]=find(U==1);

[s,t]=find(U((m+1):u,n)<=1);

B=U(:,unique(n(t)))′;%标准向量

L=V*B′;

L=mod(L,p)%得到正交表L8(27)

在Matlab程序中只需修改初始条件t,u的值,我们就可以生成形如Ltu(tm)的正交表。

2.混合水平正交表

以L8(4×23)为例,则23=8,此时t=2,u=3,k=2,由上文的程序得到L8(27),取定2个独立的列(2<3),去掉能用这2列线性表示的所有列,再将这2列所构成的22=4个互异的有序组,把这2 列所构成的每个有序组均换成它对应的自然数,从而生成正交表L8(4×23),结果如表2,Matlab程序与解释如下:

表1 正交设计表L8(27)

clc;clear

t=2;u=3;k=3;%初始条件

p=t;[z,z1]=size(L);%接上节程序

K=L(:,1:k);%默认1:k列,也可以换成其他列

i=1;

while(i<=z1)

d=rank([K,L(:,i)]′)%m个n维向量线性相关⟺秩

D=[D,d];

i=i+1;

end

D

a=find(D(1,:)>=(k+1))

L1=L(:,a)%得到正交表Ltu(tr)

%以下生成混合水平列

Y=unique(K,′rows′)%删除K中重复的行,得到有序组

[y,y1]=size(Y);

j=1;

while(j<=y)

b=find(K(:,1)==Y(j,1)&K(:,2)==Y(j,2));

[z,z1]=size(b);

K(b,:)=(y-(j-1))*ones(z,k);%有序组与自然数建立一一对应

j=j+1;

end

L2=[flipud(K(:,1)),L1]%得到混合水平正交设计表

3.高强度正交表

以L8(24)为例,则Q={0,1},q=2,N=4,t=3,首先生成强度为1的正交表,和Q2的1-正交分划,再生成强度为2的正交表,和Q3的2-正交分划,接着生成强度为3的正交表,和Q4的3-正交分划,这样就可以生成2水平强度为3的正交表。结果如表3,和表4,Matlab程序与解释如下:

表2 正交设计表L8(4×23)

clc;clear;

q=2;%水平(初始条件)

t=3;%强度(初始条件)

N=4;%列数(初始条件)

n=N-(t-1);%q水平强度为1的正交表的列数

Q=[];a0=[];a1=[];a=[];A1=[];A=[];L=[];L0=[];L1=[];

%第一部分：生成Q^n即所有的q元n维向量

i=1;

while(i<=n)

R=kron(kron(ones(q^(i-1),1),[0:(q-1)]′),ones(q^(n-i),1));

Q=[Q,R];%Q^n即所有的q元n维向量

i=i+1;

end

%第二部分：生成1-正交分划

j=1;

while(j<=(q-1))

for i=0:(q-1);

a0=Q((1+q^(n-2)*(j-1)):q^(n-2)*j,:);

a1=mod(i+a0,q);%正交分划

a=[a;a1];

end

Q=setdiff(Q,repmat(a,2,1),′rows′);%Q^n-a

j=j+1;

end

A=[a;Q];%生成强度为1的正交表

%第三部分：正交分划的递归构造

while(n<=N-1)%Q正交分划q^(n-2)行向量的个数

L0=kron(ones(q,1),kron([0:q-1]′,ones(q^(n-1),1)));

j=0;

while(j<=q-1)

A1=circshift(A,[q^(n-1)*j,0]);%每次向下移q^(n-1)

L1=[L1;A1];

j=j+1;

end

A=[L0,L1];%所有正交分划的并列

L1=[];

n=n+1;

end

%第四部分:生成强度为t的正交表

for i=1:q;

L=A((1+q^(n-1)*(i-1)):q^(n-1)*i,:)%强度为t的正交表

end

在Matlab程序中,保证n=N-(t-1)≥2的前提下,只需修改初始条件q,N,t的值,我们就生成q水平,强度为t,列数为N,行数为q^(N-1)的正交表。比如修改初始条件,使得q=4,t=3,N=4便可得到水平为4,强度为3,列数为4,行数为64的正交表;修改初始条件,使得q=5,t=3,N=4，便可得到水平为5,强度为3,列数为6,行数为125的正交表。

表3 正交设计表L8(24)

表4 正交设计表L8(24)

结 论

正交表研究正在引起众多领域研究者的广泛关注。本文在原有的理论基础上使用Matlab 生成三种类型的正交表,但是仍有一些问题值得改进和研究，本文只给出了生成单一水平的高水平高强度正交表构造方法,所以接下来还需要继续寻找混合水平的高水平高强度正交表的构造方法。

[1]杨子胥.正交表的构造.济南:山东人民出版社,1978.

[2]庞善起.正交表的构造及其应用.成都:电子科技大学,2004.

[3]张应山.正交表的数据分析及其构造.上海:华东师范大学,2006.

[4]杜蛟,王守印,温巧燕,等.强度m的对称正交表的递归构造.应用数学学报,2012,35(2):232-244.

[5]Jiang L,Yin JX.An approach of constructing mixed-level orthogonal arrays of strength≧3.Science China(Mathematics),2013,6(56):1109-1115.

[6]Du J,Wen QY,Zhang J.New Construction of Symmetric Orthogonal Arrays of Strength t.IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences,2013,9(96):1901-1904.

[7]李学斌,余小领,李斌.运用Excel进行正交表的构建.河南科技学院学报(自然科学版),2008,36(4):115-118.

[8]陈远方,林曦晨,徐利华,等.常用正交表的构造原理及SAS实现.中国卫生统计,2012,29(4):470-474.

(责任编辑：刘 壮)

国家自然科学基金(11571094)