Шпоры по вычмату (1023546), страница 2

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

Текст из файла (страница 2)

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*) с любой степенью точности.

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

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_i h/2,y_i+k₁⁽ⁱ⁾/2); k₃⁽ⁱ⁾=h*f(x_i h/2,y_i+k₂⁽ⁱ⁾/2); k₄⁽ⁱ⁾=h*f(x_i h,y_i+k₃⁽ⁱ⁾). Вычисляются знач-я k, соотв-но y_i+1=y_i+Δy_i. Шаг Δ выч-ся т.о., что Δy_i=1/6 (k₁⁽ⁱ⁾+ 2k₂⁽ⁱ⁾+ 2k₃⁽ⁱ⁾+ k₄⁽ⁱ⁾). Удобно на каждом шаге записывать таблицу

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₁ и т.д. Конечные разности записываются в виде таблицы:

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