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

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

A, B, E

X: = (A + B)/2

Определить F (X)

Начало

F (X)∙ F (B) < 0

A:= X

B:= X

| A – B | < E

Печать X

Конец

Нет

Нет

Да

Да

 

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

 

 

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

Решение

Схема алгоритма будет иметь вид, приведённый на рисунке 5.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 раза меньше предыдущего.

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

f (a) = 2 e 1 – a – 3.5 sin a

a = 0.05; b = 1.5; ε = 0.001

Начало

f (a)∙ f (x) < 0

b = x; f (b) = f (x)

| b – a | > ε

Вывод x

Конец

Нет

Нет

Да

Да

x = (a + b)/2

f (x) = 2 e 1 – x – 3.5 sin x

a = x; f (a) = f (x)

 

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

 

[kgl].

 

[gl] Тема 6. Метод итерации в решении уравнений. Схема алгоритма простой итерации. Расходящийся процесс в простой итерации [:]

 

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

f (x) = 0. (6.1)

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

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

x = ψ (x). (6.2)

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

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

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

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

f (x) = 0

y = ψ (x)

x 0

x 1

x 2

x

y

O

y = x

f (x) = 0

y = ψ (x)

x 0

x 1

x 2

x

y

O

y = x

x 3

a)

b)

 

 

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

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

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

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

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

|ψ′(x)| < 1.

x 2

x 1

x 0

x

y

f (x) = 0

y = ψ (x)

y = x

xn

 

 

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

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

 

ε = 0.001

Начало

| f i | < ε

Конец

Нет

Да

Номер итерации i = 0

xi + 1 = ψ(xi)

Ввод начальной точки x 0

i = i + 1

Вывод xi и fi

 

 

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

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

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

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

 

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