Numerical Methods Using MATLAB(4版)-02-Nonlinear Equations

引自Numerical Methods Using MATLAB(4版)書籍痘煤，如有侵權(quán)請(qǐng)聯(lián)系刪除

前言

這一章節(jié)主要講述求 $f(x)=0$ 這一方程根的不同方法辱士。

學(xué)習(xí)總結(jié)

不動(dòng)點(diǎn)迭代

我們假設(shè)按照 $g(x)$ 這一函數(shù)迭代日裙，初始值為 $p_0$ ，那么我們接下來會(huì)得到序列 $\{p_k\}$ 。如果這個(gè)序列是收斂的，那么能得到一個(gè)不動(dòng)點(diǎn) $P$ 使得 $P=g(P)$ 史侣。
當(dāng) $g∈C[a,b]$ 時(shí)拴泌，有以下幾條定理：
1、如果 $y=g(x)$ 滿足 $y∈[a,b]$ 惊橱， $x∈[a,b]$ 蚪腐，那么 $g$ 在 $[a,b]$ 中有不動(dòng)點(diǎn) $P$ 。
2李皇、如果 $g'(x)$ 在 $(a,b)$ 中有定義且對(duì)任意 $x∈(a,b)$ 存在 $|g'(x)| \leq K < 1$ 削茁，那么 $g$ 在 $[a,b]$ 上有唯一不動(dòng)點(diǎn) $P$ 宙枷。
當(dāng) $g,g'∈C[a,b];p_0∈(a,b);$ 對(duì)所有 $x∈[a,b],g(x)∈[a,b]$ 時(shí)掉房，有以下幾條定理：
1、如果對(duì)任意 $x∈(a,b)$ 存在 $|g'(x)| \leq K < 1$ 慰丛，那么迭代收斂到唯一不動(dòng)點(diǎn)卓囚，稱為吸引不動(dòng)點(diǎn)。
2诅病、如果對(duì)任意 $x∈(a,b)$ 存在 $|g'(x)| > 1$ 哪亿，那么迭代無法收斂到不動(dòng)點(diǎn)，稱為反叛不動(dòng)點(diǎn)贤笆。
P46的公式14是如何得到的蝇棉？
|a-b|<=|a-c|+|c-b|

證明過程

方法一二分法

二分法的過程很簡(jiǎn)單在此不過多贅述。

二分法的定理：
假設(shè) $f∈C[a,b]$ 芥永，并且存在 $r∈[a,b]$ 使得 $f(r)=0$ 篡殷。如果 $f(a)$ 和 $f(b)$ 符號(hào)相反，且 $\{c_n\}_{n=0}^{\infty}$ 代表二分過程中中間點(diǎn)序列埋涧，那么有
$|r-c_n| \leq \frac{b-a}{2^{n+1}},n=0,1,...$
且有
$\lim_{n\rightarrow\infty}c_n=r.$

二分法的優(yōu)點(diǎn)：
可以提前預(yù)估解的精確度板辽。假設(shè)重復(fù) $N$ 次二分，那么我們通過以下能夠保證 $c_N$ 近似于解棘催，且誤差少于 $\delta$ ：
$N=int(\frac{ln(b-a)-ln(\delta)}{ln(2)})$
proof.
$(1)Nln2=ln(b-a)-ln(\delta)$
$(2)ln2^N=ln(b-a)-ln(\delta)$
$(3)2^N=\frac{(b-a)}{\delta}$
$(4){\delta}=\frac{(b-a)}{2^N}$

方法二錯(cuò)位法

因?yàn)槎址ㄊ諗康帽容^慢劲弦，所以我們發(fā)明了錯(cuò)位法。

錯(cuò)位法的原理：
該方法連接 $(a,f(a))$ 和 $(b,f(b))$ 兩點(diǎn)醇坝，其連線在 $x$ 軸的交點(diǎn)取為 $(c,0)$ 邑跪，然后和二分法一樣， $f(c)$ 與哪個(gè)端點(diǎn)互為相反數(shù)呼猪，則更新區(qū)間画畅。
其中求 $c$ 的公式如下：
$c=b-\frac{f(b)(b-a)}{f(b)-f(a)}$

其中，二分法的誤差err=abs(b-a)郑叠，錯(cuò)位法的誤差err=abs(b-a)/2
但是錯(cuò)位法的誤差為什么是這樣的呢夜赵？證明？

逼近區(qū)域的初始化和收斂標(biāo)準(zhǔn)

上述方法都是全局收斂的乡革，但如果在區(qū)間內(nèi)有多個(gè)解寇僧，那么我們就需要更小的區(qū)間分別來尋找這些解摊腋。接下來會(huì)描述Newton-Raphson和割線法來求解，這兩種方法都是求局部收斂的嘁傀。這種局部收斂會(huì)收斂得更快兴蒸。有部分算法會(huì)結(jié)合這兩種類型的算法，在開始使用全局收斂细办，當(dāng)接近根的時(shí)候再使用局部收斂橙凳。
作圖是一種方法。但是計(jì)算機(jī)有時(shí)候也會(huì)遇到精確度不夠的特殊情況笑撞，我們需要考慮到岛啸。與此同時(shí)，由于計(jì)算機(jī)精度有限茴肥，我們可能會(huì)遇到 $f(x_k) \approx 0$ 的情況坚踩，這時(shí)候我們需要判斷附近 $x_{k-1}$ 和 $x_{k+1}$ 兩點(diǎn)斜率是否相反，相反才行瓤狐。
即瞬铸，判斷根，一個(gè)是兩邊 $f(x)$ 符合相反础锐，一個(gè)是兩邊斜率相反且 $f(x_k) \approx 0$ 嗓节。
$(i)(y_{k-1})(y_k)<0,or$
$(ii)|y_k|<\epsilon \ and \ (y_k-y_{k-1})(y_{k+1}-y_k)<0.$
對(duì)于計(jì)算機(jī)求根，我們需要一個(gè)算法來判斷什么時(shí)候循環(huán)終止皆警，因此我們需要制定數(shù)值拦宣，防止死循環(huán)，同時(shí)也要保持一定精度耀怜。我們可以有以下兩種評(píng)判標(biāo)準(zhǔn)：
$|p_n-p_{n-1}| < \delta,(the \ \ absolute \ \ error)$
$\frac{2|p_n-p_{n-1}|}{|p_n|+|p_{n-1}|} < \delta,(the \ \ relative \ \ error)$
（其中恢着，第二種標(biāo)準(zhǔn)為什么不是直接除 $|p_n|$ ，是為了防止除0現(xiàn)象财破。）

解誤差與殘差的區(qū)別

殘差

解誤差

如圖掰派，解誤差是 $y$ 的誤差，殘差是 $x$ 的誤差左痢。一般情況下我們很難得到 $P$ 靡羡，所以解誤差少用。

方法三 Newton-Raphson法

如果f(x)俊性，f'(x)略步，f''(x)在根p附近連續(xù)，那么我們可以使用更快的算法來收斂定页，其中Newton-Raphson法就是其中最有用和最出名的算法之一趟薄。牛頓法并不能保證找到根，也會(huì)出現(xiàn)循環(huán)或發(fā)散的情況典徊。

Newton-Raphson法的原理
假設(shè) $f∈C^2[a,b]$ 杭煎，且 $p∈[a,b]$ 恩够， $f(p)=0$ 。如果 $f'(p) \neq 0$ 羡铲，則存在 $\delta > 0$ 使得序列 $\{p_k\}_{k=0}^{\infty}$ 滿足以下公式：
$p_k=g(p_{k-1})=p_{k-1}-\frac{f(p_{k-1})}{f'(p_{k-1})},k=1,2,...$
其中序列最終收斂到 $p$ 蜂桶，且 $p_0∈[p-\delta,p+\delta]$ 。
且根據(jù)不動(dòng)點(diǎn)迭代的原理也切，需滿足
$g'(x)=\frac{f(x)f'''(x)}{(f'(x))^2}<1,for \ \ all \ \ x∈(p-\delta,p+\delta).$

proof.
$p_0$ 非常逼近 $p$
$(1)f(x)=f(p_0)+f'(p_0)(x-p_0)+\frac{f''(c)(x-p_0)^2}{2!},$

$(2)0=f(p_0)+f'(p_0)(x-p_0)+\frac{f''(c)(x-p_0)^2}{2!},$

$(3)0 \approx f(p_0)+f'(p_0)(x-p_0),$

$(4)p_1 = p_0-\frac{f(p_0)}{f'(p_0)}.$

Newton-Raphson法的推論
可以用來找平方根扑媚，這個(gè)推論的重點(diǎn)在于函數(shù)g(x)只能有簡(jiǎn)單的加減乘除運(yùn)算，如果有根號(hào)運(yùn)算雷恃，可能會(huì)陷入循環(huán)疆股，因此我們采用這種推論求根號(hào)。
假設(shè) $A>0$ 且 $p_0>0,p_0 \approx \sqrt{A}$ 褂萧，有
$p_k=\frac{p_{k-1}+\frac{A}{p_{k-1}}}{2},k=1,2,...$
使得 $\lim_{n\rightarrow\infty}p_k=\sqrt{A}$ 押桃。

proof.
設(shè) $f(x)=x^2-A$ ，再用牛頓法求根迭代导犹。

根的定義
假設(shè) $f(x)$ 及其 $M$ 階導(dǎo)數(shù) $f^{(M)}(x)$ 在 $x=p$ 上有定義且連續(xù)，并當(dāng)且僅當(dāng)
$f(p)=0,f'(p)=0,...,f^{(M-1)}(p)=0,f^{(M)}(p) \neq 0$

則我們稱 $f(x)=0$ 在 $x=p$ 上有 $M$ 個(gè)根羡忘。
且存在一個(gè)連續(xù)函數(shù) $h(x)$ 可以表達(dá)為 $f(x)=(x-p)^Mh(x),h(p) \neq 0.$

收斂速度
如果p是單根谎痢，那么牛頓法可以快速收斂，每次迭代精確的小數(shù)位數(shù)都可以翻倍卷雕。如果p是多根节猿，每次后繼誤差都是前面誤差的一部分。這里是為什么漫雕？
假設(shè) $\{p_n\}_{n=0}^{\infty}$ 收斂到 $p$ 滨嘱，且有 $E_n=p-p_n(n \geq 0)$ （解誤差，可以用殘差代替）浸间。如果正常量 $A \neq 0$ 太雨， $R >0$ 存在，則
$\lim_{n \rightarrow \infty}\frac{|p-p_{n+1}|}{|p-p_n|^R}=\lim_{n \rightarrow \infty}\frac{|E_{n+1}|}{|E_n|^R}=A.$
其中 $R$ 為序列收斂到 $p$ 的階數(shù)魁蒜， $A$ 為漸進(jìn)誤差常量囊扳。
當(dāng) $R=1$ 時(shí)，一般有 $A<1$ 兜看，稱為線性收斂锥咸。
當(dāng) $R=2$ 時(shí)，一般有 $A$ 為常量即可细移，稱為平方收斂搏予。
$R$ 越大，收斂得越快弧轧。

牛頓法收斂速度的定理
如果 $p$ 是單根雪侥，收斂速度是平方的球涛， $|E_{n+1}| \approx \frac{|f''(p)|}{2|f'(p)|}|E_n|^2$ 。
如果 $p$ 是 $M$ 根校镐，收斂速度是線性的亿扁， $|E_{n+1}| \approx \frac{M-1}{M}|E_n|$ 。

加速牛頓法的收斂速度
牛頓法是線性收斂到根的鸟廓，為了加速从祝，我們可以使用以下公式產(chǎn)生序列平方收斂到根：
$p_k=p_{k-1}-\frac{Mf(p_{k-1})}{f'(p_{k-1})}.$

方法四割線法

割線法與錯(cuò)位法幾乎是一樣的，但是錯(cuò)位法是在縮小區(qū)間引谜，割線法是在快速找點(diǎn)牍陌。其單根收斂階數(shù)為 R ≈ 1.618033989。
$p_{k+1}=g(p_k,p_{k+1})=p_k-\frac{f(p_k)(p_k-p_{k-1})}{f(p_k)-f(p_{k-1})}.$

收斂速度的比較

方法五 Aitken's Process

牛頓法中對(duì)于多根收斂速度是線性的员咽，而使用加速牛頓法毒涧，得提前知道根的個(gè)數(shù)。因此我們提出一些其他方法來加速贝室。
定義
對(duì)于收斂數(shù)列 $\{p_n\}_{n=0}^{\infty}$ 契讲，定義 $\Delta p_n=p_{n+1}-p_n,n \geq 0$ 。而 $\Delta^kp_n=\Delta^{k-1}(\Delta p_n),k \geq 2$ 滑频。
舉例： $\Delta^2p_n=\Delta(\Delta p_n)=\Delta(p_{n+1})-\Delta(p_n)=p_{n+2}-2p_{n+1}+p_n$ 捡偏。
定理
假設(shè)數(shù)列 $\{p_n\}_{n=0}^{\infty}$ 線性收斂到 $p$ ，且對(duì)所有 $n \geq 0$ 有 $p-p_n \neq 0$ 峡迷。如果這里存在一個(gè)實(shí)數(shù) $A$ 银伟，有 $|A|<1$ 使得
$\lim_{n \rightarrow \infty}\frac{p-p_{n+1}}{p-p_n}=A,$
則我們可以定義數(shù)列 $\{q_n\}_{n=0}^{\infty}$ 有
$q_n=p_n-\frac{(\Delta p_n)^2}{\Delta^2p_n}=p_n-\frac{(p_{n+1}-p_n)^2}{p_{n+2}-2p_{n+1}+p_n}$
通過 $\lim_{n \rightarrow \infty}|\frac{p-q_n}{p-p_n}|=0$ 我們可以知道 $q_n$ 收斂要快于 $p_n$ 。

方法六 Muller's Method

該方法是割線法的另一種演繹绘搞，只是減去了導(dǎo)數(shù)的計(jì)算彤避，但需要三個(gè)點(diǎn)。該方法比割線法快甚至幾乎和牛頓法一樣快夯辖，但會(huì)涉及復(fù)雜一點(diǎn)的運(yùn)算琉预。
假設(shè) $p_2$ 是最近似 $p$ 的點(diǎn)，定義變量 $t=x-p_2$ 楼雹， $h_0=p_0-p_2$ 模孩， $h_1=p_1-p_2$ 。
定義二元方程 $y=at^2+bt+c$ 贮缅。
代入榨咐，我們可以分別得到以下式子：
$t=h_0:ah_0^2+bh_0+c=f_0,$

$t=h_1:ah_1^2+bh_1+c=f_1,$

$t=0:a0^2+b0+c=f_2,$

通過以上式子我們求得 $a,b,c$ 。然后求根 $z=\frac{-2c}{b\pm \sqrt{b^2-4ac}}$ 谴供。最后可得 $p_3=p_2+|z|$ 块茁。在之后的迭代中，我們舍去 $\{p_0,p_1,p_3\}$ 中離 $p$ 最遠(yuǎn)的點(diǎn)，并將 $p_2=p_3$ 数焊。

詞匯學(xué)習(xí)

spherical 球形
corollary 必然的
oscillate 擺動(dòng)
interval 間隔的
consecutive 連續(xù)的
leisure 休閑
concavity 凹
slope 坡
quotient 商
secant 割線
projectile 彈丸
elapse 過去
fitfall 健身
lemma 引理
asymptotic 漸進(jìn)的
parabola 拋物線
auxiliary 輔助的

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末永淌，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子佩耳，更是在濱河造成了極大的恐慌遂蛀，老刑警劉巖，帶你破解...
沈念sama閱讀 211,639評(píng)論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件干厚，死亡現(xiàn)場(chǎng)離奇詭異李滴，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)蛮瞄，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,277評(píng)論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門所坯，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人挂捅，你說我怎么就攤上這事芹助。” “怎么了闲先？”我有些...
開封第一講書人閱讀 157,221評(píng)論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵状土，是天一觀的道長(zhǎng)。經(jīng)常有香客問我饵蒂，道長(zhǎng)声诸，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 56,474評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任退盯，我火速辦了婚禮，結(jié)果婚禮上泻肯，老公的妹妹穿的比我還像新娘渊迁。我一直安慰自己，他們只是感情好灶挟，可當(dāng)我...
茶點(diǎn)故事閱讀 65,570評(píng)論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布琉朽。她就那樣靜靜地躺著，像睡著了一般稚铣。火紅的嫁衣襯著肌膚如雪箱叁。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,816評(píng)論 1贊 290
城市分裂傳說
那天惕医，我揣著相機(jī)與錄音耕漱，去河邊找鬼。笑死抬伺，一個(gè)胖子當(dāng)著我的面吹牛螟够，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播，決...
沈念sama閱讀 38,957評(píng)論 3贊 408
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼妓笙，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼若河！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起寞宫，我...
開封第一講書人閱讀 37,718評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤萧福，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后辈赋，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體鲫忍，經(jīng)...
沈念sama閱讀 44,176評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,511評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年炭庙，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了饲窿。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,646評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡焕蹄，死狀恐怖逾雄，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情腻脏，我是刑警寧澤鸦泳，帶...
沈念sama閱讀 34,322評(píng)論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站永品，受9級(jí)特大地震影響做鹰，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜鼎姐，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,934評(píng)論 3贊 313
男人毒藥：我在死后第九天來索命
文/蒙蒙一钾麸、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧炕桨，春花似錦饭尝、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,755評(píng)論 0贊 21
一樁弒父案钥平，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至姊途，卻和暖如春涉瘾，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背捷兰。一陣腳步聲響...
開封第一講書人閱讀 31,987評(píng)論 1贊 266
情欲美人皮
我被黑心中介騙來泰國(guó)打工立叛，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人寂殉。一個(gè)月前我還...
沈念sama閱讀 46,358評(píng)論 2贊 360
代替公主和親
正文我出身青樓囚巴，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子彤叉，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,514評(píng)論 2贊 348