Задача: Пусть известно значение функции f в n точках x x n



Скачать 202.42 Kb.
страница1/2
Дата02.07.2013
Размер202.42 Kb.
ТипЗадача
  1   2
1. Интерполяционные многочлены. Аппроксимация функций аппроксимационными многочленами. Многочлен Лагранжа. Оценка остаточного члена.
Задача: Пусть известно значение функции f в n точках x1 ... xn.

Требуется найти приближённое значение функции в произвольной точке x[a, b], где a = min (x1 ... xn), b = max(x1 ... xn).

Решение:

Будем искать функцию g (x, a1, ... , an) из условия g(xi, a1, ... , an) = f (xi), i = 1... n.

Положим f(x) ≈ g(x, a1, ... , an) .

g(x, a1, ... , an) = i=1n ai∙φi (x), где φi (x) – произвольная известная функция.

j=1n aj∙φj (xi) = f (xi), i = 1... n. => находим a1 ... an.

Пусть φi (x) = xi-1. Тогда j=1n aj∙xi j-1 = f (xi), i = 1 ... n.

Метод нахождения коэффициентов путём непосредственного решения системы называется «метод определённых элементов». При больших n он не имеет смысла, так как накапливается огромная вычислительная ошибка.

Построим многочлены Фi(xj) = δij <= 0 при i ≠ j, 1 при i = j. Его степень degФi(x) ≤ n-1.

Так как Фi(xj) = 0 при i ≠ j, то x1, x2, ... , xi-1, xi+1, ... , xn являются корнями многочлена, так как degФi(x) ≤ n-1, то есть он имеет не более n-1 корней.

Фi(x) = Ai(x – x1)∙(x – x2)∙...∙(x – xi-1)∙(x – xi+1)∙...∙(x – xn).

Введём обозначение: если a1, ... , an – числа, то a1 ∙...∙ an = i=1Пnai.

и Ln(x) =

1) Ln(x) – многочлен, deg Ln(x) ≤ n-1 - многочлен Лагранжа.

2) Ln(x) =

Ln(x) =

Далее нужно оценить погрешность. Оценим разность f(x) – Ln(x).

ωn (x) = i=1Пn(x – xj).


φ (x) = f(x) – Ln(x) - k ωn(x) где k – некоторое число.

k из условия φ (x) = 0, где x – точка, в которой оценивается разность f(x) – Ln(x).

Пусть f C(n)([a, b]) => φ C(n)([a, b]) и φ = 0 в n+1 точке, x1 , ... , xn+1.

По теореме Ролля φ’(x) обратится в 0 в n точках, φ’’(x) – в n-1 точках, и так далее, в итоге мы знаем, что φ(n) = 0 не более чем в одной точке.

Итак, существует .

Так как deg Ln(x) ≤ n-1 => (Ln(x))(n) = 0.

ωn (x) = (x – x1)∙(x – x2)∙... ∙(x – xn) = xn + g(x), где g(x) – многочлен в чтепени n-1.

n (x))(n) = (xn)(n) = n!

0 = φ(n)(ξ) = f(n)(ξ) - k∙n! => k = f(n)(ξ) / n!

Следовательно для оценки погрешности получается формула:

f(x) = Ln(x) + (ωn (x))∙(f(n)(ξ) / n!)

2. Задача численного интегрирования. Использование интерполяционных многочленов в задаче численного интегрирования.
I = abf(x)dx f(x) = i=1n f(xii(x) + R(x)

I = i=1n f(xi)ci + r , где ci = abФi(x)dx, r = abR(x)dx

I ≈ i=1n f(xi)ci где ci – вес, r = abR(x)dx – погрешность

сi =

Если f – многочлен, то I = i=1n f(xi)ci.

Возьмём f(x) = xj-1 j = 1...n.

Ij = i=1n xij-1 cj j = 1...n где Ij = abxj-1dx = (bj – aj) / j

Итак, мы получили систему, решаемую по Крамару:

b – a = i=1ncj

(b2 – a2) / 2 = i=1n xi cj

...

(bn – an) / n = i=1n xin-1 cj
Пусть fC[a, b]. Найти приближённое значение интеграла abf(x)dx.

Рассмотрим произвольное разбиение τ = {xi}i=0 отрезка [a, b].

a = x0 < x1 < x2 < ... < xn = b xi = a + i∙h h = (b – a) / n



Положим q = (x – x0) / h : [a, b]  [0, n] dx = h∙dq

x – xj = q∙h + x0 – (a + j∙h) = (q – j)∙h

xi – xj = a + i∙h – (a + j∙h) = (i – j)∙h

Значит

Следовательно abf(x)dx = abLn(x)dx + R = (т.к. x = a + q∙h) =

= 0hLn(a + q∙h) ∙hdq + R =

Hi – коэффициент Котеса

Hi =

3. Метод прямоугольников. Оценка погрешности.
Пусть x0[a, b]. Тогда abf(x)dx = abf(x0)dx + R = (b – a)∙f(x0) + R.

По идее x0 может быть любым, но обычно его берут равным a (формула левых прямоугольников), b (правых) или (a+b) / 2 (средних).

R = abf(x)dx – (b – a)∙f(x0) = по Тейлору ζ (x0, x)

= ab(f(x0) + f ’(x0)∙(x – x0) + (f ‘’(ζ) / 2)∙(x – x0)2)dx – (b – a)∙f(x0) =

= f ‘(x0)∙((b – x0)2 – (a – x0)2) / 2) + ab(f ‘’(ζ) / 2)∙(x – x0)2)dx

При x = (a+b) / 2, R минимальна, так как H = 0 |b – x0| = |a – x0|

И тогда R = ab(f ‘’(ζ) / 2)∙(x – x0)2)dx

Пусть fC2[a, b], тогда сущ. M > 0 : |f ‘’(x)| ≤ M x[a, b]

|R| = | ab(f ‘’(ζ) / 2)∙(x – x0)2)dx| ≤ ab(|f ‘’(ζ)| / 2)∙(x – x0)2)dx ≤ M/2∙ab(x – x0)2dx =

= M/6∙((b – x0)3 - (b – x0)3) = M/6∙((b – ((a + b)/2))3 - (a – ((a + b)/2))3)) =

= M/6∙(((b - a) / 2)3) = M/24∙(b – a)3

Здесь М – это оценка второй производной.

Итак, оценка погрешности для пормулы прямоугольников: |R| ≤ M/24∙(b – a)3

при x0 = (a + b) / 2

Например, если f(x) = sin(x), то M = 1.
Общая формула прямоугольников

Пусть xi = a + i∙h i = 0...n h = (b – a) / 2

abf(x)dx = i=0n-1(xixi+1f(x)dx) = i=0n-1(h∙f((xi + xi+1)/2)) + R

|R| = |abf(x)dx - i=0n-1(h∙f((xi + xi+1)/2))| = | i=0n-1(xixi+1f(x)dx - h∙f((xi + xi+1)/2))| ≤

i=0n-1(M∙h3/24) = (M∙n∙h3/24)

4. Метод трапеций. Оценка погрешности.
abf(x)dx ≈ (f(a)∙H0 + f(b)∙H1)∙(b – a) = (b – a)∙(f(a) – f(b)) / 2

H0 = -1/1 ∙ 01(q∙(q –1) / q)dq = – 01(q –1)dq = – (1/2 – 1) = 1/2

H1 = 01(q∙(q - 1) / (q –1))dq = – 01(q)dq = 1/2

SABCD = (b – a)∙(f(a) + f(b)) / 2

R(h) = aa+hf(x)dx – (h/2)∙(f(a+h) + f(a)) b = a + h

Пусть fC2[a, b].

R ‘(h) = f(a + h) – (1/2)∙(f(a + h) + f(a)) – (h/2)∙f ‘(a + h) = (R(0) = 0)

= (1/2)∙(f(a + h) – f(a)) – (h/2)∙f ‘(a + h)

R ‘’(h) = (1/2)∙(f ‘(a + h)) - (1/2)∙(f ‘(a + h)) – (h/2)∙(f ‘’(a + h)) = – (h/2)∙(f ‘’(a + h))

0hR ‘’(t)dt = – (1/2)∙0ht∙f ‘’(a + t)dt = f ‘’(a + ξ1)∙0htdt

R ‘(t) |0h = - (1/2)∙0ht∙f ‘’(a + t)dt = - (1/2)∙f ‘’(ξ1)∙0htdt = - (1/2)∙f ‘’(ξ1)∙(h2/2)

Итак, R ‘(h) = - (h2/4)∙f ‘’(ξ1).

R(h) – R(0) = - (1/4)∙0ht2∙f ‘’(ξ1 + a)dt = - (1/4)∙f ‘’(ξ + a)∙0ht2dt = - (1/4)∙f ‘’(ξ + a)∙(h3/3)

R(h) = - (1/12)∙(f ‘’(ζ)∙h3 a + ξ = ζ[a, b]
Общая формула трапеций

a = x0 < x1 < ... < xn = b xi = a + i∙h h = (b – a) / 2

abf(x)dx = xx0f(x)dx + x1x2f(x)dx + ... + xn-1xnf(x)dx =

= h∙((f(x1) + f(x0) / 2) + h∙((f(x2) + f(x1) / 2) + ... + h∙((f(xn) + f(xn-1) / 2) =

= h∙((f(x0) / 2) + f(x1) + f(x2) + ... + f(xn-1) + (f(xn) / 2))

R = abf(x)dx = i=0nh∙((f(xi) + f(xi+1))/2) = i=0n-1 xixi+1f(x)dx – i=0n-1h∙((f(xi) + f(xi+1))/2) =

= i=0n-1(xixi+1f(x)dx + h∙((f(xi) + f(xi+1))/2)) = i=0n-1(– (h3/12)∙f ‘’(ξ i) ξ i(xi, xi+1)

R = (h3∙n / 12) ∙ (i=0n-1(f ‘’(ξ i)) / n ν = (i=0n-1(f ‘’(ξ i)) / n

Так как fC2[a, b] => f ‘’C[a, b] => f ‘’ ограничено на [a, b] =>

=> inf (f ‘’(x)) = m ≤ f ‘’(x) ≤ M = sup (f ‘’(x))

m = nm / n = (i=0n-1m)/n ≤ (i=0n-1(f ‘’(ξ i)) / n ≤ (i=0n-1M)/n = nM/n = M

m ≤ ν ≤ M

Следовательно сущ. ξ(a, b) : f ‘’(ξ) = ν

R = (h∙n/12)∙f ‘’(ξ)

Если |f ‘’(ξ)| ≤ M [a, b]

|R| ≤ (h3∙n/12)∙


5. Метод парабол. Оценка погрешности.
abf(x)dx ≈ (f(x0)∙H0 + f(x1)∙H1+ f(x2)∙H2)∙(b – a)







=> abf(x)dx ≈ (f(x0)/6 + f(x1)∙2/3+ f(x2)/6)∙(b – a) = (f(x0) + 4∙f(x1) + f(x2)) ∙ (b – a)/6

Это и была, собственно, формула параболы. Но когда h – большое, она не годится, потому что тогда погрешность R улетает к звёздам:

R = (h5/90)∙f(n)(ξ) ξ(a, b)
Общая формула Симпсона

Рассмотрим разбиение отрезка [a, b] – τ {x j}j=0n , n = 2m

Тогда abf(x)dx = x0x2f(x)dx + x2x4f(x)dx + ... + x(2m-2)x2mf(x)dx =

= (1/3)∙(f(x0) + 4∙f(x1) + f(x2)) + (h/3)∙(f(x2) + 4∙f(x3) + f(x4)) + ... +

+ (h/3)∙(f(x2m-2) + 4∙f(x2m-1) + f(x2m)) + R =

= (h/3)∙[(f(x0) + 4∙f(x1) + f(x3) + ... + f(x2m-1)) + 2∙(f(x2) + f(x4) + ... + f(x2m-2)) + f(x2m)] + R

R = abf(x)dx - i=1m((h/3)∙(f(x2i-2) + 4∙f(x2i-1) + f(x2i)) =

= i=1m(x(2i-2)x2if(x)dx + (h/3)∙(f(x2i-2) + 4∙f(x2i-1) + f(x2i)) = i=1m∙(h5/90)∙f(n) i) =

= - (n∙h5/90)∙((i=1mf(n) i))/m) = - (n∙h5/90)∙(f(n)(ξ))



6. Правило Рунге повышения порядка точности квадратурной формулы (правило двойного пересчёта).

7. Понятие метрического пространства, сходимость в нём, полнота пространства.
Метрическое пространство – это пара {X, p}, X – произвольное множество,

р – метрика, функция р: XxX  R (XxX = {(x, y) : x, yX})

XxX – декартово произведение

Метрика – это вектор (Х, р), удовлетворяющий аксиомам метрики:

1) p(x, y) ≥ 0 x,yX

2) p(x, y) = p (y, x) x,yX

3) p(x, y) = 0 только если x = y x,yX

4) p(x, y) ≤ p(x, z) + p(z, y) x,y,zX - фактически это теорема Пифагора

Число p(x, y) – расстояние между точками x и y.

Определение: Множество UE(a) = {xX : p(x, a) < E} называется E – окрестностью точки а.

Определение: Множество GX наз. открытым, еслиаG, E>0 : UE(a)G.

Определение: Множество F наз. замкнутым, если X \ F открыто (\ = минус)

Определение: Пусть {xn} – последовательность точек в Х.

Последовательность наз. сходящейся в точке аX если nlim p(xn, a) = 0.

Другими словами, если E > 0 nEN : n > nE будет p(xn, a) < E.

Определение: Последовательность {xn} называется фундаментальной, если

E > 0 nEN : n, m > nE будет p{xn, xm} < E.
8. Полнота пространства Rn.
Определение: Метрическое пространство, в котором всякая фундаментальная последовательность имеет предел называется полной.

Примеры полных метрических пространств:

(R, p) где p = |x – y|

(Rm, p), и p = √( i=1n(xi + yi)2), x = x1, ..., xm, y = y1, ..., ym.

Определение: Если (X, p) – МП, и MX, то (M, p) – подпространство пр-ва (X, p).

Теорема: Если (X, p) – полное МП, MX – замкн. подмн-во, то (M, p) – тоже МП.

Док-во: Возьмём произвольное {xn}, фундаментальную в М.

Так как MX, она фундаментальна и в Х. Но Х – полная МП, Значит .

Предположим, что хM. Так как М замкнуто, то Х \ М открыто, и хХ \ М =>

=> UE(x)X \ M => так как , => для UEnE : n>nE, xnUE(x).

Но xnМ, а UE(x)M = 0. Значит хМ и М – полное МП.
9. Неподвижная точка сжимающего отображения. Теорема Банаха.
Определение: Пусть А : Х  X (отображение Х в Х) и (X, p) – МП.

Отображение А называется сжимающим, еслиλ(0, 1) : p(A(x), A(y)) ≤ λ∙p(x, y)

При(x, y)X.

Обозначение: А(x) => Ax A(A(x)) => A2(x) (A2(x)X) A(Ak-1(x)) => Ak(x)

Теорема: Сжатое отображение непрерывно.

Теорема: Если f : X  X – непрерывное отображение в точке x0, то{xn}X и при будет или .

Теорема Банаха: Пусть А: ХХ сжатое отображение полного МП в себя. Тогда А имеет единственную неподвижную точку, т.е. х0Х: Ах00; при этом для хХ {Anx} сходится к неподвижной точке х0 и имеет место неравенство: (Аnx;x0)n(Ax,x)/(1-). ((0,1) : (Ax,Ay)(x,y));
10. Задача Коши для ДУ первого порядка. Разностная схема Эйлера.


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


12. Метод Эйлера-Коши.


13. Метод интегрирования систем ДУ и уравнений n-го порядка. Оценка погрешности по правилу Рунге.


14. Обращение матрицы.


15. Решение систем линейных уравнений методом квадратного корня.


16. Векторные и матричные нормы. Метрики, порождаемые нормами.
Определение: Пусть L – линейное пространство. Функция p : L  R+.

R+ = {xR : x > 0}, удовлетворяющее условиям:

1) p(x) = 0  x = 0

2) p(x + y) ≤ p(x) + p(y) x, yL

3) p(λ∙x) = |λ|∙p(x) xL и λR ...называется нормой.

p(x) = ||x||

Если в линейном пространстве введена норма, то оно называется линейным нормированным пространством. Такое пр-во автоматически становится метрическим, p(x, y) = ||x – y||:

1) p(x, y) ≥ 0 x,yX - по первой аксиоме нормы

2) p(x, y) = 0 только если x = y x,yХ - по второй её аксиоме

3) p(x, y) = p (y, x) x,yX

p(x, y) = ||x – y|| = || - (y – x)|| = |-1|∙||y – x|| = ||y – x|| = p(y, x)

4) p(x, y) ≤ p(x, z) + p(z, y) x,y,zX

p(x, y) = ||x – y|| = ||(x – z) + (z – y)|| ≤ ||x – z|| + ||z – y|| = p(x, z) + p (z, y)

Rn – множество наборов x = (x1, ..., xn) из n действительных чисел, для которых определены:

x + y = (x1,...,xn) + (y1,...,yn) = (x1+y1,...,xn+yn)

λ∙x = (λ∙x1,..., λ∙xn)

... называются линейным пространством.

Теорема: функции p1(x) : Rn  R+, p2 : Rn  R+, определённые равенствами:

p1(x) = i=1n|x i| и p2(x) = max{|x i|,...,|x n|} при x = (x1,...,xn) являются нормами.

Док-во: 1) p1(x) ≥ 0 , p2(x) ≥ 0  это вроде как очевидно

0 = p1(x) = i=1n|x i|  |x1|=...=|xn| = 0

0 = max{|x i|,...,|x n|} ≥ |x i|  |x i| ≤ 0 => xi = 0 i = 1 .. n

x + y = (x1 + y1, ..., xn + yn)

p1(x + y) = i=1n|x i+y i| ≤ i=1n|x i|+|y i| = i=1n|x i| + i=1n|x i| = p1(x) + p1(y)

|x i+y i| ≤ |x i| + |y i| ≤ p2(x) + p2(y) => max{|x1+y1|,...,|xn+yn|} ≤ p2(x) + p2(y)

p1(λ∙x) = i=1n|λ∙x i| = |λ|∙i=1n|x i| = |λ|∙p1(x)

p2(λ∙x) = max{|λ∙x1|,...,|λ∙xn|} = |λ|∙max{|x1|,..., |xn|} = |λ|∙p2(x)

Определение: Пусть в пространстве Rn введена норма вектора ||x||. Нормой матрицы A размера nxn согласованной с нормой вектора х, называется число:
  1   2

Похожие:

Задача: Пусть известно значение функции f в n точках x x n iconЗадача интерполирования состоит в том, чтобы по значениям функции f(x) в нескольких точках отрезка восстановить её значения в остальных точках этого отрезка
Й физической величины в точках, к=0,1,…, n и требуется определить её значения в других точках. Иногда возникает необходимость замены...
Задача: Пусть известно значение функции f в n точках x x n iconFaq: Численные Методы, часть V интерполирование и приближение функций
Задача интерполирования состоит в том, чтобы по значениям функции f(x) в некоторых точках отрезка восстановить ее значения в остальных...
Задача: Пусть известно значение функции f в n точках x x n iconЗадача 1 Найти критические точки функции f(X,Y), принадлежащие области D
Выбрать наибольшее Zmax и наименьшее Zmin значения функции Z=f(X,Y) в замкнутой области D, вычмслить значения функции в критических...
Задача: Пусть известно значение функции f в n точках x x n iconИнтерполирование и аппроксимация функций
Аналитическое выражение для функции не известно. Требуется приближенно вычислить значение функции в точке
Задача: Пусть известно значение функции f в n точках x x n iconЗадача 6 баллов. На координатной плоскости изображен график функции y = ax
На координатной плоскости изображен график функции y = ax2 + c (см рисунок). В каких точках график функции y = cx + a пересекает...
Задача: Пусть известно значение функции f в n точках x x n iconРешение. Испытаем поведение функции на предполагаемых точках разрыва 0 и 2, так как функции exp(x), x+4 и x
Решение. Испытаем поведение функции на предполагаемых точках разрыва 0 и 2, так как функции exp(x), x+4 и x2+1 сами по себе являются...
Задача: Пусть известно значение функции f в n точках x x n iconЗадача 6 баллов. Известно, что. Докажите, что
Первый способ. На координатной плоскости aOb неравенство задает квадрат с вершинами в точках (1; 1); (–1; 1); (–1; –1) (1; –1)*,...
Задача: Пусть известно значение функции f в n точках x x n iconЗадача Коши для обыкновенных дифференциальных уравнений Пусть требуется найти решение задачи Коши:, a ≤ x ≤ b. (1)
На отрезке [a,b] зададим конечное множество точек. Будем искать приближенное решение задачи (1) в выбранных точках xi
Задача: Пусть известно значение функции f в n точках x x n iconЗадача 6 баллов. На доске после урока алгебры остались график функции y = x
На доске после урока алгебры остались график функции y = x2 и 2007 прямых, параллельных прямой y = x, каждая из которых пересекает...
Задача: Пусть известно значение функции f в n точках x x n iconФункции. Функции предназначены для того, чтобы вычислять только одно значение, поэтому ее первое отличие состоит в том, что процедура может иметь новые значения у нескольких параметров, а функция только одно (оно и будет ее результатом)
В теле функции обязательно должен быть хотя бы один оператор присвоения, где в левой части стоит имя функции, а в правой – ее значение....
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org