第二章 插值法
知识点:拉格朗日插值法,牛顿插值法,余项,分段插值。
实际问题中,时常不能给出f (x )的解析表达式或f (x )解析表达式过于复杂而难于计算,能采集的只是一些f (x )的离散点值{xi,f(xi)}(i=0,1,2,…n )。因之,考虑近似方法成为自然之选。
定义:设f (x )为定义在区间[a ,b]上的函数,x0,x1,…,xn 为[a ,b]上的互异点,yi=f (xi )。若存在一个简单函数?(x ),满足
(插值条件)?(xi )=f (xi ),i=0,1,…,n 。
则称 ?(x )为f (x )插值函数,f (x )为被插函数,点x0,x1,…,xn 为插值节点,点{xi,f(xi)},i=0,1,2,…n 为插值点。
于是计算f (x )的问题就转换为计算 ?(x )。
构造插值函数需要解决:插值函数是否存在唯一;插值函数如何构造(L 插值);插值函数与被插函数的误差估计和收敛性。
对插值函数 ?(x )类型有多种不同的选择,代数多项式常被选作插值函数。
P23(2.18)和(2.19)指出,存在唯一的满足插值条件的n 次插值多项式p n (x )。但是需要计算范德蒙行列式,构造插值多项式工作量过大,简单表达式不易得到,实际中不采用这类方法。
插值法是一种古老的数学方法,拉格朗日(Lagrange )、牛顿(Newton )等分别给出了不同的解决方法。
拉格朗日插值
拉格朗日(Lagrange )插值的基本思想:把插值多项式p n (x )的构造问题转化为n+1个插值基函数l i (x)(i=0,1,…,n)的构造。 (1)线性插值 ①构造插值函数
已知函数y =f (x )的两个插值点(x 0,y 0),(x 1,y 1),构造多项式y =p 1(x ),使p 1(x 0)=y 0,p 1(x 1)=y 1。
p n (x )≈f (x )
由直线两点式可知,通过A ,B 的直线方程为 变形为 记 则
p 1(x )=l 0(x )y 0+l 1(x )y 1
插值完毕!
注意性质:l 0(x 0)=l 1(x 1)=1,l 0(x 1)=l 1(x 0)=0,p 1(x 0)=y 0,p 1(x 1)=y 1。
称l 0(x ),l 1(x )为点x 0、x 1的线性插值基函数。插值函数p 1(x )是这两个插值基函数的线性组合,这种形式的插值称作为拉格朗日(Lagrange )插值,相应多项式称拉格朗日线性插值多项式,记作L 1(x )。 ②误差
设L 1(x )为插值点(x 0,y 0),(x 1,y 1)的插值函数,f(x0)= y 0,f(x0)=y 1,f(x)一阶连续可导,二导数存在.则对任意给
定的x ∈[a,b],存在一点ξ∈[a,b],使
引进辅助函数,利用洛尔定理即证,见P17定理2.1。 (2)二次插值 ①构造插值函数
给定三个点{xi,f(xi)}, i=0,1,2,其中xi 互不相同,构造函数f (x )的二次插值多项式L 2(x ),满足:L
2
(x 0)=y 0,L 2(x 1)=y 1,L 2(x 2)=y 2。
通过三点的插值问题称为二次插值或抛物插值。仿线性插值,用插值基函数构造插值多项式。令
L 2(x )=l 0(x )y 0+l 1(x )y 1+l 2(x )y 2
待定函数l i (x )应是二次函数,满足约束条件
l i (xi )=1,l i (xj )=0(i ≠j ),i ,j =0,1,2。
此设l 0(x )=A(x-x1)(x-x2),l 1(x )=B(x-x0)(x-x2),l 2(x )=C(x-x0)(x-x1)。根据约束条件确定系数 由此得 ②误差
( ) ) ( 1 0 0
1 0 1 0 x p x x x x y y y y = - - - = +
1
A = (x 0-x 1)(x 0-x 2)
1
C = (x 2-x 0)(x 2-x 1)
1
B = (x 1-x 0)(x 1-x 2)
L 2(x) =
(x-x 1)(x-x 2) (x 0-x 1)(x 0-x 2) f(x 0) (x-x 0)(x-x 2) (x 1-x 0)(x 0-x 2) 1) (x-x 0)(x-x 1) (x 2-x 0)(x 2-x 1)
2)
+ + R 2(x) =
(x-x 0)(x-x 1)(x-x 2) f (ξ) (3)
,ξ∈[Min{x 0,x 1, x 2,x}, Min{x 0,x 1, x 2,x}] R 1(x) =
(x-x 0)(x-x 1) f (ξ) (2)
2!
,ξ∈[a,b] f(x)-L 1(x) = x-x 1
p 1(x )
= x 0-x 1 + x-x 0 x 1-x 0 y 0 y 1 x-x 1
l 0(x ) =
x 0-x 1
x-x 0
l 1(x )
= x 1-x 0
证明见P22定理2.2。
例 设sin11°=0.190809,sin12°=0.207912。用线性插值计算sin11°30ˊ. 解
L 1(11.5)=0.199361
例 设sin11°=0.190809,sin12°=0.207912,sin13°=0.224951。用二次插值计算sin11°30ˊ 解
L 2(11.5)=0.199369.
(3)一般情况
两个插值点可求出一次插值多项式L 1(x ),而三个插值点可求出二次插值多项式L 2(x )。当插值点增加到n +1个时,利用Lagrange 插值方法写出n 次插值多项式L n (x )。
详细说明见P22-24,(2.20),(2.21)至(2.24)。
关于Langrange 插值的几点说明
L n (x )仅与已知数据(x i ,y i ),(i =0,1,…,n) 有关,与f(x)的原来形式无关,但余式与f(x)密切相关。
若f(x)本身是一个不超过n 次多项式,则
内插(x 位于x0,x1,…,xn 之间)误差较小,外插有可能误差变大,慎用!插值点的增减,基函数要重新计算,很不方便!插值节点过多其精度不一定很好;limL n (x )=f (x ),x ∈[a,b]一般不成立.
k
n
k n
k n
k
j j j
k j
k
k n y x x x x x l y x L ) ( ) ( ) ( 0
∑ ∑ ∏
= = ≠ = - - = =
x-12 L 1(x ) =
11-12 x-11
0.190809 + 12-11
0.207912 R 1(x) = (x-x 0)(x-x 1) f (ξ) (2)
2!
=
(x-11)(x-12) -Sin(ξ) 2! |R 1(11.5)| ?
|(11.5-11)(11.5-12)|=0.125 1
2
L 2(x) = (x-12)(x-13) (11-12)(11-13) (x-11)(x-13) (12-11)(12-13) 0.207912 (x-11)(x-x 12) (13-11)13-12)
0.224951 + +
) ( ) ( , 0 ) ( x f x L x R n
n ≡ = 即
第二章 插值法
知识点:拉格朗日插值法,牛顿插值法,余项,分段插值。
Newton 插值法
Lagrange 插值多项式的一个缺点是没有承袭性质,增加插值节点时,需要重新计算所有插值基函数。牛顿插值多项式克服了这一缺点:增加一个节点时,可在原插值多项式基础上增加一项构成高一阶的插值多项式。
(1)差商即其性质
证 采用数学归纳法即证
性质2差商与节点排列顺序无关。
(2)线性牛顿插值
设互异y 0=f (x 0),y 1=f (x 1),构造线性插值函数的牛顿格式N 1(x )使y 0= N 1 (x 0),y 1= N 1 (x 1)。 利用点斜式,构造N 1(x )=a 0+a 1(x-x 0) 由f (x 0)=N 1 (x 0)= a 0
f (x 1)= N 1 (x 1)= f (x 0) +a 1(x 1-x 0
得
N 1 (x )= f (x 0) +
(x-x 0) (3)二次牛顿插值
上的二
在节点
定义 设函数 y=f(x) 在
区间 [ a , b ] 上 n +1 个互异节点 0 { x j } n
处的值 为: y i = f(x i ) ( i =0,1,2, …
,n ) - ① 称 j
i j i j i x x x f x f x x f - ?
) (
) ( ] , [ 为 f(x) 在节点 x i, 上的一阶差商;
② 称 k
i k j j i k j i x x x x f x x f x x x f -
- ? ] , [ ] , [ ] , , [ 为 在节点 阶差商 ; 依次类推 :
③ 称 n
n n n x x x x x f x x x f x x x f - - ?
- 0 2 1 1 1 0 1 0 ]
,..., , [ ] ,... , [ ] ,..., , [ 为 上的 n 阶差商.
x j f(x) x k x j, x i, f(x)
x 0, x 1, …, x n )
)....( )( ( ) ( ) (
) ( ] ,..., , [ ) ,..., 2 , 1 , 0 ( ) ( ] ,..., , [ 1 1 0 0 ' 1 0 1 0 n n
j j j n
j n x x x x x x x x x f x x x f n j x f x x x f n - - - = = = ∑ = ω ω 其中 的线性组合,即 函数值 是
阶差商 性质 ] , [ 1 0 x x f ) ( ) ( 0
1 0 1
] , [ 1 0 x x f x x x f x f = - - a 1=
设互异y 0=f (x 0),y 1=f (x 1), y 2=f (x 2),构造二次牛顿插值多项式N 2(x )使y 0= N 2(x 0),y 1= N 2(x 1),y 2=
N 2(x 2)。
令N 2(x )=a 0+a 1(x-x 0) +a 2(x-x 0) (x-x 1)
因在构造N 1 (x )过程中已得a 0和a 1,只要求出a 2即可 由
f (x 2)=N 2(x 2)= f (x 0) + (x 2-x 0)+a 2(x 2-x 0)(x 2-x 1
得
N 2(x 2)= f (x 0) + (x 2-x 0)+ (x 2-x 0)(x 2-x 1)
(4)一般情况
设互异y i =f (x i ),i=0,1,…,n 。构造n 次牛顿插值多项式N n (x )使y i = N n (x i ),i=0,1,…,n,。 根据差商定义
分段插值
(1)高阶插值与龙格现象
构造插值多项式时,根据误差表达式,是否多取插值点比少取插值点好?不一定!若被插函数是多项式,则多取插值点比少取插值点好。但对某些函数,有时插值点越多,效果越不理想。例如给定
对[-1,1]作等距分割,取h=2/10=0.2,x i = -1+0.2i , ,
i =0,1,…,10。构造10次插值多项式L 10(x ),在0点附近, L 10(x )近似f (x )的效果好,但在x=-0.90,-0.70, 0.70, 0.90时,误差较大!插值多项式在插值区间内有激烈振荡,这种现象称龙格现象。P29图2-4。
龙格现象揭示了插值多项式的缺陷,表明高次多项式的插值效果不一定优于低次多项式的插值效果。 插值误差由截断误差和舍入误差组成,由插值节点和计算产生的舍入误差,在插值过程中可能被扩散或放大,造成插值不稳定,高次多项式的稳定性一般比较差。
(2)分段线性插值
] , [ 1 0 x x f a 2= ] , , [ 2 1 0 x x x f ] , [ 1 0 x x f ] , , [ 2 1 0 x x x f 插值公式和余项。 上的
在节点 分别为 、 其中 Newton } { ) ( ) ( )
( ) ( ] ,... , [ ) )...( )( ( ... ]
, , [ ) )( ( ] , [ ) ( ) ( ) ( 0 1 0 1 1 0 2 1 0 1 0 1 0 0 0 n i n n n n n x x f x R ) ( n x N x R x N x x x f x x x x x x x x x f x x x x x x f x x x f x f + = - - - + + - - + - + = ] ,... , , [ ) )( )...( )( ( 1 0 1 1 0 n n n x x x x f x x x x x x x x - - - - + - - ) ( n+1
x N ) ( n x N ] ,... , [ ) )( )...( )( ( 1 0 1 1 0 n+1 n n x x x f x x x x x x x x - - - - + - = 2
25x 1 1
=
x) f( + x ∈[-1,1]
2 25x 1 1
, x ( + i i )
加密插值节点不一定能使插值函数很好逼近被插函数,于是就有了分段线性插值的概念。
基本思想:给定区间[a,b],作分割a=x0 第三章 数据拟合 知识点:曲线拟合,最小二乘法。 离散数据曲线拟合 (1)曲线拟合问题 实践活动中,如果只能观测或测量到函数y=f(x)的一组离散的实验数据: (x i ,y i ),i =0.1.2…,n 。则当这些数据比较准确时,可以构造插值函数?(x)逼近f(x),只要满足插值原则: ?(x i )= y i (i =0.1.2…,n) 如果离散数据序列(x i ,y i )带有不可避免的误差(噪音):插值原则限定可能使误差保留和扩散。 如果在非插值节点处插值函数?(x)不能很好近似f(x),误差可能很大。 如果实验数据很多,因插值节点多,得到的插值多项式的次数较高:不仅计算量过大,而收敛性和稳定性不能保证,会出现龙格现象,逼近效果不好! 于是,构造的逼近函数?(x)最优靠近样点(如图)成为理想选择,即向量T=(?(x 0), ?(x 1),…?(x n ))与Y=(y 0,y 1,。。。,y n )的误差和距离最小。按T 和Y 之间误差最小原则作为最优标准构造的逼近函数称拟合函数。 如何为f(x)找到一个既简单又合理的逼近函数?(x)?通常采用曲线拟合方法来处理,曲线拟合就是构造近似函数?(x),在包含全部基节点x i (i =0.1.2…,n)的区间上能“最好”逼近f(x),不必满足插值原则。这类问题称曲线拟合问题,近似函数y =?(x)称经验公式或拟合曲线或函数。拟合法则根据数据集(x i ,y i ), i =0.1.2…,n 找出其间合适的数学公式,构造出一条反映这些给定数据一般变化趋势的曲线?(x),不要求曲线?(x)通过所有的点(x i ,y i ),但要求这条曲线?(x)能尽可能靠近这些数据点或样点,即各点误差δi =?(x i )-y i 按某种标准达到最小。通常用误差的2-范数平方(均方误差或误差平方和) 2 2 2 0 n i i = = ∑ δ δ 2 4 4 2 ? ? ? ? ? ? ? ? -4 -2 样点 y =?(x) 作为总体误差的度量,以误差平方和达到最小—最小二乘原理作为最优标准构造拟合曲线的方法为曲线拟合的最小二乘法。 (2)多项式拟合 ①线性拟合 给定一组(x i ,y i ), i =0.1.2…,n 。构造线性拟合函数p 1(x )=a+b x ,使均方差 达到最小。即如何选择a 、b ,使F(a,b) 达到最小,转化为求多元函数F(a,b)极小值问题。F(a,b)取极小值 应满足 整理得到拟合曲线满足 上式称为拟合曲线的法方程组或正则方程组。用消元法或克莱姆法则求解方程组得 得到均方误差意义下的拟合函数p 1(x )。 ②二次拟合 给定一组(x i ,y i ), i =0.1.2…,n 。用二次多项式拟合这组数据。 设p 2(x )= a 0+ a 1x+ a 2x ,作出拟合函数与数据序列的均方误差: 类似线性拟合,根据最小二乘和极值原理: 2 2 δ 2 0 n i i = = ∑ δ 2 n i = = ∑ (p 1(x i )-y i ) 2 n i = = ∑ (a +b x i -y i ) =F(a,b) b n i = ∑ x i y i y i 0 n i = ∑ 0 n i = ∑ x i n - ( ) n 2 n i = ∑ x i 2 0 n i = ∑ x i ( ) - ( ) = / = a 0 n i = ∑ x i 0 i = ∑ x i y i - 2 n i = ∑ x i 0 n i = ∑ y i n ) ( / n 2 0 n i = ∑ x i 2 n i = ∑ x i ( ) - ( ) 2 0 n i = = ∑ (a +b x i -y i ) = F(a,b) a 0 2 0 n i = = ∑ (a +b x i -y i ) = F(a,b) b 0 2 x i 2 n i = ∑ (p 2(x i )-y i ) = 2 n i = = ∑ (a 0+ a 1x i+a 2 x i -y i ) F(a 0,a 1,a 2) 2 ( 2 2 δ 2 n i i = = ∑ δ ) = 0 0 n i = = ∑ (a 0+ a 1x i+a 2 x i -y i ) F a 0 2 2 n 2 = n i = ∑ x i y i y i 0 n i = ∑ b a 0 n i = ∑ x i n 2 n i = ∑ x i n i = ∑ x i 整理得到二次多项式函数拟合的法方程: 解法方程,便得到均方误差意义下的拟合函数p 2(x )。不过当多项式的阶数n>5时,法方程的系数矩阵病态。计算中要用双精度或一些特殊算法以保护解得准确性。 ③一般情况 给定一组(x i ,y i ), i =0,1 ,2…,n 。在函数类{ (m 方达到最小。这里?0(x ),? 1 (x ),…,? m (x )是一组线性无关的连续函数,p (x )是{ 的线性组合。 类似线性拟合处理。 p 2(x )= a 0+ a 1x+ a 2x 2,经计算得 } 0 (x ) m k ? } 0 (x ) m k ? 0 n i = = ∑ (a 0+ a 1x i+a 2 x i -y i ) x i F a 2 2 2 2 = 0 = 0 n i = ∑ x i n 2 n i = ∑ x i 2 n i = ∑ x i 0 n i = ∑ x i 3 0 n i = ∑ x i 3 n i = ∑ x i n i = ∑ x i 4 n i = ∑ x i 2 a 1 a 0 a 2 n i = ∑ x i y i y i n i = ∑ 0 n i = ∑ x i y i 2 相应的法方程为: 7 a 0 +0 a 1 +28 a 2=1 0 a 0 +28 a 1 +0 a 2=-39 28 a 0 +0 a 1 +196 a 2=-7 解方程得: a 0= 0.66667,a 1=-1.39286, a 2=-0.13095。 所以p 2(x )= 0.66667-1.39286x-0.13095x 拟合曲线均方误差: 如何根据测量的数据设计和确定“最贴近”的拟合曲线?关键在于找到适当的拟合曲线类型,可以根 据专业知识和工作经验确定拟合曲线类型。如果对拟合曲线一无所知,可以先绘制数据略图,可能从中观测出拟合曲线类型。一般情况下,应对数据进行多种曲线类型拟合,计算均方误差,用数学实验的方法找出最小二乘法意义下的误差最小的拟合函数。 2 2 2 δ 2 1 7 i i = = ∑ δ = 2 1 7 i = ∑ (p 2(x i )-y i ) = 3.09524 第六章 线性方程组的解法-直接法 知识点:简单消元法,主元消元法,矩阵的三角分解。 1.概 念 设线性方程组 简记 AX=B, 其中 采用克来姆法则解方程组工作量非常大,寻求数值解成为必要,线性方程组的数值解法一般归结为两类. 直接法:经过有限步算术运算,求得方程组的精确解(若在计算过程中没有舍入误差)。 迭代法:用某种极限过程去逐步逼近线性方程组精确解。 2.Gauss 消去法 古老的直接求解线性方程组的方法 例 1.解方程组 解 第一步:-2 x (1 )+(3)得同解方程组 ?? ???? ?=+++=+++=+++n n 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[][] T n T n n n ij n n n b b b x x x a a a a a a a a a a b x 2121 n 2 n 1n 222 21 12111,) (A ===????? ?? ?????=?代替所得。 列用 的第 是 , , ,其中 法则: B i A A A D n i D D x Gramer i i i i i ) det( 0 A) det( D ,..., 2 , 1 = ≠ = = = (A ) ? ? ? ? ? ? ? - = - - = - = + + ) 4 ( 1 1 4 ) 2 ( 5 4 ) 1 ( 6 3 2 3 2 3 2 1 x x x x x x x -11 -1 -4 5 -1 4 0 6 1 1 1 ? ? ? ? ? ? ? = + - = - = + + ) 3 ( 1 2 2 ) 2 ( 5 4 ) 1 ( 6 3 2 1 3 2 3 2 1 x x x x x x x x 1 1 -2 2 5 -1 4 0 6 1 1 1 增广阵 第二步:1 x (2 )+ (4 )得同解方程 回代得解向量:x =[1,2,3]T (1)顺序Gauss 消去法 顺序消去未知数的方法。 例2 .解方程组 解 第一步:用方程(1)消去(2),(3)中x 1,即(1) x (-1 )+(2),(1) x (-2)+(3),并保留(1)得 第二步:用方程(4)消去(5)中x 2,即(4) x (2 )+(5),并保留(1),(4)得上三角形方程组 回代得解:x =[1,2,3]T 求解过程中假设了变换后的同解方程组或等价矩阵的主对角元非零,即 一般计算过程见教材P106-109. 建议认真阅读。 算法见教材110-111. 建议认真阅读。 运算量见教材111。 (2)主元素 Gauss 消去法 ①列主元消去法:在一列中选取按模(绝对值)最大的元素,将其调到主干方程位置进行顺序消元的方 = + + ) 3 ( ) 2 ( ) 1 ( 6 3 2 1 = + - 1 2 2 3 2 1 x x x x x x = - + 1 3 3 2 1 2x x x = + + (5) ) 4 ( ) 1 ( 6 3 2 1 = - - -11 4 3 2 x x x x x = - -5 2 3 2 3x x = + + (6) ) 4 ( ) 1 ( 6 3 2 1 = - -21 3 7x x x x = - -5 2 3 2 3x x . , , ) ( 即数值不稳定 做除数易产生解的失真 用 此时 k kk a , 0 ) ( 很小 注 k kk a ≈ ? ? ? ? ? ? ? - = - = - = + + ) 5 ( 6 2 ) 2 ( 5 4 ) 1 ( 6 3 3 2 3 2 1 x x x x x x -6 -2 5 -1 4 0 6 1 1 1 。 0 ) ( k kk a ≠ 法。 例 3.用列主元消去法解方程组(强调选择列中绝对值最大元) 回代得解:x =[1,2,3]T Gauss 列主元消元法一般形式 第1步消元 从第一列中选出按模最大的元素作为主元素:|a i1|=max{|a j 1|,1?j ?n},交换第1行和第i 行的所有元素,然后,顺序将a 21,a 31,…,a 11,a i+1,1,…,a n1变为零。 第k 步消元 从 的第k 列 , , 中选取绝对值最大项,记录所在行,即 若 交换第k 行与l 行的所有对应元素,再进行顺序消元。建议认真阅读 ②全主元消去法:在方程组整个系数矩阵A 中选取绝对值最大的元素作为主元素,适当交换方程组中方程或未知数位置次序进行消元的方法。 例4 .用全主元消去法解例 3所示方程组,取四位有效数字。 解 首先,三个方程的系数中绝对值最大者为-18(做主元),交换第一个方程与第二个方程的位置,以交换后的方程组(方程组形式学生课堂回答)的第一个方程为主干方程,消去其余两个方程中的x 1(具体操作学生课堂回答),得 = + - ) 3 ( ) 2 ( ) 1 ( 15 3 2 1 = + + 6 3 2 1 x x x 3x 3x 12x = - + -15 3 - 3 2 1 x x 18x (A|b) = 15 6 1 1 1 3 -3 12 -15 3 -1 -18 6 1 1 1 15 3 -3 12 -15 3 -1 -18 17/18 7/6 0 5 7/3 -1 0 -15 3 -1 -18 31/6 17/18 7/6 0 5 7/3 -1 -15 3 -1 31/6 17/18 7/6 66/7 22/7 0 0 -15 3 -1 ) ( A k (k) kk a (k) k k a 1 + (k) nk .a .. k i l = 记 = ? ? max n i k k a k i k | ) ( | k a k i | ) ( | k l ≠ = - + -15 3 - 3 2 1 x x 18x 然后,在方程组中的后两个方程中,再选取系数中绝对值最大者为主元,此时主元应为2.333。交换方程组中x 2和x 3位置,并消去x 3得 回代得解:x =[1.000,2.000,3.000]T (3) 高斯-约当消去法 高斯消元法将系数矩阵化为上三角矩阵,再进行回代求解。而Gauss-Jordan 消去法是将系数矩阵化为对角矩阵,再进行求解,无回代过程见教材P112.。 Gauss 列主元消去法算法见教材P117,从算法优化的角度考虑, Gauss 列主元消去法比较好。 3.矩阵三角分解法 LU 分解相关信息见教材P118-123。建议认真阅读,有利巩固线性代数知识。 4.误差分析 教材P127,6.5节。范数基础另课介绍。 回顾、阅读、理解与运用 :P127范数,计算量统计,消去法一般解释115-117。 = 5.000 3 = 3.144 2 1.572x 2.333x - 2 x = + -15 - 1 - 3 x 3 2 x 18x 第六章 线性方程组的解法-范数 知识点:向量范数与矩阵范数及其性质,谱半径,条件数。 1.概念 在一维数轴上,任意两点x 1,x 2之间距离用| x 1-x 2 |表示。 在二维平面上,平面上任意两点P 1(x 1,y 1),P 2(x 2,y 2)的距离用 表示。 推广到n 维空间,就有了向量范数的概念。 2.向量范数 (1)常见的向量范数 (2)向量范数性质 例如 参阅P127定理6.1。 (3)向量的收敛性(P128定理6.2) 2 2122121)()(||y y x x P P -+-= |} {|max ||||) (),()||(||||| |||||),...,,(12 12 1211 221121i n i T n i i n i i T n x x x x x x x x x x x x x x ≤≤∞========∑∑设向量∞ ? ? n x x x 1 1 || || || || || || 1 ) ( ) ( 2 ) ( 1 ) ( ) ( , } ,..., , { ,...), 2 , 1 }( { 2 x x T k n k k k k n x x x k R 其中 中一向量序列 设 定义 = = n R M m x x x x ∈ ? ? ? β α β || || || || || || M m , , 使得 则必存在两正数 n n n n x x x R R x x y x y x y x ? ?∈ - ≦- ∈ β α || || , || || R 3 ,..., , || || , 2 1 2 1 中定义的任意两种范数 对 性质 的一致连续函数。 是分量 则向量范数 设 性质 。 有 对任意 性质 , 一切范数都是等价的,即 且满足 : x 的范数。 为向量 则称 , 都有 三角不等式:对任意 齐次性: 时, ,当且仅当 非负性: 法则对应于一非负实数 按某一确定的 设任一向量 x x R R k k k R y x y x y x x x x x x x n n || || || || || || || || , , ; ||, ||| | || || ; 0 || || 0 0 || || ||, || , 1 定 义+ ? + ∈ ∈ = = = ? ∈ 3.矩阵范数 (1)算子范数 单位矩阵的范数等于1(练习)。 (2)相容范数 (3)常见的矩阵范数(P129) 例题 * ) ( * || || } { 0 || || lim x x x x k (k) k 收敛到 依范数 则称向量序列 如果有 ? = - ∞ → * * ) ( lim , } { x x x x (k) k k 记作 依次收敛到 则称向量序列 = ∞ → * * * 2 * 1 * ) ,..., 2 , 1 ( lim ) ,..., , ( x i (k) i k n T n n i x x R x x x 满足 如果存在 = = ∈ = ∞ → 的一种范数。 为 则称 , , 相容性: 三角不等式: , 奇次性: 时, ,当且仅当 非负性 且满足 应于一非负实数 若按某一确定的法则对 设任意 定义 n n n n n n n n R A R B A B A AB R B A B A B A R k A k kA A A A A R A ╳ ╳ ╳ ╳ ∈ ? ? ∈ ? + ? + ∈ = = = ? ∈ || || , ; , ||, || || || || || ; || ||| | || || ; 0 || || 0 0 || :|| : ||, || , . . 3 是相容的。 与此向量范数 则称该矩阵范数 如果 的一种范数 和 分别为 设 定义 || || || || || || || || || || , || || ||, || 5 x A x A Ax R R A x n n n ? ╳ 上的算子范数。 算子范数是矩阵范数。 为 称 设 定义 , || || max || || || || max || || , , 4 1 || || 0 n n x x n n n R Ax x Ax A R A R x ╳ = ≠ ╳ = = ∈ ∈ ∞ = p p x ), 2 , 1 ( 2 相容的矩阵范数是 与向量范数 定理 ) ,... 2 , 1 ( lim 0 max lim 0 || || lim || || } { ,...) 2 , 1 }( { 1 * ) ( ) ( 1 * * ) ( * ) ( n i x x x x k i k i k i k i n i k k k k k x x x x x x = = = - = - ? = ∞ → ? ? ∞ → ∞ ∞ → ) ( 事实上 。 收敛到 数 依范 的充分必要条件是 坐标收敛到 依 向量序列 定理 ∑ = ? ? = - n i ij n j a A 1 1 1 | | || || 1 max 范数: (列和范数) ∑ = ? ? ∞ = - ∞ n j ij n i a A 1 1 | | max || || 范数: (行和范数) = - T AA A max 2 ) ( || || 2 范数: λ (谱范数) 12 - 4.矩阵的谱半径和矩阵序列收敛性 例题 (1)谱半径和矩阵序列的收敛性 P129(6.35),P130(6.37)。 (2)矩阵序列的收敛性 则称 征值 的特 为矩阵 设 定义 的谱半径。 为矩阵 A A ,...,n) , (i λ i , 2 1 6 关系。 的任何一种范数有某种 但可能与 的一种范数 不是 的谱半径 矩阵 A A A A , ) ( ρ A i n i |} {| max ) ( 1 λ ρ ? ? = = 3 3 ) ( 3 3 , 3 3 0 4 2 1 2 | | 4 2 1 2 2 1 + = - = + = = - - = - ? ? ? ? ? ? - - = A A I A ρ λ λ λ λ λ 所以 。 特征值 得: 解:由 的谱半径。 求矩阵 。 的任意性,有 由 ,故有 由于 A A A x ? = ? ≠} max{ ) ( λ ρ λ λ x x x 则 的任一特征对,即 为矩阵 设 证明 A A A A x x x x ? = = = , , ① λ λ λ λ 。 则 若 的任意一种算子范数 为 这里 则 设 定理 A A A A A A A A R A T n n = = ? ∈ ╳ || || ) ( , ② ; || || ||, || ) ( ① , 3 2 ρ ρ 如果 及矩阵 设矩阵序列 定义 n j i a a a A k a A ij k ij k n n ij n n k ij k ) ,..., 2 , 1 , ( lim , ) ( ), ,..., 2 , 1 ( ) ( 7 ) ( ) ( = = = = = ∞ → ╳ ╳ P128,P130定理6.4。 5.病态方程组与矩阵的条件数 。 的充分必要条件是 则 设 定理 。 收敛于矩阵 依范数 的充分必要条件是 收敛到矩阵 矩阵序列 1 ) ( 0 lim , 4 } { ) ,..., 2 , 1 ( } { < = ∞ → ∈ ? = ╳ A k A k R A A A A n k A n n k k ρ . ) ( ; A A A A Cond(A) R A 8 2 1 2 1 - b x 的谱条件数 关于方程组 为矩阵 称 的条件数 关于线性方程组 为矩阵 为非奇异矩阵,称 设 定义 b Ax A A A A K n n = = = = ∈ - ╳ 为病态方程组。 解的相对误差也大 大时 如果 谓良态方程组; 的相对误差也小,则称 解 相对较小时 如果 与条件数相关 解的相对误差直接 线性方程组 b Ax A b Ax A b Ax = = = , ) cond( , ) ( cond , 则称 第八章线解性方程组的迭代法 知识点:Jacobi 迭代法,Gauss-Seidel 迭代法,收敛条件,误差估计。 1.Jacobi 迭代法 例 当迭代次数增加时,迭代结果越来越逼近精确解。迭代到第11次时,有 按格式(III )的“形式”进行迭代求解的方法称雅可比迭代法。 2.Gauss-Seidel 迭代法(P163) ) 0 , 0 , 0 ( = x 做迭代初值,迭代结果如下表 取 T ) 0 ( 解:从三个方程中分离出x1,x2和x3, 3 2 1 3 2 1 2 5 . 1 3 . 0 0 4 . 0 2 . 0 1 . 0 0 2 . 0 1 . 0 2 . 0 0 ? ? ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? x x x x x x 原方程改写为 2 1 3 3 1 2 3 2 1 2 4 . 0 2 . 0 5 . 1 1 . 0 2 . 0 3 . 0 1 . 0 2 . 0 ? ? ? ? ? + + = + + = + + = x x x x x x x x x ) ( 1 x k ) ( 2 x k ) ( 3 x k k T ) 11 ( ) 0000 . 3 , 0000 . 2 , 0000 . 1 ( = x 解线性方程组 = - - - - - - 10 15 5 2 1 1 10 2 1 2 10 3 2 1 x x x T ) * ( ) 3 , 2 , 1 ( = x 精确解 由此构造迭代格式 ) ( 2 ) ( 1 ) 1 ( 3 ) ( 3 ) ( 1 ) 1 ( 2 ) ( 3 ) ( 2 ) 1 ( 1 ,... 1 , 0 2 4 . 0 2 . 0 5 . 1 1 . 0 2 . 0 3 . 0 1 . 0 2 . 0 = ? ? ? ? ? + + = + + = + + = + + + k x x x x x x x x x k k k k k k k k k (III ) 法求线性方程组 用 例 - Seidel Gauss 3.迭代法的一般形式 设线性方程组 其中 由线性方程组理论知该方程组有唯一解 。令G =I-A,F=B ,则该方程组(I )的等价形式为: x=G x+F 式中G 称迭代矩阵,F 称为迭代向量,这时称迭代公式(II )收敛,否则为发散的。 (1)Jacobi 迭代法一般情形(教材P161) - - - - n n b b x x a a a a x x a a ... 0 ... 0 0 ... 0 0 ... 0 2 1 2 1 2 21 1 12 2 1 22 11 改写(I ) = ≠ ii n i a 若A ) ,..., 2 , 1 ( 0 为非奇异矩阵且 的解。 的解,即 为方程组 的 则 或 即收敛, 若向量序列 B Ax G G F x x x F x x x x x x x k k k k k = + = + = = - = ∞ → ∞ →* * * * ) ( * ) ( ) ( 0 || || lim lim } { R R B B x n n ≠ ∈ ∈ 且 0 , 且非奇异, R A n n ∈ ╳ x * B 或Ax = = n n nn n n n n b b b x x x a a a a a a a ... ... ... ... ... ... ... ... ... 2 1 2 1 2 1 2 22 21 1 12 11 x 作 任取初始向量 ) 0 ( ...... ) 1 ( ) 2 ( ) 0 ( ) 1 ( + = + = G G F x x F x x ) ,( ... 2 , 1 , 0 = k ) ( ) 1 ( + = + G F x x k k (II ) 。 得 , , 步由 第 依此类推 ; 得 同理由 步 第 ; 代入迭代公式得 由 步 第 ; 由迭代公式解得 步 第 设初值 迭代法进行修正 对 ) 1 ( ) 0 ( ) 1 ( 1 ) 1 ( 3 ) 1 ( 2 ) 1 ( 1 ) 1 ( 3 ) 0 ( ) 0 ( 3 ) 1 ( 2 ) 1 ( 1 ) 1 ( 2 ) 0 ( ) 0 ( 2 ) 1 ( 1 ) 1 ( 1 ) 0 ( ) 0 ( 2 ) 0 ( 1 , ..., , ,..., , , 3 ,..., , 2 1 ,..., , Jacobi n n n n n n x x x x x x n x x x x x x x x x x x x x -