解非線性方程的迭代法

解非線性方程的迭代法設(shè)

(x)在區(qū)間[a,b]上連續(xù)且(a)(b)<0,根據(jù)連續(xù)函數(shù)的介值定理,區(qū)間[a,b]上必有方程(x)=0的根,稱[a,b]為方程(x)=0的有根區(qū)間.ab

xy=(x)x0x1y0設(shè)

(x)在區(qū)間[a,b]上連續(xù)且(a)(b)<0.二分法的基本思想是：將有根區(qū)間逐次分半，每次保留新的有根區(qū)間，其長(zhǎng)度減少一半，這樣有根區(qū)間長(zhǎng)度將逐漸縮小，直至縮為一點(diǎn)，此點(diǎn)即為方程的根。a1=ab1=x0a2=x1b2=b1第2頁(yè),共32頁(yè)，2024年2月25日，星期天得到新的有根區(qū)間[a1,b1],下面說明二分法的數(shù)學(xué)計(jì)算過程。0ab

yxy=(x)記a0=a,b0=b,計(jì)算若(a0)(x0)<0,取a1=a0,b1=x0;若(a0)(x0)>0,取a1=x0,b1=b0而且有根區(qū)間[a1,b1]長(zhǎng)度是有根區(qū)間[a0,b0]長(zhǎng)度的一半；x0再對(duì)有根區(qū)間[a1,b1]重復(fù)上面運(yùn)算,即:計(jì)算若(a1)(x1)<0,取a2=a1,b2=x1;若(a1)(x1)>0,取a2=x1,b2=b1,得到新的有根區(qū)間[a2,b2].而且有根區(qū)間x1[a2,b2]長(zhǎng)度是有根區(qū)間[a1,b1]長(zhǎng)度的一半.一直進(jìn)行下去,直到求出有根區(qū)間[ak,bk].第3頁(yè),共32頁(yè)，2024年2月25日，星期天再計(jì)算當(dāng)|bk-ak|<時(shí)停止計(jì)算，取xk?？梢?k趨向無(wú)窮大時(shí),xk收斂于

.而且,若要|xk-|<,只要此時(shí)可取近似根xk.在計(jì)算過程中,若出現(xiàn)|(xk)|<,或bk-ak<，則可取xk作為方程(x)=0的近似根,終止運(yùn)算.例1用二分法求x3+4x-7=0在區(qū)間[1,2]內(nèi)根的近似值,并估計(jì)誤差.顯然有第4頁(yè),共32頁(yè)，2024年2月25日，星期天

解這里

(x)=x3+4x-7，(1)(2)=-18<0,而且(x)=3x2+4>0,所以(x)=0在[1,2]區(qū)間有唯一根.取x0=1.5,由于

(x0)=2.375,得新有根區(qū)間[1,1.5],x1=1.25,由于

(x1)=-0.0468,得新有根區(qū)間[1.25,1.5],x2=1.375,由于

(x2)=1.0996,得新有根區(qū)間[1.25,1.375],x3=1.3125,由于

(x3)=0.511,得新有根區(qū)間[1.25,1.3125],

………………….x9=1.254882813,得有根區(qū)間[1.254882813,1.255859375],x10=1.255371094,(x10)=-0.000105285取

x10=1.255371094作為方程根的近似值,且有第5頁(yè),共32頁(yè)，2024年2月25日，星期天只需k>5ln210-115.61.即需取k=16,x16.如果取精度

=10-5,則要使二分法要求函數(shù)在區(qū)間[a，b]上連續(xù)，且在區(qū)間兩端點(diǎn)函數(shù)值符號(hào)相反，二分法運(yùn)算簡(jiǎn)便、可靠、易于在計(jì)算機(jī)上實(shí)現(xiàn)。但是，若方程

(x)=0在區(qū)間[a，b]上根多于1個(gè)時(shí)，也只能求出其中的一個(gè)根。另外，若方程(x)=0在區(qū)間[a，b]有重根時(shí)，也未必滿足(a)(b)<0.而且由于二分法收斂的速度不是很快,一般不單獨(dú)使用,而多用于為其他方法提供一個(gè)比較好的初始近似值.ab

(x)第6頁(yè),共32頁(yè)，2024年2月25日，星期天

§2.1簡(jiǎn)單迭代法的一般形式§2簡(jiǎn)單迭代法首先把方程

(x)=0改寫成等價(jià)(同解)形式

x=(x)(4.2)得到迭代序列{xk},如果xk,對(duì)(4.3)取極限，則有=(),即是方程

(x)=0的根.取一個(gè)適當(dāng)?shù)某跏贾祒0,然后進(jìn)行迭代計(jì)算

xk+1=(xk),k=0,1,2,…(4.3)這種求方程根的方法稱為簡(jiǎn)單迭代法.其中

(x)稱為迭代函數(shù)

,式(4.3)稱為迭代格式.若迭代序列{xk}收斂,

則稱簡(jiǎn)單迭代法是收斂的.第7頁(yè),共32頁(yè)，2024年2月25日，星期天

解由于

(1)(2)=-4<0,則方程在[1,2]內(nèi)有根。改寫原方程為等價(jià)方程。求方程x3-2x-3=0在[1,2]內(nèi)的根.例2

如果取初值x0=1.9,迭代計(jì)算得kxkkxk0123451.91.894536471.893521141.893332331.893297221.89329069678910…1.893289471.893289251.893289211.893289201.89328920……建立迭代格式：第8頁(yè),共32頁(yè)，2024年2月25日，星期天由計(jì)算結(jié)果有，x10=x9，因此可取

x10=1.89328920.

定義4.1

設(shè)

(x)為定義在區(qū)間I上的函數(shù),且對(duì)任何xI,均有(x)I,則稱(x)為I到自身上的映射.方程也可改寫成x=(x3-3)/2,建立迭代格式

xk+1=(xk3-3)/2,k=0,1,2,…仍取初值x0=1.9,則有

x1=1.9295,x2=2.0917,x3=3.0760,x4=13.0529可見,xk,此迭代格式是發(fā)散的.§2.2簡(jiǎn)單迭代法的收斂條件

定義4.2

設(shè)

(x)為I到自身上的映射,且存在0<L<1,使對(duì)任何x1,x2

I,有|(x2)-(x1)|L|x2-x1|,則稱(x)為I上的壓縮映射,L稱為L(zhǎng)ipschitz常數(shù).第9頁(yè),共32頁(yè)，2024年2月25日，星期天顯然，壓縮映射(x)是I上連續(xù)函數(shù)。反之不然,如(x)=x.

定理4.2

若

(x)為I到自身上的映射,且(x)C1(I),|(x)|L<1,則(x)為I上的壓縮映射.

證對(duì)任意x1,x2I,利用中值定理，可有

|(x2)-(x1)|=|()||x2-x1|L|x2-x1|

定義4.3

若

(x)為I到自身上的映射,且I滿足,=(),則稱為(x)的不動(dòng)點(diǎn).(方程

x=(x)的解）

定理4.3

若

(x)為I上的壓縮映射,則(x)在I上存在唯一的一個(gè)不動(dòng)點(diǎn),且對(duì)任何x0I,由迭代格式

xk+1=(xk),k=0,1,2,…產(chǎn)生的序列{xk}收斂于(x)的不動(dòng)點(diǎn).第10頁(yè),共32頁(yè)，2024年2月25日，星期天

證不妨設(shè)I=[a,b],作函數(shù)

(x)=(x)-x,由于x[a,b]時(shí),(x)[a,b],則(a)=(a)-a0,(b)=(b)-b0,由(x)的連續(xù)性,必存在I,使()=()-=0,即=(),就是(x)的不動(dòng)點(diǎn).

唯一性：若

,I均為(x)的不動(dòng)點(diǎn),利用壓縮條件有

|-|=|()-()|L|-|<|-|所以只能=,即(x)在I上僅有一個(gè)不動(dòng)點(diǎn).收斂性：對(duì)任意x0I,有x1=(x0)I,遞推得{xk}I。設(shè)是(x)的不動(dòng)點(diǎn),則由xk+1=(xk)，=()，得到

|xk+1-|=|(xk)-()|L|xk-|L2|xk-1-|…Lk+1|x0-|因L<1,所以xk,k.第11頁(yè),共32頁(yè)，2024年2月25日，星期天

推論

若

(x)C1[a,b],且滿足

1.a(x)b,x[a,b];2.|(x)|L<1,x[a,b].則迭代格式xk+1=(xk),k=0,1,2,…,x0[a,b]都收斂于方程x=(x)在區(qū)間[a,b]的唯一根.在例2中，對(duì)x3-2x-3=0，x

[1,2],建立了兩種迭代格式:xk+1=(xk3-3)/2,k=0,1,2,…,(x)=(x3-3)/2對(duì)第1種可驗(yàn)證：|(x)|<2/3<1,x

[1,2],所以迭代收斂；對(duì)第2種可有：|(x)|=3x2/2>1,x

[1,2],所以不能保證收斂。第12頁(yè),共32頁(yè)，2024年2月25日，星期天實(shí)際上,由連續(xù)性知,存在>0,使對(duì)任何xI=[-,+]都有|(x)|L<1.這種收斂稱為局部收斂，它要求初值x0充分靠近根?！?.3簡(jiǎn)單迭代法的誤差分析與收斂階定理4.4

若

=(),(x)在附近具有一階連續(xù)導(dǎo)數(shù),且|()|<1,則存在>0,當(dāng)x0I=[-,+]時(shí),有

(1)由迭代xk+1=(xk)產(chǎn)生的迭代序列xkI;

(3)

是I上(x)的唯一不動(dòng)點(diǎn).

定理4.5

若

(x)為I上壓縮映射,則x0I,由迭代

xk+1=(xk),k=0,1,2,…，產(chǎn)生的迭代序列xk

滿足估計(jì):第13頁(yè),共32頁(yè)，2024年2月25日，星期天

證由xk+1=(xk),=(),得到

|xk+1-xk|=|(xk)-(xk-1)|L|xk-xk-1||xk+1-|=|(xk)-()|L|xk-|因此|xk-

|=|xk-xk+1+xk+1-||xk+1-xk|+|xk+1-|L|xk-xk-1|+L|xk-|由誤差估計(jì)式可見,對(duì)任一

>0,要使|xk-|<,只要第14頁(yè),共32頁(yè)，2024年2月25日，星期天

求方程xex-1=0在0.5附近的根,精度要求

=10-3.

解可以驗(yàn)證方程xex-1=0在區(qū)間[0.5,0.6]內(nèi)僅有一個(gè)根.例3改寫方程為x=e-x,建立迭代格式由于(x)=e-x,在[0.5,0.6]上有|(x)|e-0.50.6<1.所以迭代法收斂.取初值x0=0.5,計(jì)算得kxk|xk-xk-1|kxk|xk-xk-1|0123450.50.606530.545240.579700.560060.571170.106530.061290.034460.019640.011116789100.564860.568440.566410.567560.566910.006310.003580.002030.001150.00065第15頁(yè),共32頁(yè)，2024年2月25日，星期天所以,取近似根

x10=0.56691滿足精度要求.如果精度要求為=10-5,則由可知,需要迭代20次.如果對(duì)方程xex-1=0，建立等價(jià)形式：x=-lnx,和迭代格式：xk+1=-lnxk，k=0,1,…,此時(shí)迭代函數(shù)

(x)=-lnx，|(x)|=|1/x|>1,x

[0.5,0.6].則此迭代不收斂。第16頁(yè),共32頁(yè)，2024年2月25日，星期天

定義4.4

設(shè)迭代序列

xk

收斂于,如果存在正實(shí)數(shù)p和正常數(shù)C,使得或|xk+1-|C|xk-|p,k>>1則稱序列

xk

是p階收斂的,稱p是收斂階,C是漸近誤差常數(shù).

p=1稱為線性收斂;p>1稱超線性收斂;p=2稱平方收斂.對(duì)簡(jiǎn)單迭代法xk+1=(xk),由于

|xk+1-|=|(xk)-()|=|(k)||xk-|那么,當(dāng)()0時(shí),有

p反映了收斂速度，當(dāng)|xk-|時(shí)，可有|xk+1-|Cp。第17頁(yè),共32頁(yè)，2024年2月25日，星期天于是因此,當(dāng)

(x)滿足條件(4.4)時(shí)，簡(jiǎn)單迭代法是m階收斂的.所以,當(dāng)()0時(shí),簡(jiǎn)單迭代法是線性收斂的.設(shè)

()=()=…=(m-1)()=0,,(m)()0,

m>1(4.4)

|xk+1-|=|(xk)-()|所以下面介紹Aitken加速算法，此方法可對(duì)線性收斂的簡(jiǎn)單迭代法起到加速作用，而且可應(yīng)用于其它數(shù)值方法中。此時(shí)第18頁(yè),共32頁(yè)，2024年2月25日，星期天假設(shè)

(1)(2)，則有由于

xk+1-=(1)(xk-)

xk+2-=(2)(xk+1-)即

(xk+1-)2(xk-)(xk+2-)

xk+12-2xk+1+2xkxk+2-(xk+xk+2)+2

解得第19頁(yè),共32頁(yè)，2024年2月25日，星期天則序列注意,如果第k步發(fā)生zk-2yk+xk=0,就終止計(jì)算,取

xk.如果記要比序列{xk}更快地收斂于

,可構(gòu)造如下的Aitken加速算法:例4分別用簡(jiǎn)單迭代法和Aitken加速算法求方程x=1.6+0.99cosx在x0=/2附近的根.(=1.585471802)第20頁(yè),共32頁(yè)，2024年2月25日，星期天取x0=/2,計(jì)算結(jié)果如下k簡(jiǎn)單迭代法kAitken算法xk|xk-xk-1|xk|xk-xk-1|012341.570801.61.571091.599711.571380.02920.028910.028620.028330121.57079631.585472581.585471800.014676280.00000078第21頁(yè),共32頁(yè)，2024年2月25日，星期天

Newton迭代法是求非線性方程根的最重要方法之一,其最大優(yōu)點(diǎn)是在方程的單根附近具有平方收斂,而且Newton迭代法還可用來(lái)求解方程的重根、復(fù)根及非線性方程組.§3Newton迭代法

§3.1Newton迭代公式設(shè)(x)在有根區(qū)間[a,b]上二階連續(xù)可微,由初始近似x0出發(fā)，假設(shè)第k步迭代值xk已知，如何確定xk+1?,因?yàn)槔?)=0且舍去高階小項(xiàng)(-xk)2，則得到

0(xk)+(xk)(-xk)解得xk-(xk)/(xk)≌xk+1第22頁(yè),共32頁(yè)，2024年2月25日，星期天從而得到迭代公式：迭代格式(4.5)稱為Newton迭代法.一般要求在附近

(x)0。

xyox0y=(x)x1x2例如，由x0出發(fā)，切線方程是：

y-(x0)=(x0)(x-x0)或y=(x0)+(x0)(x-x0)，它與x軸(y=0)的交點(diǎn)是

x1=x0-(x0)/(x0)Newton迭代法的幾何意義是：用曲線上點(diǎn)(xk,(xk))處切線與x軸的交點(diǎn)作為新的迭代值xk+1。第23頁(yè),共32頁(yè)，2024年2月25日，星期天

Newton迭代法xK+1=xk-(xk)/(xk)相當(dāng)于取迭代函數(shù)所以Newton迭代法也叫切線法.

§3.2Newton迭代法的收斂性的簡(jiǎn)單迭代法.因?yàn)槿绻?x)=0的單根,即()=0,但()0,則有()=0,從而可知Newton迭代法是局部收斂的，且至少為二階收斂。下面進(jìn)一步討論Newton迭代法收斂性。因?yàn)樗缘?4頁(yè),共32頁(yè)，2024年2月25日，星期天于是有可見,Newton迭代法當(dāng)

()≠0是平方收斂的.記M2=max|(x)|,m1=min|(x)|.則有

|xk+1-|C|xk-|2因此

C|xk+1-|(C|xk-|)2

(C|xk-1-|)4可見,當(dāng)C|x0-|<1,即|x0-|<2m1/M2時(shí),Newton迭代法是收斂的.第25頁(yè),共32頁(yè)，2024年2月25日，星期天

設(shè)

(x)在單根附近具有二階連續(xù)導(dǎo)數(shù),在鄰域(x)0。則對(duì)充分接近的初值x0,Newton迭代法產(chǎn)生的序列xk

收斂于,并且定理4.6取x0=0.5,計(jì)算結(jié)果如下:

例5

用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求

=10-5.

解

Newton迭代格式為第26頁(yè),共32頁(yè)，2024年2月25日，星期天kxk?(xk)|xk-xk-1|012340.50.571020440.567155570.567143290.56714329-0.175639360.010747510.000033930.00000000030.00000000030.071020440.003864870.000012280.00000000從結(jié)果可見,Newton迭代法迭代3次已獲得精確到小數(shù)點(diǎn)后五位的近似解,迭代4次已獲得精確到小數(shù)點(diǎn)后八位的近似解.與例3比較(20次)可見Newton迭代法收斂的確實(shí)快.§3.3Newton迭代法的變形1.簡(jiǎn)化Newton迭代法第27頁(yè),共32頁(yè)，2024年2月25日，星期天為了簡(jiǎn)化計(jì)算

(xk),采用迭代格式稱為簡(jiǎn)化Newton迭代法.oxyy=(x)

x0x1x2x3在區(qū)間I=[-,+]上,取M與(x)同號(hào),且|M|>1/2max|(x)|時(shí),簡(jiǎn)化Newton迭代法對(duì)x0I收斂.通常取M=(x0).簡(jiǎn)化Newton迭代法一般只具有線性收斂.

2.割線法將近似公式第28頁(yè),共32頁(yè)，2024年2月25日，星期天oxyy=(x)

x0x1x2x3代入Newton迭代法中，得到迭代格式初值x0,x1取定，稱為割線法.若

(x)在根附近二次連續(xù)可微,且()0,可以證明割線法是超線性收斂的,且有割線法收斂的階為

3.計(jì)算重根的Newton迭代法第29頁(yè),共32頁(yè)，2024年2月25日，星期天