Решение нелинейных уравнений. Общий вид уравнения

Общий вид уравнения

Рассмотрим уравнения вида f(x)=0. Решить уравнение это значит найти такое x, при котором уравнение превращается в тождество. В общем случае уравнение может иметь 0; 1; 2;...∞ корней. Эти уравнения не всегда могут быть решены аналитически. Например, если решения уравнения вида ax²+bx+c=0 могут быть найдены по формулам Виета, то, например, решить уравнение типа x=1-sinx в элементарных функциях уже не удается. В этих случаях применяют различные численные методы решения нелинейных уравнений.
Таким образом, при решении алгебраических и трансцендентных уравнений, встречающихся на практике, не всегда удается найти точное решение. Поэтому приходится применять различные приближенные способы определения корней. В общей постановке задачи обычно требуют непрерывность функции f(x), корни которой ищутся с заданной точностью. Решение при этом разбивается на два этапа:
1.ЛОКАЛИЗАЦИЯ корней, т.е. выделение непересекающихся отрезков, каждый из которых содержит по одному корню.
2.УТОЧНЕНИЕ корней, т.е. вычисление корня на каждом из отрезков с нужной точностью.
Первая часть задачи обычно решается либо с использованием примерного графика функции, либо с помощью исследования знака функции и, как правило, не включается в стандартный курс вычислительной математики.
Рассмотрим следующий простейший пример: определить количество и приближенное расположение корней уравнения sinx−0,2x=0. Переписывая это выражение в виде sinx=0,2x и учитывая, что значения функции y=sinx лежат между −1 и 1, находим, что корни уравнения могут быть только на отрезке [−5,5]. Ясно, что один из корней - это x=0. Если же на отрезке [−5,5] нарисовать график функций y₁(x)= sinx и y₂(x)=0,2x, то легко видеть, что точки их пересечения (а это и есть корни уравнения) расположены на отрезках [−3,−2] и [2,3]. Таким образом, уравнение исходное уравнение sinx−0,2x=0 имеет 3 различных корня.
Рассмотрим уравнения вида F(x)=0. Решить уравнение это значит найти такое x, при котором уравнение превращается в тождество. В общем случае уравнение может иметь 0; 1; 2;... корней. Эти уравнения не всегда могут быть решены аналитически. Например, если решения уравнения вида ax²+bx+c=0 могут быть найдены по формулам Виета, то, например, решить уравнение типа x=1−sinx в элементарных функциях уже не удается. В этих случаях применяют различные численные методы решения нелинейных уравнений.
Всюду далее будем считать, что уравнение F(X)=0 задано на отрезке [a,b], на котором расположен ровно один его корень, и исследовать решение второй части задачи − уточнение корней.
Рассмотрим несколько методов решения нелинейных уравнений, которые позволяют находить один корень на заданном интервале [a,b]. При этом будем предполагать, что на заданном интервале существует только один корень.

Простейшие методы

11.3.2.1. Метод перебора
При решении нелинейного уравнения вида F(x)=0 методом перебора задаются начальное значение аргумента x=a и шаг h, который при этом определяет и точность нахождения корней нелинейного уравнения. Пока выполняется условие F(x)*F(x+h)>0 аргумент x увеличиваем на шаг h (x=x+h). Если произведение F(x)*F(x+h) становится отрицательным, то на интервале [x,x+h] существует решение уравнения. Метод непроизводителен, требует огромного числа ненужных вычислений значений фукнции в промежуточных точках, однако, с другой стороны, он применим и для неунимодальных функций, легок в программровании и не требует знания правой границы интервала b.

Рис. 11.15. Иллюстрация метода перебора

11.3.2.2. Метод деления отрезка пополам
Этот метод в литературе иногда называют также методом половинного деления или методом бисекции. Однако это может приводить к терминологической путанице, поскольку аналогичные методы используются и при минимизации функции F(x) на отрезке [a,b] (см. п. 11.4.3). По этой причине будем использовать термин "метод деления отрезка пополам", когда речь идет о поиске корней уравнения F(x)=0, и "метод половинного деления", когда речь идет о минимизации то же функции на отрезке [a,b].
При решении нелинейного уравнения методом деления отрезка пополам задаются интервал [a,b], на котором существует только одно решение, и желаемая точность ε. Затем определяется середина интервала с=(а+b)/2 и вычисляется значение функции в ней: F(c). Если F(c)=0, решение найдено. Если нет, то выбирается та из половин [a,(a+b)/2] и [(a+b)/2,b] отрезка [a,b], на концах которой функция F(x) имеет противоположные знаки. С этой целью проверяется условие F(a)·F(c)<0. Если указанное условие выполняется, то правую границу интервала b переносим в среднюю точку с (b=c). Если условие не выполняется, то в среднюю точку переносим левую границу(a=c). Деление отрезка пополам продолжается пока |b−a|>ε. Для оценки требуемого количества итераций можно использовать формулу 0≤|x_n−x*|<(b−a)/2ⁿ. Метод деления отрезка пополам всегда сходится, хотя и медленно.
Метод деления отрезка пополам проиллюстрирован на рис. 11.16. Пусть для определенности F(a)<0 и F(b)>0. Начальное приближение корня c₀=(a+b)/2. Поскольку в рассматриваемом случае F(c₀)<0, то корень с∈[c₀,b], т.е. a₁=c₀, b₁=b. Следующее приближение c₁=(c₀+b)/2. На этот раз отбрасываем отрезок [c₁,b], поскольку F(c₁)>0 и F(b)>0. Таким образом, с∈[c₀,c₁], a₂=c₀, b₂=c₁. Аналогично находим другие приближения c₂=(c₀+c₁)/2 и т.д.

Рис. 11.16. Иллюстрация метода деления отрезка пополам

11.3.2.3. Метод хорд
При решении нелинейного уравнения методом хорд задаются интервал [a,b], на котором существует только одно решение, и точность ε. Затем через две точки с координатами (a,F(a)) и (b,F(b)) проводим отрезок прямой линии (хорду) и определяем точку пересечения этой линии с осью абсцисс (точка c). Уравнение хорды АВ (рис. 11.16) имеет вид: (y − F(a))/(F(b) − F(a)) = (x − a)/(b − a). Для определения значения с можно использовать формулу c = a + (b−a)·|F(a)/[F(b)−F(a)]|. Если при этом F(a)·F(c)<0, то правую границу интервала переносим в точку с (b=c). Если указанное условие не выполняется, то в точку c переносится левая граница интервала (а=с).
В отличие от метода деления отрезка пополам, в методе хорд условие окончания итераций вида |b−a|<ε неприменимо. Вместо этого рекомендуется использовать условие вида |c⁽ⁱ⁺¹⁾ − c⁽ⁱ⁾|<ε. Возможно также использование критерия |F(c)|< ε.

Рис. 11.17. Иллюстрация метода хорд

Метод деления отрезка отрезка пополам и метод хорд не требуют знания дполнительной информации о функции F(x), в частности, не требуется, чтобы функция была гладкой. Для применимости этих методов достаточно непрерывности самой функции. Более сложные методы требуют дифференцируемости функции F(x), но зато они быстрее сходятся.

11.3.2.4. Метод итераций
При решении нелинейного уравнения F(x)=0 методом итераций воспользуемся записью этого уравнения в виде x=f(x). Такая запись возможна всегда, например, если принять, что f(x)=x+F(x) или x=x+F(x). При решении уравнения x=f(x) задаются начальное значение аргумента x₀ и точность ε. Первое приближение решения x₁ находим из выражения x₁=f(x₀), второе − из x₂=f(x₂) и т.д. В общем случае i+1 приближение найдем по формуле x_i+1=f(x_i), то есть
x_i+1 = x_i + F(x_i)
Указанную процедуру повторяем пока |x_i+1-x_i|>ε. Условие сходимости метода итераций |f'(x)|<1. Очевидно, что это условие выполняется далеко не всегда. По этой причине меnод итераций иногда модифицруют, а указанную выше итерационную формулу относят к методы простых итераций.
Рассмотрим один из возможных вариантов модификации метода простых итераций
x_i+1 = x_i − λF(x_i)
где λ − параметр метода. Величина λ подбирается экспериментальным путем из условия достижения сходимости. Если выбрать значение λ достаточно малым, то можно добиться выполнения условия сходимости |f'(x)|=|λF'(x)|<1.
В некоторых случаях величину параметра метода λ делают зависящей от номера итерации и рассмтрвиают следующую итерационную схему:
x_i+1 = x_i − λ_iF(x_i)

Метод Ньютона

Знаменитый метод Ньютона является одним из наиболее эффективных методов решения самых разнообразных нелинейных задач.
Раскладывая функцию F(x) в ряд Тейлора вблизи точки x=x_i, получим, ограничиваясь первым членом разложения
F(x_i)+F´(x_i)·(x_i+1–x_i)=0
откуда
x_i+1 = x_i − F(x_i) ⁄ F´(x_i), i=0,1,2,...
Условие сходимости метода FF´´>0. На практике иногда избегают дифференцирования функции F(x), заменяя значение ее производной тем или иным приближенным выражением.
Геометрическая интерпретация метода Ньютона представлена на рис. 11.17. Уравнение касательной, проведенной к кривой y=F(x)в точке M₀ с координатами с₀ и F(c₀), имеет вид
y − F(c₀) = F'(c₀)·(x − c₀)
Отсюда найдем следующее приближение корня c₁ как абсциссу точки пересечения касательной с осью x (y=0):
c₁ = c₀ − F(c₀)/F'(c₀)
Аналогично могут быть найдены и следующие приближения, в результате чего реализуется итерационная процедура метода Ньютона:
c_i+1=c_i−F(c_i)⁄F´(c_i)
Условие окончания итерационного процесса, как и в методе хорд, следующие: |c_i+1 − c_i|<ε или |F(c_i)|< ε.

Рис. 11.18. Иллюстрация метода Ньютона

Метод Ньютона сходится намного быстрее, чем методы деления отрезка пополам и метод хорд. Кроме того, для его реализации нет необходимости в определении границ интервала поиска [a,b], − достаточно задать начальное приближение c₀.