华科数值分析期末复习总结.pptVIP

* Newton 法 算法 ：( Newton 法 ) (1) 任取迭代初始值 x0 (2) 对 k = 1, 2, ... , maxit，计算 判断收敛性，若收敛，则停止计算，输出近似解 * 收敛性 k = 0, 1, 2, . . . 迭代函数 牛顿法至少二阶局部收敛 * 举例 例：用 Newton 法求 f(x) = x2 – C=0 的正根, 并验证这一方法的二阶收敛性 解： 对任意 x00， 总有 |q|1， 即牛顿法收敛 * 举例 二阶收敛 关于二次收敛性，事实上 * 第九章常微分方程的数值解法 一阶常微分方程初值问题是： y ? = f(x , y) (1.1) y(x0) = y0 (1.2) 其中f 是已知的xOy平面上某个区域D上连续函数，式(1.1)是微分方程，有无穷多解，式(1.2)是确定解的初始条件。 一、基本知识 求初值问题，是给出它的解在某些节点数值的近似值，这称为数值离散方法。求数值解一般逐步进行，分单步法与多步法： 单步法：在计算yk+1之时只用到yk 多步法：在计算yk+1之时不仅用到yk ，还要用yk-1，yk-2，… 一般m 步法要用到yk , yk-1 , yk-2 , … yk-m+1 二者都有显式方法和隐式方法之分。 (一)Euler公式：就是用差分方程的初值问题 的解来近似微分方程初值问题的解。称为显式 Euler公式。 (二)隐式Euler公式： 也称为向后 Euler公式。 (三)梯形公式：两种Euler公式作算术平均（隐式） 通常，对于隐式公式，采用预测—校正技术，即先用显式方法计算，预测一个值 ，为隐式公式提供一个好的迭代初值，然后用隐式公式迭代一次，得到yk+1。如果用显式Euler公式预测，梯形公式校正，即 称为改进的Euler公式。为便于编程，常改写为： * 稳定性理论分析 定理：考虑线性方程组 Ax=b，设 b 是精确的，A 有微小的变化 ?A，此时的解为 x + ?x ，则 证明： 当 ?A 充分小时，不等式右端约为 设 结论 * 矩阵条件数 条件数与范数有关，常用的有无穷范数和2-范数 Cond(A)2 称为谱条件数，当 A 对称时有 * 举例 例： 计算 Cond(A)? 和 Cond(A)2 解： Cond(A)?=||A-1|| ? ||A|| ? ? 4?104 Cond(A)2=?max / ?min ? 4?104 A 对称，且 * 第六章线性方程组的迭代解法 * 矩阵分裂迭代法 矩阵分裂迭代法基本思想 Ax = b k = 0, 1, 2, … 给定一个初始向量 x(0)，可得 迭代格式 其中 B = M-1N 称为迭代矩阵 A = M - N Mx = Nx + b M 非奇异 A 的一个 矩阵分裂 * 收敛性分析 定理：对任意初始向量 x(0)，上述迭代格式收敛的充要条件是 证明：板书 定理：若存在算子范数 || · ||，使得 ||B|| 1，对任意的初始向量 x(0)，上述迭代格式收敛。 例：考虑迭代法 x(k+1) = Bx(k) + f 的收敛性，其中 基本收敛定理 充分条件 * Jacobi 迭代 考虑线性方程组 Ax = b 其中 A=(aij)n?n 非奇异，且对角线元素全不为 0。 将 A 分裂成 A = D - L- U， 其中 * Jacobi 迭代 k = 0, 1, 2, … 令 M = D，N = L + U，可得 雅可比 (Jacobi) 迭代方法 Jacobi 迭代 迭代矩阵记为： 分量形式： i = 1, 2, … , n， k = 0, 1, 2, … * Gauss-Seidel 迭代 在计算 时，如果用 代替 ，则可能会得到更好的收敛效果。 * Gauss-Seidel 迭代 写成矩阵形式: 此迭代方法称为 高斯-塞德尔 (Gauss-Seidel) 迭代法 k = 0, 1, 2, … 可得 迭代矩阵记为： * SOR 迭代 为了得到更好的收敛效果，可在修正项前乘以一个 松弛因子?，于是可得迭代格式 在 G-S 迭代中 * SOR 迭代 写成矩阵形式: 可得 —— SOR (Successive Over-Rel