Лекции ВМиК. Численные методы. [Замок Дракона] (1113826)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекции ВМиК. Численные методы. [Замок Дракона]ВведениеДанное пособие представляет собой систематизированное содержание лекций по курсу "Ведение в численные методы", которыйчитается на втором курсе факультета ВМиК с 1994 г. и содержит последовательное изложение основных понятий, определений, теореми утверждений, рассматриваемых и доказываемых на лекциях.Интерполяция и квадратурные формулы§ 1. ИнтерполированиеОпр. Пусть функция f(х) задана таблично на [a,b]:x0 = a, xn = b , x0 < x1 < x2 < .... < xn , yi = f(xi) i = 0,..., nТогда построение непрерывной на [a,b] функции ϕ (x) , такой что ϕ (xi) = yi называется интерполяцией функции f(x) на [a,b].Опр.

Пусть полином степени n Ln(x) = a0 xn + a1 xn-1 + ... + an интерполирует y=f(x) на [a,b], т.е. Ln(xi) = yi= f(xi). Тогда Ln(x) называется интерполяционным полиномом.Утверждение. Интерполяционный многочлен степени n для функции y=f(x), заданной таблично в n+1 точках, существуети единственен.Данное утверждение следует из того, что определитель Вандермонда отличен от нуля.Существуют некоторые стандартные формы записи интерполяционных полиномов. Интерполяционный многочлен в формеЛагранжа имеет вид.Интерполяционный многочлен в форме Ньютона имеет видгде. .

. - выражения такого вида называются разделенными разностями .Теорема.Пусть функция y=f(x) имеет n+1 непрерывную производную на [a,b], и Ln(x) - интерполяционный многочлен, Ln(xi) = f(xi) , i=0,1,...,n. Тогда для погрешности интерполяции ψ (x) = п L(x) - f(x)п справедлива оценкагдеПолиномы ЭрмитаПолиномы Эрмита интерполируют таблично заданную функцию с учетом известных значений производной в узлах сетки.Пусть заданы n+1 узлов xi , x0 = a, xn = b , x0 < x1 < x2 <....< xn , значения функции в них yi = f(xi) и значения производной в них yi '= f' (xi) i = 0,..., n.

Требуется построить полином P2n+1 (x) такой, что P2n+1(xi) = yi, P2n+1' (xi)= yi ' . Этот полином иназывается полиномом Эрмита.Интерполяция сплайнамиПусть функция y=f(x) задана таблично :x0 = a, xn = b , x0 < x1 < x2 < .... < xn , yi = f(xi) i = 0,..., n.Кубической сплайн-интерполяцией называется функция ϕ (x) такая, чтоϕ (xi) = f(xi) , i=0,1,...,n ,ϕ ' (xi-0) = ϕ ' (xi+0) , ϕ ' ' (xi-0) = ϕ ' ' (xi+0) i=1,...,n-1 (1)ϕ ' ' (x0) =0, ϕ ' ' (xn) =0,http://www.ergeal.ru/archive/cs/chm/ (1 of 9) [23.01.2009 13:58:51]Лекции ВМиК. Численные методы.

[Замок Дракона]и ϕ (x) = ai + bi(x-xi) +ci(x-xi)2 +di(x-xi)3 , xi-1 ё x ё xiВеличины коэффициентов a,b,c,d, находятся из системы уравнений (1). Для нахождения значений этих коэффициентов удобно,с помощью последовательного исключения неизвестных, редуцировать систему (1) к системе трехточечных уравненийотносительно коэффициентов сi , и решать ее далее с помощью метода прогонки (см. далее).§ 2.

Квадратурные формулыВыражение видапредназначенное для вычисления определенного интегралаВеличина R=I - S называется погрешностью квадратурной формулы.Формула прямоугольниковПростая : S0 = (b-a) f ( (b+a)/2 ) , R0 = -(b-a)3 f --(ξ )/ 24 , ξ О (a,b)Составная:Формула трапецийПростая : S1 = (b-a)( f(b) + f(a) )/ 2, R1 = (b-a)3 f --(ξ )/ 12 , ξ О (a,b)Составная:Формула СимпсонаПростая : S2 = (b-a)( f (a) + 4f( (b+a)/2 ) + f(b) )/ 6,R2= (b-a)5 f(4)(ξназывается квадратурной формулой., h=(b-a)/n, h=(b-a)/n)/ 90 , ξ О (a,b),Cоставная:h=(b-a)/n, здесь - четное число.Формулы ГауссаВ квадратурных формулах Гаусса ищутся не только коэффициенты Сi , но и точки xi - из соображений обеспеченияточности квадратурной формулы для полинома максимальной степени.Квадратурная формула Гауссабудет точна для произвольного полинома степени 2n+1,если величины ci иxi удовлетворяют системе уравнений:Можно показать, что узлы xj квадратурной формулы на отрезке [-1,1] являются корнями полинома Лежандра:,а коэффициенты квадратурной формулы вычисляются по формуламРешение систем линейных уравненийПостановка задачиНайти вектор x , удовлетворяющий уравнениюAx = f ,где A - квадратная матрица порядка n,A = { ai, j }, i,j = 1,2,...,n, x T = {x1,x2,..., xn }, fT= { f1,f2,...,fn },или, что тоже самое, найти x1,x2,..., xn удовлетворяющие системе уравненийhttp://www.ergeal.ru/archive/cs/chm/ (2 of 9) [23.01.2009 13:58:51]Лекции ВМиК.

Численные методы. [Замок Дракона]a11x1 + a12x2 + ... + a1nxn = f1a21x1 + a22x2 + ... + a2nxn = f2................................................a n1 x1 + a n2 x2 + ... + a nn xn = fn§ 1. Прямые методыМетод Гаусса состоит в приведении матрицы к треугольному виду.Приведение матрицы к треугольному виду осуществляется по формулам, m= k+1,...,n, l= k,..., n, k=1,...,n-1.(прямой ход метода Гаусса), в результате чего получается системаa(n)a(n)1122x1 + a(n)12x2 + ... +x2 + ... + a(n) kk xa(n)kkxk+ ...

+ka(n)+ ... + a(n)2nxn = ϕ(n)1nxn = ϕ(n)12....................................................................a(n) kk x k + ... + a(n) kn xn = ϕ (n)k....................................................................a(n) nn xn = ϕ (n) nВычисление решения x1,x2,..., xn осуществляется следующим образом(формулы обратного хода Гаусса)Общее число действий в методе Гаусса порядка (n3 +3n2)/3.Метод прогонкиМетод прогонки применяется для решения систем линейных уравнений с матрицей специального вида - трехдиагональной матрицей :- ai xi-1 + ci xi - bi xi+1 = fi i=2, ...

, n-1x1 = κ1x2 + νxn = κ2xn-1 + ν1(2)2На первом этапе находятся коэффициентыαi+1= bi /(ci - ai α i) , βi+1= ( β i ai + fi ) /(ci - ai α i ) i=2, ... , n-1 (прямой ход), α2=κ1,β2=ν1,а на втором этапе находится решениеxi = αxi+1 + βi+1xn = (ν2+βni+1, i = n-1, ... ,2,1) / ( 1-αnκ2).Для корректности метода прогонки достаточно, чтобы коэффициенты α i были по модулю меньше единицы, а выражения взнаменателях формул были отличны от нуля. Достаточные условия корректности прогонки формулируются в следующих теоремах.ТеоремаПусть система уравнений (2) такова, что ai > 0, bi >0, ci >0, ci Ё ai + bi , i=2,..., n-1, и п κ 1 + п κ 2 <2, п κ 1 ё 1, п κ 2 1.ппппёТогда метод прогонки корректен.ТеоремаПусть система уравнений (2) такова, что ai > 0, bi >0, ci >0, ci Ё ai + bi , i=2,..., n-1, и существует i0 >1 такое, что ci0 > ai0 + bi0 , и п κ1пё 1, п κ2п ё1.Тогда метод прогонки корректен.ТеоремаПусть система уравнений (2) такова, что з ai , з bi з ,з ci з >0, з ci з > з ai + +з bi з , i=2,..., n-1, и п κзз1пё 1, п κ2п ё1.Тогда метод прогонки корректен.§ 2.

Итерационные методыКанонический вид одношаговых итерационных методов для решения системы линейных алгебраических уравнений Ax = f :http://www.ergeal.ru/archive/cs/chm/ (3 of 9) [23.01.2009 13:58:51]Лекции ВМиК. Численные методы. [Замок Дракона]где Вк+1 - квадратная матрица nƒ n , τk+1> 0 - итерационный параметр. В дальнейшем будем использовать следующиесогласованные нормы в конечномерном пространстве размерности n:- евклидова норма- норма в С- энергетическая норма A=A*>0Под нормой матрицы А будем пониматьИтерационный метод сходится, если.Опр. Величина zk = xk - x называется погрешностью решения.Опр. Если Bk+1 = B и τk+1= τ то метод называется стационарнымТеорема.Пусть A=A* >0, и B- 0.5τ A>0 тогда итерационный методсходится в норме к к * к кA,.Метод ЗейделяКаноническому виду метода Зейделя соответствует B=(D+L), τ =1, где D -диагональная матрица, L - нижняя треугольная матрицаИндексный вид метода ЗейделяТеоремаПусть A=A*>0, тогда метод Зейделя сходится.Теоремаi=1,..., n, к qк <1, тогда метод Зейделя сходится со скоростьюПусть матрица A такова, чтогеометрической прогрессии со знаменателем q, т.е..Метод релаксацииКанонический видω < 1- метод нижней релаксацииω = 1- метод Зейделяω > 1- метод верхней релаксацииТеорема Пусть A=A*>0, 0<ω <2, тогда метод релаксации сходится.Метод простой итерацииКанонический вид метода простой итерации -http://www.ergeal.ru/archive/cs/chm/ (4 of 9) [23.01.2009 13:58:51]Лекции ВМиК.

Численные методы. [Замок Дракона]ТеоремаПусть A=A*>0,, тогда метод простой итерации сходится.Замечание. Если A=A*>0 то у матрицы А существует n собственных значений λ0< λmin=λ1<λ2<...<λn-1<λ n=λkтаких, чтоmax,при этоми.Можно найти оптимальное значение итерационного параметра τ = τ0такое, что заданная точность решения будет достигатьсяза минимальное число итераций.ТеоремаПусть A=A*>0, тогда придля погрешности явного метода простой итерации zk справедлива оценка.Основы теории разностных схем§ 1. Основные понятияОпр.

Пусть дан отрезок [a,b]. Равномерной сеткой на этом отрезке назовем множество узлов ωhтакое, что ωh= { xj = jh, j=0,...,n, h=(b-a)/n) }.Опр. Сеточной функцией y = y j = y(xj) называется функция, заданная в узлах сетки.Любую сеточную функцию y j = y(xj) можно представить в виде вектора Y=(y0, y1, ..., yn-1, yn), и, следовательно, множествосеточных функций образует конечномерное пространство, в данном случае размерности n+1. В этом пространстве можно ввестинорму, напримерили.Пусть дано дифференциальное уравнениеLu(x) = f(x,u) ( например,).Заменим Lu в узле сетки xi линейной комбинацией значений сеточной функции yi на некотором множестве узлов сетки,называемом шаблоном.

Такая замена Lu на Lh yh называется аппроксимацией на сетке дифференциального оператора Lразностным оператором Lh . Замена непрерывной функции f(x,u) в узлах сетки на сеточную функцию ϕ (xh,yh)называется аппроксимацией правой части.Таким образом дифференциальное уравнение можно аппроксимировать (заменить) на сетке разностной схемойLh yh = ϕ ( xh,yh) ( например,).Изучение разностных аппроксимаций проводится сначала локально, т.е. в любом фиксированном узле сетки.Пусть uh - проекция непрерывной функции u(x) на сетку ( например, uh = u(xj) = uj ).Опр.

Погрешностью аппроксимации дифференциального оператора Lu разностным оператором Lh назовем величину ψ1= (Lu)h - Lhuh , где (Lu)h - проекция на сетку результата действия дифференциального оператора L на функцию u( например,).Опр. Говорят, что погрешность аппроксимации дифференциального оператора имеет в узле xi порядок k , если ψ 1(xi) = O(hk) − 0 приh− 0.Опр. Погрешностью аппроксимации правой части f сеточной функцией ϕhназовем величину ψ2= fh - ϕh, где fh - проекция насетку функции f(x,u) (например, f(xj ,uj).Опр.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций