Методы решения нелинейных систем уравнений

Для уточнения корней систем нелинейных уравнений наиболее часто используют методы итерации (метод простой итерации и метод Зейделя) и метод Ньютона. Как и в случае уточнения корней одного нелинейного уравнения, для систем нелинейных уравнений требуется определение хорошего начального приближения (отделение корня), гарантирующего сходимость метода и высокую скорость ходимости. Для системы двух уравнений это может быть сделано графически, но для систем высоких порядков удовлетворительных методов отделения корней не существует.

Метод простой итерации

Систему нелинейных уравнений запишем в векторной форме

f(x) = 0 (3.10)

где - вектор-столбец неизвестных, - вектор-столбец функций. В методе простой итерации система (3.10) приводится к эквивалентной системе вида где или

(3.11)

Полагая известным начальное приближение для корня построим итерационный процесс или

(3.12)

Рассмотрим поведение вектора погрешности

полагая, что погрешность – величина малая. Для компонент вектора x можем записать

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

, (3.13)

Из (3.13) следует, что в методе простой итерации вектор погрешности испытывает линейное преобразование, или, иначе, метод имеет первый порядок сходимости.

Если обозначить матрицу производных системы функций для (МАТРИЦУ ЯКОБИ) ЧЕРЕЗ

то систему (3.13) можно переписать в виде

(3.14)

Достаточное условие сходимости итерационного процесса (3.12) формулируется следующим образом: если какая-либо норма матрицы согласованная с рассматриваемой нормой вектора x, меньше единицы, то метод итераций сходится, Условие сходимости есть обобщение на случай нелинейной системы условия (3.5) для одного уравнения.

Метод итераций Зейделя

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

Сходимость этого процесса также линейная. Как и при решении систем линейных уравнений, может быть поставлена задача об отыскании на каждой итерации оптимальной последовательности уточнения компонент вектора решения. Удовлетворительных методов построения оптимальной последовательности нет. На практике иногда используется упорядочение неизвестных по убыванию разности их значений на двух последовательных итерациях.

Метод Ньютона

Основная идея метода Ньютона – решение системы нелинейных уравнений f(x) = 0 - сводится к решению последовательности линейных задач, дающих в пределе решение исходной задачи. Линейная задача получается путем выделения из нелинейных уравнений главной линейной части.

Рассмотрим погрешность вычисления корня на k-й итерации где Полагая, что функции непрерывны и дифференцируемы в окрестности корня и ) – малые величины, разложим в ряд Тейлора, сохранив лишь линейную часть разложения. Получим систему уравнений

(3.15)

линейную относительно компонент вектора погрешностей. Если использовать эту систему для отыскания компонент вектора погрешностей, то в силу приближенности системы (3.15) – оставлена лишь линейная часть – найденное значение вектора погрешности будет лишь приближенным, Тогда при подстановке полученного решения в соотношение будет иметь вместо приближенное уточненное значение корня, которое обозначим через Используя запись системы (3.15) в виде

где - матрица производных системы функций (матрица Якоби), можем записать итерационный процесс для нахождения вектора x:

где - матрица, обратная матрице Якоби. Представленная формула является обобщением формулы (3.7) на случай систем нелинейных уравнений. Уточненное значение вектора может быть вновь использовано для получения следующего приближения к корню, что приводит к итерационному процессу. Заметим, что в большинстве случаев предпочтительным является не вычисление обратной матрицы а получение каким-либо методом решения линейной системы (3.15) и вычисление нового приближенного значения по соотношению

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

На каждой итерации метода Ньютона требуется вычислять матрицу производных и решать систему линейных уравнений (3.15). Можно попытаться уменьшить объем вычислений за счет отказа от вычисления матрицы на каждой итерации и использования на всех итерациях постоянного значения вычисленного по начальному приближению. Напомним, что при этом может быть дополнительно существенно уменьшен объем вычислений, если для решения последовательности линейных систем использовать алгоритм, позволяющий выполнить преобразование матрицы к верхней треугольной только один раз. Следует иметь в виду, однако, что, во-первых, указанная модификация метода Ньютона гарантирует лишь линейную сходимость итераций (против квадратичной в окрестности корня в методе Ньютона) и, во-вторых, константа в линейной зависимости погрешности при неудачном выборе начального приближения может оказаться весьма большой и сходимость будет медленней. Таким образом, увеличивается число итераций, необходимое для достижения заданной точности, и уменьшение общего объема вычислений не гарантировано.

Ускорение сходимости по Эйткену

Предположим, что отношение есть величина постоянная и неизменная в процессе итераций. Тогда

Из этого соотношения следует, что

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

4. МЕТОДЫ ПРИБЛИЖЕНИЯ И АППРОКСИМАЦИИ ФУНКЦИЙ