热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

关于牛顿迭代法的初值以及收敛性的理解

文章目录定理描述初值对于牛顿迭代法的影响Newton下山法牛顿迭代法的优缺点定理描述规规矩矩的定理就不再重复了,举个栗子吧f(x)0f(x)0f(x)0单变量方程,求根改写为等价形

文章目录

    • 定理描述
    • 初值对于牛顿迭代法的影响
    • Newton下山法
    • 牛顿迭代法的优缺点

定理描述

规规矩矩的定理就不再重复了,举个栗子吧
f ( x ) = 0 f(x) = 0 f(x)=0
单变量方程,求根
改写为等价形式
ϕ ( x ) = x \phi(x) = x ϕ(x)=x
在大前提 ϕ ∈ C [ a , b ] \phi\in C[a,b] ϕC[a,b]的条件下(即函数在区间[a,b]上连续)如果
∣ ϕ ( x ) − ϕ ( y ) ∣ ≤ L ∣ x − y ∣ |\phi(x) – \phi(y)|\leq L|x – y| ϕ(x)ϕ(y)Lxy
其中 ∀ x , y ∈ [ a , b ] \forall x,y \in [a,b] x,y[a,b] L ∈ ( 0 , 1 ) L\in(0,1) L(0,1), a ≤ ϕ ( x ) ≤ b a\leq \phi(x) \leq b aϕ(x)b
表达的意思就是
如果函数 ϕ \phi ϕ的割线斜率有最大值且最大值不超过1,则迭代序列 { x k } \{x_k\} { xk}会收敛于一个定点 x ∗ x^* x,收敛区间是[a,b]

初值对于牛顿迭代法的影响

同样举个栗子,求下列方程的根
x 3 − x − 1 = 0 x^3 – x -1=0 x3x1=0
第一次选初值 x 0 = 0.6 x_0 = 0.6 x0=0.6

x = zeros(1,10);
x(1) = 0.6;
k = 1;
while abs(x(k)^3-x(k)-1) > eps
x(k+1) = x(k)-(x(k)^3-x(k)-1)/(3*x(k)^2-1);
k = k + 1;
end
format long;
disp(x(k));

迭代情况如图

《关于牛顿迭代法的初值以及收敛性的理解》
共迭代九次
not bad
可以更快一点???
下面寻找更快的初值条件
代码如下

function X = sroot(x,epsilon)
% 初值条件一
%y(k)*y(k-1)<= 0
% 初值条件二
%拐点附近,且拐点的函数值在允许的误差范围内。
%切记所允许的误差的大小很关键。如果误差太小,
%则迭代可能一直执行下去一般选$\10^-M$大100倍,其中M是计算机浮点数的小数位数。
Y = f(x);
yrange = max(Y) - min(Y);
epsilon2 = yrange*epsilon;
n = length(x);
Y(n+1) = Y(n);
x(n+1) = x(n);
m = 0;
for k = 2:n
if Y(k)*Y(k-1) <0
m = m + 1;
X(m) = 0.5*(x(k)+x(k-1));
end
if ((Y(k)-Y(k-1))*(Y(k+1)-Y(k))<= 0)...
&&(abs(Y(k)) m = m + 1;
X(m) = x(k);
end
end

执行情况

x = -2:0.001:2;
sroot(x,0.00001)

ans =

1.324500000000000
说明能找得到的最佳初值点 x 0 x_0 x0= 1.324500000000000

再用牛顿迭代法执行一次

x = zeros(1,10);
x(1) = 1.3245;
k = 1;
while abs(x(k)^3-x(k)-1) > eps
x(k+1) = x(k)-(x(k)^3-x(k)-1)/(3*x(k)^2-1);
k = k + 1;
end
format long;
disp(x(k));

k

k =

4

x

x =

1 至 7 列

1.324500000000000 1.324718001527481 1.324717957244748 1.324717957244746 0 0 0

8 至 10 列

0 0 0

这次迭代次数缩短一半

Newton下山法

简单说一下吧
在牛顿迭代公式的基础上加一个迭代因子 λ k \lambda_k λk,即
x k + 1 = x k − f ( x k ) λ k f ( x k ) x_{k+1}=x_k &#8211; \frac{f(x_k)}{\lambda_k f(x_k)} xk+1=xkλkf(xk)f(xk)
目的
通过调整切线斜率将本不属于收敛区间[a,b]的 x k + 1 x_{k+1} xk+1划入之中

牛顿迭代法的优缺点

缺点

  • 对函数的条件太苛刻,函数 f ( x ) f(x) f(x)必须光滑
  • 导数的计算未必方便
  • 初始值必须尽量靠近最终解

优点
一旦满足条件,牛顿迭代法的局部收敛还是很有吸引力的。而牛顿迭代法是按平方收敛的,粗略的说就是每迭代一次误差平方一次,所以算 2 \sqrt{2} 2 就很方便。

另外离散Newton法这里就不说,原理类似。


推荐阅读
author-avatar
一颗顽石
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有