Некоторые дополнительные вычислительные методы

Министерство образования и науки РФ

ГОУ ВПО “УГТУ-УПИ”

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

 

по “Вычислительной математике”

на тему: “Некоторые дополнительные вычислительные методы”

Семестр № 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=[a_ij] – квадратная матрица порядка n и

,  - векторы-столбцы.

Представим матрицу A в виде произведения нижней треугольной матрицы B=[b_ij] и верхней треугольной матрицы C=[c_ij] с единичной диагональю , где

и .

Тогда элементы b_ij и c_ij определяются по формулам

и

Отсюда искомый вектор x может быть вычислен из уравнений  и .

Так как матрицы B и C – треугольные, то системы легко решаются:

и

Из этих двух формул видно, что числа y_i выгодно вычислять вместе с коэффициентами c_ij. Этот метод получил название схемы Халецкого. В схеме применяется обычный контроль с помощью сумм. Если матрица A – симметрическая a_ij=a_ji, то

Пример. Решить систему

Решение.

В первый раздел таблицы впишем матрицу коэффициентов системы, ее свободные члены и контрольные суммы. Далее так как  , то первый столбец из раздела 1 переносится в первый столбец раздела II. Чтобы получить первую строку раздела II, делим все элементы первой строки раздела I на элемент, в нашем случае на 3.

Имеем: ; ; ; ; .

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

Далее определяя по формулам, заполняем вторую сетку для раздела II:

Затем переходим к третьему столбцу, вычисляя его элементы  и  по формулам и т.д., пока не будет заполнена вся таблица раздела II. Таким образом, заполнение раздела II происходит способом “елочки”: столбец - строка, столбец - строка и т.д.

В разделе Ш, пользуясь формулами, определяем  и .

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

I							3	1	-1	2	6	11
I							-5	1	3	-4	-12	-17
I							2	0	1	1	1	3
I							1	-5	3	3	3	-1
II							3	0.333333	-0.333333	2	2	3.666667
II							-5	2.666667	-0.25	0.25	-0.75	0.5
II							2	-0.666667	2	-1.25	-1.75	-2
II							1	-5.333333	6	2.5	3	4
III											2	1
III											-0.75	-1
III											-1.75	2
III											3	3

Метод Зейделя и условия сходимости

Этот метод представляет собой модификацию метода простой итерации. Его смысл заключается в том, что при вычислении (k+1)-го приближения неизвестной x_i учитываются уже вычисленные ранее (k+1)-е приближения x_1, x₂, ..., x_i-1. Пусть дана приведенная линейная система (i = 1, 2, …n). Выберем произвольно начальные приближения корней , стараясь, чтобы они в какой-то мере соответствовали искомым неизвестным x₁, x₂, x₃, ..., x_n. Предположим, что k-е приближение  корней известно, тогда в соответствии с идеей метода будем строить (k+1)–е приближение по следующим формулам:

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

1) или 2) .

Пример. Методом Зейделя решить систему уравнений

Решение. Приведем эту систему к виду, удобному для итерации,

В качестве нулевых приближений корней возьмем: ; ; .

Применяя процесс Зейделя, последовательно получим:

 и т.д.

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

0	1,2000	0,0000	0,0000
1	1,2000	1 ,0600	0,9480
2	0,9992	1,0054	0,9991
3	0,9996	1.0001	1,0001
4	1 ,0000	1,0000	1,0000
5	1 ,0000	1,0000	1,0000

Точные значения корней: .

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

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

Метод хорд

Пусть дано уравнение f(x)=0, где функция f(x) определена и непрерывна на интервале

[a, b] и f(a)f(b)<0. Пусть для определенности f(a)<0 и f(b)>0. Разделим отрезок [a, b] в отношении - f(a):f(b). Это даст нам приближенное значение корня x₁ = a + h₁, где

.

Далее этот прием применяем к одному из отрезков [a, x₁] или [x₁, b], на концах которого функция f(x) имеет противоположные знаки. Аналогично находим второе приближение x₂ и т.д. Геометрически этот способ эквивалентен замене кривой y = f(x) хордой, проходящей через точки А[a, f(a)] и B[b, f(b)].

f(b)

ξ

f(a)

0  x

ξ x₃ x₂ x₁ b=x₀ a=x₀  x₁ x₂  b

0 f(a) x

a  

f(b)

Действительно, уравнение хорды АВ имеет вид

При х = х₁ и y = 0, получим

Полагая, что на отрезке [a, b] вторая производная f''(x) сохраняет постоянный знак, метод хорд сводится к двум различным вариантам.

Из рис. 1 видно, что конец а неподвижен и последовательные приближения: x₀=b;

образуют ограниченную монотонно убывающую последовательность, причем a<ξ<…<x_n+1<x_n<…<x₁<x₀.

Из рис. 2 видно, что неподвижен конец b и последовательные приближения: x₀=a;

образуют ограниченную монотонно возрастающую последовательность, причем

x₀<x₁<x₂<…<x_n<x_n+1<…<ξ<b.

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

Пример. Найти положительный корень уравнения  с точностью до 0,002.

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

Так как  и при  имеем , то можно принять:

Таким образом, , где . Заметим, что точный корень уравнения есть .

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

Пусть корень ξ уравнения f(x)=0, отделен на отрезке [a, b], причем первая и вторая производные f'(x) и f''(x) непрерывны и сохраняют определенные знаки при . Найдя какое-нибудь n-ое приближение корня , мы можем уточнить его по методу Ньютона следующим образом. Пусть ξ=x_n+h_n, где h_n - величина малая. Отсюда по формуле Тейлора получим: f(x_n + h_n) ≈ f(x_n)+h_n f¢(x_n)=0. Следовательно, . Подставив полученное выражение в формулу ξ=x_n+h_n, найдем следующее значение корня:

Графическое нахождение корня методом Ньютона (рис. 3).

Если в качестве начального приближения выбрать точку х₀=В₀ , то процесс быстро сходится. Если же выбрать точку х₀=А, то х₁[a, b], и процесс нахождения корня расходится. Рекомендуется: в качестве х₀ выбирать такую точку, где f(x₀)f''(x₀)>0.

Пример. Вычислить методом Ньютона отрицательный корень уравнения

 с пятью верными знаками.

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

0	-11	3453	-5183	0,7
1	-10,3	134,3	-4234	0,03
2	-10,27	37,8	-4196	0,009
3	-10,261	0,2	-	-

Останавливаясь на , проверяем знак значения . Так как , то,  и любое из этих чисел дает искомое приближение.

 

 

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

Заменим уравнение f(x)=0 эквивалентным x=φ(x). Выберем некоторое начальное приближение x₀ и вычислим дальнейшие приближения по формулам x₁= φ(x₀), x₂= φ(x₁), …, x_n= φ(x_n-1). Если последовательность x_n имеет предел, то итерационный процесс

x_n= φ(x_n-1) (n=1, 2, …) называется сходящимся. Пусть функция φ(x) непрерывна. Переходя к пределу в равенстве x_n= φ(x_n-1), получим

 Следовательно,  является корнем уравнения x=φ(x) и может быть вычислен по формуле x_n= φ(x_n-1) (n=1, 2, …) с любой точностью. Для данного метода существуют две теоремы:

Теорема 1. Пусть корень  уравнения x=φ(x), а также его последовательные приближения x₀, x_n= φ(x_n-1) (n=1, 2, …) содержатся в интервале [a, b] и  на [a, b]. Тогда справедливы утверждения:

итерационный процесс x_n= φ(x_n-1) сходится к корню уравнения ; ; .

Следствие 1. Если требуется найти корень с точностью ε, то кончаем итерационный процесс тогда, когда <ε, т.е. когда .

Следствие 2. Так как =φ() и  =φ(x_n-1), то -x_n= φ()-φ(x_n-1). По теореме Лагранжа . Из этого следует, что если φ'(x)>0 на (a, b), то последовательные приближения x_n= φ(x_n-1) (n=1, 2, …) сходятся к корню монотонно; если φ'(x)<0 на (a, b), то последовательные приближения колеблются около корня.

Теорема 2. Если  на [a, b], а корень  и начальное приближение x₀ находятся на более узком отрезке [α, β], где , то справедливы заключения теоремы 1.

Привести уравнение f(x)=0 к виду x=φ(x) таким образом, чтобы получить сходящийся итерационный процесс, можно различными способами. Рассмотрим два из них:

1) уравнение f(x)=0 равносильно при λ≠0 уравнению λf(x)=0 и уравнению x= λf(x)+x. Обозначим λf(x)+x через φ(x), получим x= φ(x). Параметр λ подберем так, чтобы функция φ'(x)= λf'(x)+1 на [a, b] была по модулю меньше единицы.

2) если , то итерационный процесс расходится. Заменим уравнение x=φ(x) эквивалентным ему уравнением x=ψ(x), где ψ(x) – функция, обратная функции φ(x). Так как , то итерационный процесс x_n=ψ(x_n-1) будет сходящимся.

Пример. Методом итерации найти корень уравнения 5x-8lnx=8 с точностью 0,01.

Решение. Запишем уравнение в виде  и построим соответствующие графики:

Уравнение имеет два корня: . За начальные приближения возьмем z₀=0,5 и x₀=3,5. Для уточнения запишем . Здесь

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

n	x	1+lnx
0  1  2  3  4	3,5 3,605 3,651 3,672 3,682	2,253 2,282 2,295 2,301	3,605 3,651 3,672 3,682	------ 0,105 0,046 0,021 0,010

Так как φ’(z₀)≈3>1, то итерационный процесс расходится. Найдем функцию , обратную функции φ(x). Так как , то итерационный процесс  будет сходится. , результаты вычислений приведены в таблице:

n	zn
0  1  2	0,5 0,503 0,503	-0,688 -0,686 ------	0,503 0,504 ------	------ 0,0015 0,0005