WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |
УДК 519.6(075) Федеральное агентство по образованию РФ Вычислительная математика. Часть вторая: Учебное пособие для студентов Ангарская государственная техническая академия дневного и заочного обучения технических и химико-технологических специ альностей./ В.С.Асламова, А.Г.Колмогоров, Н.Н.Сумарокова. Ангарская государственная техническая академия. – Ангарск: АГТА, 2005г. - 94 с.

ISBN 5-89864-030-4 В пособии рассматриваются основные положения численных методов, от носящиеся к решению задач аппроксимации функций, обыкновенных дифференциальных уравнений и уравнений в частных производных. Значительное Вычислительная математика внимание уделяется вопросам алгоритмизации методов.

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

Часть вторая Рекомендовано к изданию учебно-методическим советом ангарской государственной технической академии Рецензенты:

доктор физ.-мат. наук, старший научный сотрудник института динамики систем и теории управления СО РАН М.В.Булатов кандидат физ.-мат. наук, доцент кафедры математики АГТА С.А.Чихачев © Ангарская государственная техническая академия, 2005 © Кафедра автоматизации технологических процессов и производств © В.С.Асламова, А.Г.Колмогоров, Н.Н.Сумарокова 2 АГТА 2005 г.

Содержание 1. Аппроксимация функций 1. Аппроксимация функций.................................................................................. 4 1.1. Многочлен Лагранжа................................................................................. 7 Пусть величина у является функцией аргумента х. Это означает, что лю1.2. Многочлен Ньютона................................................................................... 9 бому значению х из области определения поставлено в соответствие значение 1.3. Линейная и квадратичная интерполяция................................................ у. Вместе с тем на практике часто неизвестна явная связь между у и х, т. е.

1.4. Сплайны..................................................................................................... 1.5. Метод наименьших квадратов (среднеквадратичное приближение)... 26 невозможно записать эту связь в виде некоторой зависимости у=f(х). В неко1.6. Контрольные вопросы.............................................................................. торых случаях даже при известной зависимости у=f(x) она настолько гро2. Методы решения обыкновенных дифференциальных уравнений............... моздка (например, содержит трудно вычисляемые выражения, сложные инте2.1. Одношаговые методы............................................................................... гралы и т. п.), что ее использование в практических расчетах затруднительно.

2.1.1. Метод Эйлера.................................................................................... Наиболее распространенным и практически важным случаем, когда вид 2.1.2. Модифицированный метод Эйлера................................................. 2.1.3. Метод Рунге-Кутта 4-го порядка точности.................................... 44 связи между параметрами х и у неизвестен, является задание этой связи в ви2.2. Многошаговые методы............................................................................ де некоторой таблицы {xi, yi}. Это означает, что дискретному множеству зна2.2.1. Методы прогноза и коррекции........................................................ чений аргумента поставлено в соответствие множество значений функ{ x } 2.2.1.1. Метод Милна............................................................................. i 2.2.1.2. Метод Адамса-Башфорта......................................................... ции ( ). Эти значения - либо результаты расчетов, либо экс{yi} i = 0, 1,K, n 2.2.1.3. Метод Хемминга....................................................................... периментальные данные. На практике нам могут понадобиться значения ве2.2.2. Сравнение методов прогноза и коррекции с одношаговыми методами...................................................................................................... 52 личины у и в других точках, отличных от узлов xi. Однако получить эти зна2.3. Решение систем обыкновенных дифференциальных уравнений......... чения можно лишь путем очень сложных расчетов или проведением дорого2.4. Краевые задачи......................................................................................... стоящих экспериментов.

2.4.1. Метод стрельбы................................................................................. Таким образом, с точки зрения экономии времени и средств мы приходим 2.4.2. Метод конечных разностей.............................................................. к необходимости использования имеющихся табличных данных для прибли2.5. Контрольные вопросы............................................................................. 3. Методы решения дифференциальных уравнений в частных производных 65 женного вычисления искомого параметра у при любом значении (из некото3.1. Построение разностных схем.................................................................. рой области) определяющего параметра х, поскольку точная связь y=f(x) не3.2. Уравнения первого порядка..................................................................... известна.

3.3. Уравнения второго порядка..................................................................... Этой цели и служит задача о приближении (аппроксимации) функций:



3.3.1. Волновое уравнение......................................................................... данную функцию f(x) требуется приближенно заменить (аппроксимировать) 3.3.2. Уравнение теплопроводности.......................................................... 3.4. Контрольные вопросы.............................................................................. 93 некоторой функцией так, чтобы отклонение от f(x) в заданной (x) (x) 4. Литература........................................................................................................ области было наименьшим. Функция при этом называется аппроксими(x) рующей. Для практики весьма важен случай аппроксимаций функции многочленом 2 m. (1.1) ( x) = a0 + a1x + a2 x + K + am x В дальнейшем будем рассматривать лишь такого рода аппроксимацию.

При этом коэффициенты aj, будут подбираться так, чтобы достичь наименьшего отклонения многочлена от данной функции.

3 (1.3) Если приближение строится на заданном дискретном множестве точек xi, (x) = a0 + a1x + a2 x2 +K + an xn используется для интерполяции функции f(x) на всем рассматриваемом инто аппроксимация называется точечной. К ней относятся интерполирование, среднеквадратичное приближение и др. При построении приближения на нетервале изменения аргумента х. Коэффициенты многочлена (1.3) находятa j прерывном множестве точек, например, на отрезке [a, b] аппроксимация нася из системы уравнений (1.2). Можно показать, что при ( ) i k xi xk зывается непрерывной (или интегральной).

эта система имеет единственное решение.

Точечная аппроксимация Интерполяционные многочлены могут строиться отдельно для разных Одним из основных типов точечной аппроксимации является интерполичастей рассматриваемого интервала изменения х. В этом случае имеем кусочрование. Оно состоит в следующем: для данной функции y=f(x) строим мноную (или локальную) интерполяцию.

гочлен (1.1), принимающий в заданных точках хi, те же значения yi, что и Как правило, интерполяционные многочлены используются для аппрокфункция, т. е.

f (xi ) симации функции в промежуточных точках между крайними узлами интер. (1.2) (xi ) = yi, i = 0,1,K, n поляции, т. е. при. Однако иногда они используются и для приx0 < x < x n При этом предполагается, что среди значений нет одинаковых, т. е.

x i ближенного вычисления функции вне рассматриваемого отрезка при. Точки называются узлами интерполяции, а многочлен. Это приближение называют экстраполяцией.

i k xi xk xi (x < x0, x > xn ) - интерполяционным многочленом. Как видим, при интерполировании основным условием является прохож (x) дение графика интерполяционного многочлена через данные значения функции в узлах интерполяции. Однако в ряде случаев выполнение этого условия yn затруднительно или даже нецелесообразно.

. Например, при большом количестве узлов интерполяции получается вы. сокая степень многочлена (1.3) в случае глобальной интерполяции, т. е. когда. нужно иметь один интерполяционный многочлен для всего интервала изменения аргумента. Кроме того, табличные данные могли быть получены путем yизмерений и содержать ошибки. Построение аппроксимирующего многочлена с условием обязательного прохождения его графика через эти эксперимен тальные точки означало бы тщательное повторение допущенных при измереyниях ошибок. Выход из этого положения может быть найден выбором такого X многочлена, график которого проходит близко от данных точек (рис. 1, пунктирная линия). Понятие «близко» уточняется при рассмотрении разных видов xn x1...

xприближения.

Рис. 1. Построение интерполяционного многочлена Одним из таких видов является среднеквадратичное приближение функТаким образом, близость интерполяционного многочлена к заданной ций с помощью многочлена (1.1). При этом ; случай m=n соответствуm n функции состоит в том, что их значения совпадают на заданной системе тоет интерполяции. На практике стараются подобрать аппроксимирующий мночек (рис. 1, сплошная линия).

гочлен как можно меньшей степени (как правило, m= 1, 2, 3).

Максимальная степень интерполяционного многочлена m = n; в этом случае говорят о глобальной интерполяции, поскольку один многочлен 5 Мерой отклонения многочлена от заданной функции f(x) на множе(x). (1.7) L(x) = y0l0 (x) + y1l1(x) +K+ ynln (x) стве точек ( i = 0, 1,K, n ) при среднеквадратичном приближении (xi, yi ) При этом потребуем, чтобы каждый многочлен li (x) обращался в нуль во всех узлах интерполяции, за исключением одного i-го узла, где он должен является величина S, равная сумме квадратов разностей между значениями равняться единице. Легко проверить, что этим условиям отвечает многочлен многочлена и функции в данных точках:

n вида (1.4) S = ) - yi ]2.

[(x i ( x - x1 )( x - x )K ( x - x ) 2 n. (1.8) l0 ( x ) = i=( x - x1 )( x - x )K ( x - x ) 0 0 2 0 n Для построения аппроксимирующего многочлена нужно подобрать коэфДействительно, l0 (x0) = 1 при x = x0. При х = х1, х2,…,хn числитель выражефициенты так, чтобы величина S была наименьшей. В этом соa0, a1, K, an ния (1.8) обращается в нуль. По аналогии с (1.8) получим стоит суть метода наименьших квадратов.

(x - x0 )(x - x2 )K(x - xn ) l1(x) =, 1.1. Многочлен Лагранжа (x1 - x0 )(x1 - x2 )K(x1 - xn ) Рассмотрим случай построения интерполяционного многочлена, единого (x - x0 )(x - x1)(x - x3 )K(x - xn ) l2 (x) =, (1.9) для всего отрезка [x0, xn]. При этом график интерполяционного многочлена (x2 - x0 )(x2 - x1)(x2 - x3)K(x2 - xn ) должен проходить через все заданные точки.





KKKKKKKKKKKKKKKKKKK (x - x0 )K(x - xi-1)(x - xi+1)K(x - xn ) Запишем искомый многочлен в виде:

li (x) =, n (xi - x0 )K(xi - xi-1)(xi - xi+1)K(xi - xn ) (1.5) ( x) = a0 + a1 x + K + a x n KKKKKKKKKKKKKKKKKKK Из условий равенства этого многочлена в узлах xi соответствующим заданным табличным значениям yi, получим следующую систему линейных Подставляя в (1.7) выражения (1.8), (1.9), находим уравнений для нахождения коэффициентов а0, а1,…, аn:

n n (x - xk ). (1.10) n L(x) = yi a0 + a1x0 +K+ anx0 = y(xi - xk ) i=0 k= n ki a0 + a1x1 +K+ anx1 = y (1.6) Эта формула называется интерполяционным многочленом Лагранжа.

KKKKKKKKK Покажем, что этот многочлен является единственным. Допустим противоn a0 + a1xn +K+ anxn = yn положное: пусть существует ещё один многочлен F(x) степени n, принимаюМожно показать, что эта система имеет единственное решение, если среди щий в узлах интерполяции заданные значения, т.е. F(xi) = yi. Тогда разность узлов интерполяции нет совпадающих, т.е. если xi xk i k. Решив при R(x)=L(x)-F(x), являющаяся многочленом степени n (или ниже) в узлах xi равна:

эту систему, найдём коэффициенты интерполяционного многочлена (1.5).

,.

R(xi ) = L(xi ) - F(xi ) = 0 i = 0, 1,K, n Заметим вместе с тем, что такой путь построения интерполяционного многочлена требует значительного объёма вычислений, особенно при большом Это означает, что многочлен R(x) степени не больше n имеет n+1 корней.

числе узлов. Существуют более простые алгоритмы построения интерполяОтсюда следует, что R(x) тождественно равно нулю и F(x)=L(x).

ционных многочленов.

Из формулы (1.10) можно получить выражения для линейной (n=1) и Будем искать многочлен в виде линейной комбинации многочленов стеквадратичной (n=2) интерполяций:

пени n:

7 x - x1 x - xL(x) = y0 + y1, n = 1, Начало x0 - x1 x1 - x(x - x1)(x - x2 ) (x - x0 )(x - x2 ) (x - x0 )(x - x1) L(x) = y0 + y1 + y2, n = 2.

ввод N (x0 - x1)(x0 - x2 ) (x1 - x0 )(x1 - x2 ) (x2 - x0 )(x2 - x1) Существует несколько обобщений интерполяционного многочлена Лаi=0, N гранжа. Например, довольно широко используются интерполяционные многочлены Эрмита. Здесь наряду со значениями функции yi в узлах xi задаются ввод X[i],Y[i] значения её производной. Задача состоит в том, чтобы найти многочлен y i степени (2n+1), значения которого удовлетворяют условию интерполя(x) ции (1.2), а производная в узлах xi удовлетворяет соотношению ввод Xр, для которого вычисляем,.

i = 0, 1,K, n (xi ) = yi значение функции В этом случае также существует единственное решение, если все xi различны.

Yр:=На рис. 2 приведена блок-схема метода аппроксимации функции интерполяционным полиномом Лагранжа.

i := 0, N вывод 1.2. Многочлен Ньютона P:=Xр, Yр Рассмотрим случай равноотстоящих значений аргумента, т.е.

. Величина h называется шагом.

xi - xi -1 = h = const, i = 1, 2, K, n k:=0, N Конец Введём также понятие конечных разностей. Пусть известны значения нет i <> k функции в узлах xi:.

yi = f (xi ) да Составим разности значений функции:

P (Xр-X[k]) y0 = y1 - y0 = f (x0 + h) - f (x0 ), = P :

X[i]- X[k] y1 = y2 - y1 = f (x0 + 2h) - f (x0 + h), LLLLLLLLLLLLLLLL yn-1 = yn - yn-1 = f (x0 + nh) - f (x0 + (n -1)h).

Yр: =Yр+PY[i] Эти значения yi (i=1,2,…n-1) называют первыми разностями (или разноРис. 2. Блок-схема метода интерполяции функции полиномом Лагранжа стями первого порядка) функции.

Можно составить вторые разности функции:

Конечные разности можно выразить непосредственно через значения,, …, 2 y0 = y1 - y0 2 y1 = y2 - y1 2 yi = yi - yi-функции. Например, i=1, 2,…n-2.

y = y - y = ( y - y ) - (y - y ) = y - 2y + y, 0 1 0 2 1 1 0 2 1 Аналогично составляются разности порядка k:

3 y0 = 2 y1 - 2 y0 = K = y3 - 3y2 + 3y1 - y0.

, i=1, 2,…n-k.

k yi = k -1 yi-1 - k -1 yi Аналогично для любого k можно записать:

9 k(k -1) y0 2yk y0 = yk - kyk-1 + yk-2 + K + (-1)k y0. (1.11) N(x) = y0 + (x- x0)+ (x - x0)(x- x1) +K 2! h 2!h (1.14) Эту формулу можно записать и для значения разности в узле xi:

ny+ (x - x0)(x- x1)K(x- xn-1).

k(k -1) n!hn k yi = yk +i - kyk +i -1 + yk +i -2 + K + (-1)k yi.

2! k Конечные разности y могут быть вычислены по формуле (1.11).

Используя конечные разности, можно определить yk:

Формулу (1.14) часто записывают в другом виде. Для этого вводится пеk (k - 1). (1.12) ременная t=(x-x0)/h; тогда yk = y0 - ky0 + 2 y0 + K + k y2! x - x1 x - x0 - h Перейдём к построению интерполяционного многочлена Ньютона. Этот x = x0 + ht, = = t - 1, h h многочлен будем искать в следующем виде:

x - xn -x - xN(x) =a +a (x-x )+a (x-x )(x-x )+K+a (x-x )(x-x )K(x-x ). (1.13) 0 1 0 2 0 1 n 0 1 n-,…, = t - n + 1.

= t - h h График многочлена должен проходить через заданные узлы, С учётом этих соотношений формулу (1.14) можно переписать в виде т.е. N(x ) = y ( ). Эти условия используем для нахождения коi = 0,1,K, n i i t(t - 1) N (x0 + th) = y0 + ty0 + 2 y0 + K эффициентов многочлена:

2! (1.15) N(x0) = a0 = y0, t(t - 1)K (t - n + 1) + n y0.

N(x1) = a0 + a1(x1 - x0) = a0 + a1h = y1, n! N(x2) = a0 + a1(x2 - x0) + a2(x2 - x0)(x2 - x1) = a0 + 2a1h + 2a2h2 = y2, Полученное выражение может аппроксимировать данную функцию y=f(x) на всём отрезке изменения аргумента [x0, xn]. С точки зрения повышения точLLLLLLLLLLLLLLLLLLLLL ности расчётов и уменьшения числа членов в (1.15) целесообразно ограниНайдём отсюда коэффициенты a0, a1, a2 :

читься случаем 0 t 1, т.е. использовать формулу (1.15) для x0 x x1.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.