Численные методы решения скалярных уравнений: Учебно-методическое пособие

М И Н И СТ Е РСТ В О О БРА ЗО В А Н И Я РО ССИ Й СК О Й Ф Е Д Е РА Ц И И В О РО Н Е Ж СК И Й ГО СУ Д А РСТ В Е Н Н Ы Й У Н И В Е РСИ Т Е Т

ЧИ СЛЕ Н Н Ы Е М Е Т О Д Ы РЕ Ш Е Н И Я СК А ЛЯ РН Ы Х У РА В Н Е Н И Й

У чебн о -мето дическо е по со бие по специальн о сти «математика» (010100)

В О РО Н Е Ж 2003

2

У твер ж ден о н аучн о -мето дическим со в ето м математическо го ф акультета пр о то ко л№ 7 о т12 мая 2003 го да.

Со став итель: Т р о ф имо в В .П .

У чебн о -мето дическо е по со бие по дго то в лен о н а каф едр е математическо го мо делир о в ан ия математическо го ф акультета В о р о н еж ско го го судар ствен н о го ун ив ер ситета. Реко мен дуется для студен то в 4 и 5 кур со в дн ев н о го и в ечер н его о тделен ий математическо го ф акультета, о бучаю щ их ся по специальн о сти «математика» (010100).

3

Н асто ящ ее учебн о -мето дическо е по со бие пр едн аз н ачен о для в ыпо лн ен ия лабо р ато р н о й р або ты «Числен н ые мето ды р еш ен ия скаляр н ых ур ав н ен ий» по кур су «М ето ды в ычислен ий» студен тами IV-V кур со в дн ев н о го и в ечер н его о тделен ий математическо го ф акультета. Раз р або ткамо ж етбытьиспо льз о в ан адля само сто ятельн о й р або ты студен то в и по дго то в ке к экз амен у. П о со бие пр едстав ляетсо бо й сущ ествен н о пер ер або тан н ый и до по лн ен н ый в ар иан тмето дических указ ан ий [5]. Литер атур а 1. Бах в ало в Н .С. Числен н ые мето ды в з адачах и упр аж н ен иях : У чеб. по со бие / Н .С.Бах в ало в , А .В .Лапин , Е .В .Чиж о н ко в ; П о д р ед. В .А .Садо в н ичего . – М .: В ысш ая ш ко ла, 2000. – 190 с. 2. П лис А .И . Лабо р ато р н ый пр актикум по в ысш ей математике: У чеб. по со бие для в туз о в / А .И .П лис, Н .А .Слив ин а. – 2-е из д., пер ер аб. и до п. – М .: В ысш ая ш ко ла, 1994. – 416 с. 3. Загускин В .Л. Спр ав о чн ик по числен н ым мето дам р еш ен ия ур ав н ен ий/ В .Л.Загускин . – М .: Ф из матгиз , 1960. – 216 с. 4. Лю стер н ик Л.А . К р аткий кур с ф ун кцио н альн о го ан ализ а / Л.А .Лю стер н ик, В .И .Со бо лев . – М .: В ысш ая ш ко ла, 1982. – 328 с. 5. М ето дические указ ан ия по мето дам в ычислен ий и в ычислительн о й пр актике. Часть I / Со ст. Г.С.А бр о ськин а, В .П .Т р о ф имо в . - В о р о н еж .: В о р о н еж . го с. ун -т, 1987. – 20 с. О бо з н ачен ия R - мн о ж ество в ещ ествен н ых чисел; N – мн о ж ество н атур альн ых чисел; C ( a ;b ) - бан ах о в о пр о стр ан ство ф ун кций н епр ер ыв н ых н а [a; b] ⊂ R.

C((ak;)b )

- пр о стр ан ство ф ун кций, имею щ их пр о из в о дн ые до по р ядка k в клю чительн о .

на

[a; b]

н епр ер ыв н ые

1. П о ст ан о в казад ач и Рассмо тр им ур ав н ен ие

f ( x) = 0 ,

(1)

f : X → R о пр еделен а и н епр ер ыв н а н а н еко то р о м пр о меж утке X * в ещ ествен н о й пр ямо й R. Число x ∈ X н аз ыв ается р еш ен и ем (ко р н ем ) где

* ур ав н ен и я (1) или н улем ф ун кц и и f если f ( x ) = 0 . Е сли в о кр естн о сти ко р н я

x * ф ун кция f пр едстав имав в иде f ( x) = (x − x* ) ⋅ g ( x) , где k ∈ N и g( x) ≠ 0 , то * число k н аз ыв ается кр ат н о ст ь ю ко р н я. Е сли k = 1 , то ко р ен ь x н аз ыв ается k

пр о ст ым.

4 *

Зам еч ан и е 1. К о р ен ь x гладко й ф ун кции f ( j ) ( x * ) = 0, j = 0,1,Κ , k − 1 и f ( k ) ( x * ) ≠ 0 .

f имеет кр атн о сть k , если n−1

f (x ) яв ляется мн о го член о м: f ( x) = a0 x + a1 x + Κ + an−1 x + an , Е сли ai ∈ R, i = 0,Κ , n, то ур ав н ен ие (1) н аз ыв ается алгебр аи ч ески м . У р ав н ен ия, н е яв ляю щ иеся алгебр аическими, пр ин ято н аз ыв атьт р ан сц ен д ен т н ыми . Специальн ые св о йства мн о го член о в по з в о ляю тпо стр о ить бо льш о е число мето до в р еш ен ия алгебр аических ур ав н ен ий. Н аибо лее часто испо льз ую тмето д в ыделен ия действительн ых мн о ж ителей (мето ды Лин а, Ф р идман а), мето д Ло бачев ско го (см. [3]). Числен н о е р еш ен ие ур ав н ен ия (1) о бычн о со сто итиз дв ух этапо в . Н апер в о м этапе о сущ ествляю то т д елен и е (ло кали зац и ю ) ко р н ей - н ах о дят о тр ез о к [a; b] ⊂ R (в о з мо ж н о мен ьш ей длин ы), н а ко н цах ко то р о го ф ун кция f пр ин имаетз н ачен ия р аз н ых з н ако в : f (a ) ⋅ f (b) < 0 . Н а в то р о м этапе о тыскив аю т n

~ пр и бли жен н о е зн ач ен и е ко р н я x ∈ [a; b] с з адан н о й абсо лю тн о й то чн о стью ε : ~ x − x* < ε .

Е сли f н епр ер ыв н а н а [a; b] и f (a ) ⋅ f (b) < 0 , то по тео р еме Бо льцан о К о ш и н а о тр ез ке [a; b] сущ ествует, по кр айн ей мер е, о дин ко р ен ь ур ав н ен ия (1). (1) Е сли f ∈ C( a;b) и пр о из в о дн ая f ′(x ) со х р ан яетз н ак в н утр и ин тер в ала(a; b) , то

* ур ав н ен ие (1) имеетедин ствен н ый пр о сто й ко р ен ь x ∈ [a; b] . Вн и м ан и е! Н епр ер ыв н ая ф ун кция f мо ж етиметьн ао тр ез ке [a; b] ко р н и и н е удо в летво р ятьусло в ию f (a ) ⋅ f (b) < 0 (см. р ис.1). y

x a

0

b

y = f (x ) Ри с. 1 Д ля о тделен ия ко р н ей испо льз ую т р аз личн ые спо со бы: ан али т и ч ески й (исследо в ан ие по в еден ия ф ун кции f мето дами математическо го ан ализ а),

5

гр аф и ч ески й (по стр о ен ие эскиз а гр аф ика ф ун кции f ), т абли ч н ы й (табулир о в ан ие – по стр о ен ие таблицы з н ачен ий ф ун кции f ). Т абличн ый спо со б со сто ит в о пр еделен ии з н ако в ф ун кции f (x ) в уз лах н еко то р о й сетки {α j = α + jh, h > 0, j = 0,1,Κ N }, в ыбо р пар аметр о в ко то р о й

α , h, N з ав исито то со бен н о стей ф ун кции f (x ) . Е сли в по стр о ен н о й таблице з н ачен ий ф ун кции f (x ) имеем f (α k ) ⋅ f (α k +1 ) < 0 , то н а о тр ез ке [α k ;α k +1 ] н ах о дится х о тя бы о дин ко р ен ь ур ав н ен ия (1). Е сли уз лы α k , α k +1 близ ки, то мо ж н о н адеяться, что ко р ен ьмеж ду н ими о дин . О дн ако в это м н уж н о убедиться с по мо щ ью до по лн ительн о го исследо в ан ия. В ыяв ить по таблице ко р н и четн о й кр атн о сти кр айн е сло ж н о . Зам еч ан и е 2. П р и н аличии до по лн ительн о й ин ф о р мации о св о йствах ф ун кции f : X → R н а пер в о м этапе н ах о дятгр убые гр ан ицы ко р н ей – о тр ез о к [m; M ] ⊂ X , со дер ж ащ ий в се ко р н и ур ав н ен ия (1) (см. р ис. 2). Затем н ах о дят о тр ез ки, каж дый из ко то р ых со дер ж итто лько о дин ко р ен ь. y

x1*

x 2*

0 m

M

y = f (x ) Ри с. 2 * П усть ур ав н ен ие (1) имеет н а о тр ез ке [a; b] един ствен н ый ко р ен ь x и

f ( x) = (x − x* ) ⋅ g ( x) , где ф ун кция g(x) со х р ан яетз н ак н а [a; b] . В это м случае сущ ествует качествен н о е р аз личие в по в еден ии ф ун кции f (x ) в о кр естн о сти ко р н я: пр и н ечетн о м k ф ун кция f (x ) мен яетз н ак н а [a; b] , апр и четн о м k - н ет. Т аким о бр аз о м, то лько по сле то го как из в естн ы о тветы н а в о пр о сы о сущ ество в ан ии, един ствен н о сти и кр атн о сти ко р н я н а о тр ез ке [a; b] , мо ж н о пер ех о дитьк в ыбо р у числен н о го мето дар еш ен ия ур ав н ен ия (1). Раз личаю тпр ям ы е (т о ч н ы е) и и т ер ац и о н н ы е мето ды р еш ен ия ур ав н ен ия (1). П р ямые мето ды по з в о ляю тн айти в се ко р н и ур ав н ен ия з а ко н ечн о е число о пер аций (н апр имер , ф о р мулы в ычислен ия ко р н ей кв адр атн о го тр ех член а). И з в естн ые пр ямые мето ды пр имен имы то лько для уз ко го класса специальн ых k

6

ф ун кций f (x ) . О сн о в н ыми спо со бами р еш ен ия ур ав н ен ия (1) яв ляю тся итер ацио н н ые мето ды. И тер ацио н н ый мето д по з в о ляет н айти такую

{ } (n )

*

по следо в ательн о стьпр иближ ен ий x , ко то р ая сх о дится к ко р н ю x ур ав н ен ия (n) * (n ) (1): lim x = x (в это м случае x н аз ыв ается n -ы м пр и бли жен и ем к ко р н ю n →∞

x * ). Е сли для лю бо го n дв а по следо в ательн ых пр иближ ен ия x (n ) и x ( n+1) * р аспо лагаю тся по р аз н ые сто р о н ы о т ко р н я x , то мето д н аз ыв ается д в уст о р о н н и м , аесли по о дн у сто р о н у – о д н о ст ор он н и м. В аж н ейш ей х ар актер истико й итер ацио н н ых мето до в яв ляется ско р о ст ь p , схо д и м о ст и . И тер ацио н н ый мето д имеет ско р о ст ь схо д и м о ст и (по р яд о к) если p есть н аибо льш ее по ло ж ительн о е число , для ко то р о го сущ ествуеттако е C > 0 , что для лю бо го n ∈ N: p

x ( n +1) − x * ≤ C x ( n ) − x * . (n ) * В еличин у x − x н аз ыв аю тпо гр еш н о ст ь ю n -о го ш ага итер аций. Число C н аз ыв аю т ко н ст ан т о й аси м пт от и ч еско й о ш и бки мето да (о бычн о C мо ж н о о цен ить с по мо щ ью пр о из в о дн ых ф ун кции f ). Е сли p = 1 и 0 < C < 1 , то го в о р ят, что мето д сх о дится со ско р о стью гео метр ическо й пр о гр ессии со з н амен ателем C (имеет лин ейн ую ско р о сть сх о димо сти). Е сли p = 2 ( C > 0 лю бо е), то ско р о стьсх о димо сти н аз ыв ается кв ад р ат и ч н о й.

2. П р акт и ч ески е кр и т ер и и ко н т р о ля т о ч н о ст и в ы ч и слен и я ко р н я О бсудим пр актические пр иемы, о беспечив аю щ ие в ычислен ие ко р н я ур ав н ен ия (1) с з адан н о й то чн о стью . Н ам н уж н о о пр еделитьмо мен тпр екр ащ ен ия в ычислен ий (усло в и е о ст ан о в а) по р еализ уемо му итер ацио н н о му пр о цессу. В качестве усло в ия о ко н чан ия в ычислен ий естествен н о в о з н икаеткр итер ий, x мо ж н о судить со гласн о ко то р о му о то чн о сти пр иближ ен н о в ычислен н о го ко р н я ~ по то му, н аско лько х о р о ш о о н удо в летво р яетз адан н о му ур ав н ен ию (1). П р и это м,

~ x яв ляется х о р о ш им пр иближ ен ием к ко р н ю . каз ало сь бы, если f ( x ) мало , то ~

~ О дн ако это н е в сегда так. Д аж е если f ( x ) в елико , это н е о бяз ательн о о з н ачает, x яв ляется гр убым пр иближ ен ием к ко р н ю . Д ействительн о , если умн о ж ить что ~ ур ав н ен ие (1) н а пр о из в о льн о е число r ≠ 0 , то по лучается экв ив ален тн о е ур ав н ен ие rf ( x ) = 0 , пр ичем число rf ( x ) мо ж н о сделатьско ль уго дн о бо льш им или ско ль уго дн о малым з а счетв ыбо р а мн о ж ителя r . К р о ме то го , имеетместо ещ е о дн о з аблуж ден ие: если пр и р еализ ации итер ацио н н о го мето да в ыпо лн ен о

~

( n +1) − x ( n ) < ε , то такж е спр ав едлив о и н ер ав ен ство усло в ие x О дн ако в о бщ ем случае это утвер ж ден ие яв ляется о ш ибо чн ым.

x (n) − x* < ε .

ε >0

П усть ко р ен ь

7

абсо лю т н ая т о ч н о ст ь , с ко то р о й тр ебуется н айти

x * ур ав н ен ия (1):

x ( n ) − x * < ε . Т о гда усло в ием о стан о в а д ля ( n +1)

− x < ε (пр и д в уст о р о н н его м ет о д а яв ляется в ыпо лн ен ие усло в ия x р еализ ации алго р итма дв усто р о н н его мето да стр о ится по следо в ательн о сть в ло ж ен н ых о тр ез ко в , со дер ж ащ их иско мый ко р ен ьур ав н ен ия (1)). Д ля о д н о ст о р о н н и х м ет о д о в мы н е мо ж ем испо льз о в ать тако й ко н тр о ль в ычислен ий. В это м случае н ео бх о димо в в ести н еко то р ую о тн о сительн ую х ар актер истику то чн о сти в ычислен ий. Будем го в о р ить, что ко р ен ь ур ав н ен ия (1) (n ) н айден с о т н о си т ель н о й т о ч н о ст ь ю ε > 0 , если в ычислен о пр иближ ен ие x (n)

тако е, что x − x < ε ⋅ x − x . Э то о з н ачает, что в ычислен ия пр о до лж аю тся до тех по р , по кар ассто ян ие о тн улев о го пр иближ ен ия до иско мо го ко р н я н е будет (n)

*

( 0)

*

1 р аз . Д ля о дн о сто р о н н его мето да часто в качестве усло в ия ε (n +1) )<ε и о стан о в апр ин имаю то дн о в р емен н о е в ыпо лн ен ие дв ух н ер ав ен ств f (x умен ьш ен о в

x ( n +1) − x ( n ) < ε . К

кр итер иям о ко н чан ия счета мо ж н о до бав ить усло в ие

x ( n +1) − x ( n )

(н апр имер ,

x ( n ) − x ( n −1) > 1 ), по з в о ляю щ ее в ыяв лять р асх о димо сть мето да н а

р ан н их этапах итер ацио н н о го пр о цесса. О дн ако пр имен ен ие тако го р о да кр итер иев мо ж ет пр ив ести к пр еж дев р емен н о му о ко н чан ию в ычислен ий, по ско льку пр иближ ен ия, пр еж де чем н ачать сх о диться к ко р н ю ур ав н ен ия (1), мо гутв н ачале пр о цессар асх о диться. Рассмо тр им к о м бин ир о ван н ы й кр итер ий ко н тр о ля то чн о сти для ε абс и дв усто р о н н их мето до в , о бъ един яю щ ий ко н тр о ль по абсо лю тн о й о тн о сительн о й по гр еш н о стям ε о т н :

x ( n +1) − x ( n ) ≤ ε абс + ε о т н ⋅ x ( n ) .

( 2)

И спо льз о в ан ие кр итер ия (2) о сн о в ан о н аследую щ их со о бр аж ен иях . Е сли з адан ато лько до пустимая абсо лю тн ая по гр еш н о сть ε абс ( ε о т н = 0 ), то тем самым з аф иксир о в ан р аз р яд пр иближ ен н о го з н ачен ия ко р н я, со о тветствую щ ий тр ебуемо й само й младш ей в ер н о й циф р е это го з н ачен ия. О дн ако если з адав ать абсо лю тн ую по гр еш н о сть без учета в еличин ы по р ядка иско мо го ко р н я и р аз р ядн о й сетки Э В М , то ко н тр о ль в ычислен ий по абсо лю тн о й по гр еш н о сти мо ж ето каз аться н ев о з мо ж н ым. Е сли з адан а то лько о тн о сительн ая по гр еш н о сть ε о т н ( ε абс = 0 ), то тем самым ф иксир уется о бщ ее тр ебуемо е ко личество в ер н ых циф р пр иближ ен н о го

8 (n )

з н ачен ия ко р н я. О дн ако если иско мый ко р ен ь мал и з н ачен ие x стало слиш ко м близ ким к н улю , то н ер ав ен ство (2) мо ж етн ико гда н е до стигаться или мо ж етпо лучиться маш ин н ый н уль. пр и в ычислен ии ε о т н ⋅ x Зам еч ан и е 3. Д ля систем пр едстав лен ия чиселс плав аю щ ей з апято й в Э В М имеетместо следую щ ее ф ун дамен тальн о е св о йство : р ассто ян ие меж ду число м r и ближ айш им к н ему число м н е мен ьш е masheps ⋅ r p и н е бо льш е macheps ⋅ r , если то лько само число или со седн ее число н е р ав н о н улю . Здесь p - о сн о в ан ие системы счислен ия Э В М , macheps - маш ин н о -з ав исимый пар аметр , х ар актер из ую щ ий о тн о сительн ую то чн о сть маш ин н о й ар иф метики с плав аю щ ей з апято й, macheps яв ляется н аимен ьш им число м с плав аю щ ей з апято й, для ко то р о го в ыпо лн ен о н ер ав ен ство : 1.0 + macheps > 1.0 . Зн ачен ие macheps p р ав н о р ассто ян ию о т1.0 до лев о го со седн его числа и само з н ачен ие macheps = p 1−t ( t ко личество р аз р ядо в ман тиссы) пр едстав ляетсо бо й р ассто ян ие о т1.0 до пр ав о го со седн его числа. (n )

( n) p , то пр и ε абс = 0 П о это му если ε о т н ⋅ x о каж ется мен ьш е macheps ⋅ x н ер ав ен ство (2) н ико гда н е будетв ыпо лн яться и, следо в ательн о , итер ацио н н ый пр о цесс мо ж ет н е з ав ер ш иться. О тсю да по лучаем кр итер ий то чн о сти, о беспечив аю щ ий максимальн ую близ о сть дв ух со седн их итер аций (со седн их чисел):

(n )

(

)

x ( n +1) − x ( n ) < macheps ⋅ max x ( n +1) , x ( n ) . О чев идн о , что по лучен н ый кр итер ий н епр имен им для н ебо льш о й о кр естн о сти н уля, в ко то р о й пр о исх о дит о бр аз о в ан ие маш ин н о го н уля пр и в ычислен ии пр ав о й части. О тметим, что р ассто ян ие о тн уля до пр ав о го (лев о го ) со седн его числа пр едстав ляетсамо сто ятельн ый маш ин н о -з ав исимый пар аметр и н е св яз ан о с пар аметр о м macheps . Т аким о бр аз о м, пр имен ен ие н ер ав ен ства (2) по з в о ляетиз беж ать тупико в ых ситуаций, ко то р ые мо гутв о з н икн уть, если з адав ать ко личество в ер н ых з н ако в в пр иближ ен н о м р еш ен ии без учетаего по р ядка. К ак уж е о тмечало сьв ыш е, пр имен ен ие кр итер ия

f (x ( n ) ) ≤ ε зн

(3) (n )

н е мо ж ет гар ан тир о в ать в ычислен ия пр иближ ен н о го з н ачен ия ко р н я x с з адан н о й то чн о стью ; то ж е само е мо ж н о сказ ать и о кр итер ии (2) для о дн о сто р о н н их мето до в . О дн ако н а пр актике для о дн о сто р о н н их мето до в о дн о в р емен н о е пр имен ен ие кр итер иев (2) и (3) (еслиε абс , ε о т н , ε зн до стато чн о малы) даетв по лн е удо в летво р ительн ые р ез ультаты.

9

Вн и м ан и е! В случае, ко гда пр о из в о дн ая ф ун кции f (x ) в близ и ко р н я x * мала по абсо лю тн о й в еличин е, то есть гр аф ик ф ун кции по чти f (x ) го р из о н тален в о кр естн о сти ко р н я, лю бо е н ебо льш о е в о з мущ ен ие (н апр имер , f (x ) + δ , δ > 0 ) пр ив о дит к з аметн о му из мен ен ию ко р н я x * . П о до бн ая н еусто йчив о cтьх ар актер н адля мн о го член о в в ысо ких степен ей. 3. М ет о д д елен и я по по лам Э то т мето д н аз ыв аю т ещ е мето до м по ло в ин н о го делен ия, дих о то мией, мето до м бисекций или мето до м в илки. М ето д делен ия по по лам - итер ацио н н ый мето д, алго р итм ко то р о го имеетв ид:

    (n) ( n+1) (n) ( n +1) a ;x , ес ли f (a ) ⋅ f (x ) < 0,    a ( n+1) ; b( n+1) =    x ( n+1) ; b( n ) , ес ли f (x ( n+1) ) ⋅ f (b( n ) ) < 0,     ( 0) ( 0)  n = 0,1,2,Λ , a = a, b = b.   1 x ( n+1) = a ( n ) + (b( n ) − a ( n ) ), 2

[

]

[

]

[

]

(4)

(n) Е сли f (x ) = 0 для н еко то р о го n , то пр о цесс в ычислен ий пр екр ащ аю ти * (n) по лагаю т x ≅ x . М ето д делен ия по по лам яв ляется дв усто р о н н им. У сло в ием о стан о в а

( n +1) − x ( n ) < ε , где ε > 0 алго р итма (4) яв ляется в ыпо лн ен ие н ер ав ен ства x з адан н ая то чн о стьв ычислен ий (см. р ис. 3).

y

y = f (x )

x* a ( 0)

x (2) b(0)

x

(1)

= (a

( 0)

+ b )/2 ( 0)

Ри с. 3

x

10

фун к ция f ∈ C( a ;b )

Тео р ем а 1. П ус т ь

[a; b] пр ин им ает

зн ачен ия

р азн ы х

зн ак о в:

и

на

к о н цах

f ( a ) ⋅ f ( b) < 0 .

о т р езк а То гда

* по с ледо ват ель н о с т ь (4) с хо дит с я пр и n → ∞ к р ешен ию x ∈ [a; b] ур авн ен ия (1) ис пр аведлива о цен к а по гр ешн о с т и

x (n) − x* ≤

b−a . 2n

(5)

Зам еч ан и е 4. Е сли н а о тр ез ке [a; b] имеется н еско лько ко р н ей ур ав н ен ия (1), то мето д делен ия по по лам сх о дится к о дн о му из н их . Т ео р етически алго р итм (4) по з в о ляетн айти ко р ен ь ур ав н ен ия (1) с лю бо й абсо лю тн о й то чн о стью ε . О цен им число итер аций n(ε ) , н ео бх о димо е для в ычислен ия ко р н я ур ав н ен ия (1) с з адан н о й абсо лю тн о й то чн о стью ε . И з (3) b−a b−a (n ) * имеем x − x ≤ n < ε . О тсю да n > log2 и, следо в ательн о , 2 ε

n(ε ) ≥ log2

b−a . ε

Э то о з н ачает, что для по лучен ия каж дых тр ех в ер н ых з н ако в н ео бх о димо о ко ло 10 итер аций. Зам еч ан и е 5. П р и числен н о й р еализ ации мето да делен ия по по лам в сегда будетпр исутство в ать о ш ибка о кр углен ия, з ав исящ ая о то со бен н о стей маш ин н о й ар иф метики (ф о р мы пр едстав лен ия чисели р еализ ации о пер аций о кр углен ия в Э В М ). О ш ибки о кр углен ия, ко то р ые сами по себе каж утся н ез н ачительн ыми, мо гуто каз ать сущ ествен н о е в лиян ие н а ко н ечн ый р ез ультатпр и бо льш о м числе ар иф метических о пер аций. П о это му следуетмин имиз ир о в ать о ш ибки в каж до й о пер ации или по следо в ательн о сти о пер аций. Рассмо тр им, как это мо ж н о сделать пр и в ычислен ии ср едн его a+b ар иф метическо го дв ух чисел a и b (о чер едн о го пр иближ ен ия мето да 2 a +b и делен ия по по лам). В о з мо ж н ы дв аспо со бав ыпо лн ен ия это й о пер ации: c = 2 b−a c=a+ . П ер в ая ф о р мула тр ебуетн а о дн у о пер ации сло ж ен ия мен ьш е, чем 2 в то р ая, н о с то чки з р ен ия то чн о сти н е в сегда даетлучш ий р ез ультат. Н етр удн о устан о в ить н аилучш ую ф о р мулу для в ычислен ия ср едн его ар иф метическо го дв ух чиселa и b : a +b b−a если ( sign(a ) ≠ sign(b) ), то c = ин аче c = a + . 2 2 Д ля мето да делен ия по по лам пр имен ен ие в то р о й ф о р мулы (n ) (n ) пр едпо чтительн ее, по ско льку пр и ув еличен ии числа итер аций з н аки a иb

11

стан о в ятся о дин ако в ыми до о ко н чан ия итер ацио н н о го пр о цесса (исклю чен ием яв ляется случай, ко гдаиско мый ко р ен ьр ав ен н улю ). Зам еч ан и е 6. О бычн ый спо со б пр о в ер ки из мен ен ия з н акаф ун кции f (x ) н а о тр ез ке [a; b] со сто итв пр о в ер ке усло в ия f (a ) f (b) < 0 . О дн ако если з н ачен ия f (a ) и f (b) близ ки к н улю , то пр о из в еден ие f (a ) f (b) мо ж етстать маш ин н ым н улем, и это тспо со б о каж ется н епр иемлемым. П о это му пр о в ер ку из мен ен ия з н ака ф ун кции лучш е в ыпо лн ятьследую щ им о бр аз о м: f (b ) f (a ) ⋅ < 0. abs( f (b) ) 4. М ет о д пр о ст ы хи т ер ац и й (по след о в ат ель н ы хпр и бли жен и й) Замен им ур ав н ен ие ему (1) экв ив ален тн ым ур ав н ен ием

x = ϕ (x).

(6)

Зам еч ан и е 7. У р ав н ен ия (1) и (6) н аз ыв аю тся экв и в ален т н ы м и , если ко р н и ур ав н ен ия (1) яв ляю тся ко р н ями ур ав н ен ия (6) и н ао бо р о т. П ер ех о д о тур ав н ен ия (1) к (6) мо ж н о о сущ ествитьпо ло ж ив , н апр имер ,

ϕ ( x) = x + λ ( x ) f ( x ) , где λ (x ) - н еко то р ая з н ако по сто ян н ая ф ун кция. П о стр о им по н ачальн о му пр иближ ен ию пр иближ ен ий – алго р итм мето дапр о сто й итер ации:

x ( n+1) = ϕ (x ( n ) ),

n = 0,1,2Λ

x (0)

по следо в ательн о сть

(7)

П о следо в ательн о сть (7) будетсх о диться пр и n → ∞ к то чн о му р еш ен ию x ур ав н ен ия (6) (ур ав н ен ия (1)), если о то бр аж ен ие ϕ яв ляется сж имаю щ им. (1) Тео р ем а 2. П ус т ь фун к ция ϕ ∈ C( a;b) . Е с ли с ущ ес т вует т ак о е чис ло q : *

0 < q < 1 , чт о ϕ ′( x ) ≤ q для вс ех x ∈ [a; b] , т о алго р ит м (7) с хо дит с я пр и n → ∞

* к един с т вен н о м у н а [a; b] р ешен ию x ур авн ен ия (6) (ур авн ен ия (1)) пр и лю бо м вы бо р е н ачаль н о го пр иближен ия x ( 0) ∈ [a; b] . П р иэт о м

x

(n)

q n (1) −x ≤ x − x ( 0) . 1− q *

(8)

О чев идн о , что чем мен ьш е ϕ ′(x ) , тем быстр ее по следо в ательн о сть (7) сх о дится к то чн о му р еш ен ию . И з (8) следует, что мето д пр о сто й итер ации сх о дится со ско р о стью гео метр ическо й пр о гр ессии со з н амен ателем q . Зам еч ан и е 8. Е сли 0 < ϕ ′( x ) < 1 для в сех x ∈ [a; b] , то сх о димо сть к ко р н ю мо н о то н н ая и о дн о сто р о н н яя. П р и это м

12

x(n) − x* ≤

q x ( n ) − x ( n −1) . 1− q

(9)

Е сли − 1 < ϕ ′( x ) < 0 для в сех x ∈ [a; b] , то сх о димо стьдв усто р о н н яя и

x ( n ) − x * ≤ x ( n ) − x ( n −1) .

(10)

Зам еч ан и е 9. Т ео р ема 2 яв ляется пр о стым следствием пр ин ципа сж имаю щ их о то бр аж ен ий (см. [4], стр . 42). Д ействительн о , пр ео бр аз о в ан ие ϕ : [a; b] → R, удо в летво р яю щ ее усло в иям тео р емы 2, о то бр аж аето тр ез о к [a; b] в себя и яв ляется сж имаю щ им:

ϕ (u ) − ϕ (v ) ≤ max ϕ ′(ς ) ⋅ u − v ≤ q u − v a ≤ς ≤b

для лю бых u, v ∈ [a; b] . П р ив едем гео метр ическую ин тер пр етацию мето дапр о сто й итер ации. y y=x y = ϕ(x)

x

x

0

*

x

(2)

x

(1)

x

( 0)

Ри с. 3. y

y=x

y = ϕ(x)

x 0

x

( 0)

x

(2)

x

*

x

Ри с. 4.

(1)

13

Н а р ис. 3 из о бр аж ен случай, ко гда 0 < ϕ ′( x ) < 1 , сх о димо сть мето да мо н о то н н ая и о дн о сто р о н н яя. Е сли ж е − 1 < ϕ ′( x ) < 0 , то сх о димо сть к ко р н ю ( n +1)

яв ляется дв усто р о н н ей x ≤ x ≤ x (см. р ис. 4). Е сли q из в естн о , то пр имер н о е число итер аций n(ε ) , н ео бх о димо е для в ычислен ия ко р н я ур ав н ен ия (6) (ур ав н ен ия (1)) с з адан н о й о тн о сительн о й то чн о стью ε , о цен ив ается н ер ав ен ство м: (n)

*

n(ε ) ≥ ln

1 1 ln . ε q

(1) П усть ур ав н ен ие (1) имеет ко р ен ь н а о тр ез ке [a; b] , f ∈ C( a;b) и f ′(x ) со х р ан яетз н ак н а это м о тр ез ке. У каж ем пр ием пр ив еден ия ур ав н ен ия (1) к в иду (6), о беспечив аю щ ий в ыпо лн ен ие усло в ия сх о димо сти мето дапр о сто й итер ации. Д ля о пр еделен н о сти будем считать, что f ′( x ) > 0 н а [a; b] (если f ′( x ) < 0 , то мо ж н о р ассмо тр еть ур ав н ен ие − f ( x ) = 0 ). П усть 0 < m1 ≤ f ′( x ) ≤ M 1 для в сех x ∈ [a; b] . Замен им ур ав н ен ие (1) экв ив ален тн ым

x = ϕ ( x) ≡ x − λf ( x), λ > 0.

В ыбер ем пар аметр λ так, что бы н а [a; b] в ыпо лн яло сьн ер ав ен ство :

0 ≤ ϕ ′( x) = 1 − λf ′( x) ≤ q < 1.

Э то н ер ав ен ство будетз ав едо мо в ыпо лн ен о , если λ будетудо в летво р ятьусло в ию

0 ≤ 1 − λM1 ≤ ϕ ′( x) ≤ 1 − λm1 < 1.

m1 1 < 1 . Следо в ательн о , пр и тако м в ыбо р е λ мы по лучаем q = 1 − M1 M1 усло в ие сх о димо сти мето дапр о сто й итер ации в ыпо лн ен о . О цен им степен ьв лиян ия о ш ибки о кр углен ия н ав ычислительн ый пр о цесс. x ( n ) р еальн о в ычислен н о е з н ачен ие n -о го пр иближ ен ия, О бо з н ачим чер ез ~ а чер ез δ (n ) - по гр еш н о сть о кр углен ия н а n -о м ш аге. В место ф о р мулы (7) по лучим: При λ=

~ x ( n+1) = ϕ (~ x ( n ) ) + δ ( n+1) , n = 0,1,2,Κ .

x ( n+1) − x ( n+1) н а (n + 1) -о м ш аге имеетв ид: Суммар н ая о ш ибка ε ( n+1) = ~

ε ( n+1) = ϕ (~ x ( n ) ) − ϕ (x ( n ) ) + δ ( n+1) = ϕ ′(ξ ( n ) ) ⋅ (~ x ( n ) − x ( n ) ) = ϕ ′(ξ ( n ) ) ⋅ ε ( n ) + δ ( n+1) , x ( n ) ≤ ξ ( n ) ≤ x ( n ) , n = 0,1,2,Κ . где ~ В усло в иях тео р емы 2 имеем:

14

ε ( n+1) ≤ q ε ( n ) + δ ( n+1) , 0 < q < 1, n = 0,1,2,Κ . И з по лучен н о го н ер ав ен ства следует, что с р о сто м n суммар н ая о ш ибка δ ( j ) , то есть т ε (n ) в едетсебя как в еличин а по р ядка δ = max о ч н о ст ь р езуль т ат а 0≤ j ≤ n со о т в ет ст в уетт о ч н о ст и в ы по лн ен и я ар и ф м ет и ч ески х о пер ац и й. Э то о бщ ее св о йство итер ацио н н ых мето до в яв ляется их в аж н ейш им пр еимущ ество м пер ед др угими числен н ыми мето дами. 5. М ет од Ньют он а Замен им ур ав н ен ие (1) экв ив ален тн ым ур ав н ен ием (пр и усло в ии f ′( x ) ≠ 0 )

x = ϕ ( x) ≡ x −

f ( x) f ′( x)

и по стр о им по н ачальн о му пр иближ ен ию x (0) , по следо в ательн о стьпр иближ ен ий

x

( n +1)

=x

(n)

f (x ( n ) ) − , n = 0,1,2 Κ f ′(x ( n ) )

(11)

А лго р итм (11) н аз ыв ается м ет од ом Ньют о н а (Н ь ю т о н а-Раф со н а). y = f (x ) н а Гео метр ически мето д Н ью то н а со сто ит в з амен е дуги кр ив о й касательн ую к н ей в каж до й итер ации (11). Д ействительн о , из ур ав н ен ия (n) (n) касательн о й к кр ив о й y = f (x) в то чке (x ; f (x ))

y − f (x ( n ) ) = f ′(x ( n ) ) ⋅ (x − x ( n ) ) ( n+1) по лучается р асчетн ая ф о р мула(11), если по ло ж ить y = 0 и x = x .

( 2) Тео р ем а3. П ус т ь f ∈C( a;b) , f (a ) ⋅ f (b) < 0 идля вс ех x ∈ [a; b] пр о изво дн ы е

f ′(x) и f ′′(x) с о хр ан яю т зн ак . То гда, ес лин ачаль н о е пр иближен ие x ( 0) ∈ [a; b] удо влет во р яет

ус ло вию :

f (x ( 0) )⋅ f ′′(x ( 0) ) > 0 ,

то

по с ледо ват ель н о с т ь

* с хо дит с я пр и n → ∞ к един с т вен н о м у н а [a; b] р ешен ию x ур авн ен ия (1). П р иэт о м

x (n) − x* ≤

2 M 2 (n ) x − x ( n −1) , 2m1

где

M 2 = max f ′′( x) и m1 = min f ′( x) . a ≤ x ≤b a≤ x≤b

(12)

(11)

15

Гео метр ическая ин тер пр етация мето даН ью то н адля р аз личн ых случаев по в еден ия ф ун кции f (x) пр ив еден ан ар ис. 5. y = f (x) f ′( x) > 0 f ′′( x) > 0 y

x

x

0 y

*

x

(2)

x

(1)

x

( 0)

f ′( x) < 0

y = f (x)

f ′′( x) > 0

x* x

x

0

( 0)

x

(1)

x

(2)

y

y = f (x)

f ′( x) > 0

f ′′( x) < 0

f ′( x) < 0

f ′′( x) < 0

x ( 0 ) x (1) x ( 2 )

0

x*

y

x

y = f (x)

x ( 2 ) x (1) x*

0

Ри с. 5

x ( 0) x

16

И з (12) следует, что мето д Н ью то н а имееткв адр атичн ую ско р о сть сх о димо сти. В мето де Н ью то н асх о димо стьмо н о то н н ая и о дн о сто р о н н яя. П р имер н о е число итер аций n(ε ) , н ео бх о димо е для в ычислен ия ко р н я ур ав н ен ия (1) с з адан н о й о тн о сительн о й то чн о стью ε , о пр еделяется н ер ав ен ство м

n(ε ) ≥ log2 log2

1 . ε

Вн и м ан и е! Бо лее по др о бн о е из ло ж ен ие р ассмо тр ен н ых и др угих мето до в р еш ен ия н елин ейн ых ур ав н ен ий пр ив еден ы на сайте: http://www.srcc.msu.su/num_anal (см. р аз дел«У чебн о -мето дические матер иалы»). Зад ан и е. Н айдите н аимен ьш ий по ло ж ительн ый ко р ен ьур ав н ен ия f ( x) = 0 с −5 то чн о стью ε = 10 мето дами делен ия по по лам, пр о стых итер аций и Н ью то н а. Вар и ан т ы зад ан и й № в ар иан та 1

f (x)

x 2 + ln x

№ в ар иан та 19

f (x)

α

β

2,01

1,1

2

x 2 − lg( x + 2)

20

2,05

1,2

3

x 2 + ln x − 4 ( x − 1) 2 − 0,5 exp( x ) ( x − 1) 2 − exp( − x )

21

2,02

1,3

22

2,15

1,4

23

2,09

1,5

3,08

1,6

25

3,02

1,7

26

3,03

1,8

27 28

3,01 3,12

1,8 2,0

29

3,11

2,1

30

1,1

2

31

1,2

3

1,3

4

1,4

5

34

1,5

6

35

1,6

2

36

1,7

3

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

x 3 − sin x 4 x − cos x x 2 − sin x x − cos x x 2 − cos πx 2 x − cos(πx 2 )

x − 2 cos(πx 2 )

x 2 − ctg (πx 3)

x 2 − cos 2 πx x 2 − sin πx 0,4 x + ln x 0,5 exp( −0,667 x ) − x ln( 0,6098 x ) − 0,6872 x − 1,5

24

32 33

sin αx − βx

tgαx − βx

17 № в ар иан та 37 38 39 40 41 42 43

f (x)

tgαx − βx

ctgαx − βx

1,8 1,9 2,0 2,1 1,1 1,2 1,3

4 5 6 4 2 3 4

№ в ар иан та 44 45 46 47 48 49 50

f (x)

α

β

ctgαx − βx

1,4 1,5 1,6 1,7 1,8 1,9 2,0

5 2 3 4 5 6 7

П р и ло жен и е. Д ля в ыпо лн ен ия з адан ия мо ж н о испо льз о в ать следую щ ие пр о цедур ы (н аяз ыке П аскаль): 1) П р о цедур а delp, р еализ ую щ ая алго р итм мето да делен ия по по лам р еш ен ия ур ав н ен ия f ( x) = 0 : Procedure delp(var a,b:real; var k:integer; var x,e:real); {В х одн ы е па р а м е тр ы : a, b – кон цы отр е зка , н а котор ом ф ун кция f м е н я е т зн а к

( f (a) f (b) < 0) ;

e – ус ловие ос та н ова :

b (n) − a (n) < e .

В ы х одн ы е па р а м е тр ы : k – чис ло ите р а ций; x – пр иближе н н ое зн а че н ие кор н я . Зде с ь f – им я пр оце дур ы -ф ун кции, вы чис ля ю ще йзн а че н ия ф ун кции f ( x ) , sgn – им я пр оце дур ы -ф ун кции, вы чис ля ю ще йзн а че н ия ф ун кции sgn( x ) .} var i:integer; r:real; begin k:=0; i:=sgn(f(a)); while b-a>=e do begin k:=k+1; x:=(a+b)*0.5; r:=f(x); if f(x)=0 then exit; f sgn(r)*i<>1 then b:=x else a:=x; end end; function sgn(x:real):integer; begin sgn:=0; if x<0 then sgn:=-1; if x>0 then sgn:=1; end;

2) П р о цедур а iter, р еализ ую щ ая алго р итм мето да пр о сто й итер ации р еш ен ия ур ав н ен ия x = ϕ (x) : Procedure iter(var x,e:real; var k:integer);

18 {В х одн ы е па р а м е тр ы : x – н а ча льн ое

x

( n +1)

−x

(n)

пр иближе н ие ; е – ус ловие ос та н ова :

< e.

В ы х одн ы е па р а м е тр ы : k – чис ло ите р а ций; x – пр иближе н н ое зн а че н ие кор н я . Зде с ь f1 – им я пр оце дур ы -ф ун кции, вы чис ля ю ще йзн а че н ия ф ун кции ϕ ( x ) .} var x1,y:real; begin k:=0; x1:=x; y:=f1(x1); while abs(x1-y)>=e do begin k:=k+1; if f(x1)=0 then exit; x1:=y; y:=f1(x1); x:=y; end end;

3) П р о цедур а newt, р еализ ую щ ая алго р итм мето да Н ью то н а р еш ен ия ур ав н ен ия f ( x) = 0 : Procedure newt(var x,e:real; var k:integer); {В х одн ы е па р а м е тр ы : x – н а ча льн ое пр иближе н ие ; е – ус ловие ос та н ова :

x ( n +1) − x ( n ) < e .

В ы х одн ы е па р а м е тр ы : k – чис ло ите р а ций; x – пр иближе н н ое зн а че н ие кор н я . Зде с ь f – им я пр оце дур ы -ф ун кции, вы чис ля ю ще йзн а че н ия ф ун кции пр оце дур ы -ф ун кции, вы чис ля ю ще й зн а че н ия ф ун кции f ′(x ) .} var xp,y:real; begin k:=0; repeat xp:=x; y:=f(xp); k:=k+1; if f(xp)=0 then exit; if df(xp)=0 then exit; x:=xp-y/df(xp) until abs(x-xp)<e end;

f ( x ) , df – им я

19

Со став итель: Т р о ф имо в В алер ий П ав ло в ич Редакто р Т их о мир о в аО .А .