Д.П. Костомаров - Методическое пособие для студентов 2 курса (1113836)
Текст из файла
Московский Государственный университет им.М.В.ЛомоносоваФакультет вычислительной математики и кибернетикиД.П.КостомаровВведение в численные методыМетодическое пособие для 2 курса1999СодержаниеВведениеI. Интерполирование§ 1. Интерполирование полиномами§ 2. Интерполированиие сплайнамиII. Численное интегрирование§ 1. Квадратурные формулы прямоугольников, трапеций, Симпсона§ 2. Квадратурные формулы ГауссаIII. Численное решение систем линейных алгебраических уравнений§ 2.
Метод Гаусса§ 3. Системы с трёхдиогональными матрицами. Метод прогонки§ 4. Обусловленность систем линейных алгебраических уравнений§ 5. Итерационные методы решения систем линейных алгебрпическихуравненийIV. Численное решение обыкновенных дифференциальных уравнений§ 1. Разностные уравнения§ 2. Численное решение задачи КошиЛитератураВведениеДанное пособие представляет собой систематизированное содержание лекцийпо курсу “Ведение в численные методы”, который читается на втором курсефакультета ВМиК с 1994 г. и содержит последовательное изложение основныхпонятий, определений, теорем и утверждений, рассматриваемых идоказываемых на лекциях.I.
Интерполирование§ 1. Интерполирование полиномами1.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].1.2.
Опр. Пусть полином степени 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 точках, существует и единственен.Данное утверждение следует из того, что определитель Вандермонда отличен отнуля.1.3. Интерполяционный многочлен в форме Лагранжа имеетвид1.4. Теорема..Пусть функция y=f(x) имеет n+1 непрерывную производную на [a,b], и Ln(x) -интерполяционный многочлен, Ln(xi) = f(xi) , i=0,1,...,n. Тогда для погрешностиинтерполяции ψ (x) = L(x) - f(x) справедлива оценка,где1.5. Полиномы ЭрмитаПолиномы Эрмита интерполируют таблично заданную функцию с учетомизвестных значений производной в узлах сетки.Пусть заданы 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 ' . Этот полиноми называется полиномом Эрмита.§ 2. Интерполированиие сплайнамиПусть функция y=f(x) задана таблично :x0 = a, xn = b , x0 < x1 < x2 < .... < xn , yi = f(xi) i = 0,..., n.2.1. Опр. Кубической сплайн-интерполяцией называется функция ϕ (x) такая,чтоϕ(xi) = f(xi) , i=0,1,...,n ,ϕ' (xi-0) = ϕ ' (xi+0) ,(1)ϕ' ' (xi-0) = ϕ ' ' (xi+0),ϕ' ' (x0) =0, ϕ ' ' (xn) =0,i=1,...,n-1и ϕ (x) = ai + bi(x-xi) +ci(x-xi)2 +di(x-xi)3 , xi-1 ≤ x ≤ xiВеличины коэффициентов a,b,c,d, находятся из системы уравнений (1).
Длянахождения значений этих коэффициентов удобно, с помощьюпоследовательного исключения неизвестных, редуцировать систему (1) ксистеме трехточечных уравнений относительно коэффициентов сi , и решать еедалее с помощью метода прогонки (см. далее).II. Численное интегрирование§ 1. Квадратурные формулы прямоугольников, трапеций,СимпсонаОпр. Выражение видапредназначенное для вычисления определенного интеграланазывается квадратурной формулой.Опр. Величина R=I - S называется погрешностью квадратурной формулы.1.1.
Формула прямоугольниковПростая : S0 = (b-a) f ( (b+a)/2 ) , R0 = -(b-a)3 f ’’(ξ )/ 24 , ξ ∈ (a,b)Составная:, h=(b-a)/nФормула трапецийПростая : S1 = (b-a)( f(b) + f(a) )/ 2, R1 = (b-a)3 f ’’(ξ )/ 12 , ξ ∈ (a,b)Составная:Формула Симпсона, h=(b-a)/nПростая : S2 = (b-a)( f (a) + 4f( (b+a)/2 ) + f(b) )/ 6,R2 = (b-a)5 f (4)(ξ )/ 90 , ξ ∈ (a,b)Cоставная:,h=(b-a)/n, здесь - четное число.§ 2.
Квадратурные формулы Гаусса2.1.В квадратурных формулах Гаусса ищутся не только коэффициенты Сi , но иточки xi - из соображений обеспечения точности квадратурной формулы дляполинома максимальной степени.Квадратурная формула Гауссабудет точна для произвольного полинома степени 2n+1,если величины ci и xiудовлетворяют системе уравнений:2.2.Можно показать, что узлы xj квадратурной формулы на отрезке [-1,1] являютсякорнями полинома Лежандра:,а коэффициенты квадратурной формулы вычисляются по формуламIII. Численное решение систем линейныхалгебраических уравненийПостановка задачиНайти вектор x , удовлетворяющий уравнениюAx = f ,где A - квадратная матрица порядка n,A = { ai, j }, i,j = 1,2,...,n,x T = {x1,x2,..., xn }, f T = { f1,f2,...,fn },или, что тоже самое, найти x1,x2,..., xn удовлетворяющие системе уравненийa 11 x1 + a 12 x2 + ...
+ a 1n xn = f 1a 21 x1 + a 22 x2 + ... + a 2n xn = f 2................................................a n1 x1 + a n2 x2 + ... + a nn xn = f n§ 2. Метод Гаусса2.1. Метод Гаусса состоит в приведении матрицы к треугольному виду.Приведение матрицы к треугольному виду осуществляется по формулам, m= k+1,...,n, l= k,..., n, k=1,...,n-1.(прямой ход метода Гаусса), в результате чего получается системаa(n) 11 x1 + a(n) 12 x2 + ...
+ a(n) kk x k + ... + a(n) 1n xn = ϕa(n) 22 x2 + ... + a(n) kk x k + ... + a(n) 2n xn = ϕ(n)(n)12....................................................................a(n) kk x k + ... + a(n) kn xn = ϕ(n)k....................................................................a(n) nn xn = ϕ(n)nВычисление решения x1,x2,..., xn осуществляется следующим образом(формулы обратного хода Гаусса)2.2. Общее число действий в методе Гаусса порядка (n3 +3n2)/3.§ 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) , β2 = κ 1 , β 2 = ν 1,i+1=(βiai + fi ) /(ci - ai α i ) i=2, ... , n-1 (прямой ход), αа на втором этапе находится решениеxi = αxn = (νi+12xi+1 + β+β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,..., n1,и существует 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.Тогда метод прогонки корректен.§ 4.
Обусловленность систем линейных алгебраическихуравнений4.1. Опр. Под нормой матрицы А будем понимать§ 5. Итерационные методы решения систем линейныхалгебрпических уравнений5.1. Канонический вид одношаговых итерационных методов для решениясистемы линейных алгебраических уравненийAx = f :где Вк+1 - квадратная матрица n× n , τ k+1 > 0 - итерационный параметр. Вдальнейшем будем использовать следующие согласованные нормы вконечномерном пространстве размерности n:- евклидова норма- норма в С- энергетическая норма A=A*>05.2.
Итерационный метод сходится, если.Опр. Величина zk = xk - x называется погрешностью решения.Опр. Если Bk+1 = B и τk+1= τ то метод называется стационарнымТеорема.Пусть A=A* >0, и B- 0.5τ A>0 тогда итерационный методсходится в норме *A,.5.3. Метод простой итерацииКанонический вид метода простой итерации ТеоремаПусть A=A*>0,, тогда метод простой итерации сходится.Замечание. Если A=A*>0 то у матрицы А существует n собственных значенийλ k таких, что0< λmin=λ1<λ 2<...<λпри этомn-1<λ n=λmaxи,.Можно найти оптимальное значение итерационного параметра τ = τ 0 такое,что заданная точность решения будет достигаться за минимальное числоитераций.ТеоремаПусть A=A*>0, тогда придля погрешности явного методапростой итерации zk справедлива оценка5.4.
Метод ЗейделяКаноническому виду метода Зейделя соответствует B=(D+L), τ =1, где D-диагональная матрица, L - нижняя треугольнаяматрицаИндексный вид метода Зейделя:Теорема.Пусть A=A*>0, тогда метод Зейделя сходится.ТеоремаПусть матрица A такова, что, i=1,..., n, q <1, тогда методЗейделя сходится со скоростью геометрической прогрессии со знаменателем q,т.е..Метод релаксацииКанонический вид:ω < 1- метод нижней релаксацииω = 1- метод Зейделяω > 1- метод верхней релаксацииТеорема Пусть A=A*>0, 0<ω <2, тогда метод релаксации сходится.IV. Численное решение обыкновенныхдифференциальных уравнений§ 1.
Разностные уравнения1.1. Опр. Пусть дан отрезок [a,b]. Равномерной сеткой на этом отрезке назовеммножество узлов ω h такое, что ω h = { xj = jh, j=0,...,n, h=(b-a)/n) }.Опр. Сеточной функцией y = yj = y(xj) называется функция, заданная в узлахсетки.Любую сеточную функцию y j = y(xj) можно представить в виде вектораY=(y0, y1, ..., yn-1, yn), и, следовательно, множество сеточных функций образуетконечномерное пространство, в данном случае размерности n+1. В этомпространстве можно ввести норму, напримерили.Пусть дано дифференциальное уравнениеLu(x) = f(x,u) ( например,).1.2.
Заменим 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 - Lh uh , где (Lu)h - проекция на сетку результата действиядифференциального оператора L на функцию u( например,).Опр. Говорят, что погрешность аппроксимации дифференциального оператораимеет в узле xi порядок k , еслиψ 1(xi) = O(hk) → 0 при h→ 0.Опр. Погрешностью аппроксимации правой части f сеточной функцией ϕназовем величину ψ 2 = fh - ϕ h , где fh - проекция на сетку функции f(x,u)(например, f(xj ,uj).hОпр.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.