Решение систем нелинейных уравнений методом Ньютона

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Челябинский государственный университет»

(ФГБОУ ВПО «ЧелГУ»)

Математический факультет

кафедра Вычислительной математики

 

 

Направление (специальность):	010400.62 Прикладная математика и информатика
	(наименование направления (специальности)
Дисциплина:
	(наименование дисциплины)

 

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

 

ТЕМА: Решение систем нелинейных уравнений методом Ньютона

 

 

	ВЫПОЛНИЛ СТУДЕНТ
	Фамилия, имя, отчество					Васильев
	Алексей Игоревич
	Академическая группа				МПЗ-401		Курс	4
	Формы обучения		Заочная
	(подпись)   «__» ______ 2015г.
	НАУЧНЫЙ РУКОВОДИТЕЛЬ
	Фамилия, имя, отчество					Овчинников
	Михаил Алексеевич
	Ученая степень	кандидат физико-математических наук
	Должность	доцент кафедры
	вычислительной математики
	(оценка)                                           (подпись)   «__» ______ 201_г.

 

 

 

Челябинск

2015

 

Оглавление

 

 

 

 

Введение

Вычислительные методы стали особенно актуальны в результате внедрения компьютерных технологий во все сферы деятельности человека.

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

Исследованием и разработкой численных методов, как правило, занимаются специалисты математики. Большинству пользователей главное и достаточно понимание основных методов и идей.

Целью этой работы является изучении способа решения систем нелинейных уравнений методом Ньютона.

 

Теоретическая часть

Для решения систем нелинейных уравнений (СНЛУ) используются различные численные методы, такие как: метод итераций, дихотомии, хорд и, нужный нам, метод Ньютона.

 

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

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

 

(1)

или в векторной форме, F(x)=0 (2).

Введём матрицу Якоби J(x) для функций fi(x), i=1, …, n, которые будем предполагать непрерывно дифференцируемыми:

 

Пусть задано начальное приближение x(0). Вместо нелинейного уравнения (2) решаем линейное уравнение

 

Если , то уравнение (4) имеет единственное решение, которое обозначим x(1). Здесь удобно решать уравнение (4) относительно ∆ x(0)=x- x(0), а затем вычислять x(1)= x(0)+ ∆ x(0). Если найдено x(m), то x(m+1) вычисляем по

x(m+1)= x(m)+∆x(m), а поправку ∆x(m)=( ∆x(m)1, …, ∆x(m)p) находим из системы

 

которая в координатной форме имеет вид

 

 

Где m – пара x,y.

В нашем случае, для системы второго порядка

 

 

Последовательные приближения по методу Ньютона вычисляются по формулам:

 

 

 

 

где

 

 

Метод Ньютона сходится, если начальное приближение выбрано удачно и матрица J(x*) невырожденна. На практике итерации обычно оканчивают, если . Для выбора начального приближения применяют графический метод, метод проб, метод табулирования и т.д.

 

Теорема 1.1. Пусть в некоторой окрестности решения системы функций

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

 

Замечание 1.1. В качестве критерия окончания процесса итераций обычно берут условие: .

Замечание 1.2. Сложность метода Ньютона – в обращении матрицы Якоби. Вводя обозначение получаем для вычисления СЛАУ

 

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

Замечание 1.3. Начиная с некоторого шага решают стационарную СЛАУ  

Данное видоизменение носит название модифицированный метод Ньютона.

 

Постановка задачи

 

В работе решается следующая система нелинейных уравнений:

 

 

Имеем три системы уравнений с разным коэффициентом α. Начальные приближения найдём графически.

 

Подготовка программы для решения задачи

Реализовывать метод Ньютона будем на языке программирования(ЯП) С++.

Распишем подробно алгоритм программы:

// подключим необходимые  библиотеки

#include "stdafx.h"

#include <iostream>

#include <iomanip>

#include <math.h>

using namespace std;

 

#define eps 0.0001 // указываем точность

double alfa; // переменная для текущего альфа-коэффициента

 

double fxy(double x, double y) // функция для f(x,y)

{

    return alfa*x*x*x - y*y - 1;

}

 

double gxy(double x, double y) // функция для g(x,y)

{

    return x*y*y*y - y - 4;

}

 

double fdx(double x, double y) // производная f по x

{

    return 3*alfa*x*x;

}

 

double fdy(double x, double y) // производная f по y

{

    return -2*y;

}

 

double gdx(double x, double y) // производная g по x

{

    return y*y*y;

}

 

double gdy(double x, double y) // производная g по y

{

    return 3*x*y*y - 1;

}

 

// реализуем функцию  для An, Bn и Jn из метода

double An(double x, double y)

{

return fxy(x,y)*gdy(x,y)-gxy(x,y)*fdy(x,y);

}

double Bn(double x, double y)

{

return fdx(x,y)*gxy(x,y)-gdx(x,y)*fxy(x,y);

}

double Jn(double x, double y)

{

return fdx(x,y)*gdy(x,y)-gdx(x,y)*fdy(x,y);

}

 

// реализуем функции  вычисления коэффициента и сдвига  для визуализации процесса

double koef(int num, double x, double y)

{

if (num==1) {return -fdx(x,y)/fdy(x,y);}

if (num==2) {return -gdx(x,y)/gdy(x,y);}

}

double sdvig(int num, double x, double y)

{

if (num==1) {return -fxy(x,y)/fdy(x,y);}

if (num==2) {return -gxy(x,y)/gdy(x,y);}

}

 

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

void nuton (double x, double y) // на входе функция получает начальное приближение

{

int i=1; // переменная счётчика итератора

double x0, y0;

 

do

{

x0=x; y0=y; // в x0, y0 записываем x и y предыдущего шага

x=x-An(x0,y0)/Jn(x0,y0); // высчитываем x по формуле (5)

y=y-Bn(x0,y0)/Jn(x0,y0); // высчитываем y по формуле (6)

cout << "-----------" << "i=" << i << "-----------" << endl; // вывод номера итерации

// выводим коэффициент  и сдвиг для функции f

cout << "f: koef k= " << koef(1,x0,y0) << endl << " sdvig= " << sdvig(1,x0,y0) << endl << endl;

// выводим коэффициент  и сдвиг для функции g

cout << "g: koef k= " << koef(2,x0,y0) << endl << " sdvig= " << sdvig(2,x0,y0) << endl << endl;

// выводим новые x и y

cout << setprecision(7) << "x=" << x << endl << "y=" << y << endl << endl;

i++;

} while (abs(x-x0)>eps); // выход из цикла по достижению точности

}

 

void main()

{

    double x, y;

do

{

    cout << "x = "; cin >> x; //запрашиваем начальноре приближение x

    cout << "y = "; cin >> y; //запрашиваем начальноре приближение y

cout << "alfa = "; cin >> alfa; //запрашиваем коэффициент альфа

cout << endl;

if (Jn(x,y)==0) { cout << "Neverno vibrano nachalnoe priblizhenie" << endl;};

} while (Jn(x,y)==0); // проверяем, что определитель матрицы Jn не равен 0

    nuton(x, y); // применяем метод Ньютона

    system("PAUSE");

}

 

Решение задачи

Приведённые результаты сверены с вычислениями на сайте www.wolframalpha.com

1. Расчёты для α=1

Определяем начальное приближение графическим способом.

Рисуем графики:

По графику определяем x и y приблизительно равными 1,5. Эти значения и используем в качестве начального приближения.

Выполняем подготовленную программу с параметрами:

X=1.5;

Y=1.5;

Alfa=1.

 

Нужная нам точность (0,0001) достигнута на 3 шаге итерации.

Для визуализации процесса изобразим графически последовательное приближение при заданных параметрах.

2. Расчитаем значения при α=0,5.

Строим графики и выбираем начальное приближение:

В качестве начального приближения примем x=2 и y=1.5

Выполняем программу при:

X=2;

Y=1.5;

Alfa=0.5.

Как и в предыдущем шаге визуализируем приближения:

 

3. Считаем для значения α=3,5.

Чертим график

Начальное приближение примем равным x=1, а y=1.8 и запускаем программу с новыми параметрами.

Визуализируем процесс приближения:

 

 

Вывод

По ходу тестирования работы программы заметил, что выбор начального приближения влияет только на количество итераций до получения заданной точности. Как следствие, если нет возможности нарисовать график или определить начальное приближение, можно брать любые значения. Вопрос будет стоять только в скорости получения результата, за исключением значений, при которых определитель Jn(x,y)=0.

 

В ходе данной работы Я приобрёл дополнительный опыт программирования на языке С++, научился применять его для решения задач по Численным методам. Кроме того, разобрался и освоил метод Ньютона для решения систем нелинейных уравнений. Готовясь к выполнению работы, разобрал смежные методы и изучил теоретическую часть вопроса.

 

Список литературы

 

1. П.И. Монастырный «Сборник задач по методам Вычислений» Минск, «Университетское»; 2000.

2. В.М. Вержбицкий. Численные  методы (линейная алгебра и нелинейные  уравнения). - Москва, «Высшая школа»; 2000.

3. Н.С.Бахвалов, А.В.Лапин, Е.В.Чижонков. Численные методы в задачах и упражнениях. - Москва, «Высшая школа»; 2000.

4. Мэтьюз, Джон, Г.,Финк, Куртис, Д. Численные методы MATLAB, 3-е издание.- Москва, «Вильяс»; 2001.

5. Сайт http://www.0zd.ru/

6. Сайт http://www.wolframalpha.com/

7. Сайт http://www.apmath.spbu.ru/