当前位置:首页 >> 理学 >>

东南大学数模课件2.6非线性方程近似根


2.6 非线性方程近似根
? 问题背景和研究目的
? 解方程(代数方程)是最常见的数学问题之一, 也是众多应用领域中不可避免的问题之一。
? 没有一般的解析方法来求解一般非线性方程,但如 果在任意给定的精度下,能够解出方程的近似解,则 可以认为问题已基本解决,至少可以满足实际需要。 ? 本节主要介绍一些有效的求解方程的数值方法:二分法, 迭代法 ( 牛顿法)。同时要求大家学会如何利用Matlab 来 求方程的近似解。

相关概念
? 线性方程 与 非线性方程

f ( x) ? 0
? 如果 f(x) 是一次多项式,称上面的方程为线性方程; 否则称之为非线性方程。

问题: 求连续的非线性方程 f ? x ? ? 0 的根的近似值。

a1

x1

b1

a2

x2 b 2

a3

x3 b a4 x4 b 3 4

a5

x5

b5 ? a6

x6 b6

根的隔离
若函数 f(x) 在闭区间[a,b]上连续,且 f(a)f(b)<0,则 f(x)在开区间 (a,b) 内至少存在一个根。通过根的隔离,可假设此区间内存在唯一根 x*。

二分法
? 基本思想
将有根区间进行对分,判断出解在某个区间内,然后 再对该区间对分,依次类推,直到满足给定的精度为 止。 求有根区间内的 单根 或 奇数重实根。

? 适用范围

? 数学原理:介值定理
设 f(x) 在 [a, b] 上连续,且 f(a) f(b)<0,则由介值定

理可得,在 (a, b) 内至少存在一点 ? 使得 f(?)=0。

二分法
? 算法
设方程在区间 [a,b] 内连续,且 f(a)f(b)<0,给定精 度要求 ? ,若有 |f(x)|<? ,则 x 就是f(x) 在区间 (a,b) 内的 近似根。
Step1: 预定精度? , i ? 0, a0 ? a, b0 ? b;

Step 2 : xi ?

? ai ? bi ? , if f ? ai ? f ? xi ? ? 0, ai ?1 ? ai , bi ?1 ? xi ; else if f ? bi ? f ? xi ? ? 0, ai ?1 ? xi , bi ?1 ? bi ;
1 2

else x? ? xi , break ;

Step3: if ? bi ? ai ? ? ? , i ? i ? 1,goto Step2; else x? ? xi .

二分法收敛性
? 收敛性分析
根据上面的算法,我们可以得到一个每次缩小一半的 区间序列 {[an , bn ]} ,在 (an, bn ) 中含有方程的根。 设方程的根为 x* ? (an , bn ) ,又 xn ? a ?b ,所以 2
n n

| xn ? x* |?

1 1 1 1 (bn ? an ) ? ? (bn ?1 ? an ?1 )= ? = n?1 (b ? a ) 2 2 2 2

0(n

?)

预定精度? , 初始区间为(a, b), 估计达到预定精度所需最少二分次数n.

二分法总是收敛的
? 二分法的收敛速度较慢 ? 通常用来给出根的一个

1 xn ? x ? n ?1 (b ? a ) ? ? 2
?

?b?a? n ? log 2 ? ? ?1 ? ? ?

较为粗糙的近似。

简单迭代法
? 基本思想
? 构造 f (x) = 0 的一个等价方程:x

? ? ( x)

?(x) 称为迭代函数
? 从某个初值 x0 出发,构造迭代格式

xk ?1 ? ? ( xk )
得到一个迭代序列

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
k ?? k ?? k ??

?

?

x*
即 x* ? ? ( x*)

? ( x*)

f ( x*) ? 0

注:若得到的点列发散,则迭代法失效!

迭代法的收敛性判据 定理2.1:全局收敛 定理2.2:全局发散

定理2.3:局部收敛与发散
定理2.4:收敛速度

迭代法收敛性判断
如果存在 x* 的某个邻域 ? =(x*-? , x* +? ), 使 ? 定义:

得对 ? x0 ? ? 开始的迭代 xk+1 = ?(xk) 都收敛, 则称该迭代法在 x* 附近局部收敛。
都有 |?’(x)|?L< 1, 则迭代局部收敛。

设 ? 定理 1: ?(x) 在某个邻域 ? 内连续,且对 ?x??

? 定理 2:如果定理 1 的条件成立,则有如下估计
L Lk | xk ? xk ? 1 | | xk ? x* |? | x1 ? x0 | | xk ? x* |? 1? L 1? L

迭代法收敛性判断
设 ? ? C1?a,b? ,且 ? 定理 3: (1) 对 ? x?[a, b],有 ?(x)?[a, b]; (2) 对 ? x?[a, b],有|?’(x)|?L< 1; 则对 ?x0?[a, b] ,由迭代 xk+1 = ?(xk) 得到 的点列都收敛(全局收敛),且

Lk | xk ? x* |? | x1 ? x0 | 1? L
L 越小,迭代收敛越快

收敛阶
为了进一步研究收敛速度问题,引入阶的概念: 记 ek ? xk ? x * ,如果 e ( p=1时还要求0<c<1) lim ?c?0 ( p ? N)
k ??

e

k ?1 p k

则称迭代是p阶收敛的。 p=1时,称为线性收敛, p>1时称为超线性收敛。 p越大收敛越快。

牛顿迭代法
? 基本思想:
用线性方程来近似非线性方程,即采用线性化方法 ? 设非线性方程 f (x)=0 , f (x) 在 xk 处作 Taylor 展开
f ( x) ? f ( xk ) ? f '( xk )( x ? xk ) ? o( x ? xk ) ? f ( xk ) ? f '( xk )( x ? xk )
令:( x P

? P( x)

k ?1

)?0

( f '( xk ) ? 0)

? 牛顿迭代公式 xk ?1

f ( xk ) ? xk ? f '( xk )

k = 0, 1, 2, ... ...

牛顿迭代公式
? 牛顿法的优点
对于单重根迭代2阶收敛,收敛速度较快, 特别是当迭代点充分靠近精确解时。

? 牛顿法的缺点
? 对重根收敛速度较慢(线性收敛) ? 对初值的选取很敏感,要求初值接近真解

? 牛顿法是目前求解非线性方程 (组) 的主要方法
在实际计算中,如果要求高精度,可以先用其它方法 (如二分法)获得真解的一个粗糙近似,然后再用牛 顿法求解。

牛顿迭代法大范围收敛性

设函数f ( x) ? C[(2)b] , 且满足条件: a,
1. f (a) f (b) ? 0;
2.?x ?[a, b], f ?( x) ? 0;
f ? x? ? ( x) ? x ? f ?? x?

3.?x ? (a, b), f ??( x)保号; 4.? (a) ? b, ? (b) ? a.
则对任意初值x0 ?[a, b], Newton迭代法产生的迭代序列2阶收敛到[a, b]内唯一单根。

Matlab 解方程的函数
roots(p):多项式的所有零点,p 是多项式系数向量。 fzero(f,x0):求 f=0 在 x0 附近的根,f 可以使用
inline、字符串、或 @,但不能是方程或符号表达式!

linsolve(A,b):解线性方程组。 solve(f,v):求方程关于指定自变量的解,f 可以是用
字符串表示的方程、符号表达式或符号方程; ? solve 也可解方程组(包含非线性); ? 得不到解析解时,给出数值解。

其他 Matlab 相关函数
? diff g=diff(f,v):求符号表达式 f 关于 v 的导数 g=diff(f):求符号表达式 f 关于默认变量的导数 g=diff(f,v,n):求 f 关于 v 的 n 阶导数
? f 是符号表达式,也可以是字符串 ? 默认变量由 findsym(f,1) 确定
>> syms x >> f=sin(x)+3*x^2; >> g=diff(f,x) >> g=diff('sin(x)+3*x^2','x')

井深的估算
假如你站在井边且身上带着一只具有计时功 能的计算器,你也许会出于好奇心想用扔下 一块石头听回声的方法来估计井的深度, 假定你能准确地测定时间,你又怎样来推算 井的深度呢,请你分析一下这一问题。
我有一只具有计时功能的 计算器。

方法一
假定空气阻力不计,可以直接利用自由落体运动的公式

1 2 h ? gt 2
来计算。设t=4秒,g=9.81米/秒2,则可求得h≈78.5米。

除去地球引力外,对石块下落影响最大的当属空气阻力。根据流体力学知识,此时 可设空气阻力正比于石块下落的速度,阻力系数K为常数,因而,由牛顿第二定律 可得:

令k=K/m,解得

dv F ? m ? mg ? Kv dt g

v ? ce

? kt

?

代入初始条件 v(0)=0,得c=-g/k,故有

k

g v ? ?1 ? e ? kt ? k g g ? kt 再积分一次,得: h ? t? 2 e ?c k k

代入初始条 件h(0)=0,得到计算水井高度的公式:

g g ? kt g g 1 ? kt g h ? t ? 2 e ? 2 ? (t ? e ) ? 2 k k k k k k
若设k=0.05并仍设 t=4秒,则可求 得h≈73.6米。 进一步深入考虑 多测几次,取平均值



听到回声再按跑表,计算得到的时间中包含了 反应时间 将e-kt用泰勒公式展开并 令k? 0+ ,即可得出前面不考 虑空气阻力时的结果。 不妨设平均反应时间 为0.1秒 ,假如仍 设t=4秒,扣除反应时间后应 为3.9 秒,代入 式①,求得h≈69.9米。 再一步深入考虑

还应考虑回声传回来所需要的时间。为此,令石块下落 音传回来的时间记 为t2,还得解一个方程组:

的真正时间 为t1,声
这一方程组是非线 性的,求解不太容 易,为了估算井深 竟要去解一个非线 性方程组似乎不合 情理

g 1 ? kt1 g ? ?h ? k ( t1 ? k e ) ? k 2 ? ?h ? 340t 2 t2 ? 0.187 s ?t ? t ? 3.9 h ? 63.6m ?1 2 相对于石块速度,声音速度要快得多,我们可 用方法二先求一 ? 次 h,令t =h/340,校正t,求石块下落时间 t ≈t-t 将t 代入式①再
2 1 2 1

算一次,得出井深的近似值。例如, 若h=69.9米,则 t2≈0.205秒, 故 t1≈3.695秒,求得 h≈63米。

作业
分别用两种迭代法: 1) Newton迭代法; 2)自己构造的非牛顿迭代格式(需讨论收敛性) 求下列非线性方程的根:
x (1) f ( x) ? sin x ? 在区间[ ? , ? ]内的根,精确至小数点后2位。 2 2
(2) f ( x) ? x3 ? 4x2 ?10在区间 [1,1.5]内的根,精确至小数点后3位。

迭代法的加速
? 设迭代 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 )

?? '( xk ) ? 1?

松弛法具有较好的加速效果,甚至有些不收敛的迭 代,加速后也能收敛。

? 缺点:每次迭代都需计算导数

Altken 迭代法
? Altken迭代法 用 差商 近似 微商
? 设 x* 是方程的根,则由微分中值定理可得

x * ? x2 ? ? ( x*) ? ? ( x1 ) ? ? '(? )( x * ? x1 )
? '(? ) ? ? ( 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迭代公式
( 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, ... ...

Altken 法同样具有较好的加速效果


赞助商链接
相关文章:
更多相关标签: