Уточнение корней

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

Итерационный процесссостоит в последовательном шаг за шагом уточнении начального приближения x₀ искомого корня. Каждый шаг такого метода называется итерацией.

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

Если эти значения с увеличением n приближаются к истинному значению корня x*, то говорят, что итерационный процесс сходится.

3.3.1.3.1. Метод половинного деления (дихотомии, бисекции)

Пусть дано уравнение

(3.17)

где функция непрерывна и монотонна на отрезке и имеет на концах отрезка разные знаки:

(3.18)

Требуется найти корень уравнения (3.17) с точностью до График функции представлен на рис. 3.5.

Рассмотрим суть и этапы реализации метода половинного деления.

1) Отрезок делим пополам и определяем середину отрезка:

(3.19)

2) Вычисляем значение функции в точке Если , то является корнем уравнения. Если то поиск корня продолжается на одном из двух полученных отрезков – или .Следует выбрать тот отрезок, на концах которого функция принимает значения противоположных знаков. В данном случае (см. рис. 3.5) выбираем отрезок , так как для него выполняется условие: Для того чтобы сохранить в дальнейших расчетах единое обозначение текущего отрезка, на котором ведется поиск корня на данном шаге вычислений, необходимо параметру b присвоить новое значение : b = . С точки зрения геометрической интерпретации (см. рис. 3.5) это означает, что правая граница исходного отрезка точка b переносится в точку а оставшаяся за пределами точки часть графика дальше не рассматривается.

3) Новый отрезок снова делим пополам:

(3.20)

4) Вычисляем и проводим анализ двух вновь полученных отрезков – и .Выбираем тот из них, для которого выполняется условие противоположности знаков функции в граничных точках.

5) Процесс деления пополам текущего отрезка продолжаем до тех пор, пока очередной отрезок не будет удовлетворять условию:

(3.21)

где ε – требуемая точность расчета.

За приближенное значение корня x*принимаем значение середины последнего отрезка , т. е.

x* = . (3.22)

При этом погрешность вычисления корня не будет превышать

, где n – количество произведенных делений отрезков (количество итераций).

Алгоритм метода половинного деления, представлен на рис. 3.6.

В блоке 2 (рис. 3.6) задается начальное значение счетчика n количества итераций (делений отрезка пополам). Блоки 6 – 8 реализуют выбор того из двух отрезков, на котором следует продолжать поиск корня и соответственно корректировку границы (b – при выборе левого отрезка, a – правого).

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

Метод устойчив к ошибкам округления. Однако скорость сходимости его меньше, чем у методов, которые будут рассмотрены ниже.

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

Требуется решить уравнение , причем и определены, непрерывны и сохраняют постоянные знаки на отрезке

Рассмотрим геометрическую интерпретацию метода Ньютона (рис. 3.7).

1) Выбираем – начальное приближение корня x* При этом надо придерживаться следующего правила: за начальное приближение корня следует принять тот конец отрезка , в котором знак функции совпадает со знаком второй производной, т.е. выполняется условие:

(3.23)

Этоусловие сходимости метода Ньютона.

Основываясь на свойствах данной функции (см. рис. 3.4), делаем вывод о том, что условие сходимости выполняется для точки , поэтому принимаем

2) Вычисляем значение функции . Проводим касательную к кривой в точке . Абсцисса точки пересечения касательной с осью Оx принимается за новое (первое) приближение корня x₁.

Известно, что уравнение касательной, проведенной в точке B₀ с координатами (x_0,f(x₀)) к кривой функции f(x), имеет вид:

(3.24)

где x, y – текущие координаты точки, лежащей на касательной.

Для точки x₁ сделаем подстановку в уравнение касательной (3.24):

x = x₁; (3.25)

(3.26)

получаем:

. (3.27)

Обе части уравнения (3.27) делим на и выражаем x₁:

(3.28)

3) Вычисляем значение функции в точке x₁, проводим касательную к кривой в точке Абсцисса точки пересечения касательной с осью Оx представляет собой второе приближение корня x₂:

(3.29)

4) Продолжаем последовательно проводить касательные и определять точки их пересечения с осью Оx. Тогда для текущего k-го приближения корня итерационный процесс реализуется рекуррентной формулой:

(3.30)

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

(3.31)

Алгоритм, реализующий метод Ньютона, представлен на рис. 3.8. Блок 4 реализует проверку условия сходимости метода и выбор значения начального приближения (блоки 5, 6), блок 10 реализует подсчет количества итераций, 11 – вычисление текущего приближения корня через предыдущее приближение.

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

Неудачно выбранное начальное приближение может привести к расходимости метода (см. рис. 3.7): представим, что за начальное приближение x₀принят левый конец отрезка a, касательная, проведенная в точке А₀, пересекает ось Оx за пределами заданного отрезка [a,b]. Таким образом, получили первое приближение к корню ‹x₁›, еще дальше отстоящее от искомого значения корня x*, чем нулевое приближение .

3.3.1.3.3. Метод итерации (метод последовательных приближений)

Пусть требуется решить уравнение . Преобразуем его к виду:

(3.32)

На заданном отрезке выбираем начальное приближение корня x₀.

Подставляем его в правую часть уравнения (3.32) и получаем первое приближение корня x₁:

(3.33)

Аналогичным образом определим второе приближение корня:

(3.34)

Продолжая этот процесс далее, получаем последовательность чисел , определяемых соотношением:

(3.35)

Итерационные вычисления продолжают до тех пор, пока для двух последовательных приближений и не выполнится условие:

(3.36)

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

для , (3.37)

причем скорость сходимости будет тем больше, чем меньше число q.

Рассмотрим геометрическую интерпретацию метода итерации. Исходное уравнение приводим к виду:

(3.38)

Строим графики функций y = x и y = . Абсцисса точки пересечения этих графиков и будет являться корнем x* уравнения f(x) = 0.

Рассмотрим несколько возможных вариантов итерационного процесса.

В а р и а н т 1. (рис. 3.9).

Задаем начальное приближение . Определяем . Через точку А₀ с координатами проводим горизонтальную линию до пересечения с прямой y = x в точке В₁. Через точку В₁ проводим вертикальную линию, пересекающую кривую y = и ось Оx. Точка пересечения этой линии с осью Оx даст первое приближение корня x₁, а точка пересечения ее с кривой y = – точку А₁ с координатами . Через точку А₁ проводим горизонтальную линию до пересечения с прямой y = x (точка В₂). Вертикальная линия, проведенная через точку В₂, пересекая ось Оx, даст второе приближение корня x₂, а также определит на кривой y = точку А₂с коор
динатами Продолжая действия по такой же схеме, получаем на оси Оx последовательность значений , приближающихся (сходящихся) к истинному значению корня x*. Причем все последовательные приближения находятся с одной стороны от корня x*. Такая сходимость называется монотонной или односторонней.

В а р и а н т 2. (рис. 3.10). Итерационный процесс расходится.

В а р и а н т 3. (рис. 3.11). Итерационный процесс сходится. Процесс сходимости носит колебательный характер (двусторонняя сходимость).

В а р и а н т 4. (рис. 3.12). Итерационный процесс расходится.

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

П р и м е р 16. Пусть требуется определить корень уравнения

4x³ – 15x + 7 = 0 (3.39)

на отрезке [0, 1].

С п о с о б 1 – прибавляем к обеим частям исходного уравнения x:

(4x³ – 15x + 7) + x = x, (3.40)

получаем:

4x³ – 14x + 7 = x. (3.41)

Следовательно,

= 4x³ – 14x + 7. (3.42)

Проверяем, выполняется ли условие сходимости на отрезке [0, 1]:

= 12x²– 14, (3.43)

= | –14 | > 1, (3.44)

= | 12–14 | >1 . (3.45)

Условие сходимости не выполняется, следовательно, функция в таком виде непригодна.

С п о с о б 2 – выражаем x из исходного уравнения:

– 15x = – 7 – 4x³, (3.46)

получаем:

(3.47)

Следовательно,

. (3.48)

Проверяем, выполняется ли условие сходимости на отрезке [0, 1]:

= |0|<1; (3.49)

< 1. (3.50)

Условие сходимости выполняется на заданном отрезке, значит, можно воспользоваться функцией для реализации метода итерации.

П р и м е р 17. Пусть требуется определить корень уравнения

(3.51)

на отрезке [0, 1].

С п о с о б 3 – представляем исходное уравнение в виде:

(3.52)

и логарифмируем обе части этого уравнения:

, (3.53)

получаем:

x = . (3.54)

Следовательно,

= , (3.55)

= . (3.56)

Проверяем, выполняется ли условие сходимости на отрезке [0, 1]:

= |-0,5| < 1; (3.57)

= |-0,269| < 1. (3.58)

Условие сходимости выполняется.

С п о с о б 4 – для некоторых уравнений рассмотренные выше способы преобразования не дают желаемых результатов. В таких случаях рекомендуется применить следующий прием, гарантирующий выполнение условия сходимости метода итерации.

Левую и правую части исходного уравнения f(x) = 0 умножаем на произвольную константу λ и прибавляем к обеим частям неизвестное x:

x = x + λf(x), (3.59)

тогда

= x + λf(x). (3.60)