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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

эйлер уравнение дифференциальный интерполирование

Цель данной курсовой работы - изучение методов приближённого интегрирования. Для некоторых подынтегральных функций интеграл можно вычислить аналитически или найти в справочниках. Однако в общем случае первообразная может быть не определена: либо первообразные не выражаются через элементарные функции, либо сами подынтегральные функции не являются элементарными. Это приводит к необходимости разработки приближенных методов вычисления определенных интегралов. Наиболее общеупотребительными приближенными методами вычисления одномерных определенных интегралов являются, так называемые, "классические" методы численного интегрирования: метод прямоугольников, метод трапеций, метод парабол (основанные на суммировании элементарных площадей, на которые разбивается вся площадь под функцией). Хотя эти методы обычно предпочтительней в случае малых размерностей, они практически не годятся для вычисления многомерных интегралов, для их вычисления используются другие методы. В связи с развитием новой вычислительной техники инженерная практика наших дней все чаще и чаще встречается с математическими задачами, точное решение которых получить весьма сложно или невозможно. В этих случаях обычно прибегают к тем или иным приближенным вычислениям. Вот почему приближенные и численные методы математического анализа получили за последние годы широкое развитие и приобрели исключительно важное значение.



1. Решение нелинейных уравнений. Метод касательных (Ньютона)

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

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

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

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

Графическая интерпретация метода показана на рис.1.

Рисунок 1. Графическая интерпретация метода половинного деления



В этом методе отыскание корня уравнения f(x) = 0 проходит в два этапа. На первом этапе необходимо отделить корень, т.е.выделить интервал на оси абсцисс, на котором функция f(x) меняет свой знак. Для отделения корня следует провести вычисление функции f(x) в точках, расположенных через равные интервалы по оси x, до тех пор, пока не будут найдены два последовательных значения функции f(x_n) и f(x_n+1), имеющие противоположные знаки.

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

Метод касательных называется также методом Ньютона. Будем считать, что функция F(x) непрерывна на отрезке [а;b] и имеет место на концах отрезка разные знаки, т.е. F(a)F(b)<0.

В качестве начального приближения x₀ в методе касательных выбирается тот конец отрезка [a;b], в котором функция F(x) и ее вторая производная F¹¹(x) имеет одинаковые значения, т.е.

F(a)F¹¹(a)>0 или F(b)F¹¹>0.

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

Примем за начальное приближение х₀ конец отрезка b, т.е. x₀=b и проведем касательную к графику функции в точке B₀(x₀;F(x₀)).

Русунок 2



Уравнение касательной будет иметь вид:

Касательная пересечет ось Ox при y=0. Подставив y=0 в уравнение, получим абсциссу точки пересечения

X₁=x₀

Записав уравнение касательной к графику в точке B₁(x₁; F(x₁)), при y=0, получим

X₂=x₁ -

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

X_{n+1 =}x_n, (n=0,1,2,….), (1.1)

Причем всегда

a<ж? х_n+1<x_n?b,



где ж - точный корень уравнения F(x)=0.

Решение:



2. Интерполирование функции. Полиномы Ньютона

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

Пусть l_n(x) - интерполяционный многочлен Лагранжа с равноотстоящими узлами. Представим в виде:

l_n(x) = l₀(x) + (l₁(x) - l₀(x)) + (l₂(x) - l₁(x)) +…+ (l_n(x) - l_n-1(x)). (2.1)

Разности l_k(x) - l_k-1(x) есть многочлены k-ой степени, обращающиеся в ноль в точках x₀, x₁,…,x_k-1, поскольку l_k(x_j) - l_k-1(x_j) при j = 0,1,…, k-1. Следовательно,

l_k(x_j) - l_k-1(x_j) = a_k(x - x₀) (x - x₁)… (x - x _{k -1}). (2.2)

Подставляя эти выражения в первую формулу (для k =1,…, k-1) находим:

l_n(x) = a₀ + a₁(x - x₀) + a₂(x - x₀) (x - x₁) +…+ a_n(x - x₀) (x - x₁)… (x - x _{n -1}). (2.3)

Коэффициенты a₀, a₁,…,a_n определяются из условий: l_n(x_j) = f(x_j) при j = 0,1,…, k-1,

l_k(x_j) - l_k-1(x_j) = a_k(x - x₀) (x - x₁)… (x - x _{k -1}). (2.4)



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

x _k = x₀+ kh, l_k(x_k) = f(x_k). Отсюда .

Покажем, что f(x_k) - l_k-1(x_k) есть k - я разность в точке x₀, т.е. она равна ?^kf(x₀).

Методом математической индукции можно доказать, что

?^kf(x₀) = f(x_k) - С_k¹ f(x_{k - 1}) + С_k² f(x_{k - 2}) +…+ (-1)ⁱС_kⁱ f(x_{k - i}) +…+ (-1)^k f(x₀). (2.5)

Вычислим разность f(x_k) - l_k-1(x_k). Имеет место равенство

f(x_k) - l_k-1(x_k) =, где

(2.6)

Таким образом,

(2.7)

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

f(x_k) - l_k-1(x_k) = f(x_k)-= ?^kf(x₀). (2.8)

Поэтому .

(2.9)

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

Линейный интерполянт по Ньютону имеет вид

(2.10)

Вводя обозначение , получим

(2.11)

При вычислении разностей удобно пользоваться таблицей.

Таблица 1

xi	f(xi)	xi+1- xi	d1 f(xi)	xi+2- xi	d2 f(xi)	…	xn- x0	dn f(xi)
x0 x1 xn- 1 xn	f(x0) f(x1) f(xn- 1) f(xn)	x1-x0 x2-x1 … xn - xn- 1	d1f(x0) d1f(x1) … d1f(xn- 1)	x2-x0 x3-x1 …	d2f(x0) d2f(x1) …	… …	xn- x0	dnf(x0)

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

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

(2.12)



где коэффициенты

(2.13)

(2.14)

(2.15)

- разделенные разности.

Алгоритм интерполяции функции многочленом Ньютона (произвольные узлы).

Ввод: Узлы интерполяции X[i], Y[i]' i = 0,1,…, n.

Вывод: Вычислить c:= f(х).

d:= 1; с:= X[0];p:=1;

Цикл по j:= 1… n выполнить

с:= Y[0];

Цикл по i:= 0… n-j выполнить Y[i]:= (Y[i+1]- Y[i])/ (X[i+j]- X[i]); конец цикла по i;

p:= p*(x- X[j-1]); c:= c+p*Y[j])

конец цикла по j;

конец.

Алгоритм интерполяции функции многочленом Ньютона (равноотстоящие узлы).

Ввод: Узлы интерполяции X[i], Y[i]' i = 0,1,…, n.

Вывод: Вычислить c:= f(х).

h:= X[1]- X[0]; с:= X[0];p:=1;

Цикл по j:= 1… n выполнить

с:= Y[0];

Цикл по i:= 0 … n-j выполнить Y[i]:= (Y[i+1]- Y[i]); / (X[i]- X[i-1]); X[i]:= X[i]- X[i-1]); конец цикла по i;

p:= p*(x- X[j-1])/(j*h); c:= c+p*Y[i]);

конец цикла по j;

конец.

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

Решение:



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

Численное интегрирование -- вычисление значения определённого интеграла (как правило, приближённое). Под численным интегрированием понимают набор численных методов для нахождения значения определённого интеграла.

Численное интегрирование применяется, когда:

1. Сама подынтегральная функция не задана аналитически. Например, она представлена в виде таблицы (массива) значений в узлах некоторой расчётной сетки.

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

(3.1)

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

3.1 Метод прямоугольников

Пусть требуется определить значение интеграла функции на [a,b] отрезке. Этот отрезок делится точками x₀, x₁, …., x_n-1, x_n на n равных отрезков длиной . Обозначим через y₀, y₁, …., y_n-1, y_n значение функции f(x) в точках x₀, x₁, …., x_n-1, x_n

Далее составляем суммы . Каждая из сумм -- интегральная сумма для f(x) на [a,b] и поэтому приближённо выражает интеграл.

Если заданная функция -- положительная и возрастающая, то эта формула выражает площадь ступенчатой фигуры, составленной из «входящих» прямоугольников, также называемая формулой левых прямоугольников, а формула

(3.2)

выражает площадь ступенчатой фигуры, состоящей из «выходящих» прямоугольников, также называемая формулой правых прямоугольников. Чем меньше длина отрезков, на которые делится отрезок [a,b], тем точнее значение, вычисляемое по этой формуле, искомого интеграла.

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

(3.3)

где

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



3.2 Метод трапеций

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

Площадь трапеции на каждом отрезке:

(3.4)

Погрешность аппроксимации на каждом отрезке:

(3.5)

где и

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

(3.6)

где

Погрешность формулы трапеций:

(3.7)

где и



3.3 Метод парабол

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

(3.8)

Если разбить интервал интегрирования на 2N равных частей, то имеем

(3.9)

где .

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

Задача на вычисление определенного интеграла по формуле Симпсона - самая популярное задание на практике.

Пусть функция y = f(x) непрерывна на отрезке [a; b] и нам требуется вычислить определенный интеграл.

Формула Симпсона для приближенного вычисления определенного интеграла имеет следующий вид: (24)



где: - длина каждого из маленьких отрезков или шаг;

f(x_i) - значения подынтегральной функции в точках x₀,x₁,x₂,x₃,…,x_2n-2,x_2n-1,x_2n.

Детализируя это нагромождение, разберу формулу подробнее:

- сумма первого и последнего значения подынтегральной функции;

- сумма членов, с чётными индексами умножаемая на 2.

- сумма членов с нечётными индексами умножается на 4.

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

Рисунок 2 - График подынтегральной функции приближенный к самой функции.

Решение:

Метод левых прямоугольников

Метод правых прямоугольников



Метод трапеции

Метод Симпсона



4. Приближенное решение обыкновенных дифференциальных уравнений первого порядка. Задача Коши

Многие задачи науки и техники сводятся к решению обыкновенных дифференциальных уравнений (ОДУ). ОДУ называются такие уравнения, которые содержат одну или несколько производных от искомой функции. В общем виде ОДУ можно записать следующим образом: , где x - независимая переменная, yⁱ - i-ая производная от искомой функции. n - порядок уравнения. Общее решение ОДУ n-го порядка содержит n произвольных постоянных c₁,.., c_n,т.е. общее решение имеет вид y=ц(x, c₁, …, c_n).

Для выделения единственного решения необходимо задать n дополнительных условий. В зависимости от способа задания дополнительных условий существуют два различных типа задач: задача Коши и краевая задача. Если дополнительные условия задаются в одной точке, то такая задача называется задачей Коши. Дополнительные условия в задаче Коши называются начальными условиями. Если же дополнительные условия задаются в более чем одной точке, т.е. при различных значениях независимой переменной, то такая задача называется краевой. Сами дополнительные условия называются краевыми или граничными.

Ясно, что при n=1 можно говорить только о задачи Коши.

Примеры постановки задачи Коши:

(4.1)

(4.2)



Примеры краевых задач:

(4.3)

(4.4)

Решить такие задачи аналитически удается лишь для некоторых специальных типов уравнений.

4.1 Численные методы решения задачи Коши для ОДУ первого порядка

Постановка задачи. Найти решение ОДУ первого порядка на отрезке [x₀, x_n] при условии y(x₀)=y₀.

При нахождении приближенного решения будем считать, что вычисления проводятся с расчетным шагом , расчетными узлами служат точки xi=x0+ih, (i=0,1,…,n) промежутка [x₀, x_n].

Целью является построение таблицы.

Таблица 2

xi	x0	x1	…	xn
yi	y0	y1	…	yn

Т.е. ищутся приближенные значения y в узлах сетки.

Интегрируя уравнение на отрезке [x_i,x_i+1]получим

(4.5)

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

(4.6)

то получим явную формулу Эйлера:

(4.7)

Порядок расчетов:

Зная , находим , затем т.д..

4.2 Геометрическая интерпретация метода Эйлера

Пользуясь тем, что в точке x₀ известно решение y(x₀) = y₀ и значение его производной , можно записать уравнение касательной к графику искомой функции y=y(x)Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

в точке (x₀,y₀):

При достаточно малом шаге h ордината , этой касательной, полученная подстановкой в правую часть значения , должна мало отличаться от ординаты y(x₁) решения y(x) задачи Коши. Следовательно, точка (x1,y1) пересечения касательной с прямой x = x₁ может быть приближенно принята за новую начальную точку. Через эту точку снова проведем прямую , которая приближенно отражает поведение касательной к y=y(x) в точке (x1, y(x1)). Подставляя сюда x2=x1+h (т.е. пересечение с прямой x = x₂), получим приближенное значение y(x) в точке x₂: , и т.д. В итоге для i-й точки получим формулу Эйлера.



Рисунок 7. Метод Эйлера

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

то придем к методу

(4.8)

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

Неявный метод Эйлера имеет первый порядок точности или аппроксимации.

Модифицированный метод Эйлера: в данном методе вычисление y_i+1 состоит из двух этапов:

(4.9)

(4.10)

Данная схема называется еще методом предиктор - корректор (предсказывающее - исправляющее). На первом этапе приближенное значение предсказывается с невысокой точностью (h), а на втором этапе это предсказание исправляется, так что результирующее значение имеет второй порядок точности.

Решение

Метод Эйлера





Заключение

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



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

1) Бахвалов Н.С. Численные методы - М.: Наука, 2006. - 632 с.

2) Березин Н.С., Жидков Н.П. Методы вычислений. - Т.1. - М.: Наука, 2008. - 464 с.

1) Васильев Ф.П. Численные методы решения экстремальных задач: Учебное пособие для вузов - 2-е изд., перераб. и доп. -М.: Наука, Гл. ред. физ.-мат. лит, 2005. -550 с.

2) Демидович Б.Н., Марон И.А. Основы вычислительной математики. -М.: Наука, 2012.- 664 с.

3) Самарский А.А. Введение в численные методы. - 3-е изд., перераб. - М.: Наука, 2011. - 239 с.

Размещено на Allbest.ru