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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: Курсовик. Предмет: Математика. Добавлен: 20.01.2010. Сдан: 2010. Уникальность по antiplagiat.ru: --.

Описание (план):


4. 'Стрелки' section. 'Стрелки' section. 'Стрелки' section. 'Стрелки' sectionArrow TableArrow TableArrow Table
46
Министерство образования и науки Республики Казахстан
Карагандинский государственный технический университет
Кафедра САПР
Курсовая работа
по дисциплине: Математическое обеспечение САПР
Тема: Сравнительный анализ численных методов
Караганда 2009
Содержание
Раздел 1 Решение нелинейных уравнений
1.1 Метод хорд
1.2 Метод касательных
1.3 Практическое применение метода хорд для решения уравнений
1.4 Практическое применение метода касательных для решения уравнений
1.5 Программная реализация итерационных методов
Раздел 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 Практическое применение метода простых итераций для решения системы уравнений
Решим систему линейных уравнений методом простых итераций с точностью равной .
Выполним проверку на условие сходимости:
Условие выполнено, можно приступать к вычислению нулевого шага:
Начнем итерационный процесс, используя результаты начального приближения:
Проверим выполняется ли условие остановки итерационного процесса::
Условие остановки на первом шаге итерации не и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


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