数值计算方法课件

数值计算方法1.1数值计算方法的意义、内容与方法20世纪最伟大的科学技术发明---计算机计算机是对人脑的模拟，它强化了人的思维智能；没有软件的支持，超级计算机只是一堆废铁而已；软件的核心就是算法！算法的研究和应用正是本章的主题！现代科学研究的三大支柱理论研究科学实验科学计算研究算法建立数学模型选取计算方法编写上机程序计算得出结果科学计算解题过程21世纪信息社会的两个主要特征：“计算机无处不在”“数学无处不在”21世纪信息社会对科技人才的要求：--会“用数学”解决实际问题--会用计算机进行科学计算学习算法的重要性通过算法的学习建立信息技术与数学的整合.培养学生使用计算机技术学习数学的习惯与技能.学习算法的重要性培养师生使用计算机技术学习数学和讲授数学，现今变得非常紧迫和必要.由教师制作课件进行演示,向师生使用数学软件学习数学和研究数学转变.一、计算数学的产生和早期发展计算数学是数学的一个古老的分支，虽然数学不仅仅是计算，但推动数学产生和发展的最直接原因还是计算问题。

二、二十世纪计算数学的发展数值代数

最优化计算

数值逼近

计算几何

概率统计计算

蒙特卡罗方法

微分方程的数值解法

微分方程的反演问题

数值计算方法学什么？学习如何用计算机解决数学问题！微积分和线性代数中没有学过的解决问题的方法;介绍一些用不同的方法解决以前用传统的数学方法解决的问题,甚至是传统的数学方法所不能解决的问题。选择一些现实世界存在的例子，用解析的方法能够解出来，以便将数值方法和解析方法做一个对比。数值软件使用传统的计算方法解决实际问题,要求具有一定的数学修养具有相当的编程能力现在大多数的人解决数学问题使用数值计算软件MATLABSCILABMathematica一些无法直接求解的数学问题1

求解线性方程组AX=b，其中系数矩阵A是的方阵，设n=20；2

求超越方程的根3

不用计算器，求的近似值。x1491234

计算定积分5在7块并排、形状大小相同的试验田上施化肥对水稻产量影响的试验，得到如下表所示的一组数据（单位：kg）施化肥量x

15202530354045水稻产量Y330345365405445450455求施肥和产量的关系6

研究对象是连续的，我们只能了解到其有限个数据温度的变化，时间是连续的，温度是时间的函数，如何画出温度的曲线图？计算机用来进行计算.解决问题.算法解决问题的一系列有序的步骤程序提供给计算机来解决问题的一系列的有序指令.1.2算法的概念1.用日常语言描述；2.用数学语言加以叙述；3.借助形式语言（算法语言）给出精确的说明；4.用框图直观地显示算法的全貌。

描述算法可以有不同的方式：例1：求解一般的二元一次方程组的算法第一步：假定（如果则将（1），（2）互换），得到方程组可化为：第二步：如果，解方程（4）得到第三步：将（5）代入（3），整理得到第四步：输出结果如果，方程组无解或有无穷组解。令通过求解过程，可以总结出算法步骤如下：S2计算S3如果则输出原方程无解或有无穷多组解的信息;否则S1输入S4输出计算的结果输入D=0开始输出

x1,x2

结束

No输出无解信息YesD=a11a22-a12a21DababxDababx/)(/)(21111221222211-=-=2122211211,,,,,bbaaaa例2:写出一个求任意3个整数的最大值的算法第一步：将3个整数表示为a,b,c,先假定a为“最大值”;第二步：将b与“最大值”比较，如果b大于“最大值”，就假定b是“最大值”;第三步：将c与“最大值”比较，如果c大于“最大值”，就假定c是“最大值”;用数学语言写出例2的算法：S1max=a(max表示最大值）S2如果b>max则max=b;S3如果c>max则max=c;S4输出计算结果max如果例2变为写出一个求有限整数序列中的最大值的算法第一步：先假定序列中的第一个整数为“最大值”;第二步：将序列中的下一个整数与“最大值”比较，如果它大于此“最大值”，就假定“最大值”是这个整数;第三步：如果序列中还有其他整数，重复第二步；第四步：在序列中一直到没有可比的数为止，这时假定的“最大值”就是这个序列中的最大值S2对于

i=2到

n（对于第二个整数到第n

个整数）

如果ai>max;则max=ai;用数学语言描述这个算法不妨设有n个整数，记为S1max=a1；S3输出计算结果max误差的背景介绍1.3.1.来源与分类

从实际问题中抽象出数学模型

——模型误差1.3

数值计算中的误差例3:质量为m的物体，在重力作用下，自由下落，其下落距离s

与时间t的关系是：（1.1）其中g

为重力加速度。

通过测量得到模型中参数的值

——观测误差

求近似解——方法误差(截断误差）机器字长有限——舍入误差

用计算机、计算器和笔算，都只能用有限位小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：

=3.1415926… x=8.12345四舍五入后……在数值计算方法中，主要研究截断误差和舍入误差（包括初始数据的误差）对计算结果的影响！1.3.2绝对误差、相对误差和有效数字1．绝对误差与绝对误差限例4:若用以厘米为最小刻度的尺去量桌子的长，大约为1.45米，求1.45米的绝对误差。1.45米的绝对误差=？不知道！定义1：设x是准确值，x*是x的一个近似值，称

是近似值x的绝对误差,简称为误差。

（1.2）但实际问题往往可以估计出不超过某个正数

.定义2若已知

*>0，使（1.3）则称

*为绝对误差限，简称为误差限。就可以知道x范围为有时也表示为2．相对误差和相对误差限（1.4）定义3：设x是准确值，x*是近似值，称为近似值x的相对误差，记作

类似定义2，有定义4相对误差的上界，称为相对误差限，即（1.5）3．有效数字定义5：如果（1.6）则说x*近似表示x

准确到小数后第n位，并从这第n位起直到最左边的非零数字之间的一切数字都称为有效数字，并把有效数字的位数称为有效位数。由上述定义

有效数位为3位有效数位为5位有效数位为4位定义6：若将准确值x

的近似值x*表示成标准形式（1.7）而其误差限（1.8）则说近似值x*具有n

位有效数字。这里n

为正整数，m

为整数，每个均为0,1，…，9中的一个数字，。定理1.1：若

x*具有n位有效数字，则其相对误差满足（1.9）反之，若x*的相对误差满足（1.10）则近似值x*至少具有n位有效数字。误差的传播与积累例5：蝴蝶效应

——墨西哥的一只蝴蝶翅膀一拍，就引起了大西洋的风暴？！以上是一个病态问题MA1.4.数值计算中应该注意的一些原则

1．算法的稳定性例6：求

（n=0,1,2,…,8）的值。解：由于初值递推公式（1.11）注意此公式精确成立按(1.8)

式就可以逐步算出Whathappened?!不稳定的算法！由递推公式（1.8）可看出，In-1的误差扩大了5倍后传给In，因而初值I0的误差对以后各步计算结果的影响，随着n的增大愈来愈严重。这就造成I4的计算结果严重失真。这就是误差传播所引起的危害!

改变公式：将公式变为不妨设I9

I10，于是由可求得I9

0.017，按公式（1.12）可逐次求得（1.12）

I8

0.019I7

0.021

I6

0.024I8

0.028

I4

0.034I3

0.043

I2

0.058I1

0.088

I0

0.182

稳定的算法！

在我们今后的讨论中，误差将不可回避，算法的稳定性会是一个非常重要的话题。2．要避免两个相似数相减在数值计算中，两个相近的数作减法时有效数字会损失。（1.13）的值。当x=1000，y的准确值为0.01580

1、直接相减2、将（1.13）改写为则y=0.01581例7:求类似地

3.绝对值太小的数不宜作除数例8：如分母变为0.0011，也即分母只有0.0001的变化时4.避免大数吃小数例9：用单精度计算的根。精确解为

算法1：利用求根公式在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1的指数部分须变为1010，则：1=0.00000000011010，取单精度时就成为：109+1=0.100000001010+0.000000001010=0.100000001010算法2：先解出注：求和时从小到大相加，可使和的误差减小。例10：按从小到大、以及从大到小的顺序分别计算5.先化简再计算，减少步骤，避免误差积累。一般来说，计算机处理下列运算的速度为1+2+3+…+40+109再利用1.5

中国古代数学中的算法案例秦九韶算法—递推方法

计算机上使用的算法常采用递推化的形式，递推化的基本思想是把一个复杂的计算过程归结为简单过程的多次重复。这种重复在程序上表现为循环。递推化的优点是简化结构和节省计算量。多项式求值：给定的x求下列n次多项式的值。解：1.用一般算法，即直接求和法:2.

逐项求和法:乘法的次数为:加法次数为：n令则记可以看出前K+1项部分和uk等于前K项部分和uk-1再加上第K

+1项，因此有k=1,2,…,n

初值应取为

所用乘法的次数为2n，加法次数为n。

3.秦九韶方法:将多项式改写为令递推公式为：

k=1,2,…,n

计算量为：乘法n次，加法n次。例11：用秦九韶方法求多项式在x=-0.2的值。

解：

Ka5-KvK00.008330.00833v0=a510.041670.04v1=v0x+a420.166670.15867v2=v1x+a330.50.46827v3=v2x+a2410.90635v4=v3x+a1510.81873v5=v4x+a01.5

算法的优劣

计算量小

存贮量少

逻辑结构简单例：用行列式解法求解线性方程组:n阶方程组，要计算n+1个n

阶行列式的值，总共需要做n!(n+1)

次乘法运算。

n=20需要运算多少次？n=100?

数值稳定数值计算方法主要研究适合于在计算机上使用的计算方法以及与此相关的理论，包括方法的收敛性、稳定性及误差分析。还要根据计算机的特点研究时间最短、需要计算机内存最少的计算方法。数值计算方法的研究对象：数值计算方法的特色1.

离散：定量地处理连续问题2.逼近：迭代，最终收敛于解。1.6

复习几个常用公式1.6.1微分中值定理考察下述几何事实：曲线中间，有一点P，在那里，曲线的切线平行于割线。揭示这一几何事实所包含的数量关系设曲线的方程为：割线的斜率曲线在点P(

,f(

))处的切线斜率就是f’(

)，点P处的切线平行于割线，也就是二者斜率相等，于是得到一个公式定理1（Roll中值定理）设函数f(x)在[a,b]上连续，在（a,b）内可微，且f(a)=f(b)，则存在，使得f’(

)=0。定理2（Lagrange中值定理）设函数f(x)在[a,b]上连续，在（a,b）内可微，且，则存在，使得

2．泰勒（Taylor）公式用多项式在某一点附近近似地表达一个函数非线性方程求根2.1引言一般的高次代数方程或超越方程非线性方程!设非线性方程f(x)=0(2.1)其中f(x)是变量x

的非线性函数。若有x*使f(x*)=0，则称x*为方程（2.1）的根或函数f(x)的零点。定义2.1设x*是方程（2.1）的根，则f(x*)=0。若存在正整数m

，使(2.2)且则称x*为（2.1）式的m重根；当m=1时，x*为单根.定理2.1若f(x)是连续函数，且f(x)的m阶导数连续，则x*为（2.1）式m重根的充要条件是：

x*满足1．根的存在性。方程有没有根？如果有根，有几个根？定理1：设函数f(x)在区间[a,b]上连续，如果f(a)

f(b)<0，

则方程f(x)=0在[a,b]内至少有一实根x*。

2．这些根大致在哪里？如何把根隔离开来？3．根的精确化求方程（2.1）根的近似值包括以下三方面内容：abx*f(x)1．画出f(x)

的略图，从而看出曲线与x轴交点的位置。2．从左端点x=a出发，按某个预先选定的步长h一步一步地向右跨，每跨一步都检验每步起点x0和终点x0+h的函数值，若那么所求的根x*必在x0与x0+h之间，这里可取x0或x0+h作为根的初始近似。开始读入a,ha

x0f(x0)

y0x0+h

x0f(x0)

y0>0打印结束否是继续扫描

例1：考察方程x0123456f(x)的符号--++--+abx0x1ab或不能保证

x

的精度x*

2xx*§1二分法

执行步骤1．计算f(x)在有解区间[a,b]端点处的值，f(a)，f(b)。2．计算f(x)在区间中点处的值f(m)。3．判断若f(m)=0，则m即是根，否则检验：（1）若f(m)与f(a)异号，则知解位于区间[a,m]，

b1=m,a1=a;（2）若f(m)与f(a)同号，则知解位于区间[m,b]，

a1=m,b1=b。反复执行步骤2、3，便可得到一系列有根区间：

(a,b),(a1,b1),…,(ak,bk),…4、当时5、则即为根的近似①简单;②对f(x)

要求不高(只要连续即可)；③事先可以估计出迭代次数。①无法求复根及偶重根②收敛慢定义f(x)f(a)

f(b)>0f(a)

f(b)=0f(a)=0打印b,K打印a,K结束是是是否否否m=(a+b)/2|a-b|<

f(a)

f(m)>0打印m,Ka=mb=m结束K=K+1是是否否输入K=0例2：求方程kakbkxkf(xk)的符号011.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-§2不动点迭代法及其收敛性1．不动点迭代法f(x)=0x=g(x)等价变换若有x*满足，则称x*是的一个不动点，也是方程（2.1）的一个根。如果连续，可构造迭代序列（2.6）x1=0.4771x2=0.3939 …x6=0.3758x7=0.37582．迭代过程的收敛性例3：求方程的一个根迭代格式取x0=1xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1

x0p0x1p1

x0p0x1p1

x0p0x1p1

定理2：如果

(x)满足下列条件（1）当x

[a,b]时，

(x)

[a,b]（2）当任意x

[a,b]，存在0<L<1，使

则方程x=

(x)在[a,b]上有唯一的根x*,且对任意初值

x0

[a,b]时，迭代序列xk+1=

(xk)

(k=0,1,…)收敛于x*。(2.7)3．迭代法的结束条件例4：求方程在[0,0.5]内的根，精确到10-5。x1=

(0.25)=0.3385416x2=

(x1)=0.3462668x3=

(x2)=0.3471725x4=

(x3)=0.3472814x5=

(x4)=0.3472945x6=

(x5)=0.3472961x7=

(x6)=0.3472963

4．迭代过程的收敛速度

设由某方法确定的序列{xk}收敛于方程的根x*，如果存在正实数p，使得

（C为非零常数）定义：则称序列{xk}收敛于x*的收敛速度是p阶的，或称该方法具有p

阶敛速。当p=1时，称该方法为线性（一次）收敛；当p=2时，称方法为平方（二次）收敛；当1<p<2时，称方法为超线性收敛。

例5：二分法和不动点迭代法的误差和收敛速度在二分法中则线性收敛在不动点迭代法中线性收敛L越小，收敛速度越快例6：构造方程解：f(x)在（1,2）区间有唯一的实根的不动点迭代格式可以构造出以下的迭代函数：§3牛顿法一、牛顿法的迭代公式x*x0x1x2xyf(x)原理：将非线性方程线性化

——Taylor展开取x0

x*，将f(x)在x0

做一阶Taylor展开:，

在x0

和x

之间。将(x*

x0)2

看成高阶小量，则有：只要f

C1，每一步迭代都有f’(xk)0，而且，，则

x*就是f(x)的根。(2.8)二、牛顿法的收敛性定理3：设f(x)在[a,b]上满足下列条件： （1）f(a)

f(b)<0； （2）f’(x)

0； （3）f

(x)存在且不变号； （4）取x0

[a,b]，使得f

(x)

f(x0)>0则由（2.3）确定的牛顿迭代序列{xk}收敛于f(x)在[a,b]上的唯一根x*。注：Newton法的收敛性依赖于x0

的选取。x*x0

x0

x03．牛顿下山法牛顿下山法计算步骤可归纳如下：（1）选取初始近似值x0；（2）取下山因子

=1；（3）计算（4）计算f(xk+1)，并比较与的大小，分以下二种情况 1）若，则当时，取x*

xk+1，计算过程结束；当时，则把xk+1作为新的xk值，并重复回到（3）。2）若，则当

≤

且，取x*

xk，计算过程结束；否则若

≤

，而时，则把xk+1加上一个适当选定的小正数，即取xk+1+

作为新的xk值，并转向（3）重复计算；当

＞

；且，则将下山因子缩小一半，取

/2代入，并转向（3）重复计算。例5：求方程f(x)=x3–x–1=0的根k

xk010.611/251.14063211.36681311.32628411.32472牛顿下山法的计算结果：1、单点弦截法：牛顿法一步要计算f

和f’，相当于2个函数值。现用f

的值近似f’:x0x1切线

割线

切线斜率

割线斜率x22、双点弦截法：切线斜率

割线斜率需要2个初值x0

和x1。x0x1x2解线性方程组的直接法直接法经过有限步算术运算，可求得线性方程组精确解的方法（假设计算过程中没有舍入误差）。迭代法迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法.3.1引言1.线性方程组的解取决于系数常数项3.1.1

矩阵概念的引入对线性方程组的研究可转化为对这张表的研究.线性方程组的系数与常数项按原位置可排为二、矩阵的定义

由个数排成的行列的元数表称为维矩阵.简称矩阵.记作简记为元素是实数的矩阵称为实矩阵,元素是复数的矩阵称为复矩阵.例如是一个实矩阵,是一个复矩阵,是一个矩阵,是一个矩阵,是一个矩阵.只有一列元素的矩阵称为列矩阵(或列向量).全为零的方阵称为上三角矩阵。

称为对角矩阵(或对角阵）.（4）形如的方阵,全为零的方阵称为下三角矩阵。记作(5)数(纯)量矩阵（标量矩阵）称为单位矩阵（或单位阵）.有时也记作E.全为1为数量矩阵或标量阵。当时，记作（6）元素全为零的矩阵称为零矩阵，零矩阵记作或.注意不同阶数的零矩阵是不“相等”的.例如

2..两个矩阵为同维矩阵,并且对应元素相等,即则称矩阵相等,记作例如为同维矩阵.

同维矩阵与矩阵相等的概念

1.两个矩阵的行数相等,列数相等时,称为同维矩阵.例

设解１、定义一、矩阵的加法设有两个矩阵那末矩阵

与的和记作，规定为说明只有当两个矩阵是同维矩阵时，才能进行加法运算.例如2、矩阵加法的运算规律1、定义二、数与矩阵相乘2、数乘矩阵的运算规律矩阵相加与数乘矩阵合起来,统称为矩阵的线性运算.（设为矩阵，为数）注：三、矩阵与矩阵相乘商品名代理商１、定义并把此乘积记作设是一个矩阵，是一个矩阵，那么规定矩阵与矩阵的乘积是一个矩阵，其中例2设例3故解注意只有当第一个矩阵的列数等于第二个矩阵的行数时，两个矩阵才能相乘.例如不存在.而２、矩阵乘法的运算规律（其中为数）;

若A是阶矩阵，则为A的次幂，即并且注意矩阵一般不满足交换律，即：例4

设则但也有例外，比如设则有注意

矩阵乘法一般不满足消去律，亦即：矩阵的基本运算：

(1)矩阵加法(2)矩阵与标量的乘法(3)矩阵与矩阵乘法(4)转置矩阵(5)单位矩阵其中

k=1,2,…,n(6)非奇异矩阵设

如果则称B是A的逆矩阵，记为

,且如果存在，则称A为非奇异矩阵。如果均为非奇异矩阵，则（7）矩阵的行列式则A的行列式可按任一行（列）展开。即其中的代数余子式，为元素的余子式。行列式的性质：。A是非奇异矩阵。定理3.1设，则下述命题等价：（1）对任何，方程Ax=b有唯一解；（2）齐次方程组Ax=0只有唯一解x=0;（3）（4）存在（5）A的秩定理3.2设为对称正定矩阵，则（1）A为非奇异矩阵，亦是对称正定矩阵；（2）记Ak为A的顺序主子阵，则Ak（k=1,2,…,n）亦是对称正定矩阵，其中

k=1,2,…,n.（3）A的特征根（4）A的顺序主子式都大于零，即定理3.3设

为对称矩阵，如果或A的特征值则A为对称正定矩阵。AX=b（3.1）

3.2高斯消去法3.2.1三角形方程组的解法（3.2）（3.3）

3.2.2高斯消去法3.2.3主元素消去法消元公式回代公式列主元消去法计算步骤：1、输入矩阵阶数n，增广矩阵

A(n,n+1);2、对于(1)按列选主元：选取l

使

(2)如果，交换A(n,n+1)

的第k行与底l

行元素(3)

消元计算：3、回代计算3.2.4无回代过程的主元消去法算法：第一步：选主元，在第一列中选绝对值最大的元素，设第k行为主元行，将主元行换至第一行，将第一个方程中x1的系数变为1，并从其余n–1个方程中消去x1。第二步：在第二列后n–1个元素中选主元，将第二个方程中x2的系数变为1，并从其它n–1个方程中消去x2。第k步：在第k列后n–k个元素中选主元，换行，将第k个方程xk的系数变为1，从其它n-1个方程中消去变量xk，…………消元公式为：对k=1,2,…,

按上述步骤进行到第n步后，方程组变为：即为所求的解3.2.5

无回代消去法的应用（1）解线性方程组系设要解的线性方程组系为：AX=b1,AX=b2,…AX=bm上述方程组系可以写为AX=B=(b1,…,bm)因此

X=A-1B即为线性方程组系的解。

在计算机上只需要增加几组右端常数项的存贮单元，其结构和解一个方程组时一样。行系数右端（2）求逆矩阵设A=(aij)n

n是非奇矩阵，

A

0，且令由于

AA-1=AX=I因此，求A-1的问题相当于解下列线性方程组相当于（1）中m=n,

B=I的情形。

（3）求行列式的值用高斯消去法将

A

化成3.3解三对角方程组的追赶法

高斯消元法的矩阵形式:Step1:3.4

矩阵的三角分解及其在解方程组中的应用记L1=L1－1=记于是Stepn

1:Lk=其中记为L记

U=定理1：（矩阵的三角分解）设A为n

n实矩阵，如果解AX=b用高斯消去法能够完成（限制不进行行的交换，即），则矩阵A可分解为单位下三角矩阵L与上三角知阵U的乘积。

A=LU且这种分解是唯一的。定理2：约化主元素（,i=1,2,…,k）

充要条件是矩阵A的顺序主子式

杜立特分解法/*DoolittleFactorization*/：

——

LU

分解的紧凑格式反复计算,很浪费哦……通过比较法直接导出L和

U的计算公式。思路直接三角分解法解AX=b的计算公式对于r=2,3,…,n计算（2）计算U的第r行元素

（3）计算L的第r列元素

(r

n)(1)(4)(5)3.5

平方根法1．矩阵的LDR分解定理3：如果n阶矩阵A的所有顺序主子式均不等于零，则矩阵A存在唯一的分解式A=LDR其中L和R分别是n阶单位下三角阵和单位上三角阵，D是n阶对角元素的不为零的对角阵，上述分解也称为A的LDR分解。2．平方根法

如果A为对称正定矩阵，则存在一个实的非奇异下三角矩阵，使A=LLT

，且当限定的对角元素为正时，这种分解是唯一的。定理4：（对称正定矩阵的三角分解）将对称

正定阵

A

做LU

分解U=uij=u11uij/uii111u22unn记为

A对称即记D1/2=则仍是下三角阵定理

设矩阵A对称正定，则存在非奇异下三角阵使得。若限定L对角元为正，则分解唯一。注：对于对称正定阵A，从可知对任意k

i

有。即L

的元素不会增大，误差可控，不需选主元。用平方根法解线性代数方程组的算法（1）对矩阵A进行Cholesky分解，即A=LLT，由矩阵乘法：对于

i=1,2,…,n计算（2）求解下三角形方程组

（3）求解LTX=y3．改进平方根法

其中改进平方根法解对称正定方程组的算法

令LTX=y，先解下三角形方程组LDY=b得解上三角形方程组LTX=Y得3.6

向量和矩阵的范数

1．向量的范数定义1：设X

Rn，

X

表示定义在Rn上的一个实值函数，称之为X的范数，它具有下列性质：（3）三角不等式：即对任意两个向量X、Y

Rn，恒有

(1)非负性：即对一切X

Rn，X

0,

Ｘ

>0(2)齐次性：即对任何实数a

R，X

Rn，

设X=(x1,x2,…,xn)T，则有

（1）（2）（3）三个常用的范数：定理5：定义在Rn上的向量范数

是变量X分量的

一致连续函数。定理6：在Rn上定义的任一向量范数

都与范数

等价，

即存在正数

M

与m(M>m)

对一切X

Rn，不等式成立。推论：Rn上定义的任何两个范数都是等价的。

对常用范数，容易验证下列不等式：

定义2：设给定Rn中的向量序列{}，即其中若对任何i(i=1,2,…,n)都有则向量

称为向量序列{}的极限，或者说向量序列{}依坐标收敛于向量，记为定理7：向量序列{Xk}依坐标收敛于X*的充要条件是向量序列依范数收敛与依坐标收敛是等价的。2．矩阵的范数定义3：设A为n

阶方阵，Rn中已定义了向量范数，

则称

为矩阵A的范数或模，

记为。矩阵范数的基本性质：

（1）当A=0时，＝0，当A

0时，>0（2）对任意实数和任意A，有（3）对任意两个n阶矩阵A、B有（4）对任意向量X

Rn，和任意矩阵A，有（5）对任意两个n阶矩阵A、B，有定理8：设n

阶方阵A=(aij)n

n，则（Ⅰ）与相容的矩阵范数是（Ⅱ）与相容的矩阵范数是其中

1为矩阵ATA的最大特征值。（Ⅲ）与相容的矩阵范数是3．A

的范数与A的特征值之间的关系定理9：矩阵A

的任一特征值的绝对值不超过A的范数。定义4：矩阵A的诸特征值的最大绝对值称为A的谱半径，记为：求解时，A

和的误差对解有何影响？

设A

精确，有误差，得到的解为，即绝对误差放大因子又相对误差放大因子§6

线性方程组的性态和解的误差分析

设精确，A有误差，得到的解为，即

Waitaminute…

Whosaidthat(I+A

1A)isinvertible?(只要

A充分小，使得

是关键的误差放大因子，称为A的条件数，记为cond(A),越则A越病态，难得准确解。大定义5：设A

为n阶非奇矩阵，称数为矩阵A的条件数，条件数的性质：

ⅰ）cond(A)≥1ⅱ）cond(kA)=cond(A)k为非零常数ⅲ）若，则记为cond(A)。例：Hilbert阵cond(H2)

=27cond(H3)

748cond(H6)

=2.9106cond(Hn)

asn

注：一般判断矩阵是否病态，并不计算A1，而由经验得出。

行列式很大或很小（如某些行、列近似相关）；

元素间相差大数量级，且无规则；

主元消去过程中出现小主元；

特征值相差大数量级。

近似解的误差估计及改善：设的近似解为，则一般有cond(A)误差上限

改善方法：Step1:近似解Step2:Step3:Step4:若可被精确解出，则有就是精确解了。经验表明：若A不是非常病态（例如：），则如此迭代可达到机器精度；但若A病态，则此算法也不能改进。解线性方程组的迭代法（4.1）

4.1

雅克比法、赛得尔法、超松驰法4.1.1．雅克比（Jacobi）迭代法设有n阶方程组若系数矩阵非奇异，且

(i=1,2,…,n)，将方程组（4.1）改写成然后写成迭代格式（4.2）（4.2）式也可以简单地写为（4.3）写成矩阵形式：A=LUDBJacobi迭代阵(4.4)…………只存一组向量即可。写成矩阵形式：Gauss-Seidel

迭代阵4.1.2高斯――赛得尔(Gauss-Seidel)迭代法(4.5)(4.6)4.1.3

超松驰法迭代加速（4.7）是松驰因子

4.2

迭代法的收敛条件定理4.1：对任意初始向量X(0)及常向量F，迭代格式(4.8)(4.8)定理4.2：若迭代矩阵Ｂ的某种范数

则（4.8）收敛的充分必要条件是迭代矩阵B的谱半径

(B)<1。确定的迭代法对任意初值X(0)均收敛于方程组X=BX+F的唯一解x*。

定义4.1：如果矩阵的每一行中，不在主对角线上的所有

元素绝对值之和小于主对角线上元素的绝对值，

即则称矩阵A按行严格对角占优，类似地，也有按列严格对角占优。定理4.3：若线性方程组AX=b的系数矩阵A按行严格对角

占优，则雅克比迭代法和高斯――赛得尔迭代法

对任意给定初值均收敛。4.3迭代法的误差估计(1)(2)定理4.4：设X*是方程组AX=b的同解方程X=BX+F

的准确解，若迭代公式中迭代矩阵B的某种范数，则有

矩阵特征问题的求解5.1

引言

定义5.1

设矩阵A,B

Rn

n，若有可逆阵P，使

则称A与B相似。定理5.1

若矩阵A,B

Rn

n且相似，则 （1）A与B的特征值完全相同； （2）若x是B的特征向量，则Px便为A的特征向量。定理5.2：设A

Rn

n具有完全的特征向量系，即存在n个线性无关其中

i为A的特征值，P的各列为相应于

i的特征向量。

的特征向量构成Rn的一组基底，则经相似变换可化A为对角阵，即有可逆阵P，使定理5.3

：A

Rn

n，

1,…,

n为A的特征值，则（2）A的行列式值等于全体特征值之积，即（1）A的迹数等于特征值之和，即定理5.4设A

Rn

n为对称矩阵，其特征值

1≥

2≥…≥

n，则

（1）对任意A

Rn，x≠0，（2）（3）定理5.5（Gerschgorin圆盘定理）设A

Rn

n，则表示以aii为中心，以

半径为的复平面上的n个圆盘。

（2）如果矩阵A的m个圆盘组成的并集S（连通的）与其余（1）A的每一个特征值必属于下述某个圆盘之中，n–m个圆盘不连接，则S内恰包含m个A的特征值。

5.2

乘幂法与反幂法5.2.1乘幂法定理5.6设A

Rn

n有完全特征向量系，若

1,

2,…,

n为A的n个特征值且满足

对任取初始向量x(0)

Rn，对乘幂公式确定的迭代序列{xk}，有下述结论：

（1）当

时，对i=1,2,…,n收敛速度取决于

的程度，r<<1收敛快，r

1收敛慢，且x(k)（当k充分大时）为相应于

1的特征向量的近似值。（2）当

时a）若

1=

2，则主特征值

1及相应特征向量的求法同（1）；收敛速度取决于

的程度。向量、c）若，则连续迭代两次，计算出x(k+1)，x(k+2)，分别为主特征值

1、

2相应的特征向量的近似值。然后对j=1,2,…,n解方程b）若

1=-

2，对i=1,2,…,n求出、后，由公式解出主特征值

1、

2。此时收敛速度取决于

的程度。向量、分别为相应于

1，

2的特征向量的近似值。规范化乘幂法令max(x)表示向量x分量中绝对值最大者。即如果有某i0，使则max(x)=xi对任取初始向量x(0)，记则一般地，若已知x(k)，称公式定理5.7设A

Rn

n具有完全特征向量系，

1,

2,…,

n为A则对任初始向量x(0)，由规范化的乘幂法公式确定的向量序列(1)（2）y(k)为相应于主特征值

1的特征向量近似值的n个特征值，且满足y(k)，x(k)满足5.2.2

原点位移法希望|

2/

1|

越小越好。不妨设

1>

2

…

n

，且|

2|

>|

n|。取

0（常数），用矩阵B=A-

0I来代替A进行乘幂迭代。

(i=1,2,…,n)设

i(i=1,2,…,n)为矩阵B的特征值，则B与A特征值之间应有关系式：关于矩阵B的乘幂公式为为加快收敛速度，适当选择参数

0，使达到最小值。

当

i(i=1,2,…,n)为实数，且

1>

2≥…≥

n时，取则为

(

0)的极小值点。这时5.2.3

反幂法若

A有|

1|

|

2|…>|

n|，则A1有11111lll…>-nnA1的主特征根A的绝对值最小的特征根如何计算解线性方程组对应同样一组特征向量。设A

Rn

n可逆，则无零特征值，由有

规范化反幂法公式为如果考虑到利用原点移位加速的反幂法，则记B=A-

0I，对任取初始向量x(0)

Rn，

5.3

子空间迭代法斯密特（Schmidt）正交化过程：

设

1，

2，

3为R3上的三个线性无关的向量，令，则

1为单位长度的向量，再令可以验证（

1,

2）=0，即

1与

2正交。若令则即与

1,

2正交，将其单位化为于是向量组

1,

2,

3构成R3上一组标准正交基，且其中Q=[

1,

2,

3]为正交矩阵，R是上三角阵。对n维向量空间，设

1,…,

n为Rn上n个线性无关的向量，类似有…………即Q为正交阵，R为上三角阵将n个线性无关向量变换为n个两两正交向量的方法称为

斯密特正交化方法。斯密特正交化过程将可逆阵A分解为正交阵与上三角阵的乘积。5.4对称矩阵的雅克比

(Jacobi)旋转法1．预备知识1）若B是上（或下）三角阵或对角阵，则B的主对角元素即是B的特征值。2）若矩阵P满足PTP=I，则称P为正交矩阵。显然PT=P-1，且P1,P2,…,是正交阵时，其乘积P=P1P2…Pk仍为正交矩阵。3）称矩阵为旋转矩阵

2．雅克比方法设矩阵A

Rn

n是对称矩阵，记A0=A，对A作一系列旋转相似变换其中Ak(k=1,2,…)仍是对称矩阵，Pk的形式Pk是一个正交阵，我们称它是（i,j）平面上的旋转矩阵

PkAk-1Pk只改变A的第i行、j行、i列、j列的元素；Ak和Ak-1的元素仅在第P行（列）和第q行（列）不同，它们之间有如下的关系：我们选取Pk，使得，因此需使

满足将

限制在下列范围内如果

直接从三角函数关系式计算sin

和cos

，记则当时，有下面三角恒等式：于是

采用下面公式计算sin

特征向量的计算P0=I记则Pk

的元素为：算法：1．从A(k-1)中找出绝对值最大元素2．若，则为对角阵，停若（1）令

（2）

当

y=0时，

（3）

（4）

（5）计算特征向量P0=I

n阶矩阵A非奇的等价性：1.A非奇；2.Ax=0当且仅当x=0；3.A可以经过行变换到In

；4.对每一个非零的向量b，Ax=b有唯一解；5.6.秩A=n；7.A的n个行向量线性无关；8.A的n个列向量线性无关；9.A的特征值非零。函数插值6.1 代数插值设已知某个函数关系y=f(x)在某些离散点上的函数值：

插值问题：

根据这些已知数据来构造函数y=f(x)的一种简单的近似表达式以便于计算点的函数值，或计算函数的一阶、二阶导数值。(6.1)选取多项式Pn(x)，使得（6.2）

作为f(x)的近似。

满足关系（6.2）的函数Pn(x)为f(x)的一个插值函数，x0,x1,…,xn

为插值节点，关系（6.2）为插值原则。这种用代数多项式作为工具来研究插值的方法叫做代数插值设

x0<x1<…<xn记a=x0,b=xn，则[a,b]

为插值区间。插值多项式的存在唯一性：设所要构造的插值多项式为：由插值条件得到如下线性代数方程组：此方程组的系数行列式为范得蒙行列式！当

时，

D

0，因此，Pn(x)由a0,a1,…,an唯一确定。定理(唯一性)满足的n

阶插值多项式是唯一存在的。6.2拉格朗日（Lagrange)插值1．线性插值

x0x1(x0,y0)(x1

,y1)P1(x)f(x)可见P1(x)是过(x0,y0

)和(x1,y1

)两点的直线。x0x1x2p2(x)

f(x)f(x)2．抛物插值因过三点的二次曲线为抛物线，故称为抛物插值。

要求：无重合节点，即3．拉格朗日插值公式设连续函数y=f（x）在[a,b]上对给定n+1个不同结点：x0,x1,…,xn分别取函数值y0,y1,…,yn其中

yi=f(xi)i=0,1,2,…,n试构造一个次数不超过n的插值多项式使之满足条件

i=0,1,2,…,n求n次多项式lk(x)k=0,1,…,n则

i=0,1,2,…,n即Pn(x)满足插值条件（6.2）

根据lk(x)的表达式，xk以外所有的结点都是lk(x)的根，又由lk(xk)=1，得：

因此令从而得n阶拉格朗日（Lagrange）插值公式：4插值余项在[a,b]内存在,考察截断误差设节点，且f

满足条件,

存在使得。且推广：若使得使得罗尔定理:若在［］连续，在充分光滑，注：

通常不能确定

x

,而是估计,

x(a,b)

将作为误差估计上限。

当

f(x)为任一个次数

n

的多项式时，,可知，即插值多项式对于次数

n的多项式是精确的。6.3牛顿插值Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。以抛物插值为例介绍牛顿插值：设：

i=0,1,2也可以将P2(x)写成：令x=x1，由（6.2），有令x=x0，由插值条件（6.2），有最后，由 得1．差商的定义定义1：设有函数f(x)以及自变量的一系列互不相等的x0,x1,…,xn

（即在i

j时，xi

xj）的值

f(xi)

,

称为f(x)在点xi,xi处的一阶差商，并记作f[xi,xj]，

又称为f(x)在点xi,xj,xk处的二阶差商

称

为f(x)在点x0,x1,…,xn处的n阶差商。f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]

xn+1f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]差商可列表计算：xi

yi

一阶差商

二阶差商

n阶差商

……由差商定义可知：高阶差商是两个低一阶差商的差商。x0x1x2xn-1xn2牛顿插值公式12…………n

1(x

x0),2……(x

x0)…(x

xn1)

n

1Nn(x)Rn(x)ai=

f[x0,…,xi]牛顿插值公式的优点是：当增加一个节点时，只要再增加一项就行了，即有递推式:由插值的唯一性可知Nn(x)

Ln(x)，故其余项也相同，即差商与导数的关系公式

6.4差分及其性质，等距节点插值公式1．微商的离散化引入符号向前差分向后差分

中心差分

一阶差商当h充分小或当xj充分靠近xi时，有在几何图形上，这三种差商分别表示弦AB、AC和BC的斜率。将这三条弦线与过点A的切线相比较，从图形上可以看出，一般地说，弦BC的斜率更接近于切线斜率f’(a)。等距节点公式向前差分iiifff-=

+1ikikikikffff1111)(-+--

-

=

=

向后差分111---

-

=

ikikikfffi1iifff-=

中心差分其中当节点等距分布时:（k个差分因子）

差分的重要性质：性质3：若f(x)是m

次多项式，则是性质1：常数的差分等于零性质2：差分算子为线性算子次多项式，且性质4：

这个性质类比于性质5：

（类比于分部积分法则）性质6：当节点xk是等距时，差分差商存在着关系：

差分值可由函数值算出：

=-+-=Dnjjknjknfjnf0)1(其中

=-+--=

njnjkjnknfjnf0)1(牛顿公式

牛顿前差公式

牛顿后差公式将节点顺序倒置：设，则)()()(000xfkthtxNxNknknn

=+=

=设，则)()1()()(0nknkknnnxfkthtxNxN

--=+=

=注：一般当x

靠近x0时用前插，靠近xn时用后插，故两种公式亦称为表初公式和表末公式。6.5Hermite插值多项式要求函数值重合，而且要求若干阶导数也重合。即：要求插值函数P(x)

满足p(xi)=f(xi),P’(xi)=f’(xi),…,P(m)(xi)=f

(m)(xi).

在实际问题中，对所构造的插值多项式，不仅把此类插值多项式称为埃米尔特（Hermite）插值多项式或称带导数的插值多项式，记为H(x)。

注：

N

个条件可以确定阶多项式。

要求在1个节点x0处直到m0

阶导数都重合的插值多项式即为Taylor多项式其余项为N

1例：设x0

x1

x2,已知f(x0)、f(x1)、f(x2)

和f’(x1),求多项式P(x)模仿Lagrange多项式的思想，设解：首先，P

的阶数=3

+=213)()()()()(=0iiixhx1f’xhxfxP

h0(x)有根x1,x2，且h0’(x1)=0

x1是重根。)()()(22100xxxxCxh--=又:h0(x0)=1C0h2(x)h1(x)有根x0,x2

))()(()(201xxxxB