Реферат: Нахождение корней уравнения методом простой итерации (ЛИСП-реализация)

|X - x ^(k+1) |

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

Имеем

X - x^{( k +1)} = X - S_{k +1} = S_∞ - S_{k +1} = (x^{( k +2)} - ^{( k +1)} ) + (x^{( k +3)} - x^{( k +2)} ) + ... .

Следовательно

|X - x^(k+1) | ≤ |x^(k+2) - ^(k+1) | + |x^(k+3) - x^(k+2) | + ... ≤ q^k+1 |x⁽¹⁾ - x⁽⁰⁾ | + q^k+2 |x⁽¹⁾ - x⁽⁰⁾ | + ... = q^k+1 |x⁽¹⁾ - x⁽⁰⁾ | / (1-q).

В результате получаем формулу

|X - x^(k+1) | ≤ q^k+1 |x⁽¹⁾ - x⁽⁰⁾ | / (1-q). (2.9)

Взяв за x⁽⁰⁾ значение x^(k) , за x⁽¹⁾ - значение x^(k+1) (так как при выполнении условий теоремы такой выбор возможен) и учитывая, что при имеет место неравенство q^k+1 ≤ q выводим:

|X - x^(k+1) | ≤ q^k+1 |x^(k+1) - x^(k) | / (1-q) ≤ q|x^(k+1) - x^(k) | / (1-q).

Итак, окончательно получаем:

|X - x^(k+1) | ≤ q|x^(k+1) - x^(k) | / (1-q). (2.10)

Используем эту формулу для вывода критерия окончания итерационной последовательности. Пусть уравнение x=φ(x) решается методом простой итерации, причем ответ должен быть найден с точностью ε, то есть

|X - x^(k+1) | ≤ ε.

С учетом (2.10) получаем, что точность ε будет достигнута, если выполнено неравенство

|x^(k+1) -x^(k) | ≤ (1-q)/q. (2.11)

Таким образом, для нахождения корней уравнения x=φ(x) методом простой итерации с точностью нужно продолжать итерации до тех пор, пока модуль разности между последними соседними приближениями остается больше числа ε(1-q)/q.

ЗАМЕЧАНИЕ 2.2: В качестве константы q обычно берут оценку сверху для величины

.

2.2 Геометрическая интерпретация

Рассмотрим график функции . Это означает, что решение уравнения и - это точка пересечения с прямой :

Рисунок 3.

И следующая итерация - это координата x пересечения горизонтальной прямой точки с прямой .

Рисунок 4.

Из рисунка наглядно видно требование сходимости . Чем ближе производная к 0, тем быстрее сходится алгоритм. В зависимости от знака производной вблизи решения приближения могут строится по разному. Если , то каждое следующее приближение строится с другой стороны от корня:

Рисунок 5.