实验二迭代法初始值与收敛性 (3)

实验二：迭代法、初始值与收敛性一：实验要求考虑一个简单的代数方程210,x x --=针对上述方程，可以构造多种迭代法，如211111,1,1n n n n n nx x x x x x +++=-=+=+等。

在实轴上取初值，分别用以上迭代做实验，记录各算法的迭代过程。

二：实验要求及实验结果（1） 取定某个初始值，按如上迭代格式进行计算，它们的收敛性如何？重复选取不同放入初始值，反复实验。

请读者自行设计一种比较形象的记录方式（如何利用Matlab 的图形功能），分析三种迭代法的收敛性与初值的选取关系。

（2） 对三个迭代法中的某一个，取不同的初值进行迭代，结果如何？试分析对不同的初值是否有差异？实验内容：ⅰ）对211n n x x +=-进行迭代运算，选取迭代次数n=20；分别选择初值-0.6， 1.6进行实验，并画出迭代结果的趋势图。

编写MATLAB 运算程序如下：%迭代法求解 %令x=x^2-1 clearn=30; x=-0.5;x1=x^2-1; for i=1:nx1=x1^2-1;xx(i)=x1;endm=linspace(0,29,n);plot(m,xx) title('x=-0.5')2468101214161820-1-0.9-0.8-0.7-0.6-0.5-0.4-0.3-0.2-0.10x=-0.602468101214161820-1-0.500.511.5x=1.6如上图所示，选取初值分别为-0.6、1.6时，结果都是不收敛的。

分析：2()1n g x x =-，'()2g x x =，要想在某一邻域上'()21,[1,1]g x x x =<∀∈-则但是()[1,1]g x ∉-，所以不存在某个邻域使得该迭代公式收敛。

即迭代公式对任何初值都是发散的。

ⅱ）对111n nx x +=+进行迭代运算，选取迭代次数n=30；分别选择初值=-0.7， 2.1进行实验，并画出迭代结果的趋势图。

数学实验题目4 Newton 迭代法摘要0x 为初始猜测，则由递推关系产生逼近解*x 的迭代序列{}k x ，这个递推公式就是Newton 法。

当0x 距*x 较近时，{}k x 很快收敛于*x 。

但当0x 选择不当时，会导致{}k x 发散。

故我们事先规定迭代的最多次数。

若超过这个次数，还不收敛，则停止迭代另选初值。

前言利用牛顿迭代法求的根程序设计流程问题1（1 程序运行如下：r = NewtSolveOne('fun1_1',pi/4,1e-6,1e-4,10) r = 0.7391（2 程序运行如下：r = NewtSolveOne('fun1_2',0.6,1e-6,1e-4,10) r = 0.5885问题2（1 程序运行如下：否 是否是是定义()f x输入012,,,x N εε开 始1k =01()f x ε<0100()()f x x x f x =-'102||x x ε-<k N =输出迭代失败标志输出1x输出奇 异标志结 束01x x = 1k k =+ 否r = NewtSolveOne('fun2_1',0.5,1e-6,1e-4,10)r = 0.5671（2）程序运行如下：r = NewtSolveOne('fun2_2',0.5,1e-6,1e-4,20)r = 0.5669问题3（1）程序运行如下：①p = LegendreIter(2)p = 1.0000 0 -0.3333p = LegendreIter(3)p = 1.0000 0 -0.6000 0p = LegendreIter(4)p =1.0000 0 -0.8571 0 0.0857p = LegendreIter(5)p = 1.0000 0 -1.1111 0 0.2381 0②p = LegendreIter(6)p = 1.0000 0 -1.3636 0 0.4545 0 -0.0216r = roots(p)'r= -0.932469514203150 -0.6612 0.9324695142031530.6612 -0.238619186083197 0.238619186083197用二分法求根为：r = BinSolve('LegendreP6',-1,1,1e-6)r = -0.932470204878826 -0.661212531887755 -0.2386200573979590.2386 0.661192602040816 0.932467713647959（2）程序运行如下：①p = ChebyshevIter(2)p = 1.0000 0 -0.5000p = ChebyshevIter(3)p = 1.0000 0 -0.7500 0p = ChebyshevIter(4)p = 1.0000 0 -1.0000 0 0.1250p = ChebyshevIter(5)p = 1.0000 0 -1.2500 0 0.3125 0②p = ChebyshevIter(6)p = 1.0000 0 -1.5000 0 0.5625 0 -0.0313r = roots(p)'r = -0.965925826289067 -0.7548 0.9659258262890680.7547 -0.258819045102521 0.258819045102521用二分法求根为：r = BinSolve('ChebyshevT6',-1,1,1e-6)r = -0.965929926658163 -0.7755 -0.2588289221938780.2588 0.7020 0.965924944196429与下列代码结果基本一致，只是元素顺序稍有不同：j = 0:5;x = cos((2*j+1)*pi/2/(5+1))x =0.965925826289068 0.7548 0.258819045102521-0.258819045102521 -0.7547 -0.965925826289068（3）程序运行如下：①p = LaguerreIter(2)p = 1 -4 2p = LaguerreIter(3)p = 1 -9 18 -6p = LaguerreIter(4)p = 1 -16 72 -96 24p = LaguerreIter(5)p =1.0000 -25.0000 200.0000 -600.0000 600.0000 -120.000②p = LaguerreIter(5)p =1.0000 -25.0000 200.0000 -600.0000 600.0000 -120.000r = roots(p)'r =12.6432 7.8891 3.5964257710407111.4520 0.263560319718141用二分法求根为：r = BinSolve('LaguerreL5',0,13,1e-6)r = 0.263560314567722 1.4789 3.5964257656311507.0720 12.6490（4）程序运行如下：①p = HermiteIter(2)p = 1.0000 0 -0.5000p = HermiteIter(3)p = 1.0000 0 -1.5000 0p = HermiteIter(4)p = 1.0000 0 -3.0000 0 0.7500p = HermiteIter(5)p = 1.0000 0 -5.0000 0 3.7500 0②p = HermiteIter(6)p = 1.0000 0 -7.5000 0 11.2500 0 -1.8750r = roots(p)'r =-2.3587 2.3588 -1.3358490740136961.335849074013698 -0.4367 0.4366用二分法求根为：r = BinSolve('HermiteH6',-3,3,1e-6)r =-2.3516 -1.335849********* -0.43630.4366 1.335848983453244 2.3504所用到的函数function r = NewtSolveOne(fun, x0, ftol, dftol, maxit)% NewtSolveOne 用Newton法解方程f(x)=0在x0附近的一个根%% Synopsis: r = NewtSolveOne(fun, x0)% r = NewtSolveOne(fun, x0, ftol, dftol)%% Input: fun = (string) 需要求根的函数及其导数% x0 = 猜测根，Newton法迭代初始值% ftol = (optional)误差，默认为5e-9% dftol = (optional)导数容忍最小值，小于它表明Newton法失败，默认为5e-9 % maxit = (optional)迭代次数，默认为25%% Output: r = 在寻根区间内的根或奇点if nargin < 3ftol = 5e-9;endif nargin < 4dftol = 5e-9;endif nargin < 5maxit = 25;endx = x0; %设置初始迭代位置为x0k = 0; %初始化迭代次数为0while k <= maxitk = k + 1;[f,dfdx] = feval(fun,x); %fun返回f(x)和f'(x)的值if abs(dfdx) < dftol %如果导数小于dftol，Newton法失败，返回空值r = [];warning('dfdx is too small!');return;enddx = f/dfdx; %x(n+1) = x(n) - f( x(n) )/f'( x(n) )，这里设dx = f( x(n) )/f'( x(n) )x = x - dx;if abs(f) < ftol %如果误差小于ftol，返回当前x为根r = x;return;endendr = []; %如果牛顿法未收敛，返回空值function p = LegendreIter(n)% LegendreIter 用递推的方法计算n次勒让德多项式的系数向量Pn+2(x) = (2*i+3)/(i+2) * x*Pn+1(x) - (i+1)/(i+2) * Pn(x)%% Synopsis: p = LegendreIter(n)%% Input: n = 勒让德多项式的次数%% Output: p = n次勒让德多项式的系数向量if round(n) ~= n | n < 0error('n必须是一个非负整数');endif n == 0 %P0(x) = 1p = 1;return;elseif n == 1 %P1(x) = xp = [1 0];return;endpBk = 1; %初始化三项递推公式后项为P0pMid = [1 0]; %初始化三项递推公式中项为P1for i = 0:n-2pMidCal = zeros(1,i+3); %构造用于计算的x*Pn+1pMidCal(1:i+2) = pMid;pBkCal = zeros(1,i+3); %构造用于计算的PnpBkCal(3:i+3) = pBk;pFwd = (2*i+3)/(i+2) * pMidCal - (i+1)/(i+2) * pBkCal; %勒让德多项式三项递推公式Pn+2(x) = (2*i+3)/(i+2) * x*Pn+1(x) - (i+1)/(i+2) * Pn(x)pBk = pMid; %把中项变为后项进行下次迭代pMid = pFwd; %把前项变为中项进行下次迭代endp = pFwd/pFwd(1); %把勒让德多项式最高次项系数归一化function p = ChebyshevIter(n)% ChebyshevIter 用递推的方法计算n次勒让德-切比雪夫多项式的系数向量Tn+2(x) = 2*x*Tn+1(x) - Tn(x)%% Synopsis: p = ChebyshevIter(n)%% Input: n = 勒让德-切比雪夫多项式的次数%% Output: p = n次勒让德-切比雪夫多项式的系数向量if round(n) ~= n | n < 0error('n必须是一个非负整数');endif n == 0 %T0(x) = 1p = 1;return;elseif n == 1 %T1(x) = xp = [1 0];return;endpBk = 1; %初始化三项递推公式后项为T0pMid = [1 0]; %初始化三项递推公式中项为T1for i = 0:n-2pMidCal = zeros(1,i+3); %构造用于计算的x*Tn+1pMidCal(1:i+2) = pMid;pBkCal = zeros(1,i+3); %构造用于计算的PnpBkCal(3:i+3) = pBk;pFwd = 2*pMidCal - pBkCal; %勒让德-切比雪夫多项式三项递推公式Tn+2(x) = 2*x*Tn+1(x) - Tn(x)pBk = pMid; %把中项变为后项进行下次迭代pMid = pFwd; %把前项变为中项进行下次迭代endp = pFwd/pFwd(1); %把勒让德-切比雪夫多项式最高次项系数归一化function p = LaguerreIter(n)% LaguerreIter 用递推的方法计算n次拉盖尔多项式的系数向量Ln+2(x) = (2*n+3-x)*Ln+1(x) - (n+1)*Ln(x)%% Synopsis: p = LaguerreIter(n)%% Input: n = 拉盖尔多项式的次数%% Output: p = n次拉盖尔多项式的系数向量if round(n) ~= n | n < 0error('n必须是一个非负整数');endif n == 0 %L0(x) = 1p = 1;return;elseif n == 1 %L1(x) = -x+1p = [-1 1];return;endpBk = 1; %初始化三项递推公式后项为L0pMid = [-1 1]; %初始化三项递推公式中项为L1for i = 0:n-2pMidCal1 = zeros(1,i+3); %构造用于计算的x*Ln+1(x)pMidCal1(1:i+2) = pMid;pMidCal2 = zeros(1,i+3); %构造用于计算的Ln+1(x)pMidCal2(2:i+3) = pMid;pBkCal = zeros(1,i+3); %构造用于计算的Ln(x)pBkCal(3:i+3) = pBk;pFwd =( (2*i+3)*pMidCal2 - pMidCal1 - (i+1)*pBkCal )/ (i+2); %拉盖尔多项式三项递推公式Ln+2(x) = (2*n+3-x)*Ln+1(x) - (n+1)^2*Ln(x)pBk = pMid; %把中项变为后项进行下次迭代pMid = pFwd; %把前项变为中项进行下次迭代endp = pFwd/pFwd(1); %把拉盖尔多项式最高次项系数归一化function p = HermiteIter(n)% HermiteIter 用递推的方法计算n次埃尔米特多项式的系数向量Hn+2(x) = 2*x*Hn+1(x) - 2*(n+1)*Hn(x)%% Synopsis: p = HermiteIter(n)%% Input: n = 埃尔米特多项式的次数%% Output: p = n次埃尔米特多项式的系数向量if round(n) ~= n | n < 0error('n必须是一个非负整数');endif n == 0 %H0(x) = 1p = 1;return;elseif n == 1 %H1(x) = 2*xp = [2 0];return;endpBk = 1; %初始化三项递推公式后项为L0pMid = [2 0]; %初始化三项递推公式中项为L1for i = 0:n-2pMidCal = zeros(1,i+3); %构造用于计算的x*Hn+1(x)pMidCal(1:i+2) = pMid;pBkCal = zeros(1,i+3); %构造用于计算的Hn(x)pBkCal(3:i+3) = pBk;pFwd =2*pMidCal - 2*(i+1)*pBkCal; %埃尔米特多项式三项递推公式Hn+2(x) = 2*x*Hn+1(x) - 2*(n+1)*Hn(x)pBk = pMid; %把中项变为后项进行下次迭代pMid = pFwd; %把前项变为中项进行下次迭代endp = pFwd/pFwd(1); %把拉盖尔多项式最高次项系数归一化function r = BinSolve(fun, a, b, tol)% BinSolve 用二分法解方程f(x)=0在区间[a,b]的根%% Synopsis: r = BinSolve(fun, a, b)% r = BinSolve(fun, a, b, tol)%% Input: fun = (string) 需要求根的函数% a,b = 寻根区间上下限% tol = (optional)误差，默认为5e-9%% Output: r = 在寻根区间内的根if nargin < 4tol = 5e-9;endXb = RootBracket(fun, a, b); %粗略寻找含根区间[m,n] = size(Xb);r = [];nr = 1; %初始化找到的根的个数为1maxit = 50; %最大二分迭代次数为50for i = 1:ma = Xb(i,1); %初始化第i个寻根区间下限b = Xb(i,2); %初始化第i个寻根区间上限err = 1; %初始化误差k = 0;while k < maxitfa = feval(fun, a); %计算下限函数值fb = feval(fun, b); %计算上限函数值m = (a+b)/2;fm = feval(fun, m);err = abs(fm);if sign(fm) == sign(fb) %若中点处与右端点函数值同号，右端点赋值为中点b = m;else %若中点处与左端点函数值同号或为0，左端点赋值为中点a = m;endif err < tol %如果在a处函数值小于tolr(nr) = a; %一般奇点不符合该条件，这样可以去除奇点nr = nr + 1; %找到根的个数递增k = maxit; %改变k值跳出循环endk = k + 1; %二分迭代次数递增endendfunction X = powerX(x,a,b)% powerX 对给定向量(x1, x2,..., xn)返回增幂矩阵(x1^a, x2^a,..., xn^a; x1^a+1, x2^a+1,..., xn^a+1; ...; x1^b, x2^b,..., xn^b;)%% Synopsis: X = powerX(x,a,b)%% Input: x = 需要返回增幂矩阵的向量% a,b = 寻根区间上下限%% Output: X = 增幂矩阵(x1^a, x2^a,..., xn^a; x1^a+1, x2^a+1,..., xn^a+1; ...; x1^b, x2^b,..., xn^b;)if round(a) ~= a | round(b) ~= berror('a,b must be integers');elseif a >= berror('a must be smaller than b!');endx = x(:)';row = b-a+1;col = length(x);X = zeros(row, col);for i = b:-1:aX(b-i+1,:) = x.^i;Endfunction [f, dfdx] = fun1_1(x)f = cos(x) - x;dfdx = -sin(x) - 1;function [f, dfdx] = fun1_2(x)f = exp(-x) - sin(x);dfdx = -exp(-x) - cos(x);function [f, dfdx] = fun2_1(x)f = x - exp(-x);dfdx = 1 + exp(-x);function [f, dfdx] = fun2_2(x)f = x.^2 - 2*x*exp(-x) + exp(-2*x);dfdx = 2*x - 2*exp(-x) + 2*x*exp(-x) - 2*exp(-2*x);function y = LegendreP6(x)p = LegendreIter(6);X = powerX(x,0,6);y = p*X;function y = ChebyshevT6(x)p = ChebyshevIter(6);X = powerX(x,0,6);y = p*X;function y = LaguerreL5(x)p = LaguerreIter(5);X = powerX(x,0,5);y = p*X;function y = HermiteH6(x)p = HermiteIter(6);X = powerX(x,0,6);y = p*X;思考题（1）由于Newton法具有局部收敛性，所以在实际问题中，当实际问题本身能提供接近于根的初始近似值时，就可保证迭代序列收敛，但当初值难以确定时，迭代序列就不一定收敛。

迭代函数对收敛性的影响一、实验目的：初步了解非线性方程的简单迭代法及其收敛性，体会迭代函数对收敛性的影响，知道当迭代函数满足什么条件时，迭代法收敛。

、实验内容：用简单迭代法求方程f(x) =2x3 _x _1 = 0的根。

方案一：化f (x)二2x3 - x -1 = 0为等价方程X = 3"0^ △0(x)\ 2 =万案二：化f (x) = 2x —x—^^=0为等价方程x 二2x3」(x) 、实验要求：(1)分别对方案一、方案二取初值X。

=0，迭代10次，观察其计算值，并加以分析。

(2)用MATLAB^部函数solve直接求出方程的所有根，并与(1)的结果进行比较。

四、迭代法程序fun ctio n[k,pia ncha,xdpia ncha,xk]=diedai(x0,k)x(1)=x0;for i=1:kx(i+1)=fu n1(x(i));pia ncha=abs(x(i+1)-x(i));xdpia ncha=pia ncha/(abs(x(i+1))+eps);i=i+1;xk=x(i);[(i-1) pia ncha xdpia ncha xk]endif (pia ncha>1)&( xdpia ncha>0.5)&(k>3)disp('此迭代序列发散，请重新输入新的迭代公式')return;endif (pia ncha<0.001)&( xdpia ncha<0.0000005)&(k>3)disp('此迭代序列收敛，且收敛速度较快')return;endp=[(i-1) pia ncha xdpia ncha xk]'五、实验结果:方案一:3化f(x)=2x-X-1 = 0为等价方程xfjx)建立M文件fun 1.m的文件function y1=fu n1(x)y1= ((x+1) ./2 ) 9(1/3)在MATLAB窗口输入程序>> [k,pia ncha,xdpia ncha,xk]=diedai(0,10)运行后输出结果y1 =0.7937ans =1.0000 0.7937 y1 =0.9644ans =2.0000 0.1707 y1 = 0.9940ans =3.0000 0.0297 y1 =0.9990ans =4.0000 0.0050 y1 = 0.9998ans =5.0000 0.0008 y1 =1.0000ans =6.0000 0.0001 y1 = 1.0000ans =7.0000 0.0000 y1 = 1.0000ans =8.0000 0.0000 y1 =1.0000ans =9.0000 0.0000 y1 =1.0000ans =10.0000 1.0000 0.7937 0.1770 0.9644 0.0298 0.9940 0.0050 0.9990 0.0008 0.9998 0.0001 1.0000 0.0000 1.0000 0.0000 1.0000 0.0000 1.00000.0000 0.0000 1.0000此迭代序列收敛，且收敛速度较快k =10 pia ncha = 1.0685e-07 xdpia ncha =1.0685e-07 xk =1.000033x = 2x -仁〕(x)2、方案二： 化f (x) = 2x …X - 1 = 0为等价方程 (1)建立 M 文件fun,m 的文件function y 仁fu n1(x) y1=2.*(x93)-1(2 )在MATLAB 窗口输入程序>> [k,pia ncha,xdpia ncha,xk]=diedai(0,10) (3 )运行后输出结果 y1 =-1y1 =-3y1 =-55y1 =-332751 ans =1.0e+05 *y1 =-I nfans =8 Inf NaN -Infy1 =-I nf ans =9 NaN NaN -Inf y1 =-I nf ans =10 NaN NaN -Inf p = 10 NaN NaN -I nfk = 10 pia ncha =NaN xdpia ncha = NaN xk =-I nf0.0000 3.3270 y1 =-7.3687e+16 ans =1.0e+16 * 0.0000 7.3687 y1 =-8.0019e+50 ans =1.0e+50 * 0.0000 8.0019 y1 =-1.0247e+153 ans =1.0e+153 * 0.0000 1.0247 0.0000 -3.32750.0000 -7.36870.0000 -8.00190.0000 -1.0247ans =1.0000 1.0000 1.0000 -1.0000ans =2.0000 2.00000.6667 -3.0000ans =3.0000 52.00000.9455 -55.00003、用MATLAB^部函数solve直接求(1 )输入程序>> x=solve('2.*(x.A3)-x-1=0')运行后输出的结果x =1.-.50000000000000000000000000000000+.50000000000000000000000000000000*i-.50000000000000000000000000000000-.50000000000000000000000000000000*i从表1可以看出，方案一收敛很快，偏差和偏差的相对误差几乎为零；方案二根本不收敛，它的偏差piancha已经NaN且相对误差xdwucha的知也已经NaN由此可见，迭代序列的敛散性与迭代公式有关，也与相邻两次迭代的偏差和偏差的相对误差有关，他们的值越小,迭代序列的收敛速度越快。

实验报告一一、实验目的理解线性方程组直接法与迭代法思想，掌握常用算法的设计，掌握用MATLAB 实现的数值解法。

二、实验题目实验一 线性方程组迭代法实验 1、 迭代法的收敛速度用迭代法分别对n=20,n=200解方程组,b Ax =其中nn A ⨯⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛------------------=431513143151513143151513143151513143151314（1） 选取不同的初值0x 和不同的右端向量b,给定迭代误差，用两种迭代法计算，观测得到的迭代向量并分析计算结果给出结论；（2） 取定初值0x 和右端向量b,给定迭代误差，将A 的主对角元成倍放大，其余元素不变，用Jacobi 迭代法计算多次，比较收敛速度，分析计算结果并给出结论。

2、 SOR 迭代法松弛因子的选取用逐次超松弛（SOR ）迭代法求解方程组,b Ax =其中 .5555551221212211212212121221121221212200199198321⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛----------=x x x x x x A （1） 给定迭代误差，选取不同的超松弛因子1>ω进行计算，观测得到的近似值向量并分析计算结果，给出你的结论；（2） 给定迭代误差，选取不同的低松弛因子1<ω进行计算，观测得到的近似值向量并分析计算结果，给出你的结论。

三、实验原理Jacobi 迭代法算法：步1 取初始点()0x ，精度要求ε，最大迭代次数N ，置0:=k ；步 2 由()n i x a b a x ni j j j ij i ii k i,,1,1,11 =⎪⎪⎭⎫⎝⎛-=∑≠=+ 或()b D x A D D x k 111)(--++-= 计算()1+k x ； 步3 若()()ε≤-∞+k k xx1，则停算，输出()1+k x作为方程组的近似解； 步4 若N k =，则停算，输出迭代失败信息；否则置1+=k k ，转布2。