Метод простых итераций (последовательность приближений)
Данный метод является наиболее общий и многие другие методы можно представить как некоторую вариацию метода простых итераций. Пусть необходимо найти корень F (х) =0 на некотором отрезке АВ. Представим уравнение F (х) =0 в виде x = f(x).
Возьмем произвольное значение х0 из области определения функции f(х), х0 Î [АВ], и будем строить последовательность чисел {xn} определенных с помощью рекуррентной формулы: хк+1 = f(xк) х1= f(x0) х2 = f(x1) (2)
Получим итерационную последовательность (2). При её изучении возникают два вопроса:
1. Можно ли процесс вычисления чисел xn продолжать неограниченно, т.е. числа xn будут принадлежать отрезку АВ?
2. Если итерационный процесс хк+1 = f(xк) бесконечен, то как будут себя вести числа xn при n →∞?
Исследование этих вопросов показывает, что при определенном ограничении для функции f(x) итерационная последовательность является бесконечной и сходится к искомому корню уравнения х = f(x); xк→х*, при к →∞.
Метод простых итераций имеет следующую наглядную геометрическую интерпретацию. Решением уравнения f(х) = х, будет абциса точки пересечения прямой у = х с кривой
у = f(х).
1) x0 = 0.2
x1 = f (x0) = f(0.2) = 0.95
2) x1 = 0.95
x2 = f(x1) = f(0.95) = 0.75
3) x2 = 0.75
x3 = f(x2) = f(0.75) = 0.8
Метод Ньютона (касательных).
Зададим некоторое начальное при общем х0 Î [АВ] для функции f(х).
Алгоритм метода Ньютона сводится к меньшему представлению f(х) в окрестности точки х0 с помощью разложения f(х) в ряд Тейлора и решением уравнения f(х) =0.
f(хi +1) = f(хi) + h * f ‘ (xi) + h2 / 2 ! f “ (xi) + h3/3! (xi) f ”’…
Отбросим члена ряда содержащие h2 , h3 , … получим f(хi +1) = f(хi) + * f ‘ (xi).
Если в точке хi +1 экстремуляция функции f(х), тогда значение функции равно нулю: f(хi +1) = 0. f(хi ) + (xi+1 – xi) *f ‘ (xi) = 0.
Отсюда, коэффициенты точки экстремума равны: xi+1 = xi – f(xi) / f ‘ (xi).
Пришли к формуле Ньютона которую можно считать итерационным процессом с итерирующей функцией f(x) = x – f (xi) / f ‘ (xi) (3).
Уравнение (3) является уравнением линии касательной к кривой f(x) из двух крайних точек отрезка АВ.
Улучшение сходимости этого метода по сравнению с предыдущими достигается увеличением затрат на выполнение каждого шага, т.к. в каждом шаге требуется вычислить не только значение функции f(x), но и её производной f ‘(x).
Существует «модифицированный» метод Ньютона, в котором производная вычисляется только один раз xk+1 = xk – f(xk) / f ‘ (x0).
Для того, чтобы точка пересечения касательной с осью ОХ лежала внутри отрезка АВ, т.е. выбирать приближение Х0, надо касательную проводить в том конце отрезка АВ, где знаки функции f(х) и её кривизна f “(х) одинаковы, т.е. выполняется условие: f(х)* f “(х) > 0.
Блок –схеме метода:
Метод хорд.
При решение нелинейного уравнения методом хорд задается интервал АВ, на котором существует только одно решение с точностью Е.
Метод хорд – это смесь метода Половинного деления и метода Касательной. Метод основан на замене функции f(х) на каждом шаге этариционного процесса поиска хордой, пересечение которой с осью абцисс дает приближение корня, т.е. исходный отрезок дается точкой пересечения хордой соединяя точки f(a) и f(b).
= ; x1 = a - ;
Далее через две точки с координатами ( a, f (a)) и (b, f(b)) проводим хорду и определяем точку пересечения этой линии с осью абцисс, получается точка С – это первое приближение, если при этом f(a) *f(c) < 0, тогда правую границу интервала В переносим в точку С. С = В.
Если указанное условие не выполняется, тогда т. С переносится в левую границу интервала А. Далее выбирается из двух частей отрезка та часть, где разные знаки и процесс продолжается.
Процедура выполняется до тех пор, пока │xn+1 - xn│≤ E.