平方根法解线性方程组.ppt

1、在第三章，求解线性代数方程的直接方法，3.1高斯消去法，3.2矩阵的三角分解，3.3三对角方程的追赶法，3.4乔莱斯基分解和改进的乔莱斯基分解，3.5线性代数方程，自然科学和工程计算中的许多问题往往归结为求解线性方程。如三次样条插值函数问题、用最小二乘距离确定拟合曲线、微分方程的数值解等。最终将转化为求解线性方程。为了求解线性方程，方程的精确解可以通过有限步算术运算的直接方法获得(如果在计算过程中没有舍入误差)。一个已知的直接解决方案是格拉姆定律。迭代法构造一个迭代格式，并利用其极限过程逐步逼近线性方程的精确解。设线性方程组为，或写成矩阵形式，或简单地写成：3.1高斯消去法3.1.1对角方程组

2、的三角形方程组的解，如果为，则Xi=bi/AII，I=1，2，n。下三角方程，运算量：因为xi需要I倍的乘法和除法，所以上三角方程，运算量：因为xi需要n -i倍的乘法和1倍的除法，也就是N-I倍的乘法和除法，所以3.1.2高斯消去法和列主成分消去法消去法的基本思想是通过初等变换把一般的线性方程变换成等价的且容易求解的三角方程。高斯消元法高斯消元法是一种求解线性方程组的古老方法，它通过一系列初等变换(消元)将线性方程组(3.1)转化为等价的上三角方程组(3.5)，然后通过逆生成法得到原方程组的解。等价于(3.1)的上三角方程可以通过重复上述过程来获得，或者以矩阵形式A(n-1)x=b(n-1)

3、来书写，其中，一致认为(3.1)的解可以通过将(3.8)逐一代入高斯消去算法来获得。消去过程：乘法：除法：反推过程：计算量：高斯消去的限制：在高斯消去过程中，我们假设对角元素每次消去都是按照未知量的自然顺序进行的，顺序消去并不改变a的主子形式的值，所以高斯消去的充要条件是a的每阶主子形式都不为零。事实上，只要有0，方程组就有解。2.即使高斯消去法是可行的，如果它很小，在运算中用它作为分母将会导致其他元素数量的严重增加和舍入误差的扩散。在例3.1中，方程组的精确解是x1=1/3，x2=2/3。计算5个有效数字。解的消元顺序：交换方程的顺序：高斯消元后：列主成分消元法，称为高斯消元过程中的主成分。

4、如果选择模数最大的元素作为列中的主元素，并将其替换到主方程的位置，然后将其消除，则称为列主成分消除法。具体来说，第一步是选择第一列中绝对值最大的元素，交换第一行和第m行中的所有元素，然后进行消去操作。在第二步中，在每个k=1、2和n被消除之前，具有最大绝对值的元素被选择，并且k线和m线被交换，然后被消除。与高斯消去法相比，列主成分消去法只增加了选择列主成分和交换两个方程(即两行元素)的过程。因此，在高斯消去算法中加入主成分选择和交换过程就足够了。选择主成分的三角分解：3.2矩阵，用矩阵乘法解释高斯消去过程，取n=4。将(3.1)转换成等式(3.6)的过程相当于L1A=A(1)，L1b=b(1)

5、，也就是说，将(3.6)转换成等式(3.7)的过程相当于L2a (1)=A (2)，L2b (1)=B (1)。该过程导致用于求解线性等式的直接分解方法。一旦实现了A=LU，Ax=b就可以变成LUx=b.假设Ux=y，那么ly=b。Y由Ly=b求解(3.4)；x由Ux=y(即(3.5)求解。如果A的各阶主子公式不为零，可以实现如下：杜利特尔分解：如果L是单位下三角矩阵，U是上三角矩阵；库朗分解：如果l是下三角矩阵，u是单位上三角矩阵。3.2.1杜利特尔分解法，让A的每阶主子公式为非零，并将A分解为A=LU，即首先计算U的元素，然后计算L的元素：第一行U，第一列L，然后计算第二行U的元素；计算L

6、的第二列元素；计算U的第k个元素：计算L的第k个元素：Ax=b计算A=LUx=b分解的运算量：从(3.17)，计算U的第二行中的n-1个元素：(n-1)1(1项的乘积)第三行中的n-2个元素：(n-2)2(2项的乘积)第n行中的1个元素：让Ux=y，然后ly=b。Yi:由Ly=b(即(3.4)求解Doritos直接分解算法：输入：n，a，b，计算u的第k行元素和l的第k列元素；例3.2用多里托斯分解法解方程：让A=LU被解。与Dolly分解方法类似，对于k=1，2和n，如果实现了A=LU，Ax=b可以转化为lux=b。让Ux=y，那么ly=b。Yi :由Ly=b求解，xi:由UX=y求解。注意

7、：为了保证LU分解，要求A的所有阶主子公式都不为零，并且线性方程有解，只需要|A| 0。为了取消这一限制，采用了相似列主成分消除法。Courand列主成分直接分解算法输入：n，A，b计算l的第k列元素和u的第k行元素，例3.3利用Courand分解求解方程：求解A=LU，即求解下三角方程Ly=b，即求解(单位)上三角方程Ux=y，即3.3求解三对角方程的追赶法考虑三对角矩阵3360， 并且从库朗分解中的(3.22)和(3.23)的直接计算中很容易知道，L和U有以下形式：比较A=LU两边的元素，通过规定c1=0，我们可以得到ui和vi的计算公式； 考虑Ax=f，其中A是(5.26)形式的三对角矩

8、阵。假设Ux=y，那么l y=f。一致认为c1=0，vn=0，结合(3.27)和(3.28)，可以得到求解三对角系数矩阵线性方程的计算公式，而计算公式(3.29)和(3.30)称为追赶法。定理1如果A是一个对称矩阵，那么多莉分解A=LU可以表示。证明了定理1中的引理A是正定的，那么对角矩阵D中的元素不是负的。定理2如果A是一个对称正定矩阵，有一个下三角矩阵U，所以A=UUT。(乔莱斯基分解)证明：因为A是对称的，所以从定理1可以知道，其中L是单个下三角矩阵，D是对角矩阵。如果A是正定的，由引理可知D中的元素不是负的。记住，通过矩阵的乘法，我们可以得到在A=LDLT中分解L和D的元素：让我取i=

9、k，然后我们可以求解方程组Ax=b，并成为LDL TX=B。对称矩阵的LDLT分解算法：注：数据输入和求解三角方程的步骤被省略。例3.4用LDLT解出方程，所以Ax=b LDLTx=b解出方程如下：3.5根据计算机上的数学公式对线性代数方程编程是否能得到正确的结果？研究示例：求解线性方程组，其精确解为x1=x2=x3=1。如果方程组的系数四舍五入到两位有效数字，其解为x1=-6.222.x2=38.25 x3=-33.65.诺姆。在实轴上，任意两点A和B之间的距离可以表示为绝对值| ab |三维空间中向量长度的向量范数用来度量向量的大小，这是三维空间中向量长度概念的一个推广。向量范数的定义定义

10、了任意向量x=(x1，x2，xn) trn，它根据一定的规则对应于非负实数，并被记录为x，如果：(1)非负x=0；并且x=0(当且仅当x=0时);(2)齐次xRn，r，其中x=| a | x(3)三角不等式称X为向量X的范数，即Rn中常用的定义形式：让x=(x1，x2，xn)T，1-范数：x1=|x1| |x2| |xn|=2-范数：x2=-范数：x=max | x1 |，|x2|，|xn|。例如，x=(1，-1，0)，显然，x=0，但x0。示例2 x=(1，3，-5)是已知的，并且获得了1，2，-范数。x1=1 3 5=9；x2=(12 32 52)1/2；X=max1，3，|-5|=5。模

11、的等价和等价定理，把和定义为Rn上定义的两种模，如果C2的C1C1有非负常数，那么和就叫做Rn上的等价模。定理1有限维空间Rn中的所有范数都是等价的。易于验证：(1)X2x 1N 1/2x 2；(2)xx2 n1/2x；(3)xx1 nx .这三个规范是相互等价的，而且证明表明：(1)第一个公式是由x12 x22 xn2(|x1| |x2| | xn|) 2建立的。第二个公式由(| x1 | | x2 | | xn |)2n(| x1 | 2 | x2 | 2 | xn | 2)建立。向量范数的收敛性定义了如果向量序列x(k) Rn和向量xRn满足，那么x(k)收敛到x(根据范数)，并且注意到

12、定理2 Rn中向量序列x(k)收敛到x(根据范数)的充要条件是在例子3中找到向量序列的极限向量。解：矩阵范数，定义让ARnn是N阶的实矩阵，按照一定的规则对应一个非负实数，并记录为A。如果A，BRnn满足：(1)非负性：A=0；并且当且仅当A=0时，A=0；(2)同质性：A=| | A，C；(3)三角不等式：(4)甲乙双方；(5)兼容性：Ax，Ax，Rn；矩阵范数可以用向量范数来定义。设ARnn为n阶实矩阵，将矩阵范数定义为三个公共矩阵范数：(1)(列向量范数的最大值)(2)(行向量范数的最大值)(3)(其中1是ATA的最大特征值)、欧几里德范数或舒尔范数：定义为例4解：a1=max | 1 | 3，27；a=最大|1| 2，3 710；ATA的特征值为1=60.19，2=2.81 A2=11/2=60.191/2，AE=(1 4 9 49)1/2=631/2。定义了矩阵范数的收敛性。如果n阶矩阵序列A(k) Rnn和矩阵ARnn满足，那么A(k)收敛到A(根据范数)。注意，定理3中矩阵序列A(k)收敛到矩阵A的充要条件是(A(k)=(aij(k)nn，A=(aij)nn。2，n，矩矩阵的谱半径由2-范数定义，谱半径与矩阵范数的关系