Кіріспе

Функцияның нөлін табу алгоритмі, үздіксіз функциялардың нөлдерін іздеу

Математикада, екіге бөлу әдісі – екі қарама-қарсы белгілі мәні бар екені белгілі кез келген үздіксіз функцияға қолданылатын түбірді табу әдісі. Бұл әдіс осы мәндермен анықталған интервалды қайта-қайта екіге бөлуден және содан кейін функцияның таңбасы өзгеріп, демек түбірі болуға тиіс кіші интервалды таңдаудан тұрады. Бұл өте қарапайым және сенімді әдіс, бірақ салыстырмалы түрде баяу. Осы себепті, ол көбінесе шешімге жуық шамаменді мәнді алу үшін қолданылады, бұл мән кейіннен тез жинақталатын әдістердің бастапқы нүктесі ретінде пайдаланылады. Бұл әдіс интервалды жартылай бөлу әдісі, бинарлық іздеу әдісі немесе дихотомия әдісі деп те аталады. Полиномдар үшін интервалда түбірдің бар екенін тексеруге арналған күрделі әдістер бар (Декарттың белгілер ережесі, Штурм теоремасы, Будан теоремасы). Олар екіге бөлу әдісін полиномның барлық нақты түбірлерін табуға арналған тиімді алгоритмдерге кеңейтуге мүмкіндік береді; қараңыз Нақты түбірді оқшаулау.

Әдіс

Әдіс нақты айнымалы x үшін f(x) = 0 теңдеуін сандық түрде шешуге қолданылады, мұнда f – [a, b] аралығында анықталған үздіксіз функция, және f(a) мен f(b) қарама-қарсы таңбалы. Бұл жағдайда a және b түбірді қамтиды, себебі аралық мән теоремасы бойынша үздіксіз f функциясы (a, b) аралығында кем дегенде бір түбірге ие болуы керек. Әр қадамда әдіс интервалды екіге бөледі, интервалдың орта нүктесін c = (a+b) / 2 және сол нүктедегі f(c) функциясының мәнін есептейді. Егер c өзі түбір болса, процесс сәтті аяқталады. Әйтпесе, екі мүмкіндік қалады: f(a) және f(c) қарама-қарсы таңбалы болып, түбірді қамтиды, немесе f(c) және f(b) қарама-қарсы таңбалы болып, түбірді қамтиды. Әдіс келесі қадамда қолданылатын жаңа интервал ретінде түбірді қамтитыны анықталған кіші интервалды таңдайды. Осылайша f-тің нөлін қамтитын интервал әр қадамда 50%-ға қысқарады. Процесс интервал жеткілікті кіші болғанша жалғасады. Егер f(c) = 0 болса, c шешім ретінде алынып, процесс тоқтатылады. Әйтпесе, егер f(a) және f(c) қарама-қарсы таңбалы болса, әдіс c-ні b-нің жаңа мәні ретінде белгілейді, ал егер f(b) және f(c) қарама-қарсы таңбалы болса, әдіс c-ні жаңа a ретінде белгілейді. Екі жағдайда да жаңа 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 үздіксіз болса да, шекті дәлдік функция мәнінің нөлге тең болуына кедергі келтіруі мүмкін. Мысалы, 1=f(x) = cos x қарастырайық; дәл нөлді беретін қалқыма нүктелік шамалау жоқ. Сонымен қатар, a және b арасындағы айырмашылық қалқыма нүкте дәлдігімен шектеледі; яғни, a және b арасындағы айырмашылық азая берген сайын, [a, b] аралығының орта нүктесі сандық тұрғыдан (қалқыма нүкте дәлдігінде) a немесе b-ға тең болады.

Жоғары өлшемдерге жалпылау

Бисекция әдісі көп өлшемді функцияларға кеңейтілді. Мұндай әдістер жалпыланған бисекция әдістері деп аталады.

Степені есептеуге негізделген әдістер

Бұл әдістердің кейбіреулері топологиялық дәрежесін есептеуге негізделген.

Характерлік екіге бөлу әдісі

Характерлік екіге бөлу әдісі функцияның әр түрлі нүктелердегі белгілерін ғана пайдаланады. Келсін, f – d ≥ 2 болатын бүтін сан үшін Rd-ден Rd-ге дейінгі функция болсын. f-тың сипаттамалық көпбұрышы (оны рұқсат етілген көпбұрыш деп те атайды) – Rd-дегі 2d төбесі бар көпбұрыш, мұнда әрбір v төбесінде f(v) белгілерінің комбинациясы бірегей болады. Мысалы, d=2 болғанда, f-тың сипаттамалық көпбұрышы төртбұрыш болады, оның төбелері (мысалы) A, B, C, D, осындай:

Sign f(A) = (–, –), яғни f1(A) < 0, f2(A) < 0. Sign f(B) = (–, +), яғни f1(B) < 0, f2(B) > 0. Sign f(C) = (+, –), яғни f1(C) > 0, f2(C) < 0. Sign f(D) = (+, +), яғни f1(D) > 0, f2(D) > 0. Сипаттамалық көпбұрыштың дұрыс қабырғасы – бұл екі төбе арасындағы қабырға, мұнда белгі векторы бір ғана белгімен өзгереді. Жоғарыдағы мысалда, сипаттамалық төртбұрыштың дұрыс қабырғалары AB, AC, BD және CD болып табылады. Диагональ – бұл екі төбе, мұнда белгі векторы барлық d белгісімен өзгереді. Жоғарыдағы мысалда диагональдар AD және BC болып табылады. Әрбір итерацияда алгоритм көпбұрыштың дұрыс қабырғасын (мысалы, AB) таңдайды және оның орта нүктесіндегі (мысалы, M) f белгілерін есептейді. Содан кейін ол келесідей жалғасады:

Егер Sign f(M) = Sign(A) болса, онда A, M-мен ауыстырылады және кішірек сипаттамалық көпбұрыш алынады. Егер Sign f(M) = Sign(B) болса, онда B, M-мен ауыстырылады және кішірек сипаттамалық көпбұрыш алынады. Әйтпесе, жаңа дұрыс қабырға таңдалып, қайтадан талпыныс жасалады. Егер бастапқы сипаттамалық көпбұрыштың диаметрі (= ең ұзын дұрыс қабырғасының ұзындығы) D болса, онда қалған көпбұрыштың диаметрі D-ден аспауы үшін кем дегенде жартылайлаудың саны қажет.