Математика
📅 9 липня 2026 ⏱ ~9 хв читання

Числові методи для нулів функцій — Ньютон, бісекція, Брент

Кожна симуляція, що розв'язує неявне рівняння — від перетину променя зі сферою до рівноважних цін чи оберненої кінематики — зрештою потребує знайти точку, де функція перетинає нуль. Ось як бісекція, метод Ньютона-Рафсона, метод січних і гібридний алгоритм Брента атакують цю задачу, і чому промислові бібліотеки зупиняються саме на Бренті.

Автор: MySimulator Team · Рецензія: MySimulator Editorial Review

1. Задача пошуку коренів

Маючи неперервну функцію f(x), коренем є таке значення x*, що f(x*) = 0. Незліченні задачі симуляцій та інженерії зводяться саме до такої форми: знаходження точки перетину променя з неявною поверхнею, обчислення рівноважної процентної ставки, за якої поточна вартість облігації відповідає її ціні, розв'язання оберненої кінематики для кута суглоба, що досягає цільової точки, або знаходження термінальної швидкості, за якої сила опору точно врівноважує гравітацію.

Аналітичні розв'язки існують лише для окремих випадків — лінійних і квадратних рівнянь та кількох інших. Загальне рівняння п'ятого степеня взагалі не має формули в радикалах (результат, доведений Еваристом Галуа 1832 року), а більшість функцій, що виникають у фізиці, фінансах і графіці, трансцендентні — містять експоненти, тригонометричні функції або є виходами симуляцій без жодної замкненої форми. Чисельний пошук коренів тому не є обхідним шляхом — це єдиний загальний доступний метод.

Кожен практичний алгоритм пошуку коренів компромісує між трьома властивостями:

Надійність

гарантована збіжність?

Чи метод завжди знаходить корінь, якщо він існує в області пошуку, незалежно від форми функції?

Швидкість

ітерацій до збіжності

Скільки обчислень функції потрібно, щоб досягти точності машинного представлення?

Вимоги

похідна? вилка?

Чи метод потребує аналітичної похідної, чи двох стартових точок, що обмежують зміну знака?

Жоден метод не виграє за всіма трьома осями одночасно — саме тому промислові чисельні бібліотеки (fzero у MATLAB, optimize.brentq у SciPy, GNU Scientific Library) реалізують кілька алгоритмів і комбінують їх адаптивно.

2. Бісекція: повільно, але надійно

Бісекція спирається на теорему про проміжне значення: якщо f неперервна на [a, b] і f(a) та f(b) мають протилежні знаки, то десь у (a, b) обов'язково є корінь. Алгоритм просто ділить навпіл інтервал пошуку на кожному кроці, завжди залишаючи ту половину, де ще є зміна знака:

Алгоритм бісекції: Маючи [a, b] з f(a)·f(b) < 0 (протилежні знаки) повторювати: m = (a + b) / 2 якщо f(a)·f(m) < 0: b = m → корінь у [a, m] інакше: a = m → корінь у [m, b] доки |b - a| < допуск Збіжність: ширина інтервалу зменшується вдвічі щоітерації похибка після n ітерацій ≈ (b₀ - a₀) / 2ⁿ → лінійна збіжність, +1 правильний біт за ітерацію → ~50 ітерацій для подвійної точності (2⁻⁵⁰ ≈ 10⁻¹⁵)

Гарантія безумовна: доки початкова вилка має протилежні знаки, а f неперервна, бісекція не може не збігтися до кореня, хоч би якою дикою була форма функції між кінцями відрізка. Саме тому вона є останнім рубежем усередині кожного гібридного розв'язувача — коли швидші методи поводяться погано, бісекція є страховкою, що гарантує прогрес.

Ціна цієї гарантії — швидкість: бісекції потрібно приблизно 50 ітерацій, щоб досягти ~15-16 значущих розрядів подвійної точності з рухомою крапкою, набуваючи лише одного біта точності (близько 0.3 десяткового розряду) за крок. Вона також повністю ігнорує форму функції — трактує майже лінійну функцію та шалено осцилюючу однаково, відкидаючи корисну інформацію, яку розумніший метод міг би використати.

Вимога вилки: бісекції потрібні дві стартові точки з f(a) та f(b) протилежного знака. Знайти таку вилку взагалі — особливо для функцій із кількома коренями чи вузькими сплесками — саме собою є нетривіальною задачею, зазвичай виконуваною скануванням грубої сітки зразків на предмет зміни знака перед запуском бісекції.

3. Ньютон-Рафсон: квадратична швидкість без страховки

Метод Ньютона-Рафсона (опублікований Ісааком Ньютоном 1669 року та вдосконалений Джозефом Рафсоном 1690 року) обирає протилежний підхід: замість обмеження вилкою він використовує локальну інформацію — значення функції та її похідну в поточній точці — щоб стрибнути прямо туди, де дотична перетинає нуль:

Ітерація Ньютона-Рафсона: xₙ₊₁ = xₙ - f(xₙ) / f'(xₙ) Геометрична інтерпретація: проведіть дотичну до f у xₙ, знайдіть, де ця дотична перетинає вісь x — це xₙ₊₁. Приклад: пошук √2 (корінь f(x) = x² - 2, f'(x) = 2x) x₀ = 1.0 x₁ = 1.0 - (1 - 2)/2 = 1.5 x₂ = 1.5 - (2.25 - 2)/3 = 1.41666... x₃ = 1.41666... - ... = 1.41421568... x₄ = 1.41421356237... (правильно до 11 розрядів)

Швидкість вражає: коли ітерація достатньо близька до простого кореня, а похідна поводиться добре, метод Ньютона демонструє квадратичну збіжність — кількість правильних розрядів приблизно подвоюється на кожному кроці. Чотири-шість ітерацій із розумного початкового наближення регулярно досягають повної точності IEEE подвійної точності (близько 15-16 значущих розрядів), порівняно з ~50 ітераціями бісекції для тієї ж точності.

Ця швидкість дорого коштує справжньою крихкістю. Метод Ньютона може поводитися погано кількома окремими способами:

Хаотичні басейни притягання: застосування методу Ньютона для пошуку комплексних коренів поліномів на кшталт z³ - 1 = 0 та розфарбовування кожної стартової точки за тим, до якого з трьох коренів вона збігається, дає разюче фрактальне зображення — басейни притягання мають нескінченно детальну самоподібну межу. Це один із найвідоміших прикладів, що зв'язує елементарний числовий аналіз із теорією хаосу.

4. Метод січних: Ньютон без похідних

Метод січних замінює точну похідну Ньютона наближенням скінченними різницями, обчисленим із двох найновіших ітерацій — нахилом прямої через останні дві точки, а не справжньою дотичною:

Ітерація методу січних: xₙ₊₁ = xₙ - f(xₙ) · (xₙ - xₙ₋₁) / (f(xₙ) - f(xₙ₋₁)) Потребує двох стартових точок x₀, x₁ (не обов'язково вилка) Кожен крок потребує лише ОДНОГО нового обчислення функції (повторно використовує попереднє значення f) → приблизно вдвічі швидший за одиницю роботи, ніж Ньютон, попри повільніший порядок збіжності

Порядок збіжності дорівнює золотому перетину φ ≈ 1.618 (красивий і несподіваний факт, доведений аналізом рекурентного співвідношення похибки) — повільніше за квадратичний (порядок 2) Ньютона, але все ще надлінійний, і набагато швидший за лінійний порядок 1 бісекції. Оскільки метод січних не потребує аналітичної похідної — лише значень функції — це практичний вибір щоразу, коли f'(x) недоступна чи дорога, наприклад коли f сама є виходом дорогої симуляції «чорної скриньки».

Як і метод Ньютона, метод січних не гарантує збіжності: він може розбігатися і не успадковує жодної страховки бісекції. На практиці його майже завжди розгортають усередині гібридної схеми, що падає назад до бісекції щоразу, коли крок січної вийшов би за межі відомої вилки.

5. Метод Брента: промисловий вибір за замовчуванням

Річард Брент опублікував свій алгоритм 1973 року, спираючись на ранішу роботу Теодора Деккера. Метод Брента — ретельно спроєктований гібрид, що бере найкраще з кожного підходу: він підтримує обмежувальний інтервал (як бісекція, гарантуючи збіжність), але на кожному кроці намагається зробити швидший крок інтерполяції (обернена квадратична інтерполяція, або січна, якщо доступні лише дві точки) і падає назад до гарантованого кроку бісекції лише тоді, коли швидкий крок мав би зазнати невдачі чи збігатися надто повільно.

Метод Брента, неформальний нарис: підтримувати вилку [a, b] з f(a)·f(b) < 0, і найкраще наближення дотепер на кожному кроці: якщо доступні 3 різні точки: спробувати обернену квадратичну інтерполяцію (провести параболу через (a,f(a)), (b,f(b)), (prev,f(prev)); її корінь оцінює новий x) інакше: спробувати крок січної якщо інтерпольований крок: - виходить за межі поточної вилки, АБО - не звужує інтервал достатньо швидко порівняно з попереднім кроком тоді: падати назад до звичайного кроку бісекції (гарантований прогрес) оновити вилку, зберігаючи кінці протилежного знака доки |b - a| < допуск

Результат поєднує непохитну гарантію збіжності бісекції з надлінійною (часто майже квадратичною) практичною швидкістю щоразу, коли функція поводиться добре. Саме тому метод Брента (чи його незначні варіанти) є типовим пошуком коренів за замовчуванням майже в кожній серйозній чисельній бібліотеці: optimize.brentq у SciPy, fzero у MATLAB, gsl_root_fsolver_brent у GNU Scientific Library та zbrent у Numerical Recipes — усі реалізують по суті той самий алгоритм.

Практичне правило, що випливає з усього цього: сягайте по метод Ньютона-Рафсона, коли у вас є дешева аналітична похідна, хороше початкове наближення і потрібна максимально швидка збіжність усередині щільного циклу (наприклад, обернена кінематика, розв'язувана кожного кадру симуляції). Сягайте по метод Брента щоразу, коли можете обмежити корінь вилкою й потрібен надійний, загальний розв'язувач «чорної скриньки», що не вибухне на складній функції — а це описує переважну більшість реальних викликів пошуку коренів у промисловому софті.

Досліджуйте математичні симуляції

Візуалізуйте хаос, фрактали, складні системи та математичні феномени інтерактивно.

Досліджувати математику →

Пов'язані статті

Стаття Метод Ньютона для квадратних коренів Розібраний приклад квадратичної збіжності Стаття Фрактальна геометрія Басейни фракталу Ньютона та комплексна динаміка Категорія Математика Теорія хаосу, фрактали та складні системи

Часті запитання

Який метод пошуку коренів обрати за замовчуванням?

Для загального застосування використовуйте метод Брента (або його реалізацію в Python scipy.optimize.brentq): він поєднує гарантовану збіжність бісекції зі швидкістю методу січних/оберненої квадратичної інтерполяції, і саме його внутрішньо використовує більшість промислових чисельних бібліотек, коли доступний інтервал-«вилка». Метод Ньютона-Рафсона краще використовувати, коли у вас є дешева аналітична похідна й хороше початкове наближення та потрібна максимальна швидкість, наприклад усередині щільного циклу симуляції.

Чому метод Ньютона іноді не збігається?

Метод Ньютона може зазнати невдачі, коли: похідна f'(x) дорівнює нулю або близька до нуля на якійсь ітерації (ділення вибухає, або крок прямує до нескінченності), початкове наближення далеко від кореня, а функція сильно немонотонна (ітерація може коливатися або розбігатися), корінь має кратність більшу за одиницю (збіжність деградує з квадратичної до лінійної), або функція недиференційовна в точках, відвіданих ітерацією. Бісекція ніколи не має цих режимів відмови ціною значно нижчої швидкості.

Що означає «квадратична збіжність» на практиці?

Квадратична збіжність означає, що кількість правильних десяткових розрядів приблизно подвоюється на кожній ітерації, щойно ітерація достатньо близька до кореня. Якщо метод Ньютона має 2 правильні розряди, наступна ітерація зазвичай дає приблизно 4, потім 8, потім 16 — повна точність подвійної точності (близько 15-16 розрядів) часто досягається за 4-6 ітерацій з розумної початкової точки. Бісекція, навпаки, набуває лише близько 0.3 десяткового розряду за ітерацію (один біт), потребуючи приблизно 50 ітерацій для тієї ж точності.

Яка різниця між бісекцією та методом січних?

Бісекція завжди ділить навпіл інтервал-вилку, у якому напевно є зміна знака — вона повільна (лінійна збіжність), але математично гарантовано працює. Метод січних використовує нахил між двома найновішими обчисленнями функції, щоб стрибнути прямо до оціненого кореня — він збігається швидше (надлінійно, порядок ≈1.618), але не гарантовано, і зовсім не потребує вилки зі зміною знака.

Навіщо в методі Брента використовується обернена квадратична інтерполяція?

Обернена квадратична інтерполяція проводить параболу через три найновіші точки (x, f(x)) і трактує x як функцію від f, потім обчислює цю параболу при f=0, щоб оцінити корінь. Коли доступні три точки, вона збігається швидше за двоточковий метод січних (що проводить лише пряму), даючи методу Брента додаткове прискорення над звичайними гібридами «січна плюс бісекція», коли є достатньо історії.

Чи можна методи пошуку коренів використовувати для розв'язання систем із кількох рівнянь?

Бісекція та метод Брента фундаментально одновимірні — вони спираються на властивість вилки зі зміною знака, яка має сенс лише на прямій. Для систем рівнянь із кількома змінними природним узагальненням методу Ньютона є багатовимірний метод Ньютона, що використовує матрицю Якобі частинних похідних замість скалярної похідної, розв'язуючи лінійну систему на кожному кроці. Квазіньютонівські методи (як-от метод Бройдена) наближають матрицю Якобі, щоб уникнути її явного обчислення.

Що таке фрактал Ньютона і чому він схожий на множину Мандельброта?

Фрактал Ньютона утворюється застосуванням методу Ньютона до комплексного полінома (наприклад, z³-1=0) з кожної точки комплексної площини та розфарбовуванням кожної стартової точки за тим, до якого кореня вона збігається. Оскільки метод Ньютона є хаотичною динамічною системою поблизу меж між басейнами притягання, межа між зафарбованими областями нескінченно детальна та самоподібна — фрактал, хоч і породжений зовсім іншим механізмом, ніж ітерація escape-time множини Мандельброта.

Як симуляції використовують пошук коренів на практиці?

Поширені застосування: перетин променя з неявною поверхнею у трасувальниках променів та рендерингу полів знакових відстаней (пошук параметра t променя, за якого f(t)=0), обернена кінематика (пошук кутів суглобів, що розміщують кінцевий ефектор у цільовій точці), знаходження точок рівноваги фізичних систем (де сумарна сила дорівнює нулю), калібрування імпліцитної волатильності в ціноутворенні опціонів (чисельно обернена формула Блека-Шоулза), а також знаходження точок перетину кривих чи термінальної швидкості в симуляції опору.

Що станеться, якщо початкова вилка для бісекції не містить зміни знака?

Якщо f(a) і f(b) мають однаковий знак, бісекція не може гарантувати наявність кореня в [a,b] — теорема про проміжне значення просто не застосовна, оскільки всередині (a,b) може бути нуль, два чи будь-яка парна кількість коренів (або жодного). Надійний софт пошуку коренів зазвичай спершу сканує грубу сітку зразків, шукаючи сусідні зразки з протилежним знаком значення функції, щоб побудувати дійсну стартову вилку перед викликом бісекції чи методу Брента.

Чи метод Ньютона те саме, що градієнтний спуск?

Вони пов'язані, але різні. Метод Ньютона для пошуку коренів безпосередньо розв'язує f(x)=0, використовуючи першу похідну. Метод Ньютона для оптимізації (пошуку мінімуму g(x)) застосовує ітерацію пошуку коренів до g'(x)=0, потребуючи другої похідної (матриці Гессе у вищих вимірах) — це збігається швидше за градієнтний спуск поблизу мінімуму, але потребує дорожчої інформації про похідні й може не збігтися до мінімуму (замість сідлової точки чи максимуму), якщо матриця Гессе не є додатно визначеною.