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

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

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

Ыкма

Биринчи итерацияда тамырды кашаага алган интервалдын акыркы чекиттери болот $a_{1}=1$ жана $b_{1}=2$ , ошондуктан орто чекит

Ар бир кадамда метод интервалдын c = ( a + b ) / 2 ортосун жана ошол чекиттеги f ( c ) функциясынын маанисин эсептөө менен интервалды эки бөлүккө/жарымга бөлөт. Бул процесс с тамырынын өзү экенин аныктаганда аяктайт. Болбосо, азыр эки гана мүмкүнчүлүк бар: же f ( a ) жана f ( c ) карама-каршы белгилери бар жана кашаа тамырга, же f ( c ) жана f ( b ) карама-каршы белгилери бар жана кашаа тамырга. ^[3] Метод кийинки кадамда колдонула турган жаңы интервал катары кашаа болууга кепилдик берилген субинтервалды тандайт. Ошентип, 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=Калып:Sfrac.
Функциянын маанисин орто чекитте эсептегиле, 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("Метод ишке ашкан жок.") // кадамдардын максималдуу саны ашты

Мисал: Көп мүчөнүн тамырын табуу

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

f(x)=x^{3}-x-2\,.

Биринчиден, эки сан $a$ жана $b$ ушундай табыш керек $f(a)$ жана $f(b)$ карама-каршы белгилер бар. Жогорудагы функция үчүн, $a=1$ жана $b=2$ сыяктуу бул критерийге жооп берет

f(1)=(1)^{3}-(1)-2=-2

Биринчи итерацияда тамырды кашаага алган интервалдын акыркы чекиттери болот $a_{1}=1$ жана $b_{1}=2$ , ошондуктан орто чекит

f(2)=(2)^{3}-(2)-2=+4\,.

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

c_{1}={\frac {2+1}{2}}=1.5

Iteration	$a_{n}$	$b_{n}$	$c_{n}$	$f(c_{n})$
1	1	2	1.5	−0.125
2	1.5	2	1.75	1.6093750
3	1.5	1.75	1.625	0.6660156
4	1.5	1.625	1.5625	0.2521973
5	1.5	1.5625	1.5312500	0.0591125
6	1.5	1.5312500	1.5156250	−0.0340538
7	1.5156250	1.5312500	1.5234375	0.0122504
8	1.5156250	1.5234375	1.5195313	−0.0109712
9	1.5195313	1.5234375	1.5214844	0.0006222
10	1.5195313	1.5214844	1.5205078	−0.0051789
11	1.5205078	1.5214844	1.5209961	−0.0022794
12	1.5209961	1.5214844	1.5212402	−0.0008289
13	1.5212402	1.5214844	1.5213623	−0.0001034
14	1.5213623	1.5214844	1.5214233	0.0002594
15	1.5213623	1.5214233	1.5213928	0.0000780

13 кайталоодон кийин, болжол менен 1,521ге жакындашуу бар экени айкын болот: көп мүчө үчүн тамыр.

Анализ

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

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

n\leq n_{1/2}\equiv \left\lceil \log _{2}\left({\frac {\epsilon _{0}}{\epsilon }}\right)\right\rceil ,

жерде баштапкы кашаа өлчөмү $\epsilon _{0}=|b-a|$ жана керектүү кашаа өлчөмү $\epsilon \leq \epsilon _{0}.$ Бисекция ыкмасын колдонуунун негизги мотивациясы - үзгүлтүксүз функциялардын жыйындысы боюнча, эч бир башка ыкма c n чечиминин эң начар учурда c _n баалоосун чыгарууга кепилдик бере албайт. $\epsilon$ n _1/2 итерациядан азыраак абсолюттук ката. ^[4] Бул f функциясына жана функциянын тамырга жакын жердеги жүрүм-турумуна байланыштуу бир нече жалпы божомолдордо да туура. ^[4] ^[5]

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

Жогорку өлчөмдөргө жалпылоо

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

Даражаны эсептөөгө негизделген методдор

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

Мүнөздүү экиге бөлүү ыкмасы

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

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

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

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

Түпнуска мүнөздүү көп кырдуу диаметри (= эң узун туура четинин узундугу) дейли $D$ . Анда, жок дегенде $\log _{2}(D/\varepsilon )$ калган көп бурчтуктун диаметри эң көп болушу үчүн четтердин экиге бөлүнүшү талап кылынат $\varepsilon$ . ^[14] : 11, Lemma.4.7

Бинардык издөө алгоритми
Лемер-Шур алгоритми, комплекстүү тегиздикте экиге бөлүү ыкмасын жалпылоо
Уюшкан интервалдар1.Калып:Harvnb2. Interval Halving (Bisection). Текшерилген күнү 5 -май (бугу) 2024. Түп булактан архивделген күнү 19 -май (бугу) 2013.

3. Калып:Harvnb4.Dichotomy method - Encyclopedia of Mathematics.

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. Калып:Harvnb. This version recomputes the function values at each iteration rather than carrying them to the next iterations.

7.Graf, Siegfried; Novak, Erich; Papageorgiou, Anargyros (1989-07-01). "Bisection is not optimal on the average" (in en). Numerische Mathematik 55 (4): 481–491. doi:10.1007/BF01396051. ISSN 0945-3245. https://doi.org/10.1007/BF01396051.

8.Kearfott, Baker (1979-06-01). "An efficient degree-computation method for a generalized method of bisection" (in en). Numerische Mathematik 32 (2): 109–127. doi:10.1007/BF01404868. ISSN 0945-3245. https://doi.org/10.1007/BF01404868.

Burden, Richard L.; Faires, J. Douglas (1985), "2.1 The Bisection Algorithm", Numerical Analysis (3rd ed.), PWS Publishers, ISBN 0-87150-857-5

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

Which root does the bisection algorithm find?, 1977
Numerical Methods with Applications, 2008

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

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

↑ Interval Halving (Bisection). Текшерилген күнү 5 -май (бугу) 2024. Түп булактан архивделген күнү 19 -май (бугу) 2013.
↑ Dichotomy method - Encyclopedia of Mathematics.
↑ If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function.
↑ ^4.0 ^4.1 Sikorski, K. (1982-02-01). "Bisection is optimal" (in en). Numerische Mathematik 40 (1): 111–117. doi:10.1007/BF01459080. ISSN 0945-3245. https://doi.org/10.1007/BF01459080.
↑ Sikorski, K (1985-12-01). "Optimal solution of nonlinear equations" (in en). Journal of Complexity 1 (2): 197–209. doi:10.1016/0885-064X(85)90011-1. ISSN 0885-064X.
↑ Graf, Siegfried (1989-07-01). Bisection is not optimal on the average. doi:10.1007/BF01396051. https://doi.org/10.1007/BF01396051.
↑ Novak, Erich (1989-12-01). Average-case results for zero finding. doi:10.1016/0885-064X(89)90022-8.
↑ ^8.0 ^8.1 Oliveira, I. F. D. (2020-12-06). An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality. doi:10.1145/3423597. https://doi.org/10.1145/3423597.
↑ OliveiraIvo An Improved Bisection Method (14 -декабрь (бештин айы) 2020). doi:10.1145/3423597.
↑ .
↑ Vrahatis, Michael N. (2020). "Generalizations of the Intermediate Value Theorem for Approximating Fixed Points and Zeros of Continuous Functions". In Sergeyev, Yaroslav D.; Kvasov, Dmitri E. Numerical Computations: Theory and Algorithms. Lecture Notes in Computer Science (in англисче). 11974. Cham: Springer International Publishing. pp. 223–238. doi:10.1007/978-3-030-40616-5_17. ISBN 978-3-030-40616-5.
↑ Kearfott, Baker (1979-06-01). "An efficient degree-computation method for a generalized method of bisection" (in en). Numerische Mathematik 32 (2): 109–127. doi:10.1007/BF01404868. ISSN 0945-3245. https://doi.org/10.1007/BF01404868.
↑ Vrahatis, Michael N. (1995-06-01). "An Efficient Method for Locating and Computing Periodic Orbits of Nonlinear Mappings" (in en). Journal of Computational Physics 119 (1): 105–119. Bibcode 1995JCoPh.119..105V. doi:10.1006/jcph.1995.1119. ISSN 0021-9991. https://www.sciencedirect.com/science/article/pii/S0021999185711199.
↑ ^14.0 ^14.1 Vrahatis, M. N.; Iordanidis, K. I. (1986-03-01). "A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations" (in en). Numerische Mathematik 49 (2): 123–138. doi:10.1007/BF01389620. ISSN 0945-3245. https://doi.org/10.1007/BF01389620.

[1] Interval Halving (Bisection). Текшерилген күнү 5 -май (бугу) 2024. Түп булактан архивделген күнү 19 -май (бугу) 2013.

[2] Dichotomy method - Encyclopedia of Mathematics.

[3] If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function.

[:0-4] 4.0 ^4.1 Sikorski, K. (1982-02-01). "Bisection is optimal" (in en). Numerische Mathematik 40 (1): 111–117. doi:10.1007/BF01459080. ISSN 0945-3245. https://doi.org/10.1007/BF01459080.

[5] Sikorski, K (1985-12-01). "Optimal solution of nonlinear equations" (in en). Journal of Complexity 1 (2): 197–209. doi:10.1016/0885-064X(85)90011-1. ISSN 0885-064X.

[6] Graf, Siegfried (1989-07-01). Bisection is not optimal on the average. doi:10.1007/BF01396051. https://doi.org/10.1007/BF01396051.

[7] Novak, Erich (1989-12-01). Average-case results for zero finding. doi:10.1016/0885-064X(89)90022-8.

[:1-8] 8.0 ^8.1 Oliveira, I. F. D. (2020-12-06). An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality. doi:10.1145/3423597. https://doi.org/10.1145/3423597.

[9] OliveiraIvo An Improved Bisection Method (14 -декабрь (бештин айы) 2020). doi:10.1145/3423597.

[10] .

[11] Vrahatis, Michael N. (2020). "Generalizations of the Intermediate Value Theorem for Approximating Fixed Points and Zeros of Continuous Functions". In Sergeyev, Yaroslav D.; Kvasov, Dmitri E. Numerical Computations: Theory and Algorithms. Lecture Notes in Computer Science (in англисче). 11974. Cham: Springer International Publishing. pp. 223–238. doi:10.1007/978-3-030-40616-5_17. ISBN 978-3-030-40616-5.

[12] Kearfott, Baker (1979-06-01). "An efficient degree-computation method for a generalized method of bisection" (in en). Numerische Mathematik 32 (2): 109–127. doi:10.1007/BF01404868. ISSN 0945-3245. https://doi.org/10.1007/BF01404868.

[13] Vrahatis, Michael N. (1995-06-01). "An Efficient Method for Locating and Computing Periodic Orbits of Nonlinear Mappings" (in en). Journal of Computational Physics 119 (1): 105–119. Bibcode 1995JCoPh.119..105V. doi:10.1006/jcph.1995.1119. ISSN 0021-9991. https://www.sciencedirect.com/science/article/pii/S0021999185711199.

[:2-14] 14.0 ^14.1 Vrahatis, M. N.; Iordanidis, K. I. (1986-03-01). "A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations" (in en). Numerische Mathematik 49 (2): 123–138. doi:10.1007/BF01389620. ISSN 0945-3245. https://doi.org/10.1007/BF01389620.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]