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

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

Предположим, что уравнение f(x) = 0 при помощи некоторых тождественных преобразований приведено к виду x = φ(x).

Заметим, что такое преобразование можно вести разными способами, и при этом будут получаться разные функции φ(x) в правой части уравнения. Уравнение f(x) = 0 эквивалентно уравнению x =x + λ(x) f(x) при любой функции λ(x) ≠ 0. Таким образом, можно взять φ(x) = x + λ(x) f(x) и при этом выбрать функцию (или постоянную) λ(x) так, чтобы функция φ(x) удовлетворяла тем свойствам, которые понадобятся нам для обеспечения нахождения корня уравнения.

Для нахождения корня уравнения x = φ(x) выберем какое-либо начальное приближение x0 (расположенное, по возможности, близко к корню x*). Далее будем вычислять последующие приближения

x1, x2,… ,xi, xi+1,…

по формулам

x1 = φ(x0); x2 = φ(x1);…; xi = φ(xi-1); xi+1 = φ(xi); …

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

Для практической реализации метода важны утверждения следующей теоремы.

Теорема.   Если функция φ(x) имеет производную в некоторой окрестности E корня x* уравнения x = φ(x), причём |φ'(x)| ≤ γ <1 при x є E, то последовательность итераций xi+1 = φ(xi), полученных при i = 1, 2, 3…, начиная с x0 є E, сходится к корню x*.

При этом скорость сходимости задаётся неравенствами

|xi – x*| ≤ γi|x0 – x*|, i = 1, 2, 3…,

|xi+1 – xi | ≤ 4δ γi,

где 2δ – длина окрестности E, а точность i-го приближения – оценкой

|xi – x*| ≤ 2δ γi.

Таким образом, для достижения необходимой погрешности нужно использовать последнее неравенство этой теоремы. Если выполнено 2δ γ i < ε, то и |xi – x*|< ε. Константа γ может быть получена путём нахождения максимума модуля производной функции φ(x) на начальном интервале E.

Задание № 5

отлично

Реализуйте программу поиска корней функционального уравнения f(x) = 0 методом простых итераций. Программа должна вести расчёт для заданной последовательности погрешностей – εi таких, что найденный приблизительно корень xi отличается от точного корня уравнения на величину меньшую εi.

Результаты всех вычислений выводить на монитор в следующем формате

ε 1 = 0.1; ­ корень = 0.4654; число итераций – 16

ε 2 = 0.01­; корень = 0.4784; число итераций – 20

ε 3­ = 0.001; корень = 0.4760; число итераций – 40

ε 4 ­ ­ = 0.0001; корень = 0.4762; число итераций – 54

…. и т. п.

хорошо

Реализуйте программу поиска корней функционального уравнения f(x) = 0 методом простых итераций. В программе задается последовательность числа итераций – 8; 16; 32; 64; 128.

Результаты всех вычислений выводить на монитор в следующем формате

i=8; ­ корень = 0.4654

i=16; корень = 0.4784

i=32; корень = 0.4760

i=­ 64; корень = 0.4762

…. и т. п.

ЗАМЕЧАНИЕ

Обычно, если определена область [a;b], содержащая единственный корень, то начальное приближение x0 обычно выбирают в соответствии со следующей формулой

x0 = (a+b)/2

вариант 1

, единственный корень уравнения находится в области [2; 3],

с точностью ε = 5e–2; 2e–3; 1e–4;5e–5; 2e–6

вариант 2

, единственный корень уравнения находится в области [0; 1]

с точностью ε = 1e–1; 1e–2; 1e–3; 1e–4; 1e–5;

вариант 3

, единственный корень уравнения находится в области [0; 1]

с точностью ε = 2e–2; 8e–4; 8e–5; 1e–5; 1e–6;

вариант 4

, единственный корень уравнения находится в области [0; 1]

с точностью ε = 8e–2; 1e–2; 1,2e–3; 1,5e–4; 1,8e–5;

вариант 5

, единственный корень уравнения находится в области [1,2; 2]

с точностью ε = 6e–2; 5e–3; 4e–4; 3e–5; 2e–6;

вариант 6

, единственный корень уравнения находится в области [0; 1,5]

с точностью ε = 1e–1; 0,8e–2; 0,7e–3; 0,6e–4; 0,5e–5;

Метод Ньютона (метод касательных)

Необходимо найти корень уравнения

f(x) = 0.

Формула итераций имеет следующий вид

,

где – производная функции f(x) в точке xi.

Сколько нужно выполнить итераций, чтобы нас могла устроить точность приближение xi+1 к значению корня x* (то есть |xi+1 - x*| < e )?

Обычно считают, что требуемая точность достигнута, если после вычисления xi+1 при выполнении очередной итерации соблюдается условие

|xi+1 – xi |< e .

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

Пример :

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

Применяя эту формулу, последовательно находим:

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

Задание № 6

Реализуйте программу поиска корней функционального уравнения f(x) = 0 методом Ньютона. В программу с клавиатуры должна вводиться последовательность погрешностей – εi такая, что найденный приблизительно корень xi отличается от точного корня уравнения на величину меньшую ε.

Результаты всех вычислений выводить на монитор в следующем формате

для ε 1 ­ – корень = 0.4654

для ε 2 ­ – корень = 0.4784

для ε 3­ – корень = 0.4760

для ε 4 ­ – корень = 0.4762

…. и т. п.

Для оценки ОТЛИЧНО необходимо самим придумать модификацию метода Ньютона для случая, когда значения производной нам неизвестны. Модификация программы должна быть легко программируемой и иметь меньшую трудоёмкость, чем метод простых итераций

вариант 1

0,1x2– x ln(x) = 0, единственный корень уравнения находится в области [1; 2],

с точностью ε = 1e–1; 1e–2; 1e–3; 1e–4; 1e–5;

вариант 2

x – cos(x) = 0, единственный корень уравнения находится в области [0; 1]

с точностью ε = 6e–2; 5e–3; 4e–4; 3e–5; 2e–6;

вариант 3

, единственный корень уравнения находится в области [3; 4]

с точностью ε = 6e–2; 5e–3; 4e–4; 3e–5; 2e–6;

вариант 4

, единственный корень уравнения находится в области [1; 3]

с точностью ε = 1e–1; 0,8e–2; 0,7e–3; 0,6e–4; 0,5e–5;

вариант 5

, единственный корень уравнения находится в области [1; 3]

с точностью ε = 1e–2; 1e–3; 1e–4;1e–5; 1e–6;

вариант 6

, единственный корень уравнения находится в области [0,4; 1]

с точностью ε = 2e–2; 5e–3; 2e–4; 5e–5; 2e–6.