数值分析课件典型例题与习题最新版本.ppt

三 四章内容提要典型例题分析 数值分析 典型例题II 化难为易 化繁为简 化繁为简 初等行变换不改变方程组的解 1 交换矩阵的第i行与第j行的位置 2 以非零数k乘以矩阵的第i行的每个元素 3 把矩阵的第i行的每个元素的k倍加到第j行的对应元素上去 A n 1 Fn 1Fn 2 F1A 其中Fk为Frobenius矩阵 A F1 1F2 1 Fn 1 1A n 1 直接方法 高斯消元法 LU 高斯消元法本质是矩阵的分解 矩阵分解 Top10Algorithms 1 特征值分解 A CDC C D eig A 3 LU分解 PA LU L U P lu A 4 Cholesky分解 A LLT R chol A 2 奇异值分解 A USV U S V svd A 5 非负矩阵分解LearningthePartsofObjectsbyNon negativeMatrixFactorization Nature 1999 Demo1 I imread monalisa pgm U S V svd double I s diag S n1 5 Snew diag s 1 n1 zeros size s 1 n1 1 figure imshow U Snew V n2 20 Snew diag s 1 n2 zeros size s 1 n2 1 figure imshow U Snew V 迭代法思想 Iterate Tosayordoagainoragainandagain 迭代背后的思想是一种与传统思维模式截然不同的方式 传统思维方式往往希望一遍做好 一次成功 但是迭代开发意味着反复地做 不断地根据反馈进行调整 迭代格式构造 收敛条件 局部vs全局 中止准则 加速 松弛思想 Aitken加速方法超松弛加速方法 共轭梯度法的关键是构造一组两两共轭的方向 第k步迭代生成共轭方向张成k维子空间 巧妙的是共轭方向可以由上次搜索方向和当前的梯度方向组合产生 现代迭代方法 Top10Algorithms 最速下降法思想简单 但收敛速度慢 本质上因为负梯度方向函数下降快是局部性质 复杂性 高斯消元法共用乘法和除法次数为n3 3 n2 n 3 常用记号O表示是多少阶的 则O n3 3 注释2 复杂性对估计求解大型方程组所需的时间有用 例如在一台特定的计算机上求解n 500个方程的方程组所需的时间我们可以通过求解一个n 50个方程的方程组得到一个很好的猜测 即对用掉的时间按比例放大1000倍 注释1 按O的记法 把n的不同次幂相加的结果仅保留了最高次幂 因为最高次幂决定了当n趋近无穷时的极限形态 换而言之 对于大的n 低阶项对算法的执行时间的估计没有太大影响 仅需要近似估计执行时间时可以忽略不计 常用的范数 Hilbert矩阵条件数 fori 1 10c i cond hilb i 2 vander 1 i end plot 1 10 c 范数 全局 问题的好与坏 算法的快与慢 X k 1 X B X k X 范数的威力和魅力 ekT 0 010 0 I mkekT Fk 1 I mkekT k 1 2 n 1 F1 1F2 1 Fn 1 1 Fk 1Fj 1 I mkekT mjejTk j F1 1F2 1 Fn 1 1 I m1e1T mn 1en 1T 例1 ekTmj 0 k j 例2 设A为对称矩阵 高斯消元法一步后 A约化为 证明B也是对称矩阵 约化主元不为零的判断 定理3 1约化主元的充分必要条件是矩阵A各阶顺序主子式不等于零 即 例4 严格对角占优矩阵的约化主元ak k k 1 0 k 1 n 例3 严格主对角占优矩阵一定是非奇异的 严格对角占优矩阵 高斯消元法中约化主元不等于零 Jacobi方法 GS方法和SOR方法收敛 思考 若A是严格对角占优矩阵 当0 w 1时 SOR方法收敛 例5 Ax b 其中A对称正定 问解此方程的Jacobi迭代法是否一定收敛 对称正定矩阵 直接法高斯消元法中约化主元大于零 迭代法GS方法 SOR方法 最速下降方法和共轭梯度法收敛 例6 例7 例8 病因是条件数大 病症是什么呢 例9 矩阵的Doolittle分解 A LU L为单位下三角矩阵 U为上三角矩阵 a11 u11 a1n u1n a21 m21u11 an1 mn1u11 对A的元素aij 当j k和i k 1时 m21u12 u22 a22 m21u1n u2n a2n u22 a22 m21u12 u2n a2n m21u1n m31u12 m32u22 a32 mn1u12 mn2u22 an2 m32 a32 m31u12 u22 mn2 an2 mn1u12 u22 矩阵L和矩阵U的元素计算公式 计算次序 更新顺序 先行后列 列除行不除 旧元素减去所在行和列前k 1分量点乘的加和 Doolittle分解 更新顺序 先列后行 行除列不除 旧元素减去所在行和列前k 1分量点乘的加和 Crout分解 求矩阵的Doolittle分解 三对角矩阵分解 步骤I 三对角矩阵分解A LU k 2 3 n 下三角方程组LY f 步骤II 上三角方程组UX Y 步骤III 求解三对角方程组的追赶法 对称正定矩阵的Cholesky分解 1 对于非零向量 xTAx总是正的 2 A的顺序主子式全大于零 3 A的特征值全为正实数 helpchol 对称正定矩阵 1 序列收敛2 迭代矩阵谱半径小于13 迭代矩阵特征值全小于14 迭代矩阵范数小于15 反证法 迭代法收敛证明思路 例10 设A是一个可逆矩阵 矩阵序列满足Xk 1 Xk 2I AXk k 0 1 2 则当时 证明 由Xk 1 Xk 2I AXk 得I AXk 1 I AXk 2I AXk I AXk 2于是I AXk I AXk 1 2 I AXk 2 2 2 例11 思路 1 A 1 B I R R2 2 任意给定n阶矩阵X0 由迭代格式Xk 1 XkR B k 0 1 2 产生的矩阵序列 Xk 收敛到矩阵A 1 3 对矩阵序列 Xk 有误差估计式 例12 设A是n阶可逆矩阵 有A的一个近似逆B 令R I AB 如果 R q 1 试证明 收敛的w取值范围 例13 方程组Ax b 其中A是对称正定阵 讨论迭代格式 思路 例14 思路 续例14 思路 例15 思路 定理4 1对任意的f和任意的初始向量X 0 迭代法X k 1 BX k f收敛的充分必要条件是 例16 思路 例17 思路 1 2 a 1 2收敛 1 2 a 1时系数矩阵正定 例18 例18 例18 参考 WrittingFastMatlabCodes 1 中小规模线性方程组x A b SolvesA x b 2 超 大规模线性方程组 Preconditionedcg 作业 题目1 从理论角度 复杂度和收敛性 比较各种方法的优劣 题目2 从数值角度比较各种方法的性能 公平 题目3 科研或生活中遇到的线性方程组 提示 参考代码 Matlab代码 IterativeSolver 1 如何生成方程组A gallery poisson n b ones size A 1 1 x0 zeros size A 1 1 2 如何生成方程组矩阵市场 UFSparseMatrixCollection 提示 3 更具挑战和趣味的例子图像编辑参考 Matlab代码 Possion图像复原参考 DeblurringImages Matrices Spectra andFilteringGooglePageRank参考 NumericalComputingwithMATLAB数据挖掘和模式识别参考 MatrixMethodsinDataMiningandPatternRecognition高光谱图像解混参考 SparseUnmixingofHyperspectralData医学成像参考 MathematicalMethodsinImageRecon