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

Метод деления отрезка пополам

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

РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

Отделить корень уравнения

f(x)=0 (8.1)

значит найти такой отрезок области определения функции f(x), который содержит только один корень этого уравнения.

Для отделения корней уравнения (8.1) можно использовать следующий критерий: если на отрезке [a,b] функция f(x) непрерывна и монотонна, а её значения на концах отрезка имеют разные знаки, то на этом отрезке существует и при том только один корень данного уравнения. Достаточным признаком монотонности функции f(x) на отрезке [a,b] является сохранение знака производной. При отделении корней стараются определить отрезок как можно меньшей длины.

Отделение корней уравнения (8.1) можно выполнить также графически. Найти корень уравнения (8.1) значит найти абсциссу точки пересечения графика функции f(x) c осью абсцисс. Если построить график функции f(x) затруднительно, то уравнение (8.1) следует представить в эквивалентном виде

f₁(x)=f₂(x) (8.2)

с таким расчетом, чтобы графики функций f₁(x), f₂(x) строились проще. Корни же уравнения (8.2) определяются как абсциссы точек пересечения графиков функций f₁(x) и f₂(x).

Замечание. Известно, что все корни алгебраического уравнения

f(z) = a₀zⁿ + a₁z^n-1 +…+ a_n-1z + a_n = 0

расположены в кольце

| a_n| c

―――― ≤ |z| ≤ 1 + ――,

b + |a_n| |a₀|

где b = max{ |a_n|,|a₁|,…,|a_n-1 |}, c = max{| a₁|,|a₂|,…,|a_n| }.

Простейшим алгоритмом уточнения корня на отрезке [a,b], если f(x) непрерывная функция и f(a)f(b) < 0 является метод деления отрезка пополам. Очевидно, что середина отрезка служит приближением к корню уравнения (8.1) с точностью

ε ═ (b-a)/2. В средней точке отрезка [a,b] определяется знак функции f(x), затем выбирается та половина отрезка, на концах которой функция принимает значения разных знаков, и деление повторяется. Если требуется найти корень с точностью до ε, то деление отрезка пополам продолжается до тех пор, пока длина отрезка не станет меньше ε/2. Тогда середина последнего даст значение корня с требуемой точностью.

Он состоит в том, что уравнение (8.1) заменяется эквивалентным уравнением вида

x = s(x) (8.3)

и итерации образуются по правилу

x_n+1 = s(x_n), n = 0,1,…,

причём задаётся начальное приближение x₀. Для сходимости большое значение имеет выбор функции s(x).

Метод простой итерации сходится при надлежащем выборе начального приближения х₀, если

|s´(x)| <1

в некоторой окрестности корня. Более точно:

Теорема. Если |s^'(x)| £ q <1 при хÎ [ a-r,a+r ], причём |s(a) – a|£ (1-q)r, то уравнение (8.2) имеет единственное решение х_* и метод простой итерации сходится к х_* при любом начальном приближении х₀Î [ a-r,a+r ].

Для метода простой итерации можно пользоваться следующей оценкой погрешности

q^k

| x_k – x_*| £ ――― |s(x₀) – x₀|, k = 1,2,….

1 - q

Где х _* - истинное значение корня, |s^¢(x)|£q<1 для х Î[a,b], х₀ Î[a,b]. Если функцию s(x) в уравнении (8.3) берём в виде

s(x) = x +tf(x), t=const,

то получаем так называемый метод релаксации. Параметр t выбирается таким образом, чтобы выполнялась оценка (8.4). Если в некоторой окрестности корня выполняются условия

f¢(x) < 0, 0 < m₁ < |f ¢(x)| <M₁,

то метод релаксации сходится при tÎ (0, 2/М₁). Наиболее быстрая скорость сходимости достигается пр оптимальном значении параметра t₀ = 2/(М₁+м₁). При этом значении для погрешности справедлива оценка

|x_n - x_*| £ r₀ⁿ |x₀ - x_*|,

где

1 – ξ m₁

r₀ = ―――, ξ = ―

1 + ξ M₁

Пример. Решим уравнение

f(x) = x³ +3x² –1 =0

методом простой итерации с точностью e = 0.5*10^-4.

По графику находим, что уравнение имеет три корня, расположенных на отрезках [-3;-2], [-1;0] и [0;1]. Найдём корень на отрезке [-3;-2]. Поделим уравнение на х² и приведём к виду

x = 1/х² –3 (8.5)

Положим s(x) = 1/x² –3 и возьмём х₀ = -2.5. На отрезке [-3;-2] (r = 0.5) выполняются условия теоремы:

max | s¢(x) | = q = ¼, | s(x₀) – x₀ | = 0.34 < (1-q)r = 0.375.

Найдём число итераций, необходимых для достижения заданной точности:

|s(x₀) – x₀|

――――― qⁿ ≤ ε Þ n ³ 6

1 - q

После шести итераций получаем приближенное значение корня –2.87938.

На отрезках [-1;0] и [0;1] представление (8.5) не годится для нахождения корней, поскольку производная функции s(x) больше 1 на этих отрезках. Для нахождения корней здесь удобно использовать представления

x = ±1/Ö x+3.

Дата добавления: 2015-05-10