作者:一颗顽石 | 来源:互联网 | 2023-10-12 13:07
文章目录定理描述初值对于牛顿迭代法的影响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)∣≤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 – 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−λ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法这里就不说,原理类似。