16 Численные методы решение алгебраических уравнений: метод половинного деления. Метод половинного деления

Для применения метода половинного деления необходимо установить окрестность или отрезок [a, b], на котором расположен один из корней уравнения, который необходимо уточнить с погрешностью Е (рис.2.1).

Рис. 2.1. Метод половинного деления.

Пусть дано уравнение , где непрерывна на отрезке [a, b] и .

Метод половинного деления, или дихотомии, заключается в следующем. Для нахождения корня уравнения, принадлежащего отрезку [a, b], делим отрезок пополам, т.е. выбираем начальное приближение, равное:

и вычисляем значение функции . Если , то является корнем уравнения. Если , то выбираем, одну из двух частей отрезка или для дальнейшего уточнения корня. Естественно, что корень будет находиться в той половине отрезка, на концах которого функция имеет разные знаки, а именно проверяем условие: . На рис.2.1 это будет отрезок , т. е. для очередного шага уточнения точку b перемещаем в середину отрезка (b= ) и продолжаем процесс деления как с первоначальным отрезком [a, b].

Итерационный (повторяющийся) процесс деления будет продолжаться до тех пор, пока не будет выполнено условие:

.

За приближенное решение принимается средняя точка последнего промежутка.

Таким образом, для реализации метода дихотомии необходимо:

1. Задать в явном виде уравнение , корни которого необходимо определить.

2. Определить начальный интервал [a, b], внутри которого лежит корень.

3. Задать точность нахождения корня уравнения .

4. Реализовать в программе итерационную процедуру, описанную выше.

17 Численные методы решение алгебраических уравнений: метод хорд

18 Численные методы решение алгебраических уравнений: метод Ньютона, модифицированный метод Ньютона. Метод Ньютона

П редположим, что у нас определено начальное приближение х₀ к одному из корней уравнения (2.1). Тогда в точке х₀ можно вычислить левую часть решаемого уравнения .

Рис.2.2. Метод Ньютона

Рассмотрение метода Ньютона начнем с его геометрического представления (рис. 2.2). Возьмем точку х₀ отрезка [a, b] и проведем в точке P₀ с координатами касательную к кривой y= до пересечения с осью 0х. Получим значение х₁, в котором касательная пересекает ось 0x. Угловой коэффициент касательной равен значению производной от функции в точке касания. Следовательно, уравнение касательной, проходящей через точку с координатами имеет вид :

.

Полагая y=0, находим точку пересечения касательной с осью 0х, которую обозначим через х₁:

Абсциссу х₁ точки пересечения можно взять в качестве приближенного значения корня. Проведя касательную через новую точку с координатами и находя точку ее пересечения с осью 0х, получим второе приближения корня х₂ . Аналогично определяются последующие приближения.

Следующие приближения находим соответственно по формулам:

……………………

В общем случае для k-го шага итерационного процесса последнее соотношение принимает вид:

(2.2)

Из формулы (2.2) вытекает необходимость вычисления значения производной функции в каждой точке. Процесс нахождения корня может считаться законченным, когда модуль отношения значения функции в точке x_k к ее производной меньше заданной величины погрешности , т.е. когда выполняется следующее условие:

(2.3)

Таким образом, для реализации метода Ньютона необходимо:

Задать в явном виде уравнение , корни которого необходимо определить.

Определить первую производную функции в аналитическом виде.

Определить начальное приближение х₀, обеспечивающее быструю сходимость метода.

Задать точность нахождения корня уравнения .

Реализовать в программе итерационную процедуру, реализующую формулу (2.2).