第二章 迭代法得一般原理
- 格式:doc
- 大小:22.50 KB
- 文档页数:3
迭代法的基本原理
迭代法的基本原理:
①通过反复逼近方式逐步缩小解与当前估计值之间差距直至满足精度要求;
②数值分析中解决非线性方程组优化问题等领域广泛应用此类算法框架;
③简单固定点迭代情形下构造收缩映射使得序列极限收敛于根所在位置;
④Newton-Raphson方法利用函数及其导数信息构建二次逼近快速找到解;
⑤求解线性系统时Jacobi Gauss-Seidel SOR等迭代格式根据矩阵特性选取;
⑥每次迭代更新未知数估计值直至相邻两次结果差异小于预设阈值停止;
⑦实践中需关注收敛速度稳定性以及如何选择初始猜测值影响最终效果;
⑧例子如求平方根时令x(n+1) = (x(n) + a / x(n)) / 2迭代直至收敛;
⑨迭代次数过多可能导致数值不稳定需引入松弛因子加速收敛抑制振荡;
⑩现代算法设计中常结合预处理技术改进条件数提升迭代法整体性能;
⑪并行计算环境下研究分布式迭代机制成为当前研究热点之一;
⑫随着应用领域拓展迭代法理论与实践将继续深化发展。
第二章 迭代法的一般原理非线性方程组无论从理论上还是计算方法上,都比线性方程组复杂得多。
一般的非线性方程组很难求出解析解,往往只能求出其数值解,且往往只能借助于迭代法。
本章我们将讨论迭代法的一般原理、迭代法的一般构造及迭代收敛速度的衡量标准。
2-1 迭代法与不动点定理设n n R R D →⊂:f ,考虑方程()0=x f (2-1)若存在D *∈x ,使()0=*x f ,则称*x 为方程(2-1) 的解。
用迭代法求解(2-1) ,先将(2-1)化为等价的方程()x g x = (2-2)这里映象n n R R D →⊂:g 。
方程(2-2)的解*x (即()**x g x =)称为映象g 的不动点。
因此用迭代法解方程(2-1),就是求(2-2)中映象g 的不动点。
这样以及g 是否存在不动点自然就是我们关心的问题。
定理2-1 若n n R R D →⊂:g 为有界闭集D D ⊂0上的严格非膨胀映象,()00D D ⊂g ,则g 在0D 内有唯一不动点。
证 唯一性 设g 在0D 内至少有两个不动点1x ,2x ,则()()2121x x x g x g x x 21-≤-=-α 因1<α,所以由上式推得21x x =。
唯一性得证。
记()()x g x x -=ϕ,由g 及泛数的连续性可知1:R R D n →⊂ϕ连续。
因0D 为有界闭集,故ϕ在0D 上有最小值。
设0D *∈x 为最小点,即()()x g x x -=∈min 0D x *ϕ则*x 为g 的不动点。
因为若不然,则有()**x g x ≠,再由g 严格非膨胀,可得()()()()()***x g g x g x g -=ϕ()()***x x g x ϕ=-<这与*x 为ϕ的最小点相矛盾,故*x 为g 的不动点。
注 定理中0D 的有界闭性、g 的压缩性和g 映0D 入自身,此3个条件缺一不可。
例如,()xx x g 1+=在[)+∞=,D 10上严格非膨胀,但它在0D 中却没有不动点。
迭代法的应用迭代法,又称递归法或回代法,是一种数学计算方法,通过逐步逼近的方式寻找方程的解。
迭代法广泛应用于各个领域,包括数学、计算机科学、物理学和工程学等等。
本文将介绍迭代法的基本原理,并探讨其在不同领域中的应用。
一、迭代法的基本原理迭代法的基本原理是通过逐步逼近的方式解决问题。
具体而言,迭代法使用一个初始值作为起点,然后通过一定的计算规则不断更新这个值,直到满足特定的条件为止。
这个过程可以理解为在数轴上不断靠近目标点的过程。
迭代法的核心在于不断重复更新值的操作,直到找到满足精度要求的解。
二、迭代法在数学中的应用1. 方程求解:迭代法广泛应用于方程求解中。
例如,使用牛顿迭代法可以求解非线性方程,通过不断迭代计算,逐步逼近方程的解。
迭代法不仅可以解决简单的方程,还可以应用于更复杂的方程组,如线性方程组和常微分方程等。
2. 数值积分:在数值方法中,迭代法也经常用于数值积分的计算。
通过将积分区间划分为多个小区间,利用迭代法逼近每个小区间的积分值,最后将这些积分值相加得到整个区间的积分近似值。
这种方法可以提高计算的精度和效率。
三、迭代法在计算机科学中的应用1. 数值优化:在计算机科学中,迭代法被广泛应用于数值优化问题。
例如,通过不断迭代调整参数的值,可以优化机器学习算法中的模型参数,使得模型在给定数据集上的表现达到最佳。
2. 图像处理:迭代法也可以应用于图像处理领域。
例如,通过不断迭代计算,可以对图像进行降噪、边缘检测和图像增强等操作。
迭代法能够逐步改进图像的质量,提高图像处理的效果。
四、迭代法在物理学和工程学中的应用1. 计算流体力学:在计算流体力学中,迭代法被广泛应用于求解流体动力学方程。
通过将流体域离散成网格,利用迭代法逐步求解每个网格点上的流体状态,可以模拟流体在不同条件下的行为,如风洞实验和飞行器设计等。
2. 结构分析:在工程学中,迭代法也可以用于结构分析和设计中。
通过不断迭代更新结构的参数,可以实现结构的优化和调整。
§2简单迭代法——不动点迭代(iterate)迭代法是数值计算中的一类典型方法,被用于数值计算的各方面中。
一、简单迭代法设方程f(x)=0 (3)在[a,b]区间内有一个根*x ,把(3)式写成一个等价的隐式方程x=g(x) (4)方程的根*x 代入(4)中,则有)(**=x g x (5)称*x 为g的不动点(在映射g下,象保持不变的点),方程求根的问题就转化为求(5)式的不动点的问题。
由于方程(4)是隐式的,无法直接得出它的根。
可采用一种逐步显式化的过程来逐次逼近,即从某个[a,b]内的猜测值0x 出发,将其代入(4)式右端,可求得)(01x g x =再以1x 为猜测值,进一步得到)(12x g x =重复上述过程,用递推关系——简单迭代公式求得序列}{k x 。
如果当k →∞时*→x x k ,}{k x 就是逼近不动点的近似解序列,称为迭代序列。
称(6)式为迭代格式,g(x)为迭代函数,而用迭代格式(6)求得方程不动点的方法,称为简单迭代法,当*∞→=x x k k lim 时,称为迭代收敛。
构造迭代函数g(x)的方法:(1)=x a x x -+2,或更一般地,对某个)(,02a x c x x c -+=≠;(2)x a x /=; (3))(21xa x x +=。
取a=3,0x =2及根*x =1.732051,给出三种情形的数值计算结果见表表 032=-x 的迭代例子问题:如何构造g(x),才能使迭代序列}{k x 一定收敛于不动点?误差怎样估计?通常通过对迭代序列}{k x 的收敛性进行分析,找出g(x)应满足的条件,从而建立一个一般理论,可解决上述问题。
二、迭代法的收敛性设迭代格式为),2,1,0()(1 ==+k x g x k k而且序列}{k x 收敛于不动点*x ,即∞→→-*k x x k (0时)因而有)3,2,1(1 =-≤-*-*k xx x x k k (7)由于),(),)((11*-*-*∈-'=-x x x x g x x k k k ξξ当g(x)满足中值定理条件时有),(),)((11*-*-*∈-'=-x x x x g x x k k k ξξ (8)注意到(8)式中只要1)(<<'L g ξ时,(7)式成立.经过上述分析知道,迭代序列的收敛性与g(x)的构造相关,只要再保证迭代值全落在[a,b]内,便得:假定迭代函数g(x)满足条件(1) 映内性:对任意x ∈[a,b]时,有a ≤g(x) ≤b ;(2) 压缩性:g(x)在[a,b]上可导,且存在正数L<1,使对任意 x ∈[a,b],有L x g <')( (9)则迭代格式)(1k k x g x =+对于任意初值0x ∈[a,b]均收敛于方程x=g(x)的根,并有误差估计式011x x LL x x kk --≤-*(10)证明 :收敛性是显然的。
东南大学-数值分析-第二章-牛顿迭代法第二章非线性方程的解法某某某某(学号)某某某某(姓名)算法与程序题目见教材P56上机题目20。
一、算法原理根据题目的要求,是关于用牛顿迭代法法求解方程f(某)0的通用算法。
该法是一种通过斜率迭代的算法,其速度比二分法和简单迭代法都要快。
其简单原理如下:设fC2[a,b],且存在数p[a,b],满足f(p)0。
如果f(p)0,则存在一个数0,对任意初始值p0[p,p],使得由如下定义的迭代序列{pk}k0收敛到p:pkg(pk1)pk1f(pk1),其中k1,2,f(pk1)(1)对于函数f(某)某3/3某=0,则其递推规则是32pkpk21,其中k1,2,3pk1-3(2)定义序列{pk}则序列{pk}也可表示为limpk某现简要证明:k0,k0收敛到某,某对于f(某)某3/3某,得f'(某)某2-1,写出牛顿迭代公式f(某)某3/3某g(某)某某2f(某)某-1(3)该公式可化简为2某3g(某)23某3(4)二、流程图题目要求于用牛顿迭代法法求解方程f(某)0的通用算法。
其计算过程主要第二章非线性方程的解法用到迭代g(某)某f(某),图流程图1所示。
f(某)输入各参数k=1迭代pkg(pk1)pk1f(pk1),其中k1,2,f(pk1)Tbreak计算各误差误差在允许范围之内Fk=k+1k三、计算代码核心代码1)p1=……;2)if(err程序1:Newton.m%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Decription:牛顿迭代法%Author:panyunqiang%Veroin:1.0%Date:2022-9-21%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%f unction[p0,err,k,y]=Newton(p0,delta,epilon,ma某N)%input-p0itheinitialappro某imationtoazerooff%-deltaithetoleranceforp0%-epilonithetoleranceforthefunctionvaluey%-ma某Nithema某iumnumberofiteration%output-p0itheNewtonappro某imationtoazero%-erritheerroretimateforp0东南大学《数值分析》上机练习——算法与程序设计实验报告%-kithenumberofiteration%-yithefunctionvaluef(p0)fork=1:ma 某N%%递归p1=2某p0^3/(3某p0^2-3);%%计算误差err=ab(p1-p0);relerr=2某err/(ab(p1)+delta);p0=p1;%%当前求出的根的函数值y=p0^3/3-p0;%%判断if(err程序2:Newton_Step.m%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Decription:寻找题目中关于牛顿迭代法收敛的尽可能大的delta%搜索步进为tep=10^(-6),即精确到小数点后六位%Author:panyunqiang%Veroin:1.0%Date:2022-9-21%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %formatlongtep=10^(-6);delta=10^-8;epilon=10^-8;ma某N=1000;p=0.6;[p0,err,k,y]=Newton(p,delta,epilon,ma某N);while((ab(p0)<=epilon)&(p0~=NaN))p=p+tep;[p0,err,k,y]=Newton(p,delta,epilon,ma某N);endp-tep四、计算结果及分析a)运行程序Newton_Step.m,获得Newton局部收敛于某2=0的初始值的范围=0.774596,六位有效数字。
第二章迭代法的一般原理知识分享迭代法是一种解决问题的常用方法,其基本原理是将问题分解为一系列子问题,并通过逐步逼近的方式逐步求解,直到达到预期的解决方案。
迭代法通常由以下几个步骤组成:初始化、迭代、判断停止条件、更新和输出结果。
迭代法的一般原理可以总结为以下几点:1.初始化:迭代法通常需要一个初始解,该解可能是问题的近似解或一个具有特定条件的解。
这个初始解将作为迭代的起点,进而逐步逼近最终的解。
2.迭代:在每一次迭代中,通过使用前一次迭代的结果作为输入来计算下一次迭代的结果。
迭代过程可以使用数学公式、算法或其他适当的方法来进行计算。
3.判断停止条件:在每一次迭代中,需要判断是否满足停止条件。
停止条件通常与所求解的问题有关,可以根据预先设定的要求来判断是否已经达到了足够的精度或满足了特定的条件。
4.更新:根据迭代的结果,需要更新迭代变量的值。
这个更新可以是简单的赋值操作,也可以是需要进行复杂计算或使用迭代公式来进行计算。
5.输出结果:当满足停止条件时,迭代过程结束,并输出最终的解。
这个解可能是问题的数值解、近似解或其他形式的解决方案。
迭代法的优点在于它可以通过逐步逼近的方式不断提高解的精度,不需要一次性找到完美的解决方案。
这使得迭代法在处理复杂问题时非常有用,因为往往很难找到问题的精确解。
迭代法的应用非常广泛,可以用于解决数值计算、优化问题、图像处理、机器学习等领域的问题。
例如,在求解非线性方程时,可以使用牛顿迭代法来逼近方程的根;在求解线性方程组时,可以使用雅可比迭代法或高斯-赛德尔迭代法来逼近方程的解。
需要注意的是,迭代法并不是万能的,不是所有问题都适合使用迭代法来解决。
在选择是否使用迭代法时,需要考虑问题的特性和求解方法的适用性。
总结起来,迭代法是一种通过逐步逼近的方式来解决问题的方法。
它的基本原理是通过初始化、迭代、判断停止条件、更新和输出结果等步骤来逼近最终的解决方案。
迭代法广泛应用于各个领域,是解决复杂问题的常用手段之一。
迭代法求解方程:原理与步骤详解迭代法,又称为辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。
迭代法又分为精确迭代和近似迭代。
迭代法求解方程的原理是基于数学中的逼近理论,通过构造一个序列,使得该序列的极限值就是方程的解。
这种方法通常用于求解非线性方程或者方程组,因为这些方程可能难以通过直接求解的方式得到解析解。
迭代法求解方程的基本步骤:1.选择迭代函数:根据待求解的方程,选择一个合适的迭代函数。
这个迭代函数通常是通过对方程进行某种变换得到的。
2.确定迭代初值:为迭代过程选择一个初始值,这个初始值可以是任意的,但不同的初始值可能会影响到迭代的收敛速度和稳定性。
3.进行迭代计算:使用迭代函数和初始值,计算得到序列的第一个值。
然后,用这个值作为下一次迭代的输入,继续计算得到序列的下一个值。
如此反复进行,直到满足某个停止条件(如达到预设的迭代次数,或者相邻两次迭代结果的差值小于某个很小的阈值)。
4.判断解的有效性:如果迭代过程收敛,即序列的极限值存在且唯一,那么这个极限值就是方程的解。
否则,如果迭代过程发散,或者收敛到非唯一解,那么这种方法就失败了。
迭代法的收敛性:迭代法的关键问题是判断迭代过程是否收敛,即序列的极限值是否存在且唯一。
这通常取决于迭代函数的选择和初始值的设定。
对于某些迭代函数,无论初始值如何,迭代过程都会收敛到同一个值;而对于其他迭代函数,迭代过程可能会发散,或者收敛到多个不同的值。
迭代法的优缺点:优点:◆迭代法适用于求解难以直接求解的方程或方程组。
◆迭代法通常比直接法更容易编程实现。
◆在某些情况下,迭代法可能比直接法更快。
缺点:◆迭代法可能不收敛,或者收敛速度很慢。
◆迭代法的收敛性通常需要额外的数学分析或实验验证。
◆对于某些方程,可能需要尝试不同的迭代函数和初始值,才能找到有效的解决方案。
常见的迭代法:◆雅可比迭代法:用于求解线性方程组的一种方法,通过不断更新方程组的近似解来逼近真实解。
迭代法在数值计算中的应用迭代法是一种通过逐步逼近的方式求解数值计算问题的方法。
它在数学、物理、计算机科学等领域有广泛的应用。
本文将从理论和实际应用角度探讨迭代法在数值计算中的应用。
一、迭代法的原理迭代法是一种基于逐步逼近的思想,通过不断重复相同的计算过程,直到满足预设的停止条件为止。
迭代法的基本原理可以总结为以下几个步骤:1. 初始化:设定初始解,并给定迭代次数的上限。
2. 迭代过程:通过一定的迭代公式对当前解进行计算,得到下一次迭代的解。
3. 判断停止条件:根据预设的停止条件进行判断,如果满足条件则停止迭代,否则返回第二步。
4. 输出结果:将迭代得到的解作为最终结果输出。
二、迭代法在数值计算中的应用1. 方程求解:迭代法可以用来求解非线性方程的根。
通过不断迭代计算,逐渐逼近方程的解。
例如,牛顿迭代法可以用来求解方程 f(x)=0 的根,其中f(x) 是一个可导函数。
2. 矩阵计算:迭代法在矩阵计算中也有广泛的应用。
例如,通过迭代法可以计算矩阵的特征值和特征向量。
另外,迭代法还可以用于解线性方程组,例如雅可比迭代法、高斯-赛德尔迭代法等。
3. 数值积分:迭代法也可以应用于数值积分的计算中。
例如,龙贝格积分方法就是一种基于迭代的数值积分方法,通过逐步逼近积分结果,得到更精确的数值近似解。
4. 数据拟合:迭代法可以用于数据拟合问题中,通过不断迭代调整拟合参数,使得拟合曲线与实际数据最接近。
例如,最小二乘法可以通过迭代来确定拟合参数的值。
5. 优化问题:迭代法也可以用于求解优化问题。
例如,通过不断迭代调整参数,使得目标函数达到最小值或最大值。
常见的优化算法,如梯度下降法和拟牛顿法,都是基于迭代的思想。
三、迭代法的优缺点迭代法在数值计算中具有以下的优点:1. 灵活性:迭代法适用于多种数值计算问题,并且可以根据具体问题的特点进行调整和改进。
2. 可扩展性:迭代法在计算上可以进行并行化处理,适用于大规模的数值计算问题。
常用算法——迭代法迭代法是一种常见的算法设计方法,它通过重复执行一定的操作来逐步逼近问题的解。
迭代法是一种简单有效的求解问题的方法,常用于求解数值问题、优化问题以及函数逼近等领域。
本文将介绍迭代法的基本概念、原理以及常见的应用场景。
一、迭代法的基本概念迭代法的思想是通过反复应用一些函数或算子来逐步逼近问题的解。
对于一个需要求解的问题,我们首先选择一个初始解或者近似解,然后通过不断迭代更新来逼近真实解。
迭代法的核心是找到一个递推关系,使得每次迭代可以使问题的解越来越接近真实解。
常见的迭代法有不动点迭代法、牛顿迭代法、梯度下降法等。
这些方法的求解过程都是基于迭代的思想,通过不断逼近解的过程来得到问题的解。
二、迭代法的原理迭代法的基本原理是通过不断迭代求解迭代方程的解,从而逼近问题的解。
迭代法的求解过程通常分为以下几个步骤:1.选择适当的初始解或者近似解。
初始解的选择对迭代法的收敛性和效率都有影响,一般需要根据问题的特点进行合理选择。
2.构建递推关系。
通过分析问题的特点,构建递推关系式来更新解的值。
递推关系的构建是迭代法求解问题的核心,它决定了每次迭代如何更新解的值。
3.根据递推关系进行迭代。
根据递推关系式,依次更新解的值,直到满足收敛条件为止。
收敛条件可以是解的变化小于一定阈值,或者达到一定的迭代次数。
4.得到逼近解。
当迭代停止时,得到的解即为问题的逼近解。
通常需要根据实际问题的需求来判断迭代停止的条件。
三、迭代法的应用迭代法在数值计算、优化问题以及函数逼近等领域有广泛的应用。
下面将介绍迭代法在常见问题中的应用场景。
1.数值计算:迭代法可以用于求解方程的根、解线性方程组、求解矩阵的特征值等数值计算问题。
这些问题的解通常是通过迭代的方式逼近得到的。
2.优化问题:迭代法可以应用于各种优化问题的求解,如最大值最小化、参数估计、模式识别等。
迭代法可以通过不断调整参数的值来逼近问题的最优解。
3.函数逼近:迭代法可以应用于函数逼近问题,通过不断迭代来逼近一个函数的近似解。
迭代法原理迭代法是一种常见的数值计算方法,也是一种解决问题的有效途径。
它的基本思想是通过不断迭代更新,逐步逼近问题的解。
在实际应用中,迭代法被广泛应用于数值分析、优化算法、计算机模拟等领域,具有较强的实用性和普适性。
迭代法的原理非常简单,它通过不断重复一个固定的计算过程,直到满足某个终止条件为止。
通常情况下,迭代法的过程可以描述为,首先选取一个初始值作为迭代的起点,然后根据某种规则进行迭代更新,直到满足预设的终止条件为止。
在每一次迭代中,都会根据当前的值计算出下一步的值,然后用新的值替代旧的值,不断迭代更新,直到满足终止条件。
迭代法的核心在于不断重复的更新过程,这种更新过程可以是简单的数值计算,也可以是复杂的函数迭代。
在实际应用中,迭代法通常用于求解方程的近似解、优化问题的最优解等。
通过不断迭代更新,可以逐步逼近问题的解,达到较高的精度要求。
迭代法的原理简单清晰,但在实际应用中需要注意一些问题。
首先,迭代法的收敛性是一个重要的问题,即迭代过程是否能够收敛到问题的解。
在一些情况下,迭代法可能会出现发散的情况,导致无法得到有效的解。
因此,在应用迭代法时,需要对问题的性质和迭代过程进行充分的分析,以确保迭代法能够有效收敛。
其次,迭代法的收敛速度也是一个重要的问题。
在实际应用中,迭代法的收敛速度直接影响到计算的效率和精度。
一般来说,迭代法的收敛速度越快,计算所需的迭代次数就越少,计算效率就越高。
因此,如何提高迭代法的收敛速度,是一个需要重点关注的问题。
总的来说,迭代法作为一种常见的数值计算方法,具有较强的实用性和普适性。
通过不断迭代更新,可以逐步逼近问题的解,解决一些复杂的数值计算和优化问题。
在实际应用中,需要注意迭代法的收敛性和收敛速度等问题,以确保迭代法能够有效地解决问题。
在数值计算、优化算法、计算机模拟等领域,迭代法都发挥着重要的作用,成为解决问题的有效途径。
通过对迭代法原理的深入理解和实际应用,可以更好地利用迭代法解决实际问题,提高计算效率和精度,推动科学技术的发展。
迭代法的原理
迭代法(IterativeMethods),又称顺序近似法,是求解用数学模型表示的问题的一
种有效方法。
它是建立在一组数值变量之间一种有效动态关系的基础上,使用迭代格式求
解问题的一种数学技术。
迭代法的基本原理是:将要求的接近的解的迭代过程,转换成一系列的子解,每个子
解满足某些约束条件。
然后,使用某种有效算法,将这些子解迭代直至满足所需的最终目
标值或损失函数的最小值。
迭代法的基本思想,主要是将一个解求解问题过程转化为一系列的子问题,对这些子
问题进行求解,以获得问题最优解。
可以将迭代法总结为以下几个步骤:
第一步:确定问题的初始值;
第二步:使用某种有效算法,将这些初始值迭代改变成满足所需最终目标的子解;
第三步:重复第二步,直至解的精度达到一定的要求;
第四步:求解完成,输出最终结果。
迭代法求解内容有:迭代解方程组,求函数极值和最优化等;优点是解的收敛速度较快,有较强的数值模拟能力,应用范围广,缺点是实现起来较为复杂,并且存在收敛障碍,很难得到满意解。
迭代法原理
迭代法是一种常用的数值计算方法,其原理是通过反复迭代逼近解的方法来求解数学问题。
迭代法的关键在于找到一个递推关系式,使得每一次迭代的结果能够接近问题的解。
具体而言,迭代法通常从一个初始值开始,然后根据递推关系式计算出下一个近似解。
然后,将新的近似解作为初始值,再次进行迭代计算,直到满足预设的停止条件。
迭代法的核心思想是将复杂的问题拆解成一系列简单的计算步骤,并通过多次迭代逼近解。
这种方法在数学问题求解、优化问题求解等领域都有广泛应用。
迭代法的成功与否取决于所选的递推关系式、初始值以及停止条件的选择。
合理选择这些参数可以提高迭代法的效率和准确性。
另外,迭代法有时也可能存在收敛性问题,即迭代的结果可能发散而无法得到解。
因此,在使用迭代法求解问题时,还需对迭代的结果进行检验和验证。
总之,迭代法是一种通过反复迭代逼近解的方法,通过选择递推关系式、初始值和停止条件来求解数学问题。
它在实际问题求解中有着广泛的应用和理论基础。
第二章迭代法得一般原理
非线性方程组无论从理论上还就是计算方法上,都比线性方程组复杂得多。
一般得非线性方程组很难求出解析解,往往只能求出其数值解,且往往只能借助于迭代法。
本章我们将讨论迭代法得一般原理、迭代法得一般构造及迭代收敛速度得衡量标准。
2-1 迭代法与不动点定理
设,考虑方程
(2-1) 若存在,使,则称为方程(2-1) 得解。
用迭代法求解(2-1) ,先将(2-1)化为等价得方程
(2-2) 这里映象。
方程(2-2)得解(即)称为映象g得不动点。
因此用迭代法解方程(2-1),就就是求(2-2)中映象g得不动点。
这样以及g就是否存在不动点自然就就是我们关心得问题。
定理2-1若为有界闭集上得严格非膨胀映象,,则g在内有唯一不动点。
证唯一性设g在内至少有两个不动点,,则
因,所以由上式推得。
唯一性得证。
记,由g及泛数得连续性可知连续。
因为有界闭集,故ϕ在上有最小值。
设为最小点,即
则为g得不动点。
因为若不然,则有,再由g严格非膨胀,可得
这与为ϕ得最小点相矛盾,故为g得不动点。
注定理中得有界闭性、g得压缩性与g映入自身,此3个条件缺一不可。
例如,在上严格非膨胀,但它在中却没有不动点。
下面我们介绍在应用上非常广泛得不动点定理。
定理2-2 (Brouwer不动点定理)设在有解闭凸集上连续,且,则g在至少有一个不动点。
本定理在一维情形下叙述为: 则f在中至少有一个不动点。
几何解释见图2-1。
2-2 迭代格式得构造
前一节我们谈到,用迭代法求解方程(2-1),就是先将这个方程化为等价得方程(2-2),然后求映象g 得不动点,通常(也就是最简单得情形)构造如下迭代序列:
, (2-3)
我们希望这个迭代序列收敛到g 得不动点,亦即方程得解。
如果g 就是压缩得,可望迭代序列收敛。
图2-2展示了一维迭代收敛得一种情形。
对于(2-3)
f 与。
如果
g 不依赖于迭代步k 只依赖于,k ,则迭代形式可表示为
(2-4) 并称之为,这时得迭代为多步迭代。
例如,则迭代可写为 (2-5)
称这种迭代为m 步迭代。
类似地有m 步非定常迭代。
通常称g 或为迭代函数。
用不同得方法构造得迭代函数可得到不同得得到法。
设,如果一个迭代法得到得序列则称得到序列就是适定得,适定性就是迭代法得起码要求。
若就是方程(2-1)得解,且序列满足
则称迭代序列收敛于。
定义2-1 设,就是方程得一个解。
若存在得一个邻域,使对任何初始值(对于m 步迭代法,初值为 ),迭代序列总就是适定得且收敛于,则称就是迭代序列得吸引点。
不少迭代法都就是设法使迭代函数g 就是压缩得,这时迭代序列得吸引点恰就是g 得不动点。
有时候也可使g 具有某种单调性,构成单调单调法。
2-3 迭代法得收敛性与收敛阶
前面谈到,一个迭代法,当其产生得迭代序列在适定与收敛时才有意义。
单步迭代格式(2-3)在实际中被采用得最多,这里,我们不加证明地给出三个与(2-3)格式有关得收敛性定理。
定理2-4 设就是方程得解,。
若存在一个开球S = 与常数,使得对一切,有
x
021(x ) 图2-2 迭代序列收敛
(2-7) 则对任意,就是迭代序列(2-3)得一个吸引点。
定理2-5 (Ostrowski) 设映象有一不动点,且在处F-可导,得谱半径(即特征值得最大模)
(2-9) 则存在开球,对任意初值,就是迭代序列得一个吸引点。
定理2-4与2-5都就是指出迭代在解得小球中即解得充分小得邻域中收敛,这种收敛称为局部收敛,也就就是说在已知方程(2-1)得解存在得情况下讨论得。
如果在不知道方程(2-1)得解就是否存在得情况下,只根据迭代初始近似满足得条件就能证明迭代序列收敛到方程得解,就称这种迭代法具有半局部收敛性。
局部收敛性与半局部收敛性都要求初始近似充分接近解,这给实际计算带来很大得不便。
如果一个迭代法对求解域D中任一点作为近似,迭代序列都能收敛到所求方程得解,这种收敛称为大范围收敛,这种收敛对实际计算很有意义。
对于定理2-5中得g若就是仿射得,即,,则条件(2-9) 变为,它就是用迭代法解线性方程组得收敛得充分必要条件,而对非线性方程组而言,条件(2-9) 仅为迭代(2-3)局部收敛得充分条件,这就是线性与非线性得不同之处。
下面我们给出一个非常实用得判断迭代全局收敛得定理。
定理2-6设
这里,,()为常数,映象具有一阶连续偏导数,。
若存在常数满足
(2-10) 这里为得第i个分量函数,则迭代序列(2-3)对于任意初始近似收敛于g得不动点,并且有估计
对于一个迭代法,除了考虑其收敛性,研究其收敛速度对实际计算也就是十分重要得。
为了衡量收敛速度,我们这里引入收敛阶得概念。
定义2-2 设迭代序列收敛到,如果存在及常数,使得当时有
(2-13) 则称序列至少p阶收敛。
当时(这时必须有),称序列至少线性收敛。
特别地,当,称序列至少平方收敛。
如果“一收敛序列至少就是p阶收敛得”这一结论对都成立,而对都不成立,则称这个序列得收敛阶就是。