Введение

Интерполяция и квадратурные формулы

┐ 1 Интерполирование

┐ 2 Квадратурные формулы

Решение систем линейных алгебраических уравнений

┐ 1 Прямые методы

┐ 2 Итерационные методы

Основы теории разностных схем

┐ 1 Основные понятия

┐ 2. Методы решения обыкновенных дифференциальных уравнений (ОДУ)

┐ 3. Разностная схема для решения краевой задачи второго порядка

┐ 4. Разностная задача на собственные значения

Литература

Тогда построение непрерывной на [a,b] функции j (x) , такой что j (x_i) = y_i называется интерполяцией функции f(x) на [a,b].

Опр. Пусть полином степени n L_n(x) = a₀ xⁿ + a₁ x^n-1 + ... + a_n интерполирует y=f(x) на [a,b], т.е. L_n(x_i) = y_i= f(x_i). Тогда L_n(x) называется интерполяционным полиномом.

Утверждение. Интерполяционный многочлен степени n для функции y=f(x), заданной таблично в n+1 точках, существует и единственен.

.

. . . - выражения такого вида называются разделенными разностями .

Пусть функция y=f(x) имеет n+1 непрерывную производную на [a,b], и L_n(x) - интерполяционный многочлен, L_n(x_i) = f(x_i) , i=0,1,...,n. Тогда для погрешности интерполяции y (x) = п L(x) - f(x)п справедлива оценка

Пусть заданы n+1 узлов x_i , x₀ = a, x_n = b , x₀ < x₁ < x₂ <....< x_n , значения функции в них y_i = f(x_i) и значения производной в них y_i ' = f' (x_i) i = 0,..., n. Требуется построить полином P_2n+1 (x) такой, что P_2n+1(x_i) = y_i, P_2n+1' (x_i)= y_i ' . Этот полином и называется полиномом Эрмита.

Кубической сплайн-интерполяцией называется функция j (x) такая, что

j (x_i) = f(x_i) , i=0,1,...,n ,

j ' (x_i-0) = j ' (x_i+0) , j ' ' (x_i-0) = j ' ' (x_i+0) i=1,...,n-1 (1)

j ' ' (x₀) =0, j ' ' (x_n) =0,

и j (x) = a_i + b_i(x-x_i) +c_i(x-x_i)² +d_i(x-x_i)³ , x_i-1 ё x ё x_i

Величины коэффициентов a,b,c,d, находятся из системы уравнений (1). Для нахождения значений этих коэффициентов удобно, с помощью последовательного исключения неизвестных, редуцировать систему (1) к системе трехточечных уравнений относительно коэффициентов с_i , и решать ее далее с помощью метода прогонки (см. далее).

Простая : S₀ = (b-a) f ( (b+a)/2 ) , R₀ = -(b-a)³ f --(x )/ 24 , x О (a,b)

Составная: , h=(b-a)/n

Простая : S₁ = (b-a)( f(b) + f(a) )/ 2, R₁ = (b-a)³ f --(x )/ 12 , x О (a,b)

Составная: , h=(b-a)/n

Простая : S₂ = (b-a)( f (a) + 4f( (b+a)/2 ) + f(b) )/ 6,

R ₂ = (b-a)⁵ f ⁽⁴⁾(x )/ 90 , x О (a,b)

Cоставная: ,

В квадратурных формулах Гаусса ищутся не только коэффициенты С_i , но и точки x_i - из соображений обеспечения точности квадратурной формулы для полинома максимальной степени.

Квадратурная формула Гаусса будет точна для произвольного полинома степени 2n+1,если величины c_i и x_i удовлетворяют системе уравнений:

Можно показать, что узлы x_j квадратурной формулы на отрезке [-1,1] являются корнями полинома Лежандра:

,

Найти вектор x , удовлетворяющий уравнению

или, что тоже самое, найти x₁,x₂,..., x_n удовлетворяющие системе уравнений

┐ 1. Прямые методы

Метод Гаусса состоит в приведении матрицы к треугольному виду.

, m= k+1,...,n, l= k,..., n, k=1,...,n-1.

a⁽ⁿ⁾ ₁₁ x₁ + a⁽ⁿ⁾ ₁₂ x₂ + ... + a⁽ⁿ⁾ _kk x _k + ... + a⁽ⁿ⁾ _1n x_n = j ⁽ⁿ⁾₁

a⁽ⁿ⁾ ₂₂ x₂ + ... + a⁽ⁿ⁾ _kk x _k + ... + a⁽ⁿ⁾ _2n x_n = j ⁽ⁿ⁾ ₂

a⁽ⁿ⁾ _kk x _k + ... + a⁽ⁿ⁾ _kn x_n = j ⁽ⁿ⁾_k

a⁽ⁿ⁾ _nn x_n = j ⁽ⁿ⁾ _n

Вычисление решения x₁,x₂,..., x_n осуществляется следующим образом

Общее число действий в методе Гаусса порядка (n³ +3n²)/3.

x₁ = k ₁ x₂ + n ₁ (2)

x_n = k ₂ x_n-1 + n ₂

a _i+1 = b_i /(c_i - a_i a _i) , b _i+1 = ( b _i a_i + f_i ) /(c_i - a_i a _i ) i=2, ... , n-1 (прямой ход), a ₂ = k ₁ , b ₂ = n _1,

x_i = a _i+1 x_i+1 + b _i+1 , i = n-1, ... ,2,1

x_n = (n ₂ + b _n ) / ( 1-a _n k 2 ).

Для корректности метода прогонки достаточно, чтобы коэффициенты a _i были по модулю меньше единицы, а выражения в знаменателях формул были отличны от нуля. Достаточные условия корректности прогонки формулируются в следующих теоремах.

Пусть система уравнений (2) такова, что a_i > 0, b_i >0, c_i >0, c_i Ё a_i + b_i , i=2,..., n-1, и п k ₁п + п k ₂п <2, п k ₁п ё 1, п k ₂п ё 1.

Пусть система уравнений (2) такова, что a_i > 0, b_i >0, c_i >0, c_i Ё a_i + b_i , i=2,..., n-1, и существует i₀ >1 такое, что c_i0 > a_i0 + b_i0 , и п k ₁п ё 1, п k ₂п ё 1.

Тогда метод прогонки корректен.

Пусть система уравнений (2) такова, что з a_iз , з b_i з ,з c_i з >0, з c_i з > з a_iз + +з b_i з , i=2,..., n-1, и п k ₁п ё 1, п k ₂п ё 1.

Тогда метод прогонки корректен.

Канонический вид одношаговых итерационных методов для решения системы линейных алгебраических уравнений Ax = f :

где В_к+1 - квадратная матрица n│ n , t _k+1 > 0 - итерационный параметр. В дальнейшем будем использовать следующие согласованные нормы в конечномерном пространстве размерности n:

- энергетическая норма A=A^*>0

Итерационный метод сходится, если .

Опр. Величина z_k = x_k - x называется погрешностью решения.

Опр. Если B_k+1 = B и t _k+1 = t то метод называется стационарным

Теорема.

Пусть A=A^* >0, и B- 0.5t A>0 тогда итерационный метод

сходится в норме к к * к к _A , .

Каноническому виду метода Зейделя соответствует B=(D+L), t =1, где D -диагональная матрица, L - нижняя треугольная матрица

Пусть A=A^*>0, тогда метод Зейделя сходится.

Пусть матрица A такова, что i=1,..., n, к qк <1, тогда метод Зейделя сходится со скоростью геометрической прогрессии со знаменателем q, т.е.

.

w < 1- метод нижней релаксации

w = 1- метод Зейделя

w > 1- метод верхней релаксации

Теорема Пусть A=A^*>0, 0<w <2, тогда метод релаксации сходится.

Теорема

Пусть A=A^*>0, , тогда метод простой итерации сходится.

Замечание. Если A=A^*>0 то у матрицы А существует n собственных значений l _k таких, что

0< l _min=l _1<l 2<...<l _n-1<l _n=l _max,

при этом и .

Можно найти оптимальное значение итерационного параметра t = t ₀ такое, что заданная точность решения будет достигаться за минимальное число итераций.

Теорема

Пусть A=A^*>0, тогда при для погрешности явного метода простой итерации z_k справедлива оценка

.

Опр. Пусть дан отрезок [a,b]. Равномерной сеткой на этом отрезке назовем множество узлов w _h такое, что w _h = { x_j = jh, j=0,...,n, h=(b-a)/n) }.

Опр. Сеточной функцией y = y _j = y(x_j) называется функция, заданная в узлах сетки.

Любую сеточную функцию y _j = y(x_j) можно представить в виде вектора Y=(y₀, y₁, ..., y_n-1, y_n), и, следовательно, множество сеточных функций образует конечномерное пространство, в данном случае размерности n+1. В этом пространстве можно ввести норму, например

или .

Lu(x) = f(x,u) ( например, ) .

Заменим Lu в узле сетки x_i линейной комбинацией значений сеточной функции y_i на некотором множестве узлов сетки, называемом шаблоном. Такая замена Lu на L_h y_h называется аппроксимацией на сетке дифференциального оператора L разностным оператором L_h . Замена непрерывной функции f(x,u) в узлах сетки на сеточную функцию j (x_h,y_h) называется аппроксимацией правой части.

L_h y_h = j ( x_h,y_h) ( например, ).

Пусть u_h - проекция непрерывной функции u(x) на сетку ( например, u_h = u(x_j) = u_j ).

Опр. Погрешностью аппроксимации дифференциального оператора Lu разностным оператором L_h назовем величину y ₁ = (Lu)_h - L_h u_h , где (Lu)_h - проекция на сетку результата действия дифференциального оператора L на функцию u

( например, ) .

Опр. Говорят, что погрешность аппроксимации дифференциального оператора имеет в узле x_i порядок k , если y ₁(x_i) = O(h^k) - 0 при h- 0.

Опр. Погрешностью аппроксимации правой части f сеточной функцией j _h назовем величину y ₂ = f_h - j _h , где f_h - проекция на сетку функции f(x,u) (например, f(x_j ,u_j).

Опр. Погрешность аппроксимации правой части имеет в узле x_i порядок m , если y ₂ = O(h^m) - 0 при h- 0

Опр. Погрешностью аппроксимации разностной схемы на решении в узле x_i (локальной погрешностью) назовем величину y , равную

y = y ₁ - y ₂ = (Lu)_h - L_h u_h - ( f_h - j _h )= j _h - L_h u_h ,

.

Опр. Значения локальной погрешности аппроксимации в каждом узле x_i образуют сеточную функцию погрешности аппроксимации y _i .

Обычно требуется оценка погрешности аппроксимации на сетке, т.е. оценка функции y _i в некоторой сеточной норме.

Опр. Говорят, что погрешность аппроксимации разностной схемы имеет m-ый порядок на сетке, если ч к y ч к = O(h^m).

ч к z_h ч к =ч к u_h - y_h ч к = O(h^k) - 0 при h- 0.

На отрезке [0,T] вводим разностную сетку w t = { t_n = nt , n=0,...,N, t =T/N } и сеточную функцию y_n = y(t_n).

Метод Эйлера

1.Явный метод Эйлера.

Погрешность аппроксимации явного метода Эйлера y = O(t ) - первого порядка ( y ₁ = O(t ), y ₂ = 0 ).

Величины p_k и a _k выбираются из соображений аппроксимации.

Величины p₁, p₂ , a определяются из условия второго порядка аппроксимации, для данной схемы p₁ = (2 a -1)/ a , p₂ = 1/2 a .

Условие второго порядка аппроксимации (1-s )a =0.5.

В методах Адамса коэффициенты b_i находятся из условий наивысшего для данного p порядка погрешности аппроксимации.

P- шаговому методу Адамса соответствует набор коэффициентов a _i вида

Погрешность аппроксимации имеет второй порядок. Для нахождения y₁ (со вторым порядком) используется обычно схема Рунге-Кутта второго порядка.

.

Разностная аппроксимация второй производной на равномерной сетке w _h простейшего вида имеет второй порядок аппроксимации:

┐ 4. Разностная задача на собственные значения

Числа l и соответствующие функции u(x)│ 0, удовлетворяющие поставленной краевой задаче называются собственными числами и собственными функциями соответственно. Для данной задачи

.

Заметим, что функции u_m(x) являются линейно независимыми и взаимно ортогональными и могут быть нормированы.

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