Метод секущих.

Стратегия поиска.

Метод секущих ориентирован на нахождение корня уравнения f(x)=0 в интервале [a,b], в котором имеются две точки, в которых f(a), f(b) < 0. Между этими точками проводится секущая к кривой y= f(x). В качестве следующего приближения выбирается точка пересечения этой секущей с осью абсцисс. Процесс построения секущих и нахождения точек пересечения с осью продолжается до тех пор, пока разность между двумя последовательными приближения не станет меньше .

Геометрически этот способ эквивалентен замене кривой f(x) секущей , проходящей через

Точка пересечения секущей с осью Ox Ох может быть найдена из уравнения:

Полагая у = 0, имеем:

. ищем как пересечение секущей , где , с осью Ox:

,

Полагая опять y=0, имеем:

и т.д.

Каждое очередное приближение к стационарной точке определяется по формуле:

Процесс продолжается до тех пор, пока не выполнится условие окончания поиска:

Примерное количество итераций n, необходимое для вычисления корня с относительной точностью ,определяется неравенством:

Алгоритм.

Шаг 1. На отрезке [a,b] задать начальное приближение и точность вычисления .

Шаг 2. Вычислить очередное приближение по формуле:

, где n=1,2,...

Шаг 3. Повторить процедуру 2 до тех пор, пока , тогда .

Пример.

Задание.

Найти минимум функции на интервале 1<X .

Решение.

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

Стратегия поиска.

Одним из самых эффективных и точных методов уточнения корней нелинейного уравнения является метод Ньютона.

Идея метода Ньютона заключается в том, что в окрестности имеющегося приближения задача f(x) =0 заменяется некоторой вспомогательной линейной задачей. Эта задача выбирается так, чтобы погрешность замены имела более высокий порядок малости, чем первый (порядок малости) в окрестности имеющегося приближения. За следующее приближение принимается решение этой вспомогательной задачи. Рассмотрим разложение функции f(x) в ряд Тейлора до членов 1-го порядка включительно в окрестности точки :

Тогда в качестве вспомогательной задачи берется линейная задача:

Ее решение принимается за следующее приближение к решению исходного уравнения, т.е. итерации ведутся по формуле:

.

Таким образом, метод состоит в замене кривой y= f(x) на касательную к ней в процессе каждой итерации. Это видно из уравнения касательной, проведенной в точке

из которого расчетная формула метода Ньютона получается, если положить y=0.

Достаточные условия сходимости определяются теоремой.

Теорема: Пусть f(х) определена и дважды дифференцируема на отрезке [а,b], причем f(а), f(b)< 0, а производные и сохраняют знак на отрезке [а,b]. Тогда, исходя из начального приближения , удовлетворяющего неравенству , можно построить последовательность

, n=0,1,...

сходящуюся к единственному на отрезке [а,b] решению уравнения .

Для достижения заданной погрешности при использовании метода Ньютона потребуется порядка итераций.

Отметим, что метод Ньютона эффективен, если выбрано хорошее начальное приближение корня и график функции имеет большую крутизну в окрестности корня. В этом случае процесс быстро сходится, со скоростью геометрической прогрессии. Если же численное значение вблизи корня мало, т.е. график почти параллелен оси 0х, то выбор метода Ньютона вряд ли разумен. Отметим также, что если бы f(х) была линейной, то метод Ньютона нашел бы корень за одну итерацию

Алгоритм.

Шаг 1. На отрезке [a,b] задать начальное приближение и точность вычисления

Шаг 2. Вычислить очередное приближение по формуле:

где n=1,2,...

Шаг 3. Повторить процедуру 2 до тех пор, пока , тогда .

Пример.

Задание.

Найти минимум функции положив , .

Решение.