УТОЧНЕНИЕ КОРНЕЙ УРАВНЕНИЯ ОБЪЕДИНЕННЫМ МЕТОДОМ И МЕТОДОМ КАСАТЕЛЬНЫХ

Мы рассмотрели два метода уточнения изолированного корня уравнения вида F(х) =0, а именно, метод половинного деления (метод дихотомии) и метод хорд. При этом алгоритм отделения корней мы применяли отдельно для каждого изолированного отрезка, содержащего корень. Можно объединить алгоритм отделения и уточнения корней. Создадим объединенный алгоритм отделения корней и, например, алгоритм метода половинного деления для уточнения корней. Он позволит находить все корни уравнения. При этом метод дихотомии оформим в виде подпрограммы, к которой будем обращаться, когда будет найден очередной локальный отрезок, содержащий корень.

Рассмотрим рис. 11. Точка А – левый конец большого интервала из области определения функции F(х), В – его правый конец, h – шаг для поиска малых интервалов (х₁, х₂), содержащих корень, e – точность вычисления корня.

Запишем объединенный алгоритм отделения корней, а в нем как подпрограмму оформим алгоритм уточнения изолированных корней методом дихотомии.

Рис. 11. Иллюстрация к объединенному методу отделения и уточнения корней

ОБЪЕДИНЕННЫЙ АЛГОРИТМ ОТДЕЛЕНИЯ КОРНЕЙ
И УТОЧНЕНИЯ ИХ МЕТОДОМ ДИХОТОМИИ

ШАГ 1. Определяем функцию F(х).

ШАГ 2. Вводим исходные данные А, В, h, e .

ШАГ 3. Организуем счетчик корней данного уравнения и полагаем его равным нулю, т.е. К=0.

ШАГ 4. Полагаем х₁ = А и х₂ = х₁ + h.

ШАГ 5. Вычисляем значение функции на левом конце малого интервала:

у₁ = F(x₁).

ШАГ 6. Проверяем, не вышли ли мы за пределы отрезка АВ, т.е. проверяем х₂ > B?

Если ответ на этот вопрос положительный, то переходим на конец задачи (шаг 11), в противном случае вычисляем значение функции на правом конце малого интервала: у₂ = F(x₂).

ШАГ 7. Проверяем знак произведения функций у₁·у₂. Если он положительный, то функция на концах текущего малого интервала имеет одинаковый знак, следовательно, корня на этом интервале нет, переходим на шаг 8, в противном случае выполняем шаг 9.

ШАГ 8. Для перехода к следующему малому интервалу присваиваем значения правого конца малого интервала его левому концу, а именно,

х₁ = х₂, вычисляем новый правый конец малого интервала х₂ = х₁ + h и перезапоминаем значения функций на концах малого интервала, т.е. y₁ = y₂. После этого возвращаемся на шаг 6.

ШАГ 9. Если знак произведения функций отрицательный, то функция на концах малого интервала имеет разные знаки и, стало быть, на этом интервале есть корень. Увеличиваем счетчик корней на единицу, К = К + 1, и уходим в подпрограмму уточнения корней методом половинного деления на данном малом интервале.

ШАГ 10. Печатаем номер уточненного в подпрограмме k-го корня и его значение х. Возвращаемся на шаг 8.

ШАГ 11. Конец задачи.

АЛГОРИТМ ПОДПРОГРАММЫ

МЕТОДА ПОЛОВИННОГО ДЕЛЕНИЯ

Входные параметры подпрограммы:

    х₁ – левый конец интервала, содержащего корень;

    х₂ - правый конец интервала, содержащего корень.

    Выходной параметр подпрограммы: искомое значение корня х на текущем малом интервале.

ШАГ 1. Вычисляем середину отрезка, содержащего корень, с = (х₁ + х₂)/2.

ШАГ 2. Определяем интервал, на котором функция сменила знак. Для этого вычисляем значения функции в точках, например, х₁ и с, и выясняем знак их произведения. Если F(х₁) F(с) < 0 , то х₂ = с, в противном случае х₁ = с.

ШАГ 3. Проверяем, не стала ли длина отрезка [х₁, х₂] меньше наперед заданного e; если модуль разности между х₁ и х₂ остается больше e, то переходим на шаг 1.

ШАГ 4. Проверяем, насколько мал модуль разности значений функции в двух соседних точках х₁ и х_2. Если ½f(x₁) – f(x₂) ½> e , то переходим на шаг 1, в противном случае переходим на шаг 5.

ШАГ 5. Вычисляем х = (х₁ + х₂)/2.

ШАГ 6. Выход из подпрограммы.

Примечание. В подпрограмме уточнения корня методом дихотомии для проверки точности берется не только длина текущего отрезка [х₁, х₂], но и модуль разности значений функции на его концах.

КОНТРОЛЬНЫЙ ПРИМЕР ДЛЯ ОБЪЕДИНЕННОГО АЛГОРИТМА ОТДЕЛЕНИЯ КОРНЕЙ И УТОЧНЕНИЯ ИХ ЗНАЧЕНИЙ МЕТОДОМ ДИХОТОМИИ

    С помощью программы, реализующей объединенный алгоритм отделения корней и уточнения их значений методом дихотомии, найти все корни уравнения cos x – lg x = 0 на отрезке [0,5; 10].

Ответ. Х₁ = 1,4184; Х₂ = 5,5521; Х₃= 6,8631.

УТОЧНЕНИЕ ЗНАЧЕНИЯ ИЗОЛИРОВАННОГО КОРНЯ МЕТОДОМ КАСАТЕЛЬНЫХ (МЕТОД НЬЮТОНА)

Метод основан на замене F(х) в точке начального приближения х = х₀ касательной, пересечение которой с осью х дает первое приближение к корню х₁ (рис.12).

Рис. 12. Иллюстрация к методу касательных

    В качестве х₀ выбирают тот конец отрезка [a, b], на котором знаки F(x₀) и F´´(x₀) совпадают. Уравнение касательной, проведенной к графику функции в точке х₀ выглядит так:

x₁ = x₀ –

    В общем виде можно записать:

x_n+1 = x_n –

Вычисления следует повторять до тех пор, пока ½х_{n +1} – x_n½³ e .

Запишем алгоритм метода касательных.

АЛГОРИТМ УТОЧНЕНИЯ ИЗОЛИРОВАННОГО КОРНЯ МЕТОДОМ КАСАТЕЛЬНЫХ

ШАГ 1. Вводим концы отрезка, содержащего корень и требуемую точность вычислений, а именно, а – левый конец отрезка, содержащего корень, b – правый конец этого отрезка, e – точность вычислений.

ШАГ 2. Вычисляем значение функции на левом конце отрезка: F1 = F(a).

ШАГ 3. Вычисляем значение функции на правом конце отрезка: F2 = F(b).

ШАГ 4. Вычисляем значение второй производной на левом конце отрезка:

F3 = F ¢¢(a).

ШАГ 5. Вычисляем значение второй производной на правом конце отрезка: F4 = F ¢¢(b).

ШАГ 6. Определяем, какой конец отрезка будем брать в качестве начального приближения. Для этого определяем, совпадают ли знаки функции и ее второй производной на концах отрезка. Если F1 F3 > 0, то х₀ = а, и переходим на ШАГ 7, иначе проверяем, если F2 F4 > 0, то х₀ = b, и переходим на ШАГ 7, иначе выводим на печать сообщение “На этом отрезке корня уравнения нет” и уходим на ввод нового отрезка, т.е. на ШАГ 1.

ШАГ 7. Вычисляем значение функции в точке начального приближения: F5 = F(x₀).

ШАГ 8. Вычисляем значение первой производной функции в точке начального приближения: F6 = F ¢(x₀).

ШАГ 9. Вычисляем следующее приближение к корню: х₁ = х₀ – F5/F6.

ШАГ 10. Проверяем, насколько близки два соседних приближения: если ½х₁ – х₀½³ e, то х₀ = х₁, и переходим на ШАГ 7 , иначе выводим на печать найденное значение корня х₁.

ШАГ 11. Конец задачи.