数值分析原理封建湖答案
【篇一:数值分析原理课件第一章】
以误差为主线,介绍了计算方法课程的特点,并概略描述了与算法相关的基本概
念,如收敛性、稳定性,其次给出了误差的度量方法以及误差的传播规律,最后,结合数值实验指出了算法设计时应注意的问题.
1.1 引言
计算方法以科学与工程等领域所建立的数学模型为求解对象,目的是在有限的时间段内
利用有限的计算工具计算出模型的有效解答。
由于科学与工程问题的多样性和复杂性,所建立的数学模型也是各种各样的、复杂的. 复杂性表现在如下几个方面:求解系统的规模很大,多种因素之间的非线性耦合,海量的数据处理等等,这样就使得在其它课程中学到的分析求解方法因计算量庞大而不能得到计算结果,且更多的复杂数学模型没有分析求解方法.这门课程则是针对从各种各样的数学模型中抽象出或转化出的典型问题,介绍有效的串行求解算法,它们包括
(1) 非线性方程的近似求解方法; (2) 线性代数方程组的求解方法;
(3) 函数的插值近似和数据的拟合近似; (4) 积分和微分的近似计算方法; (5) 常微分方程初值问题的数值解法; (6) 优化问题的近似解法;等等
从如上内容可以看出,计算方法的显著特点之一是“近似”.之所以要进行近似计算,这与我们使用的工具、追求的目标、以及参与计算的数据来源等因素有关.
计算机只能处理有限数据,只能区分、存储有限信息,而实数包含有无穷多个数据,这样,当把原始数据、中间数据、以及最终计算结果用机器数表示时就不可避免的引入了误差,称之为舍入误差.我们需要在有限的时间段内得到运算结果,就需要将无穷的计算过程截断,从而产生截
11111
???的计算是无穷过程,当用en?1?????作为e的1!2!1!2!n!
近似时,则需要进行有限过程的计算,但产生了截断误差en?e.断误差.如e?1?
当用计算机计算en时,因为舍入误差的存在,我们也只能得到en
的近似值e,也就是说最终用e近似e,该近似值既包含有舍入误差,也包含有截断误差.
当参与计算的原始数据是从仪器中观测得来时,也不可避免得有观
测误差.
由于这些误差的大量存在,我们得到的只能是近似结果,进而对这
些结果的“可靠性”进行分析就是必须的,它成为计算方法的第二个
显著特点.可靠性分析包括原问题的适定性和算法的收敛性、稳定性.
所谓适定性问题是指解存在、惟一,且解对原始数据具有连续依赖
性的问题.对于非适定问题的求解,通常需要作特殊的预处理,然
后才能做数值计算.在这里,如无特殊说明,都是对适定的问题进
行求解.
对于给定的算法,若有限步内得不到精确解,则需研究其收敛
性.收敛性是研究当允许计算时间越来越长时,是否能够得到越来
越可靠的结果,也就是研究截断误差是否能够趋于零.
*
*
1
对于给定的算法,稳定性分析是指随着计算过程的逐步向前推进,
研究观测误差、舍入误差对计算结果的影响是否很大.
对于同一类模型问题的求解算法可能不止一种,常希望从中选出高
效可靠的求解算法.如我国南宋时期著名的数学家秦九韶就提出求
n次多项式
anxn?an?1xn?1???a1x?a0值的如下快速算法
s?an;
t?an?k;s?sx?t(k?1,2,?,n)
它通过n次乘法和n次加法就计算出了任意n次多项式的值.再如幂函数x可以通过如下快速算法计算出其值
s?x;
s?s?s;循环6次
如上算法仅用了6次乘法运算,就得到运算结果.
算法最终需要在计算机上运行相应程序,才能得到结果,这样就要
关注算法的时间复杂度(计算机运行程序所需时间的度量)、空间复杂
度(程序、数据对存储空间需求的度量)和逻辑复杂度(关联程序的开
发周期、可维护性以及可扩展性).事实上,每一种算法都有自己的
局限性和优点,仅仅理论分析是很不够的,大量的实际计算也非常重要,结合理论分析以及相当的数值算例结果才有可能选择出适合自己关心问题的有效求解算法.也正因如此,只有理论分析结合实际计算才能真正把握准算法.
64
1.2 误差的度量与传播
一、误差的度量
误差的度量方式有绝对误差、相对误差和有效数字.
定义1.1 用x作为量x的近似,则称x?x?:e(x)为近似值x的绝对误差.
由于量x的真值通常未知,所以绝对误差不能依据定义求得,但根据测量工具或计算情况,可以估计出绝对误差绝对值的一个较小上界?,即有
**
e(x)?x?x??
****
(1.1)
称正数?为近似值x的绝对误差限,简称误差.这样得到不等式x???x?x?? 工程中常用
x?x??
表示近似值x的精度或真值x所在的范围.
误差是有量纲的,所以仅误差数值的大小不足以刻划近似的准确程度.如量
?5000?ms?123?0.5cm?1.23?0.005m?1230000(1.2)
为此,我们需要引入相对误
差
*
*
*
*
*
x*?x
?:er(x*)为近似值x*的相对误差.当定义1.2 用x?0作为量x的近似,称x
*
x是x的较好近似时,也可以用如下公式计算相对误差
x*?x*
er(x)? (1.3)
x*
*
2
显然,相对误差是一个无量纲量,它不随使用单位变化.如式(1.2)
中的量s的近似,无论使用何种单位,它的相对误差都是同一个值.同样地,因为量x的真值未知,我们需要引入近似值x的相对误差限?r(x*),它是相对误差绝对值的较小上界.结合式(1.1)和(1.3),x
相对误差限可通过绝对误差限除以近似值的绝对值得到,即
?r(x)?
*
*
*
?(x*)
x
*
(1.4)
为给出近似数的一种表示法,使之既能表示其大小,又能体现其精
确程度,需引入有效数字以及有效数的概念.
定义1.3 设量x的近似值x有如下标准形式
*m
x??10?0.a1a2?an?ap
*
=?a1?10
?
m?1
?a2?10m?2???an?10m?n???ap?10m?p
*
?
(1.5)
其中{ai}ip,?,9}且a1?0,m为近似值的量级.如果使不等
式 ?1?{0,1x?x?
*
1
?10m?n 2
(1.6)
成立的最大整数为n,则称近似值x具有n位有效数字,它们分别
是a1、a2、… 和
an.特别地,如果有n?p,即最后一位数字也是有效数字,则称x*是有效数.
从定义可以看出,近似数是有效数的充分必要条件是末位数字所在位置的单位一半是绝对误差限.利用该定义也可以证明,对真值进行“四舍五入”得到的是有效数.对于有效数,有效数字的位数等于从第一位非零数字开始算起,该近似数具有的位数.注意,不能给有效数的末位之后随意添加零,否则就改变了它的精度.
**
例1.1 设量x??,其近似值x1?3.141,x2?3.142,x3?
*
22
.试回答这三个近7
似值分别有几位有效数字,它们是有效数吗?解这三个近似值的量级m?1,因为有
11
?10?2??101?3 2211*?31?4
x2?x?0.0004??0.0005??10??10
22
*
x3?3.142857142857?
11*?21?3
x3?x?0.001??0.005??10??10
22
***
所以x1和x3都有3位有效数字,但不是有效数. x2具有4位有效数字,是有效数.
x1?x?0.00059??0.005?
*
二、误差的传播
这里仅介绍初值误差传播,即假设自变量带有误差,函数值的计算不引入新的误差.对于函数y?f(x1,x2,?,xn)有近似值
y?f(x1,x2,?,xn),利用在点
***(x1,x2,?,xn)处的泰勒公式(taylor formula),可以得到
*
*
*
*
3
e(y)?y?y??其中fi:?
**
?f(x,x,?,x
i
*1
*2
i?1n
n
*n)(xi*?xi)
(1.7)
?f(x,x,?,x
i
*1
*2
i?1
*n)e(xi*)
?f
,xi*是xi的近似值,e(xi*)是xi*的绝对误差(i?1,2,?,n).式(1.7)表明函?xi
数值的绝对误差近似等于自变量绝对误差的线性组合,组合系数为相应的偏导数值.从式(1.7)也可以推得如下函数值的相对误差传播近似计算公式
xi*
er(y)??fi(x,x,?,x)*er(xi*) (1.8)
yi?1
对于一元函数y?f(x),从式(1.7)和(1.8)可得到如下初值误差传播近似计算公式e(y*)?f?(x*)e(x*) (1.9)
*
n
*
1
*2
*n
x*
er(y)?f?(x)*er(x*)
y
*
*
(1.10)
式(1.9)表明,当导数值的绝对值很大时,即使自变量的绝对误差比
较小,函数值的绝对误差也可能很大.
例1.2 试建立函数y?f(x1,x2,?,xn)?x1?x2???xn的绝对误差(限)、相对误差
*
的近似传播公式,以及xi?0
??
i?1时的相对误差限传播公式.
n
解由公式(1.7)和(1.8)可分别推得和的绝对误差、相对误差传播公式如下e(y)?
**
?f(x,x,?,x
i
*1
*2
i?1
n
*n
)e(x)=?e(xi*)
*i
i?1
n
(1.11) (1.12)
n
xi*xi**
er(y)??fi(x,x,?,x)*er(xi)=?*er(xi*)
yi?1i?1y
n
*
1
*2
*n
进而有
e(y)?
*
?e(x)??e(x)???(x)
*i
*i
*i
i?1
i?1
i?1
nnn
于是有和的绝对误差限近似传播公式 ?(y)?
*
当xi?0
*
??(x
i?1
n
*i
)
??
i?1时,由式(1.3)推得相对误差限的近似传播公式 n
?r(y)?
*
??(x
i?1
n
*i
)
y
*
??
i?1*i
n
n
n
xi*xi***
?r(xi)?max?r(xi)?**1?i?nyi?1y
xi*
?max?r(x)?*?max?r(xi*)
1?i?n1?i?n
i?1y
4
.3例1.3 使用足够长且最小刻度为1mm的尺子,量得某桌面长的
近似值a?1304
mm,宽的近似值b?704.8mm (数据的最后一位均为估计值).试
求桌子面积近似值的绝
对误差限和相对误差限.
解长和宽的近似值的最后一位都是估计位,尺子的最小刻度是毫米,故有误差限 ?(a*)?0.5mm,?(b*)?0.5mm
***
面积s?ab,由式(1.7)得到近似值s?ab的绝对误差近似为
*
*
e(s*)?b*e(a*)?a*e(b*) 进而有绝对误差限
*****
?(s)?b?(a)?a?(b)?704.8?0.5?1304.3?0.5?1004.55 mm2
相对误差限 ?r(s)?
*
?(s*)
s*
?
1004.55
?0.0011?0.11%
1304.3?704.8
1.3 数值实验与算法性能比较
本节通过几个简单算例说明解决同一个问题可以有不同的算法,但
算法的性能并不完全
相同,他们各自有自己的适用范围,并进而指出算法设计时应该注
意的事项.算例1.1 表达式
111??,在计算过程中保留7位有效数字,研究对不同的
xx?1x(x?1)
x,两种计算公式的计算精度的差异.
说明1:matlab软件采用ieee规定的双精度浮点系统,即64位浮
点系统,其中尾数占52位,阶码占10位,尾数以及阶码的符号各
占1位.机器数的相对误差限(机器精度)eps=2-52--
111?和算法2: y2(x)?的误差时,精确解用双精xx?1x(x?1)
度的计算结果代替.我们选取点集{?i}30i?1中的点作为x,比较两
种方法误差的差异.从图1.1可以看出,当x不是很大时,两种算法
的精度相当,但当x很大时算法2的精度明显高于算法1.这是因为,当x很大时,
11
和是相近数,用算法1进行计算时出xx?1
现相近数相减,相同的有效数字相减后变成零,于是有效数字位数
急剧减少,自然相对误差增大.这一事实也可以从误差传播公式(1.12)分析出.鉴于此,算法设计时,应该避免相近数相减.
在图1.2中我们给出了当x接近?1时,两种算法的精度比较,其中
变量x依次取为
??
?i
?1i?1.从图中可以看出两种方法的相对误差基本上都为10?7,因
而二者的精度相当.
?
30
5
【篇二:数值分析原理课件第二章】
xt>在科学计算中常需要求解非线性方程
f(x)?0(2.1)
即求函数f(x)的零点.非线性方程求解没有通用的解析方法,常采
用数值求解算法.数值解法的基本思想是从给定的一个或几个初始
近似值出发,按某种规律产生一个收敛的迭代序列
??
{xk}k?0,使它逐步逼近于方程(2.1)的某个解.本章介绍非线性方程实根的数值求解算法:二分法、简单迭代法、newton迭代法及其变形,并讨论它们的收敛性、收敛速度等.
2.1 二分法
一、实根的隔离
定义2.1 设非线性方程(2.1)中的f(x)是连续函数.如果有x*使
f(x*)?0,则称x*为方程(2.1)的根,或称为函数f(x)的零点;如果有
f(x)?(x?x*)mg(x),且g(x)在x*邻域内连续,g(x*)?0,m为正整数,则称x*为方程(2.1)的m重根.当m?1时,称x*为方程的单根.
非线性方程根的数值求解过程包含以下两步
(1) 用某种方法确定有根区间.称仅存在一个实根的有根区间为非线
性方程的隔根区间,在有根区间或隔根区间上任意值为根的初始近
似值;
(2) 选用某种数值方法逐步提高根的精度,使之满足给定的精度要求.对于第(1)步有时可以从问题的物理背景或其它信息判断出根的所在
位置,特别是对于连续函数f(x),也可以从两个端点函数值符号确定
出有根区间.
当函数f(x)连续时,区间搜索法是一种有效的确定较小有根区间的
实用方法,其具体做法如下
设[a,b]是方程(2.1)的一个较大有根区间,选择合适的步长
h?(b?a)/n,xk?a?kh,(k?0,1,?,n).由左向右逐个计算f(xk),如果有f(xk)f(xk?1)?0,则区间[xk,xk?1]就是方程的一个较小的有根区间.
一般情况下,只要步长h足够小,就能把方程的更小的有根区间分
离出来;如果有根区间足够小,例如区间长度小于给定的精度要求,则区间内任意一点可视为方程(2.1)的根的一个近似.
例2.1 确定出方程f(x)?x3?3x2?4x?3?0的一个有根区间.解由
f?(x)?3x2?6x?4?3(x?1)2?1?0知f(x)为(??,?)上的单调递增函数,
进而f(x)在(??,?)内最多只有一个实根.经计算知f(0)?0,f(2)?0,
所以f(x)?0在区间[0,2]内有惟一实根.
如果希望将有根区间再缩小,可以取步长h?0.5,在点x?0.5,x?1,x?1.5计算出函数值的符号,最后可知区间[1.5,2]内有一个实根.
11
二、二分法
二分法是求非线性方程实根近似值的最简单的方法.其基本思想是
将有根区间分半,通过判别函数值的符号,逐步缩小有根区间,直
到充分逼近方程的根,从而得到满足一定精度要求的根的近似值.
设f(x)在区间[a,b]上连续,f(a)f(b)?0,且方程(2.1)在区间(a,b)内有
惟一实根x*.记a1?a,b1?b,中点x1?(a1?b1)/2将区间[a1,b1]分为两个小区间[a1,x1]和[x1,b1],计算函数值f(x1),根据如下3种情
况确定新的有根区间:
(1) 如果f(x1)?0,则x1是所要求的根;
(2) 如果f(a1)f(x1)?0,取新的有根区间[a2,b2]?[a1,x1]; (3) 如果
f(x1)f(b1)?0,取新的有根区间[a2,b2]?[x1,b1].
新有根区间[a2,b2]的长度为原有根区间[a1,b1]长度的一半.对有根区间[a2,b2]施以同样的过程,即用中点x2?(a2?b2)/2将区间[a2,b2]再分为两半,选取新的有根区间,并记为 [a3,b3],其长度为[a2,b2]的一半(如图2.1所示).
图2.1 二分法示意图
重复上述过程,建立如下嵌套的区间序列
[a,b]?[a1,b1]?[a2,b2]???[ak,bk]??
其中每个区间的长度都是前一个区间长度的一半,因此[ak,bk]的长度为
1
bk?ak?k?1(b?a)
2
*
由x?[ak,bk]和xk?(ak?bk)/2,得
11
xk?x*?(bk?ak)?k(b?a)
22
*
当k??时,显然,有xk?x.总结得到如下收敛定理:
定理2.1 设f(x)在隔根区间[a,b]上连续,且f(a)f(b)?0,则由二分法产生的序列
*??
{xk}k?0收敛于方程(2.1)在[a,b]上的根x,并且有误差估计
1
(b?a)(k?1,2,?) (2.2) 2k
1
设预先给定根x*的绝对误差限为?,要求xk?x*??,只要k(b?a)??成立,这样求
2
xk?x*?
12
得对分次数
ln(b?a)?ln?
. (2.3)
ln2
取k为大于(ln(b?a)?ln?)/ln2的最小整数.此时xk是方程(2.1)的
满足精度要求的根近似
k?
值.
注:由于舍入误差和截断误差存在,利用浮点运算不可能精确计算
函数值,二分法中的判断f(xk)?0几乎不可能满足,取而代之为判断
条件f(xk)??0,其中?0为根近似值的函数值允许误差限.
总结以上内容,给出如下算法算法2.1(二分法)
输入端点a,b、根的绝对误差限?、根近似值的函数值允许误差
限?0;输出近似解c或失败信息;
step 1 用公式(2.3)计算最大迭代次数k; step 2 对n?1,?,k循环执
行step 3~5; step 3 c?(a?b)/2,计算f(c);
step 4 若f(c)??0,则输出c,end; step 5 若f(c)f(b)?0,则a?c,否则b?c.
例2.2 用二分法求f(x)?x3?4x2?10?0在[1,2]上的根x*的近似值,
要求
1
xk?x*??10?3.
2
解由于在区间[1,2]上,f(1)??5,f(2)?14,
f?(x)?3x2?8x?x(3x?8)?0,故
f(x)?0在[1,2]上有惟一实根x*.确定循环次数为k?11,利用二分
法计算结果见表2.1.
二分法具有如下特点
(1) 优点:计算简单,对函数f(x)的光滑性要求不高,只要它连续,
且在两端的函数值
异号,算法收敛就可以保证;
(2) 缺点:只能求单实根和奇数重实根,收敛较慢,与1/2为公比的
等比级数相同.当函数f?(x)连续时,方程(2.1)的实重根可转换为
f(x)
?0的实单根. f?(x)
一般在求方程根近似值时不单独使用二分法,而常用它为其它数值
方法提供初值.
13
2.2 简单迭代法
简单迭代法是求解非线性方程根的近似值的一类重要数值方法.本
节将介绍简单迭代法的基本思想、收敛条件、收敛速度以及相应的
加速算法.
一、简单迭代法的基本思想
简单迭代法采用逐步逼近的过程建立非线性方程根的近似值.首先给出方程根的初始近似值,然后用所构造出的迭代公式反复校正上一步的近似值,直到满足预先给出的精度要求为止.
在给定的有根区间[a,b]上,将方程(2.1)等价变形为
x??(x) (2.4)
在[a,b]上选取x0作为初始近似值,用如下迭代公式
xk?1??(xk) (k?0,1,2,?) (2.5)
*??*
建立序列{xk}k?0.如果有limxk?x,并且迭代函数?(x)在x的邻域内连续,对式(2.5)两边
k??
取极限,得
x*??(x*)
??因而x*是(2.4)的根,从而也是(2.1)的根.称?(x)为迭代函数,所得序列{xk}k?0为迭代序列.将这种求方程根近似值的方法称为简单迭代法,简称迭代法.
例2.3 试用方程f(x)?x3?x?1?0的不同形式的变形建立迭代公式,并试求其在1.5附近根的近似值.
解利用方程的变形建立如下4种迭代公式
(1)xk?1 3
?1
(2) xk?1?xk
(3) xk?1?3xk?xk?1
(4) xk?1?
2
取初值x0?1.5,迭代计算,结果见表2.2.
例2.3表明非线性方程的不同等价形式对应不同的迭代过程,从某一初值出发,有的迭代收敛快,有的收敛慢,甚至不收敛.那么迭代函数?(x)满足什么条件时才能保证迭代序列
??
收敛? 迭代序列{xk}k?0的误差如何估计? 怎样才能建立收敛速度快的迭代公式?
14
定理2.2 若函数?(x)在区间[a,b]上具有一阶连续导数,且满足条件
①对任意x?[a,b],有?(x)?[a,b];
②存在常数l:0?l?1,使得对任意x?[a,b]有?(x)?l成立.则
(1) 方程x??(x)在[a,b]上有惟一实根x*
(2) 对任意x0?[a,b],迭代公式(2.5)收敛,且limxk?x*
k??
(3) 迭代公式(2.5)有误差估计式
xk?x*?
l
xk?xk?1(2.6) 1?llk*
xk?x?x1?x0 (2.7)
1?l
xk?1?x*
???(x*) (2.8) (4) lim
k??x?x*
k
证明 (1)构造函数g(x)?x??(x),由条件①知g(a)?a??(a)?0,
g(b)?b??(b)?0,因此g(x)?0在[a,b]上至少存在一个实根,又由条件②知当x?[a,b]时,g?(x)?1???(x)?1?l?0,所以g(x)?0在[a,b]内存在惟一实根,即x??(x)在[a,b]内存在惟一实根,记为x*.
(2) 由x0?[a,b]及条件①知,xk?[a,b](k?1,2,?),并且有
xk?1??(xk),x*??(x*),二者作差,并由微分中值定理得
2(2.9) ,xk?1?x*??(xk)??(x*)???(?k)(xk?x*) (k?1,?
其中,?k介于xk与x*之间.结合条件②,得
2(2.10) ,xk?1?x*?lxk?x* (k?1,?
反复递推,有
0?xk?1?x*?lxk?x*?l2xk?1?x*???lk?1x0?x*, (k?1,2,?)
因0?l?1,故limxk?x*.
k??
(3) 由式(2.10)得
xk?x*?xk?xk?1?xk?1?x*?xk?xk?1?xk?1?x*
?xk?1?xk?lxk?x*
从而
xk?x*?
1
xk?1?xk (2.11) 1?l
又由于
xk?1?xk??(xk)??(xk?1)???(?k)(xk?xk?1)
?lxk?xk?1 (k?1,2,?) (2.12)
其中?k介于xk和xk?1之间.综合式(2.11)及式(2.12)得误差估计 l
xk?x*?xk?xk?1
1?l
由式(2.12)反复递推,得
15
【篇三:数值分析原理第八章】
得到特征值?,然后通过求得齐次线性方程组(a??i)x?0的非零向量x而得到矩阵a的相应于特征值?的特征向量.当矩阵阶数较高时,这种方法计算量很大,故常用数值方法近似求解特征值与特征向量.目前常用的数值方法有迭代法(幂法)和变换法(jacobi方法等)两类.
8.1 乘幂法与反幂法
一、乘幂法
乘幂法是求矩阵按模最大的特征值(主特征值)和相应的特征向量的一种迭代法.
设a?r
n?n
,初始向量v(0)?rn(v(0)?0),令
v(k)?av(k?1)
(8.1)
生成迭代向量序列v(k).由递推公式(8.1),知
(k)
??
v(k)?a(av(k?2))?a2v(k?2)???akv(0)
(0)
(8.2)
这表明v等于用矩阵a的k次幂左乘v
,故称此方法为乘幂法.
下面分析当k→∞时,向量序列v(k)的变化规
律.设?1,?2,…,?n为矩阵a?r
n?n
??
的n个特征值,且满足
(8.3)
n
?1??2????n
相应于特征值?1,?2,…,?n的n个线性无关的特征向量
x1,x2,?,xn构成向量空间?上的一组基.
任取非零的初始向量v
(0)
?rn,则v(0)可由这组特征向量线性表出
v
(0)
?c1x1?c2x2???cnxn??cjxj
j?1
n
(8.4)
其中c1,c2,?,cn为线性组合系数.将式(8.4)代入式(8.2),得
148
v
(k)
?a
k
k
cx?c(a?jj?jxj) j?1
j?1
nn
(8.5)
由akxj??kjxj和式(8.5),得
v
(k)
??cj?kjxj
j?1
n
(8.6)
当?1?0时,由式(8.3)知,特征值?1??2????n?0.下面针对?1?0进行讨论.由式(8.6)有
v(k)
kn?????jk
??1?c1x1??cj?????xj?
?j?2?1????
n?j??j
?
??xj?0,?
(8.7)
k
此时有
(k)
k
v(k)??1c1x1
(k)
上式表明,v
与x1只近似相差一个常数因子,故可取v
作为矩阵a的相应于主特
征值?1的近似特征向量.当k充分大时,若vi(k)?0,则有 k?1
vi(k?1)?1(c1x1)i
???1 (k)k
vi?1(c1x1)i
(8.8)
这表明主特征值?1可由式(8.8)近似求得.
如果矩阵a的特征值满足
?1??2????l,?1??l?1????n
则根据式(8.6)有
v(k)
?l
k
??1??cjxj?
??j?1k
??j??cj??????xj?
?j?l?1?1??n
(8.9)
则当k充分大时,由于
?j
?1(j?l?1,?,n),故有 ?1
149
v
(k)
??
k1
?cx
jj?1
l
j
l
(8.10)
由于x1,x2,?,xl都是矩阵a的特征值?1对应的特征向量,故特征值?1对应的特征向量.由式(8.10)知,k较大时,v
(k)
?cx
jj?1
j
?0也是矩阵a的
就是与主特征值?1的对应的近似特
征向量.类似于式(8.8),可求得主特征值的近似.由于此时?1的特征向量子空间不是一维的,故由式(8.10)得到的近似特征向量只是该子空间的一个特征向量,对于不同的初始向量v能得到?1的特征向量空间中线性无关的近似特征向量.
对于矩阵a的其它主特征值情形,如?1???2,?1?2等,同样可以用乘幂法求解,具体过程可参阅文献[6].以上讨论说明了乘幂法的基本原理.通过上述对乘幂法过程的分析可知,乘幂法是一种迭代法,公式计算简单,便于上机实践,可以方便地用于近似求矩阵按模最大的一个(或几个)特征值及相应的特征向量.需要注意的是: (1) 从理论上讲,对于任意给定的初始向量v
(0)
(0)
可
,有可能使式(8.4)中的c1?0,但因舍
(0)
入误差的存在,随着迭代过程的进行,等效于从c1?0的v
(2) 在用乘幂法(8.1)进行迭代计算时,迭代向量v
(k)
出发进行迭代.
的分量的绝对值可能会出现非常大
(当?1?1)或者非常小(当?1?1)的现象,甚至出现溢出.为此,实用中每进行m步就需要对迭代向量v
(k)
~(k)
进行一次规范化,即用v?
(k)
v(k)(k)(k)
(其中maxv表示向量v的按模最(k)
maxv
大的分量)代替v
继续迭代.由于特征向量允许相差一个常数因子,故按前面乘幂法的理论
依然得到正确的近似特征向量.在每次规范化后,用乘幂计算前后两个向量的分量的比值作为主特征值的近似,这种规范化并不影响主特征值的近似计算。规范化的乘幂法避免了溢出的可能性,至于m取多少,取决于实际情形,可以取m=5或m=1等等.
下面给出乘幂法的具体算法.
算法8.1 (乘幂法)
150
(0)
?rn(v(0)?0)、m;
输出主特征值的近似值?1及相应的近似特征向量x1;
(1)
step 1 利用式(8.1)求v,并由式(8.8)求?1,置k=1;
(1)
step 2 利用式(8.1)求vstep 3 判断?1
(k?1)
(k?1)
(k?1)
,并利用式(8.8)求?1;
(k)(k?1)
??1??是否满足?若满足,则取?1??1,x1?v(k?1),结束;否则,转向step4;
step 4 置k=k+1,判断mod(k-1,m)=0?若满足,取v
(k)
v(k)
?;转向step2. maxv(k)
例8.1 用乘幂法计算矩阵
3???123
?
a??31?2??
??27??3?
(k?1)
(k)??1?10?7.
的主特征值及相应特征向量,要求?1
解取初始向量v