下载文档原格式
实验十六 迭代式与不动点【实验目的】1． 了解迭代的基本概念。
2． 了解不动点的基本概念。
3． 学习掌握MATLAB 软件有关的命令。
【实验内容】计算数列 ,3,3,3的极限【实验准备】1．迭代的基本概念迭代数列：迭代就是把给定的函数f 连续不断地反复作用在初值a 上。
通过迭代，我们会得到一个迭代数列：))),((()),((),(,a f f f a f f a f a把迭代数列记为 ,,,,,210n x x x x 。
迭代格式：迭代一种机械的重复动作，很适合于计算机的运算特点，因此迭代算法在各种数值方法中处于核心地位。
迭代可以表示成如下的形式：,3,2,1),(,10===+n x f x a x n n称为由函数f 导出的迭代格式。
2．不动点的基本概念对迭代格式的两端取极限∞→n ，当极限存在时,得到方程)(x f x =.函数f 的意义是把自变量x 映射成因变量y ,而上式的意义时表示x 在影射f 得像不发生改变.因此称该方程为不动点方程,方程的根称为函数f 的不动点.3．压缩映像原理定理1 设)(x f y =把区间],[b a 映射成],[b a ,并且存在10<<q ,使得对于任意],[,21b a x x ∈,有2121)()(x x q x f x f -≤-,则(1) *内存在唯一的不动点*x ,满足)(**x f x =;(2) 对任意初始值],[0b a x ∈,迭代序列)(1n n x f x =+收敛于*x ;(3) 01***11,x x qq x x x x q x x nn n n --≤--≤-+.定理2 设)(x f y =在间],[b a 内可导,且],[b a y ∈.若存在10<<q ,使得对任意],[b a x ∈均有q x f ≤)(',则定理1的结论成立.由拉格朗日中值定理可知,定理2是定理1的特例.定理不仅给出了收敛条件,而且还给出了收敛误差的估计.可以看出,q 越小收敛越快.但是要确定对任意],[b a x ∈均有q x f ≤)('显然不太方便.在*x 的附近,有如下局部收敛定理:定理3 设)(x f y =在*x 的一个领域内连续且1)('*≤x f ,则对该领域内的任意初始值0x ,迭代序列)(1n n x f x =+收敛于*x .4．迭代的MATLAB 命令MATLAB 中主要用for, while 等控制流命令实现迭代.【实验方法与步骤】练习1 计算数列 ,3,3,3的极限.可用for 语句, for 循环允许一组命令以固定的和预订的次数重复. For 循环的一般形式为:for x=表达式1:表达式2:表达式3 语句体 end其中表达式1的值为循环的初值,表达式2的值为步长,表达式3的值为循环的终值.如果表达式2省略,则默认为1.本练习中,相应的MA TLAB 代码为：>>clear; >>x=3>>for i=1:10 >>x=sqrt(x) >>end可算得迭代数列的前10项:7321, 1.3161, 1.1472, 1.0711, 1.0349, 1.0173, 1.0086, 1.0043, 1.0021, 1.0011 可见此数列的极限为1.本练习也可用while 语句,while 循环一般用于事先不能确定循环次数的情况.while 循环的一般形式为:while 表达式 语句体 end只要表达式的值为1(真),就执行while 与end 之间的语句体,直到表达式的值为0(假)时终止该循环.通常,表达式的值为标量,但对数组值也同样有效,此时,数组的所有元素都为真,才执行while 与end 之间的语句体. 本练习中,相应的MA TLAB 代码为：>>n=0; eps=1.0e-5; x=3; >>while abs(x-sqrt(x))>eps >>x=sqrt(x); n=n+1; >>end >>x, n结果为x =1.0000, n =16.这说明迭代到第16次后,数列的前后两项之间的误差小于510-,数列收敛到1.一般说来,在事先不知道迭代是否收敛时,可用for 语句.如果知道迭代是收敛的,为了控制迭代计算的误差,用while 语句是比较合适的.迭代过程启发我们,设法将方程0)(==x f y 变形为不动点方程)(x g x =,就有可能利用迭代法求出方程的根.练习２利用迭代法求解方程013=--x x .先请读者画出函数1)(3--=x x x f 的图形,观测函数的图形可以看出,在区间]2,1[方程有唯一正根.迭代格式1 方程变形为31)1(+=x x ,先用for 语句,初值设为1.5,相应的MA TLAB 代码为：>>clear; >>x=1.5; >>for i=1:10 >>x=(x+1)^(1/3) >>end可算得迭代数列的前10项:1.3572, 1.3309, 1.3259, 1.3249, 1.3248, 1.3247, 1.3247, 1.3247, 1.3247, 1.3247可见此迭代格式是收敛的,方程的根约为 1.3247.进一步,如果要控制计算误差,比如说要使得计算误差小于510-,可用while 语句, 相应的MATLAB 代码为：>>n=0; eps=1.0e-5; x=1.5; >>while abs(x-(x+1)^(1/3))>eps >>x=(x+1)^(1/3); n=n+1; >>end >>x, n计算结果为 x =1.3247,n =6,说明只需进行6次迭代,就可达到所要求的精度.迭代格式2 方程变形为21xxx +=,用for 语句,初值设为1.5,相应的MATLAB 代码为： >>clear; >>x=1.5; >>for i=1:10 >>x=(x+1)/x^2>>end可算得迭代数列的前10项:1.1111, 1.7100, 0.9268,2.2433, 0.6445,3.9590, 0.3164, 13.1504, 0.0818, 161.5755 可见此迭代格式是不收敛的.迭代格式3 方程变形为112-=x x ,用for 语句,初值设为1.5,相应的MATLAB 代码为： >>clear; >>x=1.5; >>for i=1:10 >>x=1/(x^2-1)>>end可算得迭代数列的前10项:0.8000, -2.7778, 0.1489, -1.0227, 21.8055, 0.0021, -1.0000, 1.1256e+005, 7.8922e-011, -1 可见此迭代格式也是不收敛的.这个例子表明,迭代格式是否收敛的关键是迭代函数的选取.迭代函数选取恰当,迭代过程会迅速地收敛到不动点,否则,若迭代函数选择不当,收敛速度可能很慢,甚至导致迭代发散.练习3利用压缩映像原理考察迭代格式 ,3,2,1,2,010=+==+n x x x n n 的收敛性.此迭代格式相应的迭代函数为x x g +=2)(,首先画出函数)(,x g y x y ==的图形, 相应的MA TLAB 代码为：>>clear; >>x=0:0.1:4;>>y1=x; y2=(2+x).^0.5; >>plot(x,y1,x,y2)相应的图形为图16.1 迭代函数的图形从图形中可以看出,迭代函数x x g +=2)(在区间]4,0[,满足定理2的条件,故迭代数列必定收敛到唯一的不动点.且在区间]4,0[内(甚至在更大范围内)与处置的选择无关.请加以验证.如果用while 语句,取迭代精度为510-,当初值为1时, 相应的MATLAB 代码为：>>n=0; eps=1.0e-5; x=1.0; >>while abs(x-(x+2)^(1/2))>eps >>x=(x+2)^(1/2); n=n+1;>>end >>x, n计算结果为x=2.0000, n=9,说明只需进行9次迭代,就可达到所要求的精度.练习4（一种计算平方根的迭代算法）验证不动点方程)2(21xx x +=的不动点是2。
第3章线性方程组的解法本章探讨大型线性方程组运算机求解的经常使用数值方式的构造和原理，要紧介绍在运算机上有效快速地求解线性方程组的有关知识和方式.重点论述Jacobi迭代法、Seidel迭代法、Guass消元法及LU分解法的原理、构造、收敛性等内容。
实际案例问题的描述与大体概念解线性方程组问题在线性代数中已有很优美的行列式解法，但对大型的线性方程组（阶数n>40）的求解问题利用价值并非大，因为其计算量太大。
实际问题中常常碰到自变量个数n都专门大的线性方程组求解问题，这些线性方程组要借助运算机的帮忙才能求出解。
n 个变元12,,,n x x x ⋯的线性方程组的一样形式为11112211211222221122n n n n m m mn n ma x a x a xb a x a x a x b a x a x a x b +++=⎧⎪+++=⎪⎨⎪⎪+++=⎩ （）式中，a ij 称为系数，b i 称为右端项，它们都是已知的常数。
若是有***1122,,,n nx x x x x x ===使方程组（）成立，那么称值***12,,,nx x x为线性方程组的（）的一组解。
本章在不作专门说明的情形下，要紧讨论m=n 的线性方程组11112211211222221122n n n n n n nn n na x a x a xb a x a x a x b a x a x a x b +++=⎧⎪+++=⎪⎨⎪⎪+++=⎩的求解问题，且假设它有唯一解。
线性方程组的矩阵表示Ax b =式中A称为系数矩阵，b称为右端项。
数值分析中，线性方程组的数值解法要紧分为直接法和迭代法两大类。
直接法是用有限次计算就能够求出线性方程组“准确解”的方式（不考虑舍入误差）；迭代法是由线性方程组构造出迭代计算公式，然后以一个猜想的向量作为迭代计算的初始向量慢慢迭代计算，来取得知足精度要求的近似解。
迭代法是一种逐次逼近的方式。
