5. Численное решение алгебраических и трансцендентных уравнений

Метод половинного деления

Б лок-схема алгоритма метода половинного деления представлена на рис. 1. Он состоит из следующих операций. Сначала вычисляются значения функций в точках, расположенных через равные интервалы на оси х. Это делается до тех пор, пока не будут найдены два последовательных значения функции f(х_п) и f(x_n+1), имеющие противоположные знаки. (Напомним, если функция непрерывна, изменение знака указывает на существование корня.)

З атем по формуле

вычисляется среднее значение х в интервале значений [x_n, х_п+1] и находится значение функции f(х_ср). Если знак f(х_ср) совпадает со знаком f(х_п), то в дальнейшем вместо f(х_п) используется f(х_ср). Если же f(х_ср) имеет знак, противоположный знаку f(x_n), т. е. ее знак совпадает со знаком f(х_п+1), то на f(x_ср) заменяется это значение функции. В результате интервал, в котором заключено значение корня, сужается. Если f(х_ср) достаточно близко к нулю, процесс заканчивается , в противном случае он продолжается. На рис. 2 эта процедура показана графически. Хотя метод половинного деления не обладает высокой вычислительной эффективностью, с увеличением числа итераций он обеспечивает получение все более точного приближенного значения корня. После того как впервые найден интервал, в котором заключен корень, его ширина после N итераций убывает в 2^N раза.

Метод хорд.

В основе этого метода лежит линейная интерполяция по двум значениям функции, имеющим противоположные знаки. При отыскании корня этот метод нередко обеспечивает более быструю сходимость, чем предыдущий. Блок-схема алгоритма метода хорд дана на рис. 3. Счет ведется следующим образом. Сначала определяются значения функции в точках, расположенных на оси х через равные интервалы. Это делается до тех пор, пока не будет найдена пара последовательных значений функции f(х_п) и f(х_п+1), имеющих противоположные знаки. Прямая, проведенная через эти две точки, пересекает ось х при значении

Э то значение аргумента используется для определения значения функции f(x*), которое сравнивается со значениями функций f(x_n) и f(x_n+l) и в дальнейшем используется вместо того из них, с которым оно совпадает по знаку. Если значение f(x*) недостаточно близко к нулю, то вся процедура повторяется до тех пор, пока не будет достигнута необходимая степень сходимости. На рис. 4 процесс решения показан графически.

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

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

Ч лены, содержащие h во второй и более высоких степенях, отбрасываются; используется соотношение x_n+h=x_n+1. Предполагается, что переход от х_n к x_n+1 приближает значение функции к нулю так, что f(xn+h)=0. Тогда

x_n+1=x_n-f(x_n)/f’(x_n)

З начение x_n+1 соответствует точке, в которой касательная к кривой в точке х_п пересекает ось х. Так как кривая f(x) отлична от прямой, то значение функции f(x_n+1) скорее всего не будет в точности равно нулю. Поэтому вся процедура повторяется, причем вместо х_п используется х_п+1. Счет прекращается по достижении достаточно малого значения f(x_n+l). На рис. 6 процесс решения уравнения методом Ньютона показан графически. Совершенно ясно, что быстрота сходимости в большой мере зависит от удачного выбора исходной точки. Если в процессе итераций тангенс угла наклона касательной f' (х) обращается в нуль, то применение метода осложняется. Можно также показать, что в случае бесконечно большого f"(x) метод также не будет достаточно эффективным. Так как условие кратности корней имеет вид f(x) = f' (х)= 0, то в этом случае метод Ньютона не обеспечивает сходимость. Отметим, что иногда используется другой способ контроля сходимости, состоящий в сравнении х_п и x_n+l.