Метод половинного деления
Лабораторная работа №1 «Методы решения уравнений» Выполнил: студент группы Э2 – С10 ФЭ факультета Холькин И.А. Проверил: Чистозвонова Е.А.
Обнинск 2012 Метод половинного деления Предположим, что корень отделён на отрезке [a, b] и знаки f(a) и f(b) различны (функция f(x) меняет знак при переходе через корень x*). Положим a0=a, и b0 =b и вычислим значения функции в левом конце отрезка, f(a0), и в его середине с0=(a0+b0)/2: f(c0). Сравним знаки чисел f(a0) и f(c0). Если эти знаки различны, то корень x* лежит в интервале (a0, c0); если же одинаковы, то тогда различны знаки f(c0) и f(b0)., и корень лежит в интервале (c0, b0). (Возможен ещё случай f(c0)=0; тогда корень x*=с уже найден.) В обоих случаях смены знака корень оказывается отделён на отрезке [a0, c0] либо [c0, b0], длина которого ровно в два раза меньше длины исходного отрезка [a0, b0]= [a, b]. Обозначим этот отрезок половинной длины через [a1, b1] (то есть положим a1=a0; b1=c0 в случае, когда f(a0) и f(c0) разных знаков, и a1=c0; b1=b0 в случае, когда f(a0) и f(c0) одного знака). Далее повторим процесс для отрезка [a1, b1]: снова отыщем его середину c1, найдём значение функции f(c1) и сравним знак этого числа со знаком f(a1); если знаки разные, то корень отделён на [a2, b2]= [a1, c1], если одинаковые, то на [a2, b2]= [c1, b1] (или же оказывается, что f(c1)=0; тогда корень найден). Длина отрезка, на котором отделён корень, уменьшилась ещё в два раза. Поступая тем же образом и далее, получаем, что после k делений длина отрезка, на котором лежит корень, сокращается в 2k раз и становится равной δk =(b-a)/2k ( если корень не был точно определён на каком-то предыдущем этапе, то есть не совпал с ci при некотором i). Пусть ε- заданная точность, с которой требуется отыскать корень. Процесс деления отрезков следует остановить, как только станет верным неравенство 2δk ≤ε. Очевидно, что если при этом положить x**=ck=(b-a)/2 то расстояние от корня x*, лежащего где-то в интервале (ak;bk), до середины этого интервала x** будет не больше ε, то есть приближённое равенство x*≈x** будет выполнено с нужной точностью.
|
