计算机问题求解 – 论题 矩阵计算 2018年12月20日 有限维空间与数量关系的强有力工具

Presentation on theme: "计算机问题求解 – 论题 矩阵计算 2018年12月20日 有限维空间与数量关系的强有力工具"— Presentation transcript:

1 计算机问题求解 – 论题3-14 - 矩阵计算 2018年12月20日 有限维空间与数量关系的强有力工具
计算机问题求解 – 论题 矩阵计算 2018年12月20日 有限维空间与数量关系的强有力工具 数字图像处理、计算机图形学、计算几何学、人工智能、网络通信、以及一般的算法设计和分析等

2 矩阵的逆与线性方程组的解 Cramer’s rule:如果线性方程组的系数行列式不为0，方程有唯一解。
系数方阵的逆：伴随矩阵处以系数行列式的值 伴随矩阵：代数余子式矩阵

3 问题1： 为什么通常不直接用求 逆矩阵的办法来解线性 方程组？ 速度慢，n3方

4 逆矩阵存在的条件 A的行列式为0： A1,i(i从1到n）和它的代数余子式乘积子和 这是什么意思？

5 问题2: 如何计算非奇异矩阵的逆？ 1：矩阵A的逆=A的伴随矩阵/行列式A的值 2：矩阵A的逆：对(A|E)进行行初等变换得到(E|A-1)

6 问题3.1：求N阶方阵的逆，时间复杂度多少？ N的四次方

7 问题3.1：求N阶方阵的逆，时间复杂度多少？ N的三次方 ……

8 高斯消元法过程中可能出现的现象！ 问题4： 三角阵会给解 线性方程组带 来什么便利？

9 问题5： 三角阵确实会极大简化方程求解，但是 多数情况下，我们不会遇到三角阵。 怎么办？ 三角阵可以直接使用代入法求得X

10 问题6： 你能否借助右边 的图解释一下用 LUP分解方法解 线性方程组的基 本思想？这个方 法的关键在哪里？
任意的非奇异矩阵均能保证可以分解为两个上、下三角矩阵的乘积，但是，从算法角度求解，会遇到困难。 但是，针对任意的非奇异矩阵A，我们总是能够找到一个“相关矩阵（转换矩阵）”P，使得PA能够顺利地被分解为两个上、下三角矩阵的乘积 PA=LU

11 问题7： π数组是什么？ 向量bpi中的元素是向量b中元素在P转换矩阵作用下，变换次序得到的 So:

12

13 If we have LUP, we can solve the equations in Θ(n2)
But, how can we get LUP?

14 问题8：从以下的例子中，我们能观察到什么现象？我们能如何猜想？
第一行矩阵分解就是高斯消元法；右边U就是消去后的方程系数矩阵，左边的L就是消去时的过程参数

15 假如可以不考虑P 问题10： 我们对 如何处理？ 问题9： 为什么说这是采 用了“高斯消去 法”？

16 问题11： 我们确定能对 进行 递归处理吗？

17 该页中矩阵的秩如果不满，A的秩也一定不满，A一定不是非奇异的

18 递归显然是可行的： L矩阵中的对角线以下元素的值，本质上就是高斯消元法消元时使用的“倍数”，其中涉及到了除法，导致可能的溢出，以及容易被忽略的“大误差”

19 结论 递归 = ×

20 递归，总是开销大的，可以写成循环的 问题12.1: 为什么算法中并没有用递归?

21 控制对角线，控制递归的！ 问题12.2: 算法中的控制变量k是控制行？列？还是什么？

22

23 这个循环在干什么？ 做舒尔补的递归的计算 问题12.2: 算法中的控制变量k是控制行？列？还是什么？

24 这个操作确定 能做吗？ 问题12.3:这个算法中有bug吗?

25 问题13: 下例我们遇到了什么困难？ 你有解决思路吗？ 确保不会选择0为被除数或者一个非常小的数为被除数
如果在某列中找不到非0元素，在该次递归运算中，矩阵就不再是非奇异的，会导致此次递归前的k+1矩阵奇异，……最终导致A奇异。有矛盾。

26 问题14: 为什么需要置换矩阵？为什么一定能够找到可置换的行？ 用置换矩阵进行主元选择（行初等变换：交换最大元到第一行）
某次递归过程中，如果舒尔补第一列全为0，该矩阵一定奇异， 递归前的矩阵一定奇异，进而原矩阵一定奇异

27 初等行变换，你能写出Q吗？ 递归 交换1,3两行的Q矩阵 Q：第一行的第k列为1，第一列的第k行为1，其它主对角线元素（除1,1和k,k外）为1.其它为0 我们需要将P’和Q综合起来！

28 递归可行吗？ 递归 必须清楚P的结构和Q的存在 PA=LU而且无需担心除0或者不稳定！
1，Q：第一行的第k列为1，第一列的第k行为1，其它主对角线元素（除1,1和k,k外）为1.其它为0 2，舒尔补是可递归求解的，可以得到P‘L‘U’ 3，在P’L’U’的基础上构造PLU，特别是P的构造还和Q有关：完成PA=LU。我们需要将P’和Q综合起来！ PA=LU而且无需担心除0或者不稳定！

29 行置换的处理 问题15: 如何理解数组pi？ Pi是个置换矩阵P的数组表示方式，pi[i]=j且j不等于0时，意味着置换矩阵：p[I,j]=1

30 K=1；k’=3，交换pi[1]和pi[3] K=2；k’=3，交换pi[2]和pi[3] K=3；k’=4，交换pi[3]和pi[4]
问题16：置换矩阵如何获得？

31 …… 问题17： 算法中并没有出现两个三角 矩阵,这些矩阵的值是如何 体现的？ A数组沿对角线划分

32 Pi数组 K=1；k’=3，交换pi[1]和pi[3] (递归)计算舒尔补 Pivot选择 计算L矩阵值 换行 就是pi数组

33 你能否解释一下，为什 么可以利用LUP分解来 计算逆矩阵？
问题18： 你能否解释一下，为什 么可以利用LUP分解来 计算逆矩阵？ AX=I

34 问题19： 这有多复杂？ 定义X矩阵的每一列为Xi； AXi= ei线性方程组求解，可以解出Xi，开销是n平方(有了PLU之后)
解出n个上述方程组，需要n的三次方 问题19： 这有多复杂？

35 Open topics 用循环不变式方法，证明LUP分解算法的正确性 如何用PLU分解求矩阵的行列式？