当前位置:文档之家› 计算方法复习提纲

计算方法复习提纲

数值计算方法复习提纲第一章 数值计算中的误差分析 1.了解误差及其主要来源,误差估计;2.了解误差(绝对误差、相对误差)和有效数字的概念及其关系;3.掌握算法及其稳定性,设计算法遵循的原则。

1、 误差的来源 模型误差 观测误差 截断误差 舍入误差 2误差与有效数字绝对误差 E (x )=x-x *绝对误差限ε εε+≤≤-**x x x相对误差 ***/)(/)()(x x x x x x x E r -≈-=有效数字m n a a a x 10.....021*⨯±=若n m x x -⨯≤-1021*,称*x 有n 位有效数字。

有效数字与误差关系(1) m 一定时,有效数字n 越多,绝对误差限越小; (2)*x 有n 位有效数字,则相对误差限为)1(11021)(--⨯≤n r a x E 。

选择算法应遵循的原则1、 选用数值稳定的算法,控制误差传播; 例 ⎰=101dx e x eI xn neI nI I n n 11101-=-=- △!n x n=△x 02、 简化计算步骤,减少运算次数;3、 避免两个相近数相减,和接近零的数作分母; 避免第二章 线性方程组的数值解法1.了解Gauss 消元法、主元消元法基本思想及算法; 2.掌握矩阵的三角分解,并利用三角分解求解方程组; (Doolittle 分解;Crout 分解;Cholesky 分解;追赶法)3.掌握迭代法的基本思想,Jacobi 迭代法与Gauss-Seidel 迭代法;4.掌握向量与矩阵的范数及其性质,迭代法的收敛性及其判定 。

本章主要解决线性方程组求解问题,假设n 行n 列线性方程组有唯一解,如何得到其解?⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++nn nn n n n n n n b x a x a x a b x a x a x a b x a x a x a (22112222212111212111)两类方法,第一是直接解法,得到其精确解;第二是迭代解法,得到其近似解。

一、 Gauss 消去法 1、 顺序Gauss 消去法 记方程组为:⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++)1()1(2)1(21)1(1)1(2)1(22)1(221)1(21)1(1)1(12)1(121)1(11............nn nn n n n n n n b x a x a x a b x a x a x a b x a x a x a消元过程:经n-1步消元,化为上三角方程组⎪⎪⎩⎪⎪⎨⎧=+++=+=)()(2)(21)(1)2(22)2(221)2(21)1(11)1(11......n nn n nn n n n n b x a x a x a b x a x a b x a第k步 若0)(≠k kkan k j i n k b a a bba a a aak k k kkk ikk ik ik kj k kkk ik k ijk ij,....,1,1,...1)()()()()1()()()()()1(+=-=-=-=++回代过程:⎪⎩⎪⎨⎧--=-==∑+=ni j i ii j i ij i i in nnn n n n n i a x a b x a b x 1)()()()()()1,...2,1(/)(/2、Gauss —Jordan消去法避免回代,消元时上下同时消元 3、Gauss 列主元消去法例 :说明直接消元,出现错误⎩⎨⎧=+=+32200001.02121x x x x 由顺序Gauss 消去法,得0,112≈≈x x ;Gauss 列主元消去法原理:每步消元前,选列主元,交换方程。

算法:将方程组用增广矩阵[]()(1)ij n n A b a +=M 表示。

(1)消元过程: 对k=1,2,n-1, 选主元,找{,1,,}k i k k n ∈+⋅⋅⋅使得,max k i k ikk i na a ≤≤=如果,0ki ka =,则矩阵A 奇异,程序结束;否则执行3。

如果k i k ≠,则交换第k 行与第k i 行对应的元素位置,,,, 1.k kj i j a a j k n ↔=+g g g消元,对i=k+1, L,n,计算,ikik kka l a =对j=L+1, L,n+1,计算ij ij ik kj a a l a =-(2)回代过程: 1.若0,nn a =则矩阵A 奇异,程序结束;否则执行。

2,1;1,,2,1,n n n nna x i n a +==-L 对计算,11ni n ij j j i i iia a x x a +=+⎛⎫-∑ ⎪⎝⎭=举例说明。

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 分解算法:⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡nn n n n n nn n n n n u u u u u u l l l a a a a a a a a a ............1............11............ (222112)112121212222111211 由矩阵乘法:∑==nk kjik ij u l a 1得到:∑-=+=-=11;,...1,k r rjkr kj kj n k k j u l a un k k i u u l a l k r kkrk ir ik ik ,...1,/)(11+=-=∑-=算法特点:先计算U 的行,再计算L 的列,交替进行;存储时可用紧凑格式。

矩阵分解后,解两个三角方程组: LY= b ,UX=Y⎪⎩⎪⎨⎧=-==∑-=1111,...3,2i k kik i i ni yl b y b y∑+=-=-=ni k iik iki i n n i u x uy x 11,...1,/)(3、Crout 分解若L 为下三角矩阵,U 是单位上三角矩阵,则称Crout 分解; 算法特点:先计算L 的列,再计算U 的行,交替进行。

4、正定对称矩阵的平方根法(Cholesky 分解) (1) 正定对称矩阵性质与判定:定义:是n 阶对称矩阵,若对任意非零向量n R X ∈,有0>AX X T ,则称A 为正定对称矩阵;判定:A 为n 阶正定对称矩阵充要条件A 的各阶顺序主子式大于0。

(2) Cholesky 分解定理:设A 为n 阶正定对称矩阵,则存在唯一主对角线元素都是正数的下三角阵L ,使得T LL A =.Cholesky 分解算法:⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡nn n n nn n n nn n n n n l l l l l ll l l l l l l a a a a a a a a a .................................... (222112)1121222111212222111211 21112)(∑-=-=j k jkjj jj l a l∑-=-=11/)(j k jjjk ik ij ij l l l a lnj j i n j ,...2,1;,...2,1++==5、 追赶法三对角矩阵的特殊分解⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡----n n C n n nn n n u c u u c u l l l b a c b a c b a c b a c b 312113211133322211......1......111....2n i cl b u u a l b u i i i ii i i ,...3,2/1111=⎪⎩⎪⎨⎧-===--三对角方程组的追赶法:追的过程 LY=D⎩⎨⎧=-==-n i y l d y d y i i i i ,...3,2111赶的过程 UX=Y⎩⎨⎧--=-==+1,....,2,1/)(/1n n i u x c y x u y x ii i i i nn n§2 线性方程组的迭代解法一、 Jacobi 迭代公式 例:⎪⎩⎪⎨⎧-=+=+212121212121x x x x 其解为 1,121-==x x 方程变形得到迭代公式⎪⎩⎪⎨⎧--=+-=++21212121)(1)1(2)(2)1(1k k k k x x x x 给初值⎪⎪⎭⎫ ⎝⎛=00)0(X 计算,观察解的变化。

一般地,对线性方程组⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++nn nn n n n n n n b x a x a x a b x a x a x a b x a x a x a (2211222221211)1212111若0≠iia ,则可从第i 个方程中解出i x ,得到Jacobi 迭代公式:⎪⎪⎩⎪⎪⎨⎧--=---=---=-+++nn k n nn k n n k nii k n in k i i k ik n n k k a x a x a b x a x a x a b x a x a x a b x /)...(.../).......(.../)...()(1)(11)1()()(11)1(11)(1)(2121)1(1简记为:n i a x a b xiinij j k jij i k i,...,2,1/)(1)()1(=-=∑≠=+二、 Gauss--Seidel 迭代公式n i a x ax a b xiii j ni j k j ijk jij i k i,...,2,1/)(111)()1()1(=--=∑∑-=+=++三、 SOR 迭代公式四、 迭代公式的矩阵表示 DGX X k k +=+)()1(§3 迭代公式的收敛性一、 向量与矩阵的范数与性质 1、 向量范数 定义:向量n R X ∈,对应非负实数X,满足三条件:(1)非负性 0,0,0==≥X X X(2)齐次性Xk kX =(3)三角不等式 YX Y X +≤+称X为向量范数2、 常见向量范数 1范数nx x x X +++= (211)2范数222212...nx x x X+++=∞范数ix ni X≤≤=∞1max3、 矩阵范数 定义:方阵n n R A ⨯∈,对应非负实数A,满足三条件:(1)非负性 0,0,0==≥A A A(2)齐次性Ak kA =(3)三角不等式B A B A +≤+(4)绝对值不等式 BA AB ≤称A为矩阵范数;向量范数与矩阵范数相容性:XA AX ≤4、常见矩阵范数 1范数,列范数 :∑=≤≤=ni ijnj a A 111max∞范数,行范数 :∑=≤≤∞=nj ijni a A11max2范数,谱范数 : F 范数:∑∑===n i nj ijFaA112举例计算二、 迭代公式收敛性的判定 1、 向量的极限2、 矩阵的谱半径:i ini A λλρ≤≤=1max )(为特征值;3、收敛性的判定 收敛的充要条件: 迭代公式D GX X k k +=+)()1(收敛的充要条件为谱半径1)(<G ρ。

相关主题