Шпоры по вычмату (Шпаргалка по вычислительной математике для печати)

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)

G rad-задаёт направление. Предположим что все 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-ой случай т.к. оставшиеся случаи либо сводяться к нему либо аналогичны. _