Метод хорд

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

При этом в процессе поиска семейство хорд может строиться:

а) при фиксированном левом конце хорд, т.е. z=a, тогда начальная точка х₀=b (рис. 4.10а);

б) при фиксированном правом конце хорд, т.е. z=b, тогда начальная точка х₀=a (рис. 4.10б);

Рис. 4.10. 

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

для случая а)

(4.11)

для случая б)

(4.12)

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

(4.13)

Метод обеспечивает быструю сходимость, если f(z)f"(z) > 0, т.е. хорды фиксируются в том конце интервала [a,b], где знаки функции f(z) и ее кривизны f"(z) совпадают.

Схема алгоритма уточнения корня методом хорд 

Пример программы:

double f(double x)

{

return sqrt(fabs(cos(x))) - x; // Заменить ф-ей, корни которой мы ищем

}

// a, b - пределы хорды, epsilon - необходимая погрешность

double findRoot(double a, double b, double epsilon)

{

while(fabs(b - a) > epsilon)

{

a = b - (b - a) * f(b)/(f(b) - f(a));

b = a - (a - b) * f(a)/(f(a) - f(b));

}

// a - i-1, b - i-тый члены

return b;

}

9. Численное решение уравнения методом Ньютона (касательных). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Метод Ньютона (метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции.

Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации.

Метод обладает квадратичной сходимостью.

Геометрический смысл метода Ньютона состоит в том, что на каждом шаге мы строим касательную к графику в точке очередного последовательного приближения Xn, а за следующее приближение Xn+1 берём точку пересечения этой касательной с осью . Тем самым наклон прямой подстраивается на каждом шаге наилучшим образом.

Значение корня новой итерации вычисляется по формуле

Алгоритм

1. Задается начальное приближение x₀.

2. Пока не выполнено условие остановки, в качестве которого можно взять или(то есть погрешность в нужных пределах), вычисляют новое приближение:[1].

Достоинства метода Ньютона: Метод Ньютона - самый быстрый способ нахождения корней уравнений: обычно заданная точность достигается за 2-3 итерации. Очень быстрая сходимость по сравнению с методом половинного деления и методом простой итерации к заданной точности.

Недостаток: громоздкий алгоритм: на каждой итерации необходимо вычислять значение функции и ее первой производной.

10. Численное решение уравнения модифицированным методом Ньютона. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Модифицированный метод Ньютона

Модификация метода Ньютона заключается в замене производной f’(x_n) в точке x_n в формуле

на производную f’(x₀) в точке x₀, т.е. полагаем f’(x_n)≈f’(x₀). В результате получим

 (). (3.23)

Геометрически этот способ означает, что мы заменяем касательные в точках B_n прямыми, параллельными касательной к кривой y=f(x) в точке B₀ (см. рис.3).

Рис.3. Модифицированный метод Ньютона

Здесь не надо вычислять каждый раз производную f’(x_n). Сходимость процесса (3.23) обеспечивается следующей теоремой.

Теорема 6. Пусть на [a,b] задана дважды дифференцируемая функция f(x), причем выполнены след. условия

а) f(a)f(b)<0

б) f’(x) и f’’(x)≠0 и сохраняют знаки на [a,b].

Тогда исходя из начального приближения  удовлетворяющего неравенству

f(x₀)f’’(x₀)>0

можно вычислить модифицированным методом Ньютона единственный корень ξ с любой степенью точности.

Доказательство: Пусть f’(x)>0, f’’(x₀)>0 (см.рис.3) Тогда в качестве x₀ берем точку x₀=b, так как  f(b)f’’(b)>0. Из (3.23) следует, что x_n+1<x_n, то есть последовательность {x_n} является убывающей

b=x₀>x₁>…>x_n>a (3.24)

Покажем теперь, что эта последовательность имеет предел ξ. Пусть x_n-1> ξ. Докажем, что x_n> ξ. Для этого запишем n-ое приближение, полученное по формуле Ньютона (см. формулу (3.17)) и по модифицированной формуле Ньютона (3.23)

и найдем разность

. (3.25)

Из теории выпуклых функций известно, что если f’’(x) и сохраняет знак на [a,b], то f(x)является выпуклой. Для выпуклой функции f(x) производная f’(x) является неубывающей, то есть для . Поэтому

. (3.26)

С учетом (3.26) из (11) следует  . Из теоремы 5 сходимости метода Ньютона мы получали , поэтому . Отсюда

ξ≤x_n. (3.27)

Таким образом, из (3.24) и (3.27) получили убывающую сходящуюся последовательность

x₀>x₁>…>x_n≥ξ.

Следовательно, для любого сколь угодно малого ε>0 можно указать такое n, что

|x_n-ξ|< ε. Теорема доказана.

Сходимость метода. В отличие от метода Ньютона здесь сходимость уже не будет квадратичной. Действительно, из (3.23) имеем

. (3.28)

Подставляя (3.21) в (3.28), получим

 (3.29)

Здесь появился линейный член относительно (ξ-x_n-1). При | ξ –x_n-1| << 1 вторым слагаемым в правой части (3.29) можно пренебречь, в результате получим

,

где ,  .

Таким образом, сходимость модифицированного метода Ньютона будет линейной с параметром сходимости .