Метод интераций. Метод касательных. Метод хорд.

Метод простых итераций (последовательность приближений)

Данный метод является наиболее общий и многие другие методы можно представить как некоторую вариацию метода простых итераций. Пусть необходимо найти корень F (х) =0 на некотором отрезке АВ. Представим уравнение F (х) =0 в виде x = f(x).

Возьмем произвольное значение х₀ из области определения функции f(х), х₀ Î [АВ], и будем строить последовательность чисел {x_n} определенных с помощью рекуррентной формулы: х_к+1 = f(x_к) х₁= f(x₀) х₂ = f(x₁) (2)

Получим итерационную последовательность (2). При её изучении возникают два вопроса:

1. Можно ли процесс вычисления чисел x_n продолжать неограниченно, т.е. числа x_n будут принадлежать отрезку АВ?

2. Если итерационный процесс х_к+1 = f(x_к) бесконечен, то как будут себя вести числа x_n при n →∞?

Исследование этих вопросов показывает, что при определенном ограничении для функции f(x) итерационная последовательность является бесконечной и сходится к искомому корню уравнения х = f(x); x_к→х^*, при к →∞.

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

у = f(х).

 

1) x₀ = 0.2

x₁ = f (x₀) = f(0.2) = 0.95

2) x₁ = 0.95

x₂ = f(x₁) = f(0.95) = 0.75

3) x₂ = 0.75

x₃ = f(x₂) = f(0.75) = 0.8

 

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

Зададим некоторое начальное при общем х₀ Î [АВ] для функции f(х).

Алгоритм метода Ньютона сводится к меньшему представлению f(х) в окрестности точки х₀ с помощью разложения f(х) в ряд Тейлора и решением уравнения f(х) =0.

f(х_{i +1}) = f(х_i) + h * f ‘ (x_i) + h² / 2 ! f “ (x_i) + h³/3! (x_i) f ”’…

Отбросим члена ряда содержащие h² , h³ , … получим f(х_{i +1}) = f(х_i) + * f ‘ (x_i).

Если в точке х_{i +1} экстремуляция функции f(х), тогда значение функции равно нулю: f(х_{i +1}) = 0. f(х_i ) + (x_i+1 – x_i) *f ‘ (x_i) = 0.

Отсюда, коэффициенты точки экстремума равны: x_i+1 = x_i – f(x_i) / f ‘ (x_i).

Пришли к формуле Ньютона которую можно считать итерационным процессом с итерирующей функцией f(x) = x – f (x_i) / f ‘ (x_i) (3).

Уравнение (3) является уравнением линии касательной к кривой f(x) из двух крайних точек отрезка АВ.

Улучшение сходимости этого метода по сравнению с предыдущими достигается увеличением затрат на выполнение каждого шага, т.к. в каждом шаге требуется вычислить не только значение функции f(x), но и её производной f ‘(x).

Существует «модифицированный» метод Ньютона, в котором производная вычисляется только один раз x_k+1 = x_k – f(x_k) / f ‘ (x₀).

Для того, чтобы точка пересечения касательной с осью ОХ лежала внутри отрезка АВ, т.е. выбирать приближение Х₀, надо касательную проводить в том конце отрезка АВ, где знаки функции f(х) и её кривизна f “(х) одинаковы, т.е. выполняется условие: f(х)* f “(х) > 0.

Блок –схеме метода:

 

 

Метод хорд.

При решение нелинейного уравнения методом хорд задается интервал АВ, на котором существует только одно решение с точностью Е.

Метод хорд – это смесь метода Половинного деления и метода Касательной. Метод основан на замене функции f(х) на каждом шаге этариционного процесса поиска хордой, пересечение которой с осью абцисс дает приближение корня, т.е. исходный отрезок дается точкой пересечения хордой соединяя точки f(a) и f(b).

= ; x₁ = a - ;

Далее через две точки с координатами ( a, f (a)) и (b, f(b)) проводим хорду и определяем точку пересечения этой линии с осью абцисс, получается точка С – это первое приближение, если при этом f(a) *f(c) < 0, тогда правую границу интервала В переносим в точку С. С = В.

Если указанное условие не выполняется, тогда т. С переносится в левую границу интервала А. Далее выбирается из двух частей отрезка та часть, где разные знаки и процесс продолжается.

Процедура выполняется до тех пор, пока │x_n+1 - x_n│≤ E.