方程組的迭代解法

方程組的迭代解法第1頁，共86頁，2023年，2月20日，星期五

公元前1700年的古巴比倫人就已有關(guān)于一、二次方程的解法。

《九章算術(shù)》(公元前50~100年)其中“方程術(shù)”有聯(lián)立一次方程組的一般解法。

1535年意大利數(shù)學(xué)家尼柯洛馮塔納找到了一元三次方程一般形式的求根方法。這個成就，使他在幾次公開的數(shù)學(xué)較量中大獲全勝，從此名揚(yáng)歐洲。但是馮塔納不愿意將他的這個重要發(fā)現(xiàn)公之于世.第2頁，共86頁，2023年，2月20日，星期五

當(dāng)時的另一位意大利數(shù)學(xué)家兼醫(yī)生卡爾丹諾，對馮塔納的發(fā)現(xiàn)非常感興趣。他幾次誠懇地登門請教，希望獲得馮塔納的求根公式。后來，馮塔納終于用一種隱晦得如同咒語般的語言，把三次方程的解法“透露”給了卡爾丹諾。馮塔納認(rèn)為卡爾丹諾很難破解他的“咒語”，可是卡爾丹諾通過解三次方程的對比實(shí)踐，很快就徹底破譯了馮塔納的秘密。第3頁，共86頁，2023年，2月20日，星期五卡爾丹諾把馮塔納的三次方程求根公式，寫進(jìn)了自己的學(xué)術(shù)著作《大法》中，但并未提到馮塔納的名字。由于第一個發(fā)表三次方程求根公式的人確實(shí)是卡爾丹諾，因此后人就把這種求解方法稱為“卡爾丹諾公式”。第4頁，共86頁，2023年，2月20日，星期五后來，卡爾丹諾的學(xué)生弗瑞里(Ferrari)又提出了四次方程的解法。但對于五次方程求根，求索工作始終沒有成效，導(dǎo)致人們對高次代數(shù)方程解的存在性產(chǎn)生了懷疑。1828年17歲的法國數(shù)學(xué)家伽羅華(E·Galois1811-1832)寫出了劃時代的論文“關(guān)于五次方程的代數(shù)解法問題”，指出即使在公式中容許用n次方根，并用類似算法求五次或更高次代數(shù)方程的根是不可能的第5頁，共86頁，2023年，2月20日，星期五文章呈交法蘭西科學(xué)院后，因輩份太低遭到冷遇，且文稿丟失。1830年伽羅華再進(jìn)科學(xué)院遞稿，得到泊松院士的判詞“完全不能理解”。后來伽羅華命運(yùn)不佳，投考名校巴黎工科大學(xué)落榜，屈就高等師院，并卷入政事兩次入獄，被開除學(xué)籍，又決斗受傷，死于1832年。決斗前，他把關(guān)于五次代數(shù)求解的研究成果寫成長信，留了下來。第6頁，共86頁，2023年，2月20日，星期五

十四年后，法國數(shù)學(xué)家劉維爾(J·Liouville)整理并發(fā)表了伽羅華的遺作，人們才意識到這項(xiàng)近代數(shù)學(xué)發(fā)展史上的重要成果的寶貴。38年后，即1870年，法國數(shù)學(xué)家若當(dāng)(C·Jordan)在專著《論置換與代數(shù)方程》中闡發(fā)了伽羅華的思想，一門現(xiàn)代數(shù)學(xué)的分支—群論誕生了。在前幾個世紀(jì)中，曾開發(fā)出一些求解代數(shù)方程的有效算法，它們構(gòu)成了數(shù)值分析中的古典算法。至于超越方程則不存在一般的求根方式。第7頁，共86頁，2023年，2月20日，星期五1.根的存在性定理1：設(shè)函數(shù)f(x)在區(qū)間[a,b]上連續(xù)，如果f(a)

f(b)<0，

則方程f(x)=0在[a,b]內(nèi)至少有一實(shí)根x*。

定義：如果存在使得，則稱為方程（3.1.1）的根或函數(shù)的零點(diǎn)。（3.1.1）第8頁，共86頁，2023年，2月20日，星期五m重根若其中，為正整數(shù)，則當(dāng)m=1時，稱為方程（3.1.1）的m重根或函數(shù)的m重零點(diǎn)。的單根或函數(shù)的單零點(diǎn)。稱為方程（3.1.1）當(dāng)時，（3.1.1）第9頁，共86頁，2023年，2月20日，星期五2.根的搜索(1)圖解法（利用作圖軟件如Matlab)(2)掃描法（逐步搜索法）(3)二分法*第10頁，共86頁，2023年，2月20日，星期五

（1）(描)做圖法

畫出y=f(x)

的草圖,由f(x)與橫軸交點(diǎn)的大概位置來確定隔根區(qū)間;或者利用導(dǎo)函數(shù)f(x)的正、負(fù)與函數(shù)f(x)的單調(diào)性的關(guān)系確定根的大概位置.

若f(x)比較復(fù)雜,還可將方程f(x)=0化為一個等價方程(x)=(x),

則曲線y=(x)與y=(x)之交點(diǎn)A(x*,y*)的橫坐標(biāo)x*即為原方程之根,據(jù)此也可通過作圖求得x*的隔根區(qū)間.第11頁，共86頁，2023年，2月20日，星期五如求解方程的近似根

方法1:將方程同解變換成然后畫兩條曲線第12頁，共86頁，2023年，2月20日，星期五023yx這兩條曲線的交點(diǎn)的橫座標(biāo)大致為x=2.5第13頁，共86頁，2023年，2月20日，星期五abx*f(x)1．畫出f(x)的略圖，從而看出曲線與x軸交點(diǎn)的位置。2．從左端點(diǎn)x=a出發(fā)，按某個預(yù)先選定的步長h一步一步地向右跨，每跨一步都檢驗(yàn)每步起點(diǎn)x0和終點(diǎn)x0+h的函數(shù)值，若那么所求的根x*必在x0與x0+h之間，這里可取x0或x0+h作為根的初始近似。(2)掃描法（逐步搜索法）第14頁，共86頁，2023年，2月20日，星期五例1：考察方程x00.51.01.5f(x)的符號－－－＋第15頁，共86頁，2023年，2月20日，星期五（3）二分法*（對分法）

設(shè)f(x)在區(qū)間[a,b]上連續(xù),f(a)·f(b)<0,則在[a,b]

內(nèi)有方程的根.取[a,b]的中點(diǎn)

將區(qū)間一分為二.若f(x0)=0,則x0就是方程的根,否則判別根x*在x0

的左側(cè)還是右側(cè).若f(a)·f(x0)<0,則x*∈(a,x0),令a1=a,b1=x0;若f(x0)·f(b)<0,則x*∈(x0

,b),令a1=x0,b1=b.

不論出現(xiàn)哪種情況,(a1,b1)均為新的有根區(qū)間,它的長度只有原有根區(qū)間長度的一半,達(dá)到了壓縮有根區(qū)間的目的.第16頁，共86頁，2023年，2月20日，星期五

對壓縮了的有根區(qū)間,又可實(shí)行同樣的步驟,再壓縮.如此反復(fù)進(jìn)行,即可的一系列有根區(qū)間套

由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間[an,bn]的長度為若每次二分時所取區(qū)間中點(diǎn)都不是根，則上述過程將無限進(jìn)行下去.當(dāng)

n→∞

時，區(qū)間必將最終收縮為一點(diǎn)x*

，顯然x*就是所求的根.第17頁，共86頁，2023年，2月20日，星期五誤差

分析：第1步產(chǎn)生的有誤差第k步產(chǎn)生的xk

有誤差對于給定的精度

,可估計(jì)二分法所需的步數(shù)k：①簡單;②對f(x)

要求不高(只要連續(xù)即可).①無法求復(fù)根及偶重根②收斂慢第18頁，共86頁，2023年，2月20日，星期五2.由于在偶重根附近曲線y=f(x)

為上凹或下凸,即f(a)與f(b)的符號相同,因此不能用二分法求偶重根.注：1.用二分法求根，最好先給出f(x)

草圖以確定根的大概位置?；蛴盟阉鞒绦颍瑢a,b]分為若干小區(qū)間，對每一個滿足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個根，且不必要求f(a)·f(b)<0。第19頁，共86頁，2023年，2月20日，星期五

二分法的執(zhí)行步驟1．計(jì)算f(x)在有解區(qū)間[a,b]端點(diǎn)處的值，f(a)，f(b)。2．計(jì)算f(x)在區(qū)間中點(diǎn)處的值f(x1)。3．判斷若f(x1)=0，則x1即是根，否則檢驗(yàn)：（1）若f(x1)與f(a)異號，則知解位于區(qū)間[a,x1]，

b1=x1,a1=a;（2）若f(x1)與f(a)同號，則知解位于區(qū)間[x1,b]，

a1=x1,b1=b。反復(fù)執(zhí)行步驟2、3，便可得到一系列有根區(qū)間：

第20頁，共86頁，2023年，2月20日，星期五4、當(dāng)時，停止；即為根的近似。當(dāng)時，，即這些區(qū)間必將收縮于一點(diǎn)，也就是方程的根。在實(shí)際計(jì)算中，只要的區(qū)間長度小于預(yù)定容許誤差就可以停止搜索，即然后取其中點(diǎn)作為方程的一個根的近似值。注：第21頁，共86頁，2023年，2月20日，星期五例2證明方程存在唯一的實(shí)根用二分法求出此根，要求誤差不超過。解：記，則對任意

，因而，是嚴(yán)格單調(diào)的，最多有一個根，所以，有唯一實(shí)根又因?yàn)?/p>

第22頁，共86頁，2023年，2月20日，星期五用二分法求解，要使，只要解得，取。所以只要二等分7次，即可求得滿足精度要求的根。計(jì)算過程如下表所示k

f(ak)及符號f(xk)及符號f(bk)及符號012345670(－)0(－)0(－)0(－)0.0625(－)0.0625(－)0.078125(－)0.0859375(－)0.5(+)0.25(+)0.125(+)0.0625(－)0.09375(+)0.078125(－)0.0859375(－)1(+)0.5(+)0.25(+)0.125(+)0.125(+)0.09375(+)0.09375(+)0.09375(+)表3.1所以，第23頁，共86頁，2023年，2月20日，星期五

問題雖然二分法計(jì)算簡單，能夠保證收斂，但是它對于方程單根存在區(qū)域信息要求太高，一般情況下很難實(shí)現(xiàn)，并且不能求偶重根、復(fù)根和虛根。在實(shí)際應(yīng)用中，用來求解方程根的主要方法是迭代法。使用迭代法求解非線性代數(shù)方程的步驟為：(1)迭代格式；(2)迭代格式的收斂性的構(gòu)造分析；(3)迭代格式的收斂速度與誤差分析。3.2迭代法及其收斂性第24頁，共86頁，2023年，2月20日，星期五3.2.1不動點(diǎn)迭代法

將方程f(x)=0改寫為等價方程形式

x=(x).(3.2.1)若要求x*滿足f(x*)=0，則x*=(x*)；反之亦然，稱x*為函數(shù)(x)的一個不動點(diǎn).求f(x)的零點(diǎn)就等于求(x)的不動點(diǎn)，選擇一個初始近似值x0，將它代入(3.2.1)右端，即可求得

x1=(x0).第25頁，共86頁，2023年，2月20日，星期五可以如此反復(fù)迭代計(jì)算xk+1=(xk)

(k=0,1,2,).(3.2.2)

(x)稱為迭代函數(shù).如果對任何x0∈[a,b]，由(3.2.2)得到的序列{xk}有極限則稱迭代方程(3.2.2)收斂.且x*=(x*)為(x)的不動點(diǎn)，故稱(3.2.2)為不動點(diǎn)迭代法.

上述迭代法是一種逐次逼近法，其基本思想是將隱式方程(3.1.1)歸結(jié)為一組顯式的計(jì)算公式(3.2.2)，迭代過程實(shí)質(zhì)上是一個逐步顯式化過程.第26頁，共86頁，2023年，2月20日，星期五當(dāng)(x)連續(xù)時，顯然x*就是方程x=(x)之根(不動點(diǎn)).于是可以從數(shù)列{xk}中求得滿足精度要求的近似根.這種求根方法稱為不動點(diǎn)迭代法,稱為迭代格式,(x)稱為迭代函數(shù),x0

稱為迭代初值,數(shù)列{xk}稱為迭代序列.如果迭代序列收斂,則稱迭代格式收斂,否則稱為發(fā)散.第27頁，共86頁，2023年，2月20日，星期五3.2.2

迭代法的幾何意義

通常將方程f(x)=0化為與它同解的方程的方法不止一種,有的收斂,有的不收斂,這取決于的性態(tài),方程的求根問題在幾何上就是確定曲線y=與直線y=x的交點(diǎn)P*的橫坐標(biāo)第28頁，共86頁，2023年，2月20日，星期五xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1第29頁，共86頁，2023年，2月20日，星期五例3：求方程的一個根.構(gòu)造迭代格式x1=0.4771x2=0.3939 …x6=0.3758x7=0.3758解：給定初始點(diǎn)第30頁，共86頁，2023年，2月20日，星期五分別按以上三種形式建立迭代公式，并取x0=1進(jìn)行迭代計(jì)算，結(jié)果如下：

解對方程進(jìn)行如下三種變形：

例3

用迭代法求方程x4+2x2-x-3=0

在區(qū)間[1,1.2]內(nèi)的實(shí)根.第31頁，共86頁，2023年，2月20日，星期五準(zhǔn)確根x*

=1.124123029,可見迭代公式不同,收斂情況也不同.第二種公式比第一種公式收斂快得多,而第三種公式不收斂.第32頁，共86頁，2023年，2月20日，星期五

例3表明原方程化為

x=(x)

的形式不同，有的收斂，有的不收斂，有的發(fā)散，只有收斂的的迭代過程xk+1=(xk)

(k=0,1,2,)才有意義，為此我們首先要研究(x)的不定點(diǎn)的存在性及迭代法xk+1=(xk)的收斂性.第33頁，共86頁，2023年，2月20日，星期五3.2.3不動點(diǎn)的存在性與迭代法的收斂性

首先考察(x)在[a,b]上不動點(diǎn)的存在唯一性.

定理1

設(shè)(x)∈C[a,b]滿足以下兩個條件：

1o

對任意x∈[a,b]有a≤(x)≤b.

2o

存在正數(shù)L<1，使對任意x,y∈[a,b]都有則(x)在[a,b]上存在唯一的不動點(diǎn)x*.

證明先證不動點(diǎn)的存在性.若(a)=a或(b)=b，顯然(x)在[a,b]上存在不動點(diǎn).因?yàn)閍≤(x)≤b，以下設(shè)(a)>a及(b)<b定義函數(shù)第34頁，共86頁，2023年，2月20日，星期五顯然f(x)∈C[a,b],且滿足f(a)=(a)-a>0,f(b)=(b)-b<0,由連續(xù)函數(shù)性質(zhì)可知存在x*∈(a,b)使f(x*)=0，即x*=(x*)，x*即為(x)的不動點(diǎn).

再證不動點(diǎn)的唯一性.設(shè)x1*,x2*∈[a,b]都是(x)的不動點(diǎn)，則由(3.2.3)得引出矛盾，故(x)的不動點(diǎn)只能是唯一的.

證畢.

在(x)的不動點(diǎn)存在唯一的情況下，可得到迭代法xk+1=(xk)收斂的一個充分條件.第35頁，共86頁，2023年，2月20日，星期五

定理2

設(shè)(x)∈C[a,b]滿足定理1中的兩個條件，則對任意x0∈[a,b]，由xk+1=(xk)得到的迭代序列{xk}收斂到的不動點(diǎn)x*，并有誤差估計(jì)式

證明設(shè)x*∈[a,b]是(x)在[a,b]上的唯一不動點(diǎn),由條件1o，可知{xk}∈[a,b]，再由(3.2.3)得因0<L<1，故當(dāng)k→∞時序列{xk}收斂到x*.第36頁，共86頁，2023年，2月20日，星期五下面證明估計(jì)式(3.2.4)，由(3.2.3)有于是對任意正整數(shù)p有上述令p→∞,注意到limxk+p=x*(p→∞)即得(3.2.4)式.第37頁，共86頁，2023年，2月20日，星期五又由于對任意正整數(shù)p有上述令p→∞,及l(fā)imxk+p=x*(p→∞)即得(3.2.5)式.證畢.

迭代過程是個極限過程.在用迭代法進(jìn)行時，必須按精度要求控制迭代次數(shù).誤差估計(jì)式(3.2.4)原則上確定迭代次數(shù)，但它由于含有信息L而不便于實(shí)際應(yīng)用.而誤差估計(jì)式(3.2.5)是實(shí)用的，只要相鄰兩次計(jì)算結(jié)果的偏差足夠小即可保證近似值xk具有足夠精度.第38頁，共86頁，2023年，2月20日，星期五

對定理1中的條件2o可以改為導(dǎo)數(shù)，即在使用時如果(x)∈C[a,b]且對任意x∈[a,b]有則由微分中值定理可知對任意x,y∈[a,b]有故定理1中的條件2o是成立的.

第39頁，共86頁，2023年，2月20日，星期五例如，在前面例3中采用的三種迭代公式，在隔根區(qū)間(1,1.2)內(nèi)，有故前兩個迭代公式收斂，第三個迭代公式不收斂.第40頁，共86頁，2023年，2月20日，星期五例4：求方程在內(nèi)的根。解：原方程可以等價變形為下列三個迭代格式第41頁，共86頁，2023年，2月20日，星期五由迭代格式（1）

取初值得

結(jié)果是發(fā)散的？！第42頁，共86頁，2023年，2月20日，星期五由迭代格式（2）

取初值得

結(jié)果精確到四位有效數(shù)字，迭代到得到收斂結(jié)果。

第43頁，共86頁，2023年，2月20日，星期五

由迭代格式（3）

取初值得

結(jié)果精確到四位有效數(shù)字，迭代到得到收斂結(jié)果。四步就能得到收斂的結(jié)果了！第44頁，共86頁，2023年，2月20日，星期五迭代格式（1）的迭代函數(shù)為

求導(dǎo)得

當(dāng)時故迭代格式（1）是發(fā)散的。分析:第45頁，共86頁，2023年，2月20日，星期五

迭代格式（2）的迭代函數(shù)為

當(dāng)時由于第46頁，共86頁，2023年，2月20日，星期五知當(dāng)時，

所以迭代格式（2）是收斂的。第47頁，共86頁，2023年，2月20日，星期五迭代格式（3）的迭代函數(shù)為當(dāng)時

第48頁，共86頁，2023年，2月20日，星期五由時，

知當(dāng)所以迭代格式（3）也是收斂的。第49頁，共86頁，2023年，2月20日，星期五結(jié)論:

通過以上算例可以看出對迭代函數(shù)所得到的若小于1，則收斂；且上界越小收斂速度越快。求導(dǎo)，的上界若是大于1，則迭代格式發(fā)散；第50頁，共86頁，2023年，2月20日，星期五3.2.4局部收斂性與收斂階

上面給出了迭代序列{xk}在區(qū)間[a,b]上的收斂性,通常稱為全局收斂性.有時不易檢驗(yàn)定理的條件，實(shí)際應(yīng)用時通常只在不動點(diǎn)x*的鄰近考察其收斂性，即局部收斂性.

定義1

設(shè)(x)有不動點(diǎn)x*，如果存在x*的某個鄰域R:|x-x*|≤δ，對任意x0∈R，迭代公式(3.2.2)產(chǎn)生的序列{xk}∈R，且收斂到x*，則稱迭代法(3.2.2)局部收斂.

第51頁，共86頁，2023年，2月20日，星期五

定理3

設(shè)x*為(x)的不動點(diǎn)，在x*的某個鄰域連續(xù)，且，則迭代法xk+1=(xk)局部收斂.

證明由連續(xù)函數(shù)的性質(zhì)，存在不動點(diǎn)x*的某個鄰域R:|x-x*|≤δ，使對于任意x∈R成立此外，對于任意x∈R，總有(x)∈R，這時因?yàn)橛谑且罁?jù)定理2可以斷定迭代過程xk+1=(xk)對于任意初值x0∈R均收斂.證畢.第52頁，共86頁，2023年，2月20日，星期五

例5

用不同迭代法求方程x2-3=0的根.

解這里f(x)=

x2-3，可以改寫為各種不同的等價形式x=(x)，其不動點(diǎn)為，由此構(gòu)造不同的迭代法.第53頁，共86頁，2023年，2月20日，星期五取x0=2,對上式4種迭代法,計(jì)算三步所得結(jié)果入下表.kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123┆

x0x1x2x3┆23987┆21.521.5┆21.751.734751.732361┆21.751.7321431.732051┆第54頁，共86頁，2023年，2月20日，星期五

注意，從計(jì)算結(jié)果看到迭代法(1)及(2)均不收斂，且它們均不滿足定理3中的局部收斂條件，迭代法(3)和(4)均滿足局部收斂條件，且迭代法(4)比(3)收斂快，因在迭代法(4)中(x*)=0.為了衡量迭代法(3.2.2)收斂速度的快慢可給出以下定義.

定義2

設(shè)迭代過程xk+1=(xk)收斂于方程x=(x)的根x*，如果迭代誤差ek=xk-x*當(dāng)k→∞時成立下列漸近關(guān)系式則稱該迭代法是p階收斂的.特別地，p=1時稱線性收斂，p>1時稱超線性收斂，p=2時稱平方收斂.第55頁，共86頁，2023年，2月20日，星期五

定理4

對于迭代過程xk+1=(xk)，如果(p)(x)在所求根x*的鄰近連續(xù)，并且則該迭代過程在x*的鄰近是p階收斂的.

證明由于(x*)=0，根據(jù)定理3立即可以斷定迭代過程xk+1=(xk)具有局部收斂性.

再將(xk)在根x*處做泰勒展開,利用條件(3.2.7),則有注意到(xk)=xk+1，(x*)=x*，由上式得第56頁，共86頁，2023年，2月20日，星期五因此對迭代誤差，令k→∞時有這表明迭代過程xk+1=(xk)確實(shí)為p階收斂.證畢.

上述定理告訴我們，迭代過程的收斂速度依賴于迭代函數(shù)(x)的選取.如果x∈[a,b]但(x)≠0時，則該迭代過程只可能是線性收斂.第57頁，共86頁，2023年，2月20日，星期五的三階方法.假設(shè)

x0

充分靠近x*,求

證明首先由泰勒展式可得

例子證明迭代公式

xk+1=xk(xk2+3a)/(3xk2+a)是求而1/4a≠0，故此迭代公式是三階方法.第58頁，共86頁，2023年，2月20日，星期五3.3迭代收斂的加速方法埃特金加速收斂方法

對于收斂的迭代過程，只要迭代足夠多次，就可以使結(jié)果達(dá)到任意的精度，但是有時迭代過程收斂較慢，從而使計(jì)算量變得很大，因此迭代過程的加速是個重要的課題.設(shè)x0是根x*的某個近似值,用迭代公式校正一次得

x1=(x0)而由微分中值定理，有第59頁，共86頁，2023年，2月20日，星期五假設(shè)(x)改變不大,近似地取某個近似值L,則有由于

x2-x*≈L(x1-x*).若將校正值x1=(x0)再校正一次，又得

x2=(x1)將它與(3.3.1)式聯(lián)立，消去未知的L，有由此推知第60頁，共86頁，2023年，2月20日，星期五在計(jì)算了x1及x2之后，可用上式右端作為x*的新近似,記作?x1，一般情形是由xk計(jì)算xk+1,xk+2，記它表明序列{?xk}的收斂速度比{xk}的收斂速度快.(3.3.2)式稱為埃特金(Aitken)△2加速方法.

可以證明第61頁，共86頁，2023年，2月20日，星期五也稱為埃特金(Aitken)外推法.可以證明:為線性收斂,則埃特金法為平方收斂；

這個加速迭代法也可寫成下面格式若為p(p>1)階收斂，導(dǎo)數(shù)連續(xù)，則埃特金法為2p–1

階收斂.的

p

階若第62頁，共86頁，2023年，2月20日，星期五

例題求方程x=e–x

在x=0.5

附近的根.

解取x0=0.5,迭代格式x25=x26=0.5671433

若對此格式用埃特金法,則

得第63頁，共86頁，2023年，2月20日，星期五仍取x0=0.5,得由此可見,埃特金法加速收斂效果是相當(dāng)顯著的.第64頁，共86頁，2023年，2月20日，星期五3.4牛頓法3.4.1牛頓法及其收斂性

對于方程f(x)=0，如果f(x)是線性函數(shù)，則它的求根是容易的.牛頓法實(shí)質(zhì)上是一種線性化方法，其基本思想是將非線性方程f(x)=0逐步歸結(jié)為某種線性方程來求解.

設(shè)已知方程f(x)=0有近似根x0，且在x0附近f(x)可用一階泰勒多項(xiàng)式近似，表示為一、牛頓迭代法第65頁，共86頁，2023年，2月20日，星期五當(dāng)f(x0)≠0時，方程f(x)=0可用線性方程(切線)近似代替，即f(x0)+f(x0)(x-x0)=0.

(3.4.1)解此線性方程得得迭代公式此式稱為牛頓(Newton)迭代公式.第66頁，共86頁，2023年，2月20日，星期五牛頓法有顯然的幾何意義，方程f(x)=0的根x*可解釋為曲線y=f(x)與x軸交點(diǎn)的橫坐標(biāo).設(shè)xk是根x*的某個近似值，過曲線y=f(x)上橫坐標(biāo)為xk的點(diǎn)Pk引切線，并將該切線與x軸交點(diǎn)的橫坐標(biāo)xk+1作為x*的新的近似值.注意到切線方程為這樣求得的值xk+1必滿足(3.4.1),從而就是牛頓公式(3.4.2)的計(jì)算結(jié)果.由于這種幾何背景，所以牛頓迭代法也稱切線法.xyx*xky=f(x)xk+1PkPk+1xk+2第67頁，共86頁，2023年，2月20日，星期五二、牛頓法的收斂性定理4：

設(shè)f(x)在[a,b]上存在二階連續(xù)導(dǎo)數(shù)且滿足下列條件： （1）f(a)

f(b)<0； （2）f’(x)0； （3）f(x)在區(qū)間[a,b]上不變號； （4）取x0[a,b]，使得f(x)f(x0)>0則由（2）（3）確定的牛頓迭代序列{xk}二階收斂于f(x)在[a,b]上的唯一單根x*。第68頁，共86頁，2023年，2月20日，星期五第69頁，共86頁，2023年，2月20日，星期五牛頓法收斂性依賴初值x0的選取,如果x0偏離所求根x*較遠(yuǎn),則牛頓法可能發(fā)散.x*x0x0x0第70頁，共86頁，2023年，2月20日，星期五

例如，用牛頓法求解方程x3-x-1=0.此方程在x=1.5附近的一個根x*.設(shè)取迭代初值x0=1.5，用牛頓迭代法公式計(jì)算得x1=1.34783,x2=1.32520,x3=1.32472.迭代3次得到的結(jié)果x3有6位有效數(shù)字.但是，如取x0=0.6，用上式迭代1次得計(jì)算得x1=17.9.這個結(jié)果反而比x0=0.6更偏離了所求的根x*=1.32472.第71頁，共86頁，2023年，2月20日，星期五由此得到，當(dāng)x*為單根時，牛頓迭代法在根x*的鄰近是二階(平方)收斂的.

定理(局部收斂性)

設(shè)fC2[a,b],若x*為f(x)在[a,b]上的根，且f(x*)0，則存在x*的鄰域U,使得任取初值x0U，牛頓法產(chǎn)生的序列{xk}收斂到x*，且滿足即有下面的局部收斂性定理.第72頁，共86頁，2023年，2月20日，星期五設(shè)x*是f(x)的一個單根，即f(x*)=0，f(x*)≠0,有牛頓迭代法的迭代函數(shù)為第73頁，共86頁，2023年，2月20日，星期五對于給定的正數(shù)C，應(yīng)用牛頓法解二次方程我們現(xiàn)在證明，這種迭代公式對于任意初值x0>0都是收斂的.可導(dǎo)出求開方值的計(jì)算程序3.4.2牛頓法應(yīng)用舉例第74頁，共86頁，2023年，2月20日，星期五事實(shí)上，對(3.4.3)式施行配方整理，易知以上兩式相除得據(jù)此反復(fù)遞推有第75頁，共86頁，2023年，2月20日，星期五記整理(3.4.4)式，得對任意初值x0>0，總有|q|<1，故由上式推知，當(dāng)k→∞時，即迭代過程恒收斂.第76頁，共86頁，2023年，2月20日，星期五

解將原方程化為x–e–x=0，則牛頓迭代公式為取x0=0.5，迭代得x1=0.566311,x2=0.5671431,x3=0.5671433.

f(x)=x–e–x，f(x)=1+e–x，

例7

用牛頓迭代法求方程x=e–x在x=0.5附近的根.第77頁，共86頁，2023年，2月20日，星期五3.4.3簡化牛頓法與牛頓下山法牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)①每步迭代要計(jì)算f(xk)及f(xk)，計(jì)算量較大，且有時f(xk)計(jì)算較困難；②初始近似值x0只在根x*附近才能保證收斂，如x0給的不合適可能不收斂.為克服這兩個缺點(diǎn)，通?？捎孟率龇椒?

簡化牛頓法，也稱平行弦法，其迭代公式為迭代函數(shù)為(x)=x-Cf(x).第78頁，共86頁，2023年，2月20日，星期五若|