《数值分析第三章(2012)》由会员分享，可在线阅读，更多相关《数值分析第三章(2012)（120页珍藏版）》请在金锄头文库上搜索。
1、第三章 线性方程组求解的数值方法,求解,线性方程组的基本概念,将一般方程组转化为线性方程组： 如：取log，将乘法转化为加法，得到线性方程组。,克莱姆（Cramer）法：一种解线性代数方程组的直接法,在实际中如何利用计算机这一强有力工具求解线性方程？,3.1 消元法计算机解线性方程组的一种直接法,思路：1）先将A化为上三角阵 (消元)2）再回代求解 。 (回代),高斯消元法,消元,记,其中,Step k：设 ，计算因子 且计算,共进行 ？ 步,n 1,回代,没有唯一解.,定理,若A的所有顺序主子式 均不为0，则高斯消元无需换行即可进行到底，得到唯一解。,注：事实上，只要 A 非奇异，即 A1
2、存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。,消去法是按照系数矩阵的主对角线上的元素（主元）进行消元。从而可能出现：（1）某个主元为零，导致消元过程无法进行。（2）当某个主元的绝对值很小时，计算结果误差很大。,问题?,例：单精度解方程组,用单精度(8位)高斯消元法计算：,8个,原因：小主元 导致计算失败。,（大数吃小数）,（大数吃小数）,（结果差异很大）,全主元消去法,每一步选绝对值最大的元素为主元素，保证 。,Step k: 选取, If ik k then 交换第 k 行与第 ik 行;If jk k then 交换第 k 列与第 jk 列;, 消元,注：列交换改
3、变了 xi 的顺序，须记录交换次序，解完后再换回来。,列主元消去法,省去换列的步骤，每次仅选一列中最大的元。,交换第 k 行与第 ik 行;,在第kn行，第kn列选择,在第一行是个小数，仍是小主元 导致计算失败,例：,注：列主元法没有全主元法稳定。,例：,取a21为主元，避免大吃小,用矩阵理论分析消元法：,矩阵三角分解法,L单位下三角矩阵,U上三角矩阵,直接计算 A 的 LU 分解：,直接比对等式两端矩阵元素,一般计算公式：,LU分解系数的计算顺序,按颜色顺序依次计算,给定矩阵A，如何计算其对应的L矩阵和U矩阵？,Matlab的符号计算,思考题：习题2，写出4阶三对角矩阵的LU分解公式,利用L
4、U分解求解线性方程组,思路：,两步算法：,例：用三角分解法求解线性方程,不是所有矩阵都可分解为A=LU ，例如：,LU分解：,Matlab中LU分解函数“lu()”。调用方式：“L,U,P = lu(A)”,思考：利用 MATLAB中的帮助文件“ help lu” ，查看lu函数的帮助文档，说明其中L, U, P 各是什么矩阵。 L, U, P, A如何构成等式。,置换矩阵,更一般形式：,由线性代数知，对称正定阵的几个重要性质：, A1 亦对称正定，且 aii 0, A 的顺序主子阵 Ak 亦对称正定, A 的特征值 i 0, A 的全部顺序主子式 det ( Ak ) 0, 3.2 Chol
5、esky 分解（平方根法）：对称正定矩阵的分解法,若A为n阶满秩方阵，则有ATA为对称正定矩阵,又 ATA为对称矩阵,由于A满秩，即方程 A x = 0 只有0解，所以任意非零向量有：,根据正定矩阵定义，则有ATA为对称正定矩阵,对称正定矩阵Cholesky分解：,证明： ,先将对称 正定阵 A 做 LU 分解：,即,Why is uii 0?,Since det(Ak) 0,则 仍是下三角阵,注： 对于对称正定阵 A ，从 可知对任意k i 有 。即 L 的元素不会增大，误差可控，不需选主元。,称为Cholesky 分解,单位上三角阵,LU分解和Cholesky矩阵分解的关系：,如何计算D？
6、 U矩阵的对角线元素，或 的对角线元素平方。,已知cholesky分解，求LU分解：,任意满秩方程组求解，可转化为对称正定方程组求解。,Matlab 软件给出了Cholesky分解函数,chol（）,是, 3.3 向量和矩阵的范数,为了研究线性方程组近似解的误差估计和迭代法的收敛性，引进向量（矩阵）的范数的概念。,衡量向量或矩阵 “大小”的概念,范数概念是长度和距离概念的推广,向量范数（Vector norm）,Rn空间的向量范数 | | 对任意 满足下列条件：,（正定性),对任意,(齐次性),（三角不等式),常用向量范数：,定义：,例：判断下面定义式是否是向量范数,（1）,（2）,向量范数应
7、用：判断向量的大小,最重要的用途之一：分析向量收敛性，定义向量的极限：,向量序列 收敛于向量 ,是指对每一个 1 i n 都有 。,可以理解为,可理解为对任何向量范数都成立。,定义：,收敛意义上的等价，即在不同范数下的收敛性是一致的,向量范数的等价性定理（79页定理3A.1）：,利用向量范数的等价性定理，很容易得到下列推论： 推论：向量序列在某范数下收敛，则在任意范数下收敛。, 矩阵范数（Matrix norm）,Rmn空间的矩阵范数 | | 对任意 满足：,（正定性),对任意,(齐次性),（三角不等式),(4) | AB | | A | | B | （相容 (当 m = n 时),定义：,意
8、味多个矩阵（向量）运算时，误差是可控的,Frobenius 范数与 向量2范数相容,矩阵 ATA 的最大 特征根,常用矩阵范数：,1. Frobenius 范数, 向量| |2的直接推广,对方阵 以及 有,2. 算子范数,由向量范数 | |p 导出的关于矩阵 A Rnn 的 p 范数:,则,我们只关心有相容性的范数，算子范数总是相容的。,即使 A中元素全为实数，其特征根和相应特征向量 仍可能是复数。将上述定义中绝对值换成复数模均成立。,否则，必存在某个向量范数 | |v 使得 对任意A 成立。,注：,Freebies范数不是算子范数,设AI（单位阵），其| |F为：,| |F不是算子范数,求矩
9、阵的算子范数,例：已知矩阵A，求算子1范数和算子范数。,矩阵是一种线性映射算子，称为矩阵算子。所以有些矩阵范数又叫做“算子范数”。,任意离散有限线性算子可表示为矩阵形式。,1)尺度算子：,LTI：线性时不变系统,为什么叫做“算子范数”？,线性时不变算子的矩阵表示,线性时不变算子的矩阵表示,2)差分算子,3)累加算子,4)时移算子,线性微分方程,线性时不变算子的矩阵表示,5)傅立叶变换,线性时变算子的矩阵表示,谱半径 （讨论特征根与范数的关系 ）,矩阵A的谱半径记为 (A) = ，其中i 为A 的特征根。,定义：,特征根中最大的模为谱半径,矩阵范数的性质,所以2-范数亦称为谱范数。,证明：,由算
10、子范数的相容性，得到,将任意一个特征根 所对应的特征向量 代入,证明：,A对称,若 是 A 的一个特征根，则2 必是 A2 的特征根。,若 （最大特征根），则02 必是 A2 的最大特征根。,计算2-范数的一种方法,后面分析病态问题时要用,非奇异阵,若矩阵 B 对某个算子范数满足 |B| 1，则必有,证明：, 若不然，则 有非零解，即存在非零向量 使得,根据算子范数定义：,例,，X=-3 5T，分别求A、X的“1-范数”和“无穷大范数”,Matlab: A=4,-3;2,1 X=-3 5 norm(A,1), norm(A,inf) norm(X,1), norm(X,inf),3.4 解线性
11、方程组的迭代法,迭代法（iterative method ）,迭代法是从初始猜测值开始，通过依次逼近获得问题解的方法。(Iterative method: attempts to solve a problem by finding successive approximations to the solution starting from an initial guess；（comes from wikipedia） ),应用很广： 线性方程组求解、非线性方程求解、非线性方程组求解、特征值求解、最优化方法、分形等，以及数字信号处理中的维纳滤波、卡尔曼滤波等等都要用到迭代法 典型方法： 数值
12、计算：Jacobi法、Gauss-Seidel法、Newton迭代法、最快下降法（Steepest Descent）,迭代法解一般(非线性)方程,迭代序列的基本公式：,(x)为：任意n维空间到n维空间的函数。当(x)为线性函数时，上式即为线性方程(组) 的迭代公式。,如何利用迭代法解方程？,迭代法基本原理：如果迭代序列x（k+1）= (x（k） )收敛，则其极限点x*为方程 (x)= x 的解。,x*称为函数 (x)的不动点（fixed point）,迭代函数的构造：对于一般的非线性方程f(x)=0,例1：用迭代法求解方程 2 x = 1,构造迭代函数：,或,即迭代函数为(x)= f(x)+x
13、 或 (x)= af(x)+x,迭代函数:,迭代函数的构造,迭代法的步骤： 1、写出迭代方程 2、迭代,clear all close all clcformat long% 迭代法求解2x=1 x0 = 0 % 迭代初值 N = 30 % 迭代次数% 方法1：f(x) = 1 - x x1(1) = x0; for iii = 2 : Nx1(iii) = 1 - x1(iii - 1); end figure; plot(x1, o-) title(f(x) = 1 - x),振荡序列,收敛序列,发散序列,收敛序列,迭代法的核心问题： 迭代函数收不收敛 收敛速度快不快,借助于计算机，用迭代
14、法对分形的研究更加简单化,例2：迭代法用于分形(fractal)研究,分形是一种粗糙的或分裂的几何形状，其每一部分都是整体的缩小比例的复制（自相似性）分形是具有自相似性的几何形状。,分形（Fractal）理论，是现代数学的一个新分支，但其本质却是一种新的世界观和方法论。,A fractal is “a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole,“ a pro
15、perty called self-similarity,NOVA纪录片： hunting the hidden dimension “寻找隐藏的维度” 430， 2630 ，3000,分形应用：计算机虚拟现实技术；天线设计；医学；,分形 fractal,科赫雪花（Koch snowflake）： 1、初始为正三角形； 2、将每条边等分三段； 3、以中段为底向外做等边三角形 4、移除被三等分的边的中段。 5、如此迭代。,分形艺术,曼德勃罗集（Mandelbrot）,3.4 解线性方程组的迭代法,思路：,优点：可人为控制精度特别适合于大型稀疏阵列，但存在收敛性问题,求解, 如何建立迭代格式？ 收敛速度？ 向量序列的收敛条件？ 误差估计？,
