图28 火星探测器

【模型准备】令Xk = [x1, …, xk]. 在雷达进行数据分析时需要计算出矩阵Gk = XkXkT. 一旦接收到数据向量xk+1, 必须计算出新矩阵Gk+1. 因为数据向量到达的速度非常快, 随着k的增加, 直接计算的负担会越来越重. 现需要给出一个算法, 使得计算Gk的负担不会因为k的增加而加重. 【模型求解】因为

?x1T???kT

Gk = XkXk = [x1, …, xk]??=?xixiT,

i?1T??xk???XkT?TTGk+1 = Xk+1X= [Xk, xk+1]?T?= XkXkT + xk+1xk?1= Gk + xk+1xk?1,

?xk?1?T所以一旦接收到数据向量xk+1, 只要计算xk+1xk?1, 然后把它与上一步计算得到的Gk 相加即可. 这样计算Gk的负担不会因为k的增加而加重.

Tk?1【模型分析】计算机计算加法的时间与计算乘法的时间相比可以忽略不计. 因此在考虑计算矩阵乘积的负担时, 只要考察乘法的次数就可以了. 设xk的维数是n, 则Xk = [x1, …, xk]是n?k的矩阵, Gk = XkXkT是n?n的矩阵. 直接计算Gk = XkXkT需要做n2k次乘法. 因而计算的负担会随着k的增加而增加. 但是对于每一个k, 计算xkxkT始终只要做n2次乘法.

Matlab实验题

用Matlab编写一个程序用于处理这个问题.

案例十三. 应用矩阵编制Hill密码

密码学在经济和军事方面起着极其重要的作用. 现代密码学涉及很多高深的数学知识. 这里无法展开介绍.

20

请求重传 噪声 加 信 加 冗 源 密 编 码 识 错 解 信 纠 密 宿 错 信 道 攻击 图29 保密通信的基本模型

密码学中将信息代码称为密码, 尚未转换成密码的文字信息称为明文, 由密码表示的信息称为密文. 从明文到密文的过程称为加密, 反之为解密. 1929年, 希尔(Hill)通过线性变换对待传输信息进行加密处理, 提出了在密码史上有重要地位的希尔加密算法. 下面我们略去一些实际应用中的细节, 只介绍最基本的思想.

【模型准备】若要发出信息action, 现需要利用矩阵乘法给出加密方法和加密后得到的密文, 并给出相应的解密方法.

【模型假设】(1) 假定每个字母都对应一个非负整数, 空格和26个英文字母依次对应整数0~26(见下表).

表9 空格及字母的整数代码表 F G H I J K L M 空格 A B C D E 0 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25 26 (2) 假设将单词中从左到右, 每3个字母分为一组, 并将对应的3个整数排成3维的行向量, 加密后仍为3维的行向量, 其分量仍为整数.

【模型建立】设3维向量x为明文, 要选一个矩阵A使密文y = xA, 还要确保接收方能由y准确地解出x. 因此A必须是一个3阶可逆矩阵. 这样就可以由y = xA得x = yA?1. 为了避免小数引起误差, 并且确保y也是整数向量, A和A?1的元素应该都是整数. 注意到, 当整数矩阵A的行列式= ?1时, A?1也是整数矩阵. 因此原问题转化为

(1) 把action翻译成两个行向量: x1, x2.

(2) 构造一个行列式= ?1的整数矩阵A(当然不能取A = E). (3) 计算x1A和x2A. (4) 计算A?1. 【模型求解】(1) 由上述假设可见x1 = (1, 3, 20), x2 = (9, 15, 14).

?100?

(2) 对3阶单位矩阵E =?010?进行几次适当的初等变换(比如把某一行的整

?001???

数被加到另一行, 或交换某两行), 根据行列式的性质可知, 这样得到的矩阵A的行

21

?110?列式为1或?1. 例如A =?211?, |A| = ?1.

?322????110?(3) y1 = x1A = (1, 3, 20)?211?= (67, 44, 43),

?322????110?y2 = Ax2 = (9, 15, 14)?211?= (81, 52, 43).

?322????10002?1??110100?初等行变换??0101?21?可得 (4) 由(A, E) =?211010??????001?1?11??322001??????02?1?A?1 =?1?21?.

??1?11???这就是说, 接收方收到的密文是67, 44, 43, 81, 52, 43. 要还原成明文, 只要计算(67, 44, 43)A?1和(81, 52, 43)A?1, 再对照表9“翻译”成单词即可.

【模型分析】如果要发送一个英文句子, 在不记标点符号的情况下, 我们仍然可以把句子(含空格)从左到右每3个字符分为一组(最后不足3个字母时用空格补上). 【模型检验】(67, 44, 43) A?1 = (1, 3, 20), (81, 52, 43)A?1 = (9, 15, 14).

参考文献

杨威, 高淑萍, 线性代数机算与应用指导, 西安: 西安电子科技大学出版社, 2009. 页码: 98-102.

Matlab实验题

按照上面的加密方法, 设密文为: 112, 76, 57, 51, 38, 18, 84, 49, 49, 68, 41, 32, 83, 55, 37, 70, 45, 25, 问恢复为原来的信息是什么?

案例十四. 显示器色彩制式转换问题

彩色显示器使用红(R)、绿(G)和蓝(B)光的叠成效应生成颜色. 显示器屏幕的内表面由微粒象素组成, 每个微粒包括三个荧光点: 红、绿、蓝. 电子枪位于屏幕的后方, 向屏幕上每个点发射电子束. 计算机从图形应用程序或扫描仪发出数字信号到电子枪, 这些信号控制电子枪设置的电压强度. 不同 RGB 的强度组合将产生不同的颜色. 电子枪由电磁石帮助瞄准以确保快速精确地屏幕刷新.

图30 彩色显示器的工作原理

颜色模型规定一些属性或原色, 将颜色分解成不同属性的数字化组合. 这就色彩制式的转换问题.

22

【模型准备】观察者在屏幕上实际看到的色彩要受色彩制式和屏幕上荧光点数量的影响. 因此每家计算机屏幕制造商都必须在(R, G, B)数据和国际通行的CIE色彩标准之间进行转换, CIE标准使用三原色, 分别称为X, Y和Z. 针对短余辉荧光点的一类典型转换是

?0.610.290.150??R??X???????0.350.590.063???G?=?Y?. ?0.040.120.787??B??Z???????计算机程序把用CIE数据(X, Y, Z)表示的色彩信息流发送到屏幕. 求屏幕上的电子枪

将这些数据转换成(R, G, B)数据的方程.

?0.610.290.150??R??X???????【模型建立】令A =?0.350.590.063?, ? =?G?, ? =?Y?, 则A? = ?. 现在要根

?0.040.120.787??Z??B???????据CIE数据(X, Y, Z)计算对应的(R, G, B)数据, 就是等式A? = ?中A和?已知, 求?. 如果A是可逆矩阵, 则由A? = ?可得? = A?1?.

【模型求解】在Matlab命令窗口输入以下命令

>> A = [0.61,0.29,0.15;0.35,0.59,0.063;0.04,0.12,0.787]; >> if det(A)==0, 'A不可逆'

elseif 'A可逆, A的逆矩阵如下', B = inv(A), end Matlab执行后得

B =

2.2586 -1.0395 -0.3473 -1.3495 2.3441 0.0696 0.0910 -0.3046 1.2777

?2.2586?1.0395?0.3473???于是? =??1.34952.34410.0696??. 这就是说, 屏幕上的电子枪将CIE

?0.0910?0.30461.2777???数据(X, Y, Z)转换成(R, G, B)数据的方程为

?R??2.2586?1.0395?0.3473??X????????1.34952.34410.0696G=??Y?. ????B??0.0910?0.30461.2777??Z???????Matlab实验题

民用电视信号发送使用向量(Y, I, Q)来描述每种颜色. 如果屏幕是黑白的, 则只用到了Y(这比CIE数据能提供更好的单色图象). YIQ与“标准”RGB色彩之间的对应如下

?Y??0.2990.5870.114??R??I?=?0.596?0.275?0.321??G? ????????Q????0.212?0.5280.311????B??

23

(屏幕制造商需要调整矩阵元素一适应其RGB屏幕.) 求将电视台发送的数据转换

成电视机屏幕所要求数据的方程.

案例十五. 人员流动问题

【模型准备】某试验性生产线每年一月份进行熟练工与非熟练工的人数统计, 然后1将熟练工支援其他生产部门, 其缺额由招收新的非熟练工补齐. 新、老非熟练工经62过培训及实践至年终考核有成为熟练工. 假设第一年一月份统计的熟练工和非熟

5练工各占一半, 求以后每年一月份统计的熟练工和非熟练工所占百分比.

【模型建立】设第n年一月份统计的熟练工和非熟练工所占百分比分别为xn和yn, 记

?xn??x1??1/2?成向量??. 因为第一年统计的熟练工和非熟练工各占一半, 所以??=??. 为yy1/2??1???n?了求以后每年一月份统计的熟练工和非熟练工所占百分比, 先求从第二年起每年一月份统计的熟练工和非熟练工所占百分比与上一年度统计的百分比之间的关系, 即?xn?1??xn??xn?1?求??y??与??y??的关系式, 然后再根据这个关系式求??y??. ?n?1??n??n?1?【模型求解】根据已知条件可得:

12192xn+1 = (1?)xn +(xn + yn) =xn +yn,

6565102113yn+1 = (1?)(xn + yn) =xn +yn,

56510即

?xn?1??9/102/5??xn???. ???y??=???1/103/5??yn??n?1???9/102/5?令A =??, 则

?1/103/5??xn?1??xn?2?xn?1?n?x1?????= A= A= … = A????. ?y??y??y1??n?1??n??yn?1?92??10?5|?E ? A| == (? ? 1)(? ?12), 31?10??5由此可得A的两个特征值?1 = 1, ?2 = 1/2.

解(E ? A)x = 0得对应于?1 = 1的一个特征向量?1 = (4, 1)T,

T

解(12E ? A)x = 0得对应于?2 = 1/2的一个特征向量?2 = (?1, 1).

?4?1??10?令P =?, 则P?1AP = ? =?, A = P?P?1, An = (P?P?1)n = P?nP?1, ???11??01/2?111?xn?1?n?x1?n?1?x1??4?1??10??55??2????01???14??1? ?y??= A?y?= P?P?y?=?11??2n??55??2??1??1???n?1? 24