Методы нахождения корней систем нелинейных уравнений. 
Ускорение сходимости по Эйткену

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

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

где х = (x_v х₂…х_п)^т— вектор-столбец неизвестных*, f (x) =.

= [fi (x), f₂(x)> •••> f_n(x)V— вектор-столбец функций. В методе простой итерации система (1.25) приводится к эквивалентной системе вида х = Ф (*), где <�р (х) = [ф_х(д:), <�р₂(х), …, ф_л(х)]^т, или.

Полагая известным начальное приближение для корня х^(0> — = (Xj⁰⁾, х^ …" х_л^0>)⁷', построим итерационный процесс х^{(к +} =.

= <�р (х^(А)), k = 0, 1, 2, … или.

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

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

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

‘Верхний индекс Т означает операцию транспонирования.

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

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

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

Достаточное условие сходимости итерационного процесса (1.27) формулируется следующим образом: если какая-либо норма матрицы А_ф, согласованная с рассматриваемой нормой вектора х, меньше единицы, то метод итераций сходится. Условие сходимости ||А_ф|| < 1 есть обобщение на случай нелинейной системы условия (1.20) для одного уравнения.

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

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

ЯКОБИ КАРЛ ГУСТАВ ЯКОБ (Jacobi Carl Gustav Jacob; 1804—1851) — немецкий математик, один из создателей теории эллиптических функций. Я. принадлежат открытия в области теории чисел, алгебры, вариационного исчисления, интегрального исчисления и теории дифференциальных уравнений. Он ввел в употребление функциональные определители (якобианы) и указал на их роль при замене переменных в кратных интегралах и при решении уравнений с частными производными. Я. исследовал класс ортогональных многочленов (многочлены Якоби).

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

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

Рассмотрим погрешность вычисления корня на k-й итерации е (*) = х* - х^(кК где t = е⁽₂* … е⁽_л^А)]'. Полагая, что функции /.

непрерывны и дифференцируемы в окрестности корня и г^(к) (г ® 1, …, п) — малые величины, разложим f (x*) «= f (x ^{+ е(*0 =? О в ряд Тейлора, сохранив лишь линейную часть разложения. Получим систему уравнений}

линейную относительно компонент вектора погрешностей. Если использовать эту систему для отыскания компонент вектора погрешностей, то в силу приближенности системы (1.30) — оставлена лишь линейная часть — найденное значение вектора погрешности будет лишь приближенным. Тогда при подстановке полученного решения в соотношение х* «e^(ft) — будем иметь вместо х* приближенное уточненное значение корня, которое обозначим через О. Используя запись системы (1.30) в виде

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

где [А***]'¹ — матрица, обратная матрице Якоби. Представленная формула является обобщением формулы (1.22) на случай систем нелинейных уравнений. Уточненное значение вектора может быть вновь использовано для получения следующего приближения к корню, что приводит к итерационному процессу. Заметим, что в большинстве случаев предпочтительным является не вычисление обратной матрицы [А^*]^-1, а получение каким-либо методом решения е^(А) линейной системы (1.30) и вычисление нового приближенного значения по соотношению х<-^{к +} D = дс +.

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

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

| Ускорение сходимости по Эйткену Предположим, что отношение (х⁽* «*) — х*)/(дг⁽*> - х*) = q есть величина постоянная и неизменная в процессе итераций. Тогда.

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

ЭЙТКЕН АЛЕКСАНДР КРЭГ (Aitken Alexander Craig; 1895—1967) — английский математик. Основные его труды относятся к численному анализу, статистике и алгебре. В алгебре Э. проводил исследования по теории определителей. В области численного анализа ему принадлежит идея об ускорении сходимости численного метода. Э. также разработал метод последовательной линейной интерполяции.

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