Алгоритмы решения задачи нахождения корней полинома: шаговый метод, метод половинного деления, метод Ньютона, метод простой итерации.

Алгоритм метода:

Установить интервал |а,Ь| на начало интервала поиска (а=х0).
Определить координату точки b (b=a+h), а также значе ния функции в точках а и b: F(a) и F(b).
Проверить условие F(a)*F(b)<0. Если условие не выпол нено - передвинуть интервал [а,Ь] на один шаг (а=Ь) и перейти к пункту 2.

Если условие выполнено - закончить алгоритм.

Решением являются координаты точек а и Ь. Отрезок |а,Ь] содержит корень уравнения, поскольку функция F(x) на его концах имеет разные знаки.

Метод половинного деления

Метод основан на последовательном сужении интервала, содержащего единственный корень уравнения F(x)=0 до тех пор, пока не будет достигнута заданная точность к.

Пусть задан отрезок [а,Ь], содержащий один корень уравнения. Этот отрезок может быть предварительно найден с помощью шагового метода.

Алгоритм метода :

Определить новое приближение корня х в середине отрезка [a,b]: x=(a+b)/2.
Найти значения функции в точках а и х: F(a) и F(x).
Проверить условие F(a)*F(x)<0. Если условие выполнено, то корень расположен на отрезке [а,х]. В этом случае необходи мо точку b переместить в точку х (Ь=х). Если условие не выпол нено, то корень расположен на отрезке [х,Ь]. В этом случае необ ходимо точку а переместить в точку х (а=х).
Перейти к пункту 1 и вновь поделить отрезок пополам. Алгоритм продолжить до тех пор, пока не будет выполнено усло вие |F(x)I <e.

Метод Ньютона

Задан отрезок [а,Ь], содержащий корень уравнения F(x)=0. Уточнение значения корня производится путем использования уравнения касательной. В качестве начального приближения задается тот из концов отрезка [а,Ь], где значение функции и ее второй производной имеют одинаковые знаки

(т.е. выполняется условие F(X0)*F"(X0)>0).

В точке F(х₀) строится касательная к кривой у= F(х) и ищется ее пересечение с осью х.

Точка пересечения принимается за новую итерацию. Итерационная формула имеет вид:

Содержание