当前位置：文档之家 › 非线性方程(组)的数值解法

非线性方程(组)的数值解法

  • 格式：doc
  • 大小：456.50 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

5-非线性方程组的数值解法及最优化方法

5-非线性方程组的数值解法及最优化方法
然后通过各种下降法或优化算法求出模函数的极小值点，此 极小值点即为非线性方程组的一组解。
非线性方程组的数值解法
不动点迭代法：根据非线性方程求根的迭代法，将方程组改 写为如下等价方程组
xi i x1, x2,, xn , i 1,2,, n
构造迭代公式
xik 1 i x1k , x2k ,, xnk , i 1,2,, n
非线性方程组的数值解法
若对任意A Cmn 都有一个实数 A 与之对应，且满足：
（1）非负性：当 A O 时， A 0 ；当A O 时，A 0；
（2）齐次性：对任何 C ，A A ；
（3）三角不等式：对任意 A, B C nn ，都有A B A B ;
（4）相容性：对任意A, B C nn ，都有 AB A B ，
…
…
18
(0.2325670051,0.0564515197)
19
(0.2325670051,0.0564515197)
max
1 i 2
xik
xik
1
0.2250 0.0546679688 0.0138638640 0.0032704648 0.0008430541 0.0001985303 0.0000519694 0.0000122370 0.0000032485 0.0000007649
10-9
非线性方程组的数值解法
练习题：用牛顿迭代法求解方程组
取 X 0 1.6,1.2T
xx1122
x22 x22
4 1
结果：1.5811,1.2247
非线性方程组的数值解法
应用经过海底一次反射到达水听器阵的特征声线传播时间， 来反演海底参数。假设水中和沉积层声速都是恒定的，海底 沉积层上界面水平，下界面倾斜。特征声线由水中声源出发 折射进入沉积层，经过沉积层的下界面反射后，再折射进入 水中，由水中水听器阵接收。特征声线的传播时间为声线在 水中和沉积层中的传播时间之和。 三维坐标关系如图所示：

3-第三章 非线性方程的数值解法

3-第三章 非线性方程的数值解法

到小数点后第三位小数，需要二分多少次？ 解：设 f ( x) x6 x 1，由于 f (1) f (2) 0, f ( x) 0(1 x 2)， 所以在区间 [1,2]内方程 f ( x) 0 有唯一实根。
ba 1 令 k 1 10 3 ，求得所需对分次数至少是10次。 2 2
x* xk ba k 1 2
时，停止计算。
§1 根的搜索与二分法
3 2 x 4 x 10 0 在 [1,2] 内的根的近似 例：用二分法求方程 1 2 值，要求绝对误差不超过 10 。 2 3 2 解： f ( x) x 4x 10 f ( x) 3x2 8x 0, x [1,2] 即 f ( x) 严格单调增加，又 f (1) f (2) 0 ，所以方程在[1,2]上有 唯一实根。 ba 1 2 令 2k 1 2 10 ，得到 k 6.64 ，取 k 7 ，即至少二分7次 。计算过程如下：
由 f ( x) 0 转化为 x ( x) 时，迭代函数 ( x) 不是唯一的， ( x) 不同，会产生不同的序列{xk } ，从而收敛情况也不 一样。
§2 迭代法及其迭代收敛的加速方法
几何意义： * x x ( x ) 求方程 的根 ，在几何上就是求直线 y x与曲线 y ( x) 交点 P* 的横坐标，如图所示。从图中可以看出， * ( x ) ( x ) x 当迭代函数 的导数 在根 处满足不同条件时，迭
特点：运算简单，方法可靠，对函数只要求在区间上连续 ；但收敛速度慢，不能用来求复数根及偶数重根。常用于为 其它求根方法提供较好的近似初始值。
§2 迭代法及其迭代收敛的加速方法
迭代法（逐次逼近）

第7章非线性方程组的数值解法

第7章非线性方程组的数值解法
( 1, 1 )
f 1 y f 2 2 y
2 y ( 1,1 ) 2
( 1,1 )
( y 3) ( 1, 1 )
( 1, 1 )
( x 1) ( 1 , 1 ) 2
( 1,1 )
f 1 f 2 2 2[ 2 * ( 3) ( 2 ) * ( 2 )] 4 f1 f2 g10 x ( 1,1) x ( 1,1) x f 1 f 2 g 2 2[ 2 * ( 3) 2 * ( 2 )] 20 20 y y f 1 y f 2 ( 1, 1 ) ( 1, 1 )
完
f ( x0 h, y0 k ) f ( x0 , y0 ) ( h k ) f ( x0 , y0 ) x y 1 2 ( h k ) f ( x 0 , y0 ) 2! x y 1 n ( h k ) f ( x 0 , y0 ) n! x y 1 n 1 ( h k ) f ( x0 h, y0 k ) ( n 1)! x y
2
2
令
0
得 f 1 f 1 ( g10 x g 20 y ) f 1 ( g10 ( g f 1 g f 1 ) 2 ( g 10 20 10 x y f 2 g 20 x f 2 g 20 x f 2 ) f2 y f 2 2 ) ( x y
1
f 1 ( x 0 , y0 ) f ( x , y ) 2 0 0
从n到n+1的迭代格式为：
f 1 ( x n , y n ) xn 1 x n x y y f 2 ( xn , yn ) n 1 n x

第7章 非线性方程的数值解法

第7章 非线性方程的数值解法

设 0为给定精 度要求，试确定分半次 数k 使
x* xk
ba 2k
由 于2k ， 两 边 取 对 数 ， 即 得
ba
k ln(b a) ln
ln 2
数值分析
18/47
§例1： 5.用2 二二分分法 求 法x3 4x2 10 0在[1,2]内 的 根 ，
要 求 绝 对 误 差 不 超 过1 102。 2
第七章 非线性方程的数值解法
数值分析
本章内容
§7.1 方程求根与二分法 §7.2 不动点迭代及其收敛性 §7.4 牛顿法 §7.5 弦截法
数值分析
2/47
本章要求
1. 掌握二分法基本原理，掌握二分法的算法 流程;
2. 掌握理解单点迭代的基本思想，掌握迭代 的收敛条件；
3. 掌握Newton迭代的建立及几何意义，了解 Newton迭代的收敛性；
27/47
§ 7.2 不动点迭代法及其收敛性
不动点迭代的几个重要问题： 1、迭代格式的构造； 2、初值的选取； 3、敛散性的判断；☆ 4、收敛速度的判断。
数值分析
28/47
§ 7.2 不动点迭代法及其收敛性
三.压缩映射原理（整体收敛性）
考虑方程x g( x), g( x) C[a, b], 若
则f (x)=0在[a, b]内必有一根。
二. 过程
将区间对分，判别f (x)的符号，逐步缩小有根区 间。
数值分析
14/47
§7.1.2 二分法
三. 方法
取xmid=0.5*(a+b)
若f(xmid) < (预先给定的精度)，则xmid即为根。
否则，若f (a)*f (xmid)<0，则取a1=a，b1=xmid 若f (a)*f (xmid)>0，则取a1=xmid，b1=b 此时有根区间缩小为[a1, b1]，区间长度为 b1-a1=0.5*(b-a)

(完整版)数值分析重点公式

(完整版)数值分析重点公式

第一章非线性方程和方程组的数值解法i 12)迭代法收敛阶：lim 一p c 0,若p 1则要求0 c 1i3) 单点迭代收敛定理：定理一：若当x a,b 时，(x) a,b 且 '(x) l 1， x a,b ，则迭代格式收敛于唯一的根；定理二：设 (x)满足：①xa,b 时， (x) a,b ，0, j 1,L ,P 1, (P)( )0( Taylor 展开证明)4) --------------------------------------------------- Newton 迭代法：x 1 x，平方收敛f (x)5) Newton 迭代法收敛定理：设f (x)在有根区间 a,b 上有二阶导数，且满足：①： f (a)f(b) 0 ；②： 1f (x)0,x a,b ；③：f 不变号,x a,b④：初值 x 0 a,b 使得 f (x) f (x)0 ；则Newt on 迭代法收敛于根。

1) 二分法的基本原理，误差:2k② x ,,x 2a,b ,有(xj(x 2) lx , x 2 ,0 l 1则对任意初值x 0 a,b 迭代收敛，且:1 —X i 1 x 1 l l i---- X 1 X o 1 l定理三：设(x)在 的邻域内具有连续的一阶导数, 敛性；且'()1，则迭代格式具有局部收定理四：假设 (x)在根的邻域内充分可导，则迭代格式x 1(xj 是P 阶收敛的(j)()6）多点迭代法：X j 1 X jf (X i)f(x) f(X j 1)X i x 1f (X j) f(X i 1)X i X jf (X i) f (X j 1) f(X 1) f(X)收敛阶：P 1 527）Newt on迭代法求重根（收敛仍为线性收敛），对Newt on法进行修改①：已知根的重数r，X i X「鵲（平方收敛）②：未知根的重数：X i 1叫u(X)u (X i)f (X)帀，为f （X）的重根，则为U（X）的单根。

Ch7 非线性方程与方程组的数值解法(2)

Ch7 非线性方程与方程组的数值解法(2)
( g ( x) x) 2 ( x) x . g ( g ( x)) 2 g ( x) x
4 / 19
几何意义 Aitken 加速：
y y = g(x)
一般地有：
( x K 1 x K )2 ˆ xK xK xK 2 xK 1 xK 2
y=x
15 / 19
例 再求x 3 x 1 0在1.5附近的根x * .
解：依次用牛顿法 0 1.5，x0 0.6，简化牛顿法 0 0.6， x x 牛顿下山法 1，折半， 1 / 32，计算结果如下：
k 0 1 2 3 4 xk 1.5 1.34783 1.32520 1.32472 xk 0.6 17.9 发散 xk 0.6 1.140625 1.36181 1.32628 1.32472 f(xk) -1.384 -0.656643 0.1866 0.00667 0.0000086
x0 , x1 g ( x0 ), x 2 g ( x1 ), ˆ x 0 , x3 g ( x 2 ), ˆ x1 , x 4 g ( x3 ), ......
P(x1, x2) P(x0, x1)
ˆ x K 比x K 收敛得略快。
Steffensen 加速：
x x1 x* x2 x0
2 / 19

2 x1
2 x1x * x * x2 x0 x2 x * x0 x * x * ,
2 2
x1 x * x0 x * x2 x * x1 x *
2 2 2 x2 x0 x1 x2 x0 2 x0 x1 x0 x2 x0 x1 x* x0 x2 2 x1 x0 x2 2 x1 x0

非线性方程(组)的解法


lnim(bn
an )
lim
n
2n1
(b
a)
0
lim
n
an
lim
n
bn
x
取
x
cn
1 2
(an
bn
)为
x 的近似解。
7
二分法
迭代终止准则
an - bn
即
x - cn
bn an 2
2
8
2.2一般迭代法
2.2.1 迭代法及收敛性
对于 f (x) 0 有时可以写成 x (x) 形式 如： x3 x 1 0 x 3 x 1
12
例题
例2.2.1 试用迭代法求方程 f (x) x3 x 1 0
在区间(1，2)内的实根。 解：由 x 3 x 1建立迭代关系
xk1 3 xk 1 k=0,1,2,3…… 计算结果如下:
13
例题
精确到小数点后五位
x 1.32472 1 105
2
14
例题 但如果由x x3 1建立迭代公式
xk1 xk3 1 k 1,2,...
仍取 x0 1.5，则有 x1 2.375 ，x2 12.39 显 然结果越来越大，{xk }是发散序列
15
2.3 Newton迭代法
设x*是方程f (x) = 0的根， 又x0 为x* 附近的一个值，
将f (x) 在x0 附近做泰勒展式：
f (x)
二分法
用二分法(将区间对平分)求解。
令
a1
a, b1
b, c1
1 2
(a1
b1 )
若 f (a1) f (c1) 0，则[a1, c1] 为有根区间，否 则 [c1,b1]为有根区间

数值分析 第七章 非线性方程(组)的数值解法.

x0
y
,这样就可得缩小有根区间 a1 , b1
y=f(x) y=f(x)
x* a a1 x1 a2 x* x0 b1 b2 b a x0 a1 x1 a2 b b1 b2
23/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis
§7.2 二分区间法 ② 对压缩了的有根区间 a1 , b1 施行同样的手法, b 即取中点 x a 2 ,将区间 a1 , b1 再分为两半,然 后再确定有根区间 a 2 , b2 ,其长度是 a1 , b1 的 二分之一。
长h=(B-A)/n(n是正整数),在[A,B]内取定节点:xi=x0＋ih (i=0,1,2,…,n),从左至右检查f (xi)的符号,如发现xi与端点x0 的函数值异号,则得到一个缩小的有根子区间［xi-1,xi］。
y
0 A
a1 b1 a2 b2
B
x
20/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis
§7.1 引言
数值解法的三个步骤 ① 判定根的存在性。即方程有没有根？如果有 根，有几个根？ ② 确定根的分布范围。即将每一个根用区间隔 离开来，这个过程实际上是获得方程各根的 初始近似值。（隔离根） ③ 根的精确化。将根的初始近似值按某种格式 逐步精确化，直到满足预先要求的精度为止。
10/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis
3/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis
§7.1 引言 当 f (x)不是x的线性函数时，称对应的函数方程
f (x)=0为非线性方程。

非线性方程数值解法


对分区间法
对分法的基本思想


对分法的基本思想是在平分有根区间的 过程中，逐步缩小有根区间. 设函数f(x)在区间[a, b]上连续，且f(a) f(b)<0 ，则方程f(x)=0在(a, b)内至少有一 个根.为简便起见，假定方程f(x)=0在(a, b) 内仅有一个根.这样(a, b)为有根区间.这 时可用下面的对分法求方程f(x)=0的近似 根.

迭代法的整体收敛性


定理1 （迭代收敛定理）设(x)在[a, b]上具有一阶 导数，且 1°x[a, b] ，总有(x)[a, b] ； 2°存在0m<1，使x(a, b) ，有'(x)m 则 1°方程x=(x)在[a, b]内有且仅有一根α ，其中α 为对任意初值x0 [a, b]由迭代过程xk+1=(xk)所产生 序列的极限. m xk xk xk 1 2°有估计式

求根步骤


（1）确定所给方程存在多少个根. （2）进行根的隔离，找出每个有根区间， 有根区间内的任一点都可看成是该根的 一个近似值. （3）逐步把近似根精确化，直到足够精 确为止.
根的隔离
根的隔离

确定出若干个小区间，使每个小区间有 且仅有方程f(x)=0的一个根，这个步骤称 为根的隔离.其中每个有根小区间都称为 隔根区间.
第三章
非线性方程的数值解法
根的概念
给定方程f(x)=0，如果有α使得f(α)=0， 则称α为f(x)=0的根或f(x)的零点. 设有正整数m使得f(x)=(x-α)mg(x) 且g(α)0 ，则当m2时，称α为f(x)=0的 m重根；当m=1时，称为f(x)=0的单根. 本章只讨论实根的求法.

非线性方程组数值解法

(k ) (k )
1
f (x )
1
(k )
( k 1)
x
(k )
f ( x )
f (x )
(k )
称上述公式为Newton迭代格式。 Newton迭代方法在实际迭代时，转化为求方程组的解
f ( x )( x
(k )
( k 1)
x ) f (x )
(k ) (k ) (k )
Broyden秩1方法的迭代公式变为：
x x ( A ) f ( x ) , k 0 , 1 , 2 ( 0) 1 1 ( 0) ( A ) f ( x )
( k 1) (k ) ( k ) 1 (k)
Broyden秩1算法 ( 0) n 选取初值 x R
(1)
x
( 0)
x
( 0)
0.8 0.88
计算结果如下
要求 精度 0.001 迭代 次数 2
方程组的近似解
(1.0000 1.0000)
0.0001
3
(1.0000 1. 0000)
Broyden秩1方法（拟Newton方法中的一种）
利用多元函数的Taylor展开公式得
(A ) (k ) ( k ) 1 (k ) x (A ) f (x )
( k ) 1
满足给定的精度要求，迭代终止。
Broyden秩1算法 ( 0) n 选取初值 x R
计算
( A ) (f ( x ))
( 0)
( 0) 1
1
x x (A ) f (x )
(1) ( 0) ( 0)
A y ( k 1) T ( k 1) (y ) y
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第三章 非线性方程(组)的数值解法一．取步长1h =，试用搜索法确立3()25f x x x =--含正根的区间，然后用二分法求这个正根，使误差小于310-。

【详解】因为是要寻找正根，因此，可选含根区间的左端点为0。

(0)5f =-，(1)5f =-，(2)1f =-，(3)16f =，因此，(2,3)中有一个正根。

这就确立了含根区间。

接下来，我们用二分法求这个正根，使误差小于310-，计算结果如下表 迭代次数k ak b k x0 2 3 2.5 1 2 2.5000 2.250 0 2 2 2.2500 2.125 0 3 2 2.1250 2.062 5 4 2.0625 2.1250 2.093 8 5 2.0938 2.1250 2.109 4 6 2.0938 2.1094 2.101 6 7 2.0938 2.1016 2.097 7 8 2.0938 2.0977 2.095 7 92.09382.09572.094 7二．对方程2()2sin 20f x x x =--=，用二分法求其在区间[]1.5,2内的根，要求误差小于0.01。

【详解】用二分法求解方程在[]1.5,2内的根，要求误差小于0.01，计算结果如下表： 迭代次数k ak b k x0 1.5 2 1.75 1 1.7500 2.0000 1.8750 2 1.8750 2.0000 1.9375 3 1.9375 2.0000 1.9688 4 1.9375 1.9688 1.9531 51.95311.96881.9609三．用不动点迭代法，建立适当的迭代格式，求方程3()10f x x x =--=在0 1.5x =附近的根，要求误差小于610-。

【详解】310x x --=，等价于x =。

这样，可以建立不动点迭代格式1k x +=当0x ≥时，总有23110(1)133x -'<=+≤<，因此，迭代格式对于任意初始值00x ≥总是收敛的。

取0 1.5x =，用所建立的不动点迭代格式求解近似根，要求误差小于610-，计算结果如下表：迭代次数k x1.51 1.357212 1.330863 1.325884 1.324945 1.32476 6 1.324737 1.32472 81.32472四．建立收敛的不动点迭代格式，求解方程3()250f x x x =--=在[]2,3内满足精度要求810ε-=的根。

【详解】方程恒等变形，得到x =格式1k x +=[]2,3x ∈，23220(25)133x -'<=+<<，且23<=<。

因此，对任意[]02,3x ∈，不动点迭代格式都收敛。

选0 2.5x =，用所建立的不动点迭代格式求方程在[]2,3的近似根，计算结果如下表迭代次数k x0 2.5 12.1544346902 2.1036120293 2.0959274104 2.094760545 5 2.0945832506 2.0945563097 2.0945522158 2.0945515939 2.094551498 10 2.094551484 112.094551481五．为求方程3210x x --=在 1.5x =附近的一个根，将方程改写为下列等价形式，并建立相应的迭代格式： (1) 211x x=+，迭代格式为1211k k x x +=+；(2) 321x x =+，迭代格式为x =； (3) 211x x =-，迭代格式为1k x += 讨论每种迭代格式的收敛性，并用格式(2)求出精度为210-的根的近似值。

【详解】 (1)21()x x ϕ=，32()x x ϕ'=-，32(1.5)11.5ϕ'=<，因此，该迭代格式在 1.5x =是局部收敛的。

(2) ()x ϕ=2232()(1)3x x x ϕ-'=+，2232(1.5) 1.5(1 1.5)13ϕ-'=⨯⨯+<因此，该迭代格式在 1.5x =是局部收敛的。

(3) ()x ϕ=，()x ϕ'=，(1.5)ϕ'==因此，该迭代格式在 1.5x =是不局部收敛的。

现在用格式(2)求出精度为210-的根的近似值，选0 1.5x =，计算结果如下表：迭代次数k x0 1.5 1 1.4812 21.4727六．给定方程1()cos 02f x x x =-=(1)分析该方程有几个根；(2)用迭代格式11cos 2k k x x +=求出这些根，要求误差小于310-。

【详解】(1)11(0)0cos0022f =-=-<,1(1)1cos102f =->,因此，(0,1)内必有根。

1()1sin 02f x x '=+>，因此，()f x 单调递增。

这样，方程有且只有一个根。

(2) 1()cos 2x x ϕ=，1()12x ϕ'≤<，因此，对任意0x ，迭代格式都是收敛的。

取00x =，用该迭代格式求解，要求误差小于310-。

计算结果如下迭代次数k x1 0.50002 0.43883 0.45264 0.4496 50.4503七．用Newton 法求解3()250f x x x =--=在区间[]2,3内满足精度要求810ε-=的根。

【详解】3()25f x x x =--，因此，其Newton 迭代格式为312()25()32k k k k k k k k f x x x x x x f x x +--=-=-'- 选初始值为0 2.5x =，用Newton 法求解方程在[]2,3内满足精度要求810ε-=的根，计算结果如下表：迭代次数k x0 2.5 1 2.164179104 2 2.097135356 3 2.094555232 4 2.094551482 52.094551482八．用Newton 建立求解正数a310ε-=的近似值。

【详解】是方程20x a-=的正根，Newton迭代格式为211()22kk k kk kx a ax x xx x+-=-=+。

310ε-=的近似值。

考虑到1011<<，我们可以取初始值10x=。

计算结果如下表：迭代次数kx0 101 10.75002 10.72383 10.7238九．的Newton迭代公式，使公式中既无开方运算又无除法运算，并取0.5x=310ε-=的近似值。

【详解】21xa-=的正根，自然也是方程21ax-=Newton迭代格式可以是23131()312()22k kk k k k kkkaf x xx x x x axf xx+-=-=-=-'-取0.5x=310ε-=的近似值，计算结果如下表：迭代次数k x0 0.51 0.56252 0.5768 30.5773十.用割线法求解3()250f x x x =--=在区间[]2,3内满足精度要求810ε-=的根。

【详解】3()25f x x x =--，由此，建立相应的割线法迭代格式如下311133111()(25)()()(25)(25)k k k k k k k k k k k k k k k k x x x x x x f x x x x f x f x x x x x ++++++--=-=--------- 以下用该迭代格式求方程在区间[]2,3内满足精度要求810ε-=的根，选02x =，13x =，计算结果如下表：迭代次数k x0 2 1 3 2 2.058823529 3 2.081263660 4 2.094824146 5 2.094549431 6 2.094551481 72.094551482十一.给定非线性方程20.1 3.060x x --=(1)证明该方程只有唯一正根，并取步长1h =搜索含有该正根的区间；(2) 选定适当的初值分别用Newton 法和割线法求解该正根，要求误差小于310-。

【详解】 (1)3.0601-<，因此，按照一元二次方程的理论，方程有一正根，一负根。

令2()0.1 3.06f x x x =--，则(0) 3.06f =-，(1)10.1 3.06 2.160f =--=-<，(2)40.2 3.060.740f =--=>，因此，(1,2)为含正根的区间。

(2) Newton 迭代格式为21()0.1 3.06()20.1k k k k k k k k f x x x x x x f x x +--=-=-'- 割线法迭代格式为222111111()()(0.1 3.06)(0.1 3.06)()(0.1 3.06)k k k k k k k k k k k k k k k kf x f x x x x x x x f x x x x x x x x ++++++------=-=-----取0 1.5x =，利用上面所建立的Newton 迭代格式，求方程的近似解，要求误差小于310-，计算结果如下表： 迭代次数 k x0 1.5 1 1.831034483 2 1.800270388 3 1.800000021 41.8000000005 1.800000000取01x=，12x=，用上面建立的割线法求方程的近似解，要求误差小于310-，计算结果如下表：迭代次数kx0 11 22 1.7448275863 1.7969725644 1.8000485305 1.7999999586 1.800 000 0007 1.800000000。