KIKOMO CHA KASI CHA 1974 CHA KUTATUA MILINGANYO CHATHIBITISHWA HATIMAYE

Ili kupata mahali kitendakazi (function) f kinapovuka sifuri, kompyuta mara nyingi huendesha marudio (iteration): anza na makisio x, kiulize kitendakazi maswali machache, kokotoa makisio bora zaidi, kisha rudia. Maswali hayo ni tathmini (evaluations): thamani ya f katika nukta fulani, au ya mteremko wake (kinyambuo, derivative), au ya kinyambuo cha juu zaidi.

Tarakimu zinazoongezeka maradufu

Kasi ya mbinu kama hiyo hupimwa kwa daraja lake (order). Ikiwa kosa la sasa ni ε, marudio ya daraja p huacha kosa la takriban ε kipeo p. Daraja 2 linamaanisha kwamba, karibu na jibu, idadi ya tarakimu sahihi huongezeka maradufu katika kila hatua; daraja 4, kwamba huongezeka mara nne.

Mbinu ya Newton hutumia tathmini mbili kwa kila hatua — f(x) na mteremko wake f′(x) — na kuhamia x − f(x)/f′(x). Ina daraja 2. Kuuliza maswali zaidi kwa kila hatua kunaweza kununua kasi zaidi. Swali ni kiasi gani.

Dhana ya mwaka 1974

Mwaka 1974, H. T. Kung na J. F. Traub walipendekeza jibu, kama “Conjecture 8.1” (Dhana 8.1) ya makala katika Journal of the ACM: marudio yasiyo na kumbukumbu yanayotumia tathmini n kwa kila hatua yana daraja lisilozidi 2ⁿ⁻¹. “Yasiyo na kumbukumbu” maana yake ni kwamba mbinu haihifadhi chochote kutoka hatua zilizopita isipokuwa makisio yake ya sasa.

Kikomo hicho hakingeweza kushushwa: Kung na Traub wenyewe walikuwa wamejenga mbinu za “nukta nyingi” (multipoint) zinazofikia 2ⁿ⁻¹ kwa kila n ≥ 2 — daraja 4 kwa tathmini tatu, 8 kwa nne, 16 kwa tano. Kilichokosekana kilikuwa nusu nyingine: uthibitisho kwamba hakuna mbinu inayoweza kufanya vizuri zaidi. Matokeo ya sehemu yalikuja pamoja na dhana hiyo na baada yake. Kikomo kilithibitishwa kwa mbinu zinazotegemea ukisiaji-kati (interpolation), kwa mbinu za kiuwiano (rational) zenye tathmini mbili, na chini ya masharti mbalimbali ya ziada; kwa mbinu zinazotumia thamani za kitendakazi pekee, kikomo dhaifu zaidi, 2ⁿ, kilithibitishwa. Hali ya jumla ilibaki wazi.

Kuihadaa algorithimu

Matthew Colbrook, wa Idara ya Hisabati Tumizi na Fizikia ya Nadharia ya University of Cambridge, sasa anaithibitisha kikamilifu. Modeli inayotumika kwa makusudi ni karimu kwa algorithimu. Algorithimu inaweza kuchagua mahali pa kutathmini, na vinyambuo vipi vya kuchukua, kadiri inavyoendelea. Inaweza kuchakata majibu kwa njia yoyote bainifu (deterministic) inayoipenda, bila ulaini wowote kuhitajika katika kanuni zake.

Uthibitisho unaigeuza ubainifu wa algorithimu yenyewe dhidi yake. Jenga vitendakazi viwili vinavyotoa majibu yaleyale kabisa kwa maswali yake yote lakini vyenye sifuri tofauti. Algorithimu lazima irudishe makisio yaleyale kwa vyote viwili, kwa hiyo kwa kimoja kati yake inakosea kwa angalau nusu ya umbali kati ya sifuri hizo mbili.

Ili kupata jozi kama hizo, Colbrook hukisukuma kidogo kitendakazi cha marejeo kwa polinomia ndogo ya shahada isiyozidi n, yenye vigawo n + 1 vinavyoweza kurekebishwa. Kila tathmini hufunga mchanganyiko mmoja tu wa vigawo hivyo kwa zaidi, kwa hiyo baada ya maswali n baadhi ya misukumo hiyo inabaki isiyoonekana kwa algorithimu. Hesabu hiyo peke yake haitoshi: msukumo usioonekana huenda ukasogeza sifuri kidogo tu.

Chombo muhimu ni Wronskian — dibainishi (determinant) linalojengwa kutokana na familia ya polinomia na vinyambuo vyake. Lema mpya inasema kwamba ikiwa polinomia ya familia hiyo ina sifuri nyingi zilizosongamana katika diski ndogo, Wronskian ya familia hiyo lazima iwe sifuri mahali fulani karibu na hapo. Kwa kuijibu algorithimu kila mara kwa kitendakazi ambacho sifuri yake inakaa mbali na nukta hizi chache, uthibitisho huiacha sifuri huru kusogea.

Uhasibu huu ndio unaozalisha kipeo. Kuanzia umbali ε kutoka sifuri, sifuri zinazowezekana zinabaki zimetawanyika katika wigo wa angalau kisawazisho fulani kikizidishwa na kipeo fulani cha ε. Kwa maneno ya mwandishi, “kipeo kinabaki kuwa kimoja baada ya uchunguzi wa kwanza kisha huongezeka maradufu, na kutoa 2ⁿ⁻¹ baada ya uchunguzi n.”

Kitendakazi kimoja kwa kila kiwango

Ugumu mmoja ulibaki. Ufafanuzi wa daraja unaruhusu kisawazisho kilicho mbele kutegemea kitendakazi, kwa hiyo kitendakazi kibaya tofauti katika kila kiwango (scale) hakithibitishi chochote. Kwa hiyo Colbrook anajenga kitendakazi kimoja, akiongeza marekebisho moja baada ya jingine, kila moja likiwa sifuri katika kila nukta ambayo algorithimu imekwisha kuuliza, ili majibu yote ya zamani yabaki sawasawa kabisa.

Kitendakazi kinachopatikana mwishoni ni kitendakazi kizima (entire function) — laini kila mahali, hata katika namba changamani — ambacho mteremko wake unabaki kati ya 3/4 na 5/4 kwenye mstari wa namba halisi: mkunjo unaopanda kwa utulivu wenye sifuri moja yenye tabia nzuri. Kwa p yoyote iliyo juu ya 2ⁿ⁻¹, mbinu inashindwa kufikia daraja p kwenye kitendakazi hicho. Kwa hiyo daraja bora zaidi bila kumbukumbu ni 2ⁿ⁻¹ kamili kwa n ≥ 2. Makala inathibitisha kikomo hichohicho pale tathmini zinapokuwa namba changamani.

Gharama ya kuuliza yote kwa pamoja

Kauli kali zaidi inashughulikia tathmini zinazofanywa kwa makundi, ambapo kila swali la kundi huchaguliwa kabla jibu lolote la kundi hilo halijafika — hali ya mbinu sambamba (parallel). Kwa makundi yenye ukubwa ℓ₁, …, ℓₖ, daraja halizidi ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). Kuuliza maswali yote n kwa pamoja kunaweka kikomo cha daraja kuwa n; kuyauliza moja baada ya jingine kunaruhusu 2ⁿ⁻¹. Kwa tathmini tano, hiyo ni 5 dhidi ya 16.

Kukaguliwa na mashine

Matokeo yamehakikishwa rasmi katika Lean, kisaidizi cha uthibitisho (proof assistant) kinachokagua kila hatua ya kimantiki. Msimbo ni wa umma na umesajiliwa katika sajili ya Palomar. Mwandishi anaeleza kwamba urasimishaji wa Lean ulifanywa kwa msaada wa ChatGPT 6, kisha ukakaguliwa kwa Lean 4 Comparator dhidi ya theoremu za makala, na kwamba kila hoja ilipitiwa na mwandishi, ambaye anachukua jukumu kamili kwa maudhui.

Kikomo hiki kinahusu mbinu zinazosahau. Mbinu zinazoruhusiwa kutumia tena hatua zao za awali hufuata vikomo vingine, ambavyo makala hii inaviweka kando.