计算方法教案

1、文档编码 : CX8Z3A1X6Z6 HD6Q3F6B1N10 ZO2O2R6Q9Y7第 1 章误差分析与数值运算 26第 4 章矩阵特点值与特点向量的运算 34 引言 2 引言 34 确定误差与相对误差,有效数字 幂法和反幂法 35 近似数的简洁算术运算 911 雅可比方法 36 QR 方法 *38数值运算中误差分析的一些原就 第 2 章非线性方程（组）的近似解法 13 本章小结 38 2.1 引言 13 第 5 章插值与拟合 39 根的隔离 14 引言 39 对分法 14 插值多项式的存在和唯独性 40 迭代法 15 拉格朗日插值多项式 40 弦截法 17 均差插值公式 42 弦截法 17

2、 差分等距结点插值公式 43 用牛顿法解方程组 18 爱尔米特插值公式 44 本章小结 19 分段低次插值 45 第 3 章线性方程组的解法 20 三次样条函数 45 48 引言 20 曲线拟合的最小二乘法 高斯消去法 21 本章小结 51 第 6 章数值积分和数值微分 52 矩阵的 LU 分解 25 对称矩阵的 LDL T 分解 26 引言 52 线性方程组解的牢靠性 26 牛顿一科特斯型积分公式 52 简洁迭代法 29 复合求积公式 54 本章小结 34 龙贝格求积公式 57 第 1 页,共 76 页高斯求积公式 58 欧拉法和改进的欧拉法 65 74 二重积分的数值积分法 61 龙格 -

3、库塔方法 66 数值微分 62 线性多步法 72 本章小结 63 算法的稳固性与收敛性 73 第 7 章常微分方程的数值解法 64 微分方程组和高阶微分方程解法 7.1 引言 64 本章小结 76 第 1 章 误差分析与数值运算 引言 1,课程任务和目的： 在第七届国际软件工程学术会议上, “运算方法”被列入应用方法学的争论领域,强调了运算方法的争论 应用与软件方法学的争论亲热结合；这就说明白运算方法与软件之间的联系以及在应用软件研制中的位置 与作用,运算方法是争论各种数学问题求解的数值运算方法；在运算机成为数值运算的主要工具的今日, 就要求争论适合于运算机使用的数值运算方法；运算方法就是争论

4、用运算机解决数学问题的数值方法及其 理论,它的内容包括函数的数值靠近,数值微分与数值积分,非线性方程值解,线性方程组数值解,常微 和偏微数值解等,即都是以数学问题为争论对象的；因此,运算方法是数学的一个分支,只是它不象纯数 学那样只争论数学本身的理论,是把理论与运算紧密结合,着重争论数学问题的数值方法及其理论,运算 方法是运算机应用和软件研制开发的重要组成部分,通过本课程的学习和上机实习,使同学把握利用运算 第 2 页,共 76 页机进行科学运算的基本理论和基本方法,并且学会将基本理论和基本方法应用于软件开发以及软件研制； 2,本课程基本要求 （ 1）把握方法的基本原理和思想； （ 2）把握方

5、法处理的技巧及与运算机的结合； （ 3）把握误差分析,收敛性及稳固性的基本理论； （ 4）学会进行牢靠的理论分析,对近似运算要确保精度要求,要进行误差分析； （ 5）通过例子,学习使用各种运算方法解决实际运算问题； （ 6）通过上机实践,能编写算法和实现算法； （ 7）把握数值运算中一些最基本,最常用的运算方法和算法； 3,本课程与各课程的关系： 由于本课内容包括了微积分,代数,常微分方程的数值方法,同学必需把握这几门课的基本内容才能学好 这一课程, 同时, 学习此课程仍必需具备运算机系统的初步学问, 把握一门常用的高级语言, 如： BASIC , PASCAL , C 语言等,并须具备确定的

6、编程才能； 4,本课程的特点： 第 3 页,共 76 页（ 1）面对运算机,要依据运算机特点供应实际可行的有效算法；即算法只能包括加,减,乘,除运算和 规律运算,是运算机能直接处理的； （ 2）有牢靠的理论分析,能任意靠近并达到精度要求,对近似算法要保证收敛性和数值稳固性,仍要对 误差进行分析,而且都是建立在相应数学理论基础上的； （ 3）有好的运算复杂性；时间复杂性好是指节约时间；空间复杂性好是指节约储备量；这也是建立算法 时要争论的问题,由于它关系到算法能否在运算机上完成； （ 4）要有数值试验；即任何一种算法除了从理论上要中意上述三点外,仍要通过数值试验证明是行之有 效的； 运算方法最基

7、本的立足点是容许误差,在误差容许的范畴内对某一数学问题进行近似运算,得到能中意要 求的近似结果； 现实世界中误差是普遍存在的,由于世界上没有确定精确的量具（确定精确的量具是没有刻度的） ,因此 人类通过量具采集的数据都是近似值,另一方面,我们的生产,试验工具都不是确定精确的,这就使得人 类在生产和科学试验中必需容许误差； 运算机的应用可以分为二个方面, 即数值运算和非数值运算； 利用运算机进行数值运算的过程如下图所示： 第 4 页,共 76 页实际问题 数学模型 运算方法 程序设计 上机求解 在上图中,运算方法的任务是：由建立的数学模型给出可编程并由运算机能完成的运算方法,然后编程和 上机求解

8、； 由于运算方法是编程后可由运算机求解的近似运算方法,如何确保近似解的精度显得尤为重要,必需 深化争论有关误差的基本概念和基本理论,为近似运算的精度分析打下基础； 1,误差的来源（种类） 误差的来源主要有以下四种 （ 1）模型误差：建立数学模型时的误差； 例如：在求重量的数学模型 G=m*g 中,重量 G 不是仅与质量和重力加速度有关,它仍与温度,测量地点 的海拔,地层结构等众多因素有关,为了使模型较为简洁和有用,接受抓住主要冲突的方法,去掉了大量 对重量影响不大的次要因素,建立了上述重量的近似模型,由此产生了模型误差； （ 2）观测误差：采集数据时的误差； 采集数据时,通常是依靠仪器和量具,

9、由于没有确定精确的仪器和量具,因此采集的数据有误差,此误差 称为观测误差； 第 5 页,共 76 页（ 3）舍入误差：由于运算机字长有限而产生的误差； 硬件再进展,运算机的字长总是有限的,在运算过程中,当数据的长度超过了运算机的字长时,运算机就 会进行四舍五入,由此产生的误差称为舍入误差； （ 4）截断误差：无限形式的有限化而产生的误差； 在运算中有时会运用无限形式的运算公式,例如台劳公式： f x f x 0 f 1 x 0 x x 0 f n x 0 x n x 0 1. n. 明显此公式无法进行运算,因此必需依据实际需要,从某一项起将后面的各项截断,即 f x f x 0 1 f x 0

10、 1. x x 0 f n x 0 x n. n x 0 由此产生的误差称为截断误差； 确定误差与相对误差,有效数字 为描述便利,第一商定 x* 是精确值 x 的近似值；引入误差的概念,其目的是为了衡量近似值 x* 的好坏； （ 1）确定误差： x* x 由于精确值 x 通常无法确定,因此确定误差无法运算,由此引入确定误差限的概念； 第 6 页,共 76 页确定误差限：确定误差的一个上界；即：如 | x* x | e,就称 e 为 x* 的确定误差限； 确定误差限的性质是： A. 不唯独这是由于 | x* x | 的上界是不唯独的； B. 可确定只要我们对 x* 的实际背景 有确定的明白,就不

11、难确定 | x* x |的上界；例如, x* 表示身高,就 | x* x |的上界可为 3 米；当 x* 是你求出 的,那么为了说明你的工作仔细,你确定会将 | x* x | 的上界估量得尽量小,因此在这种意义上确定误差 限可用来衡量 x* 的好坏； 由于确定误差限没有考虑问题的规模,因此有时它也不能衡量 x* 的好坏；例如： x 是地球与太阳的距离, y 是分子中二个原子间的距离,如 | x* x | 1 公里, | y* y | 1 厘米,就并不能说 y* 比 x* 精确；由此引入相 对误差和相对误差限的概念； （ 2）相对误差： x* x / x* 相对误差限：相对误差确定值的一个上界；

12、 3,有效数字 这里我们必需搞清晰什么是有效数字以及如何确定 （ 1）有效数字的定义 x* 有几位有效数字； 如 |x*-x|0k=1,2, n,其精确值为 xk0,k=1,2, n * x nxk *的确定误差限 Ex* k 1* E x nxk n* xk nxk * xk n* Exk k 1k 1 k 1 k 1 E x * n* E x k 1 第 9 页,共 76 页1和的确定误差等于各项确定误差之和； 2 和的确定误差限不超过各项确定误差限之和； 类似的可以得到：和的相对误差限介于各项相对误差限的最小者与最大者之间； 近似数的乘法 结论：乘积的相对误差限不超过各项相对误差限之和；

13、 近似数的除法 结论：商的相对误差限不超过被除数与除数相对误差限之和； 近似数的幂和根（见教材 p9） 近似数的对数（见教材 p9） 近似数的减法 结论：差的确定误差等于各项确定误差之和； 留意两个几乎相等的近似数相减会使结果的有效数字缺失,影响整个运算工作的精确性,应尽量防止； 1cosx 2 x 2sin 2ln x ln x ln x1 x2 第 10 页,共 76 页（当 |x|很小时, x 1与 x 2很接近时） 数值运算中误差分析的一些原就 为保证运算结果的高精度,在进行数值运算时应遵循下述几个原就； （ 1）在进行除法时,要防止除数的确定值 被除数的确定值； 为什么要“防止”？

14、如不“防止” ,就除出的结果很大,由于运算机字长有限,它装不下,因此会进行四舍五入,一个很大的 数进行四舍五入时舍去的部分也会很大,这会使舍入误差变大； 怎样“防止”？ 由于用户只关怀最终的运算结果,当中间运算过程中显现了除数的确定值 被除数的确定值时, 就应当换 一种运算方法,以防止这种情形的发生,以后我们将会针对详细的运算问题来争论“防止”的方法； （ 2）在进行减法时,要防止二个相近的数相减； 为什么要“防止”？ 如不“防止” ,就可能失去大量的有效数字, 例如：如 a=30001 和 b=30000 都有五位有效数字,由于 a-b=1,所以结果至多有 1 位有效数字； 怎么“防止”？

15、第 11 页,共 76 页“防止”的思路与第 1 个原就中“防止”的思路相同,须针对详细运算问题来争论； （ 3）要防止“大数吃小数” 什么是“大数吃小数”？我们用一个例子为说明； n运算 8756294874 ai ,其中 n=10 20 , 0 ai 10 6； i 1 此题是一个很大的数与很多很小的数相加,如接受将大数依次与 a1,a2, ,an 相加,由于运算机字长有限, 因此在与 ai 相加时会进行四舍五入将 ai 舍去, 这样,最终的结果仍是大数, 这就是大数将 a1,a2, ,an 吃掉了； 为什么要“防止”？ 尽管每个小数都很小,但它们很多,可能它们的和比大数仍大,而最终运算工

16、结果为大数,明显误差可能 很大； 怎样“防止”？ 有的同学提出先将小数相加,然后再与大数相加,这个思路是对的,但有一个漏洞,由于小数相加到确定 程度也会变成大数,它也开头吃小数了；可以实行分部相加的方法解决； 第 12 页,共 76 页第 2 章 非线性方程（组）的近似解法 引言 方程 fx=0 的解称为 方程的根 ；也叫做函数 fx 的 零点 ； 方程求根大致包括三个问题 （ 1）方程有没有根？假如有根,有几个根？（ 2）哪里有根？求有根的区间,区间内的任意一点作为根的 近似值；（ 3）根的精确化,已知一个根的近似值后设法逐步把根精确化,直到足够精确为止； 本课程主要争论问题（ 2）和（ 3

17、）； 根的隔离 求方程 fx=0 的解的近似值时,第一要确定如干个区间,使每个区间内只有的一个根,这个步骤称为 根的 隔离 ； 对一般的方程,根的隔离有两种方法 （ 1）试值法 ；求出 fx 在如干点上的函数值,观看函数值符号变化的情形,从而确定隔根区间； （ 2）作图 法 ；画出 y=fx 的草图,观看曲线 y=fx 与 x 轴交点的大致位置,从而确定隔根区间； 例 1.2.1 争论方程 fx=2x 32-4x +4x+2= 0 的根的位置； f1=inline2*x3-4*x2+4*x+2,fplotf1,-1,1, f2=inlinelogx-1/x, fplotf2,1,2 第 13

18、页,共 76 页例 将方程 xlogx= 1 的根进行隔离； 21.30对分法 设有方程 fx = 0在（ab）内有且仅有一个根 ,这时有 fa fb0 可用对分法求 的近似值, 方法如下 5（1） 预备：运算区间（ a b）两个端点的函数值 fa,0 fb （2）对分：取 c=a+b/2 为（ a b）的中点,运算 fc （ 3）判定：假如 fc=0 ,就 c 为 fx = 0 的根,否就检验： 0如 fcfa0 ,就方程的根位于 a c 内,用 c 代 替 -b5,如 fcfb0 ,就方程的根位于 c b 内,用 c 代替 a； 2（ 4）检验：如 |b-a|ep c=a+b/2; if

19、fc*fa0 a=c; else b=c; end a,b,absb-a,pause end 第 14 页,共 76 页方程的解 x= 迭代法 设有方程 fx = 0 在 a b 上有且仅有一个根 ,可用迭代法求 的近似值,方法如下1）将方程 fx = 0 写 （ 成迭代形式 x= x （ 2）在 a b 上任取一个初始值 x 0； （ 3）运算 x 1= x 0 （ 4）如 | x1 x0|e e 为精度要求 ,此时运算终止 =x 1,否就令 x 0=x 1转（ 3）； 定理 2.4.1收敛定理 设函数 x 在a b 上连续,在 a b内可导,且中意 1当 x a b 时 , x a b ；

20、2 当 x a b 时, | x| m1,m 为一个常数； 就以下结论成立： 1 在 a b 上 x 有且仅有一个根 ； 2 对任意 x0 a b, 由迭代公式 xn+1= xn, n=0,1,2, 产生的数列 |xn| a b, 且有 xn n ； 第 15 页,共 76 页n3 成立误差估量式 | xn | m| x1 x0 | | xn | m| xn xn 1 | 1 m 1 m争论： 1 此定理说明只要 |xn -xn-1|足够小,就可以保证 xn 充分接近方程的根 ；所以在实际运算时,用条 件 |xn -xn-1| e 把握迭代过程的终止； 2定理 指当对任意 x0 a b 作为初

21、始条件,迭代过程都收敛, 这种形式的收敛定理称为大范畴收敛定理,是一个充分条件；当此条件不成立时,往往可以取初始值 x 0 接近于方程的根 ,使迭代过程收敛； 见 P21 定理 2.4.2；3 从定理 2.4.1 中可以看出,收敛速度与 m 值 有很大关系, m 越小,收敛速度越快；当 m 接近于 1 时,收敛速度很慢；依据 | x| m1 ,所以接受迭 代法求解方程的根时, 应适当的构造 x 使| x| 在区间 a b 内尽量的小； 见下面的例子 例 用迭代法 解方程 x= 10 x-2 , x 0=1 分别接受迭代格式 x= 10 x-2 和 x=logx+2 ,观看两个运算过程的区分；

22、e=1e-3 迭代过程 : 0.3759 迭代 6 次 x= f=inlinelog10 x+2 x=1x=fx 例 2.4.2 用迭代法求方程 fx=x 3+2x-5= 0 的根, x =1 x n 135 2x n ；迭代过程 第 16 页,共 76 页迭代 9 次 x= 1.3281 2.5 牛顿迭代法 牛顿法是解方程 fx = 0 的重要方法,它也是一种迭代法；设有方程 f=inline5-2*x1/3 用x牛=1顿 xn+1=xn fx n/ f xn求 的近似值,详细运算步骤如下法 一个初始值 x0； x=fx （ （ 2）运算 x 1= x 0 fx 0/ f x0 fx = 0

23、 在 a b 上有且仅有一个根 ,可 1）求出 fx 的导数 f x,在 a b 上任取 （ 3）如 | x1 x0|e e 为精度要求 ,此时运算终止 =x 1,否就令 x 0=x 1转（ 2）； 3 2例 用牛顿法解方程 fx=x -2x -4x-7= 0 在 34 内的根 x 0=4 ； 迭代过程 : 迭代 4 次 x= 弦截法 f=inlinex3-2*x2-4*x-7 弦f截 d=法in也lin是e一 3*种x是2-解 4*方 x-4 fx = 0 的迭代法, 它的特点是不需要运算 fx 的导数 f x ,且收敛速度也相当快, 程 是工程运算中常用的算法之一；设有方程 x=4 x=x

24、-fx/fdx fx = 0 在 a b 上有且仅有一个根 ,可用弦截法求 的近似值, 方法如下 （ 1）求函数 fx 在区间 a b 的两个端点的函数值 fx 0 ,fx 1 ,其中 a= x0 ,b= x 1（ 2）运算 x2= x1 fx 1 x 1 x0/ fx 1 fx 0 （ 3）如 | x2 x1|1 称为超线性收敛, P=2 称为平方收敛,明显 P 越大,迭代过 程收敛的越快； 可以证明当 是方程 fx=0 的单根时, 牛顿法是平方收敛 当 是方 fx=0 的重根时, 的； 程 牛顿法仅为线性收敛； 对分法：收敛速度与公比为 1/2 的等比级数相同；收敛速度最慢,但简洁有效,不

25、存在发散问题； 弦截法：弦截法的收敛阶 ；收敛速度次之,不需要运算 fx 的导函数,有发散问题；牛顿法：牛顿 第 19 页,共 76 页法是平方收敛,收敛速度最快,但要运算 引言 fx 的导函数,有发散问题； 第 3 章 线性方程组的解法 在科学试验和工程设计中,常常用到解线性方程组的问题；本章争论用运算机求解线性方程组的两类主要 方法： 直接法 和 迭代法 ；解线性方程组的一般表达式 a11x1 a12 x2 a1n xn b1 a11 a12 a1n x1 b1 a21x1 a 22x2 a2n x n b2 a21 a 22 a2n x 2 b 2 依据矩阵的运算的性质有 an1x1 a

26、n2x2 ann x n bn an1 an2 ann x n b n a11 a12 a1n x1 b1 a21 a22 a 2n x 2 b 2 简记为 Ax=b 其中 A x ban1 an2 ann x n bn 方程组 Ax=b 有唯独解的充分必要条件是 detA 0；理论上,可以用克莱姆法就 xk=k/,（ k=1,2.n ）其中 =det A,是 A 中第 k 列换成向量所得到的矩阵的行列式； 运算量很大；这种方法效率低,在实际应用中很少使用； 运算需要的乘法次数为 n-1n+1., 当 n 较大时, 第 20 页,共 76 页解线性方程组的方法可以分为两类： 一类是 直接法 ,

27、其特点是只包含有限次的四就运算,在每次运算都无舍入误差的情形下,所得到的是方程 组的精确解；由于实际运算中总是有舍入误差,所以实际得到的也是近似解； 令一类是 迭代法 ,它第一挑选一组初始值,再运用同样的运算步骤,重复运算,得到近似解；由于这类方 法中显现了极限过程,必需争论迭代过程的收敛性； 本章主要介绍： 直接法中的高斯消去法和主元高斯消去法； 迭代法中的简洁迭代法和塞德尔单迭代法； 高斯消去法 次序高斯消去法 以 n=4 为例说明高斯消去法的运算过程,设有线性方程组 a 11x 1 a12 x 2 a13 x 3 a14 x 4 b 1 a11 x1 a12 x 2 a13 x 3 a1

28、4 x 4 b1 a 21x 1 a 22 x 2 a23 x 3 a 24x 4 b 2 1 a22 x 2 1 a22 x 3 a22 x 4 1 b2 a 31 x 1 a 32 x 2 a33 x 3 a34 x 4 b 3 1 a32 x 2 1 a33 x 3 a34 1 x 4 1 b3 a 41x 1 a 42 x 2 a43 x 3 a 44x 4 b 4 1 a x 2 1 a x 3 1 a x 4 b1 4第 21 页,共 76 页a11x 1 a12 x 2 a13 x 3 a14 x 4 b1 a11x 1 a12 x 2 a13 x 3 a14 x 4 b1 1

29、a 22 x 2 1 a22 x 3 1 a22 x 4 1 a 22 x 2 a22 x 3 1 a22 x 4 1 b 2 1 b2 2 a33 x 3 2 a34 x 4 2 b 3 a33 x 3 2 a34 x 4 2 b 3 2 a43 x 3 2 a44 x 4 2 b 4 3 a44 x 4 3 b4 经过 3 次消元步骤,得到以上形式；从最终一个方程中解出 运算过程见教材 P37算法 3.2,1 主元消去法 例 解线性方程组 1212x4,依次回代得到方程组的全部解； 解：按 4 位小数运算,得到 x1=0.6667,x2=0.0000, 精确解 x1=1/3, x2=2/3

30、,误差很大； 假如将方程组的次序对换,得到 1212按 4 位小数运算,得到 x1=0.3334, x2=0.6667, 精确解 x1=1/3, x2=2/3,误差很小； 在次序主元消去法中,假如遇到方程组 Ax=b 中 A 的主对角线元素为零时,运算过程不能进行；假如 A 的 主对角线元素的确定值很小,也会产生较大的舍人误差,使得最终得到的解与精确解有较大的误差； 工程中使用较多的是列主元高斯消去法,运算过程见教材 P42 算法 6x 1+3x 2+2x 3=6 例 用次序消去法解方程组 10 x1+5x 2+6x 3=0 8x 1+5x 2+3x 3=0 方程组的增广矩阵 A|b 6326

31、10 5608530消元 0 00方程组系数矩阵主对角线元素为零,消元过程无法进行 . 第 23 页,共 76 页例 用主元高斯消去法解例 6中的方程组；方程组的增广矩阵 A|b 63210 5608530选主元 10 56063268530消元 00000选主元 00000消元 00000回代得到方程组的解 第 24 页,共 76 页矩阵的 LU分解 定理 3.3.1 设矩阵 的各阶次序主子式不等于 Dk0 k=1,2, n,就 A 有唯独的 LU 分解, A=LU ,其中 L 为 单位下三角矩阵, U 为上三角矩阵； 对于线性方程组 Ax=b 假如已经得到了的 LU 分解,方程组的解可以通

32、过以下方法得到 LUx=b, 令 Ux=y,就有 Ly=b,所以,求解 Ax=b 如的问题等价于求解两的系数矩阵为三角方阵的方程组； y1 b1 nn 1,n 21yk bk k 1lkj y j k 2,3, j1xn yn / unn xk yk n ukj x j / ukk j k 1 k 求解方程组 Ax=b 的运算变得特别简洁； 8 1 6 x1 1例 解线性方程组 Ax=b 3 5 7 x2 2,PA=LU , LUx=Pb ,Ly=Pb,Ux=y4 1 2 x3 3A=magic3, b=1;2;3, L,U,P=luA, y=LP*b , x=Uy 第 25 页,共 76 页

33、对称矩阵的 LDL T 分解 设矩阵 的各阶次序主子式不等于 Dk0 k=1,2, n,就 A 有唯独的 LU 分解, A=LU ,其中 L 为单位下三角 矩阵, U 为主对角线元素不为 0 的上三角矩阵； u11 u12 u1n u11 0 0 1 u12 / u11 u1n / u11 0 u22 u2n 0 u 22 0 0 1 u2n / u22 U DV 0 0 0 0 0 00 0 unn 0 0 unn 0 0 1从而 A=LDV ,如为对称矩阵 A=A T,就有 A=A =LDV =V DL ,其中为 T T T T V T 为单位下三角矩阵, DL T 为主 对角元素不为 0

34、 的上三角矩阵,由 LU 分解的唯独性得到, L =V T ,于是 A=LDL T ； 定理 3.4.1 设对称矩阵 的各阶次序主子式不等于 Dk 0 k=1,2, n,就唯独确定一个单位下三角矩阵 L 和 主对角元素不为 0 的对角矩阵 D,使 A=LDL T ； 例 A=5 10 5 -5;10 24 -2 -6;5 -2 44 -11;-5 -6 -11 23, L,P=cholA, L*L 假如线性方程组 Ax=b 系数矩阵是对称正定的, A=L TL , LTL x =b,令 L x=y, LTy=b例 b=5 10-1 -19,y=Lb,x=Ly 线性方程组解的牢靠性 第 26 页

35、,共 76 页向量范数和误差向量 定义 设 | .|是定义在 R n 上的实值函数,假如对于 R n 中的任意向量 x,y 及任意非负实数 k,中意 1（非负性）对任意向量 x 都有 |x|0 且 |x|=0 的充分必要条件是 x=0； 2（正齐性）对任意实数 k 和任意向量 x 都有 |kx|=k|x|； 3（三角不等式）对任意向量 |x+y|x|+|y|； 称 | .|为向量范数； 定理 3.5.1 对 R n 上的任意向量 x=x 1,x2 xn ,记 Tx 1 x x 2 x n x 2 x 2x 2x n 2x max x 1 k n k | x |1, | x |2, |x |都是

36、向量范数； 定义 设 | .|是定义在 R nxn 上的实值函数,假如对于 R nxn 中的任意矩阵 A,B 及任意非负实数 k,中意 1（非负性）对任意矩阵 A 都有 |A|0 且 |A|=0 的充分必要条件是 A=0； 2（正齐性）对任意实数 k 和任意矩阵 A 都有 |kA|=k|A|； 3 （三角不等式）对任意矩阵 A,B 都有 |A+B|A|+|B| , |AB|A| |B| 称 | .|为矩阵范数； 定理 3.5.2 对 R nxn 上的任意矩阵 A 记 A 1max 1 j n naij A 2max A T A A max 1 i n na ij i 1 j 1 第 27 页,

37、共 76 页| A|1, | A |2, |A |都是矩阵范数； R nxn 中的任意矩阵 A,就 A max Ax 是一种矩阵范数,并 x 1 定理 3.5.3 对 R n 上给定一种向量范数,对于 且它与给定的向量范数相容； 6A=-5 -3 1;4 0 1;4 1 -2, x=2 -5 1 normx,1, normx,2, normx,inf 5312例 A 401x 5Ax 9运算各 normA,1, normA,2, normA,inf41211normA*x,1, normA*x,2, normA*x,inf 种范数； 定义 设 | .|是定义在 件R nxn 上的范数,对于 R

38、nxn 中的任意矩阵 A 称 cond A=| A | | A-1| 为矩阵 A 的条 数； 例 3.5.3A=1 1.0001;1 1 ,b=2;2 , b1=2.0001;2 ,Ab, Ab1 当一个线性方程组 Ax=b 的系数矩阵 A 的条件数很大时,称方程组是病态的,判定线性方程组 Ax=b 是否 为病态的方法是： 1, 当 |detA|很小或 A 的一些行或列近似相关时,方程组可能是病态的； 2, 使用列主元消去法,显现主元的确定值很小时,方程组可能是病态的； 3, 当 A 的元素在数量级上有很大差别,且无确定规律时,方程组可能是病态的； 第 28 页,共 76 页对于病态的方程组可

39、以实行下面的方法： 1, 接受高精度的算术运算,例如接受双精度数运算； 2, 当 A 的元素在数量级上差别很大时,接受行平稳或列平稳的方法可以降低 A 的条件数； A=1 1; 1 1e4 , b=2;1e4 , condA,inf, s=maxA , d=diag1./s ,condd*A,inf clear,n=4; %取 n=6,8,10 等进行比较 简洁迭代法 b=onesn,1 x=hilbnb x0=invhilbn*b 设 有 方 程 组 Ax=b , 变 为 迭 代 形 式 , x=Mx+f , 或 xk+1 =Mx k +f ,任取初始值 0 x程迭代得到 x0, x1, m

40、axabsx-x0 k+1 x2 x , k , x , 如极限 lim k xk x * 存在,就 condhilbn x* 就是原方程组的解； m 14 k x 1 f1 ratshilb4 % 字符串 以 n=4 为例 ratsinvhilb4 % 字符串 k 1 x 1 m11 m 12 m13 k 1 x 2 m 21 m 22 m 23 m 24 k x 2 f 2k 1 x 3 m 31 m 32 m 33 m 34 k x 3 f 3k 1 x 4 m 41 m 42 m 43 m 44 k x 4 f 4Mk x f第 29 页,共 76 页写成重量形式 定理 如存在某种范数

41、 k 1 x 1 m11x 1 k m 12x 2 k m13x 3 k m14 x 4 k f1 M的各个特点值 k 1 x 2 m 21x 1 k m22 x 2 k m 23 x 3 k m24 x 4 k f 2 k 1 x 3 k m 31x 1 k m 32 x 2 k m33 x 3 k m34 x 4 f 3 k 1 x 4 m 41x 1 k m42 x 2 k m 43 x 3 k m44 x 4 k f 4 |. |,使 |M|1,就简洁迭代法收敛； 定理 3.6.2 迭代公式 xk+1 =Mxk +f,对任意初始值 x 0和 f都收敛的充分必要条件是矩阵 的模都小于 1

42、； 在简洁迭代法的基础上作改进 xk+1 =M 1x k+1 + M 2x k +f ,以 n=4 为例 k x1 f 1 k+1 x k 1 x1 0000 k 1 x1 m11 m12 m13 m14 k 1 x 2 m21 000 k 1 x2 0m 22 m 23 m24 k x2 f 2 k 1 x 3 m31 m 32 00 k 1 x3 00m 33 m34 k x3 f 3 0m44 f 4 k 1 x 4 m41 m 42 m 21 0 k 1 x4 00 k x4 k+1 k M 1x M 2 x f 第 30 页,共 76 页雅可比迭代法与高斯 -塞德尔迭代法 雅可比迭代

43、法 设方程组 Ax=b,的系数矩阵主对角线元素不为零, A 可以分解为 A=D+L+U ,其中 D ,L ,U 分别取 A 的主 对角线,下三角和上三角部分的元素；由 D+L+U x=b, Dx=- L+U x+b, x=-D-1 -1 L+U x+D b,由此可以得到 迭代形式 雅可比迭代法的迭代矩阵 xk+1 =-D -1 L+U xk +D -1bk=0,1,2 3-67 M J=-D L+U ； -1 写成重量形式 k 1 x1 a12 x2 k a13 x3 k a1n xn k b1 / a11 3-68 a21x2 k a23 x3 k k 1 x2 a2n xn k b2 /

44、a22 an2 x2 k an 3 x3 k k 1 xn an, n 1 xn 1 bn / ann 3.7.2 高斯 -塞德尔迭代法 在运算 3-68 式时,用已经运算出的 xj 进行后续的运算,可以得到 第 31 页,共 76 页k 1 x1 a12 x2 k a13 x3 k a1n xn k b1 / a11 3-69 k 1 x2 a21 x2 k 1 a23 x3 k a2 n xn k b2 / a22 an 2 x2 k 1 an3 x3 k 1 k 1 xn an, n 1 xn 1 k 1 bn / ann 称式 3-69 为高斯 -塞德尔迭代法；式 3-69 的矩阵表达

45、形式为 k+1 -1 k+1 -1 k -1 x =-D Lx-D U x +D bk=0,1,2 k+1 -1 k -1 x =- D+L Ux +D+L bk=0,1,2 3-70 高斯 -塞德尔迭代法的迭代矩阵 M GS=- D+L U； -1 雅可比迭代法和高斯 - 塞德尔迭代法的收敛性 定理 雅可比迭代法和高斯 -塞德尔迭代法收敛的充分必要条件是它们的迭代矩阵的各个特点值的模都 小于 1； 定理 如存在某种范数 |. |,使 |MJ|1,就雅可比迭代法收敛；如存在某种范数 |. |,使 |MGS|1,就高斯 -塞德尔迭代法收敛； 第 32 页,共 76 页例 分别用雅可比迭代法和塞德

46、尔迭代法解方程组 10 x1 x2 2x3 72 -6 x1 10 x2 2x3 83 误差 e10 x1 x2 5 x3 42 雅可比迭代法迭代公式 xk+1 =-D -1 L+U x k +D -1 b高斯 -塞德尔迭代法迭代公式 x k+1 =- D+L Ux +D+L b-1 k -1 例 考察用雅可比迭代法和塞德尔迭代法解方程组的收敛性； A= 2 -1 1;1 1 1;1 1 -2 A= 10 -1 -2;-1 10 -2;-1 -1 5 A= 10-1 -2;-1D=1d0ia-2g;-d1ia-1g5A; b=72 83 42; 2 1 1 x1 b=71283 42; U=t

47、riuA,1; D=diagdiagA; 1 1 1 x2 D=d1iagdiagAL=;trilA,-1;U=triuA,1; 1 1 2 x3 U=tr1iuA,1; MJ=-invD*L+U; 雅可比迭代法迭代公式 L=trilA,-1; L=trilA,-1; MS=-invD+L*U; 高斯 -塞德尔迭代法迭代公式 M=-invD*L+U; b=invD*b; xk+1 =-D xk+1 =- D+L -1 L+U x k +D -1 Ux-1 bk +D+L-1b b=invD+L*b;abseigMS M=-invD+L*Ua;bseigMJx=b; x=b; 例 .f3or用k

48、雅 =1可:1比 0,x迭=M代*法x+解b,方 en程d组122x1 1误差 e10 -3 1110 x2 A= 1 -2 2;-1 1 -1;-2 -2 1 221x3 2雅可比迭代法迭代公式 xk+1 =-D -1 L+U xk +D -1 b本章小结 本章争论明白线性方程组的直接解法和迭代解法；直接解法比较适用与系数矩阵稠密（既零元素较少）的 中,小型线性方程组,但对系数矩阵是带状或近似带状的大型线性方程组也适用；直接解法中的 列主元高 斯消去法 具有精度较高和省时的优点,是运算机中常用的算法； 迭代解法中主要介绍了 雅可比迭代法, 高斯 -塞德尔迭代法 和 放松法 ；迭代法具有运算公

49、式简洁, 程序设计 简洁,占用运算机内存较少的优点；适用于解大型稀疏矩阵（既零元素较多）线性方程组；高斯 -塞德尔迭 代法是在雅可比迭代法的基础上改进得到,在很多情形下可以加快收敛速度,但它的收敛域与雅可比迭代 法不同,因此不能相互取代；放松法可以加速迭代过程的收敛速度,但要适当挑选放松因子（ 02）；在 挑选迭代法时,要特别留意检验方法的收敛性问题； 第 4 章 矩阵特点值与特点向量的运算 引言 求矩阵的特点值和特点向量, 是代数运算中的重要问题； 在自然科学和工程中的很多问题, 例如电磁振荡, 桥梁的振动,机械振动等都可以归结为求矩阵的特点值和特点向量问题； 矩阵 A 的特点值和特点向量是

50、指,假如数 和非零列向量 x 中意关系式 Ax = x,就数 称为 A 的特点值非 第 34 页,共 76 页零列向量 x 称为 A 的与特点值 对应的特点向量；运算 n 阶矩阵 A 的特点值,就是求特点方程 |AI |=0 的根 i i=1,2, ,n；齐次线性方程组 A iI x=0 的非零解 xi,是 i 对应的特点向量； 本章争论一些在运算机上运算矩阵的特点值和特点向量的较为稳固的数值算法； 幂法和反幂法 1,幂法： 运算 n 阶矩阵 A 的模最大的特点值（主特点值）及对应的特点向量； 任取 n 维列向量 x 0 ,用迭代公式 x k+1=A x k 运算得到 x0, x1,x2, 2

51、vn 设 x0 =a1v1+ a2v2+ +anvn ,由于 Avj= ivj 所以1 x 0 =Ax =a1 1v1+ a2 2v2+ +an 2 n vnx 1 =Ax =a1 2 1v1+ a2 22v2+ +an n一般地有 k+1 k k k k k k k x =Ax =a1 1 v1 + a2 2 v2+ +an n vn= 1 a 1 v1+ a2 2/ 1 v2+ +an n/ 1 vn 当 k 充分大时 x k+1 a1 1 k+1 v1 1x k 向量 xk+1 与 x k 向近似地只差一个倍数,这个倍数就是模最大的特点值 1； 1,反幂法： Ax= x,A Ax = A

52、 -1 -1 x, A x= -1 -1 x,即 A 的特点值的倒数 -1 是 A 的逆矩阵 A-1 的特点值；用幂 法求 A -1 的模最大的特点值,它的倒数就是 A 的模最小的特点值； 雅可比方法 对于 2 阶方阵 A a11 a 21 U cos sin T U U 1 0 x 0 x a21 a22 sin cos 0 1 T U A U 2 a cos 2 a sin a sin 2 1 a 22 2a sin 2 a cos2 1 2a22 a11 sin 2 a21 cos2 2 a22 cos a21 sin 2 2 a11 sin 令 1 a 22 2a sin 2 a co

53、s2 0 tan 2 2a21 U T A U 1002a11 a22 a11 a 21 a 31 对于 n 阶方阵（以 n=3 为例） A a 21 a 22 a32a31 a32 a 33 令 tan 2 2a21 作变换矩阵 U cos sin0就有 U T A U sincos00 x x a11 a22 0 01x x x 第 36 页,共 76 页令 tan 2 2a31 作变换矩阵 U cos 0sin x x 0010就有 UT A U x x x a11 a33 sin 0cos 0 x x 令 tan 2 2a32 作变换矩阵 U 100 x x x 0cos sin就有

54、UT A U x x 0a22 a33 2aij ,可以将 A 0sin cos x 0 x 一般地说,令 tan 2 中的元素的 aij 和 aji 变为 0；在实际运算中接受以下公式 aii a jj aij sin 21 121a jj a ii 2cos 2 1 sin sign 22第 37 页,共 76 页例 4.3.1 用雅可比求对称矩阵 A 210121 的特点值和特点向量； （见教材 P86） 012 QR 方法 *QR 方法是求一般矩阵 A 的全部特点值和特点向量的一种迭代方法； 其基本思路是利用矩阵 A 的 QR 分解, 其中, R 是一个上三角矩阵, Q 是正交矩阵；

55、通过迭代格式 Ak 1Qk Rk Rk Qk 将 A 化为相像的上三角矩阵 （或 Ak 分块上三角矩阵） ,从而求出 A 的全部特点值和特点向量； 例 4.4.1 用 QR 方法求矩阵 A 213的特点值； 123012特点向量 a= 2 1 3;1 2 3;0 1 2 ,q,r=qra ,a=r*q 特点值 本章小结 本章介绍了求矩阵的特点值和对应的特点向量的几种方法；幂法可以求出矩阵的主特点值和对应的特点向 第 38 页,共 76 页量,优点是算法简洁,但当 | 1/ 2| 1 时,收敛速度很慢；反幂法可以求出矩阵的模最小的特点值和对应 的特点向量； 雅可比方法是利用一系列正交相像变换（即

56、平面旋转变换）把实对称矩阵 出 实对称矩阵 全部特点值； A 化为对角阵（近似） ,从而求 QR 方法是用镜向反射阵将矩阵 A 作 QR 分解,是一种求矩阵的全部特点值的有效方法； 第 5 章 插值与拟合 引言 已知表格函数 y=f x xi x 0 x1 x2 xn-1 xn fx i y 0 y1 y2 yn-1 yn 构造一个公式 p x 近似地表示 f x ,解决这个问题的方法有两类：一类是 插值法 ,另一类是 拟合法 ,又 称为靠近法；已知函数 y=f x 在互异点 x 0 , x 1, x2, , xn-1, x n 上的函数值y0, y1 , y2, , yn-1, yn,构造一

57、个函数 px 使得 pxi= y i 这样的问题称为插值问题； y=f x 称为 被插值函数 ,x 0 xn 称为 插值区间 ,p x 称 第 39 页,共 76 页为 插值函数 , x 0 , x1, x2, , xn-1, xn 称为插值点 ,在插值区间内部用 p x 代替 f x 称为 内插 ,在插值区间 外部用 p x 代替 f x 称为 外推 ,Rx=fx-px 插值多项式的存在和唯独性 定理：给出 n+1 个插值点及函数值 称为插值函数 px 的误差 ； xi x 0 x1 x2 xn-1 xn fx i y 0 y1 y2 yn-1 yn 求一个 n 次多项式 pnx=a0+a1

58、x+a2 x + 2+ anx n中意插值条件 pn xi= y ii=0,1,2, ,n 的 n 次插值多项式 pn x 是唯独的； 拉格朗日插值多项式 1,给出 2 个插值点 x 1 ,y1 x p1 x x 3,y3x 0 x 1 y 0 x x 0 y1 x 0 , y 0, x 1 , y1可以得到一次多项式 x1 x 1 x 0 2,给出 3 个插值点 x 0 , y 0, x 1 , y1 , x 2 , y2可以得到二次多项式 p2 x x x 0 x,y10 x x 2 y 0 x x 0 x x 2 y1 x 2 x x 0 x x 1 y 2 x 0 x 1 x 0 x

59、2 x 1 x 0 x 1 x 2,y2 x 2 x 0 x 2 x 4,y4 x 1 第 40 页,共 76 页不难验证 p2x 中意插值条件 p2 x 0= y 0p2 x 1= y 1 p2 x2 = y 2 3,给出 n+1 个插值点 x 0 , y 0, x 1 , y 1, ,xn , y n可以得到一个 n 次多项式 其中 pn x L 0 xy 0 L 1 xy 1 x 1L n xy nL x x n x n x x x x 0 x x nx K nx K 例 按以下表格求 y-0.5 和 y0.5 的值； x | 1 2 3 y | 7 1423 解：插值多项式 L 2 x

60、 x x1 x x1 x 0 x2 y 0 x 2 x x 0 x x 2 y1 x x0 x x1 y 2 x 0 x1 x 0 x 1 x 2 x 2 x0 x 2x 1 x 2x 3 73 x 1x 3 14 3 x 1x 2 23 2 1 21 2 12 3 13 2 x 4 x 2L 2-0.5=0.2500 L 2例 按以下表格求 y2.5 , y4.5, y5.5 的值； x | 1 23 45y | 0215 3第 41 页,共 76 页解：插值多项式 L 4x= x 4 x 3 2 + 60.75 x - 32 L 42.5=0.9180 ,L 44.5=6.1323, L