Теория нелинейных уравнений и метод половинного деления. Метод дихотомии или метод половинного деления

Метод половинного деления (другие названия: метод бисекций , метод дихотомии ) для решения уравнения f (x ) = 0 заключается в следующем . Пусть известно, что функция непрерывна и принимает на концах отрезка
[a , b ] значения разных знаков, тогда корень содержится в интервале (a , b ). Разделим интервал на две половины и дальше будем рассматривать ту половину, на концах которой функция принимает значения разных знаков. Этот новый отрезок снова делим на две равные части и выбираем из них ту, которая содержит корень. Этот процесс продолжается до тех пор, пока длина очередного отрезка не станет меньше требуемой величины погрешности. Более строгое изложение алгоритма метода половинного деления:

1) Вычислим x = (a + b )/2; вычислим f (x );

2) Если f (x ) = 0, то переходим к пункту 5;

3) Если f (x )∙ f (a ) < 0, то b = x , иначе a = x ;

4) Если |b – a | > ε, переходим к пункту 1;

5) Выводим значение x ;

Пример 2.4. Уточнить методом бисекций с точностью до 0,01 корень уравнения (x – 1) 3 = 0, принадлежащий отрезку .

Решение в программе Excel :

1) В ячейках A 1:F 4 введем обозначения, начальные значения и формулы, как показано в таблице 2.3.

2) Каждую формулу скопируем в нижние ячейки маркером заполнения до десятой строки, т.е. B 4 - до B 10, C 4 - до C 10, D 3 - до D 10, E 4 - до E 10, F 3 - до F 10.

Таблица 2.3

	A	B	C	D	E	F
		f(a)=	=(1-B3)^3
	k	a	x	f(x)	b	b-a
		0,95	=(B3+E3)/2	=(1-C3)^3	1,1	=E3-B3
		=ЕСЛИ(D3=0;C3; ЕСЛИ(C$1*D3<0;B3;C3))			=ЕСЛИ(C$1*D3>0; E3;C3)

Результаты расчетов приведены в табл. 2.4. В столбце F проверяем значения длины интервала b – a . Если значение меньше чем 0,01, то в данной строке найдено приближенное значение корня с заданной погрешностью. Потребовалось 5 итераций для достижения требуемой точности. Приближенное значение корня с точностью до 0,01 после округления до трех знаков равно 1,0015625 ≈ 1,00.

Таблица 2.4

	A	B	C	D	E	F
		f(a)=	0,000125
	k	a	x	f(x)	b	b-a
		0,95	1,025	-2E-05	1,1	0,15
		0,95	0,9875	2E-06	1,025	0,075
		0,9875	1,00625	-2E-07	1,025	0,0375
		0,9875	0,996875	3,1E-08	1,00625	0,0187
		0,996875	1,0015625	-4E-09	1,00625	0,0094
		0,996875	0,9992188	4,8E-10	1,0015625	0,0047
		0,99921875	1,0003906	-6E-11	1,0015625	0,0023
		0,99921875	0,9998047	7,5E-12	1,000390625	0,0012

Приведенный алгоритм учитывает возможный случай «попадания в корень», т.е. равенство f (x ) нулю на очередном этапе. Если в примере 2.3 взять отрезок , то на первом же шаге попадаем в корень x = 1. Действительно, запишем в ячейке B 3 значение 0,9. Тогда таблица результатов примет вид 2.5 (приведены только 2 итерации).

Таблица 2.5

	A	B	C	D	E	F
		f(a)=	0,001
	k	a	x	f(x)	b	b-a
		0,9			1,1	0,2

Создадим в программе Excel пользовательские функции f(x) и bisect(a, b, eps) для решения уравнения методом половинного деления, пользуясь встроенным языком Visual Basic . Их описания приведены ниже:

Function f(Byval x)

Function bisect(a, b, eps)

1 x = (a + b) / 2

If f(x) = 0 Then GoTo 5

If f(x) * f(a) < 0 Then

If Abs(a - b) > eps Then GoTo 1

Функция f(x) определяет левую часть уравнения, а функция
bisect(a, b, eps) вычисляет методом половинного деления корень уравнения f (x ) = 0. Обратим внимание на то, что в функции bisect(a, b, eps) используется обращение к функции f(x). Приведем алгоритм создания пользователькой функции:

1) Выполним команду меню «Сервис - Макрос - Редактор Visual Basic ». Откроется окно «Microsoft Visual Basic ». Если в данном файле программы Excel ещё не были созданы макросы или пользовательские функции или процедуры, это окно будет иметь вид, изображенный на рис.2.4.

2) Выполним команду меню «Insert - Module» и вводим тексты программ-функции, как показано на рис 2.5.

Теперь в ячейках листа программы Excel можно в формулах использовать созданные функции. Например, введем в ячейку D 18 формулу

Bisect(0,95;1;0,00001),

то получим значение 0,999993896.

Чтобы решить другое уравнение (с другой левой частью) нужно перейти в окно редактора с помощью команды «Сервис - Макрос - Редактор Visual Basic » и просто переписать описание функции f(x). Например, найдем с точностью до 0,001 корень уравнения sin5x + x 2 – 1 = 0, принадлежащий интервалу (0,4; 0,5). Для этого изменим описание функции

на новое описание

f = Sin(5 * x) + x ^ 2 - 1

Тогда в ячейке D 18 получим значение 0,441009521 (сравните этот результат со значением корня из интервала (0,4; 0,5), найденным в примере 2.3!).

Для решения уравнения методом половинного деления в программе Mathcad создадим подпрограмму-функцию bisec (f , a , b , ε), где:

f - имя функции, соответствующее левой части уравнения f (x ) = 0;

a , b - левый и правый концы отрезка [a , b ];

ε - точность приближенного значения корня.

Решение примера в программе Mathcad :

1) Запускаем программу Mathcad. Введем определение функции bisec (f , a , b , ε). Для этого с помощью клавиатуры и панели инструментов «Греческие символы» набираем bisec (f , a , b , ε):=. После знака присваивания «:=» на панели инструментов «Программирование» указателем мыши щелкаем левой кнопкой «Add line». После знака присваивания появится вертикальная линия. Далее вводим текст программы, который приведен ниже, используя панель инструментов «Программирование» для ввода знака «←», оператора цикла while , оператора break и условного оператора if otherwise .

2) Введем определение функции f (x ):=sin(5*x)+x^2–1, а затем вычислим значение корня с помощью функции bisec при заданных значениях:
bisec (f , –0.8,–0.7,0.0001)=. После знака «=» автоматически появится вычисленное программой значение корня –0,7266601563. Аналогично вычислим остальные корни.

Ниже приведен лист Mathcad с определением функции bisec (f , a , b , ε) и расчетами:

Приведем программу на языке C ++ для решения уравнения f (x ) = 0 методом половинного деления:

#include

#include

double f(double x);

typedef double (*PF)(double);

double bisec(PF f,double a, double b,double eps);

double a, b, x, eps;PF pf;

cout << "\n a = "; cin >> a;

cout << "\n b = "; cin >> b;

cout << "\n eps = "; cin >> eps;

x = bisec(pf,a,b,eps); cout << "\n x = " << x;

cout << "\n Press any key & Enter "; cin >> a;

double f(double x){

r = sin(5*x)+x*x-1;

double bisec(PF f, double a, double b,double eps){

do{ x = (a + b)/2;

if (f(x) == 0) break;

if (f(x)*f(a)<0) b = x;

}while (fabs(b-a) > eps);

В программе функция f (x ) определена для решения уравнения

sin5x + x 2 – 1 = 0

из примера 2.3. Результат работы программы для определения корня из интервала (0,4; 0,5) с точностью 0,00001 представлен ниже (экран компьютера):

Press any key & Enter

Последняя строка нужна для организации паузы для просмотра результата.

Нелинейные уравнения можно разделить на 2 класса - алгебраические и трансцендентные. Алгебраическими уравнениями называют уравнения, содержащие только алгебраические функции (целые, рациональные, иррациональные). В частности, многочлен является целой алгебраической функцией. Уравнения, содержащие другие функции (тригонометрические, показательные, логарифмические и другие) называются трансцендентными.

Методы решения нелинейных уравнений делятся на две группы:

1. точные методы
;
2. итерационные методы
.

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

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

Пусть дано уравнение

1. Функция f (x ) непрерывна на отрезке [a, b ] вместе со своими производными 1-го и 2-го порядка.
2. Значения f (x ) на концах отрезка имеют разные знаки (f (a ) * f (b ) < 0).
3. Первая и вторая производные f" (x ) и f"" (x ) сохраняют определенный знак на всем отрезке.

Условия 1) и 2) гарантируют, что на интервале [a, b ] находится хотя бы один корень, а из 3) следует, что f (x ) на данном интервале монотонна и поэтому корень будет единственным.

Решить уравнение (1) итерационным методом значит установить, имеет ли оно корни, сколько корней и найти значения корней с нужной точностью.

Всякое значение , обращающее функцию f (x ) в нуль, т.е. такое, что:

называется корнем уравнения (1) или нулем функции f (x ).

Задача нахождения корня уравнения f (x ) = 0 итерационным методом состоит из двух этапов:

1. отделение корней
- отыскание приближенного значения корня или содержащего его отрезка;
2. уточнение приближенных корней
- доведение их до заданной степени точности.

Процесс отделения корней начинается с установления знаков функции f (x ) в граничных x = a и x = b точках области ее существования.

Пример 1. Отделить корни уравнения:

f(x ) є x 3 - 6х + 2 = 0.

Составим приблизительную схему:

Следовательно, уравнение (2) имеет три действительных корня, лежащих в интервалах [-3, -1], и .

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

В инженерной практике распространен графический способ определения приближенных корней.

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

Уравнение (4) удобно переписать в виде равенства:

Отсюда ясно, что корни уравнения (4) могут быть найдены как абсциссы точек пересечения логарифмической кривой y = lg x и гиперболы y = . Построив эти кривые, приближенно найдем единственный корень уравнения (4) или определим его содержащий отрезок .

Итерационный процесс состоит в последовательном уточнении начального приближения х 0 . Каждый такой шаг называется итерацией . В результате итераций находится последовательность приближенных значений корня х 1 , х 2 , ..., х n . Если эти значения с увеличением числа итераций n приближаются к истинному значению корня, то говорят, что итерационный процесс сходится .

Для нахождения корня уравнения (1), принадлежащего отрезку [a, b ], делим этот отрезок пополам. Если f = 0 , то x = является корнем уравнения. Если f не равно 0 (что, практически, наиболее вероятно), то выбираем ту из половин или , на концах которой функция f (x ) имеет противоположные знаки. Новый суженный отрезок [ а 1 , b 1] снова делим пополам и производим те же самые действия.

Метод половинного деления практически удобно применять для грубого нахождения корня данного уравнения, метод прост и надежен, всегда сходится.

Пример 3. Методом половинного деления уточнить корень уравнения

f(x ) = x 4 + 2 x 3 - x - 1 = 0

лежащий на отрезке [ 0, 1] .

Последовательно имеем:

f(0) = - 1; f (1) = 1; f (0,5) = 0,06 + 0,25 - 0,5 - 1 = - 1,19;

f(0,75) = 0,32 + 0,84 - 0,75 - 1 = - 0,59;

f(0,875) = 0,59 + 1,34 - 0,88 - 1 = + 0,05;

f(0,8125) = 0,436 + 1,072 - 0,812 - 1 = - 0,304;

f(0,8438) = 0,507 + 1,202 - 0,844 - 1 = - 0,135;

f(0,8594) = 0,546 + 1,270 - 0,859 - 1 = - 0,043 и т. д.

Можно принять

x = (0,859 + 0,875) = 0,867

В данном методе процесс итераций состоит в том, что в качестве приближений к корню уравнения (1) принимаются значения х 1 , х 2 , ..., х n точек пересечения хорды АВ с осью абсцисс (Рисунок 3). Сначала запишем уравнение хорды AB :

.

Для точки пересечения хорды AB с осью абсцисс (х = х 1 , y = 0) получим уравнение:

Пусть для определенности f"" (x ) > 0 при а х b (случай f"" (x ) < 0 сводится к нашему, если записать уравнение в виде - f (x ) = 0). Тогда кривая у = f (x ) будет выпукла вниз и, следовательно, расположена ниже своей хорды АВ . Возможны два случая: 1) f (а ) > 0 (Рисунок 3, а ) и 2) f (b ) < 0 (Рисунок 3, б ).

Рисунок 3, а, б.

В первом случае конец а неподвижен и последовательные приближения: x 0 = b ;x , где функция f (х ) имеет знак, противоположный знаку ее второй производной f"" (х ).

Итерационный процесс продолжается до тех пор, пока не будет обнаружено, что

| x i - x i - 1 |< e ,

где e - заданная предельная абсолютная погрешность.

Пример 4. Найти положительный корень уравнения

f(x ) = x 3 - 0,2 x 2 - 0,2 х - 1,2 = 0

с точностью e = 0,01.

Прежде всего, отделяем корень. Так как

f (1) = -0,6 < 0 и f (2) = 5,6 > 0,

то искомый корень x лежит в интервале . Полученный интервал велик, поэтому разделим его пополам. Так как

f (1,5) = 1,425 > 0, то 1< x < 1,5.

Так как f"" (x ) = 6 x - 0,4 > 0 при 1 < х < 1,5 и f (1,5) > 0, то воспользуемся формулой (5) для решения поставленной задачи:

= 1,15;

| x 1 - x 0 | = 0,15 > e ,

следовательно, продолжаем вычисления;

f (х 1) = -0,173;

= 1,190;

|x 2 - x 1 | = 0,04 > e ,

f (х 2) = -0,036;

= 1,198;

| x 3 - x 2 | = 0,008 < e .

Таким образом, можно принять x = 1,198 с точностью e = 0,01.

Заметим, что точный корень уравнения x = 1,2.

Метод дихотомии имеет свое название от древнегреческого слова, что в переводе означает деление надвое. Именно поэтому данные метод имеет еще второе название: метод половинного деления. Его мы используем довольно часто. Допустим, играя в игру "Угадай число", где один игрок загадывает число от 1 до 100, а другой пытается его отгадать, руководствуясь подсказками "больше" или "меньше". Логично предположить, что первым числом будет названо 50, а вторым в случае если оно меньше - 25, если больше - 75. Таким образом, на каждом этапе (иттерации) неопределенность неизвестного уменьшается в 2 раза. Т.е. даже самый невезучий в мире человек отгадает загаданное число в данном диапазоне за 7 предположений вместо 100 случайных утверждений.

Метод половинного деления в решении уравнения

Правильное решение уравнения методом половинного деления возможно лишь в том случае, если известно, что на заданном интервале имеется корень и он является единственным. Это совсем не означает что метод дихотомии может использоваться только для решения линейных уравнений. Для нахождения корней уравнений более высокого порядка методом половинного деления необходимо сначала отделить корни по отрезкам. Процесс отделения корней осуществляется путем отыскания первой и второй производной от функции и приравнивании их нулю f"(x)=0 и f""(x)=0. Далее определяются знаки f(x) в критических и граничных точках. Интервал, где функция меняет знак |a,b|, где f(a)*f(b)< 0.

Алгоритм метода дихотомии

Алгоритм метода дихотомии очень прост. Рассмотрим отрезок |a,b| в пределах которого имеется один корень x 1

На первой этапе вычисляется x 0 =(a+b)/2

Далее определеяется значение функции в этой точке: если f(x 0)< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.

Вычисления прекращаются, когда разность b-a меньше требуемой погрешности.

В качестве примера использования метода половинного деления найдем корень на интервале уравнения x 3 -3*x+1=0 с точностью в 10 -3

Как видно из таблицы корнем является 0,347. Колличество иттераций равно 10. Условие завершения: a-b=0,0009< 10 -3

Метод половинного деления или метод дихотомии является наиболее простым для решения уравнения в численных методах.

Скачать:

Решение уравнения методом дихотомии - Решение уравнения методом половинного деления в Паскале.

Существует довольно очевидная теорема: "Если непрерывная функция на концах некоторого интервала имеет значения разных знаков, то внутри этого интервала у нее есть корень (как минимум, один, но м.б. и несколько)" . На базе этой теоремы построено численное нахождение приближенного значения корня функции. Обобщенно этот метод называется дихотомией , т.е. делением отрезка на две части . Обобщенный алгоритм выглядит так:

Пока не будет достигнута нужная точность.

Варианты метода дихотомии различаются выбором точки деления. Рассмотрим варианты дихотомии: метод половинного деления и метод хорд .

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

Метод половинного деления известен также как метод бисекции . В данном методе интервал делится ровно пополам.

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

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

1. Один из простых способов поиска корней функции одного аргумента .
2. Применяется для нахождения значений действительно-значной функции , определяемому по какому-либо критерию (это может быть сравнение на минимум , максимум или конкретное число).

Метод половинного деления как метод поиска корней функции

Изложение метода

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

Будем считать, что корень функции отделён на отрезке . Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления. Другими словами, требуется найти приближённое значение корня с заданной точностью .

Пусть функция непрерывна на отрезке ,

и - единственный корень уравнения .

(Мы не рассматриваем случай, когда корней на отрезке несколько, то есть более одного. В качестве можно взять и другое достаточно малое положительное число, например, .)

Поделим отрезок пополам. Получим точку и два отрезка .

Новый отрезок делим пополам. Получаем середину этого отрезка и так далее.

Для того, чтобы найти приближённое значение корня с точностью до 0" alt=" \eps >0">, необходимо остановить процесс половинного деления на таком шаге , на котором и вычислить . Тогда можно взять .

Реализация метода на С++ и числовой пример

Решим уравнение методом половинного деления. Графическим методом находим отрезок , которому принадлежит искомый корень. Так как , то принимаем .

Ниже приведен пример программы на Си++ , которая решает поставленную задачу.

Программа 1. Корень уравнения

#include #include using namespace std; const double epsilon = 1e-2 ; double f(double x) { return 4 - exp (x) - 2 * x^ 2 ; } int main() { double a, b, c; a = 0 ; b = 2 ; while (b - a > epsilon) { c = (a + b) / 2 ; if (f(b) * f(c) < 0 ) a = c; else b = c; } cout << (a + b) / 2 << endl; return 0 ; }

Искомый корень . Вычисления проводились с точностью .

Промежуточные вычисления представлены в таблице ниже.

n	a n	b n	c n	b n -c n
1	0	1	0.5	0.5
2	0.5	1	0.75	0.25
3	0.75	1	0.875	0.125
4	0.875	1	0.9375	0.0625
5	0.875	0.9375	0.90625	0.03125
6	0.875	0.90625	0.890625	0.015625
7	0.875	0.890625	0.8828125	0.0078125

Метод половинного деления как метод оптимизации

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

Рассмотрим метод половинного деления как простейший однопараметрический метод безусловной оптимизации. Данный метод является методом прямого поиска . В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.

Дана функция . Необходимо найти , доставляющий минимум (или максимум) функции на интервале с заданной точностью , т.е. найти

.

Запишем словесный алгоритм метода.

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

- константа,

При выводе – координата точки, в которой функция имеет минимум (или максимум), – значение функции в этой точке.

Метод хорд

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

Изложение метода

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

При этом в процессе поиска семейство хорд может строиться:

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

• для случая а):

• для случая б):

Процесс поиска продолжается до тех пор, пока не выполнится условие или .

Метод обеспечивает быструю сходимость, если %200" alt="f(z)\cdot f""(z) > 0">, т.е. хорды фиксируются в том конце интервала , где знаки функции и ее кривизны совпадают.

Схема алгоритма уточнения корня методом хорд представлена на рис. 4.

Комбинация метода хорд и метода половинного деления

Метод хорд можно применить в качестве "последнего штриха" после того, как метод половинного деления гарантирует требуемую точность - это не улучшит существенно гарантируемой точности, но, скорее всего, на несколько порядков повысит точность решения.

Его ещё называют методом дихотомии. Этот метод решения уравнений отличается от выше рассмотренных методов тем, что для него не требуется выполнения условия, что первая и вторая производная сохраняют знак на интервале . Метод половинного деления сходится для любых непрерывных функций f(x) в том числе не дифференцируемых.

Разделим отрезок пополам точкой. Если (что практически наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке (Рис. 3.8), либо на отрезке (Рис. 3.9)

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

Пример 4. Уравнение 5x - 6x -3 = 0 имеет единственный корень на отрезке . Решить это уравнение методом половинного деления.

Решение : Программа на языке Паскаль может быть такой:

function f(x: real): real;

f:=exp(x*ln(5))-6*x-3;

a, b, e, c, x: real;

while abs(b-a)>e do

if f(a)*f(c)<0 then

writeln ("x=",x:3:3," f(x)=",f(x):4:4);

Результат выполнения программы:

e=0.001 x=1.562 f(x)=-0.0047

20.Алгоритм метода половинного деления.

1.Определить новое приближение корня х в середине отрезка [а,b]: х=(а+b)/2.

2.Найти значения функции в точках а и х : F(a) и F(x) .

3.Проверить условие F(a)*F(x) < 0 . Если условие выполнено, то корень расположен на отрезке [а,х] b переместить в точку х (b=х) . Если условие не выполнено, то корень расположен на отрезке [х,b] . В этом случае необходимо точку а переместить в точку х (а=х) .

4.Перейти к пункту 1 и вновь поделить отрезок пополам. Алгоритм продолжить до того времени, пока не будет выполнено условие /F(x)/ < e (заданная точность).

21.Метод простой итерации для поиска корней. Геометрическая интерпретация .

Исходное уравнение f(x)=0 эквивалентными преобразованиями приводится к виду с выделением неизвестного в левой части, то есть x=φ(x),где φ(x) – некоторая функция, связанная с исходной функцией f(x). Такая форма записи уравнения позволяет, задаваясь начальным приближением x 0, получить следующее, первое приближение x 1 =φ(x 0), далее получают второе приближение x 2 =φ(x 1) и так далее x n +1 =φ(x n)…. Последовательность {x n }= x 0, x 1, x 2, …, x n ,… называется последовательностью итераций или приближений с начальным значением x 0. Если функция φ(x) на непрерывна и существует предел ξ = lim x n при n→∞, то, переходя к пределу в равенстве x n +1 =φ(x n), найдем, что при n→ ∞: lim x n +1 =lim φ(x n)=φ(lim x n), то есть ξ=φ(ξ).Следовательно, если последовательность приближений сходится, то она сходится к корню уравнения (2), а значит и уравнения (1). В силу сходимости итерационного процесса этот корень можно вычислить при достаточно большом n с любой заданной точностью. Однако необходимо определить при каких условиях последовательность {x n }будет сходящейся. Получим связь между погрешностями двух соседних приближений - ε n и ε n +1: x n =ξ+ε n , x n +1 =ξ+ε n +1. Подставим эти представления в x n +1 =φ(x n) и разложим функцию в ряд Тейлора в окрестности корня:ξ+ε n +1 =φ(ξ+ε n)=φ(ξ)+ε n φ’(ξ)+(ε n 2 /2!)φ’’(η), где η Î [ξ; ξ+ε n ] Ì .Поскольку ξ - корень, то ξ=φ(ξ) , то получаем: ε n +1 =ε n φ’(ξ)+(φ’’(η)/2)ε n 2 .Так как ε<1, то ε n 2 <<ε n . Поэтому если φ’(ξ) ¹ 0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε n 2 можно пренебречь, то есть ε n +1 » ε n φ’(ξ).Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n |ε n +1 |<|ε n |. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.

Теорема о сходимости метода простых итераций. Пусть ξ - корень уравнения x=φ(x), функция φ(x) определена и дифференцируема на отрезке , причем для x Î все значения функции φ (x) Î . Тогда, если существует такое положительное число q<1, что при x Î выполняется неравенство |φ’(ξ)|≤q<1, то на отрезке уравнение x=φ(x) имеет единственный корень x=ξ и процесс итераций, выраженный формулой x n +1 =φ(x n), где n=1,2,3… , сходится к этому корню независимо от выбора начального приближения x 0 Î .Таким образом, последовательность {x n },начинающаяся с любого x 0 Î , сходится к корню ξ со скоростью геометрической прогрессии, причем скорость сходимости тем выше, чем меньше величина q Î (1;0).Если функция φ(х) монотонно возрастает и 0<φ’(х)<1, то все приближения лежат по одну сторону от корня - такую сходимость называют монотонной (или ступенчатой) – рис.1. Если функция φ(х) монотонно убывает и 0>φ’(х)>-1, то соседние приближения лежат по разную сторону от корня – такую сходимость называют двусторонней (или спиралевидной) – рис.2. Поскольку в этом случае корень заключен в интервале, концами которого являются соседние приближения – ξÎ(x n ,x n +1), то выполнение условия |x n +1 -x n |<ε обеспечивает выполнение условия |ξ-x n +1 |<ε.

Чтобы можно было сравнивать итерационные методы по скорости сходимости, вводят следующие понятия:

Определение 1: Сходимость последовательности {x n } к ξ называется линейной (соответственно, итерационный процесс - линейно сходящимся ), если существует такая постоянная CÎ(0,1) и такой номер n 0 , что выполняются неравенства |ξ-x n +1 |≤C|ξ-x n | для n≥n 0.

Для введенных ранее погрешностей это означает |ε n+1 |≤C|ε n |. В методе простой итерации в роли постоянной C выступает значение q, то есть метод сходится линейно.

Определение 2: Последовательность приближений {x n } сходится к ξ по меньшей мере с р -ым порядком (соответственно, итерационный процесс имеет по меньшей мере p -ый порядок), если найдутся такие константы C>0, p ≥1 и n 0 , что для всех n≥n 0 выполняются условия |ξ-x n +1 |≤C|ξ-x n | р (или в других обозначениях |ε n+1 |≤C|ε n | p).