Студопедия

КАТЕГОРИИ:

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



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




Читайте также:
  1. Amp; Методичні вказівки
  2. Amp; Методичні вказівки
  3. Amp; Методичні вказівки
  4. Amp; Методичні вказівки
  5. Amp; Методичні вказівки
  6. Amp; Методичні вказівки
  7. Amp; Методичні вказівки
  8. B. Искусственная вентиляция легких. Методики проведения искусственной вентиляции легких
  9. Cтруктуры внешней памяти, методы организации индексов
  10. FDDI. Архитектура сети, метод доступа, стек протоколов.

Алгоритм метода зависит от свойств функции 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; просмотров: 5; Нарушение авторских прав





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