Ньютонның модификацияланған әдісі

Лекция № 1-3 Бір белгісізді теңдеулерді шешу.

Жанамалар әдісі

Біріккен әдіс

Итерациялық әдіс.

3.1 Ньютон әдісі (жанамалар әдісі)

теңдеудің аралықта ажыратылған түбірі болсын. Біз түбірдің -ші жуықтауында түбірді таптық делік. Онда -ші жуықтау -ді төмендегіше бағалаймыз.

. (3.15)

деп аламыз.

- ты нүктеде қатарға жіктеп аламыз:

Бұл жерден

. (3.16)

(3.16)-ны (3.15) формулаға қойып аламыз:

(3.17)

Сурет 1.

Ньютон әдісінің геометриялық мағынасы:

қисықтың доғасы, сол қисықтың әйтеуір бір нүктесіне жүргізілген жанамаға эквивалент. (Сурет 1-ді қараңыз.)

нүктеде болады. Бұл жерде .

нүктеге жанама жүргіземіз, жанаманың осімен қиылысуындағы нүкте . Одан әрі нүктеге жанама жүргізіп нүктені аламыз. т.с.с.

Егер десек, онда нүктеде болады. Онда нүктедегі жанама осін кесіндінің сыртында жатқан кесіп өтеді де алғашқы нүктені бұлай таңдауда Ньютон әдісі жинақталмайды. Ньютон әдісінің жинақты болуының жеткілікті шарты төмендегі теорема арқылы анықталады.

Теорема 5. Егер , болып, және нольден өзгеше және да белгілі бір таңбаны сақтаса, онда

(3.18)

шартты қанағаттандырған бастапқы жуықтаудан бастап, (3.17) Ньютон әдісімен теңдеуінің бір ғана түбірін кез келген дәлдік дәрежесінде есептеп таба аламыз.

Дәлелдеуі:

болсын. (3.18) теңсіздікке байланысты жатқан аралық ретінде, болатын кесіндіні аламыз, қазіргі жағдайда b нүктесі.

Демек, . Енді барлық жуықтаулар , сонымен қатар барлық екендігін дәлелдейік. болсын.

деп алайық.

Тейлор формуласын қолдансақ:

бұл жерде

. , болғандықтан

және, осылайша

дәлелдеу керегі сол. (3.19)

(3.19)-дан және -дің таңбаларын ескеріп аламыз, яғни шекараланған монотон кемімелі тізбек аламыз

Демек, бар..

(3.17)-де шекке өтіп, аламыз, яғни , демек бұл жерден, - түбір д.к.с.

Ньютон әдісінің жинақталу жылдамдығын бағалайық. (3.17)-ден

. (3.20)

-ді төмендегіше жазайық.

бұл жерден

. 3.21)

(3.21)-ді (3.20)-ға қойып табамыз,

Бұл жерден

(3.22)

Бұл жерде ,

Сонымен Ньютон әдісінің жинақталу жылдамдығы квадратты.

Сурет 2.

Итерациялық процестің аяқталу критерийі төмендегіше:

Ескерту. Жалпы жағдайда және екі тізбектің дәлдікте жинақталуы және -дің сәйкес келуіне (сурет 2) кепілдік бермейді. Сондықтан да айырымнан басқа f (x_n): функция мәндерін де тексеруге болады.

Ньютонның модификацияланған әдісі

Ньютон әдісін модификациялау үшін туындыны

формуладағы нүктеде нүктедегі туындымен алмастырамыз, яғни деп аламыз. Нәтижеде

().(3.23)

Бұл тәсілдің геометриялық мағынасы: нүктедегі жанамаларды қисығына нүктеде жүргізілген жанамаларға параллель түзулермен алмастырамыз. (сурет 3).

Сурет.3. Модификацияланған Ньютон әдісі.

Бұл жерде қайта-қайта туындыны есептей берудің қажеті жоқ. (3.23) процесінің жинақталуын төмендегі теорема қамтамасыз етеді.

Теорема 6. -да екі рет дифференциялданушы функция берілсін, сонымен қатар төмендегі шарттар орындалсын.

а)

б) және және -да таңбаларын сақтасын.

Онда

шартты қанағаттандырушы алғашқы жуықтаудан Ньютонның модификацияланған әдісімен кез келген дәлдіктегі бір ғана түбірді есептеп таба аламыз.

Дәлелдеуі. (сурет.3) болсын. Онда болғандықтан ретінде нүктені аламыз. (3.23)-тен екендігі келіп шығады, яғни тізбек кемімелі болады.

. (3.24)

Енді осы тізбектің шегі екендігін көрсетеміз. болсын. екендігін дәлелдейміз. Ол үшін Ньютон формуласында алынған -ші жуықтауды(формула (3.17) жазамыз және Ньютонның модификацияланған әдісі (3.23) бойынша

және айырымды табамыз.

. (3.25)

Дөңес функциялар теориясынан, егер және -да таңбасын сақтаса, онда дөңес болады. Дөңес функциялар үшін туындылар кемімелі емес, яғни . Сондықтан

. (3.26)

(3.26)-ны ескере отырып (11)-ден .

5-теоремадан Ньютон әдісінің жинақтылығын алдық, сондықтан . Бұл жерден

. (3.27)

Сонымен, (3.24) және (3.27)-ден кемімелі тізбекке ие боламыз.

Сонымен кез келген кішкентай оң үшін, . Болатын -ді көрсетуге болады. Теорема дәлелденді.

Біріккен тәсіл

болсын, ал және -да таңбаларын сақтасын. Хордалар және Ньютон әдістерін біріктіріп, түбірді іздеуді және итерациялық процестің жинақталуын тездетуге болады. Нәтижеде әрбір қадамда түбір жатқан интервалдың екі шетінің де мәндерін табатын біріккен тәсілге ие боламыз. Хордалар тәсіліндегідей келесі жағдайларды қарастырамыз.

1. Егер (яғни - қимылдамайтын, сурет 4) онда

(3.28)

Бұл жерде

сурет. 4а сурет. 4б

2. Егер ( - қимылдамаса (сурет 5), онда

(3.29)

Бұл жерде .

сурет. 5а сурет. 5б

Итерация әдісі

Теңдеуді сандық шешудің тиімді әдістерінің бірі итерация әдісі болып табылады.

Теңдеу берілсін. .

Оны тең күшті . (3.30) теңдеуімен алмастырамыз.

Алғашқы жуық түбір -ді таңдап аламыз да оны (3.31) теңдеудің оң жағына апарып қоямыз. Сонда әйтеуір бір . (3.32)

санға ие боламыз. (3.32)-нің оң жағына -дің орнына санын қойып

санға ие боламыз. Осы процесті қайталап,

(). (3.33) сандар тізбегіне ие боламыз.

Егер осы тізбек жинақты болса, яғни шек бар болса, онда (3.33) теңдеуде шекке көшіп және функцияны үздіксіз деп,

немесе -ті табамыз.

Сонымен,

шек (3.33) теңдеудің шегі болады және оны (3.33) формуламен кез келген дәлдікте есептеуге болады.

сурет. 8а сурет. 8б

сурет. 9.

- жинақталмайтын процесс

8а, 8б суреттерде түбірдің маңайында итерациялық процесс жинақты. Бірақ, егер жағдайды қарастырсақ, онда итерациялық процесс жинақсыз болуы мүмкін (сурет 9).

Итерациялық процесстің жинақты болуының жеткілікті шарты.

Теорема 7. функция -да анықталған және дифференциялданушы болсын, сонымен қатар барлық және -да болсын. Онда итерациялық процесс алғашқы мәнге байланыссыз жинақты және шектің мәні теңдеудің кесіндідегі жалғыз мәні болады.

Дәлелдеуі: Екі тізбектелген жуықтауларды қарастырайық және және олардың айырымын қарайық . Лагранж теоремасы бойынша оң жағы былай болуы мүмкін.

Онда

деп,

(3.34)

(3.34) тен шарт бойынша тізбек әйтеуір бір санға жинақталады, яғни , демек ( -функцияның үздіксіздігінен) немесе

теорема дәлелденді.

түбірдің қателігі үшін келесі формуланы алуға болады.

Ары қарай

Енді

Нәтижеде

немесе

Бұл жерден , (3.35)

бұдан 1-ге жақын болғанда шама болғанына қарамай өте үлкен болуы мүмкін, бұл жерде -берілген сан. -ді дәлдікпен есептеу үшін,

. (3.36)

болуын қамтамасыз ету керек.

Онда (3.36)-ны (3.35)-ке қойып, -ді аламыз.

Егер өте аз болса, онда (3.35)-дың орнына

ды алуға болады.

Итерация әдісінің жинақтылық коэффициенті болып, жинақтылығы сызықты. Шынымен-ақ

бұл жерден .

Ескерту. Түбір жатқан аймақтың әйтеуір бір аймағында , теңдеу және оның туындысы таңбасын сақтасын және теңсіздік орындалсын. Онда, егер оң болса біртіндеп жуықтау түбірге монотонды жинақталады.