crout分解法

第一章 非线性方程和方程组的数值解法 12，若1p =则要求01c <<3）单点迭代收敛定理：定理一：若当[],x a b ∈时，[](),x a b ϕ∈且，[],x a b ∀∈，则迭代格式收敛于唯一的根；定理二：设()x ϕ满足： ①[],x a b ∈时，[](),x a b ϕ∈，则对任意初值[]0,x a b ∈迭代收敛，且：定理三：设()x ϕ在α的邻域内具有连续的一阶导数，且'()1ϕα<，则迭代格式具有局部收敛性；定理四：假设()x ϕ在根α的邻域内充分可导，则迭代格式1()i i x x ϕ+=是P 阶收敛的 ()()()0,1,,1,()0j P j P ϕαϕα==-≠（Taylor 展开证明）4）Newton 5）Newton 迭代法收敛定理：设()f x 在有根区间[],a b 上有二阶导数，且满足： ①：()()0f a f b <； ②：[]'()0,,f x x a b ≠∈；③：[]'',,f x a b ∈不变号④：初值[]0,x a b ∈使得''()()0f x f x <；则Newton 迭代法收敛于根α。

6）Newton 迭代法求重根（收敛仍为线性收敛），对Newton 法进行修改 ①：已知根的重数r(Newton 下山法)②：，α为()f x 的重根，则α为()u x 的单根。

6）截弦法 单点：双点（快速）：7）迭代加速收敛方法(艾特金（Aitkem)加速)：不动点迭代函数()x ϕ在α的某个邻域内具有二阶导数，'()1,0L ϕα=≠平方收敛第二章线性代数方程组数值解法1）向量范数：的充要条件是0x=；12∞范数：p2）矩阵范数：的充要条件是0A=；F1∞范数：2，iλ为H A A 的特征值，3）Gauss消元法（上三角阵）列选主元消元法：在消元之前进行行变换，将该列最大元素换置对角线主元位置；（可用于求逆矩阵，详见杨娟ppt）4）三角分解法（此部分难以简单说明，具体见ppt）：①：Doolittle分解法：A=LU，L单位下三角阵，U上三角阵②：Crout分解法：A=LU，L下三角阵，U单位上三角阵③：追赶法：Crout分解法解三对角方程8）Jacobi 迭代：A L D U =++111()i i x I D A x D b +--=-+9）Gauss-Seidel 迭代：111()()i i xL D Ux L D b +--=-+++第三章 插值法与数值逼近 1）Lagrange 插值：000()()()()n n n ni i i L x y l x y l x y l x ==++=∑，01111)()()())()()()i i n i i i i i n x x x x x x x x x x x x -+-+------2）Newton 插值：差商表0x 0()f x 1x 1()f x 01[ ]f x x2x 2()f x 02[ ]f x x 012[ ]f x x x3x 3()f x03[ ]f x x013[ ]f x x x 0123[ ]f x x x x00100101010()()[ ]()[ ]()()[ ]()()n n n n f x f x f x x x x f x x x x x x x f x x x x x x x x -=+-++--+--(10]()()(n n n fx x x x x x n --=3）Hermite 插值（待定系数法）'210()[()()()()]nn j j j j j H x x f x x f x αβ+==+∑2()()()j j j x x x l x β=-45）离散函数的最佳平方逼近（曲线的最小二乘拟合）： 法方程(,)(,)njkjk j af ϕϕϕ==∑其中(,)()()(,)()()m j k i j i k i i mk i i k i i x x f f x x ϕϕρϕϕϕρϕ====∑∑第四章 数值积分1）代数精度的概念及应用：对r 次多项式的精确成立，以及代入法求解系数。

第2章线性方程组的解法--------学习小结一、本章学习体会本章主要学习的是线性方程组的解法。

而我们则主要学习了高斯消去法、直接三角分解法以及迭代法三种方法。

这三种方法的优缺点以及适用范围各有不同。

高斯消去法中，我们又学习了顺序高斯消去法以及列主元素高斯消去法。

顺序高斯消去法可以得到方程组的精确解，但要求系数矩阵的主对角线元素不为零，而且该方法的数值稳定性没有保证。

但列主元素高斯消去法因为方程顺序的调整，其有较好的数值稳定性。

直接三角分解法中，我们主要学习了Doolitte分解法与Crout分解法。

其思想主要是：令系数矩阵A=UL，其中L为下三角矩阵，U是上三角矩阵，为求AX=b 的解，则引进Ly=b,Ux=y 两个方程，以求X得解向量。

这种方法计算量较小，但是条件苛刻，且不具有数值稳定性。

迭代法（逐次逼近法）是从一个初始向量出发，按照一定的计算格式，构造一个向量的无穷序列，其极限才是所求问题的精确解，只经过有限次运算得不到精确解。

该方法要求迭代收敛，而且只经过有限次迭代，减少了运算次数，但是该方法无法得到方程组的精确解。

二、本章知识梳理针对解线性方程组，求解线性方程组的方法可分为两大类：直接法和迭代法，直接法（精确法）：指在没有舍入误差的情况下经过有限次运算就能得到精确解。

迭代法（逐次逼近法）：从一个初始向量出发，按照一定的计算格式，构造一个向量的无穷序列，其极限才是所求问题的精确解，只经过有限次运算得不到精确解。

我们以前用的是克莱姆法则，对于计算机来说，这种方法运算量比较大，因此我们学习了几种减少运算次数的方法，有高斯消去法、直接三角分解法，同时针对病态方程组，也提出了几种不同的解法。

Gauss消去法Gauss消去法由消元和回代两个过程组成，消元过程是指针对方程组的增广矩阵，做有限次初等行变化，使它系数矩阵变为上三角矩阵。

顺序Gauss消去法消元过程：对于K=1,2,3…,n-1执行(1)如果a aa(a)=0,则算法失效，停止计算；否则转（2）(2)对于a=a+1,a+2,…,a计算a aa=a aa(a)a aa(a)⁄a aa(a+1)=a aa(a)−a aa a aa(a) (a=a+1,a+2,…,a)a a(a+1)=a a(a)−a aa a a(a)回代过程：a a=a a(a)a aa(a)⁄a a=(a a(a)−∑a aa(a)a aaa=a+1)a aa(a)⁄ (a=a−1,a−2, (1)综上：顺序Gauss消去法的数值稳定性是没有保证的。

§4矩阵的三角分解矩阵的三角分解定理：设n nA R ×∈,如果A 的前n-1个顺序主子式det()0,1,2,,1i A i n ≠=− ，则A 可分解为一个单位下三角矩阵L 与一个上三角矩阵U 的乘积，且这种分解是唯一的。

证明：1.存在性：利用高斯消去法来构L 和U(1)(2)()1122det()0,1,2,,1i i ii A a a a i n =≠=−1L A U −=，A LU=2112100101n n m L m m ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦ ，(1)(1)(1)11121(2)(1)222()0nn n nn a a a a a U a ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦2．唯一性：分A 非奇异和奇异两种情况来证 （1）A 非奇异考虑到A 的前n-1个顺序主子式非零，得 det()0,1,2,,i A i n ≠=设1122A LUL U ==，12,L L 为单位下三角矩阵，12,U U 为上三角矩阵。

因A 非奇异，所以1U 可逆，从而112121L L U U −−=112121112121(,)L L E U U L L U U −−−−⇒==因为单位下三角阵为上三角阵2121,L L U U ⇒==（2）A 奇异因det()0,1,2,,1i A i n ≠=− ，det()0n A =()0,1,2,,1i ii a i n ⇒≠=− ，()0n nn a = 设1122A LUL U ==，12,L L 为单位下三角矩阵，12,U U 为上三角矩阵。

对它们进行矩阵分块，得(1)(1)(1)(1)(1)(1)111222(1)(1)1122001010n n n n n n n n L U a L U a m a m a −−−−−−−−⎛⎞⎛⎞⎛⎞⎛⎞=⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠⎝⎠⎝⎠⎝⎠其中(1)(1)12,n n L L −−为n-1阶单位下三角矩阵，(1)(1)12,n n U U −−为可逆的n-1阶上三角矩阵(1)(1)(1)(1)(1)(1)(1)(1)11112222(1)(1)(1)(1)(1)(1)(1)(1)1111122222n n n n n n n n n n n n n n n n L U L a L U L a m U m a a m U m a a −−−−−−−−−−−−−−−−⎛⎞⎛⎞⇒=⎜⎟⎜⎟++⎝⎠⎝⎠由(1)(1)(1)(1)1122n n n n L U L U −−−−=(1)(1)(1)(1)2121,n n n n L L U U −−−−⇒==由(1)(1)(1)(1)1122n n n n L a L a −−−−=(1)(1)21n n a a −−⇒= 由(1)(1)(1)(1)1122n n n n m U m U −−−−=(1)(1)21n n m m −−⇒=由(1)(1)(1)(1)222111n n n n m a a m a a −−−−+=+21a a ⇒= 故2121,L L U U == 证毕。

逆矩阵的计算公式逆矩阵计算公式:1. 基本定义：一个矩阵$A$的逆矩阵记作$A^{-1}$，若$A、B$都是$n$阶方阵，当且仅当满足$AB=BA=I_n$时，称$B$为$A$的逆矩阵，其中$I_n$是$n$阶单位方阵；2. 求解方法：（1）数域方式：矩阵$A$不在复数域或实数域中求解，可以建立$A$的伴随矩阵，用高斯-约旦消去法来求出逆矩阵$A^{-1}$。

（2）矩阵的分块：矩阵$A$分成子矩阵，其每部分的逆矩阵都是可以算出的，因此可以将大矩阵的逆分解成子矩阵逆的乘积，求解大矩阵的逆矩阵；（3）矩阵的隐式函数法：该法是使用函数的思想来求关系矩阵A的逆矩阵$A^{-1}$，在前面假定$AX=B$有解的前提下，进行一系列推导，解出$A^{-1}$；（4）矩阵朴素算法：如果矩阵$A$是一个$n$阶方阵，可以利用矩阵$A$的特殊形态对其求逆的同时消元，并利用行变换整理出$A$的逆矩阵；（5）范数方法：它是针对正定矩阵的，首先将正定矩阵按范数排列成一系列小矩阵，然后通过小矩阵式求出正定矩阵的逆矩阵；（6）LU分解：LU矩阵分解又称为Crout分解，是一种对非奇异方阵求逆矩阵的有效方法，它是利用下三角求逆和上三角求逆相结合可以求出矩阵的逆矩阵；（7）QR分解：它是基于矩阵的Q矩阵去求逆的，是利用正交分解的齐次系数特征值问题可以求出模糊Hessenberg矩阵的逆，进而迭代求出原矩阵的逆矩阵；（8）对称正定矩阵的求逆：如果需要求解的矩阵是一个对称正定矩阵，那么可以用Cholesky分解的方法计算矩阵的逆；（9）龙贝格（Löwner）方法：也叫做增量方法，可以用来求矩阵$A$的逆矩阵，计算公式是：$A^{-1}=A^{T}+A^{T}AA^{-1}$；（10）改进的共轭梯度法：可以用于求一般方阵的逆矩阵，也可以用于求一般非完全可逆矩阵的逆，可以求出较为精确的结果。