迭代法

约 1801 个字 8 张图片预计阅读时间 6 分钟

Text Only
本章作业:1, 3, 5, 11(P159-160)

引例和问题

两个基本定理:

代数基本定理(a+bi是根,那么a-bi也是根)
函数根的存在定理(好像叫这个)

确定根的方法

确定有没有根
确定根的范围
根的精细化

绘图法:

研究单调性,极值等性质,那么可以描绘出函数的图像

画出草图,从而看出曲线和x轴交点的大致位置

可以将f(x)=0变成$\psi_2(x)=\psi_1(x)$的形式,那么两个曲线的交点所在的子区间就是含根区间

搜索法:在连续区间$[a,b]$内,选择一系列的x值,在出现两个相邻点函数值番号的时候,在此小区间至少有一个实根

以步长为$h=(B-A)/n$,从左到右确定节点,$xi=x_0+ih$从左到右检查$f(x_i)$的符号,如果相邻节点异号了,得到一个缩小的有根区间

二分法

利用函数在[a,b]内连续单调且首尾异号,那么在[a,b]内方程f(x)=0有且仅有一个实根

构造原理:适用对分区间的方法,通过判别函数的f(x)的符号,逐步将有根区间缩小,在足够小的区间内,方程有且仅有一根

其中每个区间都是前一个区间的一半，因此二分k次后的有根区间的长度就是 $\(b_k-a_k = \frac{1}{2^k}$\)

此时区间内随意一点都满足我们的精度条件,此时区间中点就是我们的近似值

误差是$\(|x^*-x_k|\leq\frac{b_k}{a_k}=\frac{b-a}{2^{k+1}}$\)

如果给定了一个精度要求

\[\varepsilon>0$$ 可估计二分法所需的步数k $$|x^*-x_k| = \frac{b-a}{2^{k+1}}< \varepsilon\]

算到第k+1次二分(最后一次是去中点找近似值的时候)计算得到的$x_k$就是满足精度要求的近似根

一般情况下,用上述的确定的k往往会偏大,程序中一般不用此式子来决定二区间的次数

基本步骤如下图

首先要求定连续,首尾单调和区间收尾异号,三个条件缺一不可

无法求复数根和偶重根,收敛速度慢

简单迭代法

迭代法的基本思想是: 迭代法是一个逐次逼近的方法,首先给定一个粗糙的开始,然后用同一个迭代公式,反复矫正这个初值,知道满足预先给定的精度要求位置

迭代法的关键在于如何构造一个合适的迭代公式

简单迭代法:

\[f(x) = 0 \]

等价变换为

\[x = \psi(x)\]

$f(x)=0$的根必须满足$x^*=\phi(x^*)$,也就是$\psi(x)$作用在$x^*$上,其值不发生变化

可以称为$x^*$为$\psi(x)$的不动点

如果产生的$X_n$有极限存在就可以说明迭代公式收敛

如果没有极限,那么迭代公式发散,不同迭代公式产生不同的序列,可能收敛可能发散

上图是迭代法几何意义

要满足能迭代的条件那么$\psi (x)'$属于$[-1,1]$

拉格朗日中值定理:

如果函数$f(x)$在$(a,b)$可导,在$[a,b]$上连续,那么必定有一个$x_i$使得

\[f(x_i)\times (b-a)=f(b)-f(a)\]

曲线在A,B间至少存在1点P(c,f©),使得该曲线在P点的切线与割线AB平行

局部收敛性:

一阶导数等于0的时候,表示了有更快速度的可能性

收敛速度和迭代公式的加速:

收敛速度:收敛时迭代误差的下降速度

牛顿迭代法

设有非线性方程$f(x)=0$,在$[a,b]$上一阶连续可微,且$f(a)\times f(b) < 0$ 又设$x_0$是$f(x)$一个零点$x^*$在(a,b)上的近似值,现在考虑用过曲线上p点的切线近似代替函数f(x),也就是用线性函数$y=f(x_0)+f(x_0)'(x-x_0)$代替f(x)

用切线与x轴交点的横坐标来代替曲线与x轴交点的横坐标,这就是切线法

收敛的充分条件

$f(a)f(b)<0$
$f'(x)\neq 0$
$f''(x)$存在且不变号(保证产生的序列单调有界,保证收敛) 则产生的序列${x_k}$收敛到$f(x)=0$在$[a,b]$的唯一根

为什么说这是一个迭代法 $\(x_{k+1}=g(x_k)$\) 其中迭代函数为 $\(g(x)=x-\frac{f(x)}{f'(x)}$\) 设$f'(x_k)\neq 0$

\[g(x)'=1-\frac{f'(x)^2-f(x)f''(x)}{f'(x)^2}=\frac{f(x)f''(x)}{f'(x)^2}\]

因为在$x=x^*$时,一阶导数为$0$,此时由于迭代法局部收敛定理,迭代法$x_{k+1}=\psi(x_k)$局部收敛

若存在三阶导

那么$\(\psi''(x)=\frac{f''(x^*)}{f'(x^*)}$\) 若不等于$0$,所以二阶导不等于$0$.此时为平方收敛

若不等于$0$,此时收敛速度更快

实用中可先用二分法做求根预处理,二分若干次后得到较靠近根$x^*$的近似根$x_0$ ,再用此根作为牛顿迭代法的初值来求根,达到取长补短的作用

缺点在于f(x)必须是光滑的,要容易计算导数,初始猜想要靠近零点

写出迭代函数
确定初值$f(x_0)\neq 0,f'(x_0)\neq 0$
迭代计算

牛顿迭代法算$\sqrt{C}$

弦截法

当f(x)计算比较复杂的时候,求导相对困难,此时可以将牛顿公式中的$f'(x)$用插商来代替

$\(f(x)\approx\frac{f(x_k)-f(x_0)}{x_k-x_0}$\) 此时得到弦截法的计算公式

初值$x_0,x_1$ $\(x_{k+1}=x_k-\frac{f(x_k)}{f(x_k)-f(x_0)}(x_k-x_0)$\)

也就是把$f'(x)$用割线来代替此时不需要求导了

几何解释:

这个方法收敛速度比牛顿法慢(一般情况是线性收敛),也是局部收敛性

当$x_0$充分接近$x^*$时,具备局部的收敛性

牛顿至少是二阶的速度

快速弦截法

为了提高弦截法的收敛速度,改用差商,代替得到迭代公式的导数

之前是$x_k$和$x_0$的值相减,此时$x_0$时老数据,不是更新得到的新数据,导致了迭代变慢

Text Only
 判断迭代终止,如果用ab判断二分次数,此时会偏大,此时应该保证工作有效,应该尽可能用新的数据来判断.此时也一样,一直用老数据,导致理论迭代速度变慢
 我们用第k次和第k-1次,就可以更加精准

$\(x{k+1}=x_k-\frac{f(x)}{f(x)-f(x_{k-1})}(x_k-x_{k-1})$\) 此时需要两个初值$x_0,x_1$(弦截法也要两个初值)

快速弦截法:两步法

迭代法,弦截法:单步法

计算步骤

选定初值
计算
如果满足了精度,输出
否则转第二步骤,继续计算

迭代法