Уточнение корней уравнения в окрестности начального приближения. Сканирование с переменным шагом

В отличие от уточнения корня на доверительном отрезке, в данном случае исходными данными помимо функции f (x) и необходимой точности решения e является только одна начальная приближенная точка x ₀, достаточно близкая к искомому корню уравнения x*. Требуется построить последовательность приближенных решений { x_i } (i= 1,2,...), сходящуюся к точному корню уравнения x*, который будет ближайшим к начальному приближению x ₀. Корень x* будет ближайшим к x ₀ сверху, если функция f (x)>0 и убывает в точке x ₀, и, наоборот, если функция f (x)<0 и возрастает в точке x ₀. В других случаях искомый корень x* будет ближайшим к x ₀ снизу.

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

1) сканирование с переменным шагом,

2) метод простой итерации,

3) метод Ньютона (метод касательных).

У метода 1) сканирования с переменным шагом точность определения корня задается длиной итогового доверительного отрезка e. У методов
простой итерации (2) и касательных (3) условием завершение итерационного процесса является, как и в методе хорд, уменьшение величины приращения значения приближенных значений корня до заданной предельной величины e: | x_i - x_{i - 1}| < e.

Методы 1) сканирования с переменным шагом и 2) простой итерации имеют нулевой порядок - в них используется только расчет значений целевой функции f (x). Метод касательных 3) имеет первый порядок, поскольку использует также первую производную f¢ (x).

8.5.1. Сканирование с переменным шагом

Поиск корня в окрестностиприближенной точки x ₀ по методу сканирования с переменным шагом заключается в начальном просмотре (сканировании на первой итерации) значений функции f (x) в направлении точного значения корня x* с крупным шагом h ₁ в результате которого определяется доверительный отрезок [ a ₁, b ₁] длины h ₁, внутри которого находится x*. Затем шаг сканирования уменьшается в заранее заданное число раз k (k >1) и просмотр значений функции f (x) производится, начиная с последней точки, в обратном направлении (h ₂:= - h ₁ /k) с определением доверительного отрезка [ a ₂, b ₂] сокращенной длины h ₂. Процесс уменьшения и смены направления сканирования (h_i:= - h_{i -1} /k) продолжается до тех пор, пока корень x* не будет локализован на доверительном отрезке длины (b_i - a_i) = h_i, не превышающей заданной точности e. Длина шага на последней итерации равна модулю ï h_i ï= ï h ₀ï /k^{i- 1}.

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

После задания h ₁ и k выполнение метода не учитывает особенности функции f (x). Как и в методе половинного деления, при случайном попадании в корень имеется возможность неправильного определения знака функции f (x) в очередном узле при малом значении ï f (x)ï и потери соответствующего корня. Поэтому для корректной работы метода во всех случаях необходимо учитывать точность e _f расчета функции f (x) и производить проверку ï f (x_i)ï< e _f, как и в методе половинного деления.

С учетом вышесказанного полная постановка задачи уточнения корня по методу сканирования с переменным шагом должна содержать следующие исходные данные:

1) начальноеприближение корня x ₀,

2) необходимую точность определения корня e,

3) точность e _f расчета функции f (x),

4) начальное значение шага сканирования h ₁,

5) коэффициент сокращения шага k.

Зависимость ï h_i ï= ï h ₁ï /k^{i- 1} ≤ e может быть использована для задания связи между параметрами задачи (h ₁, k, i). Например, при заданном коэффициенте k и числе итераций i длину начального шага ï h ₁ïна первой итерации можно задать равной ï h ₁ï=e× k^{i- 1}.

Корректная расширенная постановка задачи с учетом возможного попадания в корень означает численное определение: 1) либо нового итогового доверительного отрезка[a,b] длины, не превышающей e (8.5а), 2) либоприближенного значения корня x_пр, у которого ï f (x_i)ï< e_f (8.5б).

С учетом расширенной постановки задачи уточнения корня (8.5а)-(8.5б) численный алгоритм ее решения на каждой итерации i при известном последнем расчетном узле с_{i -1} - одной из крайних точек доверительного отрезка [ a_{i -1}, b_{i -1}] и значении шага h_{i -1} (ï h_{i -1}ï> e) на предыдущей итерации (i -1) должен вначале содержать расчет длины и направления шага h_{i -1} на текущей итерации i: h_i:= - h_{i -1} /k. Затем производится расчет значений функции в узлах вида d_{i , j} = с_{i -1} + j × h_i: (j = 1,2,...), в каждом узле d_{i , j} производятся проверки условий:

а) ï f (d_{i , j})ï≤ e_f - если оно выполнено, то имеет место попадание в корень, d_{i , j} принимаем в качестве его искомого уточненного значения и выходим из алгоритма,

б) иначе проверяем условие постоянства знака функции на последнем расчетном шаге f (d_{i , j})× f (d_{i ,( j- 1)}) >0 - если оно выполнено, продолжаем проход по узлам,

в) иначе (f (d_{i , j})× f (d_{i ,( j- 1)})<0) проверяем условие окончания работы алгоритма h_i ≤ e, если оно выполнено, отрезок [ d_{i ,( j- 1)}, d_ij ] принимаем в качестве искомого итогового доверительного отрезка и выходим из алгоритма, иначе принимаем с_i:= d_{i , j} и переходим к выполнению следующей итерации.

В качестве искомого решения принимаем последний доверительный отрезок [ d_{i ,( j- 1)}, d_ij ] или приближенное узловое значение d_{i , j}, если произошло попадание в корень.

При учете погрешности расчета значений функции метод сходится всегда, поскольку после выполнения каждой итерации i точное значение корня x* удерживается на доверительном отрезке [ a_i, b_i ] уменьшающейся длины. Скорость сходимости невысока из-за переборного характера применяемого алгоритма поиска уточнения.

Пример 1. Уточнить по методу сканирования с переменным шагом корень уравнения f (x) = x ³ - 6 х + 2 = 0 из примера 1 п.8.2 с точностью e = 0,01 в окрестности приближенного значения x ₀ = 3. Точность вычисления функции e_f = 0,0001.

Решение. Примем коэффициент сокращения шага k =10, число итераций i =2. Тогда из зависимости ï h_i ï= ï h ₁ï /kⁱ ≤ e получим, что длина начального шага ï h ₁ïна первой итерации может быть принята равной ï h ₁ï=e× k^{i- 1} = 0,01×10 = 0,1.

Так как f (3) = 11 > 0, то знак h ₀ должен быть выбран в направлении убывания функции (приближения ее к нулю). Пробные расчеты дают: f (3 - 0,1) = (2,9)³ - 6(2,9) + 2 = 8,989 <11 = f (3), f (3 + 0,1) = (3,1)³ - 6(3,1) + 2 = 13,191>11. Поэтому задаем: h ₁ = - 0,1.

Итерация 1. С учетом найденного значения f (2,9) = 8,989 >0 продолжаем вычисления значений функции до получения отрицательной величины (или попадания в корень с точностью e_f):

f (2,8) = 7,152>0; f (2,7) = 5,483>0; f (2,6) = 3,976>0; f (2,5) = 2,625>0; f (2,4) = 1,424>0; f (2,3) = 0,367>0; f (2,2) = -0,552<0.

Так как во всех точках ï f (d_{i , j})ï > e_f и ï h ₁ï = 0,1> e, то принимаем с_i:=2,2и переходим к следующей итерации.

Итерация 2. Принимаем: h ₂ = - h ₁/10 = 0,01. С учетом f (2,2)<0 вычисляем значения функции с шагом h ₂ до получения положительной величины (или попадания в корень с точностью e_f):

f (2,21) = -0,4661<0; f (2,22) = -0,379>0; f (2,23) = -0,2904<0; f (2,24) = -0,2006<0; f (2,25) = -0,1094<0; f (2,26) = -0,0168<0; f (2,27) = 0,0771>0.

Так как во всех точках ï f (d_{i , j})ï > e_f, то после смены знака функции проверяем длину полученного доверительного интервала. Так как ï h ₁ï = 0,01= e, то в качестве решения принимаем последний доверительный отрезок [2,26; 2,27].

Как видно из примера, метод не оптимален по числу вычислений функции - на поиск решения потрачено: 2 пробных расчета, 7 расчетов на итерации 1 и 7 расчетов на итерации 2 - всего 16 расчетов значения функции, что значительно превышает даже число расчетов в методе половинного деления.

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

Вопросы для проверки знаний.

1. Чем отличается уточнение корня в окрестности приближенной точки от уточнения на доверительном отрезке?

2. Какие методы уточнения корней в окрестности начального приближения являются наиболее употребительными?

3. Как задают точность решения в методах уточнения корней в окрестности начального приближения?

4. Какой порядок имеют методы уточнения корней в окрестности начального приближения?

5. В чем заключается основная идея уточнения корня в окрестности начального приближения при помощи метода сканирования с переменным шагом?

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

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

8. В каком виде может быть получено решение задачи уточнения корня в окрестности начального приближения при помощи метода сканирования с переменным шагом?

9. Каковы достоинства и недостатки метода уточнения корня в окрестности начального приближения при помощи сканирования с переменным шагом?

Практические задания.

1. Уточнить по методу сканирования с переменным шагом корень уравнения f (x) = x ⁴ - х - 14 = 0 с точностью e = 0,2 на отрезке [1,5;3].

2.Отделить положительный корень уравнения f (x) = x ³ - 0,2 x ² - 0,2 х - 1,2 = 0 и уточнить его с точностью e = 0,05.

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

Допустим, необходимо уточнить корень уравнения f (x)=0 при заданном начальномприближении x ₀ и необходимой точности определения корня e. В методе простой итерации исходное уравнение приводят к специальному виду x=φ (x), (8.9)

который удобен для применения метода простой итерации.

Схема метода простой итерации при заданном начальном приближении x ₀ имеет вид:

x_i = φ (x_{i -1}), (i=1,2,…,). (8.10 а)

Условие завершения итерационного процесса:

| x_k+1 – x_k |< ε. (8.10 б)

Достаточным условием сходимости метода является следующее условие:

1) функция φ (x) имеет первую производную φ¢ (x) на всей области поиска W (конечной или бесконечной),

2) для первой производной на W выполняется условие ½ φ¢ (x) ½£ q <1.

Справедливость условия вытекает из следующих оценок, в которых используется теорема Лагранжа о среднем:

Так как .