顺德区网站设计,logo 在线设计,wordpress备案,u8无可用数据源研究背景
形如 x − t a n x 0 x-tanx0 x−tanx0、 x l n x e − x 2 s i n x 0 xlnxe^{-x^2}sinx0 xlnxe−x2sinx0等称为非线性方程#xff0c;自变量之间并非简单的线性关系#xff0c;这种问题我们无法通过其结构求解#xff0c;需要其他的逼近方式#xff0c;本章…研究背景
形如 x − t a n x 0 x-tanx0 x−tanx0、 x l n x e − x 2 s i n x 0 xlnxe^{-x^2}sinx0 xlnxe−x2sinx0等称为非线性方程自变量之间并非简单的线性关系这种问题我们无法通过其结构求解需要其他的逼近方式本章将基于该问题介绍两种方法——二分法迭代法。
二分法
预备知识
零点定理 若 f ( x ) ∈ [ a , b ] f(x)\in[a,b] f(x)∈[a,b]且 f ( a ) f ( b ) 0 f(a)f(b)0 f(a)f(b)0则 f ( x ) f(x) f(x)在 ( a , b ) (a,b) (a,b)内至少有一个零点若 f ( x ) f(x) f(x)为单调函数则 f ( x ) f(x) f(x)有唯一零点。
重根判别方法 设 f ( x ) f(x) f(x)在 x x x有n阶导数则 x x x为 f ( x ) 0 f(x)0 f(x)0的m重根的充要条件为 f ( x ) f ′ ( x ) f m − 1 ( x ) 0 且 f m ( x ) ! 0 f(x)f(x)f^{m-1}(x)0且f^m(x)!0 f(x)f′(x)fm−1(x)0且fm(x)!0。
求实根的二分法
基本思想为 将有根区间一分为二等分为两个区间判断根再哪一个更小的区间舍去无根的小区间再把有根的小区间等分如此重复直到找到满足精度的近似根。
算法流程 取终点 x 0 a b 2 x_0\frac{ab}{2} x02ab若 f ( x 0 ) 0 , x 0 f(x_0)0,x_0 f(x0)0,x0为所求否则计算 f ( a ) f ( x 0 ) f(a)f(x_0) f(a)f(x0)的符号 0 0 0取区间 [ x 0 , b ] [x_0,b] [x0,b] 0 0 0取 [ a , x 0 ] [a,x_0] [a,x0]重复上述过程无穷多次后即为精确解 lim k → ∞ x k x \lim_{k \to \infty}x_kx limk→∞xkx但计算中不可能迭代无穷多次也不可能得知精确解故一般采用前后两次迭代逼近的程度来衡量 ∣ x k − x k − 1 ∣ ≤ b k − a k 2 b − a 2 k 1 |x_k-x_{k-1}|\le\frac{b_k-a_k}{2}\frac{b-a}{2^{k1}} ∣xk−xk−1∣≤2bk−ak2k1b−a取精度 b − a 2 k 1 ε \frac{b-a}{2^{k1}}\varepsilon 2k1b−aε迭代步数为 k l n ( b − a ) − l n 2 ε l n 2 k\frac{ln(b-a)-ln2\varepsilon}{ln2} kln2ln(b−a)−ln2ε
例题二分法求 f ( x ) x 2 − x − 1 0 f(x)x^2-x-10 f(x)x2−x−10的正根要求误差不超过0.05。 解 设 f ( x ) x 2 − x − 1 , f ( 1 ) − 1 0 , f ( 2 ) 1 0 f(x)x^2-x-1,f(1)-10,f(2)10 f(x)x2−x−1,f(1)−10,f(2)10故有根区间为 [ − 1 , 2 ] [-1,2] [−1,2]该函数在区间内单调 k − l n 0.1 l n 2 10 l n 2 3.3 k\frac{-ln0.1}{ln2}\frac{10}{ln2}3.3 kln2−ln0.1ln2103.3取步长k4求其根表示为
k a k a_k ak b k b_k bk x k x_k xkf(x)符号0121.5-11.521.7521.51.751.62531.51.6251.5625-41.56251.6251.59375
答根为1.59375。
该方法实现简单普及性高对方程只要求其连续即可但收敛速度缓慢下面介绍一种加速收敛的方法—迭代法。
迭代法
基本思想 f ( x ) 0 x g ( x ) f(x)0xg(x) f(x)0xg(x) g ( x ) g(x) g(x)为迭代函数 x k 1 g ( x k ) x_{k1}g(x_k) xk1g(xk)给定 x 0 x_0 x0可计算 x 1 . . . . x n x_1....x_n x1....xn若该数列收敛则称迭代法 x k 1 g ( x k ) x_{k1}g(x_k) xk1g(xk)收敛否则发散。
若 x ∗ x^* x∗满足 x ∗ g ( x ∗ ) x^*g(x^*) x∗g(x∗)则称 x ∗ x^* x∗为 g ( x ) g(x) g(x)的不动点。 若 lim k → ∞ x k x ∗ g ( x ) \lim_{k \to \infty}x_kx^*g(x) limk→∞xkx∗g(x)连续 x ∗ lim k → ∞ x k 1 lim k → ∞ g ( x k ) g ( lim k → ∞ x k ) g ( x ∗ ) x^*\lim_{k \to \infty}x_{k1}\lim_{k \to \infty}g(x_k)g(\lim_{k \to \infty}x_k)g(x^*) x∗limk→∞xk1limk→∞g(xk)g(limk→∞xk)g(x∗)
该过程重点在于 1如果构造 g ( x ) g(x) g(x) 2 g ( x ) g(x) g(x)满足何种条件能保证数列 x n {x_n} xn收敛 3收敛速度如何衡量
该方法的几何意义为以直代曲用切线零点代替曲线零点不断逼近坐标轴的过程。
迭代格式的适定性与收敛性
定义如果 x 0 ∈ [ a , b ] x_0\in[a,b] x0∈[a,b]若按 x k 1 g ( x k ) x_{k1}g(x_k) xk1g(xk)生成的序列 x k ∈ [ a , b ] {x_k}\in[a,b] xk∈[a,b]则称迭代格式是适定的适定性是迭代格式能够继续下去的重要条件。
例如求 x e x − 1 0 xe^{x}-10 xex−10在 x 0.5 x0.5 x0.5附近的根。 解: x e − x xe^{-x} xe−x构造迭代格式 x k 1 e − x k , x 0 0.5 x_{k1}e^{-x_k},x_00.5 xk1e−xk,x00.5,可继续迭代 e x 1 x , x − l n x e^x\frac{1}{x},x-lnx exx1,x−lnx构造 x k 1 − l n x k , x 0 0.5 , x 4 0 x_{k1}-lnx_k,x_00.5,x_40 xk1−lnxk,x00.5,x40时终止
定理一设 g ( x ) ∈ [ a , b ] g(x)\in[a,b] g(x)∈[a,b]且满足如下条件 1,任意 x ∈ [ a , b ] x\in[a,b] x∈[a,b]总有 g ( x ) ∈ [ a , b ] g(x)\in[a,b] g(x)∈[a,b] 2,存在 L ∈ [ 0 , 1 ] , 使 ∣ g ( x ) − g ( y ) ∣ ≤ L ∣ x − y ∣ x y 为 [ a , b ] 内的任意数 L\in[0,1],使|g(x)-g(y)|\le L|x-y|xy为[a,b]内的任意数 L∈[0,1],使∣g(x)−g(y)∣≤L∣x−y∣xy为[a,b]内的任意数 则 g ( x ) g(x) g(x)在 [ a , b ] [a,b] [a,b]上存在唯一不动点 x ∗ x^* x∗对任意 x ∈ [ a , b ] x\in[a,b] x∈[a,b]迭代法适定且收敛但该条件很不好证明故多采用定义二。
定理二若 g ( x ) ∈ [ a , b ] g(x)\in[a,b] g(x)∈[a,b]且满足如下条件 1任意 x ∈ [ a , b ] 有 g ( x ) ≤ [ a , b ] x\in[a,b]有g(x)\le[a,b] x∈[a,b]有g(x)≤[a,b] 2存在 0 ≤ L ≤ 1 使对任意 x ∈ [ a , b ] 有 ∣ g ′ ( x ) ∣ ≤ L 0\le L\le1使对任意x\in[a,b]有|g(x)|\le L 0≤L≤1使对任意x∈[a,b]有∣g′(x)∣≤L该定理用导数代替了验证过程。 则 x k 1 g ( x k ) ≤ L k 1 − L ∣ x − x 0 ∣ x_{k1}g(x_k)\le\frac{L^k}{1-L}|x-x_0| xk1g(xk)≤1−LLk∣x−x0∣
注 1不等式为停机标准 ∣ x k 1 − x k ∣ ε |x_{k1}-x_k|\varepsilon ∣xk1−xk∣ε时 ∣ x ∗ − x k ∣ ≤ ε 1 − L |x^*-x^k|\le\frac{\varepsilon}{1-L} ∣x∗−xk∣≤1−Lε 2先验估计用于估计达到 ε \varepsilon ε精度所需迭代的步数为 L k 1 − L ∣ x 1 − x 0 ∣ ε \frac{L^k}{1-L}|x_1-x_0|\varepsilon 1−LLk∣x1−x0∣ε从而 k l n ( − ( 1 − L ) ε ( x 1 − x 0 ) ) l n L k\frac{ln(\frac{-(1-L)\varepsilon }{(x_1-x_0)})}{lnL} klnLln((x1−x0)−(1−L)ε) 3L越小收敛速度越快。
局部收敛性与收敛阶
定义 x ∗ 为 g ( x ) x^*为g(x) x∗为g(x)的不动点对 δ 0 , 称 N ( x ∗ , δ ) [ x ∗ − δ , x ∗ δ ] \delta0,称N(x^*,\delta)[x^*-\delta,x^*\delta] δ0,称N(x∗,δ)[x∗−δ,x∗δ]为 x ∗ x^* x∗的一个邻域若存在一个邻域使对任意 x ∈ N ( x ∗ , δ ) x\in N(x^*,\delta) x∈N(x∗,δ)按 x k 1 g ( x k ) x_{k1}g(x_k) xk1g(xk)生成的 x k ∈ N ( x ∗ , δ ) {x_k}\in N(x^*,\delta) xk∈N(x∗,δ)且 lim x → ∞ x k x ∗ \lim_{x \to \infty}x_kx^* limx→∞xkx∗则称迭代格式具有迭代收敛性。 即在邻域内无穷次迭代后能获得精确解。
定理一设 g ( x ) 在 x g ( x ) g(x)在xg(x) g(x)在xg(x)的根 x ∗ x^* x∗邻域内有连续的一阶导数且 ∣ g ′ ( x ∗ ) ∣ 1 |g(x^*)|1 ∣g′(x∗)∣1迭代法具有局部收敛性。 注实际使用时往往用 ∣ g ′ ( x 0 ) ∣ 1 |g(x_0)|1 ∣g′(x0)∣1代替
n阶导数1收敛则收敛阶为n。
例题迭代函数 g ( x ) x c ( x 2 − 3 ) g(x)xc(x^2-3) g(x)xc(x2−3)讨论1写出迭代格式产生 k {k} k收敛于 3 \sqrt{3} 3 问c应为何值2c为何值时收敛速度最快 解1迭代格式 x k 1 g ( x k ) x k c ( x k 2 − 3 ) g ′ ( x ) 1 2 c x ∣ g ′ ( 3 ) ∣ ∣ 1 2 3 c ∣ 1 − 3 2 c 0 x_{k1}g(x_k)x_kc(x_k^2-3)g(x)12cx|g(\sqrt{3})||12\sqrt{3}c|1-\frac{\sqrt{3}}{2}c0 xk1g(xk)xkc(xk2−3)g′(x)12cx∣g′(3 )∣∣123 c∣1−23 c0 2 g ′ ( 3 ) 0 , 1 2 3 c 0 , c − 3 6 g(\sqrt{3})0,12\sqrt{3}c0,c-\frac{\sqrt{3}}{6} g′(3 )0,123 c0,c−63 收敛最快
Newton迭代法
基本思想满足一般理论的特殊迭代法 f ( x ) 0 f(x)0 f(x)0先假设 x k x_k xk为 f ( x ) 0 f(x)0 f(x)0的近似根 f ′ ( x k ) ! 0 f(x_k)!0 f′(xk)!0将 f ( x ) f(x) f(x)在 x k x_k xk处作Taylor展开 f ( x ) ≈ f ( x k ) f ′ ( x k ) ( x − x k ) f ′ ′ ( ξ ) 2 ! ( x − x k ) 2 f(x)\approx f(x_k)f(x_k)(x-x_k)\frac{f(\xi)}{2!}(x-x_k)^2 f(x)≈f(xk)f′(xk)(x−xk)2!f′′(ξ)(x−xk)2舍去余项后 f ( x ) ≈ f ( x k ) f ′ ( x k ) ( x − x k ) f(x)\approx f(x_k)f(x_k)(x-x_k) f(x)≈f(xk)f′(xk)(x−xk) f ( x k ) f ′ ( x k ) ( x − x k ) 0 f(x_k)f(x_k)(x-x_k)0 f(xk)f′(xk)(x−xk)0故 x x k − f ( x k ) f ′ ( x k ) xx_k-\frac{f(x_k)}{f(x_k)} xxk−f′(xk)f(xk)不动点带入获得迭代函数 g ( x ) x − f ( x ) f ′ ( x ) g(x)x-\frac{f(x)}{f(x)} g(x)x−f′(x)f(x)。
该方法的几何意义是以直代曲沿曲线方向不断作切线和x轴的交点作为下一次切线起点形成一个不断逼近 x ∗ x^* x∗的数列。
例题Newton迭代法求 f ( x ) x 3 2 x − 6 f(x)x^32x-6 f(x)x32x−6在1.5附近的根。 解 f ′ ( x ) 3 x 2 2 f(x)3x^22 f′(x)3x22Newton迭代公式 x k 1 x k − x k 3 2 x k − 6 3 x k 2 2 x_{k1}x_k-\frac{x_k^32x_k-6}{3x_k^22} xk1xk−3xk22xk32xk−6取 x 0 1.5 x_01.5 x01.5迭代运算 x 1 1.4571429 x 2 1.4561647 x_11.4571429x_21.4561647 x11.4571429x21.4561647 可以看到Newton迭代法的收敛速度还是比较快的。
Newton迭代法的收敛性与收敛阶
局部收敛性定理 设 x ∗ x^* x∗为 f ( x ) 0 f(x)0 f(x)0的单根即 f ( x ∗ ) 0 , f ′ ( x ∗ ) ! 0 f(x^*)0,f(x^*)!0 f(x∗)0,f′(x∗)!0则Newton迭代格式 x k 1 x k − f ( x k ) f ′ ( x k ) x_{k1}x_k-\frac{f(x_k)}{f(x_k)} xk1xk−f′(xk)f(xk)至少二阶收敛。
非局部收敛性定理 设 f ( x ) ∈ c 2 [ a , b ] f(x)\in c^2[a,b] f(x)∈c2[a,b]且满足如下条件 1 f ( a ) f ( b ) 0 f(a)f(b)0 f(a)f(b)0 2 f ′ ( x ) ! 0 , 任意 x ∈ [ a , b ] f(x)!0,任意x\in [a,b] f′(x)!0,任意x∈[a,b] 3 x ∈ [ a , b ] 时有 f ′ ( x ) 不变号 x\in[a,b]时有f(x)不变号 x∈[a,b]时有f′(x)不变号 4 任意 x 0 ∈ [ a , b ] , 使 f ( x 0 ) f ′ ′ ( x 0 ) 0 任意x_0\in[a,b],使f(x_0)f(x_0)0 任意x0∈[a,b],使f(x0)f′′(x0)0 则由Newton迭代格式确定的 x k {x_k} xk收敛于 f ( x ) 0 f(x)0 f(x)0在 [ a , b ] [a,b] [a,b]有唯一根 x ∗ x^* x∗
简化后的Newton法 该迭代法主要的计算量来自导数故简化后采用 x k 1 x − f ( x ) C x_{k1}x-\frac{f(x)}{C} xk1x−Cf(x)用常数C代替之 C f ′ ( x 0 ) Cf(x_0) Cf′(x0)该方法使用固定点的导数作为常数来代替后续导数计算固然简化了计算但收敛速度也随之下降。
求重根的Newton法
设 x ∗ x^* x∗为 f ( x ) 0 f(x)0 f(x)0的重根 f ( x ∗ ) f ′ ( x ∗ ) . . . f n 1 ( x ∗ ) 0 f(x^*)f(x^*)...f^{n1}(x^*)0 f(x∗)f′(x∗)...fn1(x∗)0且 f n ( x ∗ ) ! 0 f^n(x^*)!0 fn(x∗)!0 f ( x ) ( x − x ∗ ) A ( x ) f(x)(x-x^*)A(x) f(x)(x−x∗)A(x)显然 A ( x ∗ ) ! 0 A(x^*)!0 A(x∗)!0。
Newton迭代法 x k 1 x k − f ( x k ) f ′ ( x k ) g ( x ) x − f ( x ) f ′ ( x ) g ′ ( x ∗ ) 1 x_{k1}x_k-\frac{f(x_k)}{f(x_k)}g(x)x-\frac{f(x)}{f(x)}g(x^*)1 xk1xk−f′(xk)f(xk)g(x)x−f′(x)f(x)g′(x∗)1收敛 g ′ ( x ) f ( x ) f ′ ′ ( x ) [ f ′ ( x ) ] 2 g(x)\frac{f(x)f(x)}{[f(x)]^2} g′(x)[f′(x)]2f(x)f′′(x)故 g ′ ( x ∗ ) f ( x ∗ ) f ′ ′ ( x ∗ ) [ f ′ ( x ∗ ) ] 2 lim x → x ∗ g ( x ) − g ( x ∗ ) x − x ∗ g(x^*)\frac{f(x^*)f(x^*)}{[f(x^*)]^2}\lim_{x\to x^* \frac{g(x)-g(x^*)}{x-x^*}} g′(x∗)[f′(x∗)]2f(x∗)f′′(x∗)limx→x∗x−x∗g(x)−g(x∗)最后很复杂一同操作后得证 g ′ ( x ∗ ) 1 − 1 m g(x^*)1-\frac{1}{m} g′(x∗)1−m1
例题 x 3 − 3 x 2 4 0 x^3-3x^240 x3−3x240试用Newton迭代法求 x ∗ 2 x^*2 x∗2并证明收敛性求收敛阶。 解 f ( x ) x 3 − 3 x 2 4 f ′ ( x ) 3 x 2 − 6 x x k 1 x k − f ( x k ) f ′ ( x k ) x k − x k 3 − 3 x k 2 4 3 x k 2 − 6 x k f(x)x^3-3x^24f(x)3x^2-6xx_{k1}x_k-\frac{f(x_k)}{f(x_k)}x_k-\frac{x_k^3-3x_k^24}{3x_k^2-6x_k} f(x)x3−3x24f′(x)3x2−6xxk1xk−f′(xk)f(xk)xk−3xk2−6xkxk3−3xk24则 g ( x ) x − x 3 − 3 x 2 4 3 x 2 − 6 x g(x)x-\frac{x^3-3x^24}{3x^2-6x} g(x)x−3x2−6xx3−3x24若 ∣ g ′ ( 2 ) ∣ 1 |g(2)|1 ∣g′(2)∣1收敛 x ∗ 2 x^*2 x∗2为 f ( x ) f(x) f(x)的二重根根据 1 − 1 m ∣ g ′ ( 2 ) ∣ 1 2 1 1-\frac{1}{m}|g(2)|\frac{1}{2}1 1−m1∣g′(2)∣211故收敛且线性收敛。
Newton法改进
1 f ( x ) 0 f(x)0 f(x)0的重根 x ∗ x^* x∗的重数m已知则可得到 x k 1 x k − m f ( x k ) f ′ ( x k ) g ( x ) x − m f ( x ) f ′ ( x ) g ′ ( x ∗ ) 1 − m 1 m 0 x_{k1}x_k-m\frac{f(x_k)}{f(x_k)}g(x)x-m\frac{f(x)}{f(x)}g(x^*)1-m\frac{1}{m}0 xk1xk−mf′(xk)f(xk)g(x)x−mf′(x)f(x)g′(x∗)1−mm10故至少平方收敛。
2 f ( x ) 0 f(x)0 f(x)0的重根 x ∗ x^* x∗的重数m未知令 u ( x ) f ( x ) f ′ ( x ) u(x)\frac{f(x)}{f(x)} u(x)f′(x)f(x)若 x ∗ x^* x∗为 f ( x ) f(x) f(x)的m重根 x ∗ x^* x∗为 f ′ ( x ) f(x) f′(x)的m-1重根 x ∗ x^* x∗必为 u ( x ) u(x) u(x)的单根只需构造 u ( x ) 0 u(x)0 u(x)0的单根Newton法 x k 1 x k − u ( x k ) u ′ ( x k ) , u ′ ( x ) [ f ′ ( x ) ] 2 − f ( x ) f ′ ( x ) [ f ′ ( x ) ] 2 , x k 1 x k − f ( x k ) f ′ ( x k ) [ f ′ ( x k ) ] 2 − f ( x k ) f ′ ′ ( x k ) x_{k1}x_k-\frac{u(x_k)}{u(x_k)},u(x)\frac{[f(x)]^2-f(x)f(x)}{[f(x)]^2},x_{k1}x_k-\frac{f(x_k)f(x_k)}{[f(x_k)]^2-f(x_k)f(x_k)} xk1xk−u′(xk)u(xk),u′(x)[f′(x)]2[f′(x)]2−f(x)f′(x),xk1xk−[f′(xk)]2−f(xk)f′′(xk)f(xk)f′(xk)至少平方收敛。
例题1设 f ( x ) x 4 − 6 x 2 8 x − 3 f(x)x^4-6x^28x-3 f(x)x4−6x28x−3求 x 1 3 , x 2 1 x_13,x_21 x13,x21的二阶局部收敛的Newton法。 解首先判断单根还是重根 f ′ ( x ) 4 x 3 − 12 x 8 , x 1 3 , f ( − 3 ) 0 , f ′ ( − 3 ) ! 0 f(x)4x^3-12x8,x_13,f(-3)0,f(-3)!0 f′(x)4x3−12x8,x13,f(−3)0,f′(−3)!0所以 x 1 3 x_13 x13为单根用二阶收敛的呢我同法 x k 1 x k − x k 4 − 6 x k 2 8 x k − 3 4 x k 3 − 12 x k 8 x_{k1}x_k-\frac{x_k^4-6x_k^28x_k-3}{4x_k^3-12x_k8} xk1xk−4xk3−12xk8xk4−6xk28xk−3。 x 2 1 , f ( 1 ) 0 , f ′ ( 1 ) 0 , f ′ ′ ( 1 ) 0 , f ′ ′ ′ ( 1 ) ! 0 x_21,f(1)0,f(1)0,f(1)0,f(1)!0 x21,f(1)0,f′(1)0,f′′(1)0,f′′′(1)!0所以 x 2 1 x_21 x21为三重根方法同上二阶收敛的Newton法 x k 1 x k − 3 x k 4 − 6 x k 2 8 x k − 3 4 x k 3 − 12 x k 8 x_{k1}x_k-3\frac{x_k^4-6x_k^28x_k-3}{4x_k^3-12x_k8} xk1xk−34xk3−12xk8xk4−6xk28xk−3。
总结
本章介绍了非线性方程的数值解法二分法实现简单但收敛很慢迭代法主要是Newton迭代法用泰勒公式近似方程着重分析其收敛性和收敛阶该章公式很多很杂大量篇幅在于分析性质而非单纯计算到整理完毕整体也没消化完还需后面补足大致为确定适定性分析收敛性写出迭代格式计算收敛阶。
这也是数值分析的最后一章我们依次介绍了误差分析的方法、线性方程组的数值解法、函数插值的预测法、数值积分的近似计算法和本章非线性方程的数值解法这些方法我们以后未必能用得到但通过对这些方法学习我们如果能体会这种逼近和代替的思想也是很大的收获现实世界的很多问题我们没法精确求解分析构造相近的情景再解决也算是曲线救国了。
