第六章非线性方程(组)的求解 同题:求∈R使f(x)=0.f:R1→、R的函数 若n=1,称为方程求根问题;n>1称为方程组求解 理论问题 (1)解的存在性。即有解还是无解,有多少解 (2)解的邻域性态。即孤立解的区域,解的重数,光滑性 关于解的存在性及其性态,不是数值分析所讨论的问题 我们总认为:f(x)在一个确定的区域2cR内有唯一解, 任务是如何求得这个x*。 下面分别讨论方程求根和非线性方程组求解的算法
第六章 非线性方程（组）的求解 问题：求x R n 使f (x) = 0, f : R n → R n 的函数。 若n=1,称为方程求根问题；n>1称为方程组求解。 理论问题： （1）解的存在性。即有解还是无解，有多少解。 （2）解的邻域性态。即孤立解的区域，解的重数，光滑性。 关于解的存在性及其性态，不是数值分析所讨论的问题。 我们总认为： f (x)在一个确定的区域 R n 内有唯一解x * ， 任务是如何求得这个 x * 。 下面分别讨论方程求根和非线性方程组求解的算法
§61非线性方程求根 如果(x)在区间ab内有解且有唯一解,秕区间为(x)的有解区间 二分法(区间分半法去) 设f(x)在区间a,b上连续且(a)·f(b)<0,则f(x)在区间a,b呐有解。 不妨设有唯一解。 算法: 找ab]={a02b]→[a1,b]→…[anbn]→… 满足 (1)f(an)f(bn)<0 (2)b d 令 aL.+ ∴X∈a 1rn-x<3(6n-an)=o(b-a) n→∞,x→)x
§6.1 非线性方程求根 如果f (x)在区间[a,b]内有解且有唯一解，称此区间为f (x)的有解区间。 不妨设有唯一解。 设 在区间 上连续且 则 在区间 内有解。 一、二分法（区间分半法 ） f (x) [a, b] f (a) f (b) 0, f (x) [a, b] , . ( ) 2 1 ( ) 2 1 [ , ], , 2 ( ). 2 1 (2) (1) ( ) ( ) 0; [ , ] [ , ] [ , ] [ , ] , * * * 1 1 0 0 1 1 n x x x a b x x b a b a a b x b a b a f a f b a b a b a b a b n n n n n n n n n n n n n n n n n n → → − − = − + = − = − = − − 令 满 足 找 算法：
function [ x n]=erfenfaqiugen(f name, a,b, epsl) %求方程邱x)=0在有解区间[a]的根,满足fa)*(b)epsl if abs(0 else ene X-(a+b)/2; ffeval(f name, x) n=n+1 ene
function [x,n]=erfenfaqiugen(f_name,a,b,epsl) %求方程f(x)=0在有解区间[a,b]的根，满足f(a)*f(b)epsl if abs(f)0 a=x; else b=x; end x=(a+b)/2; f=feval(f_name,x); n=n+1; end
注: 1)二分法只能求奇数重的实根。 设x为f(x)的n重根,即f(x)=(x-x)mp(x),(x)≠0 不妨设叭(x)>0由(x)的连续性,则δ>0当x-x0. 又当m充分大以后{n,b]c(x-o,x"+6)于是m为偶数 时 ,x∈[an,bn,f(x)>0,不变号了! 2)二分法线性收敛,收敛因子为1/2 ∵x.-x n-Ia x)2 3)二分法可用来划分有解区间,这应是它的最大优点
注： 1）二分法只能求奇数重的实根。 时 ， 不变号了！ 又 当 充分大以后， 于 是 为偶数 不妨设 由 的连续性，则 当 时 ， 设 为 的 重根，即 ） 。 [ , ], ( ) 0, ), * , * [ , ] ( ( ) 0. * ) 0, ( ) 0, * ( ) 0 * ) ( , ( * ( ) ( ) ( * − + − = − f x n b n x a n an bn x x m x x x x x x f x n f x x x m x x 2）二分法线性收敛，收敛因子为1/2。 3）二分法可用来划分有解区间，这应是它的最大优点。 . 2 1 ( ), 2 1 ( ) 2 1 * 1 * * 1 1 1 * − − − − − − − − − x x x x x x x a x x n n n n n n
般迭代法 f(x)=0分x=0(x),q(x)称为迭代函数 xo∈Na(x.在解的邻域内选定初值 =0 n+l=( 3、讨论{xn的收敛性 定理一设0(x)在区间a,b上 (1)一阶导数连续,且題自映射,即a≤φ(x)≤b, (2)g(x)≤L<1 则vo∈[ab,由迭代6-1-1)产生的数列xn}均收敛,且 1-L 或 1-L
二、一般迭代法 、讨论 的收敛性。 、 在解的邻域内选定初值。 、 ， 称为迭代函数。 n x n x n x n x N x f x x x x 3 ( ) 1 0,1,2, ), * ( 0 2 1 ( ) 0 ( ) ( ) = + = = = 1 0 1 * 1 1 * 1 [ , ] 0 ( ) 1 ( ) , : ( ) [ , ] x x L n L x n x n x n x L x n x n x a b x x L a x b x a b − − − − + − − 6 - 1 - 1 2 1 或 则 ，由迭代（ ）产生的数列 均收敛，且 （ ） （ ）一阶导数连续，且是自映射，即 定理一 设 在区间 上
定理一的条件太强,不便于实际应用。下面给出一个局部 收敛定理 定理二:如果(x2)连续,(x2)≤L<1,则x∈N6(x2 由迭代(6-1-D产产生的数{xm}均收敛收敛 n n+1 或 1-X0 般迭代法只有理论上的意义,因为迭代函数φ(x)通常不 易构造
定理一的条件太强，不便于实际应用。下面给出一个局部 收敛定理。 0 x 1 x 1 L Ln * x n x x n 1 x n 1 L * 1 x n x 6 -1-1 x n ) * (x δ N 0 ) L 1 , x * ) (x * : (x − − − − − + − 或 由迭代（ ） 产产生的数 均收敛收敛 定理二 如果 连续， 则 ， 一般迭代法只有理论上的意义，因为迭代函数 通常不 易构造。 (x)
三、牛顿迭代法 设f(x)在其零点的邻域N。(x*)内有直到二阶连续导数 且f(x)≠O,x∈N。(x*)则xo∈Ns(x*迭代算法 f(n) n=0.1.2 (6-1-1) 产生的数列xn少平方收敛于 称算法(6-1-1)为牛顿迭代法。 证明:(x)=x ,则x∈N(x)f(x)=0<x=0(x) 0(x)=1-"(x) f1y(x):D(x)=0牛顿迭代收敛 又 :xn+1- 0p(xn)-0(x) -xsy"(=c至少三阶收敛
三、牛顿迭代法 . , 0,1,2, . ( ) ( ) ( ) 0 ( ). ( ), ( ) ( ) * 1 * 0 * * * x x n f x f x x x f x x N x x N x f x x N x n n n n n 产生的数列 至少平方收敛于 且 ， 则 迭代算法 设 在其零点 的邻域 内有直到二阶连续导数， (6 -1-1 ) = = − + 称算法（6-1-1）为牛顿迭代法。 至少二阶收敛。 又 牛顿迭代收敛 证明：令 则 , 2 ( ) ( ) ( ) ; 2 ( ) ( ) ( ) ( ), ( ) 0, [ ( )] ( ) ( ) 1 , ( ), ( ) 0 ( ) ( ) ( ) ( ) 2 * * 1 * * * 2 1 * 2 * c x x x x x x x x x x f x x f x f x x x N x f x x x f x f x x x n n n n n = − − − − = − = = = − = = = − + +
注: (1)牛顿迭代法是局部收敛的,由于。(x*)的未知性,使得 初始迭代点的选择很困难 (2)要求'(x*)≠0,说明牛顿迭代法求单榧效且平方收敛。能 重根吗? (3)牛顿迭代法中每一步蒜导数(xn)这对实际应用带来一的 困难。 关于初值的问题: 般来说釆用试探法,但对于一些实际问题初值的选择并 不困难,它是明确的。 关于重根的问题: 设x是f(x)的m重零点⑩m>1此时 f(x=(x-xmg(x),g(x)#0 f(x)=m(x-x"m-Ig(x)+i(x-x)g(x)
困难。 （ 牛顿迭代法中每一步需求导数 这对实际应用带来一定的 重根吗？ （ ）要求 说明牛顿迭代法求单根有效且平方收敛。能求 初始迭代点 的选择很困难。 （ ）牛顿迭代法是局部平方收敛的，由于 的未知性，使得 注 ： ( ), ( ) 0, ( ) * 0 * n f x f x x N x 3 ) 2 1 关于初值的问题： 一般来说采用试探法，但对于一些实际问题初值的选择并 不困难，它是明确的。 关于重根的问题： m 1 ) ( ) ( )], 1 ( ) ( ) [ ( ) ( ) ( ) ( ), ( ) 0, ( ) , * 1 * * * * x x g x m f x m x x g x f x x x g x g x x f x m m m = − + − = − − 设 是 的 重零点（ 此 时
f(x=m(x-x m-ih(x) h(x)=g(x)+1(x-x)g(x),h(x*)≠0, f(x) ∴Q(x)=x xr-(x-x g(r)/h(x) xX o(x)=1-1,p(x2) 牛顿迭代线性收敛,随m的增加收敛性越来越差 重根时的改进 (1)重数m已知时,选伐n=xnm…(6-1-2)至少平方收敛 (2)通常重数不知道,个实用的方法是: 令从(x)=f(x)则(x)=0分(x)=0,且x是(x)单重零点。 迭代n+1=x 1(xn) (6-1-3)至少平方收敛 u(n)
牛顿迭代线性收敛，且随m的增加收敛性越来越差。 m x m x x-x g x h x m x f x f x x x x x g x h x m h x g x f x m x x h x * m = − = − = − = − = + − = − − 1, 1 , ( ) 1 1 ( ) 1 ) ( )/ ( ), 1 ( ) ( ) ( ) ( ) ( ), ( ) 0, 1 ( ) ( ) ( ) ( ) ( ) * * * * * 1 ( 重根时的改进： 则 ， 且 是 的单重零点。 ） 令 （ ）通常重数不知道，一个实用的方法是： 至少平方收敛。 ） （ ）重数 已知时，迭代 , ( ) 0 ( ) 0 ( ) ( ) ( ( ) ( ) ( * 1 f x x x x f x f x x f x f x m x x m n n n n = = = + = − 2 1 (6 -1- 2 ) 迭 代 (6 -1- 3)至少平方收敛。 ( ) ( ) 1 n n n n x x x x + = −
关于导数计算的处理: (1)利用牛顿迭代先进犴步,比如进行到鐫得到近似值;, 接下来采用c n=k,k+1, k 此迭代法通常是线性敦的 (2)一个实用的方法是分代替微分,即 n+1 f(n) 此迭代法称为割线法定是超线性收敛的(敦阶至少为618) 实例分析 分别用牛顿迭代法,逖牛顿迭代渚-1-2)和(-1-3), 以及它们的离散型迭浅求方程(x)=(x+1x-1)2=0的二 重根x*=1,并比较快慢
关于导数计算的处理： 1.618) ( ) ( ) ( ) ( ) , , 1, ( ) 1 : , 1 1 1 1 此迭代法称为割线法，它是超线性收敛的（收敛阶至少为 （ ）一个实用的方法是由差分代替微分，即 此迭代法通常是线性收敛的。 接下来采用 （ ）利用牛顿迭代先进行几步，比如进行到第步得到近似值 n n n n n n n n n n k k f x f x f x x x x x x x cf x n k k f x c k x − − + + − − = − = − = + = 2 1 重 根 并比较快慢。 以及它们的离散型迭代法求方程 的 二 分别用牛顿迭代法，改进牛顿迭代法 和 （ ） ， 实例分析 1, ( ) ( 1)( 1) 0 (6 1 2) 1: * 2 = = + − = − − x f x x x 6 -1- 3