《非线性方程求根迭代格式的研究》由会员分享，可在线阅读，更多相关《非线性方程求根迭代格式的研究（50页珍藏版）》请在金锄头文库上搜索。
1、南京信息工程大学 硕士学位论文 非线性方程求根迭代格式的研究 姓名：袁媛 申请学位级别：硕士 专业：应用数学 指导教师：杨建伟 20100501 摘要 许多自然和社会现象的研究，工程技术问题的解决，都可归结为非线性方 程f ( x ) = 0 的求解。大多数非线性方程只能用迭代法求解，迭代格式的建立，在 非线性方程求解中起至关重要的作用。本文致力于迭代格式的研究，主要工作 有： 提出一种基于插值算法的反函数迭代格式。不动点迭代的迭代函数需满足 p ( x ) l L 1 或矿( 曲 2 ) 次连续可导， 且满足 9 7 ( 工) = 0 ，J = 1 ，2 ，m - 1 ，9 2 ( x )
2、0 ， 则不动点迭代= 伊( 一1 ) ，k = 1 , 2 ，的收敛阶数为研。 2 1 4 牛顿法 牛顿法的具体迭代格式在第一章1 2 节已经介绍过，这里不再重复。 关于牛顿法有下面的局部收敛定理。 定理2 4 t 7 1 设函数厂( 石) 是m ( 2 ) 次连续可导，x 是方程厂( x ) = 0 的单根，则当充 分靠近x 时，牛顿法收敛，且收敛阶数至少为二。 对方程厂( 曲= 0 有重根时，牛顿法有下面的局部收敛定理。 定理2 5 7 1 i 揪f ( x ) 是足够阶连续可导，工是方程厂( 工) = 0 的，( 2 ) 重根，则当 充分靠近工时，牛顿法收敛，且仅仅为线性收敛。 下面介
3、绍优化技术中的牛顿法。更详细的内容参见文献 4 5 4 7 等。 考虑优化问题 r a i n f ( x ) ，x R ， ( 2 1 ) 令 缈( x ) = 厂( x t ) + 厂( x I ) ( x 一以) + i 1 厂。( x k ) ( x 一工七) 2 ， 再令 9 ( 工) = f 7 ( ) + f ”( x D ( x 一) = 0 ， 得到缈( x ) 的稳定点，记作+ l ，即得 X k + I - - “ X i t 一篇 阮2 ， 在点以附近，f ( x ) 妒( 功。因此，可用函数9 ( z ) 的极小点作为目标函数厂( 曲的极小点 的估计。如果五是，( 功
4、的极小点的一个估计，那么，利用( 2 2 ) 式可以得到一个序列 k 恐l 。可以证明，在一定条件下，这个序列收敛于问题( 2 1 ) 的最优解，而且是二阶收 敛。 求解方程的一些常用迭代方法还有前面已经介绍过的H a l l e y 法及C h e b y s h e v 法等，很 多方法都是在这些常用方法的基础上改进得到的。 8 非线性方程求根迭代格式的研究硕士学位论文 2 2 插值法 2 2 1 插值法的一般概念 在科学研究和工程中，常常会遇到计算函数值等类问题。然而函数关系往往很复杂， 有的甚至没有明显的解析表达式。例如，根据观测或实验得到一系列的数据，确定了与自 变量的某些点相应的函
5、数值，而要计算未观测到点的函数值。为此，可以根据观测数据构 造一个适当的较简单的函数近似地代替要寻求的函数。这就是要介绍的插值法。更具体地 说，插值法的基本原则如下： 设函数Y = 厂( 功定义的区间 口，b 】上，x o ，而，毛是【口，b 】上取得的，l + 1 个互异点， 且仅仅在这些点处函数值Y i = 厂( 薯) 为已知，要构造一个函数g ( x ) ，使得 g ( 而) = 咒， f 专0 ，l ，n ， ( 2 3 ) 并要求误差 ，( 功= 厂( 功- g ( x ) ， ( 2 4 ) 的绝对值p ( z ) I 在区间【口，b 】上任意一点或整个区间 口，b 】上比较小，即
6、g ( x ) 较好地逼近 厂( 力。点，x a ，矗称为插值基点或简称基点。基点不一定按其大小顺序排列， m i n ( x o ，x a ，毛) ，m a x ( x o ，x a ，) 】称为插值区间。f ( x ) 称为求插函数，g ( x ) 称为 f ( x ) 的插值函数，称 厂( 功= g ( x ) + ，( 工) ， ( 2 5 ) 为( 带余项的) 插值公式。，( z ) 称为插值公式的余项。常用的插值公式有拉格朗日插值公 式，牛顿插值公式，H e r m i t e 插值公式，样条插值方法等。后面将用插值算法进行迭代格 式的构造，因此这里简要介绍拉格朗日插值公式，详见文
7、 7 等。 2 2 2 拉格朗日插值多项式 令足 x 】槲表示所有的不高于雄次的实系数多项式和零多项式构成的集合。假设函数 Y = f ( x ) 在取定的，z + 1 个互异基点而，五，而处的值已知，分别为Y o = f ( x o ) ，Y l = 厂( 再) ，咒= ( 黾) 。现在要寻找一个多项式p ( x ) 埘工】露+ l ，使它满足条件 p ( 故) = 厂( 五) ，k = 0 ，1 ，一， ( 2 6 ) 记 z；(，：)=：i：!：j：j：!；!：il：!：；：i81i!12j：j：!；：。：!：!：!：；：；i!：!：；!端，z：=。，-，。，z， c 2 7 ， ”7
8、( 薯一而) ( 薯一而) ( 而一葺一1 ) ( 一而+ 1 ) ( 而一矗) 7 77 9 非线性方程求根迭代格式的研究 硕士学位论文 z ；( 】c ) = ：血；i ? ( 】x 咯- x _ j ) 。，f = = 。，l ，l ， ( 2 f ；) 它们皆为行次多项式，称为拉格朗日基本多项式。显然( x ) 满足关系 慨，= 臻；， 令 见 ) = Z f ( x , E ( x ) = 厂( X o ) 毛( 功+ ( 五) ( 功+ + 厂( 毛) ( 功 ( 2 9 ) 则p ( x ) 灭 工】槲。在( 2 9 ) 式中令x = ，得见( & ) = f ( x k ) ，
9、k = 0 ，1 ，以，即岛( 功满 足条件( 2 6 ) 。于是，多项式( 2 9 ) 便是所要求的插值多项式。 定理2 6 7 1 假设而，五，是，l + 1 个互异基点，函数厂( 功在这组基点的值厂( h ) ， k = 0 ，1 ，n 是给定的，那么存在唯一的多项式p ( x ) n i x 槲，满足 p ( 五) = 厂( t ) ，k = O ，1 ，n 称( 2 9 ) 所表示的多项式见( 工) 为拉格朗日插值多项式。若f ( X o ) ，f ( x a ) ，厂( ) 不全 为零，则多项式见( x ) 是有次数的。通常，考虑函数y = 厂( 功在刀+ 1 个互异点而，j c
10、l ，毛 处的值f ( x o ) ，f ( x a ) ，厂( ) 不全为零。 2 2 3 线性插值 已知函数y = f ( x ) 在点而，五处的值分别为Y o ，Y l ，在公式( 2 9 ) 中取，z = 1 ，则拉格 朗日插值多项式为 小h 高( X o + 乃器 亿 一毛JL 而一J = + 盐丑( 工一而) 一工。 由于 y = 儿+ 苎二丝0 一而) ， 1 一确 是经过两点( x o ，y o ) ，( 五，M ) 的直线( 图2 1 ) ，因此这种插值法通常称为线性插值。 非线性方程求根迭代格式的研究硕士学位论文 2 2 4 二次( 抛物线) 插值 图2 1 线性插值法 已
11、知函数) ，= f ( x ) 在点而，五，x 2 处的值分别为Y o ，Y l ，Y 2 此时，在公式( 2 9 ) 中取， 以= 2 ，得 p ：= 等蓑焉+ 乃等蓑等 + y ，垡二叠迎二兰! ( 2 1 1 ) ( 屯一X o ) ( X 2 一五) 这是一个二次函数。若( j c o ，) ，( 毛，乃) ，( 而，Y 2 ) 三点不在一条直线上，则经过这三点的曲线 就是一条抛物线( 图2 2 ) 。因此，这种插值法称为二次插值或抛物线插值。 图2 2 抛物线插值法 ( 布 ( 习 非线性方程求根迭代格式的研究 硕士学位论文 2 2 5 插值公式的余项 函数厂( x ) 的拉格朗日插
12、值多项式见( 工) 只是在基点而，五，吒处，有 磊( 薯) = 厂( 薯) ，i = 0 ，1 ，嚣 若x 而( i = 0 , 1 ，挖) ，则一般说来 见( 工) 厂( 功， 即 f ( x ) 一P 。( 功0 ， 令 ( 工) = 厂( 一以( 功， ( 2 1 2 ) ，：I ( x ) 表示用P 。( 曲代替f ( x ) 时，在点x 产生的误差。 定理2 7 1 7 设( 工) 在包含玎+ 1 个互异基点而，五，在内的区间 口，6 】上具有理阶 连续导数，且在( a ，b ) 内存在恕+ 1 阶有界导数，那么，对 口，b 】上的每一点x 必存在 善( a , b ) 使得 水)
13、= 帮啪) ，州 1 ， 则 ( i ) Y Y 程f ( x ) = 0 有唯一根x ： ( i i 对任意X o k ，b 】， 用迭代格式 + l = 伊1 ( ) ， 可得l i m 也= ，； ( i i t ) k 。f 1 ，得 3 迪= x i 旧 ( i i i ) 由( 3 2 ) 式得 I x 一以I = l 一矗+ x 一以以l I 一故I + 卜一确l I X k + I X k + * q 所以 竽k 一，l k 一l ， 1 _ 陬一z l sl 一I ， 因而 I x k - x l 吉k 一蕞I ， 注意到 k + 。一以I = 眵( 矗+ ：) 一伊( k
14、“) I = 缈( 彘) l + ：- x k + ，I L l x k 也- x k “l ， 其中磊介于工“2 与z 七+ 1 之间 所以 递推可得 由上可得 I x k + l X k I 扣嘞I ， I x 。“一I 1 6 5 古卜I ， 非线性方程求根迭代格式的研究硕士学位论文 I X k - - X * I 击k 一吒I 击如飞l 西1 可b - a 类似地，当缈( j c ) 三 1 时有如下定理： 定理3 3 由方程厂( 力= o 构造一个等价方程工= 伊( 砷，若矿( 力在k ，6 】上具有一阶 连续的导数，且满足以下两个条件： ( 1 ) 当x 口，b 时，矿( 口) 口
15、，缈( 6 ) b ； ( 2 ) 存在常数 1 则 对任意而U ( x ；万) ，用迭代格式+ 1 = 9 1 ( ) 产生的序列 蠢 R ，且。l i _ + r a 。x t = x - 证明由x o U ( x ；万) 及x 是方程( 工) = 0 的根，即x 也是方程工= 伊( x ) 的根。存 在U ( x ；万) ，k = 0 ，1 ，2 ，3 ，使黾+ 1 = e 9 - 1 ( t ) ，即有黾= 9 ( + 1 ) ，将式黾= 9 ( + 1 ) 与式 X = 缈p ) ，= 缈【x ， 相减，并应用微分中值定理得到 一工= 缈( 以+ 1 ) 一9 ( 工) = 97 ( 彘) ( 以+ l x ) ， k = 0 , 1 ，2 ，3 ， 其中磊介于x _ | + 1 和工之间， 再应用条件9 7 ( x ) 三 1 得到 k x | 三k r z | ， 亦即 1 7 k = 0 , 1 ，2 , 3 ， 非线性方程求根迭代格式的研究 硕士学位论文 k - - X 怿l l x k _ l - - X * l ， 递推可得 I X k - - X * f X
