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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

СУМСКИЙ ГОСУДАСТВЕННЫЙ УНИВЕРСИТЕТ

кафедра информатики

КУРСОВАЯ РАБОТА

ПО КУРСУ:

Численные методы

на тему:

ВлИтерационные методы решения систем нелинейных уравненийВ»

Сумы, 2006

Содержание

1. Методы решения систем нелинейных уравнений. Общая информация

2. Итерационные методы решения систем нелинейных уравнений

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

2.2 Преобразование Эйткена

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

2.3.1 Модификации метода Ньютона

2.3.2 Квазиньютоновские методы

2.4 Другие итерационные методы решения систем нелинейных уравнений

2.4.1 Метод Пикара

2.4.2 Метод градиентного спуска

2.4.3 Метод релаксаций

3. Реализация итерационных методов программно и с помощью математического пакета Maple

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

3.2 Метод градиентного спуска

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

3.4 Модифицированный метод Ньютона

Выводы

Список использованной литературы

1. Методы решения нелинейных уравнений. Общая информация.

Пусть нам дана система уравнений, где - некоторые нелинейные операторы:

(1.1)

Она может быть также представлена в матричном виде:

(1.1)

Где

Её решением называется такое значение , для котрого

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

Обозначим через Х вектор-столбец (х₁, х₂,.., х_n)^T и запишем систему уравнений в виде формулы (1.2): F(Х) = 0, где F = (f₁, f₂,.., f_n)^T.

Подобные системы уравнений могут возникать непосредственно, например, при конструировании физических систем, или опосредованно. Так, к примеру, при решении задачи минимизации некоторой функции G(х)часто необходимо определить те точки, в которых градиент этой функции равен нулю. Полагая F = grad G, получаем нелинейную систему.

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

Для полноты представления о методах нахождения решения системы необходимо разъяснить такое понятие, как "скорость сходимости". Если для последовательности x_n, сходящейся к пределу х_*, верна формула

(k - положительное действительное число), то k называется скоростью сходимости данной последовательности.

2. Итерационные методы решения систем нелинейных уравнений

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

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

f_i(x₁,x₂,..x_n) = 0, i=1,2,.;

Приведём систему уравнений к специальному виду:

(2.1)

Или в векторном виде . (2.2)

Причем переход к этой системе должен быть только при условии, что

является сжимающим отображением.

Используя некоторое начальное приближение X⁽⁰⁾= (x₁⁽⁰⁾,x₂⁽⁰⁾,..x_n⁽⁰⁾)

построим итерационный процесс X^(k+1) =  (X^(k)). Расчёты продолжаются до выполнения условия . Тогда решением системы уравнений является неподвижная точка отображения .

Проведём обоснование метода в некоторой норме пространства .

Приведём теорему о сходимости, выполнение условий которой приводит к нахождению решения системы.

Теорема (о сходимости). Пусть

1). Вектор-функция Ф(х) определена в области

;

2). Для выполняется условие

3). Справедливо неравенство

Тогда в итерационном процессе:

1.

2. ,

где тАУ решение системы уравнений;

3. ,

Замечание. Неравенство условия 2) есть условие Липшица для вектор -функции Ф(х) в области S с константой (условие сжатия). Оно показывает, что Ф является оператором сжатия в области S, т. е. для уравнения (2.2) действует принцип сжатых отображений. Утверждения теоремы означают, что уравнение (2.2) имеет решение в области S, и последовательные приближения сходятся к этому решению со скоростью геометрической последовательности со знаменателем q.

Доказательство. Поскольку , то для приближения в силу предположения 3) имеем . Это значит, что . Покажем, что , k=2,3,тАж причём для соседних приближений выполняется неравенство

(2.3)

Будем рассуждать по индукции. При утверждение справедливо, т.к. и . Допустим, что приближения принадлежат S, и неравенство (2.3) выполнено для . Поскольку , то для с учётом условия 2) теоремы имеем

.

По индуктивному предположению

.

Следовательно,

,

т.е. неравенство (2.3) справедливо для . Покажем, что . Учитывая свойство (2.3) при , получаем

Итак, , и первое утверждение теоремы доказано.

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

По аналогии с предыдущим для любых р=1,2,тАж имеем

Поскольку , то , поэтому для найдётся такой номер , что для будет

Это означает выполнение признака Коши, что гарантирует сходимость последовательности . Обозначим . Утверждение 2) теоремы доказано.

Для доказательства последнего утверждения воспользуемся полученным выше неравенством

Перейдём здесь к пределу при . Учитывая непрерывность функции и тот факт, что , получаем требуемый результат тАУ утверждение 3).

Замечание 2. В условиях теоремы решение уравнения (2.2) в области S является единственным.

Действительно, пусть имеются два решения , причём . Тогда

,

Получили противоречие, что и требовалось доказать.

Обсудим условие 2) доказанной теоремы. Рассмотрим уравнение (2.2) в покомпонентной записи

и предположим, что функции непрерывно-дифференцируемы в области S (т.е. существуют и непрерывны в S частные производные

).

Теперь выясним достаточное условие выполнения неравенства 2) в этом случае.

Образуем матрицу Якоби системы функций

.

Далее, будем использовать обобщенную теорему о среднем (обобщение на случай вектор- функции формулы конечных приращений Лагранжа)

Здесь матричная норма согласована с векторной, , тАУ точка отрезка, соединяющего х, у.

Поскольку S тАУ выпуклое множество, то . Предположим, что имеет место оценка

, причём . (2.4)

Тогда согласно предыдущему выполняется условие 2) теоремы

.

Таким образом, в случае дифференцируемости условие (2.4) на матрицу Якоби гарантирует условие сжатия для вектор- функции

2.2 Преобразование Эйткена

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

Идею преобразования Эйткена поясним на простом примере.

Погрешность найденных значений на каждой итерации равна,. если

найдем предел x через три значения последних приближений x^k.

.

т. е.

Построим теперь процесс: , тогда

э

то итерационный процесс для уравнения:

(А)

Рассмотрим порядок сходимости этого процесса

Теперь из (А).

Мы рассматривали процесс простых итераций тАУ процесс первого порядка,

а получили процесс 2 тАУго порядка.

Легко показать, что если процесс имеет порядок, то схема Эйткена имеет порядок (2r-1). Более того, если процесс. не сходится, то итерационный процесс при выборе начального приближения так, чтобы,. будет сходиться.

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

Основная идея метода Ньютона состоит в выделении из уравнений линейных частей, которые являются главными при малых приращениях аргументов. Это позволяет свести исходную задачу к решению последовательности линейных систем.

Рассмотрим систему уравнений

в предположении, что тАУ непрерывно-дифференцируемые функции.

Полагая

,

прейдём к векторной записи

(3.1)

Опишем общий шаг метода. Пусть уже получено приближение проведём линеаризацию вектор-функции в окрестности точки - разложим функцию в ряд Тейлора, оставив только два первых члена в силу малости отклонения приближения от корня:

.

Здесь тАУ матрица Якоби для вектор-функции .

Очередное приближение определяется как решение линейной системы , т.е.

Если матрица Якоби не вырожденна, то решение системы линейной системы можно записать в явном виде, что приводит к стандартной формуле метода Ньютона

(3.2)

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

Через уже известное приближение к корню можно записать, что , где . Тогда после линеаризации получим систему уравнений, линейную относительно . Таким образом, на каждом шаге мы будем находить приращения , и новое приближение к решению по формулам:

тАУ система линейных уравнений

Рассмотрим вопрос о сходимости метода Ньютона. Точное условие сходимости метода Ньютона для решения систем нелинейных уравнений имеет довольно сложный вид. можно отметить очевидный результат: в достаточно малой окрестности корня итерации сходятся, если матрица Якоби невырожденная, причём сходимость квадратичная.

Приведём ряд теорем, выполнение условий которых должно обеспечивать сходимость метода Ньютона.

Пусть в пространстве выбрана некоторая векторная норма и согласованная с ней матричная норма .

Теорема (о сходимости). Пусть

1) вектор-функция определена и непрерывно-дифференцируема в области

где тАУ решение уравнения (3.1),

2) для всех существует обратная матрица , причём

3)для всех

4)

Тогда метод Ньютона (3.2)

1)

2)

3)

Доказательство. Докажем первое утверждение теоремы с помощью индукции. По условию . Допустим, что . Поскольку , то . Рассмотрим условие 3) теоремы для

.

Согласно формуле (3.2)

,

Кроме того . Тогда предыдущее неравенство принимает вид

Следовательно,

Таким образом, имеет место неравенство

(3.3)

По предположению индукции . Поскольку в силу условия 4)

, то

Это значит, что для , и шаг индукции реализован. Превое утверждение теоремы доказано.

Продолжим доказательство. Положим перепишем оценку (3.3) после умножения на в виде . Покажем, что

(3.4)

Будем рассуждать по индукции. При неравенство (3.4.) очевидно. Допустим, что оно справедливо для некоторого . Тогда

Переход завершен, т.е. неравенство (3.4) справедливо для всех . Перепишем его в исходных обозначениях

Получили утверждение 3). При этом

, т.е. .

Это значит, что имеет место сходимость:

Замечание 1. Неравенство (3.3) при условии означает, что последовательность сходится к решению с квадратичной скоростью.

Замечание 2. Поскольку , то из утверждения 3) следует оценка погрешности метода Ньютона

Теорема. Если f_i(x) непрерывны, вместе с первыми производными в выпуклой области G, содержащей решение системы и при матрица F_x не вырождена, то существует такая окрестность что при любом метод Ньютона сходится к .

Доказательство. Рассмотрим

Введем и матрицу и матрицу. Очевидно, что F(x,x)= F(x), то есть имеем

(12)

Есть тождества

Тогда.

Вблизи окрестности для любого найдется такое x⁰, что если,. то

Тогда

На начальное приближение x⁰ наложено труднопроверяемое условие.

Теорема Канторовича. Если функции f_i(x) непрерывны вместе со своими 1 -ми и 2 -ми производными в некоторой выпуклой области G, содержащей точку x⁰ вместе с ее окрестностью и выполнены следующие условия:

в точке x⁰ существует матрица F^-1 такая

то последовательность x^k+1=x^k-f^-1_x(x^k)F(x^k) сходится к .является единственным решением системы f(x)=0 в области и имеет место оценка

Докажем 3 неравенства

а)

б)

в)

б)

в)

т.е. матрица F^-1_x(x⁰)F_x(x¹) невырождена, и

и

F_x(x⁰)(x¹-x⁰)+f(x⁰)=0

Покажем, что при всех k имеют место неравенства:

(А)

Пусть имеет место m=k-1

Повторим неравенства

Неравенство (А) показывает, что в круге R последовательность x^k является фундаментальной, т.е. имеется предел.

Оценим сходимость

т.е.,

устремляя правая часть не меняется,, т.е. при очень хорошая сходимость.

2.3.1 Модификации метода ньютона

1. Вычисления в методе Ньютона гораздо сложнее, чем при простых итерациях, т.к. на каждой итерации требуется находить матрицу производных и решать систему линейных уравнений. Поэтому рекомендуется такой приём: матрица Якоби вычисляется только на начальном приближении. Однако сходимость при этом видоизменении становится линейной, причём обычно не с малой константой, ибо матрица производных на начальной итерации может заметно отличаться от окончательной. Поэтому скорость сходимости заметно уменьшается и требуемое сисло итераций возрастает.

2. В ещё одной модификации итерационную формулу метода Ньютона вводится параметр следующим образом

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

(3.5)

Проведём обоснование такой процедуры в евклидовой норме.

Ведём в рассмотрение функцию-невязку для уравнения (3.1)

Найдём градиент , используя представление

С этой целью выделим главный член приращения

Следовательно, по определению

Обозначим и найдём производную функции в точке по направлению :

если .

Таким образом, тАУ есть направление спуска для функции в точке для малых . Это значит, что выбор шага согласно условию (3.5) возможен.

2.3.2 Квазиньютоновкие методы

Одним из недостатков метода Ньютона является необходимость вычислять матрицу Якоби и решать систему линейных алгебраических уравнений. Это требует значительных расходов машинных действий, объём которых резко возрастает с увеличением размерности системы. Поэтому были разработаны модификации метода Ньютона, в которых на протяжении итерационного процесса вместо построения самой матрицы Якоби или её обратной строится их аппроксимация. Это позволяет существенно сократить количество арифметических действий на итерации. Такие методы решения систем нелинейных уравнений получили название квазиньютоновских. Большинство известных квазиньютоновских методов сходится локально с надлинейной скоростью сходимости при тех самых предположениях о свойствах функции , которые были сделаны при использовании метода Ньютона, который имеет квадратичную скорость сходимости. Квазиньютоновские методы можно разделить на два тесно связанных между собой класса методов в зависимости от того, что аппроксимируется - матрица Якоби или ей обратные.

Рассмотрим первый из классов, где матрица В_кс размерами п х п аппроксимирует матрицу . Перед началом итераций задают начальную точку а матрицу В_ообычно получают, или допуская, что она является единичной, или аппроксимируя конечно-разностными формулами. Потом для k = 0, 1.. вычисляют

Где тАФ n- мерный вектор, который является параметром рассматриваемого класса методовв. Если взять таким, что равняется ,то будем иметь первый метод Бройдена. Выбор соответствует методу Пирсона, а тАФ симметрическому методу первого ранга.

Во втором из рассматриваемых здесь классов квазиньютоновских методов матрица с размерами п х п аппроксимирует матрицу . Перед началом итерации задают начальную точку х^{0)и матрицу , которая обычно или равна единичной, или является обратной к конечно-разностной аппроксимации . Потом вычисляют

где тАФ n-мерный вектор, который является параметром рассматриваемого класса методов. Конкретный вид вектора отвечает соответствующему методу: например, тАФ второму методу Бройдена, тАФ методу Мак-Кормика.

Заметим, что если задать то можно вести перерасчет не В_к, а матриц по формуле

(3.30)

эквивалентной (3.27). Это требует порядка 0(п²) арифметических действий вместо 0(п³), необходимых для решения системы линейных уравнений .

Как видно из (3.30), между формулами (3.27) и (3.29) имеет место определенная связь. Так.если , то при . Таким образом, один и тот же метод может реализоваться двумя разными формулами (3.27) и (3.29), которые эквивалентные теоретически, но их численная реализация может отличаться по эффективности.

Рассмотрим, например, первый метод Бройдена. Его можно реализовать по формуле (3.27) так, что это потребует в общем 0(n³) арифметических действий. Это оказывается возможным, если подать матрицу В_кв виде произведения , где тАФ ортогональная, а тАФ верхняя треугольная матрица. Действительно, в этом случае решение системы нуждается в только 0(n³) арифметических действий. Имея, на представление матрицы В_к+1, которая удовлетворяет (3.27) в виде , необходимо 0(п²) арифметических действий. Важное преимущество формулы (3.27) перед (3.39) заключается в том, что в (3.27) нет необходимости умножения матрицы на вектор, поскольку

Существуют квазиньютоновские методы, которые учитывают симметричность матрицы Якоби и вырабатывают последовательность симметричных матриц В_к, (или). Эти методы также можно разделить на два класса. В первом из них матрица В_к аппроксимирует F(х). В отличие от описанного выше класса, который задается формулами (3.26) и (3.27), здесь нужна симметричность матрицы Во, и вместо (3.27) используется формула

где значение параметра отвечает симметричному варианту Пауелла методу Бройдена, а тАФ методу Давидона - Флечера - Пауелла.

Во втором из рассматриваемых классов квазиньютоновских методов матрица Н_каппроксимирует матрицу . Здесь матрица Н_одолжна быть симметричной, а вместо (3.29) используется формула

Где соответствует методу Бройдена-Флечера-Голвдфарба-Шенно, что является одним из наилучших (с вычислительной точки зрения), который учитывает симметричность матрицы Якоби.

Описанные выше квазиньютоновские методы сходятся лишь при достаточно хорошом начальном приближении х⁽⁰⁾. Для расширения области их сходимости можно использовать прием, который имеет название одномерного поиска.

Пусть имеем квазиньютоновское направление (или ).Используем длину шага = 1 и проверим неравенство

(3.34)

где - евклидовая норма. Если оно выполняется, то заканчиваем одномерный поиск и считаем

(3.35)

т.е. уменьшаем длину шага (устанавливая, например, ), пока не выполнится (3.34). На этом заканчиваем одномерный поиск и переходим к формуле (3.35).

Как видим, одномерный поиск (в случае успеха) обеспечивает монотонное уменьшение нормы отклонения с ростом к. Если квазиньютоновское направление сильно отличается от ньютоновского, то одномерный поиск может оказаться неудачным, и тогда необходимо возобновить матрицу В_к, (или)., приравняв ее, например, конечно-разносной аппроксимации матрицы Якоби (или ). Критерием окончания итераций для квазиньютоновских методов есть неровность

3. Другие итерационные методы решения систем нелинейных уравнений

3.1 Метод Пикара

Существуют также итерационные методы решения систем нелинейных уравнений, которые учитывают вид конкретной системы.

Так, если в уравнениях системы можно выделить линейную l(X) и нелинейную g(X)части функций f_i(X) = l_i(X) + g_i(x), то удобней применить к ней метод Пикара.

В таком случае систему уравнений можно записать в виде

l_i(X) = - g_i(X), i=1,2,3..;

или в векторной форме A X= - G(X);

где A- матрица коэффициентов линейных частей уравнений;

G(X) - вектор-функция нелинейных частей уравнений.

Выберем некоторый начальный вектор X⁽⁰⁾ и построим итерационный процесс в виде

A X^(k+1)=-G(X^(k)).

Для выполнения одной итерации таким методом необходимо решать систему линейных уравнений, у которой вектором свободных членов будут нелинейные части функций f_i(X). Причем поскольку матрица A остается неизменной при всех итерациях, то для решения СЛАУ можно использовать специальные алгоритмы, предусматривающие возможность преобразования только столбца свободных членов.

3.2 Метод релаксаций

Перепишем систему в виде

X=X+ F(X),

где  - некоторая константа, и построим итерационный процесс по схеме

X^(k+1) = X^(k) +  F(X^(k)).

Параметр  должен быть таким, чтобы в окрестности решения выполнялось достаточное условие сходимости

||Е+  W|| < 1,

где E- единичная матрица.

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

||X^(k)-X^(k-1)||<||X^(k-1)-X^(k-2)||.

Если окажется, что на какой-либо итерации это условие не выполняется, то необходимо изменить значение параметра .

3.3 Метод градиентного спуска

Пусть имеем систему уравнений (А)

Предположим, что функции действительные и непрерывно дифференцированные в их общей области определения. Рассмотрим функцию

(В)

Очевидно, что каждое решение системы (А) превращает в ноль функцию U(x); наоборот, числа , для которых функция U(x) равняется нулю, является корнем системы (А).

Предположим, что система имеет лишь изолированное решение, которое представляет собой точку строго минимума функции U(x) в n-мерном пространстве .

Пусть x - вектор системы (А) и x0 - его нулевое приближение. Через точку x0 проведем поверхность уровня функции U(x). Если точка x0 довольно близка к корню x, то при наших предположениях поверхность уровня

U(x)= U(x0)

будет похожа на эллипсоид.

Из точки x0 движемся по нормали к поверхности U(x)= U(x0) до тех пор, пока эта нормаль не затронет в некоторой точке x1 какой-то другой поверхности уровня U(x)= U(x1).

Потом, отправляясь от точки x1, снова движемся по нормали к поверхности уровня U(x)= U(x1) до тех пор, пока эта нормаль не затронет в некоторой точке x2 новой поверхности уровня U(x)= U(x2), и т.д.

Поскольку U(x0)>U(x1)>U(x2)>.., то, двигаясь таким путем, мы быстро приближаемся к точке с наименьшим значением U ("дно ямы"), что отвечает искомому решению исходной системы. Обозначим через

градиент функции U(x).

Находить нужное решение будем по формуле:

Остается определить множители . Для этого рассмотрим скалярную функцию

Функция F(l) дает изменение уровня функции U вдоль соответствующей нормали к поверхности уровня в точке x_p. Множитель

Вместе с этим смотрят:

10 способов решения квадратных уравнений

РЖнварiантнi пiдпростори. Власнi вектори i власнi значення лiнiйного оператора

РЖнженерна графiка

РЖнтегральнi характеристики векторних полiв

РЖнтерполювання функцiй