12. Решение нелинейных уравнений. Метод хорд.

Если в методе секущих (2) вместо точки взять точку , получаем метод хорд k=1,2,… (4)Метод - двухшаговым, требует, чтобы 1 из концов отрезка, на котором ищется решение, был неподвижен. В качестве неподвижного конца отрезка выбирается тот, для которого знак функции совпадает со знаком ее второй производной.

Если f(a)*f(b)<0, т.е. известно, что на отрезке [a,b] существует корень уравнения f(x)=0, то целесообразно использовать метод хорд в следующем виде:

1.если для нужно взять , тогда

2.если для , нужно взять , тогда

Т.о. в методе хорд кривая f(x) заменяется хордами, проходящими через концы отрезка, на котором эта кривая y=f(x) имеет разные знаки. За начальное приближение берем один из концов отрезка, на котором функция имеет знак противоположный знаку второй производной. На втором конце отрезка значение функции – это неподвижная точка. Последовательность приближений к корню х* будет монотонной и односторонней - располагается по ту сторону от корня, где выбрано начальное приближение.

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

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

13. Метод парабол.

Методы, использующие исключение отрезков, основаны на сравнении функций в 2х точках пробного отрезка, учитываются лишь значения функции в этих точках.

Учесть информацию о значениях функции между точками позволяют методы полиномиальной аппроксимации. Их основная идея заключена в том, что функция Φ(u) аппроксимируется полиномом, а точка его минимума служит приближением к u*. Разумеется, в этом случае кроме свойства унимодальности (т.е. наличия единственного минимума на рассматриваемом отрезке), необходимо на Φ(u) наложить и требования достаточной гладкости для ее полиномиальной аппроксимации.

Для повышения точности поиска u* можно как увеличивать степень полинома, так и уменьшать пробный отрезок. Поскольку первый прием приводит к заметному увеличению вычислительной работы и появлению дополнительных экстремумов, обычно пользуются полиномами второй (метод парабол) или третьей (метод кубической интерполяции) степени.

Алгоритм поиска минимума состоит в следующем.

Выбираем на пробном отрезке три точки u1, u2, u3 такие, что u1 < u2 < u3 и .

Построим параболу (квадратичный полином)

Q(u) = a0 + a1 (u - u1) + a2 (u - u1)(u - u2),

график которой проходит через точки (u1,f(u1)), (u2,f(u2)), (u3,f(u3)).

Коэффициенты ak, k = 1, 2, 3 находим из системы уравнений

Q(u1) = f(u1),

Q(u2) = f(u2),

Q(u3) = f(u3),

откуда

Точку минимума Q(u) находим, приравнивания его производную к нулю:

Далее полагаем: (очередное приближение точки минимума). Эту процедуру можно продолжить до достижения необходимой точности, выбирая новые точки uk, k = 1, 2, 3. Для этого можно использовать методы исключения отрезков, используя в качестве двух пробных точек u2 и , таких, что u2, .