Численное решение нелинейных уравнений. Методы простой итерации. Примеры методов. Теорема о сходимости метода простой итерации и ее следствия

Пусть задана функция f(x) действительного переменного. Требуется найти корни уравнения

f(x)= 0 (1)

или, что то же самое, нули функции f(x).

Уже на примере алгебраического многочлена известно, что нули f(x) могут быть как действительными, так и комплексными. Поэтому более точная постановка задачи состоит в нахождении корней уравнения (1), расположенных в заданной области комплексной плоскости. Можно рассматривать также задачу нахождения действительных корней, расположенных на заданном отрезке. Иногда, пренебрегая точностью формулировок, будем говорить, что требуется решить уравнение (1).

Задача нахождения корней уравнения (1) обычно решается в два этапа. На первом этапе изучается расположение корней (в общем случае на комплексной плоскости) и проводится их разделение, т. е. выделяются области в комплексной плоскости, содержащие только один корень. Кроме того, изучается вопрос о кратности корней. Тем самым находятся некоторые начальные приближения для корней уравнения (1). На втором этапе, используя заданное начальное приближение, строится итерационный процесс, позволяющий уточнить значение отыскиваемого корня.

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

f(x)=a₀ + a₁x+a₂x²+... + a_mx^m. (2)

Например известно, что если для многочлена (2) с действительными коэффициентами выполнены неравенства

f(c)>0, f’(с)>,…, f^(m)(c)>0,

то положительные корни f(х) не превосходят числа с.

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

2. Метод простой итерации. Он состоит в том, что уравнение (1) заменяется эквивалентным уравнением

x = s(x) (3)

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

x_n+1 = s(x_n), n = 0,1,..., (4)

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

s(x) = x + τ(x)*f(x), (5)

причем функция τ(х) не меняет знака на том отрезке, где отыскивается корень. Метод простой итерации сходится при надлежащем выборе начального приближения х₀, если |s'(x₀) | < 1, где х. – корень уравнения (1).

Отметим, что в форме метода простой итерации (4) можно записать, по существу, любой одношаговый итерационный метод.

Примеры методов: метод релаксации, метод Ньютона, метод секущих.

Сходимость метода простой итерации.

Теорема о сходимости. Перепишем уравнение

f(x)= 0 (1)

в эквивалентном виде

x = s(x) (2)

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

x_n+1 = s(x_n), n = 0, 1,..., x₀ задан. (3)

Говорят, что итерационный метод сходится, если последовательность {х_n} имеет предел при n->∞.

В следующей теореме формулируются условия на функцию s(x), гарантирующие существование и единственность решения уравнения (2) и сходимость метода простой итерации к этому решению. Напомним, что функция s(x) называется липшиц-непрерывной с постоянной q на множестве X, если для всех х', х" Х выполняется неравенство

|s(x') – s(x")| q|x' – х"|. (4)

В дальнейшем в качестве X будем брать отрезок

U_r(a)={

Теорема 1. Если s(x) липшиц-непрерывна с постоянной q (0, 1) на отрезке U_r(a), причем

|s(a) – a|<(1 – q)r, (6)

то уравнение (2) имеет на отрезке U_r(a) единственное решение х, и метод простой итерации (3) сходится к х^* при любом начальном приближении x₀ (U_r(a)). Для погрешности справедлива оценка

|x_k – x^*| q^k|x₀ – x^*|, k = 0, 1,2,... (7)

Доказательство. Сначала докажем по индукции, что x_k U_r(a), k = 0,1,… т. е. что метод простой итерации не выводит за пределы того множества, на котором s(x) липшиц-непрерывна с постоянной q (0, 1). Предположим, что x_j U_r(a) при некотором j 0, и докажем, что тогда x_j+l U_r(a). Из равенства

x_j+1 – a = s(x_j) – a = (s(x_j) – s(a)) + (s(a) – a)

получим

|x_j+1 – a| |s(x_j) – s(a)| + |s(a) – a|

Учитывая условие липшиц-непрерывности, предположение индукции и условие(6),имеем

т.е.

Оценим теперь разность двух соседних итераций x_j+1—x_j. Имеем

и поскольку все точки х_j, j = 1,2,..., находятся на отрезке U_r(a), получаем оценку

и,следовательно,

. (8)

Оценка (8) позволяет доказать фундаментальность последовательности {x_k}. Действительно, пусть p – любое натуральное число. Тогда

и согласно (8) имеем

(9)

Поскольку правая часть неравенства (9) стремится к нулю при и не зависит от р, последовательность {x_k} является фундаментальной. Следовательно, существует

Переходя в (3) к пределу при и учитывая непрерывность функции s(x), получим x^*=s(x^*), т. е. х^* - решение уравнения (2).

Предположим, что х^*’ какое – то решение уравнения (2), принадлежащее отрезку U_r(a). Тогда

и по условию теоремы

Так как q<1, последнее неравенство может выполняться лишь при , т.е. решение единственно.

Докажем оценку погрешности (7). Из уравнения (3) получим

и так как , приходим к неравенству

(10)

справедливому для всех k = 0, 1,..., из которого и следует оценка (7). Теорема 1 доказана.

Приведем следствия из теоремы 1, содержащие более удобные для проверки условия сходимости.

Будем предполагать, что s(x) непрерывно дифференцируема на отрезке U_r(a).

Следствие 1. Если

(12)

для , выполнено условие (6) и , то уравнение (2) имеет единственное решение , метод (3) сходится и справедлива оценка (7).
Действительно, из (12) следует (4) с q (0, 1).
Cледствие 2. Пусть уравнение (2) имеет решение , функция s(x) непрерывно дифференцируема на отрезке
(13)
и . Тогда существует ε>0 такое, что на отрезке U_r(x^*) уравнение (2) не имеет других решений и метод (3) сходится, если только .
Доказательство. Поскольку s(x) непрерывно дифференцируема на отрезке U_r(x^*) и , найдутся числа q (0, 1) и такие, что

ВОПРОС 18 (2)