Численное решение нелинейных уравнений: метод дихотомии и метод Ньютона

Проблема поиска корней функции

Одной из классических задач вычислительной математики является поиск корней нелинейного уравнения вида f(x) = 0. На практике это означает поиск точек пересечения графика функции с осью абсцисс. В то время как для линейных уравнений и квадратных трехчленов существуют простые аналитические формулы, для полиномов высоких степеней (начиная с пятой) таких формул в радикалах не существует, согласно теореме Абеля-Руффини. Для трансцендентных уравнений, содержащих тригонометрические или экспоненциальные функции, точное решение также, как правило, недостижимо. В таких случаях мы используем итерационные численные алгоритмы.

Процесс численного решения уравнения обычно делится на два этапа. Первый этап — это локализация (или отделение) корней, то есть нахождение отрезков [a, b], внутри которых содержится ровно один корень. Второй этап — уточнение корня с заданной точностью до тех пор, пока условие остановки не будет выполнено.

Метод половинного деления (дихотомии)

Самым надежным, хотя и достаточно медленным, является метод дихотомии. Он базируется на теореме Больцано-Коши, которая гласит: если непрерывная функция f(x) на концах отрезка [a, b] принимает значения разных знаков (то есть f(a) * f(b) < 0), то внутри этого отрезка существует хотя бы один корень.

Алгоритм метода предельно прост. Мы находим середину отрезка c = (a + b) / 2 и вычисляем значение функции в этой точке: f(c). Если f(c) = 0, корень найден точно. Если нет, мы проверяем знаки: если f(a) и f(c) имеют разные знаки, значит корень находится на отрезке [a, c]. Если нет — на отрезке [c, b]. Мы заменяем границы отрезка и повторяем процесс. На каждом шаге длина интервала неопределенности уменьшается ровно в два раза. Процесс продолжается до тех пор, пока длина отрезка не станет меньше заданной погрешности эпсилон. Главное преимущество дихотомии — абсолютная гарантия сходимости для любой непрерывной функции.

Метод Ньютона (метод касательных)

Если метод дихотомии сходится линейно, то метод Ньютона обеспечивает гораздо более высокую, квадратичную скорость сходимости. Это означает, что количество верных значащих цифр в ответе удваивается на каждой итерации. Геометрический смысл метода Ньютона заключается в том, что мы заменяем нелинейную функцию касательной прямой, проведенной в точке текущего приближения, и находим точку пересечения этой касательной с осью X.

Формула итерационного процесса Ньютона выглядит следующим образом: x_new = x_old - f(x_old) / f_prime(x_old), где f_prime — это производная функции. Несмотря на огромную скорость, метод имеет ряд существенных недостатков. Во-первых, он требует вычисления производной на каждом шаге. Во-вторых, он не гарантирует сходимости при плохом выборе начального приближения. Если начальная точка выбрана слишком далеко от истинного корня или если производная в точке близка к нулю (касательная почти параллельна оси X), метод может «улететь» в бесконечность или зациклиться. Поэтому на практике часто комбинируют методы: сначала используют надежную дихотомию для сближения с корнем, а затем быстрый метод Ньютона для финального уточнения.