Общий алгоритм поиска особенных корней
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 0, x 1, …, xm -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). Члены рекуррентной последовательности в методе простой итерации вычисляются по правилу xk = j(xk -1); k = 1,2, … Метод является одношаговым, т.к. для начала вычислений достаточно знать одно начальное приближение x 0 = a, или x 0 = b, или x 0 = (a + b)/2. Метод Ньютона (метод касательных) Этот метод является модификацией метода простой итерации и часто называется методом касательных. Если f (x) дважды непрерывно дифференцируемая функция и имеет непрерывную производную. Выбрав в (7.2) y(x) = 1/ f ' (x), получаем эквивалентное уравнение x = x – f (x)/ f ' (x) = j(x), тогда формула для метода Ньютона имеет вид: xk = xk -1 – f (xk -1) / f ' (xk -1) = j(xk -1), k = 1,2,… Очевидно, что этот метод одношаговый (m = 1) и для начала вычислений требуется задать одно начальное приближение. Метод секущих Данный метод является модификацией метода Ньютона, позволяющей избавиться от явного вычисления производной путем ее замены приближенной формулой: xk = xk -1 – f (xk -1)× q / [ f (xk -1) – f (xk -1 – q)] = j(xk -1), k = 1,2,… Здесь q – некоторый малый параметр метода, который подбирается из условия наиболее точного вычисления производной (q = h). Метод Вегстейна Этот метод является модификацией предыдущего метода секущих. В нем при расчете приближенного значения производной используется вместо точки xk -1 – q ранее полученная точка xk -2. Расчетная формула метода Вегстейна: xk = xk -1 – f (xk -1)×(xk -1 – xk -2) / [ f (xk -1) – f (xk -2)] = j(xk -1, xk -2), k = 1,2,… Метод является двухшаговым (m = 2), и для начала вычислений требуется задать 2 начальных приближения x 0 = a, x 1 = 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; // Возвращаем значение, для которого достигнута точность } Метод деления отрезка пополам Все вышеописанные методы могут работать, если функция f (x) является непрерывной и дифференцируемой вблизи искомого корня. В противном случае они не гарантируют получение решения. Для разрывных функций, а также, если не требуется быстрая сходимость, для нахождения простого корня на интервале [ a, b ] применяют надежный метод деления отрезка пополам. Идея метода: в качестве начального приближения выбираются границы интервала, на котором находится простой корень x 0 = a, x 1 = b; далее находится его середина x 2 = (x 0 + x 1)/2. Очередная точка выбирается как середина того из смежных с x 2 интервалов [ x 0, x 2] или [ x 2, x 1], на котором находится корень. Функция, реализующая данный метод приведена в примере, а блок-схема приведена на рис 7.1.
|
