線性代數(shù)報告

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

a1a 2

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

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

144]21 5]意的，階數(shù)越高，保密性越好。為了增加破譯難度，收發(fā)雙方可約定一個加密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ù)文字對照表就可以還原成原來的信息“Welcome！Tianjindaxue”。在編碼的過程中，將英文信息進(jìn)行轉(zhuǎn)化時，沒有區(qū)分大小寫字符，也可以擇的，矩陣的階數(shù)越高，破譯的難度越大?？赡婢仃嚨倪x擇必須保證與信息矩陣可乘。的不斷更新，保密技術(shù)的不斷發(fā)展，包括像矩陣在內(nèi)的許多數(shù)學(xué)知識作為工具將在其中發(fā)揮越來越大的作用。引例：已知某服裝加工廠生產(chǎn)甲、乙、丙、丁四種產(chǎn)品，每種產(chǎn)品的單件各類成本12成本(元)甲乙丙丁原材料15203025勞動力成本20103020企業(yè)管理費(fèi)用5101010運(yùn)輸成本2334表一：每種產(chǎn)品的單件各類成本季度一季度 二季度 三季度 四季度產(chǎn)品甲 4000 3000 2000 5000乙 1000 6000 4000 2000丙 2000 2000 2000

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

5000

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

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

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

0010]

105

化為行最簡形矩陣：

005|522

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

「1]P=90144

21」

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

]，于是Y=CT

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

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

(4)繼續(xù)對A2 做同樣的處理，直到不能再計算為止(均值元素為一個)，此時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)因此對矩陣A0 的行和列同時計算相鄰元素(不重疊)均值與差分，結(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)過均值差分變換后元素被分成兩大部份，一部份是原矩陣的近似(均值部份)，一部份代表原矩陣元素的變化細(xì)節(jié)(差分部份)，圖象的絕大部份信息集中在近似部份。同時對細(xì)節(jié)部份而息。因此，可以設(shè)置閾值，只保留絕對值大于閾值的細(xì)節(jié)部份元素。關(guān)于閾值的選取，本文簡單選取閾值為5，30，80，觀察壓縮效果的變化。A表示大小為n×n的圖象(矩陣)，正交均值差分變換矩陣為M，分別對A的具體算法步驟如下：計算均值差分變換矩陣。對A進(jìn)行均值差分變換，得BStep3：對于矩陣B，設(shè)置閾值e，大于閾值的像素保留，否則置零，獲得更稀疏的矩陣B，僅存儲其非零元素。Step4：計算A=(MT)1 BM1 =MBMT，即對B進(jìn)行逆均值差分變換，獲得解碼圖象A。以上算法同樣