Метод дихотомии (Метод половинного деления)

Метод половинного деления (дихотомии, бисекции, вилки, проб) отличается от большинства методов тем, что для его сходимости не требуется, чтобы функция f (x) была дифференцируемой, достаточно непрерывности f (x).

Пусть корень уравнения отделен, т.е. имеем, что f (a) и f (b) разных знаков: f (a)∙ f (b)<0, причем на отрезке находится только один корень уравнения, функция f (x) непрерывна на .

Алгоритм вычисления корня уравнения методом дихотомии:

1. Задать концы отрезка а и b, функцию f (x), точность e.

2. Разделить отрезок пополам точкой .

3. В качестве нового интервала изоляции принять ту половину интервала , на концах которой функция имеет разные знаки. Для этого:

а) вычислить значение функции в точках a и с;

б) если F (a)· F (с)<0, то корень находится на интервале . Тогда
b = с. Если условие не выполняется, то корень находится на интервале
и a = с. В обоих случаях получаем новый интервал , длина которого в 2 раза меньше предыдущего интервала.

4. Итерационный процесс повторяется, начиная со второго пункта до тех пор, пока длина не станет равной или меньше e, то есть пока не выполнится условие .

Получим последовательность отрезков , на концах которых выполняется неравенство . Последовательность является монотонной неубывающей ограниченной последовательностью; а – монотонной невозрастающей ограниченной последовательностью. Следовательно, существует предел: . Тогда . Отсюда , т.е. является корнем уравнения , причем .

Метод половинного деления практически удобно применять для грубого нахождения приближенного корня данного уравнения, так как при увеличении точности значительно возрастает объем вычислительной работы.

Контрольные вопросы

1. Метод хорд.

2. Метод Касательных.

3. Метод итераций.

4. Интерполяционный многочлен Лагранжа.

Тема.5.2. Численное интегрирование дифференциальных уравнений.
Метод Эйлера. Метод Рунге – Кутта.

Цели занятия:

Должен уметь: Используя метод Эйлера и Рунге – Кутта находить значения функции.

Должен знать: Метод Эйлера. Метод Рунге – Кутта.

Метод Эйлера

Известно, что уравнение задает в некоторой области поле направлений. Решение этого уравнения с некоторыми начальными условиями дает кривую, которая касается поля направлений в любой точке.

Если взять последовательность точек х ₀, х ₁, х ₂, …. и заменить на получившихся отрезках интегральную кривую на отрезки касательных к ней, то получим ломаную линию.

M ₂

M ₁ M ₃

M ₀

y ₀ M ₄

0 x ₀ x ₁ x ₂ x ₃ x ₄ x

При подстановке заданных начальных условий (х ₀, у ₀) в дифференциальное уравнение получаем угловой коэффициент касательной к интегральной кривой в начальной точке

Заменив на отрезке [ x ₀, x ₁] интегральную кривую на касательную к ней, получаем значение

Производя аналогичную операцию для отрезка [ x ₁, x ₂], получаем:

Продолжая подобные действия далее, получаем ломаную кривую, которая называется ломаной Эйлера.

Можно записать общую формулу вычислений:

Если последовательность точек х_i выбрать так, чтобы они отстояли друг от друга на одинаковое расстояние h, называемое шагом вычисления, то получаем формулу:

(19)

Следует отметить, что точность метода Эйлера относительно невысока. Увеличить точность можно, конечно, уменьшив шаг вычислений, однако, это приведет к усложнению расчетов. Поэтому на практике применяется так называемый уточненный метод Эйлера или формула пересчета.

Суть метода состоит в том, что в формуле вместо значения берется среднее арифметическое значений и . Тогда уточненное значение:

Затем находится значение производной в точке . Заменяя средним арифметическим значений и , находят второе уточненное значение у ₁. затем третье: и т.д. пока два последовательных уточненных значения не совпадут в пределах заданной степени точности. Тогда это значение принимается за ординату точки М ₁ ломаной Эйлера.

Аналогичная операция производится для остальных значений у.

Метод Рунге-Кутта

Метод Рунге-Кутта является более точным по сравнению с методом Эйлера.

Суть уточнения состоит в том, что искомое решение представляется в виде разложения в ряд Тейлора.

Если в этой формуле ограничиться двумя первыми слагаемыми, то получим формулу метода Эйлера. Метод Рунге-Кутта учитывает четыре первых члена разложения.