非线性方程的求根方法3

1OtherKindsofNewtonMethodNewton迭代法几个变形2•简化Newton法（平行弦法）•弦截法，又称割线法，弦位法，线性插值法•Newton下山法•Newton法对重根的求解•抛物线法（muller法），又称二次插值法•代数多项式求根3–若|`(x)|=|1-cf`(x)|1，即取0cf`(x)2在x*附近成立，则收敛。–若取c=1/f`(x0)or1/f`(xk)，则称简化Newton法。简化Newton法（平行弦法）迭代公式：)(1kkkxcfxx（c0,k=0,1,……）)()(xcfxx迭代函数：4在Newton迭代格式中，用差商近似导数，弦截法（割线法），弦位法11)()()(kkkkkxxxfxfxf称弦截法.)()()()(111kkkkkkkxxxfxfxfxx得5弦截法的几何意义：)()()()(11kkkkkkxxxxxfxfxfyxyx*xk+1xk-1Pk-1y=f(x)xkPk弦线PkPk-1的方程：当y＝0时，)()()()(111kkkkkkkxxxfxfxfxx6.,,:10端点作为初值通常取有根区间的两个才能运行弦截法需要两个初值注xx且,邻近二阶连续可微在)(设定理*xxf0)(,0)(xfxf.618.1215且收敛收敛阶,收敛敛}{序列由弦截法产弦截法产生,时),(,当,0则*10xxxOxxn证明略，因弦截法非单步法，不能用前述定理判别证明参考（关治，陆金甫《数值分析基础》）。7例用简化Newton法和弦截法计算方程x3-3x+1=0的根。313)()()()(21123111kkkkkkkkkkkkkkxxxxxxxxxxfxfxfxx解设f(x)=x3-3x+1，则f`(x)=3x2-3由简化的Newton法，得)()(01xfxfxxkkk3313203xxxxkkk由弦截法，得8x0=0.5x1=0.3333333333x2=0.3497942387x3=0.3468683325x4=0.3473702799x5=0.3472836048x6=0.3472985550x7=0.3472959759x8=0.3472964208x9=0.3472963440x10=0.3472963572x11=0.3472963553x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553简化Newton法弦截法要达到精度10-8，简化Newton法迭代11次，弦截法迭代5次（Newton迭代法迭代4次）。9无论前面哪种迭代法：（Newton迭代法、简化Newton法、弦截法）Newton迭代法)1(arctan21kkkkxxxx是否收敛均与初值的位置有关。0)arctan()(xxf0x精确解为例x0=2x1=-3.54x2=13.95x3=-279.34x4=12201720x取初值10x取初值x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.9631e-010x5=0收敛发散10•为防止Newton法发散，可增加一个条件：|f(xk+1)||f(xk)|，满足该条件的算法称下山法。•可用下山法保证收敛，Newton法加速收敛。Newton下山法)()(1kkkkxfxfxxkkkxxx)1(11（01,下山因子）记)()(1kkkkxfxfxx称Newton下山法。即11下山因子选取法的选取：从=1开始，逐次减半计算，即按,21,21,21,132的顺序，直到使下降条件|f(xk+1)||f(xk)|成立为止。12例求解方程033xx要求达到精度|xn-xn-1|≤10-5，取x0=-0.99.解：先用Newton迭代法：f`(x)=x2-1)()(1kkkkxfxfxx)1(3323kkkkxxxx)1(332003001xxxxx505829.32x2=21.69118x3=15.15689x4=9.70724x5=6.54091x6=4.46497x7=3.13384x8=2.32607x9=1.90230x10=1.75248x11=1.73240x12=1.73205x13=1.73205需迭代13次才达到精度要求13用Newton下山法，结果如下：k=0x0=-0.99f(x0)=0.666567k=1x1=32.505829f(x)=11416.4=0.5x1=15.757915f(x)=1288.5=0.25x1=7.383958f(x)=126.8=0.125x1=3.196979f(x)=7.69=0.0625x1=1.103489f(x)=-0.655k=2x2=4.115071f(x)=19.1=0.5x2=2.60928f(x)=3.31=0.25x2=1.85638f(x)=0.27k=3x3=1.74352f(x)=0.023k=4x4=1.73216f(x)=0.00024k=5x5=1.73205f(x)=0.00000k=6x6=1.73205f(x)=0.000000k下山因子xkf(xk)14•设f(x)=(x-x*)mg(x),m2，m为整数，g(x*)0,则x*为方程f(x)=0的m重根。此时有f(x*)=f`(x*)=……=f(m-1)(x*)=0,f(m)(x*)0Newton法对重根的求解方法一：只要f`(xk)0，仍可用Newton法计算，此时为线性收敛。)()()(xfxfmxx方法二：若取)()(1kkkkxfxfmxx则`(x*)=0，用迭代法求m重根，则具2阶收敛，但要知道m。15令11()[()]()[()]mmFxfxxhx1(),0,1,2,()kkkkfxxxmkfx即称之为带参数m的Newton迭代法,它是求方程(x)=0m重根的具有平方收敛的迭代法.方法二简证：设是方程(x)=0的m重根，则：(x)=(x-)mh(x),其中h(x)在x=处连续且h()0。则恰是方程F(x)=0的单根,应用Newton迭代法:1()()kkkkFxxxFx111[()]1[()]()mkkmkkfxxfxfxm16方法三：还可令则故x*是µ(x)=0的单根，对µ(x)用Newton法，可得它是平方阶收敛的。)()()(xfxfx)(*)()()(*)()(xgxxxmgxgxxx)()()()()()()(21kkkkkkkkkkxfxfxfxfxfxxxxx这是求方程(x)=0重根的具有平方收敛的迭代法,而且不需知道根的重数.17例利用Newton迭代法求方程(x)=x4-8.6x3-35.51x2+464.4x-998.46=0的正实根.oxy246810y=f(x)解y=(x)的图形为由图可知,方程在x=4附近有一个重根,在x=7附近有一单根.18利用Newton迭代法,2,1,0,)()(1kxfxfxxkkkk求方程的单根,取初值x0=7,精度=10-6,计算可得:x4=7.34846923,x5=7.348469229,|x5-x4|=0.000000001迭代5次就得到满足精度的解x5=7.348469229利用求重根的Newton迭代法求重根,取x0=4,可得x3=4.300000,x4=4.300000,|x4-x3|=0.000000006若用一般的Newton迭代法求重根,取x0=4,虽然也收敛,却需要迭代19次才能得到满足精度要求的解.迭代4次就得到满足精度的解x4=4.300000.19类似割线法，过三点做f(x)的二次插值多项式抛物线法（muller法）20],,[)](,,[],[)()()(12323123233233xxxfaxxxxxfxxfbxfcxxaxxbcy的二次插值多项式做和过)())(,())(,()),(,(332211xfxfxxfxxfx321*,,xxxx的三个近似值))(](,,[)](,[)(231233233xxxxxxxfxxxxfxfyacbbcxx4223acbbcxx42令23421(1)要有三个初始值(2)收敛速度是1.84阶。（单根）二重根的收敛阶是1.23。21321,且,,,时收敛,03Cxf方法名称收敛速度有效指数重根情况二分法11失败线性插值法1.6181.6181牛顿法21.4141二次插值法1.841.84二重时1.23各种插值方法的比较22代数多项式求解SplittingMethod劈因子法秦九韶算法23设n次代数方程用Newton迭代法求有限区间的实根，则要计算，一般采用秦九韶算法。)0(0)(0110aaxaxaxfnnn)(),(nnxfxf24由Taylor展式)2(!)()(...!2)()()()()1()()()(!)()(...!2)()()()()()()(1')(2'nxfxxxfxxxfxQxQxxxfnxfxxxfxxxfxxxfxfnnnnnnnnnnnnnnnnnn其中25)3()()()()(),()()2(12110''nnnnnnnbxbxbxQxQxxxfxfxQ的余式，令除以为且式知，由);()(1)()1(nnxfxQnxfxx，余式为次多项式为，得商）去除式表示，用（26nnnnnnnnnaxaxaxabxbxbxxxfxf111012110...])[()()(1)3(）式得式代入（),...,2,1()(的同次幂同次幂比较较等式两100nkxxfabababxnnnkkk27同理)()()()()('xRxxxfxQxQxxnnn有取除以用)4()(23120nnncxcxcxR令12211023120...])[()()()3()4(nnnnnnnnnbxbxbxbcxcxcxxxfxQ式得式代入28比较x的同次幂系数得：故代数方程的Newton迭代公式)1,...,2,1()(1100nkxxfccbcbcnnnkkk,...)2,1(11ncbxxnnnn29代数方程的Newton迭代法算法步。返回第停止计算输出做对计算输入2)(,;,||(4);)(3;;1,...,2,1)2;;)1);(),()2(;,),,...,2,1,0(:)1(101*01100101010000100000xxelsexxthenxxifffxxxfffxfafnkffafxfxfxniaki30SplittingMethod劈因子法求多项式的根从f(x)中分离出一个2次因子。即：)*)(*()(23312021110nnnnnnnnbxbxbxbvxuxaxaxaxaxf通过可解出一对共轭复根。0**2vxux思路从一对初值(u,v)出发，则有)()()()(2sxrxPvxuxxf其中(r,s)取决于u和v，可以看作是(u,v)的函数，即r=r(u,v)，s=s(u,v)。目标：r=r(u*,v*)=0，s=s(u*,v*)=0。31将r和s在初值点(u,v)做