Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Метод применим только для монотонных функций.




Алгоритм метода зависит от свойств функции f(x) .

Если f(b)f’’(b)>0, то строящаяся на каждом этапе хорда имеет правый фиксированный (закрепленный) конец. Для определенности f’’(x)>0 (обратный случай сводится к первому, если записать уравнение –f(x)=0). Тогда кривая y=f(x) будет выпукла вниз, т. е. расположена ниже своей хорды (см. рис.1).

 

 
 

 

 


Рис.1

 

 

Итак, если f(b)>0, то алгоритм выглядит следующим образом:

Применяя этот прием к тому из отрезков [a, x1] или [x1, b], на концах которого функция f(x) имеет противоположные знаки, получим второе приближение корня x2 и т. д. При этом последовательность x1, x2, будет приближаться к корню слева,
качестве x0 можно выбрать начало отрезка точку а).

Если f(a)f’’(a)>0, то строящаяся на каждом этапе хорда имеет левый фиксированный конец и алгоритм выглядит следующим образом:

При этом последовательность x1, x2, будет приближаться к корню справа, в качестве x0 можно выбрать точку b)

Приведем формулу оценки абсолютной погрешности приближенного значения хi , если известны два последовательных значения xi и xi+1.

Теоретически доказано, что если первые производные на концах интервала при монотонной и выпуклой функции f(x) не различаются более, чем в два раза, то справедливо соотношение |x* - xi | < |xi - xi-1| и условием прекращения итераций может быть |xi - xi-1 | £ e, а в качестве корня принято xi+1 (можно также окончить процесс и при достижении f(xi) £e). Таким образом, как только будет обнаружено, что

|xi - xi-1 | £ e,
где e - заданная погрешность, то гарантировано, что |x - xi | £ e.

 

3. Метод Ньютона
(метод касательных или метод линеаризации).

Одним из лучших общих методов решения уравнения f(x)=0 является метод Ньютона. Если есть некоторое приближение xi к решению x*, то метод Ньютона аппроксимирует функцию f(x) касательной к ее графику в точке xi . Точка пересечения касательной с осью абсцисс принимается за новое приближение. Метод Ньютона часто работает так, как показано на рис. 2 и приближения быстро сходятся к решению.

 

 


Рис. 2

Для вывода формул метода Ньютона разложим функцию f(x) в ряд Тейлора
в точке xi:

f(x) =f (xi) + f’(xi)(x - xi ) +…

Касательная задается при помощи первых двух членов ряда

Y = f(xi) + f’(xi)( x- xi )

Полагая y=0, получаем: xi+1 = xi - f(xi)/f’(xi).

В качестве начальной точки в зависимости от свойств функции берется или левая точка х0 =a, (если f(a) f’’(a) > 0),

или правая точка x0=b, (если f(b) f’’(b) > 0)., т.е. итерации сходятся к корню с той стороны, с которой f(x) f’’(x) > 0.

Метод Ньютона хорош тем, что быстро сходится, точнее, имеет квадратичную скорость сходимости.

Однако метод Ньютона не всегда работает так хорошо. Он может и не сходиться, например, если f’(xi)=0, метод не определен.

Если f’(xi)»0, могут возникнуть трудности, так как новое приближение xi+1 может оказаться значительно худшим, чем xi.

Еще одним недостатком метода Ньютона является необходимость вычисления f’(x). В ряде случаев можно применять упрощенный алгоритм – вместо вычисления производной в каждой точке f’(xi) использовать значение в начальной точке f’(x0).

 


Поделиться:

Дата добавления: 2014-12-03; просмотров: 96; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты