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

Метод простой итерации
Рассмотрим уравнение вида х=f(х) с корнем t, отделенным на отрезке [а;b].
Функция f предполагается непрерывной на этом отрезке.
Уравнение можно получить из исходного уравнения: f(x) = 0 путем эквивалентных преобразований.

Метод простой итерации
Пример.
Уравнение х3–3х+1=0 представляется в виде х=f(х) разными способами. Например:

Метод простой итерации
Метод простой итерации является одним из наиболее удобных и эффективных методов приближенного решения уравнений. Он основан на многократном применении итерационной формулы xn+1=f(xn) до тех пор, пока соблюдается условие |xn+1–xn| ≥ e, где e — заданная погрешность вычисления корня.
Итерационный процесс сходится (т. е. xn→t при n→∞), если соблюдается условие f'(x)<1 на отрезке [a;b].

Пример
Используем метод простой итерации для решения уравнения
с точностью
Преобразуем уравнение к виду:

Пример
Нетрудно убедиться, что корень уравнения находится на отрезке
Вычислив значения f(x) на концах отрезка, получим:
т. е. функция на концах отрезка имеет разные знаки, поэтому внутри отрезка есть корень.

Пример

Пример
Подсчитаем первую и вторую производные функции
Так как на отрезке
то производная монотонно возрастает на этом отрезке и принимает максимальное значение на правом конце отрезка, т. е. в точке

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

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

Пример
Критерий окончания выполняется при n=5
Приближенное значение корня с требуемой точностью

Пример 2.
Решить методом простой итерации уравнение на отрезке
с точностью 0,025.
Для решения исходное уравнение приводится к виду
Для выбора величины λ используем формулу
Тогда расчетная формула имеет вид

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

Задания
1. Отделите корни уравнения 3cos x=x+1.
2. Составьте программу, реализующую метод простой итерации, и уточните корень уравнения x–sinx–0,25=0 на отрезке [1,1;1,2] с точностью до 0,001.

Метод деления отрезка пополам (метод дихотомии)
Пусть корень t отделен на отрезке [а;b]. Требуется найти приближенное значение корня с точностью до e. Функция f непрерывна на [а;b] и имеет разные знаки в точках a и b (для определенности примем f(a)>0).

Метод деления отрезка пополам (метод дихотомии)
Метод деления отрезка пополам реализуется следующим алгоритмом:
1. Находим xi=(a+b)/2.
2. Вычисляем f(xi).
3. Если f(xi)>0, задаем a=x, иначе b=x.
4. Проверяем условие b–a > e. Если оно выполняется, идем к п.1, если не выполняется, заканчиваем вычисления и считаем, что t=xi с заданной точностью e.

Метод деления отрезка пополам (метод дихотомии)
Число итераций при использовании этого метода
значительно, и поэтому сходимость его медленная. Однако при любой ширине отрезка [а;b] сходимость гарантирована. Кроме того метод половинного деления дает простой и удобный алгоритм уточнения корней с любой наперед заданной степенью точности. Он требует от функции f выполнения легко проверяемых свойств: непрерывности на отрезке изоляции корня и разных знаков значений на его концах.

Метод деления отрезка пополам (метод дихотомии)
Пример.
Единственный корень t уравнения х3–х–1=0 расположен на отрезке [1;2] (проверьте графически!). Необходимо уточнить t с заданной точностью a=0,001. Можно применить метод половинного деления, поскольку функция f(x)=х3–х–1 непрерывна на этом отрезке и на его концах принимает значения разных знаков: f(1) = –1 < 0, f(2)=5> 0.

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

Пример.
На концах этого отрезка функция принимает значения с разными знаками:
Найдем число n делений отрезка [1, 2], необходимых для достижения требуемой точности. Имеем:

Пример
Следовательно, не позднее 6-го деления найдем с требуемой точностью,
Результаты вычислений представлены в таблице