武汉大学研究生课程数值分析期末考试

武汉大学研究生课程《数值分析》半开卷考试资料姓名：学号：第1章绪论1.1误差的基本概念绝对误差：∆𝑥=𝑥∗−𝑥;∆f(x)=𝑑𝑓(𝑥)=𝑓′(𝑥)𝑑𝑥;绝对误差：∆𝑟𝑥=𝑥∗−𝑥𝑥;∆𝑟𝑓(𝑥)=𝑑𝑓(𝑥)𝑓(𝑥)有效数字：𝑥=(0.𝑎1𝑎2…𝑎𝑛×10−𝑛)×10𝑚,则有n位有效数字。误差限：|∆𝑥|=|𝑥∗−𝑥|≤12×10𝑚−𝑛;|∆𝑟𝑥|≤12𝑎1×10−(𝑛−1)减少误差的原则：如果考的话最可能考：选择稳定的数值计算公式(递推公式，进行变形，放缩求平均，往前迭代)1.2向量范数与矩阵范数1范数：‖𝑥‖1=∑|𝑥𝑖|𝑛𝑖=1列范数：‖𝐴‖1=max𝑗∑|𝑎𝑖𝑗|𝑛12范数：‖𝑥‖2=√∑𝑥𝑖2𝑛𝑖=1谱范数：‖𝐴‖2=√𝜌𝑚𝑎𝑥(𝐴𝑇𝐴)∞范数：‖𝑥‖∞=max0≤𝑖≤𝑛|𝑥𝑖|行范数：‖𝐴‖∞=max𝑖∑|𝑎𝑖𝑗|𝑛11.3条件数Cond(A)=‖𝐴−1‖‖𝐴‖；远大于1时，矩阵病态第2章线性方程组解法2.1Gauss消去法{顺序消去A=LU(Doolittle分解)列主元法PA=LU2.2经典迭代法迭代法误差估计：若某种范数‖𝐺‖1，则有：A𝒙=b;A=D+L+U（1）Jacobi迭代：𝑥(𝑘+1)=𝐺𝐽𝑥(𝑘)+𝑔式中：𝐺𝐽=−𝐷−1(𝐿+𝑈)𝑔=𝐷−1𝑏（2）Gauss-Seidel迭代：𝑥(𝑘+1)=𝐺𝐺𝑆𝑥(𝑘)+𝑔式中：𝐺𝐺𝑆=−(𝐷+𝐿)−1𝑈𝑔=(𝐷+𝐿)−1𝑏经典迭代格式的收敛性判别{充要条件：迭代矩阵ρ(G)1充分条件：𝐺某种范数‖𝐺‖1充分条件：系数矩阵A对角占优第3章非线性方程(组)迭代解法3.1二分法(略)3.2不动点迭代：𝑥=𝜑(𝑥),迭代公式：𝑥𝑘+1=𝜑(𝑥𝑘)根据压缩映射原理，若𝜑(𝑥)在根𝑥∗邻域内有一阶导，且|𝜑′(𝑥∗)|1，则迭代收敛，实际根未知，可用其根邻近值收敛速度：lim𝑘→∞|𝑥∗−𝑥𝑘+1||𝑥∗−𝑥𝑘|𝑝=C(对于收敛的迭代格式，当|𝜑′(𝑥)|=0，则是线性收敛)若碰到求收敛阶：迭代公式是个方程，准确解带进去是个方程，两方程相减，然后适当变形利用微分中值定理。3.3Newton法(二阶收敛)：𝑥𝑘+1=𝑥𝑘−𝑓(𝑥𝑘)𝑓′(𝑥𝑘);假设𝑥∗是f(x)=0的单根,f(x)在𝑥∗的邻域内具有连续的二阶导数且f′(𝑥∗)≠0,则牛顿公式具有局部收敛性；若f′′(𝑥∗)≠0且𝑥0≠𝑥∗,则序列{𝑥𝑘}是平方收敛。第4章矩阵特征值特征向量(略)Householder变换（H=I-2wwT）、Givens变换、幂法第5章插值与逼近5.1插值多项式的唯一性Pn(x)=𝑎0+𝑎1𝑥+𝑎2𝑥2+⋯+𝑎𝑛𝑥𝑛;|𝐴|=∏(𝑥𝑖−𝑥𝑗)≠05.2Lagrange插值多项式：𝐿n(𝑥)=∑𝑙𝑖(𝑥)𝑦𝑖𝑛𝑖=0=∑[{∏𝑥−𝑥𝑗𝑥𝑖−𝑥𝑗𝑛𝑗=0𝑗≠𝑖}𝑦𝑖]𝑛𝑖=0;定义：𝜔𝑛+1(𝑥)=∏(𝑥−𝑥𝑗)𝑛𝑗=0则𝐿n(𝑥)=∑𝜔𝑛+1(𝑥)(𝑥−𝑥𝑖)𝜔′𝑛+1(𝑥𝑖)𝑦𝑖𝑛𝑖=0；插值余项𝑅𝑛(𝑥)=𝑓𝑛+1(𝜀)(𝑛+1)!𝜔𝑛+1(𝑥)≤𝑀(𝑛+1)!|(𝑥−𝑥0)(𝑥−𝑥1)…(𝑥−𝑥𝑛)|熟练当n=1、n=2、n=3的Lagrange插值多项式计算5.3Newton插值多项式差商(建议：利用表格计算更加清楚明了)f[𝑥𝑖,𝑥𝑗]=𝑓(𝑥𝑖)−𝑓(𝑥𝑗)𝑥𝑖−𝑥𝑗;f[𝑥𝑖,𝑥𝑗,𝑥𝑘]=𝑓[𝑥𝑖,𝑥𝑗]−𝑓[𝑥𝑗,𝑥𝑘]𝑥𝑖−𝑥𝑘;……牛顿插值：N(x)=N(𝑥0)+N[𝑥0,𝑥1](x−𝑥0)+𝑁[𝑥0,𝑥1,𝑥2](𝑥−𝑥0)(𝑥−𝑥1)+⋯+𝑁[𝑥0,…,𝑥𝑛](𝑥−𝑥0)…(𝑥−𝑥𝑛−1)插值余项：𝑅𝑛(𝑥)=𝑓[𝑥,𝑥0,…,𝑥𝑛](𝑥−𝑥0)(𝑥−𝑥1)(𝑥−𝑥2)…(𝑥−𝑥𝑛)Lagrange插值形式简单，便于计算，但当增加插值点时，原先所作计算没有利用价值，需从头计算；Newton插值要计算差商表，突出优点是当新增加一个插值点𝑥𝑛+1时，只需在原插值多项式后增加一项。PS：Lagrange插值与Newton插值得到的多项式应一样(插值多项式的唯一性)。5.4Hermite插值(不但满足插值点处函数值相等，还满足插值点处导数也相等)当给出了所有插值点的导数值时：H(x)=∑{𝑦𝑖[1−2(𝑥−𝑥𝑖)𝑙′𝑖(𝑥𝑖)]𝑙𝑖2(𝑥)+𝑦′𝑖(𝑥−𝑥𝑖)𝑙𝑖2(𝑥)}𝑛𝑖=0当插值点处导数条件少于函数值条件，解题两个步骤，第一步先利用Lagrange或者Newton插值公式得到满足插值点处函数值相等的多项式，第二步，将第一步得到的多项式与满足导数值相等的条件相结合，待定系数。插值余项：系数为𝑓𝑛+1(𝜀)(𝑛+1)!，n为插值多项式的最高次方。给出了哪个或哪些点的导数就在哪个点上写成(𝑥−𝑥𝑖)2，其余不加平方。5.5分段低次插值（分段线性插值、分段二次插值，如右式和页最后）5.7最佳(一次、二次)平方逼近一般通式称s*(x)为子空间Ф中对与f(x)在区间[a,b]上带权ρ(x)的最佳平方逼近元素（1）∑𝜑𝑘,φ𝑗𝑎𝑗𝑛𝑗=0=𝜑𝑘,𝑓,取基函数Φ=span{1,x,𝑥2,…，𝑥𝑛}（2）J(𝑎0,𝑎1,…,𝑎𝑛)=∫[𝑃(𝑥)−𝑓(𝑥)]2𝑑𝑥=∫[𝑎0+𝑎1𝑥+⋯+𝑎𝑛𝑥𝑛−𝑓(𝑥)]2𝑑𝑥𝑏𝑎𝑏𝑎，对应偏导等于0进行求解（3）Legendre正交多项式(要将积分区间进行变换：[-1,1])x=𝑏−𝑎2𝑡+𝑏+𝑎2𝑃0(𝑥)=1;𝑃1(𝑥)=𝑥;𝑃2(𝑥)=12(3𝑥2−1);𝑃3(𝑥)=12(5𝑥3−3𝑥);…𝑃𝑛+1(𝑥)=(1+𝑛𝑛+1)𝑥𝑃𝑛(𝑥)−𝑛𝑛+1𝑃𝑛−1(𝑥)𝑐𝑗=𝑷𝒋,𝒇𝑷𝒋,𝑷𝒋=2𝑗+12∫𝑓(𝑥)𝑃𝑗(𝑥)𝑑𝑥1−1;注意，逼近函数什么形式就取基函数什么形式(比如逼近函数y=ax+bx2,基函数就取{x,x2})，基函数是和进行区间变换之后的函数进行积分。得到逼近函数：φ(x)=∑𝑐𝑗𝑛𝑗=0𝑃𝑗(𝑥)第6章数值积分6.1代数精度与插值型求积公式：∫𝑓(𝑥)𝑑𝑥≈∑A𝑗𝑓(𝑥𝑗)𝑛𝑗=0𝑏𝑎,A𝑗=∫∏𝑥−𝑥𝑘𝑥𝑗−𝑥𝑘𝑑𝑥𝑗≠𝑘𝑏𝑎,𝑅𝑛[𝑓]=∫𝑓𝑛+1(𝜀)(𝑛+1)!𝜔𝑛+1(𝑥)𝑑𝑥𝑏𝑎6.2Newton-Cotes求积公式Cotes系数：𝐶𝑗(𝑛)=(−1)𝑛−𝑗𝑗!(𝑛−𝑗)!𝑛∫𝑡(𝑡−1)…(𝑡−𝑗+1)(𝑡−𝑗−1)(𝑡−𝑛)𝑑𝑡;𝐴𝑗=(𝑏−𝑎)𝐶𝑗(𝑛)𝑛0n=1时（梯形公式）：∫𝑓(𝑥)𝑑𝑥≈𝑏−𝑎2𝑏𝑎(𝑓(𝑎)+𝑓(𝑏))𝑅1[𝑓]=−(𝑏−𝑎)312𝑓′′(𝛿),𝛿∈(𝑎,𝑏)n=2时（Simpon公式）：∫𝑓(𝑥)𝑑𝑥≈𝑏𝑎𝑏−𝑎6(𝑓(𝑎)+4𝑓(𝑐)+𝑓(𝑏))𝑅2[𝑓]=−(𝑏−𝑎)52880𝑓4(𝛿),𝛿∈(𝑎,𝑏)6.3复化求积复化梯形公式：∫𝑓(𝑥)𝑑𝑥≈ℎ2𝑏𝑎(𝑓(𝑎)+2∑𝑓(𝑥𝑘)𝑛−1𝑘=1+𝑓(𝑏));ℎ=𝑏−𝑎𝑛截断误差：𝑅𝑛[𝑓]=−𝑏−𝑎12ℎ2𝑓′′(𝛿),𝛿∈(𝑎,𝑏)复化Simpon公式：∫𝑓(𝑥)𝑑𝑥≈ℎ3𝑏𝑎(𝑓(𝑎)+4∑𝑓(𝑥2𝑘−1)𝑚𝑘=1+2∑𝑓(𝑥2𝑘)𝑚−1𝑘=1+𝑓(𝑏));ℎ=𝑏−𝑎𝑛;n=2m(n为偶数）要注意给定的表格里哪个是从1开始，因为它们的系数不一样。截断误差：𝑅𝑠[𝑓]=−𝑏−𝑎180ℎ4𝑓(4)(𝛿),𝛿∈(𝑎,𝑏)6.5Gauss型求积公式（代数精度2n-1,n为Gauss点个数）对于Newton–Cotes公式：积分点n是偶数时，代数精度为n+1，n是奇数时，代数精度为n。（1）待定系数法∫𝑓(𝑥)𝑑𝑥≈∑A𝑗𝑓(𝑥𝑗)𝑛𝑗=1𝑏𝑎取基函数Φ=span{1,x,𝑥2,…，𝑥𝑛}列方程组得到系数和Gauss点（2）正交多项式（需要将积分区间转换为[-1,1]）步骤如下：a)以n+1次正交多项式的零点𝑥0，𝑥1…𝑥𝑛作为积分点(Gauss点)b)用高斯点𝑥0，𝑥1…𝑥𝑛对f(x)作Lagrange插值多项式f(𝑥)=∑𝑙𝑖(𝑥)𝑓(𝑥𝑖)𝑛𝑖=0c)带入积分式∫𝜌(𝑥)𝑓(𝑥)𝑑𝑥≈∫𝜌(𝑥)[∑𝑙𝑖(𝑥)𝑓(𝑥𝑖)𝑛𝑖=0]𝑑𝑥≈𝑏𝑎∑(∫𝜌(𝑥)𝑙𝑖(𝑥)𝑑𝑥)𝑓(𝑥𝑖)𝑏𝑎𝑛𝑖=0𝑏𝑎d)求得积分系数：A𝑖=∫𝜌(𝑥)𝑙𝑖(𝑥)𝑑𝑥𝑏𝑎(i=0,1,…,n)第7章常微分方程数值解{𝑑𝑦𝑑𝑥=𝑓(𝑥,𝑦),𝑎≤𝑥≤𝑏𝑦(𝑎)=𝑦0Euler法：{𝑦𝑛+1=𝑦𝑛+ℎ𝑓(𝑥𝑛,𝑦𝑛),𝑛=0,1,2…𝑦(𝑎)=𝑦0改进的Euler法：{𝑦𝑛+1=𝑦𝑛+ℎ2(𝐾1+𝐾2)𝐾1=𝑓(𝑥𝑛,𝑦𝑛)𝐾2=𝑓(𝑥𝑛+ℎ,𝑦𝑛+ℎ𝐾1)𝑦(𝑎)=𝑦0是否需要根据迭代公式将𝑦𝑛的表达式求出来，看题目的要求。另外，注意步距h及x的区间，它决定了需要迭代的次数。PS：以上资料为武汉大学研究生课程《数值分析》半开卷考试资料，仅供参考22()()()()min()()()bbaasxxfxsxdxxfxsxdx11111)()(iiiiiiiiyxxxxyxxxxxPxf1222112112()()()()()()()()()()iiiiiiiiiiiiiixxxxxxxxfxPxyyxxxxxxxx12221()()()()iiiiiiixxxxyxxxx