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

Пусть корень уравнения f(x)=0отделен на отрезке [a;b], то есть на этом отрезке имеется единственный корень, а функция на данном отрезке непрерывна.

Метод половинного деления позволяет получить последовательность вложенных друг в друга отрезков [a_1;b₁], [a₂;b₂], …,[a_i;b_i],…, [a_n;b_n], таких что f(a_i).f(b_i) <0, где i=1,2,…,n, а длина каждого последующего отрезка вдвое меньше длины предыдущего:

Рис.1.2.3-1

Последовательное сужение отрезка вокруг неизвестного значения корня обеспечивает выполнение на некотором шаге n неравенства |b_n - a_n|<e. Поскольку при этом для любого хÎ[a_n;b_n] будет выполняться неравенство | - х|<, то с точностью любое

может быть принято за приближенное значение корня, например его середину отрезка

В методе половинного деления от итерации к итерации происходит последовательное уменьшение длины первоначального отрезка [a₀;b₀]в два раза (рис. 1.2.3-1). Поэтому на n-м шаге справедлива следующая оценка погрешности результата:

(1.2.3-1)

где - точное значение корня, х_nÎ [a_n;b_n] – приближенное значение корня на n-м шаге.

Сравнивая полученную оценку погрешности с заданной точностью , можно оценить требуемое число шагов:

(1.2.3-2)

Из формулы видно, что уменьшение величины e (повышение точности) приводит к значительному увеличению объема вычислений, поэтому на практике метод половинного деления применяют для сравнительно грубого нахождения корня, а его дальнейшее уточнение производят с помощью других, более эффективных методов.

Рис. 1.2.3-2. Схема алгоритма метода половинного деления

Схема алгоритма метода половинного деления приведена на рис. 1.2.3-2. В приведенном алгоритме предполагается, что левая часть уравнения f(x)оформляется в виде программного модуля.

Пример 1.2.3-1.Уточнить корень уравнения x³+x-1=0 с точностью =0.1, который локализован на отрезке [0;1].

Результаты удобно представить с помощью таблицы1.2.3-3.

Таблица 1.2.3-3

Послечетвертой итерации длина отрезка |b₄-a₄|=|0.688-0.625|=0.063 стала меньше величины e, следовательно, за приближенное значение корня можно принять значение середины данного отрезка: x = (a₄+b₄)/2 = 0.656.

Значение функции f(x) в точке x=0.656 равно f(0.656)= -0.062.

Метод итерации

Метод итераций предполагает замену уравнения f(x)=0 равносильным уравнением x=j(x). Если корень уравнения отделен на отрезке [a;b], то исходя из начального приближения x₀Î[a;b], можно получить последовательность приближений к корню

x₁ = j(x₀), x₂ = j(x₁), …, ,(1.2.3-3)

где функция j(x) называется итерирующей функцией.

Условие сходимости метода простой итерации определяется следующей теоремой.

Пусть кореньх* уравнения x=j(x)отделен на отрезке [a;b]и построена последовательность приближений по правилу x_n=j(x_n-1). Тогда, если все члены последовательности x_n=j(x_n-1)Î [a;b]и существует такоеq (0<q<1), что для всех хÎ [a; b]выполняется |j’(x)| = q<1, то эта последовательность является сходящейся и пределом последовательности является значение корня x*, т.е. процесс итерации сходится к корню уравнения независимо от начального приближения.

Таким образом, если выполняется условие сходимости метода итераций, то последовательность x₀, x₁, x₂, …, x_n,…,полученная с помощью формулы x_n+1 = j(x_n), сходится к точному значению корня :

если

Условие j(x)Î[a;b] при xÎ[a;b] означает, что все приближения x₁, x₂, …, x_n,…,полученные по итерационной формуле, должны принадлежать отрезку [a;b], на котором отделен корень.

Для оценки погрешности метода итерации справедливо условие

(1.2.3-4)

За число q можно принимать наибольшее значение |j'(x)|,а процесс итераций следует продолжать до тех пор, пока не выполнится неравенство

(1.2.3-5)

На практике часто используется упрощенная формула оценки погрешности. Например, если 0<q£½то

|x_n-1 - x_n|£ .

Использование итерационной формулы x_n+1=j(x_n) позволяет получить значение корня уравнения f(x)=0 с любой степенью точности.

Геометрическая иллюстрация метода итераций. Построим на плоскости X0Y графики функций y=x и y=j(x). Корень уравнения х=j(x) является абсциссой точки пересечения графиков функции y = j(x) и прямой y=x. Возьмем некоторое начальное приближение x₀Î [a;b]. На кривойy = j(x) ему соответствует точка А₀ = j(x₀). Чтобы найти очередное приближение, проведем через точку А₀прямую горизонтальную линию до пересечения с прямой y = x (точкаВ₁) и опустим перпендикуляр до пересечения с кривой (точкаА₁), то естьх₁=j(x₀). Продолжив построение аналогичным образом, имеем ломаную линию А₀, В₁, А₁, В₂, А₂…, для которой общие абсциссы точек представляют собой последовательное приближение х₁, х₂, …, х_n («лестницу») к корню х*. Из рис. 1.2.3-3а видно, что процесс сходится к корню уравнения.

Рассмотрим теперь другой вид кривой y = j(x) (рис. 1.2.6b). В данном случае ломаная линия А₀, В₁, А₁, В₂, А₂…имеет вид “спирали”. Однако, и в этом случае наблюдается сходимость.

a) b)

Рис. 1.2.3-3

Нетрудно видеть, что в первом случае для производной выполняется условие 0<j’(x)< 1,а во втором случае производная j’(x)<0иj’(x)>-1. Таким образом, очевидно, что если |j’(x)|<1, то процесс итераций сходится к корню.

Теперь рассмотрим случаи, когда |j’(x)|>1. На рис. 1.2.3-4а показан случай, когда j’(x)>1, а на рис. 1.2.3-4b – когда j’(x) < -1.В обоих случаях процесс итерации расходится, то есть, полученное на очередной итерации значение х все дальше удаляется от истинного значения корня.

a) b)

Рис. 1.2.3-4

Способы улучшения сходимости процесса итераций. Рассмотрим два варианта представления функции j(x) при переходе от уравнения f(x)кx=j(x).

1.Пусть функция j(x) дифференцируема и монотонна в окрестностях корня и существует числоk£ |j‘(x)|, где k³ 1 (т.е. процесс расходится). Заменим уравнение х=j(x) эквивалентным ему уравнением х=Y(х),где Y(х) = 1/j(x)(перейдем к обратной функции). Тогда

а значит q=1/k<1 и процесс будет сходиться.

2.Представим функцию j(x) как j(x) = х - lf(x), где l- коэффициент,не равный

нулю. Для тогочтобы процесс сходился, необходимо, чтобы
0<|j¢(x)|=|1 - lf¢(x)|<1. Возьмем l= 2/(m₁+M₁), где m₁иM₁– минимальное и максимальное значенияf’(x) (m₁=min|f’(x)|, M₁=max|f’(x)|)для хÎ[a;b],т.е.0£ m₁£ f¢(x) £ M₁£1.Тогда

и процесс будет сходящимся, рекуррентная формула имеет вид

Если f¢(x) < 0, то в рекуррентной формуле f(x) следует умножить на -1.

Параметр λ может быть также определен по правилу:

Если , то , а если , то , где .

Схема алгоритма метода итерации приведена на рис. 1.2.3-5.

Исходное уравнение f(x)=0преобразовано к виду, удобному для итераций: Левая часть исходного уравнения f(x) и итерирующая функция fi(x) в алгоритме оформлены в виде отдельных программных модулей.

Рис. 1.2.3-5. Схема алгоритма метода итерации

Пример 1.2.3-2.Уточнить корень уравнения 5x – 8∙ln(x) – 8 =0 с точностью 0.1, который локализован на отрезке [3;4].

Приведем уравнение к виду, удобному для итераций:

Следовательно, за приближенное значение корня уравнения принимаем значение x₃=3.6892, обеспечивающее требуемую точность вычислений. В этой точке f(x₃)=0.0027.