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

文章目录

• • 定理描述
  • 初值对于牛顿迭代法的影响
  • 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) &＃8211; \phi(y)|\leq L|x &＃8211; y| ∣ϕ(x)−ϕ(y)∣≤L∣x−y∣
其中 ∀ 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 &＃8211; x -1=0 x3−x−1=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​−λk​f(xk​)f(xk​)​
目的
通过调整切线斜率将本不属于收敛区间[a,b]的 x k + 1 x_{k+1} xk+1​划入之中

牛顿迭代法的优缺点

缺点

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

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

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