数值计算方法复习提纲

数值计算方法复习提纲第一章数值计算中的误差分析12．了解误差(绝对误差、相对误差)3．掌握算法及其稳定性，设计算法遵循的原则。1、误差的来源模型误差观测误差截断误差舍入误差2误差与有效数字绝对误差E（x）=x-x*绝对误差限**xxx相对误差***/)(/)()(xxxxxxxEr有效数字mnaaax10.....021*若nmxx1021*，称*x有n位有效数字。有效数字与误差关系（1）m一定时，有效数字n越多，绝对误差限越小；（2）*x有n位有效数字，则相对误差限为)1(11021)(nraxE。选择算法应遵循的原则1、选用数值稳定的算法，控制误差传播；例101dxexeIxnneInIInn11101△!nxn△x02、简化计算步骤，减少运算次数；3、避免两个相近数相减，和接近零的数作分母；避免第二章线性方程组的数值解法1．了解Gauss消元法、主元消元法基本思想及算法；2．掌握矩阵的三角分解，并利用三角分解求解方程组；（Doolittle分解；Crout分解；Cholesky分解；追赶法）3．掌握迭代法的基本思想，Jacobi迭代法与Gauss-Seidel4．掌握向量与矩阵的范数及其性质,迭代法的收敛性及其判定。本章主要解决线性方程组求解问题，假设n行n列线性方程组有唯一解，如何得到其解？nnnnnnnnnnbxaxaxabxaxaxabxaxaxa............22112222212111212111两类方法，第一是直接解法，得到其精确解；第二是迭代解法，得到其近似解。一、Gauss消去法1、顺序Ｇauss消去法记方程组为：)1()1(2)1(21)1(1)1(2)1(22)1(221)1(21)1(1)1(12)1(121)1(11............nnnnnnnnnnbxaxaxabxaxaxabxaxaxa消元过程：经ｎ－１步消元，化为上三角方程组)()(2)(21)(1)2(22)2(221)2(21)1(11)1(11......nnnnnnnnnnbxaxaxabxaxabxa第ｋ步若0)(kkkankjinkbaabbaaaaakkkkkkikkikikkjkkkkikkijkij,....,1,1,...1)()()()()1()()()()()1(回代过程：nijiiijiijiiinnnnnnnniaxabxabx1)()()()()()1,...2,1(/)(/２、Ｇauss—Ｊｏｒｄａｎ消去法避免回代，消元时上下同时消元３、Ｇauss列主元消去法例：说明直接消元，出现错误32200001.02121xxxx由顺序Ｇauss消去法，得0,112xx；Ｇauss列主元消去法原理：每步消元前，选列主元，交换方程。算法：将方程组用增广矩阵(1)ijnnAba表示。（1）消元过程：对k=1,2,n-1,选主元，找{,1,,}kikkn使得,maxkikikkinaa如果,0kika，则矩阵A奇异，程序结束；否则执行3。如果kik，则交换第k行与第ki行对应的元素位置，,,,1.kkjijaajkn消元，对i=k+1,,n,计算,ikikkkala对j=L+1,,n+1,计算ijijikkjaala（2）回代过程：1．若0,nna则矩阵A奇异，程序结束；否则执行。2,1;1,,2,1,nnnnnaxina对计算,11ninijjjiiiiaaxxa举例说明。4、消元法应用（1）行列式计算；（2）矩阵求逆。二、利用矩阵三角分解求解线性方程组1、求解原理线性方程组写成矩阵形式为：AX=b若A=LU，则LUX=b，记UX=Y则LY=b若L、U为特殊矩阵，则求解线性方程组变为解两个特殊线性方程组问题。2、Doolittle分解L为下三角矩阵,U为上三角矩阵,不一定能分解,分解也不一定唯一;设L或U是单位三角矩阵,若能分解,则可分解唯一.L是单位下三角矩阵,称为Doolittle分解;U是单位上三角矩阵,称为Crout分解；定理:n阶矩阵A有唯一分解的充要条件为A的前n-1阶主子式都不为0.Doolittle分解算法：nnnnnnnnnnnnuuuuuulllaaaaaaaaa............1............11.....................222112112121212222111211由矩阵乘法：nkkjikijula1得到：11;,...1,krrjkrkjkjnkkjulaunkkiuulalkrkkrkirikik,...1,/)(11算法特点：先计算U的行，再计算L的列，交替进行；存储时可用紧凑格式。矩阵分解后，解两个三角方程组：LY=b，UX=Y1111,...3,2ikkikiiniylbybynikiikikiinniuxuyx11,...1,/)(3、Crout分解若L为下三角矩阵，U是单位上三角矩阵，则称Crout分解；算法特点：先计算L的列，再计算U的行，交替进行。4、正定对称矩阵的平方根法（Cholesky分解）（1）正定对称矩阵性质与判定：定义：是n阶对称矩阵，若对任意非零向量nRX，有0AXXT，则称A为正定对称矩阵；判定：A为n阶正定对称矩阵充要条件A的各阶顺序主子式大于0。（2）Cholesky分解定理：设A为n阶正定对称矩阵，则存在唯一主对角线元素都是正数的下三角阵L，使得TLLA.Cholesky分解算法：nnnnnnnnnnnnnnlllllllllllllaaaaaaaaa.............................................222112112122211121222211121121112)(jkjkjjjjlal11/)(jkjjjkikijijlllalnjjinj,...2,1;,...2,15、追赶法三对角矩阵的特殊分解nnCnnnnnnucuuculllbacbacbacbacb1-n12113211133322211......1......111....2niclbuualbuiiiiiii,...3,2/1111三对角方程组的追赶法：追的过程LY=Dniyldydyiiii,...3,2111赶的过程UX=Y1,....,2,1/)(/1nniuxcyxuyxiiiiinnn§2线性方程组的迭代解法一、Jacobi迭代公式例：212121212121xxxx其解为1,121xx方程变形得到迭代公式21212121)(1)1(2)(2)1(1kkkkxxxx给初值00)0(X计算，观察解的变化。一般地，对线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa............22112222212111212111若0iia，则可从第i个方程中解出ix,得到Jacobi迭代公式：nnknnnknnkniikninkiikiknnkkaxaxabxaxaxabxaxaxabx/)...(.../).......(.../)...()(1)(11)1()()(11)1(11)(1)(2121)1(1简记为：niaxabxiinijjkjijiki,...,2,1/)(1)()1(二、Gauss--Seidel迭代公式niaxaxabxiiijnijkjijkjijiki,...,2,1/)(111)()1()1(三、SOR迭代公式四、迭代公式的矩阵表示DGXXkk)()1(§3迭代公式的收敛性一、向量与矩阵的范数与性质1、向量范数定义：向量nRX，对应非负实数X，满足三条件：（1）非负性0,0,0XXX（2）齐次性XkkX（3）三角不等式YXYX称X为向量范数2、常见向量范数1范数nxxxX...2112范数222212...nxxxX∞范数ixniX1max3、矩阵范数定义：方阵nnRA，对应非负实数A，满足三条件：（1）非负性0,0,0AAA（2）齐次性AkkA（3）三角不等式BABA（4）绝对值不等式BAAB称A为矩阵范数；向量范数与矩阵范数相容性：XAAX4、常见矩阵范数1范数，列范数：niijnjaA111max∞范数，行范数：njijniaA11max2范数，谱范数：F范数：ninjijFaA112举例计算二、迭代公式收敛性的判定1、向量的极限2、矩阵的谱半径：iiniA1max)(为特征值；3、收敛性的判定收敛的充要条件：迭代公式DGXXkk)()1(收敛的充要条件为谱半径1)(G。判定定理1：若,1G则迭代公式DGXXkk)()1(收敛。判定定理2：若对方程AX=b的系数矩阵A为对角占优，则Jacobi迭代公式，Gauss--Seidel迭代公式收敛；判定定理3：若对方程AX=b的系数矩阵A为对称正定，则Gauss--Seidel迭代公式收敛；Jacobi迭代公式收敛与Gauss--Seidel迭代公式收敛关系举例：第三章非线性方程的数值解法1．了解二分法的原理与算法；2．掌握一般迭代法的基本思想及其收敛性判定；3．掌握Newton切线法、弦截法，并用它们求方程近似根的方法。本章问题：求方程f(x)=0的根§1二分法一、根的存在性定理：函数f(x)在区间[a，b]连续，且f(a).f(b)0,则方程f(x)=0在区间[a，b]有根。方程的根存在，不一定唯一，若在区间[a，b]上有唯一根，称区间[a，b]为根隔离区间。二、二分法（区间逐次分半法）原理：通过计算根隔离区间中点，将区间分半，缩小区间，得到方程近似根数列{}nx。...,....,,11nnbababakkkabab2/)(取2/)(*nnbax§2迭代法一、迭代原理迭代法是一种逐次逼近法，由提供的递推公式计算，逐次精确，直到满足精度要求。方程f(x)=0变形为)(xx，得到递推公式)(1kkxx--------简单迭代公式称)(x为迭代函数给初值计算，得到数列{}nx，若*limxxkk，则称迭代收敛，否则发散。例：求方程]4.0,3.0[0210*xxx写出两个简单迭代公式：（1）2101kxkx（2）)2lg(1kkxx观察计算得到数列{}nx的收敛性。迭代法的几何解释：二、迭代收敛性判定收敛性定理：设方程)(xx的迭代函数)(x在[a，b]满足：（1）当],[bax时，)(x],[ba；（2）)(x在[a，b]可导，且1)(Lx，],[bax，则（1）方程)(xx在[a，b]有唯一根*x；（2）迭代公式)(1kkxx收敛，即*limxxkk；（3）误差估计01*1xxLLxxkk。说明可根据迭代函数)(x的导数判断迭代收敛性。三、迭代公式的加速§3Newton迭代法一、Newton切线公式几何作法迭代公式