4.7. Справочная информация

Как известно, далеко не всякое алгебраическое уравнение

может быть решено аналитически. Это относится к большинству трансцендентных уравнений и к алгебраическим уравнениям выше четвертого порядка. Однако точное решение уравнений на практике часто и не требуется. Чтобы считать задачу решенной, достаточно бывает отыскать значения корней с требуемой степенью точности. Для получения таких решений разработаны численные методы.

Р

Рис. 1

ешение нелинейных уравнений осуществляется в два этапа. На первом этапе производится отделение корней, то есть поиск достаточно малых отрезков, каждый из которых содержит единственный корень уравнения. Для этого используется график функции y = f(x), точки пересечения которого с осью абсцисс являются корнями исходного уравнения. Случай, когда корнем уравнения является точка касания графика и оси абсцисс здесь не рассматривается. Это позволяет выделить отрезки [a,b], содержащие только один корень (см. рис 1). При этом для непрерывной функции f(x) будет выполняться неравенство f(a) f(b) < 0.

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

Методы сужения отрезка [a, b], к которым относятся метод хорд, метод половинного деления и др., не имеют ограничений на функцию f(x), присущих методам последовательного уточнения.

Метод половинного деления (метод бисекций)

Работа метода иллюстрируется на рис.2. Отрезок изоляции [a, b] корня делится пополам x₀ = (a + b)/2 и в полученной точке вычисляется значение функции. Если f(x₀) = 0, то корень найден и расчеты прекращают. В противном случае выбирается новый отрезок, содержащий корень уравнения, из отрезков [a, x₀] и [x₀, b]. На концах искомого отрезка функция f(x) должна иметь значения разного знака. Для этого проверяется условие

f(a)f(x₀) < 0.

П

Рис. 2 Рис. 3

ри его выполнении в качестве нового отрезка принимается отрезок [a, x₀], в противном случае - [x₀, b]. Процесс сужения отрезка продолжается до тех пор, пока его длина не станет меньше наперед заданного значения абсолютной погрешности  или не будет выполнено условие по относительной погрешности определения корня. При этом за значение корня принимается либо одна из границ суженного отрезка [a, b], либо его середина.

Метод хорд

Идея метода состоит в замене функции f(x) внутри отрезка [a, b] линейной функцией. Точка пересечения x₀ графика линейной функции и оси абсцисс принимается за значение одной из границ нового отрезка изоляции корня, который выбирается аналогично методу половинного деления. Далее процесс повторяется и находится x₁ - точка пересечения графика линейной функции нового отрезка с осью абсцисс. Иллюстрацией этого алгоритма является рис.3.

Процесс поиска корня продолжается до тех пор, пока не будет выполнено условие, задающее погрешность его определения.

Для расчета на каждом шаге координаты точки пересечения графика линейной функции и оси абсцисс используются выражения вида:

или

.

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

Метод простых итераций

Метод основывается на приведении исходного уравнения к форме

Это преобразование может быть выполнено многими способами.

Например, уравнение

может быть преобразовано как x= e^-x или x = ln |1/x|.

Далее процесс уточнения корня строится по следующей итерационной схеме

……………

……………

где x₀ - первоначальное приближенное значение корня на отрезке [a, b].

Если последовательность значений x_k (k = 0, 1, 2, ...) имеет конечный предел, то итерационный процесс сходится к точному значению корня x^* за бесконечно большое число шагов. Поэтому итерации завершают при выполнении одного из условий:

или ,

г

Рис. 4 Рис. 5

де  - требуемая абсолютная или относительная погрешность определения корня, соответственно. Однако, может случиться так, что последовательность значений x_k (k = 0, 1, 2, ...) не имеет предела. В этом случае метод расходится, и описанная итерационная схема не может быть применена для решения уравнения.

Процесс уточнения корня уравнения методом простых итераций может быть проиллюстрирован графически.

Как видно на рис.4, для выбранной на отрезке [a, b] начальной точки x₀ вычисляется значение функции  (x₀). Абсцисса этой точки с помощью графика функции y = x преобразуется в новое приближение переменной x₁. Далее процесс повторяется, и находятся значения x₂, x₃, ..., x_k,... до тех пор, пока не будет выполнено условие завершения итерационного процесса по заданной погрешности вычисления корня . В данном случае итерационный процесс сходится и заданная погрешность вычисления корня достижима. На рис.5 показана ситуация, когда метод итераций расходится. Каждое новое значение x_k отстоит все дальше от точного решения уравнения x^* и заданная погрешность вычисления недостижима. Такая ситуация характерна для неудачного преобразования уравнения f(x) = 0 к уравнению x =  (x).

В методе итераций рекомендуется преобразовывать исходное уравнение, основываясь на теореме о его сходимости, которая гласит: если во всех точках отрезка изоляции [a,b] корня уравнения x =  (x) функция  (x) удовлетворяет условию |(x)| < 1, то итерационный процесс сходится к точному значению корня x^* для любого x₀ из отрезка изоляции.

Исходя из вышесказанного, можно указать еще один способ преобразования исходного уравнения к форме, требуемой методом итераций. Исходное уравнение f(x) = 0 равносильно уравнению x = x + f(x), где  - отличная от нуля произвольная постоянная. Эта постоянная выбирается из условия сходимости метода |(x)| < 1, считая  (x) = x +  f(x).

В этом случае условие сходимости переписывается в виде:

|1+ f(x)| < 1 ,

и условие на допустимое значение параметра  приобретает вид

-2< f(x)<0 ,

что дает весьма широкий интервал значений. Это позволяет использовать приближенную оценку производной f(x) в окрестности искомого корня, которую можно получать, например, из построенного графика функции f(x). Очевидно, что для каждого корня уравнения следует формировать соответствующую ему функцию  (x) на основе подобранного значения параметра . Удобно, например, выбирать его в середине интервала допустимых значений:

=-1/ f(x) .

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

В данном методе каждое новое приближение к значению корня уравнения f(x) = 0 ищется по следующей итерационной схеме

Рис. 4

………………….

………………….

где x₀ - первоначальное приближенное значение корня на отрезке [a,b].

Графическая интерпретация работы метода Ньютона представлена на рис.4. Из точки на кривой y = f(x), имеющей абсциссу x₀, проводится касательная до пересечения с осью 0x и абсцисса точки пересечения принимается за новое приближение x₁ значения корня уравнения f(x) = 0. В случае сходимости последовательности вычисляемых значений x₀, x₁, ..., x_k,... процесс продолжается до тех пор, пока не выполнится условие его завершения по заданной погрешности определения корня .

Чтобы последовательность приближений x₀, x₁, ..., x_k, ... сходилась к значению корня x^*, необходимо и достаточно выполнение условий следующей теоремы. Если в окрестности корня x^* функция f(x) имеет непрерывные производные f(x) и f(x), для которых справедливо неравенство

,

то итерационный процесс сходится к точному значению корня для любого x₀ из [a, b].