Курсовая работа системы нелинейных уравнений

Курсовая работа: Решение систем нелинейных уравнений методом Бройдена

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

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Факультет автоматики и электромеханики

Кафедра «Автоматизированные и вычислительные системы»

Специальность «Вычислительные машины, комплексы, системы и сети»

по дисциплине «Вычислительная математика»

Тема работы «Решение систем нелинейных уравнений методом Бройдена»

Пояснительная записка 26 с., 14 рисунка, 2 источника. Ключевые слова: МЕТОД БРОЙДЕНА, РЕШЕНИЕ СИСТЕМ МЕТОДОМ БРОЙДЕНА, РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

Объект исследования или разработки – решение систем нелинейных уравнений методом Бройдена.

Цель работы – создать программу, иллюстрирующую решение систем нелинейных уравнений методом Бройдена и исследовать результат ее работы.

Полученные результаты – листинг полученный программы, проверка соответствия найденных решений точным решениям заданной системы нелинейных уравнений.

Основные конструктивные, технологические и технико-эксплуатационные характеристики — персональная ЭВМ.

1. Алгоритм бройдена

1.1 Входные данные для алгоритма Бройдена

1.2 Содержание алгоритма Бройдена

1.3 Метод исключения Гаусса для решения СЛАУ

1.4 Вывод формулы пересчета Бройдена

2. Разработка программы и иследование результата ее работы

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

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

,

где — нелинейные функции от , в тождество.

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

Для большинства практических задач отсутствует аналитическое выражение для функции , а значит, и для . В этом случае приходится прибегать к аппроксимации якобиана. Одним из способов такой аппроксимация является метод Бройдена [1].

В курсовой работе будет рассматриваться метод решения Бройдена для систем нелинейных уравнений.

1. АЛГОРИТМ БРОЙДЕНА.

1.1 Входные данные для алгоритма Бройдена

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

1. 2 Содержание алгоритма Бройдена

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

Для начального вектора формируется матрица Якоби на основе конечно-разностной аппроксимации производных и аналогично методу Ньютона находится вектор очередного приближения из решения системы уравнений. . На следующих шагах поиска матрица Якоби рассчитывается по формуле пересчета Бройдена

,

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

Поскольку необходимо решить линейное уравнение, то рассмотрим метод решения Гаусса.

1.3 Метод исключения Гаусса для решения СЛАУ

Суть всех методов исключения состоит в приведении исходной системы уравнений к системе более простого вида, для которой легко найти решение. К этим методам можно отнести метод исключения Гаусса, который имеет много вычислительных схем и, как показали исследования, является идеальным алгоритмом для решения СЛАУ.

Рассмотрим сначала самую простую схему – схему единственного деления. Применение схемы единственного деления продемонстрируем на примере СЛАУ 4- го порядка

Разделив первое уравнение системы на , получим

Из второго уравнения системы вычтем первое, умноженное на коэффициент при , то есть на . В результате получаем:

=

Поступая таким же образом с третьим и последующими уравнениями системы, получим

;

;

.

К выделенной системе применим тот же алгоритм, что и к исходной. В результате получаем

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

, , .

1.4 Вывод формулы пересчета Бройдена

В процессе построения методов Ньютона и секущих решения нелинейного скалярного уравнения
функция f(x) в окрестности текущей точки подменяется линейной функцией (аффинной моделью)

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

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

Равенство , переписанное в виде , называют соотношением секущих в Оно легко обобщается на n -мерный случай и лежит в основе вывода метода Бройдена. Опишем этот вывод.

В n-мерном векторном пространстве соотношение секущих представляется равенством

,

где — известные n-мерные векторы, — данное нелинейное отображение, а — некоторая матрица линейного преобразования в . С обозначениями , соотношение секущих в обретает более короткую запись . Аналогично одномерному случаю, а именно, по аналогии с формулой , будем искать приближения к решению векторного уравнения по формуле . Обратимую n x n-матрицу в ней нужно подобрать так, чтобы она удовлетворяла соотношению секущих . Но это соотношение не определяет однозначно матрицу : глядя на равенство , легко понять, что при n>1 существует множество матриц , преобразующих заданный n-мерный вектор в другой заданный вектор (отсюда — ясность в понимании того, что могут быть различные обобщения одномерного метода секущих).

При формировании матрицы будем рассуждать следующим образом. Переходя от имеющейся в точке аффинной модели функции F(x) к такой же модели в точке мы не имеем о матрице линейного преобразования никаких сведений, кроме соотношения секущих . Поэтому исходим из того, что при этом переходе изменения в модели должны быть минимальными. Эти изменения характеризует разность . Вычтем из равенства определяющее равенство и преобразуем результат, привлекая соотношение секущих . Имеем:

Представим вектор в виде линейной комбинации фиксированного вектора определенного в , и некоторого вектора t, ему ортогонального: ,

Подстановкой этого представления вектора в разность получаем другой ее вид

Анализируя выражение , замечаем, что первое слагаемое в нем не может быть изменено, поскольку — фиксированный вектор при фиксированном k . Поэтому минимальному изменению аффинной модели будет отвечать случай, когда второе слагаемое в будет нуль-вектором при всяких векторах t, ортогональных векторам , т.е. следует находить из условия

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

Таким образом, приходим к так называемой формуле пересчета С. Бройдена

2. РАЗРАБОТКА ПРОГРАММЫ И ИСЛЕДОВВАНИЕ РЕЗУЛЬТАТА ЕЕ РАБОТЫ

Задача. Разработать программу, реализующую метод Бройдена.

Структура программы. Программа была разработана в интегрированной среде разработке приложений Microsoft Visual Studio 2008 на языке программирования C#, проект программы Console Application. В ходные данные программы начальный вектор решения, начальная матрица Якоби и удовлетворяющая погрешность. Программа решает систему уравнений . Если программа не находит решения удовлетворяющего требуемой точности за 10 итераций, то поиск решения прекращается, а так же если процесс расходится (в соответствии с приложением А).

Введем матрицу Якоби , погрешность 0,3 начальное решение является точным решение. На 1 итерации получаем результат решения (рисунок 1).

Рисунок 1 – Первый пример работы программы

Результат точное решение на 1 шаге. Попробуем задать начальное решение отличное от точного (рисунок 2).

Рисунок 2 – второй пример работы программы

Получили близко решение к точному решению. Попробуем уменьшить погрешность (рисунок 3).

Рисунок 3 – третий пример работы программы

Получили точное решение. Попробуем сильнее отойти в начальном решении от точного (рисунок 4).

Рисунок 4 – Четвертый пример работы программы

Получаем точное решение. Уменьшим погрешность и сильнее отойдем от точного решения. Теперь начальное решение произвольное (рисунок 5).

Рисунок 5 – Пятый пример работы программы

Видим увеличение количества итераций. Решение получили точное. Немного изменим начальную матрицу Якоби (рисунок 6).

Рисунок 6 – Шестой пример работы программы

Увеличение количества итераций. Решение точное. Теперь возьмем другую матрицу Якоби (рисунок 7).

Рисунок 7 – Седьмой пример работы программы

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

Попробуем с начальной матрицей Якоби. Процесс решения стал расходится. Делаем вывод, что не смогли найти решения из-за начального решения (рисунок 8).

Рисунок 8 – Восьмой пример работы программы

На основе рисунка 9, рисунка 10 и рисунка 11 видим, что наша первая матрица Якоби была удачно выбрана.

Матрица Якоби близка к первой матрице Якоби (рисунок 12).

Рисунок 9 – Девятый пример работы программы

Рисунок 10 – Десятый пример работы программы

Рисунок 11 – Одиннадцатый пример работы программы

Рисунок 12 – Двенадцатый пример работы программы

Попробуем изменить систему уравнений, решаемую программой и посмотрим на результаты работы программы (рисунок 13,14).

Рисунок 13 – Тринадцатый пример работы программы

Рисунок 14 – Четырнадцатый пример работы программы

ЗАКЛЮЧЕНИЕ

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

Данная курсовая работа выполнена в полном объеме. В курсовой работе был рассмотрен метод Бройдена, написана программа реализующая его.

СПИСОК ЛИТЕРАТУРЫ

1. С.Л. Подвальный, Л.В. Холопкина. Вычислительная математика- учебное пособие ВГТУ, 2004 — 147 с.

2. Методы решения систем нелинейных уравнений. Метод Ньютона. Его реализации и модификации. — Электрон. дан. – Режим доступа: www.exponenta.ru/educat/referat/XVkonkurs/15/index.asp.

ПРИЛОЖЕНИЕ

/*программа предназначена для решения системы нелинейных уравнений.

Программа выполнена 1 ноября 2009 года. Обем необходимой памяти для работы составляет 124 КБ. Версия программы №1.Автор Харитонова Яна Андреевна.*/

static void Main(string[] args)

Console.WriteLine(«x+y-3» + «\n» + «x^2+y^2-9»);

double[,] yakob = new double[N, N];

Console.WriteLine(«введите элементы матрицы Якоби»);

for (int i = 0; i = 0; i—)

for (int j = i + 1; j = 0)

double[] Y = new double[N];

Y[0] = (XJ[0] + XJ[1] — 3) — Bnach[0];

Y[1] = (XJ[0] * XJ[0] + XJ[1] * XJ[1] — 9) — Bnach[1];

Решение нелинейных уравнений

Автор: Katerine122 • Январь 6, 2021 • Курсовая работа • 5,614 Слов (23 Страниц) • 197 Просмотры

Министерство образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Факультет математики и информационных технологий

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

«Программная инженерия задач вычислительной математике»

ОГУ 09.03.04. 3019. 562. ПЗ

« ___ »________________ 2020 г.

Студент группы з-17Пинж(ба)РПиС

« ___ »________________2020 г.

Оренбург 2020 [pic 1]

[pic 2] Задание

Решение нелинейных уравнений

Разработать ПС и решить уравнение методами половинного деления (бисекций), хорд, касательных (метод Ньютона) с точностью до 0,001. Интервалы выбрать самостоятельно. х 3 -3х-2е -х =0

Система линейных алгебраических уравнений (СЛАУ)

Разработать ПС и решить СЛАУ методами Гаусса, итераций (метод последовательных приближений), Зейделя. Для методов итераций и Зейделя решить с точностью 0,001.

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

Разработать ПС и решить СНУ методами простой итерации и Ньютона с точностью 0,001.

Интерполирование функций (приближение функций)

1. Интерполируемая функция задана таблицей

Построить интерполяционный многочлен Лагранжа, найти значение функции в точке 3,5.

2. Построить интерполяционный многочлен Ньютона по первой таблице.

Численное интегрирование. Численное дифференцирование

1. Вычислить интеграл методом трапеций при n=7 [pic 5]

2. Вычислить интеграл по формуле Симпсона при n=7 [pic 6]

3. Функция y=f(x) задана табл.

Методом численного дифференцирования найти две производные этой функции в точке х =3.

Численное решение обыкновенных дифференциальных уравнений (ОДУ)

Разработать ПС и решить дифференциальное уравнение методами: [pic 7] [pic 8]

y’=x+y/2 y(0)=1 h= 0,1 на отрезке [0,1]

Аннотация

В разработанных программных средствах реализованы проекты на основе Windows приложений в Visual Studio. В работе дается краткое теоретическое описание каждого метода, решения задачи, результаты работы.

Описывается процесс работы программ.

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

Работа содержит 24 рисунка, 47 листов, 7 таблиц..

Решение не линейных уравнений 8

Решение системы линейных алгебраических уравнений 11

Решение системы нелинейных уравнений 15

Решение обыкновенных дифференциальных уравнений 17

Интерполирование функции 20

Численное интегрирование 24

Численное дифференцирование 26

Список использованных источников 29

Приложение 1. Листинг кода 30

Приложение 2. Экранные формы 46

Введение

Раздел математики, который изучает разные проблемы получения числовых результатов решения математических задач, называют вычислительной математикой. Вычислительная математика превратилась в самостоятельную ветвь относительно недавно: примерно в середине двадцатого века. Это было связано с появлением собственных внутренних задач. Вычислительная математика имеет столь же древнюю и богатую историю, что и сама математика. Почти все результаты математики, которые носили формульный вид, ложились в копилку вычислительной математики. Наверное, следует признать, что разделение математики на «чистую», прикладную, вычислительную соответствует скорее узкой специализации математиков, а не задачам, которые математика призвана решать. С появлением ЭВМ начался «золотой век» вычислительной математики. Её приложения в науке и технике расширяются с каждым годом. Методы математики можно условно разделить на четыре группы: качественные, аналитические, методы возмущений и численные. Качественные методы позволяют определить само существование (или несуществование) решения, но не найти его. Примерами могут служить: теорема о корнях алгебраического полинома, теорема Бендиксона о предельных циклах на плоскости и т.п. Аналитические методы дают формулы для решения конкретной задачи. При этом совершенно необязательно в алгоритме решения задачи должно быть конечное число формул, могут быть и бесконечные процессы, предельные переходы, т.е. весь разнообразный набор средств математического анализа (примером может служить метод последовательных приближений для решения задачи Коши дифференциального уравнения). Могут возникнуть задачи, в которых существует аналитический метод, но он является практически неприменимым при росте размерности задачи. Так, при решении систем линейных алгебраических уравнений по правилу Крамера, увеличение размерности определителя системы до n приводит к тому, что количество вычислений будет расти как n!. Методы возмущений занимают промежуточное положение между численными и аналитическими методами, т.е. между методами, дающими приближенное и точное решение. Они могут быть выделены в особое направление, как по тому разнообразному математическому аппарату, так и по тому месту в методах вычислительной математики, которое они занимают. В этих методах обычно рассматривается задача, зависящая от малого параметра, который является возмущением предельной задачи. Решение предельной задачи предполагается известным. Для решения задачи ис- 4 пользуется и информация о малости параметра возмущения и информация о решении предельной задачи. Численные методы – это методы, которые могут быть сведены к арифметическим действиям над числами. Успех численных методов объясняется их сравнительно простой реализацией на ЭВМ. Искусство вычислений состоит фактически не столько в предъявлении числовых результатов в виде таблиц, графиков, сколько в обосновании того, что эти результаты получены с заданной точностью. В процессе проектирования и выполнения научных и инженерных исследований приходится выполнять самые разные вычисления. Некоторые просты и не требуют применения вычислительных машин, другие без ЭВМ невыполнимы. Можно выделить следующие категории расчетов, требующих применения ЭВМ: ‰ вычисления, аналогичные выполняемым вручную, но выполняемые многократно; ‰ вычисления слишком громоздкие, чтобы их можно было выполнить вручную, обеспечив необходимую точность за приемлемое время; ‰ подготовка графического представления данных, подготовка данных для производства и выпуска документации. Характер работы инженера или исследователя определяет многократное повторение решаемых задач, в число которых входят алгебраические и трансцендентные уравнения, задачи на собственные значения, обыкновенные дифференциальные уравнения, дифференциальные уравнения в частных производных, оптимизация, обработка массивов числовых данных. Математическая формулировка технической задачи не должна рассматриваться как объект, не подлежащий изменению. Задачу следует с помощью эквивалентных преобразований привести к виду, наиболее удобному для решения.

Курсовая работа по дисциплине: «Численные методы» на тему: «Исследование метода простой итерации и метода Ньютона для решения систем двух нелинейных алгебраических уравнений»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра экономической информатики

Курсовая работа

по дисциплине «Численные методы»

на тему: «Исследование метода простой итерации и метода Ньютона для решения систем двух нелинейных алгебраических уравнений»

Студент: Обухова Т.С.

Преподаватель: Сарычева О.М.

СОДЕРЖАНИЕ

1 Постановка задачи. Математическое описание методов

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

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

2 Описание программного обеспечения

3 Описание тестовых задач

4 Анализ результатов, выводы

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

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

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

Численный метод, в котором производится последовательное, шаг за шагом, уточнение первоначального грубого приближения решения, называется итерационным. Итерационные методы дают возможность найти решение системы как предел бесконечного вычислительного процесса, позволяющего по уже найденным приближениям к решению построить следующее, более точное приближение. Плюсом таких методов является самоисправляемость и простота реализации на ЭВМ. В точных методах ошибка в вычислениях приводит к накопленной ошибке в результате, а в случае сходящегося итерационного процесса ошибка в каком-либо приближении исправляется в последующих итерациях, и такое исправление требует, как правило, только нескольких лишних шагов единообразных вычислений. Для начала вычислений итерационных методом требуется знание одного или нескольких начальных приближений к решению.

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

1 Постановка задачи. Математическое описание методов

При определенных условиях ЭО в установившемся режиме описывается системой нелинейных АУ вида . Если при этом входной сигнал 1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.png» /> известен, то для определения соответствующего значения Предположим, что система допускает лишь изолированные корни. Число этих корней и их приближенные значения можно установить, построив кривые 1/AppData/Local/Temp/msohtmlclip1/01/clip_image014.png» /> и Функции 1/AppData/Local/Temp/msohtmlclip1/01/clip_image020.png» /> и где 1/AppData/Local/Temp/msohtmlclip1/01/clip_image028.png» /> (Коэффициенты 1/AppData/Local/Temp/msohtmlclip1/01/clip_image040.png» />, F=[1/AppData/Local/Temp/msohtmlclip1/01/clip_image047.png» />; j=[1/AppData/Local/Temp/msohtmlclip1/01/clip_image049.png» /> 1/AppData/Local/Temp/msohtmlclip1/01/clip_image053.png» /> 1. Решение системы 1/AppData/Local/Temp/msohtmlclip1/01/clip_image060.png» /> обеими методами, графики решений и ошибок при начальных условиях 2. При начальных условиях 3. При начальных условиях 4. Для проверки времени счета введем в модули методов новую переменную t, определяющую время счета, и возьмем начальные приближение, очень далекие от точного решения 1/AppData/Local/Temp/msohtmlclip1/01/clip_image073.jpg» />