根据上面的算法，我们可以得到一个每次缩小一半的 区间序列 {[ak , bk ]} ，在 (ak , bk ) 中含有方程的根。 设方程的根为 x* (ak , bk ) ，又 xk
1 1 1 1 | xk | ( bk ak ) ( bk 1 ak 1 )= = k 1 ( b a ) 2 2 2 2
数学实验
求代数方程的近似根(解)
问题背景和实验目的
解方程（代数方程）是最常见的数学问题之一，也是 众多应用领域中不可避免的问题之一。 目前还没有一般的解析方法来求解非线性方程，但如 果在任意给定的精度下，能够解出方程的近似解，则可 以认为求解问题已基本解决，至少可以满足实际需要。 本实验主要介绍一些有效的求解方程的数值方法：对 分法，迭代法 和 牛顿法。同时要求大家学会如何利用 Matlab 来求方程的近似解。
>> k1=polyder([2,-1,0,3]); >> k2=polyder([2,-1,0,3],[2,1]); >> [k2,d]=polyder([2,-1,0,3],[2,1]);
多项式的值
计算多项式在给定点的值
代数多项式求值
y = polyval(p,x): 计算多项式 p 在 x 点的值
|’(x0)| 明显小于 1 时，则我们就认为迭代收敛
迭代法的加速
设迭代 xk+1 = (xk) ，第 k 步和第 k+1 步得到的近似 根分别为 xk 和 (xk) ，令
xk 1 (1 wk ) xk wk ( xk )
其中 wk 称为加权系数或权重。得新迭代 xk+1 = (xk)
( x ) (1 w) x w ( x )
加权系数 wk 的确定：令 ’(x)=0 得
w 1 1 '( x )
wk
1 1 '( xk )
松弛迭代法
松弛法迭代公式：
xk 1 (1 wk ) xk wk ( xk )
1 wk , 1 '( xk )
Matlab 多项式运算
Matlab 中多项式的表示方法
在 Matlab 中，n 次多项式是用一个长度为 n+1的向量来 表示，缺少的幂次项系数为 0。
p( x) an x n an1x n1 a1x a0 在 Matlab中表示为向量： [an , an1 , , a1 , a0 ]
ak bk ，所以 2
0(k
)
对分法总是收敛的
但对分法的收敛速度较慢 通常用来试探实根的分布区间， 或给出根的一个较为粗糙的近似。
迭代法
基本思想 构造 f (x) = 0 的一个等价方程：x 从某个近似根 x0 出发，计算
( x)
xk 1 ( xk )
得到一个迭代序列
>> p=[2,-1,0,3]; >> q=[2,1]; >> k=conv(p,q);
多项式除法运算： [k,r] = deconv(p,q)
其中 k 返回的是多项式 p 除以 q 的商，r 是余式。 [k,r]=deconv(p,q) <==> p=conv(q,k)+r
多项式的求导
polyder
k k k


x*
即 x* ( x*)
( x*)
f ( x*) 0
注：若得到的点列发散，则迭代法失效！
迭代法收敛性判断
如果存在 x* 的某个 邻域 =(x*- , x* + ), 使 定义： 得对 x0 开始的迭代 xk+1 = (xk) 都收敛, 则称该迭代法在 x* 附近局部收敛。 设 定理 1： x* =(x*)，的某个 邻域 内连续，且对 x 都有 |’(x)|q< 1, 则对 x0 ，由迭 代 xk+1 = (xk) 得到的点列都收敛。
k=polyder(p) : 多项式 p 的导数；
k=polyder(p,q): p*q 的导数；
[k,d]=polyder(p,q): p/q 的导数，k 是分子，d 是分母
p( x) 2 x 3 x 2 3， q( x) 2 x 1 ， 例：已知 求 p' , ( p q)', ( p / q)'
(4) 令 x1 (a1 b1 ) / 2, 若 | f ( x1 ) | ，则停止计算， 输出结果 x x1； 若 f (a1 ) f ( x1 ) 0，令 a2 a1, b2 x1; 否则令 a2 x1, b2 b1；
... ...
对分法收敛性
收敛性分析
例： 2 x 3 x 2 3
多项式显示: poly2sym(p,’x’)
[2, 1, 0, 3]
注：系数中的零不能省！
poly2sym([1 0 -2 -5],'t')
多项式四则运算
多项式加减运算
Matlab 没有提供专门进行多项式加减运算的函数，事实 上，多项式的加减就是其所对应的系数向量的加减运算 对于次数相同的多项式，可以直接对其系数向量进行 加减运算； 如果两个多项式次数不同，则应该把低次多项式中系 数不足的高次项用 0 补足，然后进行加减运算。
(1) 令 x0 (a b) / 2，计算 f ( x0 )； (2) 若 | f ( x0 ) | ，则 x0 就是我们所要的近似根，
停止计算， 输出结果 x x0；
(3) 若 f (a) f ( x0 ) 0，令 a1 a, b1 x0 ; 否则令a1 x0 , b1 b；
相关概念
线性方程 与 非线性方程
f ( x) 0
如果 f(x) 是一次多项式，称上面的方程为线性方 程；否则称之为非线性方程。
对分法
基本思想
将有根区间进行对分，判断出解在某个分段内，然后再 对该段对分，依次类推，直到满足给定的精度为止。
适用范围
求有根区间内的 单根 或 奇重实根。
qk | xk x* | | x1 x0 | 1 q
q 越小，迭代收敛越快
’(x*) 越小，迭代收敛越快
迭代法收敛性判断
以上所给出的收敛性定理中的条件的验证都比较 困难，在实际应用中，我们常用下面不严格的判别 方法：
当有根区间 [a, b] 较小，且对某一 x0[a, b] ，
'( ) ( x1 ) ( x0 )
x1 x0 x2 x1 x1 x0
x2 x1 x* x2 ( x * x1 ) x1 x0
( x2 x1 )2 x* x2 x2 2 x1 x0
Altken 迭代法
Altken迭代公式
xk 1
f ( xk ) xk f '( xk )
(x) 即为牛顿
法的迭代函数
f ( x ) f ''( x ) '( x ) [ f '( x )]2
牛顿法的收敛速度
f ( x) ( x) x 令 f '( x )
当 f (x*) 0 时 ’(x*)=0 牛顿法至少二阶局部收敛
以课本p84中x^3-3x+1=0为例，来考察上 面的几种求根方法
（1）二分法 erfenfa.m （2）普通迭代法 jiandandiedaifa.m （3）收敛发散判断 diedaifashoulianxing.m （4）松弛迭代法 songchidiedaifa.m （5）Altken迭代法 Altkendiedaifa.m （6）牛顿迭代法 niudundiedaifa.m
k = 0, 1, 2, ... ...
xk k 0

f (x) = 0 f (x) 的零点
等价变换
x = (x)
(x) 的不动点
迭代法的收敛性
收敛性分析
若
xk 收敛，即 lim xk x *，假设 (x) 连续，则 k
lim xk 1 lim ( xk ) lim xk
p1 2 x 3 x 2 3 例： p2 2 x 1 p1 p2 2 x 3 x 2 2 x 4
[2, 1, 0, 3] [ 0, 0, 2, 1] [ [2, 1, 2, 4]
多项式四则运算
多项式乘法运算： k = conv(p,q)
例：计算多项式 2 x 3 x 2 3 和 2 x 1 的乘积
( x2 x1 )2 x* x2 x2 2 x1 x0
(2)
xk
(1)
( xk ), xk
( xk )
(1)
( xk ( 2) xk (1) )2 xk 1 xk ( 2) ( 2) xk 2 xk (1) xk
k = 0, 1, 2, ... ...
注：若 x 是向量或矩阵，则采用数组运算 (点运算)！ 例：已知 p( x) 2 x 3 x 2 3，分别取 x=2 和一个 22 矩阵， 求 p(x) 在 x 处的值 >> p=[2,-1,0,3]; >> x=2; y=polyval(p,x) >> x=[-1, 2;-2,1]; y=polyval(p,x)
Altken 法同样具有较好的加速效果
牛顿迭代法
基本思想：
用线性方程来近似非线性方程，即采用线性化方法 设非线性方程 f (x)=0 , f (x) 在 x0 处的 Taylor 展开为
f ''( x0 ) f ( x ) f ( x0 ) f '( x0 )( x x0 ) ( x x0 ) 2 2!