Бисекция ыкмасы

Математикада ,бисекция ыкмасы - карама-каршы белгилери бар эки маанини билген ар кандай үзгүлтүксүз функцияга тиешелүү тамыр табуу ыкмасы .Процедура бул маанилер аныктаган интервалды бир нече жолу экиге бөлүү, андан кийин функциянын белгиси өзгөргөн субинтервалды тандоо, бул анын тамыры болушу керек экендигин көрсөтөт. Бул абдан жөнөкөй жана бекем ыкма, бирок ал дагы салыштырмалуу жай. Ушундан улам, ал көп учурда тезирээк жакындашуучу ыкмалар үчүн баштапкы чекит катары колдонулган чечимге болжолдуу жакындоону алуу үчүн колдонулат.  Бул метод интервалды жарымга бөлүү ыкмасы,  бинардык издөө ыкмасы,  же дихотомия ыкмасы деп да аталат. 

Көп мүчөлөр үчүн интервалда тамырдын бар экендигин текшерүү үчүн кеңири ыкмалар бар ( Декарттын белгилер эрежеси, Штурм теоремасы, Будан теоремасы ). Алар көп мүчөнүн бардык чыныгы тамырларын табуу үчүн экиге бөлүү ыкмасын эффективдүү алгоритмдерге кеңейтүүгө мүмкүндүк берет; Чыныгы тамыр изоляциясын караңыз.

 Ыкма 
Биринчи итерацияда тамырды кашаага алган интервалдын акыркы чекиттери болот  жана , ошондуктан орто чекит

Ар бир кадамда метод интервалдын c = ( a + b ) / 2 ортосун жана ошол чекиттеги f ( c ) функциясынын маанисин эсептөө менен интервалды эки бөлүккө/жарымга бөлөт.  Бул процесс с тамырынын өзү экенин аныктаганда аяктайт.  Болбосо, азыр эки гана мүмкүнчүлүк бар: же f ( a ) жана f ( c ) карама-каршы белгилери бар жана кашаа тамырга, же f ( c ) жана f ( b ) карама-каршы белгилери бар жана кашаа тамырга. If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function. Метод кийинки кадамда колдонула турган жаңы интервал катары кашаа болууга кепилдик берилген субинтервалды тандайт. Ошентип, f нөлүн камтыган интервал ар бир кадамда туурасы 50% га кыскарат. Процесс интервал жетиштүү аз болмоюнча улантылат.

Эгерде f ( c )=0 болсо, анда процесс аяктайт жана С жооп катары каралышы мүмкүн.  Болбосо, эгерде f ( a ) жана f ( c ) карама-каршы белгилер болсо, анда ыкма b үчүн жаңы маани катары c орнотот, ал эми f ( b ) жана f ( c ) карама-каршы белгилерге ээ болсо, анда метод с жаңы деп коёт. а . Эки учурда тең жаңы f ( a ) жана f ( b ) карама-каршы белгилерге ээ, ошондуктан ыкма ушул кичине интервалга колдонулат. 

 Итерация тапшырмалары 
Метод үчүн киргизүү үзгүлтүксүз функция f, интервал [ a, b ] жана функциянын маанилери f ( a ) жана f ( b ). Функциянын маанилери карама-каршы белгиге ээ (аралыктын ичинде жок дегенде бир нөлдүк кайчылаш бар). Ар бир итерация төмөнкү кадамдарды аткарат:

 Эсептеңиз c, интервалдын ортосу,  c=.
 Функциянын маанисин орто чекитте эсептегиле, f ( c ).
 Эгерде конвергенция канааттандырарлык болсо (б.а. c - a жетишээрлик кичине, же | f ( c )| жетишерлик кичинекей), c кайтарып, кайталоону токтотуңуз.
 f ( c ) белгисин карап чыгыңыз жана ( a, f ( a )) же ( b, f ( b )) менен алмаштырыңыз ( c, f ( c )) жаңы интервалда нөлдүк кесилиш бар болсун. ME = bfe

Компьютерде ыкманы колдонууда көбүнчө кошумча конвергенциялык тесттер же итерациялык эсептөө чектөөлөрү бар, анткени потенциалдуу чексиз тактык маселелери бар.f үзгүлтүксүз болгонуна карабастан, функциянын мааниси чексиз тактыкка байланыштуу эч качан нөлгө барабар болбошу мүмкүн. Мисалы, f(x) = cos x алалы.  x = π /2 ге жакын эч кандай өзгөрмө чекиттик маани так нөлдү бербейт. Мындан тышкары, жылмакай чекиттин тактыгы a менен b ортосундагы айырмачылыктын чегин белгилейт. башкача айтканда, a менен b ортосундагы ажырым тарлаган сайын, [а, b] ортосундагы чекит акыры сандык жактан a же b (калкуучу чекиттин тактыгынын ичинде) менен барабар болот.

 Алгоритм 
Метод псевдокоддо төмөнкүчө жазылышы мүмкүн: 
 киргизүү: Функциясы f, 
     акыркы чекит маанилери a, b, 
     сабырдуулук TOL, 
     максималдуу кайталоо NMAX
 шарттары: a < b, 
       же f ( a ) < 0 жана f ( b ) > 0 же f ( a ) > 0 жана f ( b ) < 0
 чыгаруу: f ( x ) = 0 тамырынан TOLдан азыраак айырмаланган маани

 N ← 1
 ал эми N ≤ NMAX do // чексиз циклди болтурбоо үчүн итерацияларды чектейт
   c ← ( a + b )/2 // жаңы орто чекит
   f ( c ) = 0 же ( b – a )/2 < TOL анда // чечим табылды
     Чыгуу( c )
     Токто
   бүтсө
   N ← N + 1 // кадам эсептегичти көбөйтүү
   if sign( f ( c )) = sign( f ( a )) анда a ← c else b ← c // жаңы интервал
 качан бүтөт
 Output("Метод ишке ашкан жок.") // кадамдардын максималдуу саны ашты

 Мисал: Көп мүчөнүн тамырын табуу 
Көп мүчө тамыры экиге бөлүү ыкмасы менен табылат дейли:



Биринчиден, эки сан  жана  ушундай табыш керек  жана  карама-каршы белгилер бар. Жогорудагы функция үчүн,  жана  сыяктуу бул критерийге жооп берет



Биринчи итерацияда тамырды кашаага алган интервалдын акыркы чекиттери болот  жана , ошондуктан орто чекит



Функция үзгүлтүксүз болгондуктан, [1, 2] аралыкта тамыр болушу керек.


Iteration1121.5−0.12521.521.751.609375031.51.751.6250.666015641.51.6251.56250.252197351.51.56251.53125000.059112561.51.53125001.5156250−0.034053871.51562501.53125001.52343750.012250481.51562501.52343751.5195313−0.010971291.51953131.52343751.52148440.0006222101.51953131.52148441.5205078−0.0051789111.52050781.52148441.5209961−0.0022794121.52099611.52148441.5212402−0.0008289131.52124021.52148441.5213623−0.0001034141.52136231.52148441.52142330.0002594151.52136231.52142331.52139280.0000780
13 кайталоодон кийин, болжол менен 1,521ге жакындашуу бар экени айкын болот: көп мүчө үчүн тамыр.

 Анализ 
Эгерде f [ a, b ] интервалында үзгүлтүксүз функция болсо жана f ( a ) жана f ( b ) карама-каршы белгилер болсо, метод f тамырына жакындашына кепилдик берилет. Абсолюттук ката ар бир кадамда эки эсеге азаят, ошондуктан метод сызыктуу жакындайт . Тактап айтканда, эгерде c 1 =  - баштапкы интервалдын ортосу, ал эми c n - n -кадамдагы интервалдын ортосу, анда c n менен c чечиминин ортосундагы айырма  менен чектелет.

Бисекция ыкмасынын белгилүү бир толеранттуулуктун ичинде тамырга жакындашы үчүн талап кылынган итерациялардын санынын жогорку чегин ушул формуланы колдонуудан мурун табууга болот. n чектелген мааниси-бул талап кылынган толеранттуулукка жетүү үчүн талап кылынган итерациялардын саны, бул эң көп дегенде ε  болушу кепилденген ката.



жерде баштапкы кашаа өлчөмү  жана керектүү кашаа өлчөмү  Бисекция ыкмасын колдонуунун негизги мотивациясы - үзгүлтүксүз функциялардын жыйындысы боюнча, эч бир башка ыкма c n чечиминин эң начар учурда c n баалоосун чыгарууга кепилдик бере албайт.  n 1/2 итерациядан азыраак абсолюттук ката.  Бул f функциясына жана функциянын тамырга жакын жердеги жүрүм-турумуна байланыштуу бир нече жалпы божомолдордо да туура.  

Бирок, абсолюттук ката критерийлери боюнча эң начар көрсөткүчтөргө карата биссекциялык ыкма оптималдуу болгонуна карабастан, стандарттык божомолдор боюнча   жана асимптотикалык көрсөткүчтөр боюнча орточо көрсөткүчтөргө карата субоптималдуу болуп саналат.  Бисекция ыкмасына популярдуу альтернативалар, мисалы, секант ыкмасы, Риддерс ыкмасы же Бренттин ыкмасы (башкалардын арасында) адатта жакшыраак иштешет, анткени алар тамырга жакындашуунун жогорку буйруктарына жетүү үчүн эң начар көрсөткүчтөрдү алмаштырышат. Жана, бисекция ыкмасын катуу жакшыртууга ITP Методунун эң начар көрсөткүчтөрүн алмаштырбастан конвергенциянын жогорку тартиби менен жетишүүгө болот.  

 Жогорку өлчөмдөргө жалпылоо 
Бисекция ыкмасы көп өлчөмдүү функцияларга жалпыланган. Мындай ыкмалар жалпыланган экиге бөлүнүү ыкмалары деп аталат.  

 Даражаны эсептөөгө негизделген методдор 
Бул ыкмалардын айрымдары топологиялык даражаны эсептөөгө негизделген. 

 Мүнөздүү экиге бөлүү ыкмасы 
Мүнөздүү экиге бөлүү ыкмасы функциянын ар кандай чекиттердеги белгилерин гана колдонот. Lef f кээ бир бүтүн d ≥ 2 үчүн R d ден R d ге чейинки функция. Мүнөздүү көп жактуу  (ошондой эле жол берилген көп бурчтук деп аталат)  f R d деги 2 d чокусу бар көп жактуу, ар бир v чокусунда f ( v ) белгилеринин айкалышы уникалдуу болуп саналат. Мисалы, d =2 үчүн, f үчүн мүнөздүү көп жактуу төрт бурчтуу, чокулары (айталы) A,B,C,D, мындай:

 f( A) = (-,-) белгиси, башкача айтканда, f 1 (A)<0, f 2 (A)<0.
 f (B) = (-,+) белгиси, башкача айтканда, f 1 (B)<0, f 2 (B)>0.
 f (C) = (+,-) белгиси, башкача айтканда, f 1 (C)>0, f 2 (C)<0.
 f (D) = (+,+) белгиси, башкача айтканда, f 1 (D)>0, f 2 (D)>0.

Мүнөздүү көп бурчтуктун туура чети - бул белги вектору бир гана белги менен айырмаланган жуп чокулардын ортосундагы кыр. Жогорудагы мисалда мүнөздүү төрт бурчтуктун туура четтери AB, AC, BD жана CD болуп саналат. Диагонал - бул белги вектору бардык d белгилери менен айырмаланган чокулардын жуптары. Жогорудагы мисалда диагоналдар AD жана BC болуп саналат.

Ар бир итерацияда алгоритм көп жүздүүнүн туура четин тандап алат (айталы, A--B) жана анын ортоңку чекитиндеги f белгилерин эсептейт (мисалы, M). Андан кийин ал төмөнкүдөй ишке ашат:

Түпнуска мүнөздүү көп кырдуу диаметри (= эң узун туура четинин узундугу) дейли  . Анда, жок дегенде  калган көп бурчтуктун диаметри эң көп болушу үчүн четтердин экиге бөлүнүшү талап кылынат  .  : 11, Lemma.4.7 

 Бинардык издөө алгоритми
 Лемер-Шур алгоритми, комплекстүү тегиздикте экиге бөлүү ыкмасын жалпылоо
 Уюшкан интервалдар1.2. 

3. 4.

5.If the function has the same sign at the endpoints of an interval, the endpoints may or

may not bracket roots of the function.

6. . This version recomputes the function values at each iteration rather than carrying them to the next iterations.

7.

8.



 Андан ары окуу 




 Тышкы шилтемелер 

 Weisstein, Eric W. "Bisection". MathWorld.
 Bisection Method Notes, PPT, Mathcad, Maple, Matlab, Mathematica from Holistic Numerical Methods Institute