求代数方程的近似根解

求代数方程的近似根解第1页，共27页，2023年，2月20日，星期六1解方程（代数方程）是最常见的数学问题之一，也是众多应用领域中不可避免的问题之一目前还没有一般的解析方法来求解非线性方程，但如果在任意给定的精度下，能够解出方程的近似解，则可以认为求解问题已基本解决，至少可以满足实际需要本实验主要介绍一些有效的求解方程的数值方法：对分法，不动点迭代法和牛顿法。同时要求大家学会如何利用Matlab来求方程的近似解

问题背景和实验目的代数方程近似求解第2页，共27页，2023年，2月20日，星期六2相关概念

如果f(x)

是一次多项式，称上面的方程为线性方程；否则称之为非线性方程

线性方程与非线性方程本实验主要讨论非线性方程的数值求解第3页，共27页，2023年，2月20日，星期六3主要内容对分法

本实验讨论的数值算法

牛顿迭代法不动点迭代一般形式松弛加速迭代法不动点迭代法第4页，共27页，2023年，2月20日，星期六4基本思想对分法将有根区间进行对分，判断出解在某个分段内，然后再对该段对分，依次类推，直到满足给定的精度为止

适用范围求有根区间内的单重实根或奇重实根

数学原理：介值定理设

f(x)

在[a,b]

上连续，且f(a)f(b)<0，则由介值定理可得，在(a,b)

内至少存在一点

使得f()=0第5页，共27页，2023年，2月20日，星期六5具体步骤对分法设f(x)在区间[a,b]

内连续，且f(a)f(b)<0。对于给定的精度要求，若有|f(z)|<，则z

就是我们所需要的f(x)=0

在区间[a,b]

内的近似根例：用对分法求x3-3x+1=0在[0,1]中的解。（fuluA.m）(1)令x

=(a+b)/2,计算f(x)

(2)若|f(x)|<

，则停止计算，输出近似解x(3)若f(a)·f(x)<0，则令b

=

x;否则令a

=

x(4)返回第一步第6页，共27页，2023年，2月20日，星期六6收敛性分析对分法收敛性设方程的根为x*(ak,bk

)，又，所以0(k

)对分法总是收敛的对分法的收敛速度通常较慢对分法通常用来试探实根的分布区间，或给出根的一个较为粗糙的近似根据上面的算法，我们可以得到一个每次缩小一半的区间序列

{[ak,bk

]}

，在(ak,bk

)中含有方程的根。第7页，共27页，2023年，2月20日，星期六7主要内容对分法

本实验讨论的数值算法

牛顿迭代法不动点迭代一般形式松弛加速迭代法不动点迭代法第8页，共27页，2023年，2月20日，星期六8不动点迭代法基本思想构造

f(x)=0

的一个等价方程：从某个近似根x0

出发，计算得到一个迭代序列k=0,1,2,......

(x)

的不动点f(x)=0x=(x)等价变换f(x)

的零点第9页，共27页，2023年，2月20日，星期六9若收敛，即，假设(x)

连续，则收敛性分析迭代法的收敛性即注：若得到的点列发散，则迭代法失效！第10页，共27页，2023年，2月20日，星期六10定义：迭代法收敛性判断如果存在

x*的某个

邻域

=(x*-,x*+),

使得对

x0

开始的迭代

xk+1

=

(xk)都收敛,则称该迭代法在

x*

附近局部收敛。定理：已知方程

x=(x)，且(1)对

x[a,b]，有(x)[a,b]；(2)对

x[a,b]，有|’(x)|q<1；则对

x0[a,b]

，由迭代

xk+1

=

(xk)得到的点列都收敛，且第11页，共27页，2023年，2月20日，星期六11迭代法收敛性判断以上所给出的收敛性定理中的条件的验证都比较困难，在实际应用中，我们常用下面不严格的判别方法：当有根区间[a,b]

较小，且对某一

x0[a,b]，|’(x0)|明显小于1时，则我们就认为迭代收敛例：用不动点迭代法求x3-3x+1=0在[0,1]中的解。

（fuluB.m）q越小，迭代收敛越快’(x*)

越小，迭代收敛越快第12页，共27页，2023年，2月20日，星期六12迭代法的加速设迭代xk+1

=

(xk)

，第k

步和第k+1

步得到的近似根分别为xk

和(xk)，令其中wk

称为加权系数或权重。得新迭代xk+1

=

(xk)

加权系数wk

的确定：令’(x)=0得第13页，共27页，2023年，2月20日，星期六13松弛迭代法松弛法迭代公式：松弛法具有较好的加速效果甚至有些不收敛的迭代，加速后也能收敛缺点：每次迭代需计算导数例：用松弛迭代法求x3-3x+1=0在[0,1]中的解。

（fuluD.m）第14页，共27页，2023年，2月20日，星期六14主要内容对分法

本实验讨论的数值算法

牛顿迭代法不动点迭代一般形式松弛迭代法不动点迭代法第15页，共27页，2023年，2月20日，星期六15牛顿迭代法令：

基本思想：用线性方程来近似非线性方程，即采用线性化方法设非线性方程f(x)=0

,f(x)在x0

处的Taylor展开为第16页，共27页，2023年，2月20日，星期六16牛顿法迭代公式牛顿迭代公式k=0,1,2,......牛顿法的收敛速度令牛顿法至少二阶局部收敛当f’(x*)0时’(x*)=0(x)即为牛顿法的迭代函数例：用牛顿法求x3-3x+1=0的解。(fuluF.m)第17页，共27页，2023年，2月20日，星期六17牛顿法迭代公式牛顿的优点牛顿法是目前求解非线性方程(组)的主要方法至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。牛顿的缺点

对重根收敛速度较慢（线性收敛）对初值的选取很敏感，要求初值相当接近真解在实际计算中，可以先用其它方法获得真解的一个粗糙近似，然后再用牛顿法求解。第18页，共27页，2023年，2月20日，星期六18Matlab解方程函数roots(p)：多项式的所有零点，p

是多项式系数向量。fzero(f,x0)：求f=0

在x0

附近的根，f

可以使用inline、字符串、或@，但不能是方程或符号表达式！solve(f,v)：求方程关于指定自变量的解，f

可以是用字符串表示的方程、符号表达式或符号方程；solve也可解方程组(包含非线性)；得不到解析解时，给出数值解。linsolve(A,b)：解线性方程组。

第19页，共27页，2023年，2月20日，星期六19多项式的零点x=roots(p)：若

p

是

n

次多项式，则输出是p=0

的

n

个根组成的

n

维向量若已知多项式的全部零点，则可用poly函数给出该多项式p=poly(x)>>

p=[2,-1,0,3];>>

x=roots(p)例：已知p

=2x3-

x2+3，求p(x)的零点多项式的零点第20页，共27页，2023年，2月20日，星期六20线性方程组求解

线性方程组求解linsolve(A,b)：解线性方程组Ax=b

例：解方程组>>

A=[12-1;101;130];>>

b=[2;3;8];>>

x=linsolve(A,b)b

是列向量！第21页，共27页，2023年，2月20日，星期六21非线性方程的根

非线性方程的数值求解fzero(f,x0)：求方程

f=0

在

x0

附近的根方程可能有多个根，但fzero

只给出x0

附近的一个

fzero

先找出一个包含x0

的区间，使得f

在这个区间两个端点上的函数值异号，然后再在这个区间内寻找方程f=0

的根；如果找不到这样的区间，则返回NaN

x0

是一个标量，为参考点，不能缺省由于fzero

是根据函数是否穿越横轴来决定零点，因此它无法确定函数曲线仅触及横轴但不穿越的零点，如|sin(x)|

的所有零点第22页，共27页，2023年，2月20日，星期六22非线性方程的根

fzero

的另外一种调用方式fzero(f,[a,b])方程在[a,b]

内可能有多个根，但fzero

只能求一个求方程f=0在[a,b]

区间内的根。

参数

f

可通过以下方式给出：

字符串：

内联函数：

f

不是方程，即不含等号！f=inline('x^3-3*x+1');fzero(f,2)fzero('x^3-3*x+1',2)第23页，共27页，2023年，2月20日，星期六23>>

fzero('sin(x)',10)>>

fzero(@sin,10)>>

fzero('x^3-3*x+1',1)>>

fzero('x^3-3*x+1',[1,2])>>

fzero('x^3-3*x+1=0',1)X>>

fzero('x^3-3*x+1',[-2,0])>>

f=inline('x^3-3*x+1');>>

fzero(f,[-2,0])用

fzero

求零点时可以先通过作图确定零点的大致范围例：fzero举例第24页，共27页，2023年，2月20日，星期六24符号求解s=solve(f,v)：求方程关于指定自变量的解s=solve(f)：求方程关于默认自变量的解

f

可以是用字符串表示的方程，或符号表达式若f

是字符串，可以不含等号，表示解方程f=0若f

是符号表达式，不能含等号例：解方程x^3-3*x+1=0>>

symsx;f=x^3-3*x+1;s=solve(f,x)>>

s=solve('x^3-3*x+1','x')>>

s=solve('x^3-3*x+1=0','x')

非线性方程的符号求解第25页，共27页，2023年，2月20日，星期六25符号求解

solve

也可以用来解方程组solve(

f1,f2,...,fN,v1

,v2

,...,vN)求解由f1,f2,...,fN

确定的方程组关于v1

,v2

,...,vN

的解例：解方程组>>

[x,y,z]=solve('x+2*y-z=27','x+z=3',...