Алгоритм МПД:
1. Находим интервал a, b на котором функция меняет свой знак:
f(a)*f(b)<0 (имеет хотя бы один корень)
2. Делим интервал пополам точкой с:
3. Из 2-х полученных интервалов([ a,c ] и [ c,b ]) выбираем тот, на котором происходит смена знака:
f(a)*f(с)<0 - [ a,c ]
f(с)*f(b)<0 - [ c,b ]
4. Повторить пункт 2, если не достигли наперед заданной точности , иначе, если , то идем на пункт 5.
5. В качестве точного решения берём (середина последнего интервала). От этой точки х расстояние до любой другой точки отрезка не превосходит .
Замечание:
В предложенном выше методе мы контролируем точность по х (). Иногда, вместо этого требуется достигнуть заданной точности по y, т.е. , но обычно, под точностью понимается точность по x.
П.3.Модификация МПД – Метод Хорд (МХ).
В отличие от МПД в МХ отрезок мы делим не пополам, а на отрезки, пропорциональные f(a) и f(b).
т.е. искомая точка С – точка пересечения прямой, проходящейчерез т. a и b, с Ох.
Уравнение прямой, проходящей через точки () и ():
Пересечем эту прямую с Ох:
Из 2-х новых интервалов([ a,c ] и [ c,b ]) выбираем тот, на котором происходит смена знака (как и в МПД).
Как мы видим из рисунка, в МПД длина интервала уменьшается вдвое и стремится к нулю, в МХ этого не происходит – длина интервала не стремится к нулю. Один край интервала стоит на месте, а второй двигается к точному решению.
Критерий прерывания из МПД в МХ не работает, поэтому берем универсальный критерий прерывания:
Если , то прекращаем вычисления. В качестве приближенного значения берём .
В принципе, универсальный критерий прерывания можно использовать не только при решении МХ, но и при использовании других методов (в МПД,в итерационных методах решения СЛАУ). Недостаток – мы не можем гарантировать:
и поэтому, если есть возможность избежать использования этого критерия прерывания, выгоднее использовать другой. Но, если ничего не остается, применяем универсальный критерий прерывания.