1. 不動(dòng)點(diǎn)定理及其條件驗(yàn)證

不動(dòng)點(diǎn)定義：$P=g(P)$
不定點(diǎn)迭代：$x_{k+1}=g\left(x_k\right)$
定理： 如果$g(x_k)$是連續(xù)的并且序列$x_k$是收斂的，$x_k$收斂到方程的解：$x=g(x)$
$$x^{?}=g\left(x^{?}\right)\text{?and?}{x}_k?>x^{?}$$

定理： 假設(shè)
(1) 對(duì)于$g(x)$，$g^{\prime }(x)\in C[a,b]$（連續(xù)）
(2) $K$是一個(gè)正的常數(shù)
(3) $p_0\in (a,b)$
(4) $g(x)\in [a,b],?x\in [a,b]$
那么
(a) 如果$\left|{\mathrm{g}}^{\prime }(x)\right|\le \mathrm{K}<1，?x\in [\mathrm{a},\mathrm{b}],{\mathrm{x}}_{\mathrm{k}+1}=\mathrm{g}\left({\mathrm{x}}_{\mathrm{k}}\right)$收斂。
(b) 如果$\left|{\mathrm{g}}^{\prime }(x)\right|>1，?x\in [\mathrm{a},\mathrm{b}],{\mathrm{x}}_{\mathrm{k}+1}=\mathrm{g}\left({\mathrm{x}}_{\mathrm{k}}\right)$不收斂

曲線(xiàn)的切線(xiàn)斜率$k\in (?1,1)$看下面的圖逐漸收斂：

曲線(xiàn)的切線(xiàn)斜率$k\in [?\infty ,?1)\cup (1,\infty ]$看下面的圖不收斂：

綜上所述，不動(dòng)點(diǎn)迭代滿(mǎn)足最重要的是：

$\begin{array}{rlr}& (1)\left|{\mathrm{g}}^{\prime }(x)\right|\le \mathrm{K}<1,?x\in [\mathrm{a},\mathrm{b}]& 【g^{\prime }(x)的邊界條件】\\ & (2)\mathrm{g}(x)\in [\mathrm{a},\mathrm{b}]，?x\in [\mathrm{a},\mathrm{b}]，并且有g([a,b])?[a,b]& 【g(x)的邊界條件】\end{array}$

單調(diào)和非單調(diào)要分別判斷邊界條件，單調(diào)的g(x)的范圍看端點(diǎn)就可以了，非單調(diào)還要看極值點(diǎn)。

2. 收斂階、收斂檢測(cè)與收斂加速

定義;
$$\left|x_{k+1}?x^{?}\right|\le C{\left|x_k?x^{?}\right|}^p,k>M\text{,?for?}C>0,p>0$$
或
$$\underset{k\to \infty }{\lim }\frac{\left|x_{k+1}?x^{?}\right|}{{\left|x_k?x^{?}\right|}^p}=C$$
為$p$階收斂
其中：
$p=1$ , 線(xiàn)性收斂（linear convergence）
$1<p<2$ , 超線(xiàn)性收斂（superlinear convergence）
$p=2$ , 平方收斂（square convergence）

2.1 如何估計(jì)不動(dòng)點(diǎn)迭代的收斂階$x_{k+1}=g\left(x_k\right)$

定理;設(shè)$x^{?}$是最優(yōu)解，如果$g^{\prime }\left(x^{?}\right)=g^{\prime \prime }\left(x^{?}\right)=\dots =g^{(p?1)}\left(x^{?}\right)=0$, $g^{(p)}\left(x^{?}\right)\ne 0$， $x_{k+1}=g\left(x_k\right)$是 $p$階收斂。

證明：
$$\begin{array}{rl}{x}_{k+1}& =g\left(x_k\right)=g\left(x^{?}\right)+g^{\prime }\left(x^{?}\right)\left(x_k?x^{?}\right)+\dots \\ & +\frac{g^{(p?1)}\left(x^{?}\right){\left(x_k?x^{?}\right)}^{p?1}}{(p?1)!}+\frac{g^{(p)}(\xi ){\left(x_k?x^{?}\right)}^p}{p!},【\xi \in \left[x_k,x^{?}\right]或\left[x^{?},x_k\right]】\\ ?& x_{k+1}=x^{?}+\frac{g^{(p)}(\xi ){\left(x_k?x^{?}\right)}^p}{p!}\\ ?& \frac{x_{k+1}?x^{?}}{{\left(x_k?x^{?}\right)}^p}=\frac{g^{(p)}(\xi )}{p!}\to \frac{g^{(p)}\left(x^{?}\right)}{p!}\end{array}$$

2.2 給定精度的情況下，如何預(yù)測(cè)不動(dòng)點(diǎn)迭代需要迭代的次數(shù)

定義L=max?x∈[a,b]{∣g′(x)∣}<1L=\max _{x \in[a, b]}\left\{\left|g^{\prime}(x)\right|\right\}<1L=maxx∈[a,b]?{∣g′(x)∣}<1
迭代的次數(shù)滿(mǎn)足：$k\ge \ln \left(\epsilon (1?L)/\left|x_1?x_0\right|\right)/\ln L$

證明：
$$\begin{array}{r}{x}_{k+1}=g\left(x_k\right)=g\left(x^{?}\right)+g^{\prime }(\xi )\left(x_k?x^{?}\right)=x^{?}+g^{\prime }(\xi )\left(x_k?x^{?}\right)\\ ?\left|x_{k+1}?x^{?}\right|\le \left|g^{\prime }(\xi )\Vert \left(x_k?x^{?}\right)\right|\le L\left|x_k?x^{?}\right|\le L^k\left|x_1?x^{?}\right|\end{array}$$
又有
$$\left|x_{k+1}?x_k\right|=\left|g\left(x_k\right)?g\left(x_{k?1}\right)\right|\le L\left|x_k?x_{k?1}\right|\le L^k\left|x_1?x_0\right|$$
于是有：
$$\begin{array}{rl}& \left|x_{k+q}?x_k\right|\le \left|x_{k+q}?x_{k+q?1}\right|+\left|x_{k+q?1}?x_{k+q?2}\right|+\dots +\left|x_{k+1}?x_k\right|\\ & \le \left(L^{q?1}+L^{q?2}+\dots +1\right)\left|x_{k+1}?x_k\right|\\ & <\left(1+L+L^2+\dots +L^{q?1}+\dots \right)\left|x_{k+1}?x_k\right|\\ & =\frac{1}{1?L}\left|x_{k+1}?x_k\right|\\ & \le \frac{L^k}{1?L}\left|x_1?x_0\right|\end{array}$$

讓$q\to \infty$有

$$\left|x^{?}?x_k\right|\le \frac{1}{1?L}\left|x_{k+1}?x_k\right|\le \frac{L^k}{1?L}\left|x_1?x_0\right|$$

于是：

$$\frac{L^k}{1?L}\left|x_1?x_0\right|\le \epsilon ?k\ge \ln \left(\epsilon (1?L)/\left|x_1?x_0\right|\right)/\ln L$$

2.3 如何加快收斂的速度

$$\begin{array}{rl}& x_{k+1}?x^{?}\approx L\left(x_k?x^{?}\right)\\ & x_{k+2}?x^{?}\approx L\left(x_{k+1}?x^{?}\right)\\ & \frac{x_{k+1}?x^{?}}{x_{k+2}?x^{?}}\approx \frac{x_k?x^{?}}{x_{k+1}?x^{?}}?x^{?}\approx x_k?\frac{{\left(x_{k+1}?x_k\right)}^2}{x_{k+2}?2x_{k+1}+x_k}=x^{\Delta }\end{array}$$

根據(jù)上面的思路我們可以：

$$\begin{array}{rl}Iteration& {\bar{x}}_{k+1}=g\left(x_k\right)\\ Onemore& {\hat{x}}_{k+1}=g\left({\bar{x}}_{k+1}\right)\\ Tospeedup& x_{k+1}=x_k?\frac{{\left({\bar{x}}_{k+1}?x_k\right)}^2}{{\hat{x}}_{k+1}?2{\bar{x}}_{k+1}+x_k}\end{array}$$

2.4 停止不定點(diǎn)迭代的條件

當(dāng)L=max?x∈[a,b]{∣g′(x)∣}<1L=\max _{x \in[a, b]}\left\{\left|g^{\prime}(x)\right|\right\}<1L=maxx∈[a,b]?{∣g′(x)∣}<1時(shí)，可以使用下面的條件：

$$\left|x_{\mathrm{k}+1}?x_{\mathrm{k}}\right|<\mathrm{eps}$$

2.5 不動(dòng)點(diǎn)迭代的兩個(gè)缺點(diǎn)

1. 很難估計(jì)L(max?x∈[a,b]{∣g′(x)∣})L(\max _{x \in[a, b]}\left\{\left|g^{\prime}(x)\right|\right\})L(maxx∈[a,b]?{∣g′(x)∣})
2. $L<1$時(shí)無(wú)法收斂。

3. 應(yīng)用：如何求解非線(xiàn)性方程組$f(x)=0$的解

3.1 二分法(Bisection Method of Bolzano)

算法的流程：

1. 用一個(gè)區(qū)間找到一個(gè)根。
2. 用中點(diǎn)分割該區(qū)間。
3. 選擇其中的一個(gè)子區(qū)間作為新的位置。

$$\begin{array}{rl}& a=x_0,b=x_0+h\\ & c=\frac{a+b}{2}\\ & f(a)f(b)<0,\end{array}$$
于是：

$$\begin{array}{rl}& [a,b]\to \left[a_1,b_1\right]\to \left[a_2,b_2\right]\to \dots \to \left[a_n,b_n\right]\\ & a=a_0\le a_1\le ?\le a_n\le ?\le r\le ?\le b_n\le ?\le b_1\le b_0=b\end{array}$$
定義$r$是精確解。
$$\begin{array}{rl}& \left|r?c_n\right|\le \frac{b?a}{2^{n+1}},\text{?for?}n=0,1,2,\dots \\ & c_n=\frac{a_n+b_n}{2}\end{array}$$

迭代次數(shù)N：

$$\begin{array}{rl}& \left|r?c_n\right|\le \frac{b?a}{2^{n+1}}<\delta \\ & 2^{n+1}>\frac{b?a}{\delta }\\ & (n+1)\ln 2>\ln (b?a)?\ln \delta \\ & n+1>\frac{\ln (b?a)?\ln \delta }{\ln 2}\\ & N=\mathrm{int}\left(\frac{\ln (b?a)?\ln \delta }{\ln 2}\right)\end{array}$$

簡(jiǎn)單地利用二分法可以判斷區(qū)間內(nèi)有沒(méi)有零點(diǎn)（區(qū)間內(nèi)有變號(hào)【可取最大值和最小值】）

3.2 試位法(False Position Method)

算法的流程：

1. 用一個(gè)區(qū)間找到一個(gè)根。
2. 以割線(xiàn)與X軸的交點(diǎn)劃分區(qū)間。(過(guò)程中仍然保證端點(diǎn)的異號(hào)，讓區(qū)間包含零點(diǎn))
3. 選擇其中一個(gè)子區(qū)間作為新的位置。

$$\begin{gathered} c=b?\frac{f(b)(b?a)}{f(b)?f(a)} \\ {c}_1\to c_2\to \dots \to r \\ \left[a_n,b_n\right]\to [a,c]:=\left[a_{n+1},b_{n+1}\right] \end{gathered}$$

缺點(diǎn)：在凹函數(shù)下不適用，不會(huì)收斂。

3.3 牛頓-拉夫遜方法(Newton-Raphson method)

我們知道不動(dòng)點(diǎn)迭代，能不能用到求解非線(xiàn)性方程組呢？

使用泰勒展式：

$$f(x_{k+1})=f\left(x_k\right)+f^{\prime }\left(x_k\right)(x_{k+1}?x_k)+O\left(|d{|}^2\right)=0$$

于是我們可以讓

$$f\left(x_{\mathrm{k}}\right)+f^{\prime }\left(x_{\mathrm{k}}\right)\left(x_{k+1}?x_k\right)=0$$

使得：

$$x_{\mathrm{k}+1}=x_k?f\left(x_{\mathrm{k}}\right)/f^{\prime }\left(x_{\mathrm{k}}\right)=g(x_k)$$

總結(jié)Newton-Raphson方法即：

$$\begin{array}{l}f(x)=0\\ x=g(x)=x?\frac{f(x)}{f^{\prime }(x)}\\ x_{k+1}=g\left(x_k\right)=x_k?\frac{f\left(x_k\right)}{f^{\prime }\left(x_k\right)}\end{array}$$

我們可以證明在解的附近，Newton-Raphson方法是收斂的。

證明：

$$g(x)=x?f(x)/f^{\prime }(x)$$

$$g^{\prime }(x)=1?\frac{f^{\prime }(x)f^{\prime }(x)?f(x)f^{\prime \prime }(x)}{{\left[f^{\prime }(x)\right]}^2}=\frac{f(x)f^{\prime \prime }(x)}{{\left[f^{\prime }(x)\right]}^2}$$

我們知道不動(dòng)點(diǎn)的條件是$\left|g^{\prime }(x)\right|<K<1$，當(dāng)我們?nèi)〉泥徲蜃銐蛐?#xff0c;條件$g([a,b])?[a,b]$會(huì)滿(mǎn)足，注意到$f(x^{?})=0$，在解的鄰域附近，因?yàn)?span id="vxwlu0yf4" class="katex--inline">$f(x)=0$，所以$g^{\prime }(x)=0$。

各種條件下的推導(dǎo)（不做要求，想了解可以看一下）

1. $f^{\prime }\left(x^{?}\right)>0\text{?and?}{f}^{\prime \prime }\left(x^{?}\right)<0,g\left(\left[x^{?}?\delta ,x^{?}+\delta \right]\right)?\left[x^{?}?\delta ,x^{?}+\delta \right]$
   
   $$\begin{array}{rl}& x^{?}?\delta <g\left(x^{?}?\delta \right)=\left(x^{?}?\delta \right)?\frac{f\left(x^{?}?\delta \right)}{f^{\prime }\left(x^{?}?\delta \right)}\\ ?& 0<?\frac{f\left(x^{?}?\delta \right)}{f^{\prime }\left(x^{?}?\delta \right)}\\ ?& \frac{f\left(x^{?}?\delta \right)}{f^{\prime }\left(x^{?}?\delta \right)}<0\\ ?& f\left(x^{?}?\delta \right)<0\\ ?& f\left(x^{?}\right)?f^{\prime }(\xi )\delta <0【\xi \in [x^{?}?\delta ,x^{?}]】\\ ?& ?f^{\prime }(\xi )\delta <0\\ ?& ?{\delta }_1>0,f^{\prime }(\xi )>0,\text{?for?}{x}^{?}?\xi <{\delta }_1\end{array}$$
   又有
   $$\begin{array}{rl}& f^{\prime \prime }\left(x^{?}\right)<0\\ ?& ?{\delta }_2>0,f^{\prime \prime }(x)<0【保號(hào)性】\\ ?& g^{\prime }(x)=\frac{f(x)f^{\prime \prime }(x)}{{\left[f^{\prime }(x)\right]}^2}>0,\text{?for?}{x}^{?}?x<{\delta }_2\\ & 【{\delta }_2足夠小，導(dǎo)數(shù)保號(hào)性，f^{\prime }(x)>0,x<x^{?},f(x^{?})=0，f(x)<0】\end{array}$$
   當(dāng)δ<min?{δ1,δ2}\delta<\min\{\delta_1,\delta_2\}δ<min{δ1?,δ2?}有：
   $$x^{?}?\delta <g\left(x^{?}?\delta \right)<g(x),\text{?for?}{x}^{?}?x<\delta$$
2. $f^{\prime }\left(x^{?}\right)>0\text{?and?}{f}^{\prime \prime }\left(x^{?}\right)<0,g\left(\left[x^{?}?\delta ,x^{?}+\delta \right]\right)?\left[x^{?}?\delta ,x^{?}+\delta \right]$
   
   $$\begin{array}{rl}& x^{?}?\delta <g\left(x^{?}?\delta \right)=\left(x^{?}?\delta \right)?\frac{f\left(x^{?}?\delta \right)}{f^{\prime }\left(x^{?}?\delta \right)}\\ ?& 0<?\frac{f\left(x^{?}?\delta \right)}{f^{\prime }\left(x^{?}?\delta \right)}\\ ?& \frac{f\left(x^{?}?\delta \right)}{f^{\prime }\left(x^{?}?\delta \right)}<0\\ ?& f\left(x^{?}?\delta \right)<0\\ ?& f\left(x^{?}\right)?f^{\prime }(\xi )\delta <0【\xi \in [x^{?}?\delta ,x^{?}]】\\ ?& ?f^{\prime }(\xi )\delta <0\\ ?& ?{\delta }_1>0,f^{\prime }(\xi )>0,\text{?for?}{x}^{?}?\xi <{\delta }_1\end{array}$$
   又有
   $$\begin{array}{rl}& f^{\prime \prime }\left(x^{?}\right)>0\\ ?& ?{\delta }_2>0,f^{\prime \prime }(x)<0【保號(hào)性】\\ ?& g^{\prime }(x)=\frac{f(x)f^{\prime \prime }(x)}{{\left[f^{\prime }(x)\right]}^2}<0,\text{?for?}{x}^{?}?x<{\delta }_2\\ & 【{\delta }_2足夠小，導(dǎo)數(shù)保號(hào)性，f^{\prime }(x)>0,x<x^{?},f(x^{?})=0，f(x)<0】\end{array}$$
   當(dāng)δ<min?{δ1,δ2}\delta<\min\{\delta_1,\delta_2\}δ<min{δ1?,δ2?}有：
   $$x^{?}?\delta <x^{?}=g\left(x^{?}\right)<g(x),\text{?for?}{x}^{?}?x<\delta ,x<x^{?}$$

注意Newton-Raphson方法對(duì)于單根是二階收斂(二次收斂)【quadratic convergence】

$$\left|E_{n+1}\right|\approx \frac{\left|f^{\prime \prime }(p)\right|}{2\left|f^{\prime }(p)\right|}{\left|E_n\right|}^{2}n\to \infty$$

證明：

而對(duì)于多重根是線(xiàn)性（一次）收斂，收斂速度降低。

$$\left|E_{n+1}\right|\approx \frac{M?1}{M}\left|E_n\right|n\to \infty$$

證明：

如果出現(xiàn)了多重根$p^{?}$，我們看到在$f^{\prime }(p^{?})=0$，Newton-Raphson方法的分母會(huì)出現(xiàn)0.然而一般來(lái)說(shuō)，分子$f(p_k)$要比分母$f^{\prime }(p_k)$先出現(xiàn)0，所以Newton-Raphson方法一般還是可以用的。

Newton-Raphson方法的問(wèn)題：

1.分母可能為0，除以零是不允許的。
2.收斂到一個(gè)不同的根，或發(fā)散。
3.產(chǎn)生一個(gè)循環(huán)序列。
4.產(chǎn)生一個(gè)發(fā)散的振蕩序列。

由于多重根線(xiàn)性收斂的問(wèn)題，可以考慮Newton-Raphson方法加速：
$$p_k=p_{k?1}?\frac{Mf\left(p_{k?1}\right)}{f^{\prime }\left(p_{k?1}\right)}M>1$$

證明：

3.4 割線(xiàn)法(Secant Method)

當(dāng)Newton-Raphson的導(dǎo)數(shù)不好顯式表達(dá)的時(shí)候，可以通過(guò)兩端點(diǎn)的直線(xiàn)的斜率來(lái)近似導(dǎo)數(shù)。

我們有：

$$x_{k+2}=g\left(x_k,x_{k+1}\right)=x_{k+1}?\frac{f\left(x_{k+1}\right)\left(x_{k+1}?x_k\right)}{f\left(x_{k+1}\right)?f\left(x_k\right)}$$

3.5 Aitken過(guò)程加速

使用不定點(diǎn)的迭代，Aitken過(guò)程加速又稱(chēng)為史蒂芬森加速（Steffensen’s acceleration）.注意，只對(duì)一階方法有效。

$$\underset{n\to \infty }{\lim }\frac{p?p_{n+1}}{p?p_n}=A,p\approx \frac{p_{n+2}{p}_n?p_{n+1}^2}{p_{n+2}?2p_{n+1}+p_n}=q_n$$

3.6 Muller方法（Muller’s method）

給定三個(gè)初始值$\left(p_0,f\left(p_0\right)\right),\left(p_1,f\left(p_1\right)\right),\left(p_2,f\left(p_2\right)\right)$

令
$$\begin{array}{rl}& t=x?p_2\\ & h_0=p_0?p_2,h_1=p_1?p_2\end{array}$$

我們使用二次函數(shù)計(jì)算下一個(gè)點(diǎn)：

$$y=a{t}^2+bt+c$$

則有：

$$\begin{array}{rl}t=h_0:a{h}_0^2+b{h}_0+c=f_0& ?a{h}_0^2+b{h}_0=f_0?c=e_0\\ t=h_1:a{h}_1^2+b{h}_1+c=f_1& ?a{h}_1^2+b{h}_1=f_1?c=e_1\\ t=0:a{0}^2+b0+c=f_2& ?c=f_2\end{array}$$

解得：

$$a=\frac{e_0{h}_1?e_1{h}_0}{h_1{h}_0^2?h_0{h}_1^2},b=\frac{e_1{h}_0^2?e_0{h}_1^2}{h_1{h}_0^2?h_0{h}_1^2}$$

于是得到：

at2+bt+c=0:t=z1,z2?zi=?2cb±b2?4acz=arg?min?{∣zi∣}【對(duì)于一個(gè)復(fù)數(shù)，在計(jì)算中只保留其實(shí)數(shù)部分】\begin{aligned} &a t^{2}+b t+c=0: \quad t=z_{1}, z_{2} \Rightarrow z_{i}=\frac{-2 c}{b \pm \sqrt{b^{2}-4 a c}} \\ &z=\arg \min \left\{\left|z_{i}\right|\right\}【\text{對(duì)于一個(gè)復(fù)數(shù)，在計(jì)算中只保留其實(shí)數(shù)部分}】 \end{aligned}?at2+bt+c=0:t=z1?,z2??zi?=b±b2?4ac??2c?z=argmin{∣zi?∣}【對(duì)于一個(gè)復(fù)數(shù)，在計(jì)算中只保留其實(shí)數(shù)部分】?

$$p_3=p_2+z$$

繼續(xù)得到$\left({\bar{p}}_1,{\bar{p}}_2,p_3\right)$，其中${\bar{p}}_1,{\bar{p}}_2$是距離$p_3$最近的兩個(gè)點(diǎn)。

4. 其他問(wèn)題

4.1 如何尋找初值

例如

可以有兩個(gè)判斷條件：

1. 【針對(duì)$r_1$和$r_2$】
   $$f\left(x_{k?1}\right)f\left(x_k\right)<0[a,b]=\left[x_{k?1},x_k\right]$$

2. 【針對(duì)$r_3$】
   $$\left|f\left(x_k\right)\right|<\epsilon \text{?并且}\left(f\left(x_k\right)?f\left(x_{k?1}\right)\right)\left(f\left(x_{k+1}\right)?f\left(x_k\right)\right)<0[a,b]=\left[x_{k?1},x_{k+1}\right]$$

4.2 收斂條件

可以有兩個(gè)收斂條件：

1. 根據(jù)縱坐標(biāo)
$$\left|f\left(x_k\right)\right|<\epsilon$$

誤差為：${\text{Error}}_x=\left|x_k?r\right|$

2. 根據(jù)橫坐標(biāo)

$$\left|x_k?x_{k?1}\right|<\delta$$

由以下推出：

$$\left|x_k?r\right|<\delta ?\left|x_k?x_{k?1}\right|<\delta$$

誤差為：Error?f=max?{∣f(r?δ)∣,∣f(r+δ)∣}\text { Error }_{f}=\max \{|f(r-\delta)|,|f(r+\delta)|\}?Error?f?=max{∣f(r?δ)∣,∣f(r+δ)∣}

3. 我們也可以把上面兩個(gè)進(jìn)行組合：

$$\left|f\left(x_k\right)\right|<\epsilon \text{并且}\left|x_k?r\right|<\delta$$

4. 如果針對(duì)Newton-Raphson問(wèn)題，我們還可以有如下的判斷標(biāo)準(zhǔn)：

①$f^{\prime }(r)\ne 0$
②$x_0\in [r?\delta ,r+\delta ]$, $\delta$足夠小。

4.3 算法的收斂速度對(duì)比

4.4 算法的選擇

單根：
Newton-Raphson方法

雙根（當(dāng)分母為0失效）：
Newton-Raphson方法
Steffensen’s method