Общий алгоритм поиска особенных корней

1. Начало цикла для x, изменяющегося от a до b с шагом h (h £ e).

2. Если f (x) < e, то xn – начало отрезка, на котором вероятно существует особенный корень уравнения f (x) – продолжаем цикл.

3. Если f (x) > e, то xk – конец искомого отрезка.

4. Выводим на экран полученный интервал.

5. Конец цикла.

Общий алгоритм поиска простых корней

1. Начало цикла для x, изменяющегося от a до b с шагом h.

2. Если f (x)× f (x + h) < 0, то на отрезке [ x, x + h ] существует простой корень уравнения f (x).

3. Обращаемся к созданной функции, реализующей выбранный алгоритм, параметрами которой являются: интервал [ x, x + h ], на котором существует корень, вид функции f (x), заданная точность e.

4. Выводим на экран полученное значение.

5. Конец цикла.

Поиск простого корня с заданной точностью e осуществляется одним из итерационных методов. В соответствии с общей методикой, на найденном интервале выбирается m начальных значений (приближений) x ₀, x ₁, …, x_{m -1}, после чего последовательно выполняются вычисления до тех пор, пока не выполнится неравенство | x 1 – x 0| < e (x 0 – значение, найденное на предыдущем шаге, x 1 – найденное значение). Значение x 1, при котором | x 1 – x 0| > e принимается в качестве приближенного значения корня.

Рассмотрим основные итерационные методы поиска корней.

Метод простой итерации

Функцию f (x) записывают в виде разрешенном, относительно x:

x = j(x). (7.1)

Переход от записи исходного уравнения к эквивалентной записи (7.1) можно сделать многими способами, например, положив

j(x) = x + y(x)× f (x), (7.2)

где y(x) – произвольная, непрерывная, знакопостоянная функция (часто достаточно выбрать y = const).

Члены рекуррентной последовательности в методе простой итерации вычисляются по правилу

x_k = j(x_{k -1}); k = 1,2, …

Метод является одношаговым, т.к. для начала вычислений достаточно знать одно начальное приближение x ₀ = a, или x ₀ = b, или x ₀ = (a + b)/2.

Метод Ньютона (метод касательных)

Этот метод является модификацией метода простой итерации и часто называется методом касательных. Если f (x) дважды непрерывно диффе­ренцируемая функция и имеет непрерывную производную. Выбрав в (7.2) y(x) = 1/ f ' (x), получаем эквивалентное уравнение x = x – f (x)/ f ' (x) = j(x), тогда формула для метода Ньютона имеет вид:

x_k = x_{k -1} – f (x_{k -1}) / f ' (x_{k -1}) = j(x_{k -1}), k = 1,2,…

Очевидно, что этот метод одношаговый (m = 1) и для начала вычислений требуется задать одно начальное приближение.

Метод секущих

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

x_k = x_{k -1} – f (x_{k -1})× q / [ f (x_{k -1}) – f (x_{k -1} – q)] = j(x_{k -1}), k = 1,2,…

Здесь q – некоторый малый параметр метода, который подбирается из условия наиболее точного вычисления производной (q = h).

Метод Вегстейна

Этот метод является модификацией предыдущего метода секущих. В нем при расчете приближенного значения производной используется вместо точки x_{k -1} – q ранее полученная точка x_{k -2}. Расчетная формула метода Вегстейна:

x_k = x_{k -1} – f (x_{k -1})×(x_{k -1} – x_{k -2}) / [ f (x_{k -1}) – f (x_{k -2})] = j(x_{k -1}, x_{k -2}), k = 1,2,…

Метод является двухшаговым (m = 2), и для начала вычислений требуется задать 2 начальных приближения x ₀ = a, x ₁ = b.

Функция, реализующая данный метод может иметь вид:

double Metod1(type_f f,double x0,double x1,double eps) {

double y0,y1,x2,de;

y0=f(x0); y1=f(x1);

do {

x2=x1-y1*(x1-x0)/(y1-y0);

de=fabs(x1-x2);

x0=x1; x1=x2; y0=y1; y1=f(x2);

} while (de>eps);

return x2; // Возвращаем значение, для которого достигнута точность

}