Брент әдісімен түбір табу алгоритмі

Кіріспе

Тамыр табу алгоритмі
Бренттің циклді анықтау алгоритмі
Сандық талдауда Бренттің әдісі – екіге бөлу әдісін, секант әдісін және кері квадраттық интерполяцияны біріктіретін гибридті тамыр табу алгоритмі. Оның сенімділігі екіге бөлу сияқты, бірақ кейбір сенімсіз әдістердей жылдам болуы мүмкін. Алгоритм, мүмкін болса, потенциалды түрде жылдам жинақталатын секант әдісін немесе кері квадраттық интерполяцияны қолдануға тырысады, бірақ қажет болған жағдайда неғұрлым берік екіге бөлу әдісіне қайта оралады. Бренттің әдісі Ричард Брентке тиесілі және Теодорус Деккердің алдыңғы алгоритміне негізделген. Сондықтан бұл әдіс Брент-Деккер әдісі деп те аталады. Бренттің әдісінің қазіргі заманғы жақсартуларына Чандрупатла әдісі кіреді, ол тамырларының маңында тегіс функциялар үшін қарапайым және жылдам; Риддерс әдісі, ол итерациялар үшін қарапайым жабық формула беретін квадраттық емес, экспоненциалдық интерполяцияларды жүзеге асырады; және ITP әдісі, ол нашар жағдайдың ең нашар сценарийі мен асимптотикалық кепілдіктерге қол жеткізетін regula falsi және екіге бөлу арасындағы гибрид.

Мысал

Егер f(x) = (x + 3)(x − 1)2 функциясының нөлін іздеп жүрміз делік. [a0, b0] = [−4, 4/3] дегенді бастапқы аралық ретінде аламыз. Бізде f(a0) = -25 және f(b0) = 0.48148 (бұл бөлімдегі барлық сандар дөңгелектенді), сондықтан f(a0)f(b0) < 0 және |f(b0)| ≤ |f(a0)| шарттары қанағаттандырылады. Бірінші итерацияда (b−1, f(b−1)) = (a0, f(a0)) = (−4, −25) және (b0, f(b0)) = (1.33333, 0.48148) арасындағы сызықтық интерполяцияны қолданамыз, бұл s = 1.23256 береді. Бұл (3a0 + b0) / 4 және b0 арасында орналасқан, сондықтан бұл мән қабылданды. Сонымен қатар, f(1.23256) = 0.22891, сондықтан a1 = a0 және b1 = s = 1.23256 деп белгілейміз. Екінші итерацияда (a1, f(a1)) = (−4, −25) және (b0, f(b0)) = (1.33333, 0.48148) және (b1, f(b1)) = (1.23256, 0.22891) арасындағы кері квадраттық интерполяцияны қолданамыз. Бұл 1.14205 береді, ол (3a1 + b1) / 4 пен b1 арасында орналасқан. Сонымен қатар, |1.14205 − b1| ≤ |b0 − b−1| / 2 теңсіздігі қанағаттандырылады, сондықтан бұл мән қабылданды. Сонымен қатар, f(1.14205) = 0.083582, сондықтан a2 = a1 және b2 = 1.14205 деп белгілейміз. Үшінші итерацияда (a2, f(a2)) = (−4, −25) және (b1, f(b1)) = (1.23256, 0.22891) және (b2, f(b2)) = (1.14205, 0.083582) арасындағы кері квадраттық интерполяцияны қолданамыз. Бұл 1.09032 береді, ол (3a2 + b2) / 4 және b2 арасында орналасқан. Бірақ Бренттің қосымша шарты іске қосылады: |1.09032 − b2| ≤ |b1 − b0| / 2 теңсіздігі қанағаттандырылмаған, сондықтан бұл мән қабылданбайды. Оның орнына [a2, b2] интервалының орта нүктесі m = −1.42897 есептеледі. Бізде f(m) = 9.26891 бар, сондықтан a3 = a2 және b3 = −1.42897 деп белгілейміз. Төртінші итерацияда (a3, f(a3)) = (−4, −25) және (b2, f(b2)) = (1.14205, 0.083582) және (b3, f(b3)) = (−1.42897, 9.26891) арасындағы кері квадраттық интерполяцияны қолданамыз. Бұл 1.15448 береді, ол (3a3 + b3) / 4 және b3 аралығында емес. Сондықтан ол орта нүктесімен ауыстырылады m = −2.71449. Бізде f(m) = 3.93934 бар, сондықтан a4 = a3 және b4 = −2.71449 деп белгілейміз. Бесінші итерацияда кері квадраттық интерполяция −3.45500 береді, бұл қажетті аралықта жатыр. Алайда, алдыңғы итерацияда екіге бөлу кезеңі болды, сондықтан |−3.45500 − b4| ≤ |b4 − b3| / 2 теңсіздігі қанағаттандырылуы керек. Бұл теңсіздік қате, сондықтан орта нүктесі m = −3.35724 қолданылады. Бізде f(m) = −6.78239, сондықтан m жаңа қарсы нүктеге айналады (a5 = −3.35724) және итерациясы бірдей қалады (b5 = b4). Алтыншы итерацияда кері квадраттық интерполяцияны қолдануға болмайды, өйткені b5 = b4. Сондықтан (a5, f(a5)) = (−3.35724, −6.78239) және (b5, f(b5)) = (−2.71449, 3.93934) арасында сызықтық интерполяцияны қолданамыз. Нәтижесі s = −2.95064, бұл барлық шарттарды қанағаттандырады. Бірақ итерация алдыңғы қадамда өзгермегендіктен, біз осы нәтижені қабылдамаймыз және қайтадан екіге бөлуді қолданамыз. Біз s = 3.03587 және f(s) = 0.58418 жаңартамыз. Жетінші итерацияда кері квадраттық интерполяцияны қолданамыз. Нәтижесі s = −3.00219, бұл барлық шарттарды қанағаттандырады. Енді, f(s) = −0.03515, сондықтан біз a7 = b6 және b7 = −3.00219 деп белгілейміз (a7 және b7 алмасып, |f(b7)| ≤ |f(a7)| шарты орындалады). Сегізінші итерацияда кері квадраттық интерполяцияны қолдануға болмайды, өйткені a7 = b6. Сызықтық интерполяция s = −2.99994 береді, ол қабылданады. Келесі итерацияларда x = −3 түбіріне тез жақындалады: b9 = −3 + 6·10−8 және b10 = −3 − 3·10−15.

Suppose that we are seeking a zero of the function defined by f(x) = (x + 3)(x − 1)2. We take [a0, b0] = [−4, 4/3] as our initial interval. We have f(a0) = −25 and f(b0) = 0.48148 (all numbers in this section are rounded), so the conditions f(a0) f(b0) < 0 and |f(b0)| ≤ |f(a0)| are satisfied. In the first iteration, we use linear interpolation between (b−1, f(b−1)) = (a0, f(a0)) = (−4, −25) and (b0, f(b0)) = (1.33333, 0.48148), which yields s = 1.23256. This lies between (3a0 + b0) / 4 and b0, so this value is accepted. Furthermore, f(1.23256) = 0.22891, so we set a1 = a0 and b1 = s = 1.23256. In the second iteration, we use inverse quadratic interpolation between (a1, f(a1)) = (−4, −25) and (b0, f(b0)) = (1.33333, 0.48148) and (b1, f(b1)) = (1.23256, 0.22891). This yields 1.14205, which lies between (3a1 + b1) / 4 and b1. Furthermore, the inequality |1.14205 − b1| ≤ |b0 − b−1| / 2 is satisfied, so this value is accepted. Furthermore, f(1.14205) = 0.083582, so we set a2 = a1 and b2 = 1.14205. In the third iteration, we use inverse quadratic interpolation between (a2, f(a2)) = (−4, −25) and (b1, f(b1)) = (1.23256, 0.22891) and (b2, f(b2)) = (1.14205, 0.083582). This yields 1.09032, which lies between (3a2 + b2) / 4 and b2. But here Brent's additional condition kicks in: the inequality |1.09032 − b2| ≤ |b1 − b0| / 2 is not satisfied, so this value is rejected. Instead, the midpoint m = −1.42897 of the interval [a2, b2] is computed. We have f(m) = 9.26891, so we set a3 = a2 and b3 = −1.42897. In the fourth iteration, we use inverse quadratic interpolation between (a3, f(a3)) = (−4, −25) and (b2, f(b2)) = (1.14205, 0.083582) and (b3, f(b3)) = (−1.42897, 9.26891). This yields 1.15448, which is not in the interval between (3a3 + b3) / 4 and b3). Hence, it is replaced by the midpoint m = −2.71449. We have f(m) = 3.93934, so we set a4 = a3 and b4 = −2.71449. In the fifth iteration, inverse quadratic interpolation yields −3.45500, which lies in the required interval. However, the previous iteration was a bisection step, so the inequality |−3.45500 − b4| ≤ |b4 − b3| / 2 need to be satisfied. This inequality is false, so we use the midpoint m = −3.35724. We have f(m) = −6.78239, so m becomes the new contrapoint (a5 = −3.35724) and the iterate remains the same (b5 = b4). In the sixth iteration, we cannot use inverse quadratic interpolation because b5 = b4. Hence, we use linear interpolation between (a5, f(a5)) = (−3.35724, −6.78239) and (b5, f(b5)) = (−2.71449, 3.93934). The result is s = −2.95064, which satisfies all the conditions. But since the iterate did not change in the previous step, we reject this result and fall back to bisection. We update s = 3.03587, and f(s) = 0.58418. In the seventh iteration, we can again use inverse quadratic interpolation. The result is s = −3.00219, which satisfies all the conditions. Now, f(s) = −0.03515, so we set a7 = b6 and b7 = −3.00219 (a7 and b7 are exchanged so that the condition |f(b7)| ≤ |f(a7)| is satisfied). (Correct : linear interpolation 1=s = 2.99436, f(s) = 0.089961)
In the eighth iteration, we cannot use inverse quadratic interpolation because a7 = b6. Linear interpolation yields s = −2.99994, which is accepted. (Correct : 1=s = 2.9999, f(s) = 0.0016)
In the following iterations, the root x = −3 is approached rapidly: b9 = −3 + 6·10−8 and b10 = −3 − 3·10−15. (Correct : Iter 9 : f(s) = −1.4 × 10−7, Iter 10 : f(s) = 6.96 × 10−12)