七八线性方程的数值解.PPT

运算量 （Amount of Computation） （1）用克莱姆（Cramer）法则求解n阶线性方程组 （2） 高斯消去法: 第1个消去步， 计算li1(i=2,3，…，n)， 有n-1次除法运算. 使aij(1)变为 aij(2) 以及使bi(1)变为bi(2)有n(n-1)次乘法运算. 回代过程的计算 除法运算次数为n次. 乘法运算的总次数为 n+(n-1)+…+1=n(n-1)/2次 列主元消去法 在第k 步消元前，在系数矩阵第k 列的对角线以下的元素中找出绝对值最大的元。 6.1.2 三角分解法 一般计算公式 LU 分解求解线性方程组 6.1.4 求解正定方程组的Cholesky方法 对称正定阵A的几个重要性质： （1）A?1 亦对称正定，且 aii 0 （2）A 的顺序主子阵 Ak 亦对称正定 （3）A 的特征值 ?i 0 （4）A 的全部顺序主子式 det ( Ak ) 0 定理 1.5 设矩阵A对称正定，则存在唯一的对角元全为正的下三角阵G 使得 A＝GGT 6.1.5 求解三对角方程组的追赶法 Ex: 设A＝(aij)∈M. 定义 相容性 （1）矩阵范数与矩阵范数的相容:‖AB‖≤‖A‖‖B‖ Gauss消去法的舍入误差 §6.5 解线性方程组的迭代法  迭代法的基本思想 Jacobi迭代和Gauss－Seidel迭代 迭代法的收敛性 超松弛迭代SOR 迭代法的基本思想 例：求解方程组 设Ax=b，A非奇异，且对角元不为零，将原方程组改写为 又代入，反复继续，得迭代格式： Gauss－Seidel迭代法 若在迭代时尽量利用最新信息，则可将迭代格式变为 其中 BG-S=(D-L)-1 U 称Gauss－Seidel迭代矩阵. 注2 （2）Jacobi迭代法和Gauss-Seidel迭代法的收敛性没有必然的联系： 迭代法收敛的其他结论： 定义 设A=(aij )n×n ?Rn×n ，若 (i=1,2,…,n) 则称A为对角占优矩阵，若不等式严格成立，则称A为严格对角占优矩阵. 对于BJ=I-D-1A,有 Thm 若系数阵严格对角占优， 若 0 ? ≤1 ，则松弛法收敛.(P 171) 注：对于SOR，希望找 ? 使得 ? ( H? ) 最小. 只是对于某些特殊的矩阵，可以找到最优的迭代系数，对于一般矩阵，即便是对称正定的矩阵目前尚未有理想结果. 6.5 共轭斜量法（Conjugate Gradient Methods) 属于一种迭代法，但如果不考虑计算过程的舍入误差，CG算法只用有限步就收敛于方程组的精确解. Outline Background Steepest Descent Conjugate Gradient Conjugate gradient method is maybe the most popular optimization technique based on what we’ll see here. Directional Derivatives: first, the one dimension derivative Directional Derivatives :  Along the Axes… Directional Derivatives :  In general direction… The Gradient: Definition in The Gradient: Definition in Main Idea A method to solve quadratic function minimization: (A is symmetric and positive definite) Conjugate Gradient Originally aimed to solve linear problems: Later extended to general functions under rational of quadratic approximation to a function is quite accurate. 5 最速下降法 求解二次泛函数极小点的爬山法 最速下降法 最速下降法的算法 共轭方向法 共轭梯度法 共轭梯度法的理论 共轭斜量法与最速下降法的比较 松弛法 SOR Successive over relaxation 换个角度看Gauss - Seidel 方法： 其中ri(k+1)