Решение. Схема алгоритма дихотомии показана на рисунке 3

Схема алгоритма дихотомии показана на рисунке 3

Рисунок 3 – Схема алгоритма дихотомии

Пример 2. Методом половинного деления найти корень уравнения на отрезке [0.05; 1.5] с точностью ε = 0.001. Составить программу.

Решение

Схема алгоритма будет иметь вид, приведённый на рисунке 4.

Вначале задаются значения границ отрезка [ a; b] и точность, с которой должен быть найден корень. Затем вычисляется значение функции в точке а

.

В середине отрезка [ a; b ] (точка x = (a + b)/2) вычисляется функция . Проверка f (a)· f (x) < 0 определяет, имеют ли значения функции на границах отрезка [ a; x ] разные знаки.

Если условие f (a)· f (x) < 0 верно, то корень находится на отрезке [ x; b ].

Если условие f (a)· f (x) < 0 ложно, то корень находится на отрезке [ a; x ].

При этом задаются новые значения для a или b. Таким образом, новый отрезок [а; b] на котором отыскивается корень, становится в 2 раза меньше предыдущего.

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

Рисунок 4 – Схема алгоритма дихотомии

Метод итерации

Пусть задана функция f (x), требуется найти корни уравнения

f (x) = 0.

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

Представим уравнение в виде

x = ψ (x).

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

Рассмотрим последовательность чисел x_i, которая определяется следующим образом:

x_{k +1} = ψ (x_k), x ₀ принадлежит [ a; b].

Метод простых итераций имеет следующую наглядную геометрическую интерпретацию (рисунок 5). Решением уравнения будет абсцисса точки пересечения прямой y = x с кривой y = ψ (x). При выполнении итераций значение функции ψ (x) в точке x_i необходимо отложить по оси абсцисс. Это можно сделать, если провести горизонталь до пересечения с прямой y = x и из точки их пересечения опустить перпендикуляр на ось абсцисс. На рисунке 5 показаны разные ситуации: a) сходимость к корню односторонняя; b) сходимость с разных сторон.

Рисунок 5 – Приближение к корню методом простой итерации

Сходимость процесса приближения к корню в значительной степени определяется видом зависимости ψ (x). На рисунке 6 показан расходящийся процесс, при котором метод простой итерации не находит решения уравнения.

На рисунке 6 расходящийся процесс наблюдается для более быстро меняющейся функции |ψ'(x)| > 1.

Можно сделать вывод, что для обеспечения сходимости метода простой итерации необходимо выполнить условие |ψ'(x)| < 1.

На практике в качестве рассматриваемой окрестности используют интервал [ a; b], а условие сходимости итерационного процесса имеет вид:

|ψ′(x)| < 1.

Рисунок 6 – Расходящийся процесс в методе простой итерации

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

Рисунок 7 – Схема алгоритма простой итерации

Процесс итераций продолжается до тех пор, пока для двух последовательных приближений x_{n +1} и x_n не будет обеспечено выполнение неравенства

| x_n – x_{n – 1}| ≤ ε

где ε – точность вычислений.

Пример 3. Методом итераций уточнить с точностью до 10 ^–4 корень уравнения 5 x ³ – 20 x + 3 = 0, заключённый на отрезке [0; 1].