您好、欢迎来到现金彩票网!
当前位置:双彩网 > 线性归结 >

研究生数值分析-第3章-方程(组)迭代解法ppt

发布时间:2019-05-25 20:26 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  3 方程(组)的迭代解法 m重根 若 2. 根的搜索 (1) 图解法(利用作图软件如 Matlab) 仍取 x0=0.5 , 得 由此可见, 埃特金法加速收敛效果是相当显著的. 3.4 牛 顿 法 3.4.1 牛顿法及其收敛性 对于方程f(x)=0,如果f(x)是线性函数,则它的求根是容易的. 牛顿法实质上是一种线性化方法,其基本思想是将非线逐步归结为某种线性方程来求解. 设已知方程f(x)=0有近似根x0,且在 x0附近f(x)可用一阶泰勒多项式近似,表示为 一、牛顿迭代法 当f?(x0)≠0时,方程f(x)=0可用线性方程(切线) 近似代替,即 f(x0)+f?(x0)(x-x0)=0. (3.4.1) 解此线性方程得 得迭代公式 此式称为牛顿(Newton)迭代公式. 牛顿法有显然的几何意义,方程f(x)=0的根x*可解释为曲线y=f(x)与x轴交点的横坐标. 设xk是根x*的某个近似值,过曲线y=f(x)上横坐标为xk的点Pk引切线,并将该切线与x轴交点的横坐标xk+1作为x*的新的近似值. 注意到切线方程为 这样求得的值xk+1必满足(3.4.1), 从而就是牛顿公式(3.4.2)的计算结果. 由于这种几何背景,所以牛顿迭代法也称切线法. x y x* xk y=f(x) xk+1 Pk Pk+1 xk+2 二、牛顿法的收敛性 定理4: 设f (x)在[a, b]上存在二阶连续导数且满足下列条件: (1)f (a) ? f (b) 0; (2)f’ (x) ? 0; (3)f? (x) 在区间[a,b]上不变号; (4)取x0? [a, b],使得f? (x)?f (x0) 0 则由(2)(3)确定的牛顿迭代序列{xk}二阶收敛于f (x)在 [a, b]上的唯一单根x*。 准确根 x* = 1.124123029, 可见迭代公式不同, 收敛情况也不同. 第二种公式比第一种公式收敛快得多, 而第三种公式不收敛. 例3 表明原方程化为 x=? (x) 的形式不同,有的收敛,有的不收敛,有的发散,只有收敛的的迭代过程xk+1=? (xk) (k=0,1,2,?)才有意义,为此我们首先要研究? (x)的不定点的存在性及迭代法xk+1=? (xk)的收敛性. 3.2.3 不动点的存在性与迭代法的收敛性 首先考察?(x)在[a, b]上不动点的存在唯一性. 定理1 设?(x)∈C[a, b]满足以下两个条件: 1o 对任意x∈[a, b]有a≤?(x)≤b. 2o 存在正数L1,使对任意x,y∈[a, b]都有 则?(x)在[a, b]上存在唯一的不动点x*. 证明 先证不动点的存在性. 若?(a)=a或?(b)=b,显然?(x)在[a, b]上存在不动点. 因为a≤?(x)≤b,以下设?(a)a及?(b)b定义函数 显然f(x)∈C[a, b],且满足f(a)=?(a)-a0, f(b)=?(b)-b0, 由连续函数性质可知存在 x*∈(a, b) 使 f(x*)=0,即x*=?(x*),x*即为?(x)的不动点. 再证不动点的唯一性. 设x1*, x2*∈[a, b]都是?(x)的不动点,则由(3.3)得 引出矛盾,故?(x)的不动点只能是唯一的.证毕. 在?(x)的不动点存在唯一的情况下,可得到迭代法 xk+1=?(xk)收敛的一个充分条件. 定理2 设?(x)∈C[a, b]满足定理1中的两个条件,则对任意x0∈[a, b],由xk+1=?(xk)得到的迭代序列{xk}收敛到的不动点x*,并有误差估计式 证明 设x*∈[a, b]是?(x)在[a, b]上的唯一不动点,由条件1o,可知{xk}∈[a, b],再由(3.3)得 因0L1,故当k→∞时序列{xk}收敛到x*. 下面证明估计式(3.4),由(3.3)有 于是对任意正整数p有 上述令p→∞, 注意到limxk+p=x* (p→∞)即得(3.4)式. 又由于对任意正整数p有 上述令p→∞, 及limxk+p=x* (p→∞)即得(3.5)式. 证毕. 迭代过程是个极限过程. 在用迭代法进行时,必须按精度要求控制迭代次数. 误差估计式(3.4)原则上确定迭代次数,但它由于含有信息L而不便于实际应用. 而误差估计式(3.5)是实用的,只要相邻两次计算结果的偏差足够小即可保证近似值xk具有足够精度. 对定理1中的条件2o可以改为导数,即在使用时如果?(x)∈C[a, b]且对任意x∈[a, b]有 则由微分中值定理可知对任意x, y∈[a, b]有 故定理1中的条件2o是成立的. 例如,在前面例3中采用的三种迭代公式,在隔根区间(1, 1.2)内,有 故前两个迭代公式收敛,第三个迭代公式不收敛. 例4: 求方程 在 内的根 。 解: 原方程可以等价变形为下列三个迭代格式 由迭代格式 (1) 取初值 得 结果是发散的?! 由迭代格式 (2) 取初值 得 结果精确到四位有效数字,迭代到 得到收敛结果。 由迭代格式(3) 取初值 得 结果精确到四位有效数字,迭代到 得到收敛结果。 四步就能得到收敛的结果了! 迭代格式(1)的迭代函数为 求导得 当 时 故迭代格式(1)是发散的。 分析: 迭代格式(2)的迭代函数为 当 时 由于 知当 时, 所以迭代格式(2)是收敛的。 迭代格式(3)的迭代函数为 当 时 由 时, 知当 所以迭代格式(3)也是收敛的。 结论: 通过以上算例可以看出对迭代函数 所得到的 若小于1,则收敛;且上界越小收敛速度越快。 求导, 的上界若是大于1,则迭代格式发散; 3.2.4 局部收敛性与收敛阶 上面给出了迭代序列{xk}在区间[a, b]上的收敛性,通常称为全局收敛性. 有时不易检验定理的条件,实际应用时通常只在不动点x*的邻近考察其收敛性,即局部收敛性. 定义1 设?(x)有不动点x*,如果存在x*的某个邻域R: x-x*≤δ,对任意x0∈R,迭代公式(3.2)产生的序列{xk}∈R,且收敛到x*,则称迭代法(3.2)局部收敛. 定理3 设x*为?(x)的不动点, 在x*的某个邻域连续,且 ,则迭代法xk+1=?(xk)局部收敛. 证明 由连续函数的性质,存在不动点x*的某个邻域R: x-x*≤δ,使对于任意x∈R成立 此外,对于任意x∈R,总有?(x)∈R,这时因为 于是依据定理2可以断定迭代过程xk+1=?(xk)对于任意初值x0∈R均收敛. 证毕. 例5 用不同迭代法求方程x2-3=0的根 . 解 这里f(x)= x2-3,可以改写为各种不同的等价形式x=?(x),其不动点为 ,由此构造不同的迭代法. 取x0=2, 对上式4种迭代法, 计算三步所得结果入下表. 2 1.75 1.732143 1.732051 ┆ 2 1.75 1.73475 1.732361 ┆ 2 1.5 2 1.5 ┆ 2 3 9 87 ┆ x0 x1 x2 x3 ┆ 0 1 2 3 ┆ 迭代法(4) 迭代法(3) 迭代法(2) 迭代法(1) xk k 注意 ,从计算结果看到迭代法(1)及(2)均不收敛,且它们均不满足定理3中的局部收敛条件,迭代法(3)和(4)均满足局部收敛条件,且迭代法(4)比(3)收敛快,因在迭代法(4)中??(x*)=0. 为了衡量迭代法(3.2)收敛速度的快慢可给出以下定义. 定义2 设迭代过程xk+1=?(xk)收敛于方程x=?(x)的根x*,如果迭代误差ek=xk-x*当k→∞时成立下列渐近关系式 则称该迭代法是p阶收敛的. 特别地,p=1时称线时称超线=?(xk),如果?(p)(x)在所求根x*的邻近连续,并且 则该迭代过程在x*的邻近是p阶收敛的. 证明 由于??(x*)=0,根据定理3立即可以断定迭代过程xk+1=?(xk)具有局部收敛性. 再将?(xk)在根x*处做泰勒展开, 利用条件(3.7), 则有 注意到?(xk)=xk+1,?(x*)= x*,由上式得 因此对迭代误差,令k→∞时有 这表明迭代过程xk+1=?(xk)确实为p阶收敛. 证毕. 上述定理告诉我们,迭代过程的收敛速度依赖于迭代函数?(x)的选取. 如果x∈[a, b]但??(x)≠0时,则该迭代过程只可能是线性收敛. 的三阶方法. 假设 x0 充分靠近 x*, 求 证明 首先由泰勒展式可得 例子 证明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求 而1/4a≠0,故此迭代公式是三阶方法. 3.3 迭代收敛的加速方法 埃特金加速收敛方法 对于收敛的迭代过程,只要迭代足够多次,就可以使结果达到任意的精度,但是有时迭代过程收敛较慢,从而使计算量变得很大,因此迭代过程的加速是个重要的课题. 设x0是根x*的某个近似值, 用迭代公式校正一次得 x1=?(x0) 而由微分中值定理,有 假设??(x)改变不大, 近似地取某个近似值L, 则有 由于 x2-x*≈L(x1-x*). 若将校正值x1=?(x0)再校正一次,又得 x2=?(x1) 将它与(3.1)式联立,消去未知的L,有 由此推知 在计算了x1及x2之后,可用上式右端作为x*的新近似,记作?x1,一般情形是由xk计算xk+1, xk+2,记 它表明序列{?xk}的收敛速度比{xk}的收敛速度快. (3.2)式称为埃特金(Aitken) △2加速方法. 可以证明 也称为埃特金 ( Aitken ) 外推法. 可以证明: 为线性收敛,则埃特金法为平方收敛; 这个加速迭代法也可写成下面格式 若 为 p ( p 1)阶收敛, 导数连续,则埃特金法为 2p–1 阶收敛. 的 p 阶 若 例题 求方程 x = e –x 在 x=0.5 附近的根. 解 取 x0=0.5, 迭代格式 x25=x26=0.5671433 若对此格式用埃特金法, 则 得 * 3.1 引言 (3-1) 本章主要讨论求解单变量非线性方程 其中 也可以是无穷区间. 如果实数 满足 ,则称 是方程(3-1)的 根,或称 是 的零点. 1.根的存在性。方程有没有根?如果有,有几个根? 2.根的搜索。这些根大致在哪里?如何把根隔离开? 3.根的精确化。 问题: 公元前1700年的古巴比伦人就已有关于一、二次方程的解法。 《九章算术》(公元前50~100年)其中“方程术”有联立一次方程组的一般解法。 1535年意大利数学家尼柯洛 冯塔纳找到了一元三次方程一般形式的求根方法。这个成就,使他在几次公开的数学较量中大获全胜,从此名扬欧洲。但是冯塔纳不愿意将他的这个重要发现公之于世. 当时的另一位意大利数学家兼医生卡尔丹诺,对冯塔纳的发现非常感兴趣。他几次诚恳地登门请教,希望获得冯塔纳的求根公式。 后来,冯塔纳终于用一种隐晦得如同咒语般的语言,把三次方程的解法“透露”给了卡尔丹诺。冯塔纳认为卡尔丹诺很难破解他的“咒语”,可是卡尔丹诺通过解三次方程的对比实践,很快就彻底破译了冯塔纳的秘密。 卡尔丹诺把冯塔纳的三次方程求根公式,写进了自己的学术著作《》中,但并未提到冯塔纳的名字。 由于第一个发表三次方程求根公式的人确实是卡尔丹诺,因此后人就把这种求解方法称为“卡尔丹诺公式”。 后来,卡尔丹诺的学生弗瑞里(Ferrari)又提出了四次方程的解法。 但对于五次方程求根,求索工作始终没有成效,导致人们对高次代数方程解的存在性产生了怀疑。 1828年17岁的法国数学家伽罗华(E·Galois 1811-1832)写出了划时代的论文“关于五次方程的代数解法问题”,指出即使在公式中容许用n次方根,并用类似算法求五次或更高次代数方程的根是不可能的 文章呈交法兰西科学院后,因辈份太低遭到冷遇,且文稿丢失。1830年伽罗华再进科学院递稿,得到泊松院士的判词“完全不能理解”。 后来伽罗华命运不佳,投考名校巴黎工科大学落榜,屈就高等师院,并卷入政事两次入狱,被开除学籍,又决斗受伤,死于1832年。决斗前,他把关于五次代数求解的研究成果写成长信,留了下来。 十四年后,法国数学家刘维尔(J·Liouville)整理并发表了伽罗华的遗作,人们才意识到这项近代数学发展史上的重要成果的宝贵。 38年后,即1870年,法国数学家若当(C·Jordan)在专著《论置换与代数方程》中阐发了伽罗华的思想,一门现代数学的分支 — 群论诞生了。 在前几个世纪中,曾开发出一些求解代数方程的有效算法,它们构成了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。 1.根的存在性 定理1:设函数 f (x) 在区间[a, b]上连续,如果f (a) ? f (b) 0, 则方程 f (x) = 0 在[a, b]内至少有一实根x*。 定义: 如果存在 使得 ,则称 为方程(3-1) 的根或函数 的零点。 (3-1) 其中, 为正整数, 则当m=1时, 称 为方程(3-1) 的 m重根或函数 的m重零点。 的单根或函数 的单零点。 称 为方程(3-1) 当 时, (3-1) (2) 扫描法(逐步搜索法) (3) 二分法* (1) (描)做图法 画出 y=f(x) 的草图, 由f(x)与横轴交点的大概位置来确定隔根区间; 或者利用导函数f?(x)的正、负与函数f(x)的单调性的关系确定根的大概位置. 若f(x)比较复杂, 还可将方程f(x)=0化为一个等价方程?(x)=?(x), 则曲线y=?(x)与y=?(x)之交点A(x*,y*)的横坐标 x*即为原方程之根, 据此也可通过作图求得x*的隔根区间. 如求解方程 的近似根 方法1: 将方程同解变换成 然后画两条曲线 y x 这两条曲线的交点的横座标大致为x=2.5 a b x* f(x) 1.画出 f(x) 的略图,从而看出曲线与x 轴交点的位置。 2.从左端点x = a出发,按某个预先选定的步长h 一步一步地向右跨,每跨一步都检验每步起点x0 和终点x0 + h的函数值,若 那么所求的根x*必在x0与x0+h之间,这里可取x0或x0+h 作为根的初始近似。 (2) 扫描法(逐步搜索法) 例1:考察方程 x 0 0.5 1.0 1.5 f (x) 的符号 - - - + (3) 二分法*(对分法) 设f(x)在区间[a, b]上连续, f(a)·f(b)0, 则在[a, b] 内有方程的根. 取[a, b]的中点 将区间一分为二. 若 f (x0)=0, 则x0就是方程的根, 否则判别根 x*在 x0 的左侧还是右侧. 若f(a) ·f(x0)0, 则x*∈(a, x0), 令 a1= a, b1=x0; 若f(x0) ·f(b)0, 则x*∈(x0 , b), 令 a1=x0, b1=b. 不论出现哪种情况, (a1, b1)均为新的有根区间, 它的长度只有原有根区间长度的一半, 达到了压缩有根区间的目的. 对压缩了的有根区间, 又可实行同样的步骤, 再压缩. 如此反复进行, 即可的一系列有根区间套 由于每一区间都是前一区间的一半,因此区间[an , bn]的长度为 若每次二分时所取区间中点都不是根,则上述过程将无限进行下去. 当 n→∞ 时,区间必将最终收缩为一点x* ,显然x*就是所求的根. 误差 分析: 第1步产生的 有误差 第 k 步产生的 xk 有误差 对于给定的精度 ? ,可估计二分法所需的步数 k : ①简单; ② 对f (x) 要求不高(只要连续即可) . ①无法求复根及偶重根 ② 收敛慢 2.由于在偶重根附近曲线 y=f(x) 为上凹或下凸, 即 f(a)与f(b)的符号相同, 因此不能用二分法求偶重根. 注: 1.用二分法求根,最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序,将[a, b]分为若干小区间,对每一个满足 f (ak)·f (bk) 0 的区间调用二分法程序,可找出区间[a, b]内的多个根,且不必要求 f (a)·f (b) 0 。 二分法的执行步骤 1.计算f (x)在有解区间[a, b]端点处的值,f (a),f (b)。 2.计算f (x)在区间中点处的值f (x1)。 3.判断若f (x1) = 0,则x1即是根,否则检验: (1)若f (x1)与f (a)异号,则知解位于区间[a, x1], b1=x1, a1=a; (2)若f (x1)与f (a)同号,则知解位于区间[x1, b], a1=x1, b1=b。 反复执行步骤2、3,便可得到一系列有根区间: 4、当 时,停止; 即为根的近似。 当 时, ,即这些区间必将收缩于一点,也就是 方程的根。在实际计算中,只要 的区间长度小于预定容 许误差 就可以停止搜索,即 然后取其中点 作为方程的一个根的近似值。 注: 例2 证明方程 存在唯一的实根 用二分法 求出此根,要求误差不超过 。 解:记 ,则对任意 , 因而, 是严格单调的, 最多有一个根, 所以, 有唯一实根 又因为 用二分法求解,要使 ,只要 解得 ,取 。所以只要二等分7次,即可求得满 足精度要求的根。计算过程如下表所示 1( + ) 0.5( + ) 0.25( + ) 0.125( + ) 0.125( + ) 0.09375( + ) 0.09375( + ) 0.09375( + ) 0.5(+) 0.25(+) 0.125(+) 0.0625(-) 0.09375(+) 0.078125(-) 0.0859375(-) 0(-) 0(-) 0(-) 0(-) 0.0625(-) 0.0625(-) 0.078125(-) 0.0859375(-) 0 1 2 3 4 5 6 7 f(bk)及符号 f(xk)及符号 f(ak)及符号 k 表3.1 所以, ? 问题 ? 虽然二分法计算简单,能够保证收敛,但是它对于方程单根存在区域信息要求太高,一般情况下很难实现,并且不能求偶重根、复根和虚根。在实际应用中,用来求解方程根的主要方法是迭代法。 使用迭代法求解非线性代数方程的步骤为: (1) 迭代格式; (2) 迭代格式的收敛性的构造分析; (3) 迭代格式的收敛速度与误差分析。 3.2 迭代法及其收敛性 3.2.1 不动点迭代法 将方程f(x)=0改写为等价方程形式 x=?(x). (3.1) 若要求x*满足f(x*)=0,则x*=?(x*);反之亦然,称x*为函数?(x)的一个不动点. 求f(x)的零点就等于求?(x)的不动点,选择一个初始近似值x0,将它代入(3.1)右端,即可求得 x1=?(x0). 可以如此反复迭代计算 xk+1=?(xk) (k=0,1,2,?). (3.2) ?(x)称为迭代函数. 如果对任何x0∈[a, b],由(3.2)得到的序列{xk}有极限 则称迭代方程(3.2)收敛. 且x*=?(x*)为?(x)的不动点,故称(3.2)为不动点迭代法. 上述迭代法是一种逐次逼近法,其基本思想是将隐式方程(3.1)归结为一组显式的计算公式(3.2),迭代过程实质上是一个逐步显式化过程. 当?(x)连续时,显然x*就是方程x=?(x)之根(不动点). 于是可以从数列{xk}中求得满足精度要求的近似根. 这种求根方法称为不动点迭代法, 称为迭代格式, ?(x)称为迭代函数, x0 称为迭代初值,数列{xk}称为迭代序列. 如果迭代序列收敛, 则称迭代格式收敛,否则称为发散. 3.2.2 迭代法的几何意义 通常将方程f(x)=0化为与它同解的方程 的方法不止一种,有的收敛,有的不收敛,这取决于 的性态,方程 的求根问题在几何上就是确定曲线y= 与直线y=x的交点P*的横坐标 x y y = x x y y = x x y y = x x y y = x x* x* x* x* y=g(x) y=g(x) y=g(x) y=g(x) x0 p0 x1 p1 ? x0 p0 x1 p1 ? x0 p0 x1 p1 ? x0 p0 x1 p1 ? 例3:求方程 的一个根. 构造迭代格式 x1 = 0.4771 x2 = 0.3939 … x6 = 0.3758 x7 =0.3758 解: 给定初始点 分别按以上三种形式建立迭代公式,并取x0=1进行迭代计算,结果如下: 解 对方程进行如下三种变形: 例3 用迭代法求方程x4+2x2-x-3=0 在区间[1, 1.2]内的实根.

http://lusobeat.com/xianxingguijie/3.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有