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

Анализ и сравнение численных методов решения нелинейных уравнений

Автор работы: Пользователь скрыл имя, 27 Октября 2014 в 18:42, курсовая работа

Краткое описание

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

Содержание

1. Введение 3
2. Численные методы решения нелинейных
уравнений 5
3. Постановка задачи 6
4. Основные методы решения нелинейных
уравнений 7
5.1. Метод половинного деления 8
5.2. Метод касательных 11
5.3. Метод хорд 14
5. Практическая часть 19
6. Заключение 26
7. Список используемой литературы 27

Прикрепленные файлы: 1 файл

Пояснительная записка .docx

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

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

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

«Башкирский государственный университет»

Кафедра математического моделирования

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

на тему: ««Анализ и сравнение численных методов решения нелинейных

Выполнили студенты 3 курса

группы БИ-31

Серебряков Е.А.________

Федоров С.О.__________

«___»__________2014г.

Научный руководитель к.ф.-м.н., доцент

Карасев Е.М. __________

«___»____________2014г.

Содержание

1. Введение 3
2. Численные методы решения нелинейных

1. Постановка задачи 6
2. Основные методы решения нелинейных

5.1. Метод половинного деления 8

5.2. Метод касательных 11

5.3. Метод хорд 14

1. Практическая часть 19
2. Заключение 26
3. Список используемой литературы 27

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

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

В своей курсовой работе я поставила три основные цели и задачи:

1. Изучение разновидности комбинаторных задач.
2. Изучение основных комбинаторных операций.
3. Изучение комбинаторики как раздел элементарной алгебры.

Для достижения поставленных целей и решения задач в курсовой работе я использовала различные источники информации. В основном это были книги Бахвалов Н. С. Численные методы и Вержбицкий В. М. Численные методы. Линейная алгебра и нелинейные уравнения. В них четко и точно изложен нужный для моей курсовой работы материал.

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

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

Проблема численного решения линейных уравнений интересует математиков уже несколько столетий. Первые математические результаты появились в XVIII веке. В 1750 году Г. Крамер (1704-1752) опубликовал свои труды по детерминантам квадратных матриц и предложил алгоритм нахождения обратной матрицы, известный как правило Крамера. Гаусс в 1809 году опубликовал работу, посвященную движению небесных тел, в которой был изложен метод для решения линейных систем, известный как метод исключения.

В 40-х годах XX века с появлением компьютеров сильно возрос интерес к численным методам. Тогда же началось активное исследование существующих методов для их реализации на ЭВМ и предпринимались активные попытки увеличить их точность.

Вплоть до 80-х годов решение вычислительных задач было ограничено ресурсами ЭВМ, поэтому особое значение придавалось экономичности алгоритмов.

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

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

Пусть имеется уравнение вида

где f (x) — заданная алгебраическая или трансцендентная функция. (Функция называется алгебраической, если для получения её значения нужно выполнить арифметические операции и возведение в степень с рациональным показателем. Примеры трансцендентных функций — показательная, логарифмическая, тригонометрические, обратные тригонометрические.)

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

Поставим задачу найти такое приближенное значение корня xпр, которое мало отличается от точного значения корня x*, так что выполняется неравенство │x* – xпр │ 0, граница a сдвигается вправо – заменить a на с: a:= c.

Перейти к шагу 1.

Алгоритм деления отрезка пополам довольно медленный, но зато абсолютно застрахован от неудач. Основное достоинство метода состоит в том, что его скорость сходимости не зависит от вида функции f (x). Данный метод не имеет дополнительных условий сходимости, кроме f(a)∙f(b) 0, то нулевое приближение выбираем x0=a. Рассмотрим геометрический смысл метода. Рассмотрим график функции y=f(x). Пусть для определенности f ‘(x) > 0 и f “(x) > 0 (рис. 1). Проведем касательную к графику функции в точке B (b, f (b)). Ее уравнение будет иметь вид:

y = f (b) + f ’(b) * (x – b)

Полагая в уравнении y = 0 и учитывая, что f ’(x) ¹ 0, решаем его относительно x. Получим :

x = b – (f (b) /f ‘(b))

Нашли абсциссу x1 точки c1 пересечения касательной с осью Оx:

x1 = b – (f (b) – f ’ (b))

Проведем касательную к графику функции в точке b1 (x1; f (x1)).Найдем абсциссу x2 точки с2 пересечения касательной с осью Ox:

x2 = x1 – (f (x1) / ( f ’(x1))

xk+1 = x k – ( f (x k) / f ’(x k)) (3)

Таким образом, формула (3) дает последовательные приближения (xk) корня, получаемые из уравнения касательной , проведенной к графику функции в точке b k (x k; f (x k0) метод уточнения корня c [a;b] уравнения f (x) = 0 с помощью формулы (3) называется методом касательной или методом Ньютона.

Геометрический смысл метода касательных состоит в замене дуги y = f (x) касательной, одной к одной из крайних точек . Начальное приближение x 0=a или x0 = b брать таким, чтобы вся последовательность приближения х k принадлежала интервалу (a;b). В случае существования производных f ’, f ”, сохраняющих свои знаки в интервале, за х0 берется тот конец отрезка [a;b], для которого выполняется условие f ’(х0) * f (х0) > 0. Для оценки приближения используется общая формула :

|c-x k-1 | £ | f (x k+1)/m| , где m = min f ’(x) на отрезке [a;b] .

На практике проще пользоваться другим правилом :

Если на отрезке [a;b] выполняется условие 0 НЕТ

Метод хорд.

Пусть на отрезке [a;b] функция непрерывна, принимает на концах отрезка значение разных знаков, а производная f ‘(x) сохраняет знак. В зависимости от знака второй производной возможны следующие случаи расположения кривых (рис. 1).

Рис. 1. Возможные случаи расположения кривых.

Алгоритм приближенного вычисления корня методом хорд.
Исходные данные: f (x) – функция; ε – требуемая точность; x0 – начальное приближение.
Результат: xпр – приближенный корень уравнения f (x) = 0.

Рис. 2. Геометрическая интерпретация метода хорд для случая f ‘(x) f »(x)>0.

Рассмотрим случай, когда f ‘(x) и f »(x) имеют одинаковые знаки (рис. 2).

График функции проходит через точки A0(a,f(a)) и B0(b,f(b)). Искомый корень уравнения (точка x*) нам неизвестен, вместо него возьмет точку х1 пересечения хорды А0В0 с осью абсцисс. Это и будет приближенное значение корня.
В аналитической геометрии выводится формула, задающая уравнение прямой, проходящей через две точки с координатами (х1; у1) и (х2; у2): .
Тогда уравнение хорды А0В0 запишется в виде: .
Найдем значение х = х1, для которого у = 0: . Теперь корень находится на отрезке [x1;b]. Применим метод хорд к этому отрезку. Проведем хорду, соединяющую точки A1(x1,f(x1)) и B0(b,f(b)), и найдем х2 — точку пересечения хорды А1В0 с осью Ох: x2=x1 .
Продолжая этот процесс, находим: x3=x2. Получаем рекуррентную формулу вычисления приближений к корню xn+1=xn.
В этом случае конец b отрезка [a;b] остается неподвижным, а конец a перемещается.
Таким образом, получаем расчетные формулы метода хорд:

Дипломная работа: Сравнительный анализ численных методов

Министерство образования и науки Республики Казахстан

Карагандинский Государственный Технический Университет

По дисциплине: ”Математическое обеспечение САПР»

Тема: «Сравнительный анализ численных методов»

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

2. Методы решения нелинейных уравнений

2.1 Общие сведения

2.2 Метод касательных (метод Ньютона)

2.2.1 Общие сведения

2.2.2 Решение нелинейного уравнения методом касательных

2.3.1 Общие сведения

2.3.2 Решение нелинейного уравнения методом хорд

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

2.5.1 Общие сведения

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

2.6 Программа для решения нелинейных уравнений

3. Решение нелинейных уравнений методом интерполирования

3.2 Многочлен Лагранжа

3.3 Интерполяция сплайнами

3.4 Использование интерполяции на практике

3.4.1 Интерполяция с помощью многочлена Лагранжа

3.4.2 Обратная интерполяция

3.4.3 Интерполяция сплайнами

3.5 Программа для использования интерполяции

4. Итерационные методы решения систем линейных алгебраических уравнений

4.1 Общие сведения

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

4.2.1 Описание метода

4.2.2 Решение СЛАУ методом простых итераций

4.2.3 Программа для решения СЛАУ методом простых итераций

4.3 Метод Зейделя

4.3.1 Описание метода

4.3.2 Решение СЛАУ методом Зейделя

4.3.3 Программа дл решения СЛАУ методом Зейделя

4.4 Сравнительный анализ

5. Сравнительный анализ различных методов численного дифференцирования и интегрирования

5.1 Методы численного дифференцирования

5.1.1 Описание метода

5.1.2 Нахождение производной

5.2 Методы численного интегрирования

5.2.1 Общие сведения

5.2.2 Нахождение определенного интеграла

5.3.1 Решение ОДУ методом Эйлера

5.3.2 Решение ОДУ методом Рунге-Кутты

6.Численные методы решения обыкновенных дифференциальных уравнений

6.1 Общие сведения

6.2 Метод Эйлера

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

Введение

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

Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами, т.е. к тем действиям, которые выполняет ЭВМ.

В настоящее время появилось значительное число различных программных продуктов (MathCAD, MathLABи т.д.), с помощью которых, задавая только входные данные, можно решить значительное число задач.

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

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

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

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

Определить корень в заданном или любом выбранном отрезке методом хорд, касательных, простых итераций.

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

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

Используя функции f ( x) из п.1, построить интерполяционный многочлен L₄ (x) на [a, b], использовав в качестве узловых a иb, остальные необходимые узловые точки выбрать, разделив промежуток [a, b] на почти равные части. Вычислить значения f (x) и L₄ (x) в двух точках, одна из которых — середина крайней части, а вторая — середина части, содержащей точку . Сравнить полученные величины. Используя эти же узловые точки, провести обратную интерполяцию и определить значение х при y=0 . Полученный результат сравнить с ранее найденным решением уравнения.

Сравнить результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации.

Провести сравнительный анализ различных методов численного дифференцирования и интегрирования.

Найти численное решение обыкновенного дифференциального уравнения методом Эйлера и уточненным методом Эйлера с 5-ю и 20-ю шагами и сравнить их, если возможно с результатом точного решения ОДУ.

2. Методы решения нелинейных уравнений

2.1 Общие сведения

Рассмотрим уравнение вида f (x) =0, (2.1), где f (x) — любая нелинейная функция.

Корнем уравнения ( 2.1) называется значение , при котором. Способы приближенного решения, т.е. алгоритм решения, предполагает определение x * c некоторой наперед заданной точностью.

Для нахождения корней уравнения (2.1) различают следующие два этапа.

Отделения (локализации) корней, т.е. нахождение таких интервалов по аргументу x, внутри каждого из которых существует только один корень уравнения (2.1). Если у функции на концах исследуемого отрезка [a,b] функция имеет разные знаки, то на этом отрезке функция имеет не менее одного корня. Если же одинаковые знаки, то функция может не иметь корней или иметь четное число корней. Следовательно, локализация заключается в том, что необходимо установить отрезки, на которых есть смена знаков функции и, кроме того, выполнено условие единственности корня, т.е. функция на этом отрезке должна иметь первую производную с постоянным знаком. Из условия сходимости итерационной последовательности также требуется, чтобы вторая производная не меняла знак, т.е. на исследуемом отрезке функция бала бы только выпуклой или вогнутой.

Уточнение корней заключается в применении некоторого итерационного метода, в результате которого корень уравнения (2.1) может быть получен с любой наперед заданной точностью ε. При этом, останавливая процесс на какой-либо конечной итерации, необходимо оценить погрешность по сравнению с точным корнем, который неизвестен. Выбранный метод позволяет построить последовательность х₁ , х₂ , х₃ , …, х_k , … приближений к корню. Итерационный процесс состоит в последовательном уточнении начального приближения х0. Каждый такой шаг называется итерацией. В результате итераций находится последовательность приближенных значений корня х1, х2, х3, …, хk, … Если эти значения с ростом k стремятся к истинному значению корня , то итерационный процесс сходится.

Основными методами решения нелинейных уравнений, реализованных в виде численной процедуры, являются итерационные методы.

2.2 Метод касательных (метод Ньютона)

2.2.1 Общие сведения

Метод Ньютона, называемый также методом касательных, состоит в следующем. Рассмотрим в точке x₀ касательную к кривой y=f (x), задаваемую уравнением

За начальное приближение x₀ принимается один из концов отрезка [a, b], где значение функции имеет такой же знак, что и 2-я производная. Функция f (x) должна удовлетворять на отрезке [a, b] следующим условиям:

1) существование производных 1-го и 2-го порядков;

2) f ’ (x) 0;

3) производные 1-го и 2-го порядков знакопостоянны на отрезке [a, b].

Положим y=0, находим точку x₁ пересечения касательной с осью абсцисс:

Построив касательную в точке x_{1 (} рисунок 2.1), получаем по аналогичной формуле точку x₂ пересечения этой касательной с осью x и т.д. Формула для n-го приближения имеет вид:

Рисунок 2.1 — Метод касательных

В этом методе на n-й итерации проводится касательная к кривой y =f (x) при х=xn-1 и ищется точка пересечения касательной с точкой абсцисс. При этом необязательно задавать отрезок [a,b], содержащий корень уравнения, а достаточно лишь найти некоторое начальное приближение корня х.

Итерационный процесс останавливают при выполнении условия ; где ε — заданная точность.

2.2.2 Решение нелинейного уравнения методом касательных

1. Дано уравнение tg (0.36*x +0.4) =x 2 . Решить его методом касательных с точностью решения=0,001.

Для нахождения корня исследуем функцию

.

График функции представлен на рисунке 2.2

Рисунок 2.2 — График исследуемой функции

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

Выбираем концы отрезка: a= -1; b = 0. График функции на этом отрезке представлен на рисунке 2.3

Рисунок 2.3 — График функции на выбранном отрезке

Проверяем существование корня на отрезке по условию

x>0.001

x>0.001

,

x 3 -0,2x 2 +0,4x-1,4=0.

Решить его методом касательных с точностью решения=0,001.

Для нахождения корня исследуем функцию

.

График функции представлен на рисунке 2.5

Рисунок 2.5 — График исследуемой функции

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

Выбираем концы отрезка: a= -0.1; b = 1.5 График функции на этом отрезке представлен на рисунке 2.6

Рисунок 2.6 — График функции на выбранном отрезке

Проверяем существование корня на отрезке по условию

-3,066375

Экстремумов на выбранном отрезке нет.

Находим первую производную функции:

;

В точке a первая и вторая производные равны:

,

В точке bпервая и вторая производные равны:

,

Выбираем тот конец отрезка, значение функции в котором совпадает со знаком 2-ой производной.

x₀ = 1,5 2.125*6.55=13,91875,

x>0.001

x>0.001

x>0.001

x 2 .

Решить его методом хорд с точностью решения=0,001.

Как в предыдущем методе для нахождения корня исследуем функцию

.

Выбираем концы отрезка: a= -1; b = 0. График функции на этом отрезке представлен на рисунке 2.9

Рисунок 2.9 — График функции на выбранном отрезке

По данным из п.2.2.2 за x₀ выбираем тот конец отрезка, который совпадает со знаком 2-ой производной. А за x₁ второй конец отрезка.

x>0.001

x>0.001

x>0.001

x>0.001

x>0.001

x 3 -0,2x 2 +0,4x-1,4=0. Решить его методом хорд с точностью решения=0,001.

Как в предыдущем методе для нахождения корня исследуем функцию

.

График функции представлен на рисунке 2.5

Выбираем концы отрезка: a= -0.1; b = 1.5 График функции на этом отрезке представлен на рисунке 2.11

Рисунок 2.11 — График функции на выбранном отрезке.

По данным из п.2.2.2 за x₀ выбираем тот конец отрезка, который совпадает со знаком 2-ой производной и удовлетворяет условию . А за x₁ второй конец отрезка.

x>0.001

x>0.001

x>0.001

x>0.001

x>0.001

x>0.001

x>0.001

x 0 вычисления следует вести до тех пор, пока не окажется выполненным неравенство

Если величина , то можно использовать более простой критерий окончания итераций:

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

1. Дано уравнение tg (0.36*x +0.4) =x 2 . Решить его методом простых итераций с точностью решения=0,001. Как в предыдущих методах для нахождения корня исследуем функцию

.

Выбираем концы отрезка: a= -1; b = 0. График функции на этом отрезке представлен на рисунке 2.14.

Рисунок 2.14 — График функции на выбранном отрезке

Приведем уравнение к виду x=x- af (x), где итерационная функция  (x) =x- af (x), a — итерационный параметр.

Максимальное и минимальное значения производной достигаются на концах отрезка:

Применяем формулу x=x — af (x) =f (x):

2. Дано уравнение x 3 -0,2x 2 +0,4x-1,4=0. Решить его методом методом простых итераций с точностью решения=0,001.

Для нахождения корня исследуем функцию .

Выбираем концы отрезка: a= -0.1; b = 1.5 График функции на этом отрезке представлен на рисунке 2.15.

Рисунок 2.15 — График функции на выбранном отрезке.

Найдем корень с помощью встроенной функции root :

Приводим уравнение к виду x= f (x), где

Проверим условие сходимости:

Максимальное по модулю значение производной итерационной функции достигается в левом конце отрезка:

Применяем формулу x=  (x):

2.6 Программа для решения нелинейных уравнений

На рисунках 2.16, 2.17 представлены программы для решения нелинейных уравнений методами хорд и касательных.

Пользователь вводит необходимые данные и при нажатии кнопки «Решить» выводится результат.

Листинги программ представлены в приложениях А, Б.

Рисунок 2.16 — Программа для решения методом касательных

Рисунок 2.17 — Программа для решения методом хорд

3. Решение нелинейных уравнений методом интерполирования

3.1 Интерполяция

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

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

Допустим, в n+1 точке заданы значения x₀ ,x₁ ,…x_n и соответствующие им значения f (x₀ ), f (x₁ ), …, f (x_n ). Значения f (x_i ) вычисляются только в случае, если известна функция f (x), но эти значения могут быть получены, например, экспериментальным путем как значение некой неизвестной функции.

Точки x_i , в которых известны значения функции, носят названия узлов интерполяции .

Интерполяция заключается в выборе функции φ (х), значения которой в узлах интерполяции совпадают со значениями f (x_i ).

Между узлами значения этих функций могут отличаться (рисунок 3.1).

Рисунок 3.1 – Интерполяция

Мы рассмотрим простейший случай, когда в качестве интерполируемой функции используется полином степени n. Преимущества такой интерполяции очевидны. Значения полинома легко вычисляются, имеют непрерывную производную.

3.2 Многочлен Лагранжа

Пусть известны значения некоторой функции f в n+1 различных точках. Возникает задача приближенного восстановления функции f в произвольной точке x. Часто для решения этой задачи строится алгебраический многочлен L_n (x) степени n, который в точках x_i принимает заданные значения, т.е.

и называется интерполяционным.

В частности, мы рассматриваем построение интерполирующего многочлена Лагранжа.

,

f_i — значения интерполируемой функции в i-том узле;

— коэффициент интерполяции Лагранжа

.

Можно сказать, что L₁ (x) — линейная функция x, поэтому такую интерполяцию называют линейной (она производится для двух точек).

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

Обратная интерполяция заключается в построении зависимости x (y) и, затем, с помощью такого многочлена легко можно найти корень нелинейного уравнения.

Многочлен Лагранжа в этом случае выглядит следующим образом:

,

— коэффициент интерполяции Лагранжа

.

Если задано достаточно много узлов на отрезке [a,b], то интерполирующие функции на отрезке [a,b] представляют собой непрерывную функцию, уже первая производная которой является кусочно-непрерывной.

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

3.3 Интерполяция сплайнами

Пусть отрезок [a, b] разбит на n одинаковых частей точками x₀ , x_1, …x_n .

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

Например, линейная интерполяция — это сплайн первого порядка с дефектом 1.

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

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

Этот сплайн не прерывен вместе с первой производной, но непрерывность второй производной не гарантируется, т.е. дефект сплайна равен 2. Если этот сплайн имеет непрерывную вторую производную на отрезке [a, b], т.е. имеет дефект 1, то такой сплайн носит название глобального.

Для построения кубического сплайна используется формула:

Для построения глобального сплайна, т.е. сплайна с дефектом 1 необходимо, начиная со 2-го узла, поставить условие непрерывности 2-й производной, т.е.2-я производная при подходе к точке 2 и дальше слева (x₁ -0) должна равняться второй производной при подходе справа (x₁ +0).

Такие равенства можно составить для всех внутренних узлов x₁ до x_{n -1} . Затем используем условия на краях x₀ и x_n , получаем систему уравнений, которая и обеспечит дефект 1.

Очевидно, что при наличии S3 на соответствующих участках, построение таких равенств не представляет особого труда.

Приравнивая эти значения, для определения m получим СЛАУ.

В двух крайних точках:

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

3.4 Использование интерполяции на практике

3.4.1 Интерполяция с помощью многочлена Лагранжа

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

Составляем таблицу узлов интерполяции:

Поскольку n=5 строим интерполяционный многочлен L₅ (x):

L₅ (x) =P₅₀ *f (x₀ ) +P₅₁ *f (x₁ ) + P₅₂ *f (x₂ ) + P₅₃ *f (x₃ ) + P₅₄ *f (x₄ ) + P₅₅ *f (x₅ )

В результате получаем многочлен:

L₅ (x) = 1.049*10 -3 *x 5 +5.4373*10 -3 *x 4 +0.027*x 3 — 0,936*x 2 + 0,424*x +0.42278, X= — 0.48051

Подставляя заданное значение аргумента, получаем ответ:

При подстановки того аргумента в заданную функцию, получаем такой же результат:

f (-0.48051) =0.00011

3.4.2 Обратная интерполяция

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

Составляем таблицу узлов интерполяции:

Поскольку n=4 строим интерполяционный многочлен L₄ (y):

В результате получаем многочлен:

L₄ (y) = 7.99*y 4 -0.8176*y 3 — 0.4932* y 2 +0.9008*y — 0.4759

Подставляя заданное значение функции, получаем ответ:

Таким образом, получаем приближенное значение корня:

При подстановки этого аргумента в заданную функцию, получаем результат:

f (-0,47591) = 0.00625

3.4.3 Интерполяция сплайнами

На участке [b,b+2] выбрать 3 точки (b,b+1,b+2), построить два сплайна на двух отрезках, убедиться в том, что в точке b+1 производная не терпит разрыва.

Для построения сплайна используем формулы:

h=

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

Для построения глобального сплайна необходимо, начиная со второго узла поставить условие непрерывности 2-ой производной, т.е.2-ая производная при подходе к точке 2 и дальше слева (x₁ -0) должна равняться 2-ой производной при подходе справа (x₁ +0):

Приравнивая эти значения, получаем:

Для нашей функции получаем:

0.42435

— 2.10346

После того, как мы нашли m₁ , можем построить графики (рисунок 3.2).

Рисунок 3.2 — Глобальная интерполяция сплайнами

Также можно сравнить с графиком самой функции (рисунок 3.3).

Рисунок 3.3 — Сравнение графика функции и глобальной интерполяции

3.5 Программа для использования интерполяции

На рисунках 3.4 представлена программа для использования интерполяции сплайнами. Пользователь вводит необходимые данные и при нажатии кнопки «График» строится кубический сплайн.

Листинг программы представлен в приложении В.

Рисунок 3.4 — Программа для использования интерполяции сплайнами

4. Итерационные методы решения систем линейных алгебраических уравнений

4.1 Общие сведения

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

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

4.2.1 Описание метода

Рассмотрим СЛАУ вида

Ax = B, где А — матрица. (1)

Если эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру

x_k → x*, где х* — решение заданной системы.

В конечном варианте система будет имееть вид:

Условием сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е.

, или .

Необходимо, чтобы диагональные элементы матрицы А были ненулевыми.

Для преобразования системы можно выполнить следующие операции:

В результате получим систему:

В ней на главной диагонали матрицы С находятся нулевые элементы, остальные элементы выражаются по формулам:

Итерационный процесс продолжается до тех пор, пока значения х₁ ( k), х₂ ( k), х₃ ( k) не станут близкими с заданной погрешностью к значениям х₁ ( k-1), х₂ ( k-1), х₃ ( k-1).

4.2.2 Решение СЛАУ методом простых итераций

Решить СЛАУ методом простых итераций с точностью .

Для удобства преобразуем систему к виду:

,

Принимаем приближение на 0-ом шаге:

,

,

На 1-м шаге выполняем следующее:

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

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 2-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 5-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 6-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

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

4.2.3 Программа для решения СЛАУ методом простых итераций

На рисунке 4.1 представлена программа для решения систем алгебраических линейных уравнений методом простых итераций.

Листинг программы приведен в приложении Г.

Рисунок 4.1 — Программа «Метод простых итераций»

4.3 Метод Зейделя

4.3.1 Описание метода

В этом методе результаты, полученные на k-том шаге, используются на этом же шаге. На (k+1) — й итерации компоненты приближения вычисляются по формулам:

Этот метод применим к система уравнений в виде Ax=B при условии, что диагональный элемент матрицы коэффициентов A по модулю должен быть больше, чем сумма модулей остальных элементов соответствующей строки (столбца).

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

, либо

4.3.2 Решение СЛАУ методом Зейделя

Решить СЛАУ методом Зейделя с точностью .

Эту систему можно записать в виде:

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

Для удобства преобразуем систему к виду:

,

Принимаем приближение на 0-ом шаге:

На 1-м шаге выполняем следующее:

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

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 2-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

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

4.3.3 Программа дл решения СЛАУ методом Зейделя

На рисунке 4.2 представлена программа для решения систем алгебраических линейных уравнений методом простых итераций.

Листинг программы приведен в приложении Г.

Рисунок 4.2 — Программа «Метод Зейделя»

4.4 Сравнительный анализ

Можно заметить, что в методе Зейделя быстрее мы достигаемой нужной точности, в нашем случае в точность была достигнута на 4-й итерации, когда в методе простых итераций она была достигнута на 6-й итерации. Но в то же время в методе Зейделя ставится больше условий. Поэтому вначале нужно произвести иногда довольно трудоемкие преобразования. В таблице 4.1 приведены результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации:

Сравнительный анализ методов численного решения систем нелинейных уравнений Текст научной статьи по специальности « Математика»

Аннотация научной статьи по математике, автор научной работы — Богданов А.Е., Торшина О.А.

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

Похожие темы научных работ по математике , автор научной работы — Богданов А.Е., Торшина О.А.

COMPARATIVE ANALYSIS OF COMPUTATIONAL METHODS OF SYSTEM OF NONLINEAR EQUATIONS

The consideration of numerous applied problems leads to systems of nonlinear equations , they include boundary problems for ordinary differential equations and partial differential equations (solved by the finite difference method), optimization problems, problems of minimization of functions of many variables, the use of implicit methods for integrating ordinary differential equations , etc. Numerical solution of systems of nonlinear equations in the general case is a more complicated problem than the solution of systems of linear equations, since there are no methods that guarantee the success of solving any problem of this kind. Identifying the optimal method and its further selection allows you to increase the chances of successfully solving systems of nonlinear equations . In connection with the relevance of the above-mentioned, this article presents the algorithms for methods for the numerical solution of systems of nonlinear equations , according to which the root of a typical system for applied problems was searched. According to the obtained results, a comparative analysis was conducted in order to identify the optimal method. The optimal method is the one that found the values of all the roots of the system with the required accuracy in the least number of iterations.

Текст научной работы на тему «Сравнительный анализ методов численного решения систем нелинейных уравнений»

СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ЧИСЛЕННОГО РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ

Богданов А.Е.1, Торшина О.А.2′ *

2 ORCID: 0000-0003-3999-0622, 1 2 Федеральное государственное бюджетное образовательное учреждение высшего образования Магнитогорский государственный технический университет им. Г.И. Носова, Магнитогорск, Россия

* Корреспондирующий автор (olganica[at]mail.ru)

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

Ключевые слова: краевые задачи, системы нелинейных уравнений, численные методы, дифференциальные уравнения.

COMPARATIVE ANALYSIS OF COMPUTATIONAL METHODS OF SYSTEM OF NONLINEAR EQUATIONS

Bogdanov A.E.1, Torshina O.A.2′ *

2 ORCID: 0000-0003-3999-0622, 1,2 Federal State Budgetary Educational Institution of Higher Education, Nosov Magnitogorsk State Technical University,

Corresponding author (olganica[at]mail.ru)

The consideration of numerous applied problems leads to systems of nonlinear equations, they include boundary problems for ordinary differential equations and partial differential equations (solved by the finite difference method), optimization problems, problems of minimization of functions of many variables, the use of implicit methods for integrating ordinary differential equations, etc. Numerical solution of systems of nonlinear equations in the general case is a more complicated problem than the solution of systems of linear equations, since there are no methods that guarantee the success of solving any problem of this kind. Identifying the optimal method and its further selection allows you to increase the chances of successfully solving systems of nonlinear equations. In connection with the relevance of the above-mentioned, this article presents the algorithms for methods for the numerical solution of systems of nonlinear equations, according to which the root of a typical system for applied problems was searched. According to the obtained results, a comparative analysis was conducted in order to identify the optimal method. The optimal method is the one that found the values of all the roots of the system with the required accuracy in the least number of iterations.

Keywords: boundary value problems, systems of nonlinear equations, numerical methods, differential equations.

В общем случае системы n нелинейных уравнений с n неизвестными x1,x2. ,xn принято записывать следующим образом (1).

Где F1, F2. Fn — функции независимых переменных.

Решением системы (1) является вектор (векторы) X* , при подстановке которого все уравнения системы обращаются в тождества (2).

Количество решений (единственное, конечное, бесконечное) зависит от рассматриваемого частного случая. Решение системы (1) можно разбить на три этапа: графическое разделение корней, выбор оптимальных начальных приближений, преобразование системы к требуемому методами виду с последующим поиском численных решений согласно алгоритмам.

Графическое разделение корней сводится к построению графика для системы (1) в любом математическом пакете, обладающем необходимыми графическими средствами (Maple, MathCad). На основании построенного графика можно сделать вывод о количестве решений системы и выбрать оптимальные нулевые приближения для поиска каждого корня рассматриваемыми численными методами.

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

В рамках статьи рассмотрены следующие итерационные процессы поиска корней: «метод простых итераций», «метод Ньютона», «метод секущих».

Условия сходимости итерационных процессов можно оценивать различными способами, в числе которых «принцип сжимающих отображений», представленный следующей теоремой: последовательность , k = 0,1. элементов n-мерного евклидова пространства, порожденная итерационным процессом xk+1 = F(xk), x0 = a, сходится

к решению X системы нелинейных алгебраических уравнений x = F(x) , если отображение v = F(x) является

сжимающим; при этом выполнено p(X, xk) е, то положить k = k + 1 и перейти к пункту 2.

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

Для сходимости итерационного процесса необходимо, чтобы норма производной вектор-функции Ф^) = (ф, ф2. фп)T была меньше некоторого положительного числа q Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

х = х + tg(xy + 0.2) — х2 — = у sec2 (ху + 0.2) — 2х + 1 dx 4 17 ‘ 0.236093 2.296253

— = х sec2(xy + 0.2) йу ‘ 2.06016

tg(xy + 0.2) х =- х й ху sec2 (ху + 0.2) — tg(xy + 0.2) йх х2 0.206455 2.266615

— = sec2(xy + 0.2) йУ 2.06016

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

Таблица 4 — Нормы производных для ф в нулевом приближении (1;0.6)

Вид записи Производная (1;0.6) Норма

1 — 0.6х2 й 1.2х йх у 2 3.11111

у = у й 0.6х2 — 1 йу у2 1.11111

у = ±71 — 0.6х2 й 0.6х йх ± —1 — 0.6х2 0.948683 0.948683

у = у + 0.6х2 + у2 — 1 — = 1.2х йх 1.2 3.4

Условие сходимости итерационного процесса выполняется только во втором случае. Алгоритм метода Ньютона [3].

Для численного решения методом Ньютона необходимо преобразовать систему (3) к виду (1). Таким образом, система (3) примет вид:

Алгоритм будет следующим:

1. Задать начальное приближение X(0) и малое положительное число е (точность). Положить k = 0.

2. Решить систему линейных алгебраических уравнений относительно поправки Ax(k): W(x

3. Вычислить X(k+1) по формуле: x(k+1) = x(k) + Дх(к).

4. Если A(k+1)= max |x(k+1) — x(k)| е, то положить k = k + 1 и перейти к пункту 2.

Алгоритм метода секущих [4].

1. Задать начальное приближение x(0) и малое положительное число е (точность).

2. Положить k = 0 и A0 = W(x(0)), где W(x) — матрица Якоби.

3. Решить систему линейных алгебраических уравнений AkSk == —F(x(k)) относительно Sk — поправки к текущему приближению.

4. Вычислить x(k+1) по формуле: x(k+1) = x(k) + sk.

5. Если ||skn е, то вычислить: yk = F(x(k+1)) —

F(x(k)), Ak+1 = Ak + (yk AkSk) Sk, положить k = k + 1 и перейти к пункту 3. sksk

Результаты численного решения системы нелинейных уравнений (3) по рассмотренным выше алгоритмам приведены в таблицах 5-6.

Таблица 5 — Расчетная таблица для нулевого приближения (0.2;-0.9)

k Метод простых итераций Метод Ньютона Метод секущих

0 x=0.2 е x=0.2 е x=0.2 е

1 0,1778 0,088 0,16981 0,096 0,16981 0,096

-0,98793 -0,99625 -0,99625

2 0,17046 0,007 0,17196 0,005 0,17012 0,018

-0,99047 -0,9911 -0,97831

3 0,1726 0,002 0,17197 0 0,17165 0,013

-0,99125 -0,99109 -0,9918

4 0,17172 0,001 0,17173 0,002

Из таблицы 5 видно, что все методы для начального приближения (0.2;-0.9) дали результаты, близкие к точному решению. Однако количество итераций методов различно.

Таблица 6 — Расчетная таблица для нулевого приближения (1;0.6)

k Метод простых итераций Метод Ньютона Метод секущих

0 x=1 е x=1 е x=1 е

1 — — 1,03481 0,035 1,03481 0,035

2 — — 1,03421 0,001 1,03355 0,001

3 — — 1,03424 0,001

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

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

Конфликт интересов Conflict of Interest

Не указан. None declared.

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

1. Бахвалов Н.С Численные методы. / Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков — Москва. Лаборатория Базовых Знаний. 2002. — С. 324-330.

2. Ортега Д. Итерационные методы решения систем уравнений со многими неизвестными / Д. Ортега, В. Рейнболдт — Москва. Мир. 1975. — С. 180-232.

3. Нестеров Ю.Е. Эффективные методы в нелинейном программировании / Ю.Е. Нестеров — Москва, Радио и связь. — 1989. — 304 с.

4. Дубровский В.В. Дискретность спектра задачи Неймана / В.В. Дубровский, О.А. Торшина // Вестник Магнитогорского государственного университета. — 2004. — № 5. — С. 130-131.

5. Дубровский В.В. Об одной лемме спектральной теории оператора Штурма — Лиувилля / В.В. Дубровский, О.А. Торшина // Проблемы науки и образования в современной высшей школе Тезисы докладов XXXVIII внутривузовской научной конференции преподавателей МаГУ. — 2000. — С. 42-43.

6. Кадченко С.И. Вычисление собственных чисел эллиптических дифференциальных операторов с помощью теории регуляризованных рядов / С.И. Кадченко, О.А. Торшина // Вестник Южно-Уральского государственного университета. Серия: Математика. Механика. Физика. — 2016. — Т. 8. — № 2. — С. 36-43.

7. Торшина О.А. Существенный спектр задачи Неймана для оператора Лапласа / О.А. Торшина // Современные проблемы науки и образования: материалы L внутривузовской научной конференции преподавателей МаГУ. -Магнитогорск: Издательство Магнитогорский государственный университет, 2012. — С. 271.

8. Торшина О.А. Формула асимптотики собственных чисел оператора Лапласа — Бельтрами с потенциалом на проективной плоскости / О.А. Торшина // Современные методы теории функций и смежные проблемы. Материалы конференции. — 2003. — С. 258-259.

9. Торшина О.А. Формула регуляризованного следа дифференциального оператора со сложным вхождением спектрального параметра / О.А. Торшина // Вестник Тамбовского университета. Серия: Естественные и технические науки. — 2003. — Т. 8. — № 3. — С. 467-468.

10. Торшина О.А. К вопросу сложения четных сферических гармоник / О.А. Торшина // Вестник Магнитогорского государственного университета. — 2004. — № 6. — С. 73-77.

Список литературы на английском языке / References in English

1. Bakhvalov N.S. Chislennyye metody [Numerical Methods] / N.S. Bakhvalov, N.P. Zhidkov, G.M. Kobelkov -Moscow. Laboratory of Basic Knowledge. 2002. — P. 324-330. [In Russian]

2. Ortega D. Iteratsionnyye metody resheniya sistem uravneniy so mnogimi neizvestnymi [Iterative Methods for Solving Systems of Equations with Many Unknowns] / D. Ortega, V. Reinboldt — Moscow. World. 1975. — P. 180-232. [In Russian]