線性代數(shù)報(bào)告

建造環(huán)境與能源應(yīng)用工程1班陳嘉威3013214105杜澎磊3013214106宋子旭3013214127近幾十年來(lái)，隨著科學(xué)技術(shù)的發(fā)展，特殊是計(jì)算機(jī)技術(shù)的發(fā)展，數(shù)學(xué)的應(yīng)法去解決。線性代數(shù)是一個(gè)數(shù)學(xué)分支，是代數(shù)的一個(gè)重要學(xué)科它對(duì)于培養(yǎng)學(xué)生嚴(yán)謹(jǐn)?shù)妮嬐评砗统橄笏季S能力起著不可或者缺的作用線性代數(shù)研究最多的是矩陣矩陣是一個(gè)數(shù)表，而這個(gè)數(shù)表可以進(jìn)行變換以形成新的數(shù)表。也就是說(shuō)如果抽象出某種變化規(guī)律，就可以用代數(shù)的理論對(duì)研究的數(shù)表進(jìn)行變換，并得出想要的 一些結(jié)論。所以，矩陣是一種方便的計(jì)算工具可以以簡(jiǎn)單的形式表示復(fù)雜的公式，比如數(shù)字圖象處理、計(jì)算機(jī)圖形學(xué)、計(jì)算幾何學(xué)、人工智能、網(wǎng)絡(luò)通信以及的知識(shí)。隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，通信技術(shù)中的保密工作顯得尤其重要，速擴(kuò)展到非物理領(lǐng)域，特別是在保密通信中發(fā)揮著重要作用。m×n矩陣，矩陣用a

a1a 2

]這m×n個(gè)數(shù)稱(chēng)為矩陣a am1m2mn的元素，a 稱(chēng)為矩A的行列元素，一m×n矩也可簡(jiǎn)記A=ij(a ) 或者A 。ij m×n m×n矩陣加法：設(shè)有兩m×n矩A=(a )矩的和記A+B，ij ij規(guī)定為A+B= (a +b ij ij

。m×n矩陣乘法：設(shè)A=(a ) ，B=(b ) 。矩陣A與矩陣B的乘積記作AB，ij m×n ij m×n規(guī)定為AB=(c

其中c

b

b +?+ a

=∑s a

(i=1，ij m×n

ij i1

i2

is sj

k=1 ik kj2，…，m；j=1，2，…，n)。為可逆矩陣，而矩陣B稱(chēng)為的逆矩陣。記作A-1，即A-1=B。自從人類(lèi)有了文字書(shū)寫(xiě)之后，就考慮使用一些手段來(lái)保障通信的機(jī)密，防止被獲取甚至被篡改。早期的古典密碼，如人類(lèi)最早由記載的棋盤(pán)密碼、愷撒密碼、維吉尼亞密碼等，相對(duì)照較簡(jiǎn)單。直到第二次世界大戰(zhàn)，關(guān)于通信的加密、解密取得了許多發(fā)展，研制成為了“隱謎機(jī)”，也就是從這個(gè)時(shí)期開(kāi)始，關(guān)于通信的加密解密開(kāi)始成為一門(mén)專(zhuān)門(mén)的學(xué)科，包括數(shù)學(xué)家在內(nèi)的許多科學(xué)家投身其中進(jìn)行深入的研究。20世紀(jì)末開(kāi)始，計(jì)算機(jī)的發(fā)展帶來(lái)了通信的變革，為了保證數(shù)據(jù)通信的安用，以及智能手機(jī)的介入，對(duì)信息的傳輸過(guò)程中的安全性和可靠性提出了更高要求。而保密通信作為實(shí)現(xiàn)信息安全的有效手段，在這其中起著舉足輕重的作通信的保密。因此保密通信主要涉及加密、解密的理論。保密通信過(guò)程中，存在明文和密文兩個(gè)概念。想要發(fā)送的信息稱(chēng)為明文，通過(guò)某種方法進(jìn)行偽裝或者隱藏的信息稱(chēng)為密文。通信過(guò)程中， 發(fā)送方會(huì)通過(guò)某種算法對(duì)明文數(shù)據(jù)進(jìn)行加密，通過(guò)加密后轉(zhuǎn)換成密文數(shù)據(jù)再發(fā)送給接收方，接收方再通過(guò)相應(yīng)的某種算法，對(duì)密文數(shù)據(jù)進(jìn)行解密轉(zhuǎn)換，就變成為了明文數(shù)據(jù)。這個(gè)過(guò)程就是加密解密的過(guò)程，其中的某種算法就是密鑰，這也就是數(shù)保密通信的模型，具體如下圖所示:收方再通過(guò)相應(yīng)的逆運(yùn)算將密文編譯成明文，就完成為了信息的傳遞。設(shè)矩陣A為明文矩陣，矩陣B為加密矩陣(密鑰)，用明文矩陣與加密矩陣的乘積來(lái)實(shí)施對(duì)所發(fā)消息的加密，這樣就得出密文矩陣C=AB。如果矩陣B是可逆矩陣，則矩陣方程C=AB有惟一解C=AB-1，其中B-1是B的逆矩陣。這樣，發(fā)送方將信息通過(guò)可逆矩陣進(jìn)行加密編碼成密文矩陣C=AB發(fā)出，接收方接收后再右逆矩陣B-1，就可得到明文矩陣A。如何快速而有效地構(gòu)造一個(gè)可逆矩陣作為加密矩陣和求出其逆矩陣作為解密矩陣是利用可逆矩陣實(shí)現(xiàn)保密通信的關(guān)鍵。得到初等矩陣的具體初等變換。加密矩陣。生成解密矩陣也只需要再次利用生成加密矩陣時(shí)的變換矩陣對(duì)單位矩陣做一序列的初等逆變換即可。利用矩陣對(duì)“Welcome！Tianjindaxue”進(jìn)行編碼。先將英文的26個(gè)字母用數(shù)字1-26代替，嘆號(hào)用27代替，構(gòu)成一個(gè)對(duì)照表。此時(shí)，“Welcome！Tianjindaxue”可譯為:2351231513527209114109144124215將發(fā)送數(shù)字排23 5 12315 13 527成5×4的明文矩陣，即A=20

1 此時(shí)，對(duì)于矩陣階數(shù)的選擇是隨[910[91

144]21 5]意的，階數(shù)越高，保密性越好。為了增加破譯難度，收發(fā)雙方可約定一個(gè)加密1 2 05矩陣，B=[1 3 2 ]可求的逆矩。發(fā)送者將加密后的密文矩陣1 0 050 2 1340 67 1318433 123 53181C=AB=

95

4送7給接收方。接收方接受信息后，就再右乘[46

55 22 ]84 53B-1，可得ABB-1=A然后根據(jù)文字對(duì)照表就可以還原成原來(lái)的信息“Welcome！Tianjindaxue”。在編碼的過(guò)程中，將英文信息進(jìn)行轉(zhuǎn)化時(shí)，沒(méi)有區(qū)分大小寫(xiě)字符，也可以擇的，矩陣的階數(shù)越高，破譯的難度越大?？赡婢仃嚨倪x擇必須保證與信息矩陣可乘。的不斷更新，保密技術(shù)的不斷發(fā)展，包括像矩陣在內(nèi)的許多數(shù)學(xué)知識(shí)作為工具將在其中發(fā)揮越來(lái)越大的作用。引例：已知某服裝加工廠生產(chǎn)甲、乙、丙、丁四種產(chǎn)品，每種產(chǎn)品的單件各類(lèi)成本12成本(元)甲乙丙丁原材料15203025勞動(dòng)力成本20103020企業(yè)管理費(fèi)用5101010運(yùn)輸成本2334表一：每種產(chǎn)品的單件各類(lèi)成本季度一季度 二季度 三季度 四季度產(chǎn)品甲 4000 3000 2000 5000乙 1000 6000 4000 2000丙 2000 2000 2000

2000丁 3000 2000表二：四季度各類(lèi)產(chǎn)品產(chǎn)量

5000

1000時(shí)費(fèi)力。讓我們來(lái)用矩陣的方法來(lái)描述此問(wèn)題設(shè)A為每種產(chǎn)品的單件各類(lèi)成本矩陣，即：|15|A= |5|L2

2030103020||101010||334」B:300020005000300020005000]60004000200020002000200020005000」||1000B=||2000則四個(gè)季度的原材料、勞動(dòng)力成本、企業(yè)管理費(fèi)用、運(yùn)輸成本的總成本為矩陣ABX，即:||X=|80000|L29000

00|220000240000|11500012000075000||5000042000」根據(jù)矩陣X，可以得到各類(lèi)產(chǎn)品總成本分類(lèi)表，如表三。成本(元)春夏秋冬合計(jì)原材料205000275000295000200000975000勞動(dòng)力成本210000220000240000200000870000企業(yè)管理費(fèi)用8000011500012000075000390000運(yùn)輸成本29000500004200026000147000合計(jì)5240006600006970005010002382000表三：各類(lèi)產(chǎn)品總成本分類(lèi)表可見(jiàn)，應(yīng)用矩陣計(jì)算成本一目了然，省時(shí)省力。又如：某工廠每批次投料生產(chǎn)中，獲得4種不同產(chǎn)量的產(chǎn)品，同時(shí)測(cè)量出各批次的生產(chǎn)總成本，如表四所示：生產(chǎn)批次產(chǎn)品/kgABCD120010010050290025002502001007050310040402013604400180160605500表四試求每種產(chǎn)品的單位成本。ACD4種產(chǎn)品的單位成本分別為a可以得到得方程組：化簡(jiǎn)得：「422|

0010]

105

化為行最簡(jiǎn)形矩陣：

005|522

103L20983275」 L00012」因?yàn)橄禂?shù)矩陣的秩等于增廣矩陣的秩，所以方程組有惟一解，即：a=10，b=5，c=3從而直觀地反映了工廠生產(chǎn)的產(chǎn)品的單位成本。生產(chǎn)利潤(rùn)的計(jì)算對(duì)于企業(yè)生產(chǎn)和策略制定具有指導(dǎo)性作用，利用矩陣能夠直觀的計(jì)算利潤(rùn)問(wèn)題。如：一個(gè)工廠生產(chǎn)甲、乙兩種產(chǎn)品。需用A、B、C三種原料。給出產(chǎn)品的單價(jià)向量P(單位：千元／件)，原材料成本的向量C(單位：千元

「1]P=90144

21」

9 4][設(shè)甲、乙產(chǎn)品的單位成本向量Y=a

]，于是Y=CT

[ ]2040可得：售出甲、乙產(chǎn)品所獲的利潤(rùn)為：PTX—YX=(PT-Y)X=9900—1800=8100(千元)而不是圖片，所以一幅圖象在用計(jì)算機(jī)處理前必須先轉(zhuǎn)化為數(shù)字形式。左圖表明了如何用一個(gè)數(shù)字矩陣來(lái)表示一個(gè)物理圖象。物理圖象被劃分為稱(chēng)作圖象元素的小區(qū)域，圖象元素簡(jiǎn)稱(chēng)為像素，最常見(jiàn)的劃分方案是圖中所示的方形采樣網(wǎng)格，圖象被分割成由相鄰像素組成的許多水平線，賦予每一個(gè)像素位置的數(shù)值反映了物理圖象上對(duì)應(yīng)點(diǎn)的亮度。有的像素都完成上述轉(zhuǎn)化后，圖就被表示成一個(gè)坐標(biāo)決定，它們又稱(chēng)為行和列。表示該像素位置上亮暗程度的整數(shù)稱(chēng)為灰度。此數(shù)字矩陣就作為計(jì)算機(jī)處理的對(duì)象了。由此，每一幅灰度格式的圖象(我們尋常稱(chēng)為黑白圖片)，都可用一個(gè)元素255RGBRGB通過(guò)對(duì)矩陣進(jìn)行一些數(shù)據(jù)處理就可以將圖片改變。比如將圖片所對(duì)應(yīng)的矩陣進(jìn)行轉(zhuǎn)置，就能得到原圖片沿主對(duì)角線對(duì)稱(chēng)的圖片。前 后接下來(lái)介紹如何從圖象的矩陣表示出發(fā)，通過(guò)矩陣的乘法進(jìn)行矩陣的正交變換、求矩陣轉(zhuǎn)置進(jìn)行正交逆變換最終實(shí)現(xiàn)數(shù)據(jù)圖象的壓縮。設(shè)a，b為介于0－255之間的數(shù)，則稱(chēng)c= a+ 2 2為a與b的均值。

a? 1 11?1 ad= a? √2 √2

? 2b√2√2b為a與b的差分。從定義中可看出，均值是a，b的近似，差分度量了a與b的差別。矩陣A0

=a

n×nn=2m為自然n×n ij n×n數(shù)，，2，…，通計(jì)算矩A0 的行相鄰元不重)的均n×n值與差分，按均值在前差分在后的順序得到矩陣=a 1 ，即n×n ij? n×na1 =

1111

a =( )?( a000i,(j1

)?2

a0i,j

√2 i,j1

√2√2 a0i,a1 = 1a0

11?1

=( )?( a0i,(nj1)? 2 √2

i,j

a0√2 i,j1

√2√2 a0i,j?=1,3,5,7,?,n?1;i=1,2,3,?, n.易得

=A0 Mn n×n1

(3)1 0√21 0√20 1√21其中 M = 0 11

0 1 0 0√20 ?1 0 0√2√0 0 1 0√20 0 ?1 000√2 ? 000√2 ? 0000 ? 000001√20 0 ?00 0 1√2(0 0 1√2

)n×n1 0 √21 0 √20 1 √2? 設(shè) M0= 0 1 ? K √20√20√20?000?000001√2?

1 0 0√2?1 0 0√20 1 0√20 ?1 00 0 ? 00 0 1√2(0 0 1√2

)2 K×KK為自然數(shù)，M =M01 n。顯然，是正交矩陣，故式知，上面的過(guò)程實(shí)質(zhì)上是對(duì)矩進(jìn)行K n×n了一次正交變換，得到矩。稱(chēng)該變換為正交均值差分變換。n×n繼續(xù)對(duì)中元素a1，j=1,2,?, n;i=1,2,?, n，計(jì)算行相鄰元素(不重n×n i,j 2疊)的均值與差分，按均值在前差分在后的順序放置，其它元素即a1，j=n1,n 2,?, n;i=1,2,?,n 保持不動(dòng)，得到矩陣記A2 ，n×n

i,j 22A2 =A1 M =A0 MM ，M2=(M2=(M/20 )其中 En/2

(4)繼續(xù)對(duì)A2 做同樣的處理，直到不能再計(jì)算為止(均值元素為一個(gè))，此時(shí)n×n

=A0 MM

， (5)row

row

n×n 1 2 p m其中Mp=(M02n/2)，p=1,2,?,其中Mp=(M02n/2)，p=1,2,?,m.n×n算為止，則可得

A =MT?MT?MTMTA0 .Colummp21n×n

(6)因此對(duì)矩陣A0 的行和列同時(shí)計(jì)算相鄰元素(不重疊)均值與差分，結(jié)果n×n記為B，則B=M

?MT?MTMTA0 MM

=MTA0 M，(7)

m p 2 1 n×n 1 2 p

n×n其中 M=M M?M ?M12pm(8)(1均值和差分的定義不難看出，矩陣經(jīng)過(guò)均值差分變換后元素被分成兩大部份，一部份是原矩陣的近似(均值部份)，一部份代表原矩陣元素的變化細(xì)節(jié)(差分部份)，圖象的絕大部份信息集中在近似部份。同時(shí)對(duì)細(xì)節(jié)部份而息。因此，可以設(shè)置閾值，只保留絕對(duì)值大于閾值的細(xì)節(jié)部份元素。關(guān)于閾值的選取，本文簡(jiǎn)單選取閾值為5，30，80，觀察壓縮效果的變化。A表示大小為n×n的圖象(矩陣)，正交均值差分變換矩陣為M，分別對(duì)A的具體算法步驟如下：計(jì)算均值差分變換矩陣。對(duì)A進(jìn)行均值差分變換，得BStep3：對(duì)于矩陣B，設(shè)置閾值e，大于閾值的像素保留，否則置零，獲得更稀疏的矩陣B，僅存儲(chǔ)其非零元素。Step4：計(jì)算A=(MT)1 BM1 =MBMT，即對(duì)B進(jìn)行逆均值差分變換，獲得解碼圖象A。以上算法同樣