Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ЧИСЛЕННЫЕ МЕТОДЫ
Посмотреть оригинал

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

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

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

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

где х = (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). Предложенный способ пригоден как для одного нелинейного уравнения, так и для систем нелинейных уравнений. Это предположение означает, что метод применим к процессам с линейной сходимостью (простые итерации), но неприменим к методам Ньютона, секущих, парабол и т. п.

 
Посмотреть оригинал
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы