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

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

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

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

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

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

Полагая известным начальное приближение для корня х(0> — = (Xj0), х^ ...» хл0>)7', построим итерационный процесс х + =

= <р(х(А)), 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<*> = е(2* .... е(лА)]'. Полагая, что функции /.

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

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

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

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

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

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

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

Предположим, что отношение (х(* " *) - х*)/(дг(*> - х*) = q есть величина постоянная и неизменная в процессе итераций. Тогда

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >