Untitled

1.Метод простой итерации.

Решим систему Ах=В (1), А= х= В= пусть аij ≠ 0 тогда Х₁=β₁+£₁₂Х₂+£₁₃Х₃+…+£_1nХ_n. Хn= βn+£_n1Х₁+£_n2Х₂+ …+£nn-1An-1, где βi=вi/Aii £ij=Aij/Aii Х=β+£х – эту систему будем наз. методом последовательных приближений. За 0-е приближение можно взять столбец свобод. членов Х⁰=β, тогда Х¹=β+£, Х¹ – 1-ое прибл. Если посл-ть х0,х1… имеет предел, то этим пределом будет решение сис. т.е. Х^k=∑(i=1 до n) £*Xi^(K-1) +βi. Дост. услов. сходим. 1) ∑(от i=1 до n)|Aij|<1 для люб.Y 2) ∑(от j=1 до n) |Aij|<1 для любого i Следствие: для сист. метод итер. сходит. если все модули диагонал. коэффициентов для каждого Ур-ия >, суммы модулей всех остал. коэффиц.|Aii|<∑(i ≠ j)|Aij|.

2.Метод Зейделя.

Основная идея: при вычислении (К+1)-го приближения неизвестной Хi учитываются уже вычисленные ранее (К+1)-е приближение х1,х2,… Пусть дана приведенная лин. система Хi=βi+(∑ от j=1 до n)£ij*xi^K Предпол. что К-е приближ. известны тогда (К+1) имеет вид Xn^(K+1)=βn+(∑ отj=1 до n-1) £niXj^(K+1) + £nnXn^(K). Достаточное условие: 1) ∑(от i=1 до n)|Aij|<1 для любого y 2) ∑(от j=1 до n)|Aij|<1 для любого i Следствие: для сист. метод итер. сходит. если все модули диагонал. коэффициентов для каждого Ур-ия >, суммы модулей всех остал. коэффиц. |Aii| <(i≠j)|Aij|.

3.Достаточные условия сходимости процесса итерации (доказать)

Теорема: процесс итерации для системы Х=£x+β сх. к единств. решению если какая либо норма матр. £<1 или ||£||<1, x^K=£x^(K-1)+β,

Док-во: постр. последов. приближен., таких, что X^K=(£^(K-1) +£^(K-2)+…+ £+E)β+£^KX⁰ Т.к. норма матр.<1, то норма £к→0, при к→∞ E+£+£²+…+£^K-1=(∑от n=0 до K-1) £n| ||£||<1 |=(E-£)^-1 X=lim(k→∞)X^к=lim[ (£^(K-1) +£^(K-2)+…+ £+E)β+£^KX⁰ ]=(E-£ )^-1β Сходимость доказана.

4. Отделение корней уравнения.

Отделение корней может происходить аналитически или графически.

F(x)=0 X^*- решение( F(X^*) =0). Т. Если непрерывная ф-ция F(x) принимает значения различных знаков на [a,b], т.е F(a)*F(b)<0,то внутри этого отрезка содержится по крайней мере один корень уравнения F(x)=0

5. Метод половинного деления.

Будем решать ур-ние f(x)=0 на [a,b], известно, что f(a)*f(b)<0. Найти X такое [x-x*] < ε. Метод состоит в последовательном построении интервалов [an, bn], вложенных друг в друга и содерж. реш. X*. Пусть a₀=a, b₀=b предпол. что [ai,bi]промежуток построения, причем f(ai)*f(bi)<0 т.е. X* Є[ai,bi] найдем (.)Ci=(ai+bi)/2. Если f(ci)=0 то (ci) точное решение, если f(ci) ≠ 0 то: либо 1) f(ai)*f(сi) < 0, тогда a(i+1)=ai*b(i+1)=ci, либо 2) f(ci)*f(bi)<0, тогда то a(i+1)=ci, b(i+1)=bi В любом случае получ. интервал вдвое меньше исходного, причем f(ai+1)*f(bi+1) < 0 Процесс заканчив. либо 1)|ai-bi|<E,тогда (F(ci)=0),ci- –выбир. любую (.) и приним. ее за решен. ОЦЕНКА точности. f(ai)*f(bi)<0; bn-an=1/2ⁿ X(с чертой)-an<=1/2ⁿ (b-a) k-кол-во шагов k=log₂((b-a)/E)+1. Решение нелин. ур-ий . Решен. осущ. в 2 этапа 1) локализация корней , т.е. нахожд. промежутков [a,b] котор. принадл. корень ур-ия 2)уточнение корней ,т.е. решение с задан. точностью.

6. Метод хорд.

Пусть дана ф-ция F(x) = 0 на [a, b], причем F(a)*F(b) < 0. Для определенности предпол., что F(a)<0 а F(b)>0, тогда поделим отрезок [a,b] на F(a)/F(b). (x-a)/(b-a)=(y-f(a))/(f(b)-f(a)); Допустим X=X₁, y=0; X₁=a – (f(a) / (f(b)-f(a)))*(b-a) по этой ф-ле можно записать итерац. процесс X₁=a+h, где h₁=-f(a)/(f(b)-f(a)) Докаж. сходим. итер. процесса будем предполагать, что корень f(x) определен и сохр. знак. на [a,b]. Имеем 2 сл. f(a)>0 и f(a)<0

1)a>0 ;

2) a<0

Т.е.1) неподвиж. тот конец , для кот. знак ф-ции совпад. со знаком втор. производ. 2)Послед. приближен. Xn лежат по ту сторон. X*, где f(x) имеет знак противоп знаку ее 2-ой произв. Критерий остановки |X_n+1 - X_n|< ε

18,19. Метод скорейшего спуска решения линейных систем

Есть система

Предположим, что все f_i непр. дифф., рассм. Ф-цию U(x) = (,)=

. Каждое решение сис. обращает в 0 ф-цию U и наоборот

U()  0 => будем искать минимум ф-ции U, кот. и будет решением

Пусть - 0-ое приближение. Проведем пов. уровня U() и из (.)будем двигаться по нормали к пов-ти уровня (в напр., противоп. grad U = U = (), пока не “коснемся” следующей пов-ти уровня. Точка касания –. И т д. Очевидно, что , таким образом придем в (.) min U, а этот min – решение сист. Можно записать , где _p – это нек-й коффициет, вычисляемый на каждом шаге. Задача в том, чтобы его найти. Рассм ф-ю (_p) = U(). Она задает новый уровень ф-ции U который получен продвижением вдоль соответствующей нормали к пов-ти уровня в (.) x^p и зависит от _p. Множители _p нужно выбирать т.о. чтобы (_p) имела минимум при этом знач. _p, т.е. (_p)/_p = 0. Наименьший положит корень это и есть _p. (_p) = Разложим функции f_i в ряд Тейлора до линейных членов. (_p) = =>

выразим отсюда _p и подставим значение U = 2W^Tf(x). В итоге получим:

x^p+1=x^p-_pW^T(x^p)f(x^p), где _p = 2_p = (f_p,W_pW_p^Tf_p)/( W_pW_p^Tf_p, W_pW_p^Tf_p)

Для линейных систем видаW=A и f_p = r_k =- называется вектором невязки линейной системы.

18. Метод скорейшего спуска решения систем.(grad)

Grad-задаёт направление. Предположим что все fi непрерыв диф-мы Рассмотрим ф-ю u(x)=(_f(_x);_f(_x))= ф-я сама на себя скалярная = (i от 1 до n)(fi(_x))². Очевидно что каждое решение исход сист обращ в 0 ф-ю u(x) и наоборот те числа обращают в 0 ф-ю u(x) явл решеним исх сист. Предположим что исх сист имеет лишь решения которые явл (.) мин ф-ии u таким образом задача сводится к нахождения (.) мин ф-ии u. Пусть _х – решение сист _х(0) – нулевое приблежение. В (.) _х(0) проведём поверхность уровня u(x)=u(xi0), если нач (.) близка к решению, то поверхность похожа на эллипсоид . Из(.) х(0) будем двигаться по нормали поверхности u(x)=u(x0) до тех пор пока нормаль не каснётся другой поверхности уровня u(x)=u(x(1)) Затем отправляемся из (.) х(1) по нормали поверхности уровня u=u(x(1)) до тех пор пока эта нормаль не каснётся поверхности уровня в (.) х(2) и т.д.

Очевидно что u(x(0))>(u(x(1)))>(u(x(n))), т.е. прийдём к (.) мин ф-ии, а этот минимум явл реш исх сист (рис1), grad U. X(p+1)=x(p) - Лp U(x(p)), Лр – нек коэф на каждом шаге задача состоит в том что бы его найти. Ф(Л)=U(x(p) - ЛU(x(p)) эта ф-я задет изменения ф-ии уровня и вдоль соотв нормали к поверхности уровня в (.) х(р) Множ Л=Лр нужно выбирать таким образом, что бы ф-я φ(Л) имела мин т.е. U(x(p) – ЛNU(x(p)) наим положит корень это и есть Л. Получ сист ур-й будем решать численно, поскольку предпол., что Л мало, то будем брать только лин. члены разлож ф-ии в ряд Тейлора x(p)=x(p) - μpwT (xP)f(x(p)) где μр=2Лр=

(Примечание (Л – лямбда))

21. Нахождение остаточного члена формулы трапеций.

Рассмотрим остаточный член для 1-го звена, а остальные просуммируем

Предположим, что ф-ция f дважды дифференцируема. Получим ф-цию

R(h) =- h/2(y(x₀+h)+ y(x₀)). Продифференцируем это рав-во по h

; (y(x₀))’_h = 0; R’(h) = y(x₀+h) – (1/2)*(y₀(x₀+h) + y(x₀)) -

- (h/2)*y’(x₀+h) = (1/2)*(y(x₀+h) - y(x₀)) - (h/2)*y’(x₀+h)

R”(h) = (1/2)*y’(x₀ + h) - (1/2)*y’(x₀ + h) - (h/2)*y”(x₀ + h) = - (h/2)*y”(x₀ + h)

R(0)=R’(0)=R”(0)=0. Проинтегрируем по h и воспользуемся теоремой о среднем

, c₂(x₀, x₀+h)

, c₁(x₀, x₀+h)

Теперь просуммируем остаточные члены для одного звена и получим полный

R(h) = - (h³/12)*y”(c_i), c_i(x_i-1, x_i)

Далее,  (.) c[a, b], такая что (y”(c_i))/n = y”(c) => R(h) = - (h³/12)*n*y”(c) =>

R(h) = - (b-a)*h²*y^”(c)/12, c[a, b]

На практике: I_h = _h + Mh², I_2h = _2h + 4Mh² => R = (_h - _2h)/3

22.Формула СИМПСОНА (парабола).

∫f(x)dx (рис.).

Число разбиен. должно делиться на 4, чтобы можно было вычислить суммы с шагом 2h. Пары интервалов, следующие друг за другом, начиная с первой, будем “накрывать” параболой, проход. через 3 (.)-ки y=A₀+A₁x+A₂x²; (x₀,y₀), (x₁,y₁), (x₂,y₂). Предпол что x₀ = 0 => x₁ = h, x₂ = 2h. Для нахожд. A₀,A₁,A₂ подстав. эти (.)-ки в ур-ие параб. =>

y₀ = A₀; y₁ = A₀+A₁h+A₂h²; y₂=A₀+2A₁h+4A₂h²;

Получим, A₀ = y₀; A₁ = (-3y₀ + 4y₁ - y₂)/2h; A₂ = (y₀ - 2y₁ + y₂)/2h²

Площадь одного эл-та (зависит от h и значений ф-ции в выбранных точках) = = A₀2h+A₁(4h²)/2+A₂h³8/3;

Подставл знач-я А₀, А₁, А₂ получ. I_n=(h/3)*(y_n-2 + 4y_n-1 + y_n);

 I_n = = (h/3)*[y₀ + y_n + 2*y_2k + 4* y_2k-1] – ф-ла Симпсона

23. Оценка погрешности в методе Симпсона.

Предположим, что ф-я y непрерывна и трижды дифференцируема.

Запишем ошибку для первого интервала в виде:

- (h/3)*[y(x₁-h) + 4y(x₁) + y(x₁+h)]

Продифференцируем эту ф-ю 3 раза.

R’(h) = y(x₁+h) – y(x₁-h) – (1/3)[y(x₁-h) + y(x₁+h) + 4y(x₁)] – (h/3)*[-y’(x₁ – h) +

+y’(x₁+h)]

R”(h) = - (1/3)y’(x₁-h) + (1/3)y’(x₁+h) – (h/3)[y”(x₁-h) + y”(x₁+h)]

R”’(h) = -(h/3)[y”’(x₁-h) - y”’(x₁+h)] = -(2h²/3)*y^IV(c₄), c₄(x₁-h, x₁+h)

Теперь будем интегрировать:

R”(h) = , c₃(x₁-h, x₁+h)

R’(h) = = -(1/18)*h⁴*y⁴(c₂), c₂(x₁-h, x₁+h)

R(h) = = -(1/90)*h⁵*y^IV(c₁), c₁(x₁-h, x₁+h) – ошибка для 1-ой пары интервалов; Для всего отрезка ошибка R = -((b-a)/180)*h⁴*y^IV(c), c(a, b);

На практике: R_h = Mh⁴, R_2h = 16Mh⁴; R = (_h - _2h)/15

10. Комбинированный метод.

f(x)=0 : (a,b) : f(a)*f(b)<0 имеем 4 случая:

1. f ’(x)>0 f ’’(x)>0	2.f ’(x)>0 f ’’(x)<0
3.f ’(x)<0 f ’’(x)>0	4.f ’(x)<0 f ’’(x)<0

Расм. только 1-ой случай т.к. оставшиеся случаи либо сводяться к нему либо аналогичны. _

X* Є (a,b) x₀=a x₀=b

X* Є

Если допустимая погрешность задана u=E, то как только , то процесс заканчивается. За решение ур-ия удобно взять среднее

20.Формула ТРАПЕЦИИ.

Разобьем отрезок [a; b]

на n равных отрезков

[x₀,x₁], [x₀,x₂], …, [x₀,x_n]

шаг h = (b-a)/n

y_i=f(x_i)

Ф-ла ТРАПЕЦИИ:

= (y₀+y₁)*h/2+(y₁+y₂)*h/2+…+(y_n-1+y_n)*h/2= (y₀+y_n)*h/2+h*(y₁+y₂+…+y_n-1)

24. Метод Эйлера решения дифференциальных уравнений

y’=f(x,y); y(x₀) = y₀ - задача Коши. Разобьем ось х на промежут. x_i = x₀+i*h (рис.) В (.)M₀-пров. касател. до пересеч. с прямой х = х₁, получим (.)M₁. y₁ = х₁ M₁

Через (.) (x₁, f(x₁, y₁)) пров касат до пересечения с прямой x = x₂, получим M₂ и тд Получ. Ломаную M₀M₁M₂… считаем решением.

Аналитически: f(x_i,y_i) = y’ (y_i+1 - y_i)/h => y_i+1 = y_i + h*f(x_i,y_i)-ф-ла облад. малой точностью.(порядка h²); y(xi+h)=y(xi)+y’(xi)h остал. члены разлож. в ряд Тэйлора (y(x)=y(x₀)+y’(x₀)(x-x₀)+y”(x₀)(x-x₀)²/2!-поэт. точность порядка h².

7. Геометрическая иллюстрация метода касательных.

Геометрически прямая параллельная первой касательной . т.е. здесь касательная заменяется на прямую, паралл. первой касательной.

8. Теорема о методе касательных.

Если ф-ия f(a)*f(b)>0, причем вторая призводная сохраняет знак на отрезке [a,b], то исходя из любого начального приближения х₀Є[a,b], удовл. условию f(х₀) f”( х₀)>0 то можно вычислить корень ур-я с любой степенью точности. Док-во: f(a)<0; f(b)>0; f”(x)>0; f’(x)>0, т.е. f(b) f”(b)>0 x₀=b. Методом индукции докажем что, все x_n>x*. Т.е. f(x_n)>0, очевидно х₀>x*. Путь х_n>х*. Представим х*=х_n+(х*-х_n) по форм. Тейлора f(x*)=f(x_n)+f’(x_n) (х*-х_n)+1/2 f”(x_n) (х*-х_n)², тогда f(x_n)-f’(x_n) (х*-х_n)<0 х_n+1=x_n(+)-f(x_n)/f’(x_n)>x*. Ч.т.д.

9. Видоизмененный метод касательных.

X(n+1)=Xn-f(Xn)/ (Xn). Если производная исходной ф-ции меняется мало на [a,b] то можно предположить f(Xn)≈f(X0) X(n+1)=Xn-f(Xn)/ (X0) Это дает воз-ть не вычисл. зн-е произв. в каждой (.).

Геометрически

прямая параллельная первой касательной . т.е. здесь касательная заменяется на прямую, паралл. первой касательной

12. Теорема о сходимости метода итераций.

Пусть φ(х) опред. и диф. на [a,b] тогда, если сущ. дробь q такая Тогда 1) процесс итерации А(n+1)=φ(x_n) сход. независ. от x₀.2) Предельн. знач-е явл. единств. корнем ур-ия

.Д-во: рассмотр. x_n=φ(x_(n-1)); x_(n+1)=φ(x_n); вычтем, по теорем. Лагранжа будем иметь x_(n+1)-x_n=(x_n-x_(n-1))*(x_n(с чер.)); |x_(n+1)-x_n|<=q|x_n-x_(n-1)|.Пусть n=1,2…Тогда. |x_(n+1)-x_n| <=|x_n-x₀|. Рассмотр. ряд x₀+(x₁-x₀)+(x₂-x₁)+… для этого ряда посл-ти приближен. явл. (n+1)-ми частными суммами Т.е. x_n=S_(n+1) В силу неравенств все члены ряда < соотв. членов геом. прогрессии. У котор. знаменат. <1 поэт. ряд сход. абсолютно. LimSn+1=LimXn=X* (n-бескон.)- единств. решение.x_(n+1)=φ(x_n), x*. Итер. процесс сход. тем быстрее, чем

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

f(x)=0, заменим это ур-е равносильным x=f(x) и построим приближение x₂=f(х₁),…x_n+1=f(x). Если эта последовательность существует и сходиться, т.е. сущ. Предел x*=f(x*) с любой степенью точности.

Метод простой итерации вычисляется след. образом на плоскости построим: А0В1А1В2А2…	полученная лестинца сх. к решению иначе:

Если φ(х) возр. то получается лестницей, если убыв. то строится по спирали.

16. Метод Ньютона решения систем.

или _F(_x)=0. Предположим что найдено _х=(х1(p), х2(p),… хn(p)) одного из его корней, тогда точный корень _х=_х(р)+_Е(р)

_Е(р)=(Е1(р), Е2(р), Е(р))-явл погрешностью (поправкой) т.е. ур-е может быть записано _F(_x(p)+_E(p))=0 Разложим левую часть ур-я по степеням Е, ограничевшись линейными членами _F(_x(p)+_E(p))=F’(_x(p))E(p) Препишем это ур-е в развёрнутом виде Fn(x1(1)+E1(p)…xn(p)+En(p)) = Fn(x1(p)…xn(p)) + F’nx1(x1(p)…xn(p))E1(p) + Fn’x2(x1(p)…x(p))En(p) + F’nxn(x1(p)…x4(p))En(p)т.е. матр F’(x)-явл матрицей Якоби

F’(x)=w(x)=

Иначе F’(x)=w(x)=[fi / xj] i, j=_(1,n) и исходная система примет вид (x(p))+w(x(p))E(p)=0 Подставив в исходное мы получим x(p+1)=x(p)-w-1(_x(p))_F(_x(p)) сист методом Нютона.

(Примечание: _X – иск с чертой)

17. Теорема о сход-ти метода Ньютона. Модиф-ный метод Ньютона.

Теорема Пусть дана _f(_x)=0, где

(_f(_x)= ф-я f1 fn определена и непрерывна вместе со своими частными производными первого и второго пор-ка Пусть х0 некоторое начальное условиеи пусть выполнима:

Якобиант w(x(0))=[ fi(x⁽⁰⁾) / xi(x⁽⁰⁾)] имеет обратную матрицу w -1(x(0))=Г0 причем ||Г0||=<А0, ||Г0f(x(0))|| =<B0, | ²fi(x)/ xixj | =< C. Получим пост удовлет условию μ0=2nА₀В₀С<1

Тогда процесс Ньютона

X(p+1)=x(p)-w -1(x(p))f(x(p)) – сх. Причём x=lim(n∞)x(p) |x - x(p) |=<2B0

Под нормой матрицы понимается ||A||=max(i) |aij|. Метод простой итер. X(p+1) – w -1(x(0))f(x(0)) явл модифиц методом Ньютона и соотв теорема о сходимости метода прост итер аналогична теореме сх метода Ньютона

15. Метод простой итераций решения систем общего вида.

-сист с n неизвестными из n ур-ий φ1, φ2, φ3 - действ опред и непрерывны в некоторой окр (х1*…хn*), кот-я явл реш. Зап эту сист в векторной форме _х=(x1,х2,…хn) _φ =( φ1, φ2,… φn) _х=_φ(_х) - это сист ур-ий в векторной форме

_х(р+1)=_φ(_х(р)) - ур-е в итер процессе Если итерационный проц сх, то он сх к корню векторного ур-я. Т.к. проц итер для ур-ий X_р+1= φ(х(р)) сх только в случае | φ’(x)|<1, то такое же усл мы получим и для сист аналогично найдём множитель, который даст возможность удовлет усл | φ’(x)|<1 Рассмотрим в общем виде сист ур-й _F(_x)=0. представим её в виде: _х=_х+Л_F(_х); в данном случае Л неособенная матрица, т.е опр ≠ 0. _х=_φ(х), где φ(_x)=_х+Л_F(_х)

Для послед ур-я применим метод итер. φ(_x)=Е+Л_F’(_х) т.к. норма этой матрицы должна быть мала, выбираем Л из усл-я _φ’(_х(0))=Е+ЛF’(_x(0))=0

Л = - [F’(_x(0))]-1

13. Выбор коэффициента в методе итераций.

Нужно учитывать что в у-ии х= φ(х), φ(х) должно удовлет усл φ(х)<1. Этого можно добиться таким способом Рассмотр ур-е F(x)=0 это ур-е равносильно х=х-ЛF(x)=> φ(х)=ч-ЛF(x), где парам Л выбирают таким образом что бы 0=<1-ЛF’(x)=<q<1 По условию задачи m1=<F’(x)=<M1(наиб и наим значение) на [a;b] => Л=1/M1

(Примечание (Л – лямбда))

14. Метод итераций решения нелинейных систем второго порядка (x,y)-реш. сист

При локализации корня графич. способом, удобно эти значения применять за нулевое приблежение. Из 1-ого ур-я явно выразим х, а из 2-ого у.

Lim(n  )Xn=x* Lim(n  )Yn=y*

31.Формула Ньютона для разностных узлов.

∆y₀ = y₁-y₀ ∆y₁= y₂-y₁ ∆y₂= y₃-y₂ ∆y_n-1 = y_n - y_n-1

∆y₀ = y₁-y₀ ∆²y₀ = ∆y₁- ∆y₀ = y₂ – y₁ – y₁ + y₀ = y₂ – 2y₁ + y₀ ∆³y₀= ∆²y₁- ∆²y₀ = y₃ – 3y₂ +3y₁ – y₀

∆^ky₀ = y_k – ky_k-1 + ((k(k-1))/2!)y_k-2 + ((k(k-1)(k-2))/3!)y_k-3 + ...+ (-1)^Ky₁

Запишем эту формулу для значения разности в узле x_i: ∆^ky_i = y_k+i – y_k+i-1 + ((k(k-1))/2!)y_k+i-2 y_k=y₀ +k∆y₀ +((k(k-1)/2!)∆²y₀ + … ∆^ky₀

Построим интерполяционный многочлен Ньютона: N(x)= a₀ +a₁(x-x₀) +a₂(x-x₀)(x-x₁) +a₃(x-x₀)(x-x₁)(x-x₂) + … a_n(x-x₀)(x-x₁)…(x-x_n-1) Этот многочлен должен проходить через заданные узлы, поэтому: N(x₀)= a₀=y₀ N(x₁)= a₀ +a₁(x-x₀) = a₀ + a₁h=y₁ N(x₂)= a₀ +2a₁h+ 2a₂h² = y₂ Отсюда найдём коэффициенты: a₀=y₀ a₁= (y₁-y₀)/h=∆y₁/h a₂=∆²y₀/2h² Следовательно, любой коэффициент имеет вид: a_k = ∆^ky₀/k!h^K и полином Ньютона будет иметь вид: N(x)=y₀+ (∆y₀(x-x₀))/h + (∆²y₀(x-x₀)(x-x₁))/2!h² + … + (∆ⁿy₀(x-x₀)(x-x₁)…(x – x_n-1))/n!hⁿ

Запишем его иначе: пусть (x-x₀)/h =q тогда N(x) =(y₀ +q∆y₀∆²y₀q(q-1))/2! + … + ∆ⁿy₀(1/n!)q(q-1)(q-2)…(q-n+1) Многочленами Ньютона пользуются в случае равноотстоящих узлов.

32.Приближенное дифференцирование. Постановка краевых задач

Пусть имеем функцию y(x) заданную в равноотстоящих точках. Запишем многочлен Ньютона для этой функции y(x)= y₀+q∆y₀+(q(q-1) ∆²y₀)/2 + (q(q-1)(q-2)∆³y₀)/3! + (q(q-1)(q-2)(q-3)∆⁴y₀)/4! Для нахождения производной функции будем искать производную этого многочлена h=x_i+1-x_i; q=(x-x₀)/h y(x)= y₀+q∆y₀+ ((q²-q)∆²y₀)/2+((q³-3q²+2q)∆³y₀)/3! + ((q⁴-6q³+4q²-6) ∆⁴y₀)/4!+… dy/dx=(dy/dq)(dq/dx)=(1/h)(dy/dq) y’(x)=1/h(∆y₀+((2q-1)∆²y₀)/2+((3q²-6q+2)∆³y₀)/3! + ((4q³-18q²+22q-6)∆⁴y₀)/4!+…) Аналогично вычисляются производные любых порядков. Иногда требуеся находить производные функции в основных табличных точках x_i, тогда производная выглядит следующим образом: y’(x₀)= (1/h)(∆y₀ - ∆²y₀/2 + ∆³y₀/3 -∆⁴y₀/4+…) Постановка краевых задач: пусть дано: y”=f(x,y,y’) y(a)=A y(b)=B Геометрически это означает, что требуется найти интегральную кривую, проходящую через заданные точки. В некоторых случаях краевые условия сводятся к заданиям значений производных y’(a)=A y’(b)=B, т.е нужно найти такую интегральную кривую, которая в заданных точках проходит под известным углом.

33.Метод конечных разностей

y’_i= (y_i+1-y_i)/h y’’_i = (y’_i+1-y’_i)/h = ((y_i+2-y_i+1)/h-(y_i+1-y_i)/h)/h=(y_i+2-2y_i+1+y_i)/h² т.е для нахождения производной 1 порядка нужно знать значения ф-ции в 2 узлах. Для нахождения производной второго порядка нужно знать значения ф-ции в 3 узлах. Пользуются следующей разностной схемой:1)разбивают отрезок [a,b] точками a=x₀,x₁, x₂,…,x_n=b 2)y’_i=(y_i+1-y_i-1)/2h 3) y’’_i=(y_i+1-2y_i+y_i-1)/h² 4)y’₀=(y₁-y₀)/h 5) y’_n = (y_n-1 – y_n)/-h Будем рассматривать д.у 2 порядка: y” +p(x)y’+q(x)y =f(x) при заданных условиях α₀y(a)+ α₁y’(a)=A β₀y(b)+ β₁y’(b)=B │α₀│+│α₁│≠0 │ β₀│+│ β₁│≠0 Исходная система может быть представлена в виде разностной схемы (y_i+1–2y_i+y_i-1)/h²+p_i(y_i+1-y_i-1)/2h +q_iy_i=f_i, где p_i, q_i, f_i –значения коэффициентов в точках x_i. α₀y₀+ (α₁(y₁-y₀))/h=A β₀y_n+ (β₁(y_n-1-y_n))/-h=B Решив эту систему получим таблицу значений искомой функции y

35.Уравнение Лапласа в конечных разностях

Будем решать δ²u/δx²+ δ²u/δy²=0 Будем решать задачу Дирихле, т.е найдём решение уравнения Лапласа в заданной области, ограниченной контуром гамма причём u(p)=φ(p) PГ для всех точек p принадлежащих границе.Т.е на границе области задана непрерывная функция. Перейдём от дифура к его разностному аналогу δ²u/δx²= =(u(x+h,y)-2u(x,y)+u(x-h,y))/h² δ²u/δy²=(u(x,y+h)-2u(x,y)+u(x,y-h))/h² Подставим u(x,y)=1/4(u(x+h,y)+u(x-h,y)+ u(x,y+h) +u(x,y-h)) Это уравнение соответствует первой разностной схеме. 1 осн схема изображена на левом рисунке. 2 осн сх: u(x,y)=1/4(u(x+h,y+h)+u(x+h,y-h)+ u(x-h,y-h) +u(x-h,y+h)) И 1 и 2 схема являются точными до порядка h²

34 .Метод прогонки

Будем рассматривать д.у 2 порядка: y” +p(x)y’+q(x)y =f(x) при заданных условиях α₀y(a)+ α₁y’(a)=A β₀y(b)+ β₁y’(b)=B │α₀│+│α₁│≠0 │ β₀│+│ β₁│≠0 Исходная система может быть представлена в виде разностной схемы (y_i+1–2y_i+y_i-1)/h²+p_i(y_i+1-y_i-1)/2h +q_iy_i=f_i (1), где p_i, q_i, f_i –значения коэффициентов в точках x_i. α₀y₀+ (α₁(y₁-y₀))/h=A β₀y_n+ (β₁(y_n-1-y_n))/-h=B Будем использовать метод прогонки Из ур (1) можно получить y_i+1+m_iy_i+n_iy_i-1=f^_ih² (4) где коэффициенты имеют вид: m_i=(2-q_ih²)/(1+p_ih/2) n_i= (1-p_ih/2)/(1+p_ih/2) f^_i=f_i/(1+p_ih/2) Из уравнения (4) выразим y_i y_i=f^_ih²/m_i – (1/m_i)(y_i+1)-(n_i/m_i)(y_i-1) (5) Предположим, что с помощью системы (2), (3), (4) из ур-ния (5) исключено y_i-1,тогда y_i= c_i(d_i-y_i+1) (6) Из ур (6) можно записать y_i-1= c_i-1(d_i-1-y_i) Подставляя это уравнение в ур-ние (4) получим y_i+1+m_iy_i+n_ic_i-1d_i-1-y_i=f^_ih²

Отсюда выразим y_i

y_i=( f^_ih²- n_ic_i-1d_i-1-y_i+1)/(m_i-n_ic_i-1) Исходя из сравнения полученных формул получим c_i=1/m_i-n_ic_i-1 d_i=f^_ih²-n_ic_i-1d_i-1 c₀= α₁/ (α₀h - α₁) d₀=Ah/ α₁ На основании этих формул последовательно определяются с_i и d_i при i=1 до n-1 включительно Обратный ход начинается с вычисления y_n Вычислив y_n по ф-ле (6) определяются все остальные значения y

36.Метод сеток. Построение шаблонов

Пусть в плоскости XOY имеется область G с границей Г, построим на плоскости два семейства параллельных прямых x= x₀+ih y=y₀+kh

В каждой внутренней точке заменим исходное уравнение конечно-разностным по 1 или 2 схеме. В граничных точках u(Bh)=u(B)=φ(B),где B-ближайшая к границе точка. Для внутренних узлов:u^k_ij =1/4(u^k-1_i-1,j+ u^k-1_i+1,j+ u^k-1_i,j-1+ u^k-1_i,j+1) В граничных точках значения могут быть поправлены по формулам линейной интерполяции u⁰(Ah)= u(a)=φ(A) u^k(Ah)= u(a)+(( u^k-1(B)-u(A))/(h+δ))δ точка A ближайшая к узловой точке Ah границы Г B-ближайший к Ah внутренний узел сетки δ- удаление узла Ah от точки A. Значение δ может быть как + так и – Если узел расположен на границе u^k(Ah)= u(a)=φ(A) При решении задачи для выбора u⁰_ij используют линейную интерполяцию. Иногда для решения задачи используют крупную сетку, а затем решают её же но на более мелкой сетке. Построение шаблонов. Для построения шаблонов строим вторую сетку, линии которой проходят посередине между линиями первой, причём так, что узлы первой сетки попадают в центры клеток 2 сетки

25. Модифицированный метод Эйлера.

В отличии от метода Эйлера, когда для вычисления следующей точки (X_i+1, Y_i+1) требуется информация только Y предыдущей точки. Мод. метод предполагает знание о нек-ой промежуточной точки x_i+1/2=x_i+h/2 и x_i+1/2=x_i+(h/2)*f_i. Метод заключается: 1) через точку (x_i,y_i) проводится кас-ая с tg наклона tgα=f(x_i,y_i) до х с прямой x=x_i+1/2. В полученной точке х по методу Эйлера выч-ся знач-я ф-ии y=y_i+1/2 и выч-ся знач-е производной f_i+1/2=f(x_i+1/2, y=y_i+1/2). Знач-е этой производной определяет tg угла наклона 2-ой производной, кот. проводится из полученной точки. 2) Затем возвр-ся в исходную точку и через неё проводим прямую, парал 2-й кас-ой.

26. Усовершенствованный метод Эйлера.

1) через точку (x_i,y_i) проводится касс-ая до х с прямой x_i+1/2=x_i+h. Угл. коэф-т этой кривой tgα₁=f(x_i,y_i). 2) В полученной точке по методу Эйлера выч-ся знач-е ф-ии y_i+1=y_i+h*( f(x_i,y_i)) и выч-ся новая производная tg α₂= f(x_i,y_i+1). 3) Далее происходит возврат в точку (x_i,y_i) и через нее проводится новая касательная, где tg угла наклона есть среднее арифметическое 2-ух предыдущих tg-енсов, т.е. tgα = (tgα₁+ tgα₂)/2 = (f(x_i,y_i)+F(x_i+1,y_i+1))/2. Новое значение y_i+1 = y_i+h*((f(x_i,y_i)+F(x_i+1,y_i+1))/2).

28. Интерполирование функций. Постановка задачи.

Пусть на [a,b] заданы (n+1) точек x₀,x₁,…,x_n (эти точки наз-ся узлами интерполяции). Известны значения нек-ой ф-ии в этих точках: f(x₀)=y₀, f(x₁)=y_1, f(x_n)=y_n. По этим точкам требуется построить ф-ю F(x), принадлежащую известному классу, принимающую в узлах интерполяции известные знач-я. В такой интерполяции ф-ия F(x) либо не однозначна, либо не сущ-ет вовсе. Если же ф-ия F(x)=P_n(x) имеет вид полинома степени не выше степени n, то такая задача имеет единственное решение. Полученную интерполяционную ф-ию F(x) используют для нахождения значений ф-ии в точках, отличных от узлов интеропляции. Если эти точки принадлежат промежутку [a,b], то такая задача наз-ся интерполированием в узком смысле. Если же точки выходят за границы [a,b], то такая задача наз-ся экстраполированием.

27. Метод Рунге-Кутта.

Обычно говорят, что метод Р-К явл. Методом 4 и 5 порядка точности, т.е. (h⁴,h⁵). Точно вычислить погрешность этого метода затруднительно, т.к. исходя из текущего значения y(x_i) вычисляют величину y(x_i+2h) 2-мя способами. 1 раз с шагом h, другой с шагом 2h. Если расхождение полученных значений не превышает допустимой погрешности, то шаг выбран правильно и полученное значение можно принять за верное, в противном случае шаг уменьшают в 2 раза. Мы решаем ур-е

Выбирается шаг h, наносится сетка x_i+1=x₀+hi. Рассматривают числа k₁⁽ⁱ⁾=h*f(x_i,y_i); k₂⁽ⁱ⁾=h*f(x_ih/2,y_i+k₁⁽ⁱ⁾/2); k₃⁽ⁱ⁾=h*f(x_ih/2,y_i+k₂⁽ⁱ⁾/2); k₄⁽ⁱ⁾=h*f(x_ih,y_i+k₃⁽ⁱ⁾). Вычисляются знач-я k, соотв-но y_i+1=y_i+Δy_i. Шаг Δ выч-ся т.о., что Δy_i=1/6 (k₁⁽ⁱ⁾+ 2k₂⁽ⁱ⁾+ 2k₃⁽ⁱ⁾+ k₄⁽ⁱ⁾). Удобно на каждом шаге записывать таблицу

i	x	y	k=hf(x,y)	Δy
0	x0	y0	k1^(0)	k1^(0)
	x0+h/2	y0+k1^(0)/2	k2^(0)	2k2^(0)
	x0+h/2	y0+k2^(0)/2	k3^(0)	2k3^(0)
	x0+h	y0+k3^(0)	k4^(0)	k4^(0)

30. Формула Лагранжа.

Будем считать данную ф-ию f(x) и полином Q_m(x)=a₀+a₁x+a₂x²…+a_mx^m близкими, если они совпадают на заданной системе точек x₀,x₁,x₂…x_n. Задача состоит в том, чтобы построить многочлен возможно низшей степени m, принимающий в данных точках известные значения. По основной теореме алгебры можно предположить, что m=n. Исходя из условия задачи, можно записать систему линейных уравнений.. Эта система линейная, её можно решать по формуле Крамера (определитель Вандермода): Δ==П(x_q-x_p) – произведение, где <q. Исходя из этого, можно выписать интерполяционный многочлен Лагранжа:

29. Конечные разности.

Пусть известны значения ф-ии y = f(x) в равноотстоящих узлах x_k=x₀+kh (k=0,n): y₀=f(x₀), y₁=f(x₁), y_n=f(x_n). x = x₀(h)x_n – означает разбивку [x₀,x_n]с шагом h. Конечные разности I (первого) порядка имеют вид: Δy₀=y₁-y₀, Δy₁=y₂-y₁ и т.д. Конечные разности II (второго) порядка: Δ²y₀= Δy₁-Δy₀, Δ²y₁= Δy₂-Δy₁ и т.д. Конечные разности записываются в виде таблицы:

x	y	Δy	Δ^2y	Δ^3y	Δ^4y	Δ^5y
x0	y0
		Δy0
x1	y1		Δ^2y0
		Δy1		Δ^3y0
x2	y2		Δ^2y1		Δ^4y0
		Δy2		Δ^3y1		Δ^5y0
x3	y3		Δ^2y2		Δ^4y1
		Δy3		Δ^3y2
x4	y4		Δ^2y3
		Δy4
x5	y5

Т.е. все разности чётного порядка располагаются в тех же гор. Строках, что и аргументы. А нечётные – в промежуточных строчках.