ITP ыкмасы

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

ITP ыкмасы тамырдын жайгашкан жеринин жогорку жана төмөнкү чектерин көзөмөлдөсө, эң начар учурдагы көрсөткүчтөр жогорку чекте сакталган аймакты да көзөмөлдөйт. Бул структура салттуу кронштейн стратегиясына окшош. Кронштейн техникасын ишке ашыруу үчүн, ITP функциянын маанисин ар бир итерациянын бир жеринде сурайт жана функциянын мааниси бирдей белгиге ээ болгон эки чекиттин ортосундагы интервалдын бөлүгүн жок кылат. Сурамжыланган чекитти эсептөөгө үч кадам катышат: биринчиден, Регула фалсинин баасы интерполяция жолу менен табылат; андан кийин, болжолдоо бузулат же кыскартылат (Регула фалсидеги Регула фалсинин жакшыртуулары сыяктуу); акыры, бузулган болжолдоо экиге бөлүнгөн орто чекитке жакын аралыкка проекцияланат.Минмакс оптималдуулугун кепилдөө үчүн ар бир итерацияда экиге бөлүнүү чекитинин тегерегиндеги коңшулук эсептелет ( ^[1] теоремасы 2.1). Метод үч гипер-параметрге көз каранды $\kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)$ жана $n_{0}\in [0,\infty )$ кайда $\phi$ алтын катышы болуп саналат ${\tfrac {1}{2}}(1+{\sqrt {5}})$ : биринчи экөө кыскартуунун өлчөмүн көзөмөлдөйт, үчүнчүсү - проекция кадамы үчүн интервалдын өлчөмүн башкарган бош өзгөрмө. ^{[lower-alpha 1]}

Тамыр табуу көйгөйү

Үзгүлтүксүз функция берилген $f$ тартып аныкталат $[a,b]$ чейин $\mathbb {R}$ ушундай $f(a)f(b)\leq 0$ , бул жерде бир суроонун баасы менен баалуулуктарга жетүүгө болот $f(x)$ кандайдыр бир берилген боюнча $x$ . Жана, алдын ала белгиленген максаттуу так берилген $\epsilon >0$ , тамыр табуу алгоритми мүмкүн болушунча аз сандагы суроо менен төмөнкү маселени чечүү үчүн иштелип чыккан:

Көйгөйдүн аныктамасы: Табыңыз ${\hat {x}}$ ушундай $|{\hat {x}}-x^{*}|\leq \epsilon$ , кайда $x^{*}$ канааттандырат $f(x^{*})=0$ .

Компьютердик илимде, инженердик жана сандык анализде бул көйгөй көп кездешет жана аны чечүү үчүн кадимки ыкма-тамыр табуу ыкмаларын колдонуу. Тамыр маселелерин натыйжалуу чечүү өтө маанилүү, анткени натыйжасыз ыкма чоң контекстти эске алганда, олуттуу эсептөө чыгымдарына алып келиши мүмкүн. Көп учурда, тамыр табуу процедурасы чоңураак контекстте татаал ата-эне алгоритмдери менен аталат. ITP техникасы муну бир эле учурда экиге бөлүү ыкмасынын минималдуу оптималдуу кепилдиктерин жана интерполяциялык кепилдиктерди пайдалануу менен ишке ашырууну көздөйт. $n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil$ итерациялар интервалда башталганда $[a_{0},b_{0}]$ .

Ыкма

Берилген $\kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)$ , $n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil$ жана $n_{0}\in [0,\infty )$ кайда $\phi$ алтын катышы болуп саналат ${\tfrac {1}{2}}(1+{\sqrt {5}})$ , ар бир итерацияда $j=0,1,2\dots$ ITP ыкмасы пунктту эсептейт $x_{\text{ITP}}$ төмөнкү үч кадам:

ITP методунун 1-кадамы.

ITP методунун 2-кадамы.

ITP методунун 3-кадамы.

Бардык үч кадам ITP ыкмасын түзөт. Калың көк сызык ыкманын "болжолдонгон-кесилген-интерполяциясын" билдирет.

[Интерполяция кадамы] Бисекцияны жана нормалдуу жалган чекиттерди эсептеңиз: $x_{1/2}\equiv {\frac {a+b}{2}}$ жана $x_{f}\equiv {\frac {bf(a)-af(b)}{f(a)-f(b)}}$ ;
[Кыюу кадамы] Баалоочуну борборго карай буруңуз: $x_{t}\equiv x_{f}+\sigma \delta$ кайда $\sigma \equiv {\text{sign}}(x_{1/2}-x_{f})$ жана $\delta \equiv \min\{\kappa _{1}|b-a|^{\kappa _{2}},|x_{1/2}-x_{f}|\}$ ;
[Проекция кадамы] Баалоочуну минималдуу интервалга долбоорлоо: $x_{\text{ITP}}\equiv x_{1/2}-\sigma \rho _{k}$ кайда $\rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}},|x_{t}-x_{1/2}|\right\}$ .

Андан кийин, бул чекиттеги функциянын мааниси https://wikimedia.org/api/rest_v1/media/math/render/svg/1fbb08a19578e3fc2151a4f4459f7979f5779080 суралгандан кийин, ар бир учунда карама-каршы белгинин функциялык маанилери менен суб-интервалды сактоо менен тамырды курчап алуу үчүн интервал кыскартылат.d.

алгоритм

Төмөнкү алгоритм ( псевдокод менен жазылган) баштапкы маанилерин кабыл алат $y_{a}$ жана $y_{b}$ берилет жана канааттандырылат $y_{a}<0<y_{b}$ кайда $y_{a}\equiv f(a)$ жана $y_{b}\equiv f(b)$ ; жана, ал болжолду кайтарат ${\hat {x}}$ бул канааттандырат $|{\hat {x}}-x^{*}|\leq \epsilon$ эң көп $n_{1/2}+n_{0}$ функцияларды баалоо.

Input:  $a,b,\epsilon ,\kappa _{1},\kappa _{2},n_{0},f$  
    Preprocessing:  $n_{1/2}=\lceil \log _{2}{\tfrac {b-a}{2\epsilon }}\rceil$ ,  $n_{\max }=n_{1/2}+n_{0}$ , and   $j=0$ ;
    While (  $b-a>2\epsilon$  )
  
        Calculating Parameters:
             $x_{1/2}={\tfrac {a+b}{2}}$ ,  $r=\epsilon 2^{n_{\max }-j}-(b-a)/2$ ,  $\delta =\kappa _{1}(b-a)^{\kappa _{2}}$ ;
        Interpolation:
             $x_{f}={\tfrac {y_{b}a-y_{a}b}{y_{b}-y_{a}}}$ ;
        Truncation:
             $\sigma ={\text{sign}}(x_{1/2}-x_{f})$ ;
            If  $\delta \leq |x_{1/2}-x_{f}|$  then  $x_{t}=x_{f}+\sigma \delta$ ,
            Else  $x_{t}=x_{1/2}$ ;
        Projection:
            If  $|x_{t}-x_{1/2}|\leq r$  then  $x_{\text{ITP}}=x_{t}$ ,
            Else  $x_{\text{ITP}}=x_{1/2}-\sigma r$ ;
        Updating Interval:
             $y_{\text{ITP}}=f(x_{\text{ITP}})$ ;
            If  $y_{\text{ITP}}>0$  then  $b=x_{ITP}$  and  $y_{b}=y_{\text{ITP}}$ ,
            Elseif  $y_{\text{ITP}}<0$  then  $a=x_{\text{ITP}}$  and  $y_{a}=y_{\text{ITP}}$ ,
            Else  $a=x_{\text{ITP}}$  and  $b=x_{\text{ITP}}$ ;
             $j=j+1$ ;
Output:  ${\hat {x}}={\tfrac {a+b}{2}}$

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

Көп мүчөнүн тамырын табуу үчүн ITP ыкмасы колдонулат дейли $f(x)=x^{3}-x-2\,.$ Колдонуу $\epsilon =0.0005,\kappa _{1}=0.1,\kappa _{2}=2$ жана $n_{0}=1$ биз табабыз:

Итерация	$a_{n}$	$b_{n}$	$c_{n}$	$f(c_{n})$
1	1	2	1.43333333333333	-0,488629629629630
2	1.43333333333333	2	1.52713145056966	0.0343383329048983
3	1.43333333333333	1.52713145056966	1.52009281150978	-0,00764147709265051
4	1.52009281150978	1.52713145056966	1.52137899116052	-4.25363464540141e-06
5	1.52137899116052	1.52713145056966	1.52138301273268	1.96497878177659e-05
6	1.52137899116052	1.52138301273268	← Токтотуу критерийлери канааттандырылды

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

Анализ

ITP ыкмасынын негизги артыкчылыгы $n_{0}=0$ болгон учурда, аны экиге бөлүү ыкмасына караганда азыраак кайталоо керек. Ошондуктан, интерполяция иштебей калса дагы, анын орточо көрсөткүчү экиге бөлүү ыкмасынан жогору болот. Мындан тышкары, эгерде интерполяция ийгиликтүү болсо (түз функциялар) интерполяцияга негизделген ыкмалар менен бирдей жогорку конвергенцияга ээ экендиги кепилденет.

Эң начар көрсөткүч

Анткени ITP ыкмасы баалоочуну минмакс интервалына а менен проекциялайт $n_{0}$ боштук, ал эң көп талап кылат $n_{1/2}+n_{0}$ кайталоо ( теоремасы 2.1). Бул качан экиге бөлүү ыкмасы сыяктуу minmax оптималдуу болуп саналат $n_{0}$ болуу үчүн тандалат $n_{0}=0$ .

Орточо көрсөткүч

Анткени андан ашык талап кылынбайт $n_{1/2}+n_{0}$ итерациялар, итерациялардын орточо саны ар дайым экиге бөлүү ыкмасынан азыраак болот. $n_{0}=0$ ( ичинен 2.2 жыйынтык).

Асимптотикалык аткаруу

Эгерде функция $f(x)$ эки жолу дифференциалдануучу жана тамыры болуп саналат $x^{*}$ жөнөкөй болсо, анда ITP ыкмасы менен өндүрүлгөн интервалдар жакындашуу тартиби менен 0гө жакындайт. ${\sqrt {\kappa _{2}}}$ эгерде $n_{0}\neq 0$ же эгер $n_{0}=0$ жана $(b-a)/\epsilon$ термин менен 2дин күчү эмес ${\tfrac {\epsilon 2^{n_{1/2}}}{b-a}}$ нөлгө өтө жакын эмес ( теоремасы 2.3).

Эскертүүлөр

Гипер-параметрлерди тереңирээк талкуулоо үчүн, КУРБО китепканасындагы ITP үчүн документтерди караңыз.

↑ For a more in-depth discussion of the hyper-parameters, see the documentation for ITP in the kurbo library.

Шилтемелер

1.Argyros, I. K.; Hernández-Verón, M. A.; Rubio, M. J. (2019). "On the Convergence of Secant-Like Methods". Current Trends in Mathematical Analysis and Its Interdisciplinary Applications (in англисче). pp. 141–183. doi:10.1007/978-3-030-15242-0_5. ISBN 978-3-030-15241-3. Unknown parameter |s2cid= ignored (help)(жеткиликсиз шилтеме)

↑ .

2. 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.

3. Oliveira, I. F. D.; Takahashi, R. H. C. (2020-12-06). "An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality". ACM Transactions on Mathematical Software 47 (1): 5:1–5:24. doi:10.1145/3423597. ISSN 0098-3500. https://doi.org/10.1145/3423597.

[2] For a more in-depth discussion of the hyper-parameters, see the documentation for ITP in the kurbo library.

[:0-1] .

[1]

[lower-alpha 1]