Министерство образования и науки РФ
ГОУ ВПО “УГТУ-УПИ”
Курсовая работа
по “Вычислительной математике”
на тему: “Некоторые дополнительные вычислительные методы”
Семестр № 3
Преподаватель
Кочнев В.П.
Студент гр. № р-23021д
Логиновских М.А.
Номер зачетной книжки 17309013
Екатеринбург
2004
________________________________________________________________________
_____
Домашнее задание по ________________________________ № ________________
№ записи в книге регистрации __________________ дата регистрации
___________200_г.
Преподаватель _________________________________________
Студент _________________________________________ группа №
________________
Деканат ФДО _______________
СОДЕРЖАНИЕ
1. Решение систем линейных уравнений …………………………………………………… 3
а) Схема Халецкого …………………………………………………………………………. 3
б) Метод Зейделя и условия сходимости ………………………………………………… 5
2. Методы решения нелинейных уравнений ……………………………………………….. 6
а) Метод хорд ………………………………………………………………………………. 7
б) Метод Ньютона (метод касательных) …………………………………………………. 8
в) Метод итерации ………………………………………………………………………… 9
3. Интерполирование и экстраполирование ……………………………………………….. 11
а) Интерполирование с помощью многочленов ………………………………………… 11
б) Интерполяционный многочлен Лагранжа ……………………………………………. 12
в) Интерполяционные многочлены Стирлинга и Бесселя ……………………………… 13
г) Тригонометрическое интерполирование …………………………………….………… 15
д) Интерполяция сплайнами ……………………………………………………..………… 15
4. Численное дифференцирование и интегрирование ……………………………….…….. 16
а) Постановка задачи численного интегрирования ……………………………………… 16
б) Составные квадратурные формулы ………………………………………………….… 17
5. Приближенное вычисление обыкновенных дифференциальных уравнений
………….. 18
а) Метод Рунге-Кутта ……………………………………………………………………… 18
б) Экстраполяционные методы Адамса ………………………………………………….. 20
в) Метод Милна ……………………………………………………………………………. 20
г) Краевые задачи для обыкновенных дифференциальных уравнений
………………… 21
6. Приближенные методы решения дифференциальных уравнений с частными
производными ………………………………………………………………………………… 21
а) Классификация дифференциальных уравнений второго порядка ……………………
22
б) Постановка краевых задач ……………………………………………………………… 23
в) Метод конечных разностей (метод сеток) …………………………………………….. 24
г) Разностные схемы для решения уравнения теплопроводности ………………………
25
д) Разностные схемы для решения уравнения колебания струны ………………………
26
7. Список литературы ………………………………………………………………………… 27
1. Решение систем линейных уравнений
Системы линейных уравнений (СЛУ) имеют в вычислениях очень большое
значение, так как к ним может быть приведено приближенное решение
широкого круга задач. Так, основными источниками возникновения СЛУ
являются теория электрических цепей, уравнения балансов и сохранения в
механике, гидравлике и т.д. Существует несколько способов решения таких
систем, которые в основном делятся на два типа: 1) точные методы,
представляющие собой конечные алгоритмы для вычисления корней системы,
2) итерационные методы, позволяющие получать корни системы с заданной
точностью путем сходящихся бесконечных процессов. Заметим, что даже
результаты точных методов являются приближенными из-за неизбежных
округлений. Для итерационных процессов также добавляется погрешность
метода.
,
матрица коэффициентов системы;
– вектор свободных членов.
Схема Халецкого
,
где A=[aij] – квадратная матрица порядка n и
– векторы-столбцы.
, где
.
Тогда элементы bij и cij определяются по формулам
.
Так как матрицы B и C – треугольные, то системы легко решаются:
Решение.
, в нашем случае на 3.
.
.
Далее определяя по формулам, заполняем вторую сетку для раздела II:
по формулам и т.д., пока не будет заполнена вся таблица раздела II.
Таким образом, заполнение раздела II происходит способом “елочки”:
столбец – строка, столбец – строка и т.д.
.
Текущий контроль осуществляется с помощью столбца ?, над которым
производятся те же действия, что и над столбцом свободных членов.
2 -0.666667 2 -1.25
-??????????????????????????????????????????????????????????????????????†
††††††††††††††††
Метод Зейделя и условия сходимости
Обычно процесс Зейделя сходится быстрее, чем метод простой итерации.
Бывает, что процесс Зейделя сходится, когда простая итерация расходится
и т.п. Правда, бывает и наоборот. Во всяком случае, достаточные условия
сходимости для метода простой итерации достаточны и для сходимости
метода Зейделя. То есть процесс итерации сходится, если выполнено одно
из условий
.
.
Применяя процесс Зейделя, последовательно получим:
и т.д.
Результаты вычислений с точностью до четырех знаков помещены в таблице:
.
2. Методы решения нелинейных уравнений
)?0. В первую очередь это относится к трансцендентным уравнениям. Кроме
того, даже для алгебраических уравнений степени выше четвертой не
существуют формулы, выражающей их решения через коэффициенты уравнения
при помощи арифметических операций и извлечение корней. Для уравнений
третьей и четвертой степени формулы для отыскания корней существуют, но
они настолько сложны, что практически не применяются. Поэтому большое
значение имеет приближенное вычисление корней уравнения f(x)=0. Для
этого существует множество методов некоторые, из которых мы рассмотрим.
Метод хорд
Пусть дано уравнение f(x)=0, где функция f(x) определена и непрерывна на
интервале
[a, b] и f(a)f(b)0. Разделим
отрезок [a, b] в отношении – f(a):f(b). Это даст нам приближенное
значение корня x1 = a + h1, где
.
Далее этот прием применяем к одному из отрезков [a, x1] или [x1, b], на
концах которого функция f(x) имеет противоположные знаки. Аналогично
находим второе приближение x2 и т.д. Геометрически этот способ
эквивалентен замене кривой y = f(x) хордой, проходящей через точки А[a,
f(a)] и B[b, f(b)].
f(b)
f(a)
? x3 x2 x1 b=x0 a=x0 x1 x2 b
a
f(b)
Полагая, что на отрезке [a, b] вторая производная f”(x) сохраняет
постоянный знак, метод хорд сводится к двум различным вариантам.
Из рис. 1 видно, что конец а неподвижен и последовательные приближения:
x0=b;
образуют ограниченную монотонно убывающую последовательность, причем
a0.
Пример. Вычислить методом Ньютона отрицательный корень уравнения
с пятью верными знаками.
вычисляем по следующей схеме:
и любое из этих чисел дает искомое приближение.
Метод итерации
Заменим уравнение f(x)=0 эквивалентным x=?(x). Выберем некоторое
начальное приближение x0 и вычислим дальнейшие приближения по формулам
x1= ?(x0), x2= ?(x1), …, xn= ?(xn-1). Если последовательность xn имеет
предел, то итерационный процесс
xn= ?(xn-1) (n=1, 2, …) называется сходящимся. Пусть функция ?(x)
непрерывна. Переходя к пределу в равенстве xn= ?(xn-1), получим
является корнем уравнения x=?(x) и может быть вычислен по формуле xn=
?(xn-1) (n=1, 2, …) с любой точностью. Для данного метода существуют
две теоремы:
на [a, b]. Тогда справедливы утверждения:
;
;
.
.
. Из этого следует, что если ?'(x)>0 на (a, b), то последовательные
приближения xn= ?(xn-1) (n=1, 2, …) сходятся к корню монотонно; если
?'(x):
ji• h
jv“ h
‘ h
h
jo1/2 h
j1/4 h
jN¶ h
jY? h
jf? h
jq° h
j~® h
j‹¬ h
jU¦ h
jae¤ h
jic h
ju h
? h
h
h
h
j^— h
jAEa h
jNa h
jUeTH h
jcUe h
joU h
j?O h
jJO h
jWN h
jbI h
joI h
j|E h
jEA h
jOA h
jssA h
h
h
je? h
?????(?e:e:;
h
h
j4
h
h
h
h
jeu h
jou h
jAo h
jLo h
jY? h
jdi h
jqi h
j|e h
h
h
j»ae h
?
j
h
? h
h
h
h
h?IkH* h
hA;} h
h;m h
– h?
h?
h?
h?
h?
h?
h?
h?
h?
h?
h?
h?
h?
h?
h?
h?
h?
o h?
h?
h?
h?
h?
jo- h?
jm1 h?
gdH^c
¬
¬
gd
h
h
h
h
h
h
h
h
h
h
¤
h
h
h
h
h
h
h
h
h
h
h
L+аi3(x - xi)3, x([xi, xi+1], удовлетворяющий условиям
S3(xi)=f(xi), i=0, ..., n.
Данный сплайн на каждом из отрезков [xi, xi+1], i=0, ..., n-1
определяется четырьмя коэффициентами, и поэтому для его построения на
всем промежутке [a, b] необходимо определить 4n коэффициентов. Для их
однозначного определения необходимо задать 4n уравнений.
Условие S3(xi)=f(xi), i=0, ..., n дает 2n уравнений, при этом функция
S3(xi), удовлетворяющая этим условиям, будет непрерывна во всех
внутренних узлах.
, r=1,2 во всех внутренних узлах xi, i=1, ..., n-1 сетки ( дает 2(n-1)
равенств.
Вместе получается 4N-2 уравнений.
Два дополнительных условия обычно задаются в виде ограничений на
значение производных сплайна на концах промежутка [a, b] и называются
краевыми условиями.
Наиболее употребительны следующие типы краевых условий:
а) S'3(а)=f'(а), S'(b)=f'(b);
б) S"3(а)=f"(а), S"(b)=f"(b);
;
г) S'''3(x p+0)=S'''3(x p-0), р =1, n-1.
4. Численное дифференцирование и интегрирование
применяются приближенные методы.
Постановка задачи численного интегрирования
, где
где Rn[f] – ошибка квадратурной формулы. Отсюда получаем приближенную
квадратурную формулу
(i=0, 1, 2, …, n). Для вычисления Ai заметим, что
1) коэффициенты Ai при данном расположении узлов не зависят от выбора
функции f(x);
(k=0, 1, …, n), из которой можно определить коэффициенты A0, A1, …,
An.
Составные квадратурные формулы
Положим f(xn)=yn=f(a+nh).
Погрешность формулы определяется выражением
Погрешность формулы определяется выражением
Погрешность формулы определяется выражением
Если длина интервала [a, b] велика для применения простейших
квадратурных формул, то поступают следующим образом:
на n интервалов по некоторому правилу;
3) из полученных выражений Qi составляют (отсюда и название составная
формула) квадратурную формулу для всего интервала [a, b];
4) абсолютную погрешность R составной формулы находят суммированием
погрешностей Ri на каждом частичном интервале.
5. Приближенное вычисление обыкновенных дифференциальных уравнений
следующим условиям:
называется порядком уравнения.
Метод Рунге-Кутта
которое посредством последнего интеграла связывает значения решения
рассматриваемого уравнения в двух точках, удаленных друг от друга на
расстояние шага h. Для удобства записи данного выражения используем
обозначение
?y=y(x+h)–y(x) и замену переменной интегрирования t=x+(h. Окончательно
получим:
где
где
где
Метод Рунге-Кутта имеет погрешность четвертого порядка (~ h4 ).
- приближенные решения в точке xi, найденные с шагом h и 2h
соответственно.
Экстраполяционные методы Адамса
, совпадает с рассмотренным ранее методом Эйлера первого порядка
точности. В практических расчетах чаще всего используется вариант метода
Адамса, имеющий четвертый порядок точности и использующий на каждом шаге
результаты предыдущих четырех. Именно его и называют обычно методом
Адамса. Рассмотрим этот метод.
.
.
в процессе счета; этого недостатка лишены одношаговые методы.
Метод Милна
последовательно находятся по формулам Милна
.
.
Пример. Дано дифференциальное уравнение y’=y-x, удовлетворяющие
начальному условию x0=0, y(x0)=1,5. Вычислить с точность до 0,01
значение решения этого уравнения при x=1,5.
Решение. Выберем начальный шаг вычисления. Из условия h40 – коэффициент
теплопроводности; ?0, ?1, ?2 – заданные на Г функции, причем ?2 есть
произведение коэффициента теплопроводности на температуру внешней среды,
соприкасающейся с телом.
Таким образом, краевая задача заключается в том, чтобы найти
классическое решение уравнения Пуассона или Лапласа, удовлетворяющее
одному из граничных условий.
Смешанная краевая задача. Рассмотрим задачу распространения тепла в
тонком
, а для единственности решения в этом случае необходимо еще задать
температурный режим на концах стержня. Это можно сделать с помощью
граничных условий, аналогичных тем, которые были сформулированы для
уравнений Пуассона и Лапласа.
.
.
.
Для другого конца стержня x=1 правые части граничных условий заменяются
соответственно на ?0(t), ?1(t), ?2(t). Заметим, что начальное и
граничное условия должны удовлетворять так называемым условиям
сопряжения, т.е. при условии I рода u0(0)=?0(0), при условии II рода
u0x(0)=?1(0), при условии III рода -u0x(0)+?u0(0)=?2(0). Аналогичные
условия сопряжения должны выполнятся и на другом конце стержня x=1.
. Эта задача обычно называется первой краевой задачей для уравнения
теплопроводности. Соответственно краевые задачи с граничными условиями
II роди или III называются второй и третьей краевой задачей для
уравнения теплопроводности.
Метод конечных разностей (метод сеток)
Численные методы, основанные на разностной аппроксимации производных
называется разностным методом, методом конечных разностей или методом
сеток.
. Здесь u – искомое решение уравнения; L – некоторый дифференциальный
оператор, сокращенно обозначающий соответствующую дифференциальную
операцию; f – правая часть уравнения (заданная функция).
.
Разностный метод решения этих двух задач можно представить в виде двух
этапов:
построение разностной схемы, аппроксимирующей данную непрерывную задачу;
получение решения разностной задачи и оценка погрешности этого решения.
.
Второй шаг в построении разностной схемы состоит в аппроксимации
дифференциального выражения Lu некоторым разностным выражением, а
функцию непрерывного аргумента f – сеточной функцией, т.е. в построение
некоторого разностного аналога для данного уравнения, при данных краевых
условиях.
. Эту систему можно записать в следующем виде:
Где Lh и ?h – разностные операторы, аппроксимирующие соответственно L и
l; ?h – искомая сеточная функция, аппроксимирующая решение u; fh, ?h –
заданные сеточные функции, аппроксимирующие f и ?.
Совокупность разносных уравнений, аппроксимирующих исходную задачу –
есть разностная схема. Рассмотрим их подробнее на примерах уравнения
теплопроводности и колебания струны.
Разностные схемы для решения уравнения теплопроводности (параболический
тип)
решение задачи:
{xn, tk} с шагом h=1/N по координате x и с шагом ?=T/M по координате t:
.
.
Для второй и третьей краевых задач граничные условия аппроксимируются на
основе разностных выражений.
– – для второй разностной схемы.
.
Разностные схемы для решения уравнения колебания струны (гиперболический
тип)
решение задачи:
. Отличие заключается в приближении второй производной по переменной t:
.
Разностная аппроксимация принимает вид
.
.
.
, где ?=?/h.
.
Список литературы
Демидович Б.П., Марон И.А. Основы вычислительной математики. Наука,
1970.
Минкова Р.М., Вайсбурд Р.А. Методы вычислительной математики. УПИ, 1981.
Боглаев Ю.П. Вычислительная математика и программирование. Высшая школа,
1990.
Кацман Ю.Я. Прикладная математика. Численные методы. ТПУ, 2000.
PAGE
PAGE 2
0 x
y
y
A
A
B
B
0 f(a) x
Рис. 1. Рис. 2.
Рис. 3.
?
y
B0
A
0 f(a) x2 x1 x
B1
a ?
Рис. 4.
Mn
M0
y = P(x)
y = f(x)
y
x0 x1 xn x
b=x0 x1’
Нашли опечатку? Выделите и нажмите CTRL+Enter
