Итерационное уточнение корней.

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

Этап уточнения корня имеет своей целью вычисление приближенного значения корня с заданной точностью. При этом применяются итерационные методы вычисления последовательных приближений к корню: x₀, x₁, ..., x_n, …, в которых каждое последующее приближение x_n+1вычисляется на основании предыдущего x_n. Каждый шаг называется итерацией. Если последовательность x₀, x₁, ..., x_n, …при n ® ¥ имеет предел, равный значению корня , то говорят, что итерационный процесс сходится.

Существуют различные способы отделения и уточнения корней, которые мы рассмотрим ниже.

 

Отделение корней

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

 

Графическое отделение корней

 

Графическое отделение корнейосновано на графическом способе решения уравнений – отыскании точек, в которых функция f(x)пересекает ось 0Х.

 

Пример 1.2.2-1. Отделить корни уравнения ln (x-1)² – 0.5 = 0.

На рис. 1.2.2-1 изображен график функции y = ln (x-1)² – 0.5, из которого следует, что уравнение имеет два действительных корня [-1; 0] и [2; 3].

 

Рис.1.2.2-1

 

В некоторых случаях удобно вначале преобразовать функцию f(x) к виду f(x)=g₁(x ) - g₂(x), из которого, при условии f(x)=0, следует, что g₁(x)=g₂(x). При построении графиков y₁=g₁(x ) и y₂=g₂(x)находят отрезки, содержащие точки пересечения этих графиков.

Пример 1.2.2-2. Отделить корни уравнения сos(x) – x + 1 = 0.

Приведем исходное уравнение к виду сos(x)= x – 1. Построив графики функций y₁ = сos(x) и y₂ = х – 1 (рис. 1.2.2), выделим отрезок, содержащий корень [1; 2].

 

Рис. 1.2.2-2

Аналитическое отделение корней

 

Аналитическое отделение корней основано на следующей теореме.

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

 

Действительно, если условия теоремы выполнены, как это имеет место на отрезке [a; b] (рис. 1.2.2-3), то есть f(a)∙ f(b)< 0 и f'(x)> 0 для xÎ [a; b], то график функции пересекает ось 0Х только один раз и, следовательно, на отрезке [a; b] имеется один корень уравнения f(x) = 0.

Аналогично можно доказать единственность корня на отрезке [c; d], на[d; e]и т.д

Рис. 1.2.2-3

 

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

1) установить область определения функции;

2) определить критические точки функции, решив уравнение f¢ (x)=0;

3) составить таблицу знаков функции f(x) в критических точках и на границах области определения;

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

Пример 1.2.2-3. Отделить корни уравнения x - ln(x+2) = 0.

Область допустимых значений функции f(x) = x - ln(x+2) лежит в интервале (-2; ∞ ), найденных из условия x+2> 0. Приравняв производную f¢ (x)=1-1/(x+2) к нулю, найдем критическую точку х_k= -1. Эти данные сведены в табл. 1.2.2-1 и табл. 1.2.2-2 знаков функции f(x).

Таблица 1.2.2-1 Таблица 1.2.2-.2

x	x→ -2	-1	x→ ∞		x	-1.9	-1.1	-0.9	2.0
Sign(f(x))	+	-	+		Sign(f(x))	+	-	-	+

 

Уравнение x - ln(x+2) = 0 имеет два корня (-2; -1]и [-1; ∞ ). Проверка знака функции внутри каждого из полученных полуинтервалов (табл.1.2.2) позволяет отделить корни уравнения на достаточно узких отрезках [-1.9; -1.1]и [-0.9; 2.0].

 

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

Задача уточнения корня уравнения с точностью , отделенного на отрезке [a; b], состоит в нахождении такого приближенного значения корня , для которого справедливо неравенство . Если уравнение имеет не один, а несколько корней, то этап уточнения проводится для каждого отделенного корня.

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

Пусть корень уравнения 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

k	a	b	f(a)	f(b)	(a+b)/2	f((a+b)/2)	a k	b k
			-1		0.5	-0.375	0.5
	0.5		-0.375		0.75	0.172	0.5	0.75
	0.5	0.75	-0.375	0.172	0.625	-0.131	0.625	0.75
	0.625	0.75	-0.131	0.172	0.688	0.0136	0.625	0.688

 

После четвертой итерации длина отрезка |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.

⇐ Предыдущая123Следующая ⇒

Поделиться:

Популярное:

1. Уточнение, конкретизация уже известного,