Xreferat.com » Рефераты по математике » Итерационные методы решения систем нелинейных уравнений

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

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

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

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

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

ПО КУРСУ:

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

на тему:

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

Сумы, 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 нелинейных алгебраических или трансцендентных уравнений с n неизвестными.

Обозначим через Х вектор-столбец (х1, х2,..., хn)T и запишем систему уравнений в виде формулы (1.2): F(Х) = 0, где F = (f1, f2,..., fn)T.

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

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

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

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


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

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

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

fi(x1,x2,...xn) = 0, i=1,2,..n;

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

 (2.1)

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

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

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

Используя некоторое начальное приближение X(0)= (x1(0),x2(0),...xn(0))

построим итерационный процесс 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 через три значения последних приближений xk.

begin{eqnarray*}x^k-X^{ast}&=&Aq^k,quadx^{k-1}-X^{ast}=Aq^{k-1}\ q&=&fra... ...x^{k-1}-X^{ast}},quad q=frac{x^{k+1}-X^{ast}}{x^k-X^{ast}},end{eqnarray*}.

т. е.

begin{displaymath}(x^k-X^{ast})^2=(x^{k+1}-X^{ast})(x^{k-1}-X^{ast}),quadX^{ast}= frac{x^{k+1}x^{k-1}-(x^k)^2}{x^{k+1}-2x^k+x^{k-1}}.end{displaymath}

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

э

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


 (А)

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

begin{eqnarray}x^k&=&X^{ast}+varepsilon^k=x+varepsilonnonumber\ varphi(x... ...r\ &=&x+frac{alphabeta(alpha-1)varepsilon^3}{dvarepsilon}.end{eqnarray} 

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

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

$mid Bvarepsilon^0mid<1$а получили процесс 2 –го порядка.

$x^{k+1}=varphi(x^k)$
 


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

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

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

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

 

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

Полагая

,

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

 (3.1)

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


.

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

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

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

 (3.2)

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

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

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


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

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

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

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

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

 

где  – решение уравнения (3.1),

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

3)для всех

4)

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

1)

2)

3)

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

.

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

,

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
Страницы: 1 2 3

Похожие рефераты: