Рефотека.ру / Математика

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

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

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

Кафедра САПР


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

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

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


Караганда 2009

Содержание


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

Метод хорд

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

Практическое применение метода хорд для решения уравнений

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

Программная реализация итерационных методов

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

2.1 Многочлен Лагранжа и обратное интерполирование

2.2 Практическое применение метода интерполяции

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

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

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

3.3 Практическое применение метода простых итераций при решении СЛАУ

3.4 Практическое применение метода Зейделя при решении СЛАУ

3.5 Программная реализация итерационных методов решения СЛАУ

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

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

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

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

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

5.2 Модификация метода Эйлера

5.3 Практическое применение метода Эйлера

5.4 Практическое применение уточненного метода Эйлера


Раздел 1. Решения нелинейных уравнений


Задача нахождения корней нелинейных уравнений вида F(x)=0 , где F(x)-непрерывная функция,- встречается в различных областях научных исследований. Методы решения нелинейных уравнений делятся на :

прямые;

итерационные.

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

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

Алгоритм нахождения корня нелинейного уравнения с помощью итерационного метода состоит из двух этапов:

а) отыскания приближенного значения корня (начального приближения);

б) уточнения приближенного значения до некоторой заданной степени точности.

В некоторых методах отыскивается не начальное приближение, а некоторый отрезок, содержащий корень, например:(метод хорд, метод касательных). Начальное приближение может быть найдено различными способами, например - графическим методом. Если оценку исходного приближения провести не удается, то находят две близко расположенные точки a и b , в которых непрерывная функция F(x) принимает значения разных знаков, т. е. F(a)>0 F(b)<0 . При выполнении этого условия, можно говорить, что между точками a и b есть, по крайней мере, одна точка, в которой F(x)=0 .

Итерационный процесс состоит в последовательном уточнении начального приближения х0 . Каждый такой шаг называется итерацией. В результате итераций находится последовательность приближенных значений корня х1 ,х2 , х3, … , хn ,… Если эти значения с ростом n стремятся к истинному значению корня

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


1.1 Метод хорд


Пусть мы нашли отрезок [a ,b] , на котором функция F(x) меняет знак. Для определенности примем F(a) >0 , F(b)<0 . В данном методе процесс итераций состоит в том , что в качестве приближений корню уравнения принимаются значения х0, х1,… точек пересечения хорды с осью абсцисс.

Сначала найдем уравнение хорды АВ:


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


Для точки пересечения ее с осью абсцисс ( y=0, ) получим уравнение


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


Далее, сравнивая знаки величин F(a) и F(x) для рассматриваемого случая, приходим к выводу, что корень находится в интервале (a, x) , так как F(a)*F(x)<0 (условие существование корня). Отрезок [x , b] отбрасываем и больше не рассматриваем. Следующая итерация состоит в определении нового приближения xn как точки пересечения хорды АВ1 с осью абсцисс и так далее.

На рисунке 1 изображена геометрическая интерпретация нахождение решения методом хорд.


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

Рисунок 1. Метод хорд


При решении уравнения методом хорд поводится прямая соединяющая концы отрезка [a,b]. Из двух точек А и В выбирается х0. Находится точка пересечения хорды с осью OX. Определяется значение функции в точке пересечения и из найденной точки проводится новая хорда. Этот процесс повторяется до получения необходимой точности.

Формула для n-го приближения имеет вид(х0=а , xn-1=b,xn=x):


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


В методе хорд условием окончания итераций является:

- условие близости двух последовательных приближений : Сравнительный анализ численных методов;

- условие малости невязки Сравнительный анализ численных методов(величина F(xn) есть невязка, полученная на n-й итерации, а Сравнительный анализ численных методов-число , с заданной точностью которого необходимо найти решение).


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


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


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

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


Уравнение касательной, проведенной к кривой y =F(x) в некоторой точке с координатами х0 и F(х 0) имеет вид


y-F(х0)=F’(х0)(x-х0).


Отсюда найдем следующее приближение корня х как абсциссу точки пересечения касательной с осью х (у=0):


х=х0 - F(х0) /F’(х0).


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


хn=хn-1 - F(хn-1) /F’(хn-1), n=1,2,…

При этом необходимо , чтобы выполнялось условие F’(хn-1)Сравнительный анализ численных методов0.

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


1.3 Практическое применение метода хорд для решения уравнений


Возьмем для исследования функцию Сравнительный анализ численных методов и определим точность решения какСравнительный анализ численных методов=0,001.


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

Рисунок 3. График функции Сравнительный анализ численных методов (в разных пределах)


Визуально определяем границы отрезка, на котором находится корень. Выделяем отрезок [a,b], (а=-0,1, b=0.35).

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

Проверяем существование корня на отрезке по условию Сравнительный анализ численных методов


f(-0.1)=-1.571

f(0.35)=1.51037

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

-2,37280.4954<0


Условие выполнено, следовательно на данном промежутке корень есть.

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


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

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

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

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

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


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

Проверяем функцию на единственность корня на отрезке.


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

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

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

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

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

43.74>0


На данном промежутке имеется только один корень.

4. Выбор точки х0 зависит от того совпадает ли её знак со знаком второй производной данной функции.


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


Точка а условию не удовлетворяет.


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

Из условия следует , что х0=b=0.35, тогда за х1 принимаем a = х1=-0.1

6. Формула для решения


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


При решении мы получили следующие результаты:


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

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

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

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


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

Добиться указанной точности нам удалось на 5-ой проведенной итерации.


1.4 Практическое применение метода касательных для решения уравнений


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

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

Сравнительный анализ численных методов=0,001.


Начальное условие:

Сравнительный анализ численных методов(выбрали по тому же правилу, которое использовали для решения уравнения методом хорд Сравнительный анализ численных методов)

Применим формулу


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

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

Сравнительный анализ численных методов ;

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

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

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

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

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


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

Добиться указанной точности нам удалось на 3-й проведенной итерации

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

Рисунок 4. График функции на отрезке [Сравнительный анализ численных методов; Сравнительный анализ численных методов]


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


[Сравнительный анализ численных методов; Сравнительный анализ численных методов].


Значения исходной функции на концах этого отрезка


f(Сравнительный анализ численных методов)=-0,0001391

f(Сравнительный анализ численных методов)=0,000000033


Как мы видим, на каждой итерации объем вычислений в методе касательных больший, чем в методе хорд, так как приходится находить не только функции F(х) , но и ее производной. Однако скорость сходимости значительно выше в методе касательных: в методе касательных условие сходимости выполнилось на 3- м шаге, а в методе хорд на 5-м.

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


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


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


Рисунок 6. График функции Сравнительный анализ численных методов для метода хорд


Говоря о функции х=Сравнительный анализ численных методов, - выбрав начальное приближение х0 (для метода касательных), х0 и x1(для метода хорд) строится последовательность хn стремящаяся к Сравнительный анализ численных методов и условием сходимости здесь является Сравнительный анализ численных методов,т.е. тангенс угла наклона касательной должен быть меньше 1(угол должен составлять менее 45 градусов). Исходя из рисунков 5,6 очевидно что условие сходимости (Сравнительный анализ численных методов) итерационной процедуры было выполнено.


1.5 Программная реализация итерационных методов


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

Рисунок 7. Решение уравнения методом хорд


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

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

Раздел 2. Интерполирование


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


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


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


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

Рисунок 9. Интерполяция.


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


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


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

Будем искать интерполяционный многочлен в виде линейной комбинации многочленов степени n:


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


При этом потребуем, чтобы каждый многочлен Сравнительный анализ численных методов обращался в нуль во всех узлах интерполяции, за исключением одного (i-го), где он должен равняться единице. Этим условиям при i=0 отвечает многочлен вида


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


По аналогии получим

при i=1


Сравнительный анализ численных методов,


при i=2


Сравнительный анализ численных методов,

Сравнительный анализ численных методов,

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

Подставляя полученные выражения в


Сравнительный анализ численных методов,


находим


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


Эта формула определяет интерполяционный многочлен Лагранжа.

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

Функция выглядит следующим образом:


Ln(y)=Сравнительный анализ численных методов


2.2 Практическое применение метода интерполяции для решения уравнений


Для исследования примем ту же функцию , что и в предыдущем разделе:


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

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

Рисунок 10. График функции Сравнительный анализ численных методов


В пункте 1.2 для этой функции был выбран отрезок [3,4] и проверен на единственность корня.

Примем


х0=-0.1

х1=0.0125

х2=0.125

х3=0.237

х4=0.35.


Тогда многочлен Лагранжа будет иметь вид:


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


Вычислим значения функции (многочлена Лагранжа) в узлах интерполяции и исходной функции в тех же точках.


Сравнительный анализ численных методов=-1.571

Сравнительный анализ численных методов=-1.571

Сравнительный анализ численных методов=-0.9245293

Сравнительный анализ численных методов=-0.9245293

Сравнительный анализ численных методов=-0.2011719

Сравнительный анализ численных методов=-0.2011719

Сравнительный анализ численных методов=-0.6076152

Сравнительный анализ численных методов=-0.6076152

Сравнительный анализ численных методов=1.510375

Сравнительный анализ численных методов=1.510375


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

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

Для сравнения выберем точки: середина крайней части отрезка х=0.29375 и середина части, содержащей точку (a+b)/2 - х=0.18125.


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

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

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

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


Результаты для точки находящейся в середине отрезка начинают различаться на 13 знаке после запятой; для крайней точки - на 14-ом знаке. Следовательно, точность данного метода достаточно велика.


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

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


Используя эти же узловые точки проведем обратную интерполяцию и определим значение х при у=0.

Y=0


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

L4(0)=0,1541658


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

Решение найденное методом хорд: х=Сравнительный анализ численных методов

Решение найденное методом касательных: х=Сравнительный анализ численных методов

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


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

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

Применение итерационных методов для качественного решения СЛАУ требует серьёзного использования её структуры, специальных знаний и определённого опыта. Именно поэтому разработано большое число итерационных средств, каждый из которых ориентирован на решения сравнительно узкого числа задач, и существует довольно мало программ, реализующих эти методы. В курсе математического обеспечения САПР мы рассмаривали следующие итерационные методы решения СЛАУ: метод простой итерации, метод Зейделя.

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


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

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


x=Bx+c,


где В- квадратная матрица с элементами bij (I,j=1,2,3…m) c- вектор-столбец с элементами ci (i=1,2,3…m)

В развёрнутой форме записи система имеет вид:


x1=b11x1+b12x2+b13x3+…b1mxm+c1

x2=b21x1+b22x2+b23x3+…b2mxm+c1

x3=b31x1+b32x2+b33x3+…b1mxm+c3

xm=bm1x1+bm2x2+bm3x3+…bmmxm+cm


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

Самым простым способом приведения системы к такому виду является тот, что описан ниже:

И первого уравнения системы выразим x1:


x1=a11-1(b1-a12x2- a13x3-…- a1mxm)

Из второго уравнения системы выразим x2:


x2=a22-1(b2-a21x2- a23x3-…- a2mxm)

xm=amm-1(bm-am1x2- am3x3-…- am-1mxm-1)


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


x1=0+ b12x2+ b13x3-…+ b1m-1xm-1+ b1mxm+c1

x2= b21x2+0 +b23x3+…+ b2m-1xm-1+ b2mxm+c2

xm= bm1x1+ bm2x20 +bm3x3+…+ bmm-1xm-1+ 0+cm


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


bij=-aij/aii ci=bi/aii (i,j=1,2,3…m, i<>j)


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

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

Часто систему преобразуют к виду x=x-Сравнительный анализ численных методов(Ax-b), где Сравнительный анализ численных методов-специально выбираемый числовой параметр.

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

Выберем начальное приближение x0=( x01 x02… x0m)

подставляя его в праву часть системы


x=Bx+c,


и вычисляя полученное выражение, находим первое приближение:

x1=Bx0+c


на втором шаге подставляем приближение x1 в правую часть той же системы, получим второе приближение:


x2=Bx1+c


Продолжая этот процесс далее, получим последовательность x1 x2 x3… xn приближений, вычисляемых по формуле :


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


Эта формула и выражает собой метод простой итерации.

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

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


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


Метод Зейделя можно использовать как модификацию метода простых итераций. Основная идея модификации состоит в том, что при вычислении очередного (k+1)-го приближения к известному xi при i>1 используют используются уже найденные приближения к известным x1,… xi-1, а не k-е приближение как в методе простых итераций.

На (k+1)-й итерации компоненты приближения Сравнительный анализ численных методов вычисляются по формулам:

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

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

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


Условие сходимости метода Зейделя заключается в том, что матрица A системы Ax=b, должна удовлетворять условию:

модуль диагонального элемента должен быть больше суммы модулей оставшихся элементов строки или столбца.

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


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


3.3 Практическое применение метода простых итераций для решения системы уравнений


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


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


Выполним проверку на условие сходимости:

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

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


Условие выполнено, можно приступать к вычислению нулевого шага:


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

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

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

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


Начнем итерационный процесс, используя результаты начального приближения:


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

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

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

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

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


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


Условие остановки на первом шаге итерации не было выполнено, поэтому продолжаем итерацию, вычисляя x(2) :


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

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

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

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


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


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


Условие остановки на втором шаге итерации не было выполнено, поэтому продолжаем итерацию, вычисляя x(3) :

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

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

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

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


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


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


Условие остановки на третьем шаге итерации было выполнено лишь для x4, поэтому продолжаем итерацию, вычисляя x(4) :


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

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

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

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


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


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

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


Сходимость в сотых долях имеет место уже на 4-ом шаге, тогда можно принять


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


3.4 Практическое применение метода Зейделя для решения системы уравнений


Решим ту же систему линейных уравнений методом Зейделя с той же точностью : Сравнительный анализ численных методов.


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


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


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

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

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

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

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

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

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

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

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


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


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

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


Условие остановки на первом шаге итерации не было выполнено, поэтому продолжаем итерацию, вычисляя x(2) :


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

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


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

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


Условие остановки на втором шаге итерации было выполнено лишь для x3, x4, поэтому продолжаем итерацию, вычисляя x(3) :


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


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


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

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


Условие сходимости выполнено на 3-ем шаге .

Корнями уравнения можно принять:

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


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

Ниже приведена сравнительная таблица1, позволяющая сравнить результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации:


Таблица1. Сводная таблица значений элементов приближений двух методов итерации

№ шага Метод постой итерации Метод Зейделя
0

X1=1.04

X2=1.3

X3=1.45

X4=1.55

X1=1.04

X2=1.3

X3=1.45

X4=1.55

1

X1=0.75

X2=0.95

X3=1.14

X4=1.36

X1=0.75

X2=0.9674

X3=1.1976

X4=1.40402

2

X1=1.8106

X2=1.0117

X3=1.2117

X4=1.4077

X1=0.8019

X2=0.99956

X3=1.19956

X4=1.39999

3

X1=0.7978

X2=0.9977

X3=1.1975

X4=1.3983

X1=0.80006

X2=0.00002

X3=1.19999

X4=1.39997

4

X1=0.80046

X2=0.000502

X3=1.20052

X4=1.40034



3.5 Программная реализация итерационных методов


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

Рисунок 12. Решение системы уравнений методом простых итераций


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

Рисунок 13. Решение уравнения методом Зейделя


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


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


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

Предположим, что в окрестности точки xi функция F(x)дифференцируема достаточное число раз. Исходя из определения производной:


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


используем для её вычисления две приближенные формулы:


Сравнительный анализ численных методов (1)

Сравнительный анализ численных методов(2)


Формулы (1) и (2) называют правыми и левыми разностными производными.

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


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

откуда можно вычислить:


Сравнительный анализ численных методов (3)


Выражение (3) имеет погрешность порядка (x-xi), следовательно, формулы правых и левых разностных производных имеют погрешность одного порядка с h , где


h=xi-xi-1


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


Сравнительный анализ численных методов (4)


Хотя очевидно, что формула (4) используется для внутренних точек отрезка.

Для примера возьмём ряд точек:


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


Вычислим производную функции f(x)=sin(x) в одной из них двумя способами.

Очевидно, что h=Сравнительный анализ численных методов

По центрально-симметричной формуле:

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


По формуле левой разностной производной:


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


Табличное значение Сравнительный анализ численных методов=cos(Сравнительный анализ численных методов)=0.8660 ,т.е. значение производной, полученное по центрально-симметричной формуле ближе к истинному.


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


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


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


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


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

Суть приближенного вычисления заключается в двух операциях:

1. в выборе конечного числа вместо n

2. в выборе точки Сравнительный анализ численных методов в соответствующем отрезке.

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

Формулы левых и правых прямоугольников (5),(6)


Сравнительный анализ численных методов (5)

Сравнительный анализ численных методов (6)


Формула трапеции:


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


Формула Симпсона


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


где


m=n/2

h=b-a/n


b, a- концы рассматриваемого отрезка.

Для сравнения результатов вычисления вышеизложенными формулами численного интегрирования вычислим 3-мя способами следующий интеграл, разделив отрезок [0, Сравнительный анализ численных методов] на 6 равных отрезков:

Сравнительный анализ численных методов h=Сравнительный анализ численных методов


По формуле левых прямоугольников:


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


По формуле трапеции:


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


По формуле Симпсона:


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

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


Сравнительный анализ численных методов=1


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


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


Инженеру часто приходится иметь дело с техническими системами и технологическими процессами, характеристики которых непрерывным образом меняются во времени. Соответствующие явления как правило подчиняются физическим законам, которые формулируются в виде дифференциальных уравнений. Одной из основных математических задач, которые приходится решать для таких уравнений, является задача Коши (начальная задача). Чаще всего к ней приходят тогда, когда известно начальное состояние физической величины системы в некоторый момент времени t0 (x0,y0) и требуется предсказать её поведение в момент времени t>t0 ( x>x0). В курсе математического обеспечения САПР, мы рассматривали методы решения задачи Коши с помощью решения обыкновенного дифференциального уравнения первого порядка Сравнительный анализ численных методов.

Напомним, что решением обыкновенного дифференциального уравнения (ОДУ) первого порядка является функция y , которая при подстановке в уравнение Сравнительный анализ численных методов, превращает его в тождество.

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


Сравнительный анализ численных методов,


где х – независимая переменная.

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

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

Графические методы используют геометрические построения.

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

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

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


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


Простейшим численным методом решения задачи Коши для ОДУ является метод Эйлера. Рассмотрим уравнение Сравнительный анализ численных методов в окрестностях узлов Сравнительный анализ численных методов (i=1,2,3,…) и заменим в левой части производную Сравнительный анализ численных методов правой разностью. При этом значения функции Сравнительный анализ численных методов узлах Сравнительный анализ численных методов заменим значениями сеточной функции Сравнительный анализ численных методов:


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

Полученная аппроксимация ДУ имеет первый порядок, поскольку при замене


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


на


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


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

Будем считать для простоты узлы равноотстоящими, т.е.


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


Тогда из равенства


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


получаем


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


Заметим, что из уравнения


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


следует

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


Поэтому


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


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

Полагая i=0, с помощью соотношения


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


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


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


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

Аналогично могут быть найдены значения сеточной функции в других узлах:


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


Построенный алгоритм называется методом Эйлера.

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

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

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


На рисунке 14. изображены первые два шага, т.е. проиллюстрировано вычисление сеточной функции в точках Сравнительный анализ численных методов. Интегральные кривые 0,1,2 описывают точные решения уравнения Сравнительный анализ численных методов. При этом кривая 0 соответствует точному решению задачи Коши, так как она проходит через начальную точку А(x0,y0). Точки B,C получены в результате численного решения задачи Коши методом Эйлера. Их отклонения от кривой 0 характеризуют погрешность метода. При выполнении каждого шага мы фактически попадаем на другую интегральную кривую. Отрезок АВ – отрезок касательной к кривой 0 в точке А , ее наклон характеризуется значением производнойСравнительный анализ численных методов. Погрешность появляется потому, что приращение значения функции при переходе от х0 к х1 заменяется приращением ординаты касательной к кривой 0 в точке А. Касательная ВС уже проводится к другой интегральной кривой 1. таким образом , погрешность метода Эйлера приводит к тому, что на каждом шаге приближенное решение переходит на другую интегральную кривую.


4.2 Модификация метода Эйлера: Усовершенствованный метод Эйлера


Рассмотрим уравнение Сравнительный анализ численных методов в окрестностях узлов


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

В левой части уравнения Сравнительный анализ численных методов заменим производную центральной разностью


Сравнительный анализ численных методов,


а правую часть оставим без изменений:


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


Приближенное значение функции Сравнительный анализ численных методов в точке Сравнительный анализ численных методов вычислим с помощью метода Эйлера:


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


Выразим Сравнительный анализ численных методов из


Сравнительный анализ численных методов,


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


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


Данный метод имеет второй порядок точности.


4.3 Практическое применение метода Эйлера для ОДУ


Исходное ОДУ:


Сравнительный анализ численных методов y(0.6)=1.2, Сравнительный анализ численных методов


Таблица 1. метод Эйлера (n=5)

i xi yi f(xi,yi)
0 0.6 1.2 0.953971
1 0.8 1.3907942 1.2071579
2 1 1.6322258 1.4725082
3 1,2 1.9267274 1.7488018
4 1,4 2.2764878 2.0337464
5 1,6 2.6832371 2.3236155

Таблица 2. метод Эйлера (n=20)

i xi yi f(xi,yi)
0 0.6 1.2 0.953971
1 0.65 1.2476986 1.0173845
2 0.7 1.2985678 1.0816058
3 0.75 1.3526481 1.1466263
4 0.8 1.4099794 1.2124345
5 0.85 1.4706011 1.2790158
6 0.9 1.5345519 1.3463522
7 0,95 1.6018695 1.414422
8 1 1.6725906 1.4831991
9 1,05 1.7467506 1.5526532
10 1,1 1.8243832 1.6227488
11 1,15 1.9055207 1.6934454
12 1,2 1.9901929 1.7646967
13 1,25 2.0784278 1.8364504
14 1,3 2.1702503 1.9086477
15 1,35 2.2656827 1.981223
16 1,4 1.4490611 1.8231403
17 1,45 1.5402182 1.8978804
18 1,5 1.6351122 1.9732751
19 1,55 1.7337759 2.0492675
20 1,6 1.8362393 2.1257929

4.4 Практическое применение уточненного метода Эйлера для ОДУ


Таблица 3. уточнённый метод Эйлера (n=5)

i xi yi f(xi,yi)
0 0.6 1.2 0.953971
1 1,8 1.3961444 1.2086308
2 2 1.6388191 1.4742593
3 2,2 1.9344575 1.7507486
4 2,4 2.2851468 2.0357638
5 2,6 2.6924796 2.3255361

Таблица 4. уточнённый метод Эйлера (n=20)

i xi yi f(xi,yi)
0 0.6 1.2 0.953971
1 0.65 1.2480344 1.0174786
2 0.7 1.2989239 1.081705
3 0.75 1.3530242 1.1467304
4 0.8 1.4103753 1.2125432
5 0.85 1.4710165 1.2791289
6 0.9 1.5349863 1.3464694
7 0,95 1.6023224 1.4145429
8 1 1.6730614 1.4833234
9 1,05 1.7472384 1.5527803
10 1,1 1.8248874 1.6228784
11 1,15 1.9060401 1.6935769
12 1,2 1.9907265 1.7648295
13 1,25 2.0789741 1.8365838
14 1,3 2.1708081 1.9087811
15 1,35 2.2662503 1.9813557
16 1,4 2.3653194 2.054235
17 1,45 1.5408387 1.8980477
18 1,5 1.6357494 1.9734443
19 1,55 1.7344284 2.0494379
20 1,6 1.8369055 2.1259637

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

  1. • Сравнительный анализ численных методов
  2. • Численное интегрирование функций
  3. • Численные методы линейной алгебры
  4. • Автоматизированный анализ проектирования на ...
  5. • Спектральный анализ и его приложения к обработке сигналов в ...
  6. • К решению нелинейных вариационных задач
  7. • Экзаменационные билеты по численным методам за первый семестр ...
  8. • Методы сравнительного анализа деятельности посреднических ...
  9. • Численные методы решения типовых математических задач
  10. • Численные методы интегрирования и оптимизации ...
  11. • Методология сравнительного правоведения
  12. • Сравнительный анализ методов оптимизации
  13. • Численные методы анализа и синтеза периодических сигналов
  14. • Сравнительное правоведение: общая характеристика
  15. • Сравнительный анализ методов оптимизации
  16. • Экономика недвижимости
  17. • Численное интегрирование методом Гаусса
  18. • Численные методы решения систем линейных уравнений
  19. •  ... высокого уровня для реализации численных методов
Смотреть все похожие работы
Рефетека ру refoteka@gmail.com