Решение систем конечномерных уравнений методом дифференциального спуска
Отаров А.О., Едилбекова Р.М.
Каракалпакский государственный университет
Пусть имеется система уравнений (линейных или нелинейных)
(1)
где мерный вектор, а заданная вектор-функция, знак штрих означает транспонирование. Предполагается, что функции имеют достаточное число частных производных и система уравнений (1) в некоторой области имеет единственное решение .
Как известно [1, 2, 3], при градиентном методе решение системы (1) сводится к нахождению в области точки, дающей минимум функционалу, построенного из функции . Идеальным градиентным методом явилось бы движение к этой точке, совпадающей с решением системы (1), по линии наискорейшего спуска, которая определяется решением системы дифференциальных уравнений [1, 2, 3]
(2)
с начальными условиями начальное приближение к решению системы (1), дуга линии наискорейшего спуска и .
Так как получение решения системы (2) в замкнутом виде в большинстве случаев невозможно, то используют приближенное решение . Двигаясь по линии , отыскивают на этой линии точку , в которой функция имеет минимальное значение. Затем, если приближенное решение системы (2) с начальными условиями , то, двигаясь по линии , находят на этой линии точку , в которой функция имеет минимальное значение.
Если уже найдено е приближение к корню , то е приближение суть точка на линии , в которой имеет минимальное значение, приближенное решение системы (2) с начальными условиями
Как видно из изложенного, применение обычного метода наискорейшего спуска требует на ом шаге выполнения большой вычислительной работы при нахождении минимума функции
В данной работе рассматривается метод дифференциального спуска [2], который не требует нахождения на ом шаге минимума функции Этот метод применяется для решения системы конечномерных уравнений (1).
Перейдем к рассмотрению метода дифференциального спуска. Пусть , где такой функционал что тогда и только тогда, когда решение системы (2).
Построение функционала в явном виде, вообще говоря, не является обязательным. Например, можно задать функционал Тогда, если условия теоремы о неявной функции [4] выполнены, то этот функционал определяет дифференциальное уравнение
(3)
с начальными условиями где начальное приближение к корню производная Фреше, операция обратная операции . Решение дифференциального уравнения (3) при дает корень , и различные способы его численного интегрирования [1, 3] дают возможность построить различные итерационные методы решения системы уравнений (1).
Если перейти в системе (2) от переменной к переменной то получим систему дифференциальных уравнений
(4)
с начальными условиями Решение системы (4) при дает корень системы уравнений (1), т.е.
Интегрируя задачу Коши (4) приближенными способами, можно получить различные итерационные методы решения системы (1). Например, метод Эйлера с шагом [1,3] (уравнение (4) решается с начальными условиями ) дает итерационный метод
(5)
а метод Рунге-Кутта [1, 3] с тем же шагом и имеющий порядок ошибки дает итерационный метод
(6)
где
В одномерном случае, если , то формула (5) дает метод Ньютона и, если интегрировать (4) методом Рунге-Кутта с шагом то можно получить итерационные методы высоких порядков [1,3].
Теперь рассмотрим применение итерационного метода (5) для решения систем линейных алгебраических уравнений.
Пусть имеется система линейных уравнений с неизвестными
(7)
где вещественная симметричная матрица порядка, вектор-столбец свободных членов, вектор-столбец неизвестных. Предполагается, что матрица имеет собственные значения, отличные от нуля.
Примем
,
вектор невязки. Тогда, так как , система дифференциальных уравнений (4) и метод (5) примут соответственно вид
(8)
(9)
Рассмотрим вопрос выбора шага интегрирования системы (8) таким образом, чтобы, интегрируя (8) методом Эйлера, можно было прийти к точному решению системы (7) с любого начального приближения.
Естественно принимать шаг интегрирования равным где некоторая постоянная, удовлетворяющая условию
На вопрос о том, как выбирать постоянную , дает ответ следующая теорема.
Теорема. Последовательные приближения метода
(10)
сходятся к решению системы (7) с быстротой геометрической прогрессии с любого начального приближения , если
а)
б)
где число обусловленности Тодда [1, 3].
Доказательство. Покажем прежде всего, что если условия теоремы выполнены, то
(11)
откуда
Если выполняется условие а), то получим
А выполнение условия б) приведет к следующим соотношениям
Отсюда видно, что в обоих случаях удовлетворяется неравенство (11). Итак,
Следовательно, и потому точное решение системы (7).
Оценим теперь длину вектора ошибки, т.е. . Так как
то
и стремится к нулю со скоростью геометрической прогрессии со знаменателем
Что и требовалось доказать.
Таким образом, выбирая шаг интегрирования, зависящий от обусловленности матрица , можно, интегрируя (8) методом Эйлера, прийти к точному решению системы (7) с любого начального приближения.
Литература
Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. – М.: Наука, 1987.
Отаров А.О. Решение систем нелинейных уравнений методом сведения к задачам Коши для обыкновенных дифференциальных уравнений //Журнал “Вестник” КК отделения АНРУз, Нукус, 2002, №1.
Самарский А.А., Гулин А.В. Численные методы. – М.: Наука, 1989.
Треногин В.А. Функциональный анализ. – М.: Наука, 1980.
Do'stlaringiz bilan baham: |