Решение алгебраических уравнении и систем. Уточнение корней. Решение систем линейных алгебраических уравнений

16. РЕШЕНИЕ АЛГЕБРАИЧЕСКИХ УРАВНЕНИИ И СИСТЕМ

 Нелинейные алгебраические уравнения

Нелинейные уравнения вида f(x) = 0, где f(x) - нелинейная

функция аргумента х, можно подразделить на две группы:

алгебраические, когда f(x) представима в виде многочлена, и неалгебраические или трансцендентные, когда f(x) является некоторой комбинацией трансцендентных функций типа а^x, ln(х), sin(х) и т.д. В дальнейшем численные методы решения будем рассматривать применительно к алгебраическим уравнениям, поскольку именно они представляют наибольший интерес. Однако это не означает, что данные методы не применимы к решению трансцендентных уравнений, если соблюдены условиях корректной постановки задачи (например, функция f(x) = sin(x) имеет бесконечное число нулей при x = kI , k = 0, 1,2, ..., a f(x) = 2х не имеет ни одного нуля). Итак, стоит задача решения алгебраического уравнения

a₀ + a₁x + a₂x² + ... + a_nxⁿ = 0.               (4.1)

В общем случае и коэффициенты и корни уравнения (4.1) могут быть любыми действительными или комплексными числами. Ограничимся вариантом, когда аi, i принадлежат [0,n] представляют собой действительные числа. При этом корни уравнения (4.1) могут быть действительными либо комплексно-сопряженными, простыми или кратными. Существует достаточно большое количество алгоритмов решения алгебраических уравнений [12]. Разнообразие их связано с отсутствием универсального метода, эффективного для любого вида искомых корней.  Зачастую используются комбинации различных алгоритмов. Например, с помощью одних, достаточно простых алгоритмов, определяется "грубое" приближение корней, а затем посредством других, более сложных, найденное приближение уточняется.

 Отделение корней на интервале изоляции

Будем предполагать, что функция f(x), стоящая в левой части уравнения f(x) = 0,(4.2)имеет только изолированные нули, т.е. такие, вокруг которых существует некоторая окрестность, не содержащая других нулей. Тогда на всем интервале [а,b], где f(x) непрерывна и определена, можно выделить так называемые интервалы изоляции корней - отрезки, на которых содержится только по одному корню. Осуществляется это следующим образом. Интервал [a,b] делится на N отрезков [a_i,b_j]

iÎ[1,N], а далее анализируются знаки f(x) в точках a_i и b_i.. Из математического анализа известно, что если f(a_i)f(b_i) < 0, то на [a_i,b_i], содержится, по крайней мере, один нуль функции f(x). Единственность нуля f(x) на [a_i,b_i]  определяется знакопос-тоянством производной f'(x) на [a_i,b_i]) т.е. если f(ai)*f(bi)<О и f'(x) не изменяет свой знак, значит, внутри [a_i,b_i] находится только один корень уравнения (4.2). Количество интервалов изоляции определяется порядком уравнения.

17. Уточнение корней

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

б < 2е,

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

метод дихотомии очень прост и надежен и к простому корню схо-дится для любых непрерывных и дифференцируемых f(x).

Следует отметить, что описанный метод уточнения корня устой-чив к вычислительным погрешностям.

Недостаток дихотомии - относительно медленная сходимость.

В случае если уравнение (4.2) имеет кратные корни, то применять дихотомию к поиску корней четной кратности вообще не рекомен-дуется, а для корней нечетной кратности метод менее точен и хуже устойчив к вычислительным погрешностям [13].

Метод Ньютона. Высокой скоростью сходимости при уточнении корня обладает метод Ньютона. Рассмотрим одну из модификаций метода Ньютона, известную как метод касательных.

Пусть х0 есть приближенное значение корня х* уравнения (4.2). В предположении, что f(x) непрерывна и дифференцируема, представим ее в виде ряда Тейлора в окрестности точки х0 ограничившись линейной частью ряда

f(x) = f(х₀) + f''(х₀)(x – х₀).

Тогда линеаризованное уравнение (4.2) будет иметь вид