Г.М. Кобельков - Курс лекций по численным методам (1160467), страница 7
Текст из файла (страница 7)
Вовсякому случае я проверял — у меня просто зашибись как всё сходится. Конечно, в словах «любой вектор» таится угроза того, чтоон случайно может оказаться собственным, и тогда он никуда с места не стронется. Поэтому лучше говорить о векторах общегоположения, которые заполняют плотное подмножество нашего пространства. А именно, это в точности те вектора, у которых всекоординаты в разложении по собственному базису ненулевые.Далее, вектор u уже выбрать легко. Чтобы максимизировать скалярное произведение, его нужно выбратьпропорциональным вектору Av и отнормировать.
После этого вычисляем µ и получаем тройку (µ, u, v), длякоторой значение kf − µuvk минимально. Это будет первым приближением.Положим теперь µ1 := µ, u1 := u, v1 := v и рассмотрим функцию f1 := f − µ1 u1 v1 . Несложно показать, чтоf1 ⊥u1 v1 в L2 (это общий факт, который в народе называют теоремой Пифагора). Теперь можно применить туже процедуру к функции f1 и найти тройку (µ2 , u2 , v2 ), которая минимизирует значение нормы kf1 − µ2 u2 v2 k,и так далее.Можно показать, чтоXL2f.(13)µi ui (x)vi (y) −−→У этого метода есть очевидные преимущества. Когда мы заранее фиксируем базис пространства L2 [0, 1] ипытаемся приближать функцию из L2 ⊗ L2 линейной комбинацией разложимых тензоров ϕi (x) ⊗ ϕj (y) прификсированном базисе, то получается плохо.
А в этом алгоритме мы на каждом шаге строим оптимальныйразложимый тензор, и получается, вообще говоря, лучше. Но недостаток тоже ясен. Этот метод хорош теоретически, но на практике мы не знаем ничего про оператор A и его собственные значения, поэтому непонятно,как этот алгоритм можно применять.3.3. Численное интегрированиеКак и в случае дифференцирования, будем приближать интегралы линейными комбинациями значенийфункции в некоторых узлах. Будем рассматривать интегралы видаI(f ) =Zbp(x)f (x) dx,(14)aгде p(x) — некоторая весовая функция. Приближения в общем виде записываются так:XI(f ) ≈ci f (xi ).(15)Один из способов численного интегрирования — приблизить функцию многочленом Лагранжа степени nи проинтегрировать его.
Естественно, значение интеграла заведомо будет точным для многочленов степени n.На практике применяются так называемые квадратурные формулы прямоугольников, трапеций и Симпсона(как частные случаи формулы Лагранжа). Они получаются из соображений того, что приближённая формуладолжна быть точной для многочленов наиболее высокой степени.Оценки погрешности для всех трёх формул будут доказаны единообразно чуть ниже.Определение.
Квадратуры с равноотстоящими узлами называются квадратурами Ньютона – Котеса.На лекциях этого определения не было, и оно было нагло сдуто из лекций Арушаняна. Также неясно, как быть с доказательствами оценок формул, которые будут ниже. На лекциях их также не было, но теоретически могут попросить вывести.233.3.1.
Формула прямоугольниковНайдём квадратурную формулу для одногоузла. Она должна быть точна на многочленах нулевой степени,.и потому имеет вид K1 (f ) = (b − a) · f a+b2(b−a)4Погрешность вычислений данной формулы R(f ) 6 kf ′ k ·и R(f ) 6 kf ′′ k ·(b−a)324 .3.3.2. Метод трапецийВ этой формуле используется два узла. Формула должна быть точной для многочленов нулевой и первойстепеней. Пусть x1 = a, x2 = b. Найдём коэффициенты: K2 (f ) = c1 f (x1 ) + c2 f (x2 ).
Имеем(b − a = c1 + c2 ,(16)b2 −a2= c1 a + c2 b.2Отсюда c1 = c2 =b−a2 .Погрешность вычислений данной формулы R(f ) = kf ′′ k ·(b−a)312 .3.3.3. Метод СимпсонаАбсолютно аналогично получается формулаK3 (f ) =b−a6a−bf (a) + 4f+ f (b) .2(17) (4) (b−a)54·Погрешность вычислений данной формулы R(f ) 6 kf ′′′ k · (b−a)192 и R(f ) 6 f2880 . Она оказывается точнойи для многочленов третьей степени за счёт симметрии узлов.3.4. Оценка погрешности квадратурных формулБудем считать, что узлы заданы. Будем проверять точность формулы I(f ) на функциях fk (x) = xk .
Пустьформула имеет видnXI(f ) =ci f (xi ).(18)i=1Получаем систему уравнений с матрицей Вандермонда:c1 + . . . + cn = I(1),c1 x1 + . . . + cn xn = I(x),c1 x21 + . . . + cn x2n = I(x2 ),. . .c xn−1 + . . . + c xn−1 = I(xn−1 ).1 1n n(19)Она имеет единственное решение, поскольку все узлы различны. Оценим погрешность: R(f ) := I(f ) − Kn (f ).Имеем R(Pm ) = 0 при m = 1, . .
. , n − 1.|R(f )| 6Zba|p| · |f − Pm | dx +nXi=1|cj | · |f (xi ) − Pm (xi )| 6Zba|p| dx · kf − Pm kC +nXi=1|ci | · kf − Pm kC ,причём можно считать, что Pm — МНРП (раз уж эта оценка верна для любого многочлена). Значит,ZX |R(f )| 6|p| dx +|ci | Em (f ),(20)(21)где Em (f ) = inf kf − Pm k (константа наилучшего приближения).Допустим, что cj > 0 и p > 0. Покажем, что в этом случае R(f ) → 0 при m → ∞. В самом деле, посколькуквадратура точна, в частности, на многочленах нулевой степени, имеемZXM :=cj = p dx,(22)откуда R(f ) 6 M · Em (f ) → 0.24В частности, получаем оценки для квадратурных формул:1· max |f (2) | · (b − a)3 ,241R2 (f ) 6· max |f (2) | · (b − a)3 ,121R3 (f ) 6· max |f (4) | · (b − a)5 .2880R1 (f ) 6(23)Теперь фиксируем число узлов n и попробуем построить квадратурную формулу, которая будет точна длямногочленов наиболее высокой степени.
У нас имеется 2n неизвестных cj и xj . Хочется ожидать, что формулаокажется точной для многочленов степени 2n − 1. Ну что же, напишем систему уравнений:I(1) = c1 + . . . + cn ,I(x) = c1 x1 + . . . + cn xn ,...(24).I(x2n−1 ) = c1 x2n−1+ . . . + cn x2n−1n1Утверждение 3.1. Существует квадратурная формула, точная на многочленах степени не выше 2n − 1. Построим систему ортогональных многочленов на отрезке [a, b] относительно веса p. Мы знаем, чтоортогональный многочлен степени n имеет ровно n простых корней.
Пусть мы уже построили квадратуру Kn ,которая точна на многочленах степени n − 1. Покажем, что за счёт выбора узлов x1 , . . . , xn можно сделать так,что она будет точна на многочленах степени не выше 2n − 1. Пусть узлы выбраны так, что ωn совпадает сприведённым ортогональным многочленом степени n.Пусть Q2n−1 — произвольный многочлен степени не выше 2n − 1. Разделим его с остатком на многочлен ωn ,получимQ2n−1 (x) = Qn−1 (x)ωn (x) + rn−1 (x).(25)Мы знаем, что I(rn−1 ) = Kn (rn−1 ).Заметим, чтоI(Qn−1 ωn ) =потому что ωn ⊥Qn−1 .
С другой стороны, имеемZKn (Qn−1 ωn ) =p(x)Qn−1 (x)ωn (x) dx = 0,(26)X(27)cj Qn−1 (xj )ω(xj ) = 0,потому что xj — корни ωn . Тогда, в силу линейности и квадратуры, и интеграла I, получимI(Q2n−1 ) = I(Qn−1 ωn ) + I(rn−1 ) = 0 + I(rn−1 ) = K(rn−1 ) = K(Qn−1 ωn ) + K(rn−1 ) = K(Q2n−1 ),(28)и мы показали, что квадратурная формула точна на многочленах степени не выше 2n − 1.
Мы доказали, что можно построить достаточно хорошую квадратурную формулу. А теперь покажем, чтоничего лучше сделать уже нельзя.Утверждение 3.2. Не существует квадратурной формулы, которая была бы точна на всех многочленахстепени 2n. В самом деле, пусть квадратурная формула точна на многочленах степени 2n.
Пусть она используетузлы x1 , . . . , xn . Рассмотрим многочлен ωn по этим узлам. Тогда, в частности, имеемZ2I(ωn ) = p(x)ω 2 (x) dx > 0,(29)а с другой стороны,Kn (ωn2 ) =Xcj ωn2 (xj ) = 0,(30)потому что это нули многочлена ωn . Противоречие. Утверждение 3.3.
Коэффициенты cj квадратурной формула Гаусса положительны. Зафиксируем некоторое k и рассмотрим многочленQ2n−2 (x) :=25ωn2 (x).(x − xk )2(31)Для него формула точна, иI := I(Q2n−2 ) =Но правая часть равенства естьI=ZnXj=1p(x)cjωn2 (x)dx > 0.(x − xk )2ωn2 (xj ),(xj − xk )2(32)(33)а здесь все слагаемые равны нулю, кроме одного (при j = k). Отсюда следует, что ck > 0. Но k можно былобрать любым, поэтому всё доказано. Значит, можно применить оценки скорости сходимости, полученные нами для квадратурных формул с неотрицательными коэффициентами.Zb|Rn (f )| 6 2 p(x) dx · E2n−1 (f ),(34)a (2n) 2nf1b−a· 2n−1 ·.E2n−1 (f ) =(2n)!22(35)3.5.
Подсчёт интегралов по составным квадратурным формулам3.5.1. Составные квадратурные формулыИз всего вышесказанного видно, как можно вычислять интегралы. Разобьём отрезок на большое числочастей N (назовём эти части Ik ) и применим на каждом отрезке какую-нибудь квадратурную формулу. Потомпросуммируем то, что получится.Например, составная квадратурная формула трапеций выглядит так:N−1Xf (a + kh) + f a + (k + 1)hI(f ) = KN (f ) =h.(36)2k=0А теперь посчитаем, насколько мы при этом наврём. На каждом шаге мы врём на величинуrk 61max |f ′′ |h3 ,12 Ik(37)поэтомуRN =N−1Xrk 6k=01max |f ′′ | · (b − a)h2 .12 [a,b](38)Но это довольно грубо, мы выносим за скобку max |f ′′ |. Давайте улучшим эту формулу:Xkгде M :=112Rbark 6N −1h2 Xmax |f ′′ | · h = M h2 + o(h2 ),Ik12(39)k=0|f ′′ | dx.3.5.2.
Правило РунгеХотелось бы иметь некоторый метод оценки погрешности квадратурной формулы даже в том случае, когда мы ничего не знаем про точное значение интеграла (именно так оно и бывает на практике). Применимквадратурную формулу для N узлов и для 2N узлов. Имеем22 I(f ) = KN (f ) + M h + o(h ), 2 2(40)hh+o. I(f ) = K2N (f ) + M24Разность значений даёт оценку для главного члена погрешности:3M h2 = K2N − KN ,4(41)откуда4 K2N − KN·.3h2Это так называемый метод Рунге оценки погрешности.M=26(42)3.5.3.
Интегрирование быстро осциллирующих функцийПусть нужно вычислить интеграл от функции f = eiωx g(x), где 1 ≪ ω. Тогда нужно взять в качестве весафункцию p = eiωx . Предполагается, что функция g уже достаточно хорошая, чтобы её можно было приближатьмногочленом Лагранжа.Итак, пусть, для простоты, всё происходит на отрезке [−1, 1]. Заменим исходный интегралZeiωx g(x) dx(43)на интегралZeiωxLn (x) dx =Xjf (xj )ZeiωxXY x − xkdx =:f (xj )Cj (ω).xj − xkj(44)k6=jЗдесь функции Cj (ω) можно вычислить точно, поскольку интеграл от квазимногочлена явно считается.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
