下载文档原格式
迭代法——非线性方程与方程组的数值解法7.1方程求根与二分法二分法，取中点判断左右区间[a,b]-----x 0=(b+a)/2---f(x0)是否为0是：零点为x 0；否，f(x 0)与f(a)同号，则x 0取代a ；f(x 0)与f(b)同号，则x 0取代b 重新计算区间；7.2不动点迭代法及其收敛性不动点：将f(x)=0写成隐式x=φ(x)，若x*满足f(x*)=0，则x*=φ(x*) ；反之亦然，则x*为函数φ(x)的一个不动点。
迭代函数：φ(x)选初值x 0，x 1=φ(x 0)……有x k+1=φ(x k ),k=0,1,2….。
lim k→∞x k =x ∗等价于{xk}等价于迭代方程收敛不动点存在性: φ(x)在[a,b]区间内满足：（1）任意∀x ϵ[a,b]，有a ≤φ(x)≤b ；（2）∃1>L >0，使得∀x ，y ∈ a,b 都有丨∅ x −∅ y 丨≤L 丨x −y 丨； 则φ(x)在[a,b]区间内存在唯一不动点x*收敛误差计算： 丨xk −x ∗丨≤L k1−L 丨x1−x0丨丨xk +1−xk 丨≤L k 丨x1−x0丨丨x ∗−xk 丨≤11−L 丨xk +1−xk 丨局部收敛性：φ(x)在x*的某个领域R ：丨x-x*丨≤δ，对任意x0属于R 迭代后产生的｛xk ｝属于R ，且收敛到x*则称为局部收敛。
P 阶收敛：设迭代过程x k+1=φ(x)收敛于方程x=φ(x)的根x*，如果当k →∞，则有迭代误差e k =x k -x*满足渐进关系式：e k +1e k p →C （非零常数）则称迭代过程P 阶收敛。
领域内p 阶收敛：φ（p ）在所求根x*的领域内连续，有φ’(x*)=φ”(x*)=…= φ（p-1）(x*)=0；φ（p ）(x*)≠0，则在x*领域内p 阶收敛7.3收敛加速法1．艾特金加速收敛法x*=x 2x 0−x 12x 2−2x 1+x 0=x 0−（x 1−x 0）2x 2−2x 1+x 0；x k+1=φ(x k )x k+2=φ(x k+1)X k +1 =x k −（x k +1−x k ）2x k +2−2x k +1+x k =x k -（Δx k ）2/Δ2x k2．史蒂文森迭代法y k =φ(x k )，z k =φ(y k )，x k+1=x k −（y k −x k ）2zk −2y k +x k ，k=0，1，…改写为不动点迭代法：x k+1=Ψ(x k )，k=0，1，…Ψ(x)=x-（φ（x ）−x ）2φ（φ（x ））−2φ（x ）+x若x*为Ψ(x)的不动点，则x*也是φ（x ）的不动点；反之，若x*是φ（x ）的不动点，当φ”(x)存在， φ’(x)≠1时，x*也是Ψ(x)的不动点； 史蒂文森迭代法是二阶收敛的。
一：非线性方程的基本迭代方法简单迭代法非线性方程的一般形式f(x)=0 其中f(x)是一元非线性函数。
若存在常数s 使f(s)=0，则称s 是方程的根。
把方程转化为其等价的方程)(x x ϕ=，因而有)(s s ϕ=。
选定s 的初始近似值0x ，用迭代公式)(1k k x x ϕ=+，得到}{k x 收敛于s ，就求出了方程的解。
收敛性：)(s s ϕ=,)(x ϕ'在包含s 的某个开区间内连续。
如果|)(x ϕ'|<1则存在δ>0，0x ∈[s-δ,s+δ]时，由该迭代函数产生的迭代法收敛。
收敛速度：（}{k x 收敛于s ，k e 为s 与k x 的差值绝对值，则c e e r k k k =+∞→1lim，c 是常数，则该迭代是r 阶收敛）Newton 法为了使迭代的收敛速度更快，应尽可能使)(x ϕ在s 处有更多阶的导数等于零。
令)(x ϕ=)()(x f x h x +,)(x h 为待定函数，已知)(s ϕ'=0，推出)(x h =)(1x f '-。
这就得出了牛顿法的迭代形式 )()(1k k k k x f x f x x '-=+，（k=0、1、···） 牛顿法是二阶收敛的迭代方法，但是牛顿法的是局部收敛的，因此要求初值要靠近根。
求解中，对于每一个k 都要计算)(k x f '，而导数的计算比较麻烦，否则会产生很大误差。
割线法 在牛顿法基础上，用11)()(----k k k k x x x f x f 来代替)(k x f '，其中1-x 、0x 预先给定。
得到了割线法的迭代形式 )()())((111--+---=k k k k k k k x f x f x x x f x x ，（k=0、1、···） 割线法的收敛速度至少为1.618这样就避免了牛顿法求导数的繁琐程序单点割线法单点割线法就是在割线法的基础上，用))(,(00x f x 代替))(,(11--k k x f x ，得到的迭代形式 )()()(001k k k k k x f x f x f x x x x ---=+，（k=1、2、···） 单点割线法是一阶收敛的方法，它比割线法初值要少取一个点更加容易选取初值二：非线性方程的迭代解法的拓展修正的Chebyshev 法思想：将函数)(x f 在k x 处进行泰勒展开既 +-''+-'+≈!2)()())(()()(2k k k k k x x x f x x x f x f x f ，如果)(x f ≠0，先取线性部分来代替原来函数，既)(x f =)(k x f +))((k k x x x f -'=0，得到k x x -=)()(k k x f x f '-； 再用二次多项式部分代替原函数，既!2)()())(()()(2k k k k k x x x f x x x f x f x f -''+-'+==0，合并这两次的结果得到)()()))((2)()(1(2k k k k k k x f x f x f x f x f x x ''''⋅+-=，令1+=k x x ，得到就得到了新的迭代公式，这就是Chebyshev 方法的思想，该方法的迭代公式具有三阶收敛速度。
一、考试内容线性方程组和非线性方程（组）的求解、矩阵特征值和特征向量的计算、微积分的计算、微分方程定解问题的求解等，都是工程、科技、统计等实际问题中大量碰到的数学问题，这些问题的精确解很难求出。
而《计算方法》则是一门适合于计算机计算求解的数值方法，它简单可行，能有效求出上述数学问题的近似解。
通过本课程的学习，要求学生能掌握利用计算机求解基本数学问题常用的数值计算方法，学会构造基本的计算格式，并能作一定的误差分析，使学生具备基本的科学计算能力。
主要有：1.了解计算方法的认务和特点；2.熟练掌握方程的的近似解法，包括二分法、迭代法、牛顿迭代法和弦割法3.熟练掌握线性代数方程组的解法，直接解法中的高斯消去法、矩阵的直接三角分解法，平方根分解法，解三对角方程组的追赶法；解线性方程组的迭代法，简单迭代法，雅可比迭代法，赛德尔迭代法，SOR方法及其收敛性4.熟练掌握矩特征值和特征向量的计算，乘幂法与反幂法，古典雅可比方法，雅可比过关法5.熟练掌握插值法，拉格朗日插值法，牛顿插值法，等距节点插值法，埃尔米特插值法，三次样条插值法6.熟练掌握最小二乘法与曲线拟合，掌握矛盾方程组与最小二乘法，数据的多项式拟合，可化为线性拟合模型的曲线拟合7.熟练掌握数值积分与数值微分，包括牛顿-柯特斯求积公式、复化求积公式、龙贝格求积算法、高斯型求积公式和数值微分；8. 熟练掌握常微分方程初值问题数值解法，包括欧拉法与梯形法、泰勒展开法与龙格-库塔法、线性多步法2006-2007第一学期一. 填空1） 近似数253.1*=x 关于真值249.1=x 有____位有效数字；2） 设有插值公式)()(111k nk k x f A dx x f ⎰∑-=≈，则∑=nk kA1=______；（只算系数）3） 设近似数0235.0*1=x ，5160.2*2=x 都是有效数，则相对误差≤)(*2*1x x e r ____； 4） 求方程x x cos =的根的牛顿迭代格式为______；5） 矛盾方程组⎪⎩⎪⎨⎧-=+=-=+1211212121x x x x x x 与⎪⎩⎪⎨⎧-=+=-=+121222212121x x x x x x 得最小二乘解是否相同______。
