3[1]3模糊等价矩阵与模糊相似矩阵课件.ppt

1、,m nRU(),ijRr0,1,()ijRr10 ijijijrrr(),ijRrR定义定义3-153-15 设设对对记记其中其中则则称为称为的的截矩阵截矩阵.截矩阵截矩阵.RRR0.80.30.60.20.40.70.50.81R0.6101001011R0.7100001011R的的截矩阵截矩阵对应于模糊关系的对应于模糊关系的截关系截关系.的元素仅能是的元素仅能是0 0或或1,1,因此相应的因此相应的是一普通关系是一普通关系.例如例如则则 显然显然截关系截关系0,1,RSRS,RS,RS.ijijrs,RS,ijijrs证证 设设欲证欲证只需证只需证已知已知即即对对分两种情况分两种情况;

2、(1)(1)对对1,ijijrr1,ijijijrss;ijijrs而而于是于是,ijijrs0,ijijss1,ijijss.ijijrs.RS而而此时或此时或或或于是于是故故 0,ijijrr,RS.RS,RS00(,),ij0 00 0.i ji jrs0 0,i jr0 00 01,0,i ji jrsRS.RS再设再设来证明来证明(反证法反证法)假设假设则必则必使使取取则有则有这与这与矛盾矛盾.故故(),().RSRSRSRS,RSCRSD,.ijijijijijijrscrsd()RSRS.ijijcd证证 只证第一式只证第一式.设设从而有从而有于是于是,要证要证只需证只需证分两种

3、情况分两种情况:(2)(2)1ijijijijcrsr 1ijijsr1()()11.ijijijijsrsd 0ijijijijcrsr0ijijsr0()()00ijijijijsrsd,ijijcd,CD()RSRS 或或或或 且且且且总之总之故故即即()Q RQR.SQ R(),QRQR1()mijikkjksqr(3)(3)证证 设设要证要证即要证即要证分两种情况分两种情况:11()mijijikkjkssqr ()()()()ikkjikkjk qrk qr 且1()(11)()1mikkjikkjkkqrqr 且101()1mijijikkjkssqr 1()0.mikkjkqr

4、 1()mijikkjksqr()Q RQR 故故 即即 (4)(4)()()TTRR,n nRU2,RRRRRR().t R若若则则包含包含而又被任一包含而又被任一包含的传递矩阵所包含的的传递矩阵所包含的的传递闭包的传递闭包,记作记作关于传递闭包有以下结论关于传递闭包有以下结论:设设称为称为模糊模糊传递矩阵传递矩阵.传递矩阵传递矩阵,称为称为,n nRU21()mkkt RRRRR 对任意对任意总有总有1(),kkt RR 1kkR,QR1.kkQR 1111kkkjkkkjRRRR 1111kjkjkjkjRRR 21mkmkRR1kkR证证 要证明要证明就是要证明就是要证明是传递的是传递

5、的,有有因为因为所以所以是传递的是传递的.同时对任意传递矩阵同时对任意传递矩阵n nQU.QRQ2,kQQQQ,QRkkQR,kkQQR,kQRk1kkQR 1()kkt RR 设设为任意传递矩阵且为任意传递矩阵且因为因为是传递的是传递的,所以所以又由又由有有从而有从而有即即再由再由的任意性得的任意性得 于是有于是有,n nRU1().nmmt RR U,Rn,Rn 设设则则此定理的重要性在于此定理的重要性在于,对有限域对有限域上的模糊关系上的模糊关系如果对应的模糊矩阵为如果对应的模糊矩阵为阶方阵阶方阵则它的传递闭包则它的传递闭包次并运算即可求出次并运算即可求出.(证明略证明略.).)只需只需

6、,n nRURR12345,Uu u u u uRU10.40.80.50.50.410.40.40.40.80.410.50.50.50.40.510.60.50.40.50.61RRU若若的模糊矩阵，则的模糊矩阵，则例例1 1 设设是是上的模糊关系上的模糊关系,可表示为可表示为求证求证是是上的模糊等价矩阵上的模糊等价矩阵.设设是自反、对称、传递是自反、对称、传递称为称为模糊等价矩阵模糊等价矩阵。R2RRRRRRR证证 显然显然是自反、对称的是自反、对称的,经计算得到经计算得到所以所以,是传递的是传递的.为模糊等价矩阵为模糊等价矩阵,为模糊等价关系为模糊等价关系.故故n nRU0,1,R0,

7、1,RR 是等价矩阵的充要条件是是等价矩阵的充要条件是:对对都是等价的普通矩阵都是等价的普通矩阵.便可以相应得到一个普通等价关系便可以相应得到一个普通等价关系于是由于是由便可决定一个便可决定一个水平的分类水平的分类.显然显然,不同的不同的对应着不同的分类对应着不同的分类,当当形成一个动态的图象形成一个动态的图象.那么那么,由于由于有何特征呢有何特征呢?这就是下面的定理要说明的问题这就是下面的定理要说明的问题.关于等价矩阵有两个重要的结论关于等价矩阵有两个重要的结论 定理说明有限域上定理说明有限域上的模糊等价关系确定后的模糊等价关系确定后,对给定的对给定的从从1 1降到降到0 0时时,分类也随之

8、变化分类也随之变化,的变化而分出的类的变化而分出的类01,RR(1)(1),ijijijijrrrr 11().ijijrr,i jRR 若若则则分出的每一个类必是分出的每一个类必是所分出的子类所分出的子类.亦即亦即这说明这说明,若若按照按照归为一类归为一类,则按则按一类一类,从而证明了定理的正确性从而证明了定理的正确性.此定理指出此定理指出类分得越细类分得越细.因此若要把问题分得细些因此若要把问题分得细些,只需增大只需增大即可即可.证证 亦必归为亦必归为越大越大,UUR10.40.80.50.50.410.40.40.40.80.410.50.50.50.40.510.60.50.40.50

9、.61RR,RURURRiuju1.ijr例例2 2 试将例试将例1 1中的中的解解 例例1 1中中上的模糊关系上的模糊关系的矩阵为的矩阵为已经证明已经证明是等价矩阵是等价矩阵,现在利用现在利用截矩阵截矩阵对对分类分类.所谓利用所谓利用对对分类是指分类是指:令令写出相应的写出相应的然后按然后按分类分类,与与归为同类等价于归为同类等价于分类分类.由由1 1降至降至0,0,1,11000001000001000001000001R12345,.uuuuu令令则则此时分为五类此时分为五类:亦即每一个元素为一类亦即每一个元素为一类,这是最细的分类这是最细的分类.0.80.810100010001010

10、00001000001R13245,.u uuuu(2)(2)令令,则则此时分为四类此时分为四类:0.6,0.61010001000101000001100011R13245,u uuu u0.5,0.51011101000101111011110111R13452,.u u u uu(3)(3)令令则则此时分为三类此时分为三类:(4)(4)令令则则此时分为两类此时分为两类:0.4,0.1,RE12345,u u u u u,n nRURR(5)(5)令令则则此时全归为一类此时全归为一类若若是自反、对称的模糊矩阵是自反、对称的模糊矩阵,则则称为称为模糊相似矩阵模糊相似矩阵.即分类即分类“最粗最

11、粗”.上述分类过程是一个动态的聚类过程上述分类过程是一个动态的聚类过程.例如例如10.40.50.410.60.50.61R就是一个相似矩阵就是一个相似矩阵.易见易见,模糊等价关系是相似关系的特殊情况模糊等价关系是相似关系的特殊情况.模糊等价模糊等价矩阵可以进行分类矩阵可以进行分类,先把它改造成为模糊等价矩阵先把它改造成为模糊等价矩阵,然后进行分类然后进行分类.n nRU,kn()()kt RRknk,l.lkRR()ijn nRr1(1,2,).iirin2(),ijn nR RRc 为相似矩阵为相似矩阵,则存在最小的自然数则存在最小的自然数使得使得且对于一切大于且对于一切大于的自然数的自然

12、数有有证证 设设为相似矩阵为相似矩阵,由于其自反性由于其自反性,于是有于是有考虑考虑其中其中 1()nijippjiiijijpcrrrrr,ijijrc2.RR即即故故利用模糊矩阵合成的性质利用模糊矩阵合成的性质,得得 322RRRRRR2221kkkkRRRRRR2kRRR 1()nmnmt RRRn,kn()kt RR23RRR()in1iinRRRkik,l1()()klmmt RRRRt RlkRR从而有非降序列从而有非降序列于是由定理于是由定理3-73-7与上式知与上式知:又由于又由于是一个有限的自然数是一个有限的自然数,因此必定存在自然数因此必定存在自然数使得使得(当非降矩阵序列

13、当非降矩阵序列从中间某一个从中间某一个起起,有有时时,取取对于任意的大于对于任意的大于的自然数的自然数因为因为所以所以 12422kkRRRRR122,kkRR2()kt RR122,kkn21logknk 2log1kn2log1n 计算计算直至出现直至出现则则因为因为所以所以 这表明用逐次平方法这表明用逐次平方法,至多只需要至多只需要步便可得到传递闭包步便可得到传递闭包.由此定理由此定理,我们可得出求相似矩阵传递闭包的我们可得出求相似矩阵传递闭包的简捷方法如下简捷方法如下:此方法叫做此方法叫做逐次平方法逐次平方法.n nRUR()kt RR,RI,kkRII()kRt R,TRR()()(

14、)(),TkTTkkt RRRRt R()kt RR()kt RR()kt RR 为一相似矩阵为一相似矩阵,则则的传递闭包的传递闭包证证 (1)(1)若若则则即即是自反的是自反的;则则 即即(3)(3)由传递闭包的定义由传递闭包的定义,因此因此,是模糊等价矩阵是模糊等价矩阵.必是模糊等价矩阵必是模糊等价矩阵.(2)(2)若若是对称的是对称的;是传递的是传递的.10.10.20.110.30.20.31R10.10.210.10.20.110.30.110.30.20.310.20.31R R 210.20.20.210.30.20.31R2210.20.210.20.20.210.30.210

15、.30.20.310.20.31RR 4210.20.20.210.30.20.31RR2R例例1010 把相似矩阵把相似矩阵改造成为一等价矩阵改造成为一等价矩阵.于是于是就是所求的等价矩阵就是所求的等价矩阵.解解 一个博采众长的求传递闭包的算法一个博采众长的求传递闭包的算法n 付国耀 ijn nAat A设为模糊相似矩阵，求，步骤11221maxmaxjjn nn njnjnaaa 1i、求,假设1111,iiiiAaaaa将 中元素用圆圈圈起来，11111,iiiiiaaaaa1记 x=,2A、假定 中有圈的k行 k=2,3,n-1 是12,kiii=1,，行1kjkxikx所在的列是 列

16、，在这 行的剩下元素中找最大元1212,maxkkkijii iiji iixa,kilxa假定 11,jk jki iki iki li laxaxaa用，1,kili laa代替，其对称元素也代替，lla最后把它们及=1用圈圈起来.1kn这过程一直做到，ija得 到 的 矩 阵 A=就 是 t A例：求例：求A的传递闭包的传递闭包n解12113210.50.40.810.50.40.80.510.70.50.510.70.50.40.710.60.40.710.60.80.50.610.80.50.6110.50.60.810.60.60.80.510.70.50.60.710.60.80.50.61A 320.610.70.60.60.710.60.80.60.61t R10.50.40.80.510.70.50.40.710.60.80.50.61A