中山大学-数值分析-复习神器.docVIP

考试允许带简单的计算器，切勿使用智能手机、电脑等设备！ 学院规定，试题必须用英文出，请同学们做好准备。英文的试题中的英文词汇很少，基本上都是在课堂上使用过的。我们尽量在最后两次课和复习中，概括所有可能出现的词汇。 复习 Chapter 1 Significant digit（有效数字） Approximate value True value 切勿简单地比较有几个数字相同。一定要先计算绝对误差的绝对值，然后看小于哪位的半个单位，最后再往前数到首个非零的数字。 例如，假设有5位有效数字，，则 Iteration for solving x=g(x) Fixed point Theorem The key point is to select an interval [a, b] , y=g(x) satisfies 自映射：[a, b]到[a, b]的映射 压缩：存在，使得 或 注意：与无关。 Results: There is one and only one fixed point: x=g(x) 该不动点必为吸性不动点 For any initial point in [a, b], the iteration converges to fixed point 注：选择哪些初值，不动点迭代会收敛？ 应用不动点定理，For any initial point in [a, b] 如果某个初值，迭代若干次后，则继续迭代下去，不动点定理保证迭代收敛到唯一的吸性不动点。 事前误差估计： 事后误差估计： Attractive fixed point、中性(Neutral)不动点、斥性(repulsive)不动点的判定 常见的迭代格式 Newton’s Methods Newton-Raphson iteration function（牛顿迭代函数） Recursive rule（递推规则） Speed of convergence（收敛速度），用不动点迭代收敛速度的判断，可以 计算出： Order of convergence is 2 for single root 1 for multiple root. 注意应用牛顿迭代法的前提条件： 函数f在闭区间[a,b]二阶连续可微 函数f在闭区间有零点p 在零点的导数非零（单根）： Secant method（弦截法） Iteration formula（迭代公式） Speed of convergence（收敛速度）：Order of convergence is for single root Horner’s method（秦九韶算法） Exercise Write out a recursive rule to evaluate a polynomial and it derivative at the same time。 Bisection Approximate value 误差估计 Chapter 2 Gaussian Elimination（高斯消去法） Elimination and back substitute 直接使用高斯消去法求解方程组 选列主元以减少误差 Triangular factorization A=LU, 对应于不做行交换的高斯消去法 PA=LU，对应于行交换（列主元）的高斯消去法 参见作业和讲义上的分解算法 Solution of a Linear System Elimination and back substitute 计算复杂性： Using triangular factorization 首先将矩阵A做PA=LU分解，在此基础上再来求解方程组。 求解n个方程组就可以得到矩阵的逆矩阵 A的行列式正好就是矩阵U的对角线上元素之积 Computational Complexity。已知LU分解， 求线性方程组AX=b的计算量 求逆矩阵的计算量 LU分解的Computational Complexity： Iterative Methods for Linear Systems，掌握迭代格式 Jacobi Iteration Gauss-Seidel Iteration 矩阵的表示形式和一般的代数表示形式 Vector norm, Matrix norm 懂得如何计算向量的1范数、二范数和无穷范数 矩阵的1范数（列范数）和无穷范数（行范数） 2范数的计算公式参见教案： 掌握线性方程组迭代收敛的条件 当时，迭代收敛 Chapter 3 书上介绍了求解插值问题的三种方法： 拉格朗日插值基法 牛顿