Уточнение корней. 
Информатика.

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

Рассмотрим некоторые итерационные методы решения нелинейных уравнений.

Метод деления отрезка пополам (метод бисекций)

Пусть дано уравнение/(х) = 0. Допустим, удалось найти такой отрезок [а, Ь], на котором расположено значение корня т. е. а < ^ < Ь. В качестве начального приближения корня х₀ (рис. 2.5) принимают середину отрезка х₀ = (а + Ь) / 2. Далее исследуют значения функции: если /(х₀) = 0, то х₀ — корень уравнения, т. е. ^=х₀. Если Дх₀) * 0, то выбирают одну из половин отрезка [а, х₀] или [х₀, />, на концах которой/(х) имеет противоположные знаки, т. е. содержит искомый корень, поэтому его принимают в качестве нового отрезка [х₀, Ь]. Вторую половину отрезка, на концах которого знак функции /(х) нс меняется, отбрасывают: в данном случае [а, х₀]. Отрезок [х₀, Ь] вновь делят пополам. Следующее приближение: Х] = (хо+ b) / 2. Вновь исследуют функцию /(х) на концах отрезка и отбрасывают отрезок [xi, Ь], т. к. ДхД > 0 и f{b) > 0.

Рис. 2.5. Метод деления отрезка пополам

Отрезок [х₀, х,], на концах которого функция имеет противоположные знаки j{x) > 0,/(х₀) < 0, вновь делят пополам, получают новое приближение корня х₂=(х₀ + х,)/2 и т. д. Итерационный процесс продолжают до тех пор, пока длина отрезка после п-й итерации не станет меньше некоторого заданного малого числа е (погрешности), т. е.

Тогда за искомое значение корня принимают полученное приближение х": ?,=х" и говорят, что решение уравнения найдено с точностью е. Пример 2.3. Найти корни уравнения.

с точностью 8 = 0,1.

В результате процедуры отделения корней было получено три отрезка, содержащих действительные корни. Выберем отрезок [-3,-1] и определим корень уравнения, используя метод деления отрезка пополам.

Последовательность решения. Определяем знак функции на концах отрезка [-3,-1]:

Делим данный отрезок пополам:

Значение функции в этой точке:

У (—2) = —8 + 12 + 2 = 6.

имеет положительное значение. Отбрасываем половину отрезка, на концах которого функция Дх) имеет положительные знаки, а именно — отрезок [-2, -1]. Полученный отрезок [-3, -2] делим пополам:

• /(-2,5) > 0, следовательно, отбрасываем отрезок [-2,5; -2], а отрезок [-3; -2,5] делим пополам:

• /(-2,75) < 0, следовательно, рассматриваем отрезок [-2,75; -2,5]:

• /(-2,625) < 0, — отрезок [-2,625; -2,5]:

• Д—2,563) > 0. Следовательно, вновь полученный отрезок будет Проверим условие окончания расчетов по формуле (2.3*):

Таким образом, за искомое значение корня принимают значение:

На рис. 2.6 представлена блок-схема определения корня уравнения (2.1) методом деления отрезка пополам (бисекций).

Рис. 2.6. Блок-схема алгоритма метода деления отрезка пополам 2.2.2. Метод Ньютона (метод касательных).

Если известно начальное приближение к корню уравнения /(д') = 0, то эффективным методом уточнения корней является метод Ньютона (метод касательных) [2−10].

Сформулируем достаточные условия сходимости метода Ньютона.

Пусть функцияУ (д') имеет первую и вторую производные на отрезке [а, Ь]. Выполняется условие знакопеременности функции: /(я) • /(&)< 0, а производные f'(x), f" (x) сохраняют знак на отрезке [а, Ь]. Тогда, исходя из начального приближения х₀е[а, Щ, которое удовлетворяет неравенству J{x)? f" (x)>0, можно построить следующую итерационную последовательность:

которая сходится к единственному на отрезке [а, 6] решению ?, уравненияУ (х) = 0.

В данном методе процесс поиска корня состоит в том, что в качестве приближений к корню принимаются значения х₀, Х, х₂ ??? точек пересечения касательной к кривой у=/(х) с осью абсцисс. Таким образом, геометрически метод Ньютона эквивалентен замене небольшой дуги кривой У⁼Л^Х) касательной. При этом необязательно задавать отрезок [а, 6], содержащий корень уравнения _Дх) = 0, а достаточно найти некоторое начальное приближение корня х=хо (рис. 2.7).

Рис. 2.7.

В качестве начального приближения выбирается х₀=а, для которого выполняется условие /(х₀) •/" (*о) > 0. Проведем касательную в точке Ло[хо,_Дхо)]. Первым приближением корня будет точка пересечения этой касательной с осью абсцисс х,. Через точку А[хьДхО] вновь проводим касательную, точка пересечения которой с осью Ох даст нам второе приближение корня х₂ и т. д.

На рис. 2.8 приведены возможные варианты выбора в качестве начального приближения правого или левого конца отрезка.

Условие выбора:/{х) • /" (х) > 0.

Вывод формулы Ньютона. Запишем уравнение касательной, проведенной к кривой y=j{x) в точке Ло[х₀,_Дх₀)]:

Рис. 2.8.

Найдем отсюда следующее приближение корня.

Принимаем х=х (у=0), тогда.

Аналогично найдем следующие приближения корня, как точки пересечения с осью ОХ касательных, проведенных в точках А, А₂ и т. д. Формула Ньютона для (п+ 1)-го приближения будет иметь следующий вид:

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

При мер 2.4. Найти корни уравнения

На этапе отделения корней уравнения было выделено три интервала, на которых функция меняет знак, следовательно, уравнение имеет три действительных корня. Вычислим по методу Ньютона (касательных) значение корня на отрезке [4, 6]. Выберем начальное приближение таким образом, чтобы выполнялось условие Дх₀) •/" (*о) > 0.

Запишем первую и вторую производные функцииДт):

Вычислим значения Д, т₀) и f" (xо).

При

Следовательно, за начальное приближение можно принимать, т₀ = 6. Найдем корень уравнения по Формуле (2.4) с точностью е = 0,001:

Таким образом, корнем данного уравнения с точностью е = 0,001 примем значение х=5,000.

Проверяем по формуле (2.7*) условие окончания вычислений:

Блок-схема алгоритма метода Ньютона приведена на рис. 2.9.

Рис. 2.9. Блок-схема метода Ньютона:

Хо — начальное приближение:

X— последовательное приближение (значение) корня